Embed Size (px)
Citation preview
Mathematik fur Informatiker
Wolfgang Ertel
21. Mai 2010
Vorwort
Diese erste Version eines Vorlesungsskripts der Mathematikvorlesung fur Informatiker ist ent-standen im Wintersemester 95/96. Ich habe in dieser Vorlesung nur die Numerik behandelt,obwohl ich ursprunglich auch die, fur Informatiker sehr wichtige, diskrete Mathematik behan-deln wollte. Will man in einer Vorlesung mit drei Semesterwochenstunden beides behandeln,so kann dies nur sehr oberflachlich geschehen. Ich habe mich deshalb dafur entschieden, michgenau wie meine Kollegen auf die Numerik zu konzentrieren, denn nur so ist es moglich aneinigen Stellen ein wenig in die Details zu gehen und ein tieferes Verstandnis zu erreichen.Die Vorlesung beginnt mit einer Einfuhrung in Mathematica. Mathematica ist eine funk-tionale Programmiersprache zusammen mit einer umfangreichen Progreammbibliothek furNumerik und Symbolverarbeitung und Grafik. Damit steht fur die Ubungen zur Vorlesungein leistungsfahiges Werkzeug bereit.Aus der Numerik werden neben den Grundlagen die linearen Gleichungssysteme, verschie-dene Methoden der Interpolation von Meßwerten und Approximation von Funktionen sowiedie Nullstellenberechnung fur nichtlineare Gleichungen vorgestellt. Am Ende des Semestersfolgt dann noch ein Exkurs in die angewandte Forschung, in dem gezeigt wird, wie sich z.B.im Gebiet des Benchmarking von Mikroprozessoren die Mathematik (Funktionalgleichungen)direkt auf die Praxis des Informatikers auswirkt.Fur das Erstellen der ersten Version des Skripts bedanke ich mich bei Herrn A. Rehbeck,der mit viel Engagement und Geduld und LATEX seinen Vorlesungsmitschrieb in diese Formgebracht hat.Im Sommersemester 1998 wurde das Skript erganzt durch ein Kapitel uber Statistik, einGebiet, das bisher in der Mathematik an unserer Fachhochschule zu kurz kam.Im Wintersemester 1999/2000 wurde das Layout und die Struktur verbessert sowie verschie-dene Fehler beseitigt.Im Rahmen von Anderungen der Studienordnung in der Angewandten Informatik wurdezum Sommersemester 2002 die Statistik in die Vorlesung Mathematik 2 verlagert, denndie Statistik ist fur Studenten aller Studienrichtungen relevant. Statt der Statistik solltenInhalte aufgenommen werden, die speziell fur Informatiker relevant sind. Die Erzeugung undUberprufung von Zufallszahlen ist wichtiges Thema, das nun endlich behandelt wird.Seit dem Sommersemester 2008 wird dieses Fach nur noch fur Master Informatik angeboten.Hierfur wurde das Kapitel uber Zufallszahlen ausgebaut. Eventuell werden noch weitereInhalte in die Vorlesung eingebaut. Zu einigen Themen wird auch Originalliteratur ausgeteiltwerden, die sich der Student dann selbst erarbeiten muss.
W. Ertel
Inhaltsverzeichnis
1 Computeralgebra 21.1 Symbolverarbeitung auf dem Computer . . . . . . . . . . . . . . . . . . . . . 31.2 Kurze Einfuhrung in Mathematica . . . . . . . . . . . . . . . . . . . . . . . 4
2 Zufallszahlen 92.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Pseudozufallszahlengeneratoren . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Lineare Schieberegister mit Ruckkopplung . . . . . . . . . . . . . . . . . . . 142.4 Echte Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Berechnung von Mittelwerten - Anwendung fur Funktionalgleichungen 183.1 Herleitung einer geeigneten Speedup-Formel . . . . . . . . . . . . . . . . . . 183.2 Anwendung/ Fallstudie: Randomisierte Tiefensuche . . . . . . . . . . . . . . 21
4 Numerik 244.1 Rechnen auf dem Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.2 Lineare Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.3 Interpolation mit Polynomen . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.4 Methode der kleinsten Quadrate . . . . . . . . . . . . . . . . . . . . . . . . . 444.5 Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.6 Nullstellenberechnung/ Nichtlineare Gleichungen . . . . . . . . . . . . . . . . 594.7 Numerische Integration und Monte Carlo Simulation . . . . . . . . . . . . . 70
5 Ubungsaufgaben 745.1 Computeralgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.2 Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.3 Numerik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Literaturverzeichnis 82
Kapitel 1
Computeralgebra
Definition 1.1 Computeralgebra = Symbolverarbeitung + Numerik + Grafik
Definition 1.2 Symbolverarbeitung ist das Rechnen mit Symbolen (Variablen, Kon-stanten, Funktionssymbolen), wie in Mathematikvorlesungen.
Vorteile der Symbolverarbeitung:
• oft erheblich geringerer Rechenaufwand gegenuber Numerik
• symbolisches Ergebnis (fur weitere Berechnungen), Beweise im strengen Sinn mog-lich.
Nachteile der Symbolverarbeitung:
• oft existiert keine symbolische (geschlossene) Losung →, dann wird Numerik an-gewendet, z.B. beim
– Berechnung von Stammfunktionen
– Losen von nichtlinearen Gleichungen (ex = sinx)
Beispiel 1.1
1. symbolisch:
limx→∞
(lnx
x+ 1
)′=? (Asymptotisches V erhalten)
(lnx
x+ 1
)′=
1x(x+ 1)− lnx
(x+ 1)2=
1
(x+ 1)x− lnx
(x+ 1)2
x→∞ :
(lnx
x+ 1
)′→ 1
x2− lnx
x2→ lnx
x2→ 0
1.1 Symbolverarbeitung auf dem Computer 3
2. numerisch:limx→∞
f ′(x) =?
Beispiel 1.2 Numerische Losung von x2 = 5
x2 = 5, x =5
x, 2x = x+
5
x
x =1
2
(x+
5
x
)Iteration:
xn+1 =1
2
(xn +
5
xn
)n xn0 2 ← Startwert1 2.252 2.2361113 2.236067984 2.23606798
⇒√
5 = 2.23606798± 10−8
(Naherungslosung)
1.1 Symbolverarbeitung auf dem Computer
Beispiel 1.3 Symbolisches Rechnen mit naturlichen Zahlen:Rechenregeln, d.h. Axiome notig. ⇒ Peanoaxiome z.B.:
∀x, y, z : x+ y = y + x (1.1)
x+ 0 = x (1.2)
(x+ y) + z = x+ (y + z) (1.3)
Aus diesen Regeln laßt sich z.B. 0 + x = x ableiten:
0 + x=
(1.1) x+ 0=
(1.2) x
Implementierung der Symbolverarbeitung auf dem Computer durch Ersetzungsregeln (TermRewriting).
Beispiel 1.4 (reelle Zahlen) Kettenregel fur Differenzieren:
[f(g(x))]′ ⇒ f ′(g(x))g′(x)
sin(lnx+ 2)′ = cos(lnx+ 2)1
x
Computer: (Pattern matching)
sin(Plus(lnx, 2))′ = cos(Plus(lnx, 2))Plus′(lnx, 2)
4 1 Computeralgebra
sin(Plus(lnx, 2))′ = cos(Plus(lnx, 2))Plus(ln′ x, 2′)
sin(Plus(lnx, 2))′ = cos(Plus(lnx, 2))Plus
(1
x, 0
)sin(Plus(lnx, 2))′ = cos(Plus(lnx, 2))
1
x
sin(Plus(lnx, 2))′ =cos(lnx+ 2)
x
Erfolgreiche Systeme:
• Mathematica (S. Wolfram & Co.)
• Maple(ETH Zurich + Univ. Waterloo, Kanada)
1.2 Kurze Einfuhrung in Mathematica
Demo: Mathematica
1.2.0.1 Einige Beispiele als Starthilfe
In[1]:= 3 + 2^3
Out[1]= 11
In[2]:= Sqrt[10]
Out[2]= Sqrt[10]
In[3]:= N[Sqrt[10]]
Out[3]= 3.16228
In[4]:= N[Sqrt[10],60]
Out[4]= 3.1622776601683793319988935444327185337195551393252168268575
In[5]:= Integrate[x^2 Sin[x]^2, x]
3 24 x - 6 x Cos[2 x] + 3 Sin[2 x] - 6 x Sin[2 x]
Out[5]= ------------------------------------------------24
In[7]:= D[%, x]
2 212 x - 12 x Cos[2 x]
Out[7]= ----------------------24
In[8]:= Simplify[%]
2 2Out[8]= x Sin[x]
1.2 Kurze Einfuhrung in Mathematica 5
In[9]:= Series[Exp[x], {x,0,6}]
2 3 4 5 6x x x x x 7
Out[9]= 1 + x + -- + -- + -- + --- + --- + O[x]2 6 24 120 720
In[10]:= Expand[(x + 2)^3 + ((x - 5)^2 (x + y)^2)^3]
2 3 6 7 8 9Out[10]= 8 + 12 x + 6 x + x + 15625 x - 18750 x + 9375 x - 2500 x +
10 11 12 5 6 7> 375 x - 30 x + x + 93750 x y - 112500 x y + 56250 x y -
8 9 10 11 4 2> 15000 x y + 2250 x y - 180 x y + 6 x y + 234375 x y -
5 2 6 2 7 2 8 2 9 2> 281250 x y + 140625 x y - 37500 x y + 5625 x y - 450 x y +
10 2 3 3 4 3 5 3 6 3> 15 x y + 312500 x y - 375000 x y + 187500 x y - 50000 x y +
7 3 8 3 9 3 2 4 3 4> 7500 x y - 600 x y + 20 x y + 234375 x y - 281250 x y +
4 4 5 4 6 4 7 4 8 4> 140625 x y - 37500 x y + 5625 x y - 450 x y + 15 x y +
5 2 5 3 5 4 5 5 5> 93750 x y - 112500 x y + 56250 x y - 15000 x y + 2250 x y -
6 5 7 5 6 6 2 6 3 6> 180 x y + 6 x y + 15625 y - 18750 x y + 9375 x y - 2500 x y +
4 6 5 6 6 6> 375 x y - 30 x y + x y
In[11]:= Factor[%]
2 3 4 2 3 2Out[11]= (2 + x + 25 x - 10 x + x + 50 x y - 20 x y + 2 x y + 25 y -
2 2 2 2 3 4 5 6> 10 x y + x y ) (4 + 4 x - 49 x - 5 x + 633 x - 501 x + 150 x -
7 8 2 3 4 5> 20 x + x - 100 x y - 10 x y + 2516 x y - 2002 x y + 600 x y -
6 7 2 2 2 2 3 2> 80 x y + 4 x y - 50 y - 5 x y + 3758 x y - 3001 x y +
4 2 5 2 6 2 3 2 3 3 3> 900 x y - 120 x y + 6 x y + 2500 x y - 2000 x y + 600 x y -
4 3 5 3 4 4 2 4 3 4 4 4> 80 x y + 4 x y + 625 y - 500 x y + 150 x y - 20 x y + x y )
6 1 Computeralgebra
In[12]:= InputForm[%7]
Out[12]//InputForm= (12*x^2 - 12*x^2*Cos[2*x])/24
In[20]:= Plot[Sin[1/x], {x,0.01,Pi}]
Out[20]= -Graphics-
In[42]:= Plot3D[x^2 + y^2, {x,-1,1}, {y,0,1}]
Out[42]= -SurfaceGraphics-
In[43]:= f[x_,y_] := Sin[(x^2 + y^3)] / (x^2 + y^2)
In[44]:= f[2,3]
Sin[31]Out[44]= -------
13
In[45]:= ContourPlot[x^2 + y^2, {x,-1,1}, {y,-1,1}]
Out[45]= -SurfaceGraphics-
In[46]:= Plot3D[f[x,y], {x,-Pi,Pi}, {y,-Pi,Pi}, PlotPoints -> 30,PlotLabel -> "Sin[(x^2 + y^3)] / (x^2 + y^2)", PlotRange -> {-1,1}]
Out[46]= -SurfaceGraphics-
Sin[(x^2 + y^3)] / (x^2 + y^2)
-2-1
0
1
2-2
-1
0
1
2
-1
-0.5
0
0.5
1
-2-1
0
1
2-2 -1 0 1 2
-2
-1
0
1
2
Sin[(x^2 + y^3)] / (x^2 + y^2)
In[47]:= ContourPlot[f[x,y], {x,-2,2}, {y,-2,2}, PlotPoints -> 30,ContourSmoothing -> True, ContourShading -> False,PlotLabel -> "Sin[(x^2 + y^3)] / (x^2 + y^2)"]
Out[47]= -ContourGraphics-
In[52]:= Table[x^2, {x, 1, 10}]
Out[52]= {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
1.2 Kurze Einfuhrung in Mathematica 7
In[53]:= Table[{n, n^2}, {n, 2, 20}]
Out[53]= {{2, 4}, {3, 9}, {4, 16}, {5, 25}, {6, 36}, {7, 49}, {8, 64},> {9, 81}, {10, 100}, {11, 121}, {12, 144}, {13, 169}, {14, 196},> {15, 225}, {16, 256}, {17, 289}, {18, 324}, {19, 361}, {20, 400}}
In[54]:= Transpose[%]
Out[54]= {{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,> 20}, {4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256,> 289, 324, 361, 400}}
In[60]:= ListPlot[Table[Random[]+Sin[x/10], {x,0,100}]]
Out[60]= -Graphics-
20 40 60 80 100
-0.5
0.5
1
1.5
In[61]:= x = Table[i, {i,1,6}]
Out[61]= {1, 2, 3, 4, 5, 6}
In[62]:= A = Table[i*j, {i,1,5}, {j,1,6}]
Out[62]= {{1, 2, 3, 4, 5, 6}, {2, 4, 6, 8, 10, 12}, {3, 6, 9, 12, 15, 18},> {4, 8, 12, 16, 20, 24}, {5, 10, 15, 20, 25, 30}}
In[63]:= A.x
Out[63]= {91, 182, 273, 364, 455}
In[64]:= x.x
Out[64]= 91
In[71]:= B = A.Transpose[A]
Out[71]= {{91, 182, 273, 364, 455}, {182, 364, 546, 728, 910},> {273, 546, 819, 1092, 1365}, {364, 728, 1092, 1456, 1820},> {455, 910, 1365, 1820, 2275}}
In[72]:= B - IdentityMatrix[5]
Out[72]= {{90, 182, 273, 364, 455}, {182, 363, 546, 728, 910},> {273, 546, 818, 1092, 1365}, {364, 728, 1092, 1455, 1820},> {455, 910, 1365, 1820, 2274}}
8 1 Computeralgebra
% letzten Befehl wiederholen%n Befehl Nr. n wiederholen?f Hilfe zur Funktion f??f mehr Hilfe zu f
f[x_,y_] := x^2 * Cos[y] Funktion f(x, y) definierena = 5 Variable a wird mit 5 belegt
f = x^2 * Cos[y] Variable f wird mit Ausdruck belegt(f ist Abkurzung fur x2, aber keine Funktion!)
D[f[x,y],x] part. Abl. von f nach xIntegrate[f[x,y],y] Stammfunktion von f bez. y
Simplify[expr] vereinfachenExpand[expr] auswerten
Solve[f[x]==g[x]] Gleichung losen^C Abbruch
InputForm[Expr] Umwandeln in EingabenotationTeXForm[Expr] Umwandeln in TeX-Notation
FortranForm[Expr] Umwandeln in Fortran-NotationCForm[Expr] Umwandeln in C-Notation
ReadList["daten.dat", {Number, Number}] Liest 2-spaltige Wertetabelleaus Datei
Table[f[n], {n, n_min, n_max}] Liste mit Wertenf(nmin), . . . , f(nmax)
Plot[f[x],{x,x_min,x_max}] Graph zeichnenListPlot[Liste] Wertetabelle zeichnen
Plot3D[f[x,y],{x,x_min,x_max},{y,y_min,y_max}] Graph zeichnenContourPlot[f[x,y],{x,x_min,x_max},{y,y_min,y_max}] Hohenlinien zeichnen
Display["Dateiname",%,"EPS"] auf Postcript–Datei schreiben
Tabelle 1.1: Mathematica – wichtige Befehle
Beispiel 1.5 (Berechnung von Quadratwurzeln)
(*********** Wurzel[2] iterativ **************)sqrt[a_,genauigk_] := Module[{x, xn, delta, n},
For[{delta=9999999; n = 1; x=a}, delta > 10^(-genauigk), n++,xn = x;x = 1/2(x + a/x);delta = Abs[x - xn];Print["n = ", n, " x = ", N[x,2*genauigk], " delta = ", N[delta]];
];N[x,genauigk]
]sqrt::usage = "sqrt[a,n] computes the square root of a to n digits."
Table[sqrt[i,10], {i,1,20}]
(*********** Wurzel[2] rekursiv **************)x[n_,a_] := 1/2 (x[n-1,a] + a/x[n-1,a])x[1,a_] := a
Kapitel 2
Zufallszahlen
2.1 Allgemeines
2.1.1 Anwendungen
• randomisierte Algorithmen
• stochastische Simulation (Monte-Carlo-Simulation)
• Kryptographie (z.B. Schlusselerzeugung, One-Time-Pad)
Literatur: Don Knuth “The Art of Computer Programming” Bd. 2
Eine gute Definition von Zufalligkeit gibt U. Maurer in [15]:
Definition 2.1 A random bit generator is a device that is designed to output a sequenceof statistically independent and symmetrically distributedbinary random variables, i.e.,that is designed to be the implementation of a so-called binary symmetric source(BSS). In contrast, a pseudo-random bit generator is designed to deterministically gene-rate a binary sequence that only appears as if it were generated by a BSS.
Definition 2.2 Eine binare Variable heißt symmetrisch verteilt, wenn die Wahrschein-lichkeit fur beide Werte exakt 1/2 ist.
Eine Folge ist zufallig, falls fur jede Lange ` die Verteilung aller Zeichenketten der Lange `maximale Entropie besitzt.
Definition 2.3 Ein Pseudozufallszahlengenerator (PRNG, pseudo random numbergenerator) ist ein Algorithmus, der nach Eingabe einer oder mehrer Initialisierungszahlen(seed numbers) deterministisch eine Zahlenfolge erzeugt.
10 2 Zufallszahlen
Fur kryptographische Anwendungen sehr problematisch!Alternative:Verwendung von physikalischen Zufallsereignissen, wie thermisches Rauschen oder radioak-tiver Zerfall: echte Zufallszahlen⇒ real random number generator (RRNG).Philosophie:Bis heute ist unklar ob verborgene Parameter einen scheinbar zufalligen Prozess deter-ministisch beschreiben.
2.1.2 Kolmogorov-Komplexitat
• Laßt sich eine (große) Datei komprimieren, so ist der Inhalt nicht zufallig.
• Echte Zufallszahlen lassen sich nicht komprimieren!
• Ist (31415926 . . .) zufallig?
• Nein, denn π = 3.1415926 . . . laßt sich komprimieren
• Computerprogramm kann beliebig viele Dezimalstellen von π berechnen!
Definition 2.4 Die Kolmogorov-Komplexitat einer Folge ist die Lange des kurzestenProgramms, das die Folgenglieder dieser Folge berechnen kann [21].
• Eine zufallige Folge hat unendliche Kolmogorov-Komplexitat!
• Fur die Praxis untauglich, denn die Kolmogorov-Komplexitat ist nicht berechenbar!
• Jeder PRNG erzeugt nur Zahlenfolgen endlicher Kolmogorov-Komplexitat. Also sinddiese nicht zufallig
2.1.3 Kompression von Zufallszahlenfolgen
Satz 2.1 Kein Programm kann ohne Verlust alle Dateien mit mindestens n Bit komprimie-ren (n ≥ 0).
Beispiel 2.1
Lange n Bitfolgen der Lange n Anzahl0 ε 11 0, 1 22 00, 01, 10, 11 43 000, 001, 010, 011, 100, 101, 110, 111 8
8 Folgen der Lange 3, aber nur 7 kurzere!
2.2 Pseudozufallszahlengeneratoren 11
Beweis: Angenommen, ein Programm konnte dies. Wir komprimieren mit diesem Pro-gramm (nur!) alle Dateien mit genau n Bit. Die komprimierten Dateien sind dann hochstensn− 1 Bit groß. Die Zahl der komprimierten Dateien der Großen 0 bis n− 1 ist
1 + 2 + 4 + 8 + . . .+ 2n−1 = 2n − 1.
Da es 2n Dateien mit n Bit gibt, mussen mindestens zwei Dateien auf die gleiche Datei kom-primiert werden. Damit ist die Kompression nicht verlustfrei. �
2.2 Pseudozufallszahlengeneratoren
Lineare Kongruenzgeneratoren sind rekursiv definiert durch
xn = (axn−1 + b) mod m.
mit Parametern a, b und m. [22] empfiehlt fur 32 Bit Integer Zahlen a = 7141, b = 54773und m = 259200Die Periode ist hochstens m. Warum? (siehe Aufgabe 3)
Satz 2.2 Es gelten folgende Zusammenhange zwischen der funktionalen Gestalt eines Kon-gruenzgenerators und der Periodendauer:
Rekursionsvorschrift Periodendauerxn = f(xn−1) mod m ≤ mxn = f(xn−1, xn−2) mod m ≤ m2
xn = f(xn−1, xn−2, xn−3) mod m ≤ m3
. . .
Beweis: Da es beim Modul m nur m verschiedene Werte fur xn gibt, und f determini-stisch ist, mussen sich bei der ersten Wiederholung einer Zahl alle folgenden Zahlen auchwiederholen, wenn xn von einem Vorganger abhangt. Also: Periode ≤ m. Hangt f von zweiVorgangern ab, so gibt es m2 Kombinationen von Vorgangern. Also ist die Periode durch m2
beschrankt, usw. �
Offenbar kann die Periode immer langer werden, je mehr Vorganger einen Einfluss auf xnhaben. Also liegt es nahe, moglichst viele Vorganger zu verwenden, im Extremfall alle schonberechneten Vorganger. Wir versuchen es mit der Summe aller Vorganger und erhalten alsBerechnungsvorschrift
x0 = a, xn =
(n−1∑i=0
xi
)mod m,
die vielleicht sogar zu einer nicht periodischen Folge fuhrt, denn die Zahl der verwendetenVorganger wird immer großer.Leider wird diese Hoffnung grundlich enttauscht. Betrachten wir die angegebene Folge mitx0 = 1 erst mal nicht modular:
1, 1, 2, 4, 8, 16, 32, 64, 128, 256, . . .
Offenbar ist dies die Folge der Zweierpotenzen und es gilt:
12 2 Zufallszahlen
Satz 2.3 Fur die durch x0 = 1, xn =∑n−1
i=0 xi rekursiv definierte Folge gilt fur n ≥ 1 dieFormel xn = 2n−1.
Bevor wir diesen Satz beweisen, betrachten wir seine Konsequenzen im modularen Fall. Auchfur die modulare Folge x0 = 1, xn =
(∑n−1i=0 xi
)mod m gilt xn = 2n−1 mod m falls n ≥ 1.
Also hangt xn nur von xn−1 ab und m ist eine obere Schranke fur die Periode.Die Periode der Folge ist sogar ≤ m− 1, denn sobald eine Null in der Folge vorkommt, wirddie Folge konstant gleich Null.Beweis: von Satz 2.3: Fur n ≥ 2 gilt
xn =n−1∑i=0
xi = xn−1 +n−2∑i=0
xi = xn−1 + xn−1 = 2 · xn−1.
Fur n = 1 gilt x1 = x0 = 1. Nun laßt sich leicht per Induktion zeigen, dass xn = 2n−1 furn ≥ 1 (siehe Aufgabe 3). �
Nicht nur die Periodendauer ist wichtig fur die Qualitat eines PRNG. Die Symmetrie derBits sollte auch moglichst gut sein.
2.2.1 Der Symmetrietest
Im Prinzip ist es einfach, eine Bitfolge auf Zufalligkeit zu testen. Man bildet den Mittelwert
M(X1, . . . , Xn) =1
n
n∑i=1
xi
der n Bits der Folge und vergleicht ihn mit dem Erwartungswert E(X) = 1/2 einer echtenZufallsbitfolge. Ist die Abweichung des Mittelwerts vom Erwartungswert klein genug, sobesteht die Folge den Test.Nun wollen wir eine Schwelle fur die noch tolerierbare Abweichung berechnen. Der Erwar-tungswert eines echten Zufallsbits X ist E(X) = 1/2 und auch seine Standardabweichungσ(X) = 1/2 (siehe Aufgabe 4). Bei der Mittelung uber n echte Zufallsbits wird der Mit-telwert umso weniger vom Erwartungswert abweichen, je großer n wird. Der folgende Satzmacht dazu eine quantitative Aussage:
Satz 2.4 (Zentraler Grenzwertsatz) Sind X1, X2, . . . unabhangige identisch verteilte Zu-fallsvariable mit σ(Xi) <∞ und ist
Sn = X1 + . . .+Xn,
so strebt Sn fur n→∞ gegen eine Normalverteilung mit dem Erwartungswert nE(X1) undder Standardabweichung
√nσ, d.h. es gilt
limn→∞
sup{|Sn(x)− ϕnE(X1),√nσ(X1)(x)| : x ∈ R} = 0.
2.2 Pseudozufallszahlengeneratoren 13
Definition 2.5 Die Normalverteilung mit Erwartungswert µ und Standardabweichungσ hat die Dichte
ϕµ,σ(x) =1√2πσ
exp
(−(x− µ)2
2σ2
).
Aus diesem Satz ergeben sich einige wichtige Folgerungen:
• Die Summe identisch verteilter unabhangiger Zufallsvariablen strebt asymptotisch ge-gen eine Normalverteilung.
• Der Mittelwert aus den n unabhangigen Meßwerten einer Zufallsgroße ist naherungswei-se normalverteilt. Die Naherung gilt umso besser, je mehr Messungen gemacht werden.
• Die Standardabweichung einer Summe X1 + . . .+Xn von identisch verteilten Zufalls-variablen ist gleich
√nσ(X1).
Fur die Standardabweichung σn des Mittelwerts
M(X1, . . . , Xn) =1
n
n∑i=1
xi
der n Zufallsbits vom Erwartungswert ergibt sich also
σn =1
n
√nσ(X1) =
1√nσ(X1)
Da eine normalverteilte Zufallsvariable mit Wahrscheinlichkeit 0.95 im Intervall [µ− 2σ, µ+2σ] liegt, nennt man dieses Intervall Konfidenzintervall zum Niveau 0.95.Da bei den Zufallsbits σ(X1) = 1/2 ist, ergibt sich
σn =1
2√n
Wir definieren den Test auf Zufalligkeit als bestanden, wenn der Mittelwert der Bits imIntervall [1/2− 2σn, 1/2 + 2σn, ] liegt.
2.2.2 BBS-Generator
Auch Polynomiale Kongruenzgeneratoren der Form
xn = (akxkn−1 + ak−1x
k−1n−1 + . . .+ a0) mod m.
konnen geknackt werden. Daher liegt es nahe, nach besseren Generatoren zu suchen. EinPRNG, der Bits sehr guter Qualitar erzeugt, ist der sogenannte BBS-Generator (siehe [20].)Wahle Primzahlen p und q mit
p ≡ q ≡ 3 mod 4.
Berechne n = p · q und wahle eine Zufallszahl s, mit ggT(s, n) = 1.Berechne den Seed
x0 = s2 mod n.
14 2 Zufallszahlen
Der Generator berechnet nun, beginnend mit i = 1 wiederholt
xi = (xi−1)2 mod n
bi = xi mod 2,
Bit bi wird als i− tes Zufallsbit ausgegeben.BBS gilt als sehr gut, aber:Ein mit BBS betriebenes One-Time-Pad ist so sicher wie eine Chiffre mit einen Schlussel derLange |s|.
2.3 Lineare Schieberegister mit Ruckkopplung
Definition 2.6
• Ein Schieberegister der Lange n besteht aus einem Bitvektor (xn, . . . , x1). In jedemRechenschritt werden die Bits um eine Stelle nach rechts verschoben, d. h.
xn 7→ xn−1 , . . . , x2 7→ x1
und es wird links ein neues Bit In nachgeschoben sowie das letzte Bit Out ausgegeben:
In 7→ xn, x1 7→ Out .
• Ein lineares Schieberegister mit Ruckkopplung (LFSR) berechnet die Einga-be (In) durch Addition modulo 2 von bestimmten Bits des Registers. (LFSR ist dieAbkurzung von linear feedback shift register.)
Beispiel 2.2 LFSR1:
x3 x x2 1
1 1 1
x3 x2 x1 Out1 1 1
0 1 1 1
1 0 1 1
1 1 0 1
0 1 1 0
Periode 3.
Beispiel 2.3 LFSR2 hat die Periode 7:
1 1 1
x3 x2 x1 Out1 1 10 1 1 1
1 0 1 1
0 1 0 1
0 0 1 0
1 0 0 1
1 1 0 0
1 1 1 0
2.3 Lineare Schieberegister mit Ruckkopplung 15
Die maximale Periode eines LSFR der Lange n ist 2n − 1.
Beispiel 2.4 Analyse eines LFSR der Lange 3Wir beobachten die Bitfolge
B = (01110010)
und suchen die Parameter a1, a2, a3.
1 1 0
a3 a a2 1
Das LFSR lasst sich mathematisch darstellen durch die Abbildung
(x3, x2, x1) 7→ (a1x1 ⊕ a2x2 ⊕ a3x3, x3, x2),
welche iterativ wiederholt wird. Die ersten drei Bit der Folge B geben den Zustand des LFSRzu einem bestimmten Zeitpunkt an, d. h. x1 = 0, x2 = 1, x3 = 1Zustand des LFSR: (1, 1, 0)Je eine Zeiteinheit spater gilt fur den Zustand
(1, 1, 1) = (a2 ⊕ a3, 1, 1) (2.1)
(0, 1, 1) = (a3 ⊕ a2 ⊕ a1, 1, 1) (2.2)
(0, 0, 1) = (a2 ⊕ a1, 0, 1) (2.3)
Aus (2.1), (2.2), (2.3) erhalt man die Gleichungen
a2 ⊕ a3 = 1 (2.4)
a3 ⊕ a2 ⊕ a1 = 0 (2.5)
a2 ⊕ a1 = 0 (2.6)
und berechnet
(2.4) in (2.5) : 1⊕ a1 = 0 ⇒ a1 = 1 (2.7)
(2.7) in (2.6) : a2 ⊕ 1 = 0 ⇒ a2 = 1 (2.8)
(2.8) in (2.4) : a3 = 0 (2.9)
Das Schieberegister hat also die Form
1 1 0
und die Folge der Zustande einer Periode von LFSR3 ist
1 1 01 1 1 0
0 1 1 1
0 0 1 1
1 0 0 1
0 1 0 0
1 0 1 0
1 1 0 1
0
16 2 Zufallszahlen
Man beachte, dass zur Analyse nur sechs Bit der Ausgabefolge benutzt wurden und dassLFSR3 maximale Periode hat.
Allgemein kann man zeigen, dass zur Analyse eines linearen Schieberegisters hochstens 2nBit der Ausgabefolge benotigt werden. (Berlekamp-Massey-Algorithmus)
Definition 2.7 Die lineare Komplexitat einer Folge ist die Lange des kurzesten LFSR,das die Folge erzeugen kann.
Besitzt also eine Schlusselfolge endliche lineare Komplexitat n, so werden nur 2n Bit derFolge benotigt, um den Code der zugehorigen Stromchiffre zu knacken.⇒ Kolmogorov-Komplexitat.
2.4 Echte Zufallszahlen
• Spezialhardware
◦ Physikalische Rauschquelle, AD-Wandler, Verstarker, Filter, Test(?)
◦ Spezialhardware (thermisches Rauschen) fur Testzwecke
◦ Spezialhardware fur kryptographische Anwendungen zu teuer
• Intel: thermisches Rauschen eines Widerstands im Pentium-III-Prozessor
◦ Frequenz: 75000 Bits pro Sekunde [23, 17]
• Maxtor: Rauschen von IDE-Festplatten
◦ Frequenz: 835200 Bits pro Sekunde [18]
2.4.1 Der Neumann-Filter
John von Neumann, 1963
f : 00 7→ ε
11 7→ ε
01 7→ 0
10 7→ 1,
ε = leere Zeichekette
Beispiel 2.5 10001101011100101110 7→ 10011
Beispiel 2.6 11111111111111111111 7→ ε
Beispiel 2.7 10101010101010101010 7→ 1111111111
Allgemein gilt:
2.4 Echte Zufallszahlen 17
Satz 2.5 Sind aufeinanderfolgende Bits in einer langen (n → ∞) Bit-Folge statistisch un-abhangig, so sind nach Anwendung des Neumann-Filters die Bits symmetrisch verteilt. DieLange der Bit-Folge verkurzt sich dabei um den Faktor p(1− p).
Beweis: Wenn in der Folge a die Bits unabhangig sind und mit Wahrscheinlichkeit p denWert “1” annehmen, dann ist die Wahrscheinlichkeit fur ein Paar “01” gleich p(1 − p). DieWahrscheinlichkeit fur ein Paar“10” ist auch gleich p(1−p). Damit ist die Wahrscheinlichkeitpn fur den Wert “1” nach Anwendung des Neumann-Filters gegeben durch
pn =p(1− p)2p(1− p)
= 1/2.
Fur den Beweis des Verkurzungsfaktors wird auf Ubung 7 verwiesen. �
2.4.2 Einfluß der Asymmetrie auf die Ausbeute des Neumann-Filters
00.050.1
0.150.2
0.25
0 0.2 0.4 0.6 0.8 1
p(1-p)
p
Kapitel 3
Berechnung von Mittelwerten -Anwendung fur Funktionalgleichungen
3.1 Herleitung einer geeigneten Speedup-Formel
Aufgabe:Vergleich der Laufzeiten von 3 Computern
• Computer A: SUN-SPARC classic
• Computer B: PC Pentium 90 xxx
• Computer C: HP 9000/720
Vorgehen:
Beispiel 3.1 Laufzeit von Programm 1
Computer Laufzeit TX Speedup TA/TXCA 10.4 sec 1CB 8.1 sec 1.28CC 7.9 sec 1.32
Problem 1 Ergebnis ist nicht reprasentativ, denn:
Beispiel 3.2 Laufzeit von Programm 2
Computer Laufzeit TX Speedup TA/TXCA 2.7 sec 1CB 4.3 sec 0.63CC 2.6 sec 1.04
Losung 1 messe Laufzeiten auf reprasentativer Menge von Benchmarks (bestimmt auf Grundvon Statistik der benutzten Anwendungen eines typischen Benutzers).
Beispiel 3.3 Benchmarks I1, I2, I3
3.1 Herleitung einer geeigneten Speedup-Formel 19
Computer I1 I2 I3 TCA 1 2 100 34.3CB 2 4 47 17.7
⇒ Speedup TA/TB = 1.93⇒ CB doppelt so schnell wie CA?Nein, nur fur Benchmark I3
Problem 2 Speedup S1 = TA/TB ist relatives Maß, aber im vorigen Beispiel wird S nurdurch Benchmark I3 (großter Wert) bestimmt.
Definition 3.1 Seien x1, . . . , xn ∈ R, dann heißt A : Rn → R mit
A(x1, . . . , xn) =1
n
n∑k=1
xk
arithmetisches Mittel von x1, . . . , xn.
Definition 3.2 Seien α1, . . . , αn (β1, . . . , βn) die Laufzeiten von Computer A (ComputerB) auf den Benchmarks I1, . . . , In. Dann ist der (Operator-) Speedup S1 definiert als:
S1(CA, CB) =A(α1, . . . , αn)
A(β1, . . . , βn)=
∑nk=1 αk∑nk=1 βk
Losung 2 berechne Summe der Quotienten statt Quotient der Summen!
Definition 3.3
S2(CA, CB) = A
(α1
β1
, . . . ,αnβn
)=
1
n
n∑k=1
αkβk
Anwendung von S2 auf voriges Beispiel:
S2(CA, CB) = A(1
2,1
2,100
47) =
12
+ 12
+ 10047
3= 1.04
S2(CB, CA) = A(2, 2,47
100) =
2 + 2 + 0.47
3= 1.49
⇒ CA besser als CB, oder CB besser als CA?
Problem 3 S2(CA, CB) 6= 1
S2(CB, CA)
Beispiel 3.4 Berechnung des Speedup
20 3 Berechnung von Mittelwerten - Anwendung fur Funktionalgleichungen
Computer Laufz. bei Benchm. I1 Laufz. bei Benchm. I2
CA 1 10CB 10 1
S2(CA, CB) = S2(CB, CA) =
(1
10+ 10
)· 1
2= 5.05
Erwartung: S2 = 1!
Vermutung: geometrisches Mittel lost Problem
Definition 3.4 Fur x1, . . . , xn ∈ R{0} heißt G : R→ R mit
G(x1, . . . , xn) = n√x1 · . . . · xn
geometrisches Mittel von x1, . . . , xn
Definition 3.5
S3(CA, CB) = G
(α1
β1
, . . . ,αnβn
)= n
√√√√ n∏k=1
αkβk
heißt Benutzer-Speedup.
Bemerkung:S3 lost Problem 3 und Problem 4!
z.B. S3(CA, CA) = G(1, . . . , 1) = 1
S3(CA, CB) = n
√√√√ n∏k=1
αkβk
=n∏k=1
α1/nk
β1/nk
=1∏n
k=1
β1/nk
α1/nk
=1
S3(CB, CA)
Forderungen an eine Speedup-Funktion (von relativen Großen)
1. M(x, . . . , x) = x
2. M(x1, . . . , xn) ·M(y1, . . . , yn) = M(x1y1, . . . , xnyn)
3. M(x1, . . . , xk) = M(xπ(1), . . . , xπ(k)) fur jede Permutation π auf {1, . . . , k}
Begrundung von Forderung 2:
CA CB CC10x 2x
20x
- -
-
3.2 Anwendung/ Fallstudie: Randomisierte Tiefensuche 21
S(CA, CB) · S(CB, CC) = S(CA, CC)
⇔M(α1
β1
, . . . ,αnβn
) ·M(β1
γ1
, . . . ,βnγn
) = M(α1
γ1
, . . . ,αnγn
)
⇔M(x1, . . . , xn) ·M(y1, . . . , yn) = M(x1y1, . . . , xnyn)
Satz 3.1 Die eindeutig bestimmte Funktion M : Rn → R+, die die Forderungen 1,2,3 erfullt,ist das geometrische Mittel G(x1, . . . , xn).
Beweis:
M(x1, . . . , xn)n = M(x1, . . . , xn) ·M(x2, . . . , xn, x1) · . . . ·M(xn, x1, . . . , xn−1)
= M(x1 · . . . · xn, . . . , x1 · . . . · xn)
= x1 · . . . · xn
3.2 Anwendung/ Fallstudie: Randomisierte Tiefensu-
che
Randomisierte Algorithmen
Definition 3.6 Ein Algorithmus A, der neben seiner Eingabe I eine Folge von Zufalls-zahlen erhalt, heißt randomisierter Algorithmus.
Bemerkung:Im allgemeinen hangt fur feste Eingabe I die Laufzeit von A von den Zufallszahlen ab.
Beispiel 3.5 Suche nach der”Stecknadel im Heuhaufen“ (kombinatorische Suche)
1 2
3 4
5 6
7 8
zu durchsuchender Bereich
����
��
HHHH
HH���
@@@
���
@@@
�� @@ �� @@ �� @@ �� @@e e e e e u e e1 2 3 4 5 6 7 8
Suchbaum
ue Erfolg (success)Fehler (fail)
Algorithmus terminiert, wenn eine Losung gefunden wurde.Tiefensuche mit Backtracking
22 3 Berechnung von Mittelwerten - Anwendung fur Funktionalgleichungen
backtrack(node)
IF (node = success) THEN exit(success);
ELSE IF (node = fail) THEN exit(fail);
ELSE backtrack(left_successor(node));
backtrack(right_successor(node));
ENDIF;
ENDIF;
END;
backtrack(tree) durchsucht den Binarbaum tree rekursiv bis eine Losung gefunden wurdeund gibt dann success aus.
Beispiel 3.6 4 verschiedene Baume mit je 1 Losung:�
��
@@@
�� @@ �� @@e e u eRechenzeit t = 5
���
@@@
�� @@ �� @@u e e eRechenzeit t = 2
6
-
n(t)
t
1 u u u u1 2 3 4 5 6
Laufzeiten: t = 2, 3, 5, 6
����
��
HHHH
HH�
��
@@@
���
@@@
�� @@ �� @@ �� @@ �� @@e e e e e e e e1 2 3 4 5 6 7 8
6
-
n(t)
t
1
3 4 6 7 10 11 13 14
u u u u u u u u
���������
PPPPPPPPP���
@@@
���
@@@
���
@@@
�� AA �� AA �� AA �� AA �� AA �� AA �� AA �� AA �� AA
6
-
n(t)
t
1
3 4 5 7 8 9 11 12 13 16 17 18
u u u u u u u u u u u u
Randomisiertes Backtracking: zufallige Wahl von linkem/rechtem Nachfolger.⇒ mogliche Laufzeiten entsprechend n(t) (Laufzeitverteilung).Wahrscheinlichkeit fur bestimmte Laufzeit p(t):
p(t) =n(t)∑tmax
t=1 n(t)
3.2 Anwendung/ Fallstudie: Randomisierte Tiefensuche 23
benutzter Speedup (Quotient der Mittelwerte):
S(k) = S1(C1, Cp) =E(T1)
E(Tp)=A(C1)
A(Cp)
Problem 4 Streuung des Speedups?
Speedup ist eine Zahl, hat keine Streuung!⇒ neue Definition
⇒ S3(C1, Cp) = G
(α1
β1
, . . . ,αnβn
)?
nicht sinnvoll, da Zuordnung αi ↔ βi nicht besteht!aber:
S3(CA, CB) = G
(α1
β1
, . . . ,α1
βm;α2
β1
, . . . ,α2
βm; . . . ;
αnβ1
, . . . ,αnβm
)Es werden alle moglichen Quotienten berechnet.⇒ Vorgehen wie oben, aber Forderung 2 sinnlos⇒ andere Axiome ⇒ anderer (schwierigerer) Beweis.
Kapitel 4
Numerik
4.1 Rechnen auf dem Computer
4.1.1 Gleitpunktzahlen
Die Menge der Gleitpunktzahlen zur Basis β mit t Nachkommastellen und Exponenten zwi-schen m und M laßt sich formal beschreiben durch die Menge
F (β, t,m,M) = {d : d = ±.d1d2 . . . dt · βe} ∪ {0} ⊂ Q
mit
β ∈ N0 ≤ di ≤ β − 1 di : Ziffern, d1 6= 0
d1, d2, . . . , dt : Mantisse
t : Mantissenlange
e : Exponent mit m ≤ e ≤M m,M ∈ ZF (β, t,m,M) : Menge der Gleitpunktzahlen
Die Gleitpunktzahl ±.d1d2 . . . dt · βe hat den Wert
d = ±(d1β
e−1 + d2βe−2 + · · ·+ dtβ
e−t)Beispiel 4.1 Sei β = 2 und t = 3 vorgegeben, das heißt wir betrachten dreistellige Zahlenim Binarsystem. Die Zahl 0.101 · 221 hat den Wert
0.101 · 221 = 1 · 220 + 0 · 219 + 1 · 218 = 220 + 218.
Im Dezimalsystem mit β = 10 benotigen wir eine sechsstellige Mantisse (t = 6), um dieseZahl darzustellen:
220 + 218 = 1310720 = 0.131072 · 107.
4.1.1.1 Verteilung von F (β, t,m,M)
|F (β, t,m,M)| = 2︸︷︷︸±
(M −m+ 1)︸ ︷︷ ︸Exponenten
(βt − β(t−1))︸ ︷︷ ︸Mantissen
+ 1︸︷︷︸0
4.1 Rechnen auf dem Computer 25
Beispiel 4.2 F (2, 3,−1, 2)
mit obiger Formel gilt:
|F (2, 3,−1, 2)| = 2(4)(23 − 22) + 1 = 33
⇒ es gibt nur 0 und 32 verschiedene Zahlen zwischen
±0.100 · 2−1 als betragsmaßig kleinste Zahlen und±0.111 · 22 als betragsmaßig großte Zahlen
Die positiven Elemente ≥ 0 von F(2,3,-1,2) sind
0;1
4,
5
16,3
8,
7
16;1
2,5
8,3
4,7
8; 1,
5
4,3
2,7
4; 2,
5
2, 3,
7
2
Verteilung auf der Zahlengeraden:
21 3 41/20
Lücke bei der Null
1/4
Probleme:
• Exponentenuberlauf (overflow)
• Exponentenunterlauf (underflow)
• Rundungsfehler
4.1.2 Rundungsfehler
4.1.2.1 Rundungs-/Abschneidefehler (absolut)
Definition 4.1 flc, flr :[−0.α . . . α · βM , 0.α . . . α · βM
]→ F (β, t,m,M) mit α =
β − 1
Runden: x 7→ flr(x) = nachster Nachbar von x in F (β, t,m,M)
Abschneiden: x 7→ flc(x) = max {y ∈ F (β, t,m,M)|y ≤ x} = betragsmaßig nachst klei-nere Zahl von x.
Es gilt:
absoluter Rundungsfehler = |flr(x)− x| ≤ 1
2βe−t
aboluter Abschneidefehler = |flc(x)− x| < βe−t
26 4 Numerik
Beispiel 4.3 β = 10︸ ︷︷ ︸10er System
,
2stellige Mantisse︷ ︸︸ ︷t = 2 , e = 3︸ ︷︷ ︸
Exponent
x = 475flr(x) = 0.48 · 103 ← Rundenflc(x) = 0.47 · 103 ← Abschneiden
|flr(x)− x| = |480− 475| = 5 ≤ 1
2· 103−2 = 5
|flc(x)− x| = |470− 475| = 5 < 103−2 = 10
4.1.2.2 Rundungs-/Abschneidefehler (relativ)
|flr(x)− x||x|
≤ 1
2β1−t
|flc(x)− x||x|
< β1−t
Beispiel 4.4 relativer Rundungsfehler
|480− 475||475|
=1
95≤ 1
2·10−1 =
1
20
→ obere Schranke fur kleinsteZahl!
|110− 105||105|
=1
21<
1
20
Bei fester Stellenzahl wird rela-tiver Fehler bei kleineren Zahlengroßer!
Beispiel 4.5 t=3, β = 10
110 · 105 = 11550 6= 11600 = flr(11550)
Achtung:Korperaxiome verletzt!F (β, t,m,M) ist bezuglich der Multiplikation nicht abgeschlossen.
Sei ? ∈ {+,−, ·, div}
∃x, y ∈ F (β, t,m,M) : flr(x ? y) 6= x ? y
4.1.3 Ausloschung
Beispiel 4.6 Sei β = 10 und t = 8
a = 0.1 · 109
b = 0.1 · 101
c = −0.1 · 109
a+ b+ c = 0.1 · 101 = 1
flr (flr (a+ b) + c) = 0.1 · 109 − 0.1 · 109 = 0
flr (a+ flr (b+ c)) = 0.1 · 109 − 0.1 · 109 = 0
flr (flr (a+ c) + b) = 0 + 0.1 · 101 = 1
4.1 Rechnen auf dem Computer 27
⇒ Assoziativgesetz gilt nicht in F (β, t,m,M)
4.1.4 Kondition
Beispiel 4.7 Losen des linearen Gleichungssystems
x+ ay = 1
ax+ y = 0
x− a2x = 1
x =1
1− a2fur a 6= ±1
a = 1.002 = exakter Werta = 1.001 = Messung bzw. Rundungsfehler
relativer Fehler:
∣∣∣∣ a− aa∣∣∣∣ =
1
1002
Losung:
x ≈ − 1
0.004≈ −249.75
x ≈ − 1
0.002≈ −499.75
⇒ relativer Fehler
∣∣∣∣ x− xx∣∣∣∣ ≈ ∣∣∣∣ −250
249.75
∣∣∣∣ = 1.001 (100% Fehler)
Siehe Abb. 4.1.
Matrix A =
(1 aa 1
)ist singular fur a = 1, d.h. det
(1 11 1
)= 0
Definition 4.2 Sei P das Problem, die Funktion f(x) bei gegebenen Eingabedaten x zuberechnen. Die Konditionszahl Cp ist der Faktor, um den ein relativer Fehler ∆x
xin den
Eingabedaten durch f verstarkt wird, d.h.∣∣∣∣f(x+ ∆x)− f(x)
f(x)
∣∣∣∣ = Cp
∣∣∣∣∆xx∣∣∣∣
Damit gilt
Cp =
∣∣∣∣(f(x+ ∆x)− f(x))/f(x)
∆x/x
∣∣∣∣ ≈ ∣∣∣∣f ′(x)
f(x)x
∣∣∣∣Beispiel 4.8 Berechnung von Cp
x = f(a) =1
1− a2f ′(a) =
2a
(1− a2)2
Cp ≈∣∣∣∣ 2a
(1− a2)2(1− a2)a
∣∣∣∣ =
∣∣∣∣ 2a2
1− a2
∣∣∣∣ = 501.5
28 4 Numerik
a
x
-1 1
x
a
Abbildung 4.1: Verstarkung des Eingangsfehlers bei schlechter Kondition.
direkte Rechnung (s.o.): Cp ≈ 1002Faktor 2 wegen Linearisierung von f in a!
Definition 4.3 Ein Problem heißt schlecht (gut) konditioniert, wenn Cp � 1(Cp < 1 oder Cp ≈ 1)
Bemerkung: Cp hangt von den Eingabedaten ab!
4.2 Lineare Gleichungssysteme 29
4.2 Lineare Gleichungssysteme
siehe [1]
4.2.1 Losen von linearen Gleichungssystemen (Gauß-Verfahren)
Lineares Gleichungssystem L:
a11x1 + a12x2 + · · · + a1nxn = b1
a21x1 + a22x2 + · · · + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .an1x1 + an2x2 + · · · + annxn = bn
aij ∈ R n ≥ 1
Fragen:
• Ist L losbar?
• Ist L eindeutig losbar?
• Wie berechnet man die Losungen?
• Gibt es einen effizienten Algorithmus?
4.2.1.1 Das Eliminationsverfahren
a11x1 + a12x2 + · · · + a1nxn = b1
a22x2 + · · · + a2nxn = b2
akkxk + · · · + akjxj + · · · + aknxn = bk...
......
aikxk + · · · + aijxj + · · · + ainxn = bi...
......
ankxk + · · · + anjxj + · · · + annxn = bn
Der Algorithmus:
for k=1,...,n-1
suche a_mk mit |a_mk|=max{ |a_lk| : l >= k }
if a_mk=0 print "singulaer"; stop
vertausche Zeile m mit Zeile k
for i=k+1,...,n
q_ik:=a_ik/a_kk
for j=k+1,...,n
a_ij:=a_ij - q_ik*a_kj
end
b_i:=b_i - q_ik*b_k
end
end
30 4 Numerik
Satz 4.1 Komplexitat: Die Zahl der Operationen der Gauß-Elimination ist fur große nungefahr gleich 1
3n3.
Beweis:
1. Schritt:
Zeilen︷ ︸︸ ︷(n− 1)
Spalten︷ ︸︸ ︷(n− 1 + 2) Operationen
k-ter Schritt: (n− k)(n− k + 2) Operationen
gesamt:
T (n) =n−1∑k=1
(n− k)(n− k + 2)l:=n−k︷︸︸︷
=n−1∑l=1
(l(l + 2))
=n−1∑l=1
(l2 + 2l) =n3
3− n2
2+n
6+ n(n− 1)
=n3
3+n2
2− 5
6n
⇒ fur große n:n3
3
Beispiel 4.9 Rechner mit 1 GFLOPS
n T (n)10 1/3 · 103 · 10−9 sec ≈ 0.3 µsec
100 1/3 · 1003 · 10−9 sec ≈ 0.3 msec1000 1/3 · 10003 · 10−9 sec ≈ 0.3 sec
10000 1/3 · 100003 · 10−9 sec ≈ 300 sec = 5 min
Probleme/Verbesserungen:
1. lange Rechenzeiten fur große n
• bessere Algorithmen
T (n) = C · n2.38 statt1
3n3
• Iterationsverfahren (Gauß-Seidel)
2. Rundungsfehler
• vollstandige Pivotisierung
• Gauß-Seidel
Anwendungen:
• Konstruktion von Kurven durch gegebene Punkte
4.2 Lineare Gleichungssysteme 31
• Schatzen von Parametern (Methode der kleinsten Quadrate)
• Lineare Optimierung
• Computergraphik, Bildverarbeitung (z.B. Computertomographie)
• Numerisches Losen von Differentialgleichungen
4.2.1.2 Ruckwartseinsetzen
Nach n-1 Eliminationsschritten:
A′x = b mit A′ =
a′11 a′12 · · · a′1n0 a′22 · · · a′2n
0 0. . .
...0 0 0 a′nn
Berechnung von x1, . . . , xn:
xn =bna′nn
xn−1 =bn−1 − a′n−1,nxn
a′n−1,n−1
allgemein:
xi =bi −
∑nk=i+1 a
′ikxk
a′ii
i = n, n− 1, . . . , 1
Rechenzeit:
• Divisionen: n
• Zahl der Additionen und Multiplikationen:
n∑i=1
(i− 1) =n−1∑i=1
i =1
2n(n− 1) ≈ 1
2n2
⇒ Einsetzen ist viel schneller als Elimination!
Satz 4.2 Korrektheit: Das Gauß-Verfahren liefert eine eindeutige Losung (x1, . . . , xn) ge-nau dann, wenn das Gleichungssystem L die eindeutige Losung (x1, . . . , xn) besitzt.
Beweisidee:Losungsmenge invariant gegenuber Addition von Gleichungen, Multiplikation mit konstan-tem Faktor, sowie Vertauschung von Gleichungen.Singularitat → lineare Algebra
32 4 Numerik
4.2.2 Iterative Verbesserung der Losung
Sei x die mit dem Gauß-Verfahren berechnete Losung von Ax = b. Im Allgemeinen istAx = b− r mit r 6= 0 (r: Residuenvektor) wegen x = x+ ∆x.
⇒ Ax = A(x−∆x) = b− r
A ·∆x = r
Aus dieser Gleichung kann man die Korrektur ∆x berechnen. ⇒ bessere Naherung fur x:
x(2) = x+ ∆x
Iterationsverfahren:
x(1) := x
fur n = 1, 2, 3, . . .:
r(n) = b− Ax(n)
berechne ∆x(n) nach A∆x(n) = r(n)
x(n+1) = x(n) + ∆x(n)
Bemerkungen:
1. normalerweise (A nicht sehr schlecht konditioniert) nur sehr wenige Iterationen (≈ 3)notig.
2. Losen von A∆x(n) = r(n) ist zeitaufwendig: O(13n3). Mit LU-Zerlegung (auch LR-
Zerlegung genannt) von A laßt sich A∆x(n) = r(n) in O(n2) Schritten losen.
3. Muß ein Gleichungssystem fur mehrere rechte Seiten gelost werden, so werden alleLosungen simultan berechnet (Elimination nur einmal notig!)
4.2 Lineare Gleichungssysteme 33
4.2.3 LU-Zerlegung
Bei der Gauß-Elimination (siehe Algorithmus) wird zur Elimination jedes Elements aik in derk-ten Spalte unterhalb der Diagonalen die Zeile i mit dem Faktor qik := aik/akk multipliziert.Schreiben wir alle berechneten qik in eine untere Dreiecksmatrix, die wir durch Einsen in derDiagonale erganzen, so ergibt sich
L :=
1 0 . . . . . . 0
q21 1 0...
q31 q32 1. . .
......
.... . . . . . 0
qn1 qn2 . . . qnn−1 1
Außerdem sei
U := A′ =
a′11 a′12 · · · a′1n0 a′22 · · · a′2n...
. . . . . ....
0 . . . 0 a′nn
die obere Dreiecksmatrix nach der Elimination.
Satz 4.3 Dann gilt L · U = A und die Losung x des Gleichungssystem Ax = b fur einebeliebige rechte Seite b laßt sich berechnen durch Auflosen der Gleichungen L · c = b nach cund der Gleichung U · x = c nach x.
Das System L · c = b wird gelost durch Vorwartseinsetzen und U · x = c durch Ruckwarts-einsetzen.
Beweis: Wir werden zeigen, dass L · U = A. Dann gilt offenbar
A · x = L · U · x = b.
Nun schreiben wir L · U = A ausfuhrlich:
L · U =
1 0 . . . . . . 0
q21 1 0...
q31 q32 1. . .
......
.... . . . . . 0
qn1 qn2 . . . qnn−1 1
·
a′11 a′12 · · · a′1n0 a′22 · · · a′2n...
. . . . . ....
0 . . . 0 a′nn
= A
Wir wenden nun die Gauß-Elimination auf beiden Seiten an und erhalten 1 0. . .
0 1
· U = U
Also gilt LU = A. Wegen der Assoziativitat der Matrixmultiplikation muss auf der linkenSeite nur in L eliminiert werden. �
34 4 Numerik
4.2.4 Konditionsanalyse
Ax = b mit A : Matrix (n× n) und x, b ∈ Rn
Betrag einer Matrix?Vektornormen:
Definition 4.4∀x ∈ Rn : ‖x‖p = (|x1|p + |x2|p + · · ·+ |xn|p)
1p
1 ≤ p <∞
Lemma 4.1 ‖x‖p ist eine Norm, d.h. es gilt
• ∀x 6= 0 : ‖x‖p > 0 ; ‖x‖p = 0⇔ x = 0
• ∀α ∈ R : ‖αx‖p = |α| · ‖x‖p
• ∀x, y ∈ Rn : ‖x+ y‖p ≤ ‖x‖p + ‖y‖p
Lemma 4.2‖x‖∞ := max
1≤i≤n|xi| = lim
p→∞‖x‖p
‖ ‖∞heißt Maximumnorm
Im folgenden sei ‖x‖ = ‖x‖∞Matrixnorm:
Definition 4.5 Zu einer beliebigen Vektornorm ‖ ‖ wird die kanonische Matrixnorm wiefolgt definiert:
‖A‖ = maxx 6=0
‖Ax‖‖x‖
Lemma 4.3 Auch die Matrixnorm ist eine Norm, und fur eine n×m Matrix A gilt
‖A‖∞ = max1≤i≤n
m∑j=1
|aij|
‖Ax‖ ≤ ‖A‖ · ‖x‖
‖AB‖ ≤ ‖A‖ · ‖B‖
Kondition: Auswirkung von Fehlern in Parametern auf Fehler in der Losung
4.2 Lineare Gleichungssysteme 35
1. Fehler in b:
b = b+ ∆b
⇒ x = x+ ∆x
⇒ A(x+ ∆x) = b+ ∆b
⇒ ∆x = A−1∆b
⇒ ‖∆x‖ = ‖A−1∆b‖ ≤ ‖A−1‖ · ‖∆b‖
b = Ax ⇒ ‖b‖ ≤ ‖A‖ · ‖x‖ ⇒ 1
‖x‖≤ ‖A‖‖b‖
⇒ ‖∆x‖‖x‖
≤ ‖A‖ · ‖A−1‖‖∆b‖‖b‖
‖∆x‖‖x‖‖∆b‖‖b‖
≤ CA
mit CA = ‖A‖ · ‖A−1‖
CA: Konditionszahl von A
2. Fehler in A:
(A+ ∆A)(x+ ∆x) = b
x+ ∆x = (A+ ∆A)−1b = (A+ ∆A)−1Ax
∆x =((A+ ∆A)−1A− I
)x
= (A+ ∆A)−1 (A− (A+ ∆A))x
= (A+ ∆A)−1∆Ax
⇒ ‖∆x‖ ≤ ‖(A+ ∆A)−1‖ · ‖∆A‖ · ‖x‖
‖∆x‖‖x‖
≤ ‖(A+ ∆A)−1‖ · ‖A‖ · ‖∆A‖‖A‖
≈ CA‖∆A‖‖A‖
≈ ‖A−1‖ · ‖∆A‖
CA analog zu Cp : Cp =
∣∣∣∣f ′(x)
f(x)x
∣∣∣∣Beispiel 4.10 (
1 aa 1
)︸ ︷︷ ︸
A
x =
(1
0
)︸︷︷︸
b
A−1 =1
1− a2
(1 −a−a 1
)‖A‖ = 1 + a, ‖A−1‖ =
∣∣∣∣ 1 + a
1− a2
∣∣∣∣ =
∣∣∣∣ 1
1− a
∣∣∣∣ fur a > 0
36 4 Numerik
⇒ CA = ‖A‖ · ‖A−1‖ =
∣∣∣∣(1 + a)2
1− a2
∣∣∣∣ =
∣∣∣∣1 + a
1− a
∣∣∣∣a=1.002:
⇒ A =
(1 1.002
1.002 1
)∆A =
(0 −0.001
−0.001 0
)⇒ CA = 1001
‖∆A‖ = 0.001, ‖A‖ = 2.002
‖∆x‖‖x‖
≤≈ 1001
0.001
2.002= 0.5
4.3 Interpolation mit Polynomen 37
4.3 Interpolation mit Polynomen
Beispiel 4.11 Lineare Interpolation (siehe Abb. 4.2)
Als es noch keine Taschenrechner gab, war die Logarithmusfunktion in Tabellen nachschlag-bar, aber nur auf ganzzahligen Werten. Zwischenwerte wurden durch lineare Interpolationbestimmt.
x1230 12311230.3
3.0903
3.0899
y
Abbildung 4.2: Bestimmung von lg(1230.3) mit linearer Interpolation.
lg(1230) = 3.0899
lg(1231) = 3.0903
lg(1230.3) = ?
lg(1230.3) ≈ 3.0899 + 4 · 0.0001 · 0.3 = 3.09002
4.3.1 Motivation
• Interpolation hoherer Ordnung (quadratisch,...)
• Hilfsmittel fur numerische Verfahren (Funktions-Approximation, numerische Differen-tiation, Integration,...)
4.3.2 Der Potenzreihenansatz
gegeben: Tabelle (xk, yk) fur (k = 1, . . . , n)
gesucht: Polynom p mit p(xi) = yi fur (i = 1, . . . , n)
Ansatz: p(x) = a1 + a2x+ · · ·+ anxn−1
⇒ a1 + a2xi + a3x2i + · · ·+ anx
n−1i = yi fur (i = 1, . . . , n)
38 4 Numerik
⇒ A
a1...an
=
y1...yn
mit A =
1 x1 x2
1 · · · xn−11
1 x2 x22 · · · xn−1
2...
...1 xn x2
n · · · xn−1n
︸ ︷︷ ︸
Vandermonde-Matrix
Satz 4.4 Wenn x1, . . . , xn paarweise verschieden sind, dann gibt es zu beliebigen y1, . . . , ynein eindeutig bestimmbares Polynom p vom Grad ≤ n− 1 mit p(xi) = yi fur (i = 1, . . . , n).
Beweis:Die Gleichung Aa = y ist eindeutig losbar, d.h. Aa = 0 ⇒ a = 0
sei Aa = 0 ⇒ ∀i = 1, . . . , n : p(xi) = 0
⇒ p(x ) ≡ 0 (Nullpolynom)
⇒ a = 0
Beispiel 4.12 Interpolation von sin(x)Tabelle von Werten in {−m,−m+ 1, . . . , 0, 1, 2, . . . ,m}
sin(0.5) = 0.479426
p(0.5) = 0.479422 (m=3, d.h. n=7 Punkte)
p(0.5) = 0.469088 (m=2, d.h. n=5 Punkte)
Bemerkung:sin(x) wird durch das Interpolations-Polynom gut angenahert, schon bei relativ geringer Zahlvon Stutzstellen (n=5,7), wie man auch in Abb. 4.3, Abb. 4.4 und Abb. 4.5 erkennt.
Beispiel 4.13 Interpolation von f(x) im Intervall [-1,1]:
f(x) =1
1 + 25x2
Bemerkung:An Abb. 4.6 erkennt man deutlich die schlechte Naherung, insbesondere im Randbereich.Idee: mehr Stutzstellen am RandVerbesserung: Tschebyscheff-Interpolation
Definition 4.6 Sei f : [a, b]→ R gegeben.
‖f‖∞ := maxx∈[a,b]
|f(x)|
4.3 Interpolation mit Polynomen 39
-3 -2 -1 1 2 3
-2
-1
1
2
Abbildung 4.3: Interpolation von sin(x) mit n = 5 Stutzstellen.
-4 -2 2 4
-1
-0.5
0.5
1
Abbildung 4.4: Interpolation von sin(x) mit n = 7 Stutzstellen.
Satz 4.5 Sei f : [a, b] → R n-mal stetig differenzierbar. Seien a = x1 < x2 < . . . <xn−1 < xn = b und sei p das Interpolations-Polynom vom Grad n-1 mit p(xi) = f(xi) fur(i = 1, . . . , n). Dann ist
f(x)− p(x) =f (n)(z)
(n+ 1)!(x− x1)(x− x2) · · · (x− xn)
fur einen Punkt z ∈ [a, b].
Bemerkung:
• Restglied gleich wie bei Taylerformel fur x1 = x2 = · · · = xn!
40 4 Numerik
-7.5 -5 -2.5 2.5 5 7.5
-2
-1
1
2
Abbildung 4.5: Interpolation von sin(x) mit n = 15 Stutzstellen.
-1 -0.5 0.5 1
0.5
1
1.5
2
Abbildung 4.6: Interpolation mit 11 Stutzstellen.
• rechte Seite gleich Null fur x = xi (d.h. in allen Stutzstellen)
Frage: Wie mussen die Stutzstellen x1, . . . , xn verteilt sein, so daß der maximale Fehler (beifestem n) moglichst klein wird?
Antwort: Tschebyscheff-Interpolation
Satz 4.6 Sei f : [−1, 1] → R gegeben und sei p das Interpolations-Polynom bei den Stutz-stellen −1 ≤ x1 < · · · < xn ≤ 1.Der Approximationsfehler ‖f − p‖∞ = maxx∈[−1,1] |f(x)− p(x)| wird minimal fur
xk = − cos
(2k − 1
n· π
2
)(k = 1, . . . , n)
4.3 Interpolation mit Polynomen 41
Die Werte xk heißen Tschebyscheffabszissen.
Beispiel 4.14 Sei n=6. Die Tschebyscheffabszissen sind dann (siehe auch Abb. 4.7).
k 1 2 3 4 5 62k-1 1 3 5 7 9 11
-cos(π12
(2k − 1))
-0.966 -0.707 -0.259 0.259 0.707 0.966
Tschebyscheff−Abszissenäquidistantes Gitter
−1
0.52 0.26
0 1
Abbildung 4.7: Verteilung der Stutzstellen auf der Zahlengeraden.
Beispiel 4.15 Abb. 4.8 zeigt eine deutliche Verringerung der Maximumnorm der Abwei-chung durch Tschebyscheff-Interpolation.
-1 -0.5 0.5 1
0.2
0.4
0.6
0.8
1
Abbildung 4.8: Tschebyscheff-Interpolation mit 11 Stutzstellen.
Corollar 4.3.1 Satz 4.6 laßt sich in einfacher Weise auf Funktionen f : [a, b]→ R anwenden,indem man die Stutzstellen tk fur k = 1, . . . , n aus den Tschebyscheffabszissen xk berechnetnach
tk =1
2(a+ b) +
1
2(b− a)xk
Erganzende Bemerkungen:
42 4 Numerik
1. Sind Polynome geeignet zur Approximation einer gegebenen Funktion f?Polynome sind ungeeignet fur Funktionen mit Wechsel zwischen starker und schwacherKrummung oder Polstellen.Gegebenenfalls: stuckweise Approximation durch Polynome (⇒ Spline-Approximation)oder Approximation mit gebrochenrationalen Funktionen.
2. Wird ein Polynom durch die Daten (Wertetabelle) gut festgelegt?aquidistante Stutzstellen → Tschebyscheffabszissen oder Grad des Polynoms kleinerwahlen⇒ uberbestimmtes lineares Gleichungssystem (Grad(p) ≤ 2 ·
√n wobei n=Zahl
der Stutzstellen).
4.3.3 Das Horner-Schema
Durch die Verwendung des folgenden Schemas laßt sich bei der Auswertung von PolynomenRechenzeit sparen:
p(x) =n∑k=1
akxk−1 = a1 + a2x+ . . .+ anx
n−1
= a1 + x(a2 + x(a3 + x(. . .+ x(an−1 + xan) . . .)))
Iteration:
y0 := an
yk := yk−1x+ an−k k = 1, . . . , n− 1
⇒ p(x) = yn−1
Rechenzeit:(n-1) Additionen + Multiplikationennaive Auswertung: (xk = x · x · . . . · x · x︸ ︷︷ ︸
k-mal
)
(n-1) Additionen, (n-2)-mal potenzieren, (n-1) Multiplikationen
n−1∑k=0
k =n(n− 1)
2=
1
2(n2 − n) Multiplikationen
4.3.4 Funktionsapproximation vs. Interpolation
Bei der Interpolation sind n Datenpunkte (xk, yk) fur (k = 1, . . . , n) gegeben und es isteine Funktion p (z.B. ein Polynom vom Grad n-1) gesucht mit p(xk) = yk fur (k = 1, . . . , n).
Bei der Approximation von Funktionen ist eine Funktion f : [a, b]→R gegeben (symbo-lisch durch eine Formel oder durch eine Wertetabelle) und die Aufgabe besteht darin, einemoglichst “einfache“ Funktion p zu finden, die f auf dem Intervall [a, b] moglichst gut appro-ximiert bezuglich einer Norm (z.B. Maximumnorm). Die Funktion p kann z.B. ein Polynomsein, aber auch eine Linearkombination von Basisfunktionen wie z.B.
p(x) = a1 sinx+ a2 sin 2x+ a3 sin 3x+ · · ·+ an sinnx
4.3 Interpolation mit Polynomen 43
(hier sind a1, . . . , an zu bestimmen)
Die Interpolation ist ein Hilfsmittel zur Funktionsapproximation.
44 4 Numerik
4.4 Methode der kleinsten Quadrate
4.4.1 Minimierung nach Gauß
geg: n Messungen, d.h. Wertepaare (x1, y1), . . . , (xn, yn)Funktion f(x, a1, . . . , ak) = f(x) k ≤ n
ges: Werte fur a1, . . . , ak derart, daß
E(f(x1)− y1, . . . , f(xn)− yn) =n∑i=1
(f(xi)− yi)2
minimal wird!
Vereinfachung: f ist Linearkombination von Funktionen
f(x, a1, . . . , ak) = a1f1(x) + a2f2(x) + · · ·+ akfk(x)
E extremal⇒ ∀j = 1, . . . , k :∂E
∂aj= 0
E(. . .) =n∑i=1
(a1f1(xi) + · · ·+ akfk(xi)− yi)2
∂E
∂aj= 2
n∑i=1
(k∑l=1
alfl(xi)− yi
)fj(xi)
∂E
∂aj= 0⇒
n∑i=1
k∑l=1
alfl(xi)fj(xi) =n∑i=1
yifj(xi)
⇔k∑l=1
al
n∑i=1
fl(xi)fj(xi)︸ ︷︷ ︸Ajl
=n∑i=1
yifj(xi)︸ ︷︷ ︸bj
⇔k∑l=1
Ajlal = bj fur (j = 1, . . . , k)
lineares Gleichungssystem fur die Parameter a1, . . . ak (Normalgleichungen!)Losen der Normalgleichungen liefert a1, . . . , ak.Bemerkung: Normalgleichungen sind in der Regel (nicht immer) eindeutig losbar (sieheSatz 4.7).
Beispiel 4.16 Mit der Methode der kleinsten Quadrate sollen die Koeffizienten a1, a2, a3 derFunktion f(x) = a1x
2+a2x+a3 anhand von den gegebenen Punkten (0,−1), (2, 0), (3, 2), (4, 1)bestimmt werden. Zuerst stellen wir die Normalgleichungen auf:
k∑l=1
Ajlal = bj fur (j = 1, . . . , k)
4.4 Methode der kleinsten Quadrate 45
mit
Ajl =n∑i=1
fl(xi)fj(xi), bj =n∑i=1
yifj(xi).
Daraus folgt:
A =
∑ni=1 x
4i
∑ni=1 x
3i
∑ni=1 x
2i∑n
i=1 x3i
∑ni=1 x
2i
∑ni=1 xi∑n
i=1 x2i
∑ni=1 xi
∑ni=1 1
=
353 99 2999 29 929 9 4
und
b =
∑ni=1 yix
2i∑n
i=1 yixi∑ni=1 yi
=
34102
Die Losung dieses linearen Gleichungssystems lautet a1 = −3/22, a2 = 127/110, a3 =−61/55, denn 353 99 29
99 29 929 9 4
−
322
127110
−6155
=
34102
Die resultierende Parabel hat folgende Gestalt:
1 2 3 4
-1
-0.5
0.5
1
1.5
2
4.4.2 Anwendung: Entzerrung von Fotos
Im RoboCup werden sogenannte OmniCams verwendet. Dies sind Digitalkameras, die ubereinen parabolischen Spiegel eine 360-Grad-Aufnahme machen (siehe Abb. 4.9).Der Spiegel verzerrt das Bild stark. Aus der Formel fur die Spiegelkrummung kann maneine Formel herleiten fur die Umrechnung der Pixelkoordinaten in reale Abstande auf demSpielfeld. Da diese Formel aber durch Justierungen der Kamera, des Spiegels, etc. leichtverandert wird, stimmt sie meist nicht exakt, mit der Folge, dass das Bild nicht ganz entzerrtwird. Daher verwenden wir zur Bestimmung der Transformation von Pixel-Abstanden inreale Abstande Polynominterpolation. Auf das Spielfeld werden im Abstand von 25cm weisseMarkierungen geklebt (Abb. 4.10) und im Bild die Pixelabstande vom Mittelpunkt gemessen.Man erhalt folgende Wertetabelle:
Abst. d [mm] 0 250 500 750 1000 1250 1500 1750 2000 2250 2500 2750 3000 3250 3500 3750 4000 4250Pixelabst. x 0 50 108 149 182 209 231 248 263 276 287 297 305 313 319 325 330 334
46 4 Numerik
Abbildung 4.9: Der RoboCup-Roboter Kunibert mit nach oben zeigender Kamera und Spie-gel (links), sowie eine verzerrte Aufnahme des Spielfelds.
0
1000
2000
3000
4000
5000
0 50 100 150 200 250 300 350
mm
pix el
DataPolynom
Abbildung 4.10: Im linken Bild sind die Markierungen fur die Interpolation auf dem Spielfeldzu erkennen und rechts der Graph des Interpolationspolynoms d(x).
Abbildung 4.11: Links das bearbeitete Bild nach der Kantenerkennung und rechts das ent-zerrte Bild nach Anwendung der Transformation.
4.4 Methode der kleinsten Quadrate 47
Durch die Wertepaare wird dann mit der Methode der kleinsten Quadrate ein Polynom vomGrad 6 gelegt. Man erhalt
d(x) = 3.02 · 10−11 · x6 − 2.57 · 10−8 · x5 + 8.36 · 10−6 · x4 − 1.17 · 10−3 · x3 +
6.85 · 10−2 · x2 + 3.51 · x+ 6.79 · 10−1
In Abb. 4.11 ist das Bild vor und nach der Transformation gezeigt.
Satz 4.7 Die Normalgleichungen sind genau dann eindeutig losbar, wenn die Vektoren f1(x1)...
f1(xn)
, . . . ,
fk(x1)...
fk(xn)
linear unabhangig sind.
x
y
f1(x)
f2(x)
x5 x6 x7 x8x1 x2 x3 x4 ... xn
f2(x1)...
f2(xn)
= 2
f1(x1)...
f1(xn)
⇒ f1 und f2 sind nicht linear unabhangigauf dem Gitter (x1, . . . , xn).
Beweis:Normalgleichungen eindeutig losbar ⇔ A nicht singular
Ajl =n∑i=1
fl(xi)fj(xi)
⇔ A = F TF mit F =
f1(x1) · · · fk(x1)...
...f1(xn) · · · fk(xn)
Annahme: F TF singular ⇒ ∃z 6= 0 : F TFz = 0
⇒ zTF TFz = ‖Fz‖22 = 0
⇒ Fz = 0⇒k∑i=1
a izi = 0 (a i=i-te Spalte von F)
⇒ Spalten von F sind linear abhangig⇒ Widerspruch zur Voraussetzung von Satz 4.7
48 4 Numerik
Beispiel 4.17 Wir zeigen nun nachtraglich, daß die Methode der kleinsten Quadrate imBeispiel 4.16 anwendbar ist und daß die Koeffizienten eindeutig bestimmt sind.Nach Satz 6 mussen folgende Vektoren linear unabhangig sein:
v1 =
f1(x1)...
f1(x4)
=
04916
, v2 =
f2(x1)...
f2(x4)
=
0234
, v3 =
f3(x1)...
f3(x4)
=
1111
Wenn v1, v2, v3 linear abhangig sind, muß es reelle Zahlen a, b, c 6= 0 geben, so daß
a
04916
+ b
0234
+ c
1111
= 0.
Angenommen es gibt derartige Zahlen a, b, c. Dann folgt sofort c = 0 woraus
a
04916
+ b
0234
= 0.
folgt. Das bedeutet, aber, v1 muß Vielfaches von v2 sein. Das ist offensichtlich nicht der Fall.Also sind v1, v2, v3 linear unabhangig.
4.4.3 Spezialfall: Regressionsgerade
Regressionsgerade f(x, a, b) = ax+ b
E =n∑i=1
(axi + b− yi)2
∂E
∂a= 2
n∑i=1
(axi + b− yi)xi = 0
∂E
∂b= 2
n∑i=1
(axi + b− yi) = 0
a
n∑i=1
x2i + b
n∑i=1
xi =n∑i=1
xiyi
an∑i=1
xi + nb =n∑i=1
yi
Losung:
a =n∑xiyi −
∑xi∑yi
n∑x2i − (
∑xi)
2
b =
∑x2i
∑yi −
∑xi∑xiyi
n∑x2i − (
∑xi)
2
4.4 Methode der kleinsten Quadrate 49
Bleibt zu zeigen: Die Losung(ab
)von grad E=0 ist ein Minimum!
4.4.4 Statistische Rechtfertigung
Die Methode der kleinsten Quadrate kann mit statistischen Methoden schon begrundet wer-den. Hier wird dies nur fur einen Spezialfall durchgefuhrt. Sei f(x) = c die konstante Funktionund sei c gesucht.
xx2x1 xn...
y
Abbildung 4.12: Mittelwert uber alle Funktionswerte.
E =n∑i=1
(f(xi)− yi)2 =n∑i=1
(c− yi)2
∂E
∂c= 2
n∑i=1
(c− yi) = 2
(n∑i=1
c−n∑i=1
yi
)
= 2
(nc−
n∑i=1
yi
)= 0
⇒ nc =n∑i=1
yi
c =1
n
n∑i=1
yi Arithmetisches Mittel
Fehler der Koeffizienten aiWegen Meßfehler in (xi, yi) sind a1, . . . , ak fehlerhaft.Berechnung der Genauigkeit ∆a1, . . . ,∆ak aus ∆y1, . . . ,∆yn mit dem Fehlerfortpflanzungs-gesetz (maximaler Fehler).1
∆ai =n∑j=1
∣∣∣∣∂ai∂yj
∣∣∣∣∆yjBei vielen Meßwerten liefert die Formel fur den maximalen Fehler einen zu großen Wert.Eine bessere Schatzung erhalt man durch die Formel fur den mittleren Fehler
1∆yi ist der Betrag des maximalen zu erwartenden Messfehlers der Variablen yi.
50 4 Numerik
∆ai =
√√√√ n∑j=1
(∂ai∂yj
)2
(∆yj)2
Spezialfall Regressionsgerade:
∂a
∂yj=
1
N
(nxj −
n∑i=1
xi
)∂b
∂yj=
1
N
(n∑i=1
x2i −
(n∑i=1
xi
)xj
)mit N = n
∑x2i −
(∑xi
)2
∆a =n∑j=1
∣∣∣∣ ∂a∂yj∣∣∣∣∆yj
∆b =∑n
j=1
∣∣∣ ∂b∂yj
∣∣∣∆yj
y
x
a+da
a-da
b+db
b
b-db
Abbildung 4.13: Regessionsgerade durch die Wertepaare.
Beispiel 4.18 siehe Ubungen
Nichtlineare Regression (Beispiele):
Beispiel 4.19 (Klausuraufgabe WS01-02) Gegeben seien die Punkte (0, 2), (1, 3), (2, 6).Mit der Methode der kleinsten Quadrate bestimmen wir die Koeffizienten c und d der Funk-tion f(x) = c · ed·x. Man beachten, dass der Parameter d nicht linear auftritt!
4.4 Methode der kleinsten Quadrate 51
Potenzfunktion:
v = c · ud Konstanten c, d gesucht!
log v = log c+ d log u
y := log v, x := log u⇒ a1 = log c, a2 = d
y = a1 + a2x
Exponentialfunktion:
v = Aebu A, b gesucht
ln v = lnA+ bu
y := ln v, x := u, ⇒ a1 = lnA, a2 = b
y = a1 + a2x
4.4.5 Losen von uberbestimmten linearen Gleichungssystemen
Das Gleichungssystemx1 + x2 + x3 = 1x1 + x2 = 1x1 + x3 = 1
x2 + x3 = 1
ist nicht losbar, denn es ist uberbestimmt. Damit mussen wir uns abfinden. Wir konnenuns aber fragen, welcher Vektor x das Gleichungssystem am
”besten” erfullt. Dies laßt sich
folgendermassen formalisieren:Gegeben sei ein uberbestimmtes lineares Gleichungssystem
Mx = y
mit n Gleichungen und k < n Unbekannten x1, . . . xk. M ist also eine n× k Matrix, x ∈ Rk
und y ∈ Rn. Offenbar gibt es im allgemeinen keinen Vektor x, fur den Mx = y gilt. Wirsuchen daher einen Vektor x, der die linke Seite moglichst gut gleich der rechten macht, dasheißt, fur den Mx ≈ y gilt, bzw. fur den
||Mx− y||2 =√
(Mx− y)2
minimal wird. Daraus folgt, dass auch (Mx− y)2 minimal wird. Also muss
n∑i=1
((Mx)i − yi)2 =n∑i=1
(k∑l=1
Milxl − yi
)2
minimal sein. Zur Bestimmung des Minimums setzen wir alle partiellen Ableitungen gleichnull:
∂
∂xj
n∑i=1
(k∑l=1
Milxl − yi
)2
= 2n∑i=1
(k∑l=1
Milxl − yi
)Mij = 0
52 4 Numerik
und erhalten nach Ausmultiplizieren
n∑i=1
k∑l=1
MilMijxl =n∑i=1
Mijyi
bzw.k∑l=1
(n∑i=1
MTjiMil
)xl =
n∑i=1
MTjiyi
oder als VektorgleichungMTMx = MTy.
Damit haben wir folgenden Satz hergeleitet
Satz 4.8 Sei ein uberbestimmtes lineares Gleichungssystem
Mx = y
mit x ∈ Rk, y ∈ Rn und der n × k Matrix M gegeben. Dann erhalt man die Losung x mitden kleinsten Fehlerquadraten durch Losen des linearen Gleichungssystems
MTMx = MTy.
Dieses Gleichungssystem laßt sich umschreiben in
x = (MTM)−1MTy.
Ist M invertierbar und damit das Gleichungssystem Mx = y eindeutig losbar, so kann dieLosung x mittels
x = M−1y
berechnet werden. Vergleicht man diese Gleichung mit obiger fur x, so wird klar, weshalbman die quadratische Matrix
(MTM)−1MT
als Pseudoinverse von M bezeichnet.Nun wenden wir den Satz auf das Beispiel vom Anfang des Abschnitts an. Das Gleichungs-system lautet
111110101011
x =
1111
Anwenden von Satz 4.8 liefert
MTM =
1 1 1 01 1 0 11 0 1 1
·
1 1 11 1 01 0 10 1 1
=
3 2 22 3 22 2 3
und das Gleichungssystem 3 2 2
2 3 22 2 3
· x =
333
mit der Losung x = (3
7, 3
7, 3
7)T .
4.5 Spline Interpolation 53
4.5 Spline Interpolation
4.5.1 Interpolation von Funktionen
gegeben: Wertetabelle (xk, yk) mit k = 0, 1, . . . , n
gesucht: Interpolierende (Funktion) s(x) mit s(xk) = yk, und s(x) sei 2 Mal stetig differen-zierbar.
Losung: stuckweise kubische Polynome
s0(x)
s1(x) s2(x)
x3x2x1x0
y0
y1y2
s(x)
x
Abbildung 4.14: naturlicher, kubischer Spline durch 4 Wertepaare.
Aus s(x) sei 2 mal stetig differenzierbar folgt:
s′(x) stetig , s′′(x) stetig an allen inneren Intervallgrenzen.
⇒ 2 zusatzliche Bedingungen fur jedes kubische Polynom
⇒ Teilpolynome eindeutig bestimmt durch 2 Punkte + 2 Ableitungsbedingungen.
Ansatz: fur (i=0,. . . ,n-1) sei
s(x) = si(x) = ai(x− xi)3 + bi(x− xi)2 + ci(x− xi) + di (4.1)
Forderungen:
si(xi) = yi i=0,. . . ,n-1 (4.2)
sn−1(xn) = yn (4.3)
si(xi+1) = si+1(xi+1) i=0,. . . ,n-2 (4.4)
s′i(xi+1) = s′i+1(xi+1) i=0,. . . ,n-2 (4.5)
s′′i (xi+1) = s′′i+1(xi+1) i=0,. . . ,n-2 (4.6)
⇒ n+ 1 + 3(n− 1) = 4n− 2 lineare Gleichungen fur
4n Unbekannte
54 4 Numerik
⇒ 2 Bedingungen fehlen
Zusatzbedingung (naturlicher Spline):
s′′(x0) = 0, s′′(xn) = 0 (4.7)
Abkurzung:hi = xi+1 − xi (4.8)
(4.1), (4.2) ⇒ si(xi) = di = yi (4.9)
(4.1), (4.2), (4.4) ⇒ si(xi+1) = aih3i + bih
2i + cihi + di = yi+1 (4.10)
(4.1) ⇒ s′i(xi) = ci (4.11)
(4.1) ⇒ s′i(xi+1) = 3aih2i + 2bihi + ci (4.12)
(4.1) ⇒ s′′i (xi) = 2bi =: y′′i (4.13)
(4.1) ⇒ s′′i (xi+1) = 6aihi + 2bi = s′′i+1(xi+1) = y′′i+1 (4.14)
(4.13), (4.14)⇒ ai =1
6hi(y′′i+1 − y′′i )
(4.13)⇒ bi =1
2y′′i (4.15)
(4.9), (4.10), (4.13), (4.14)⇒ ci =1
hi(yi+1 − yi)−
hi6
(y′′i+1 + 2y′′i )
(4.9)⇒ di = yi
wenn y′′i bekannt, dann sind auch ai, bi, ci, di bekannt.(4.15) in (4.12):
s′i(xi+1) =1
hi(yi+1 − yi) +
hi6
(2y′′i+1 + y′′i )
i→ i− 1 : s′i−1(xi) =1
hi−1
(yi − yi−1) +hi−1
6(2y′′i + y′′i−1) (4.16)
wegen s′i−1(xi) = s′i(xi) (Forderung (4.5))
und s′i(xi) = ci =1
hi(yi+1 − yi)−
hi6
(y′′i+1 + 2y′′i )
folgt
1
hi−1
(yi − yi−1) +hi−1
6(2y′′i + y′′i−1) =
1
hi(yi+1 − yi)−
hi6
(y′′i+1 + 2y′′i )
Sortieren der y′′-Variablen nach links ergibt
⇒ hi−1y′′i−1 + 2(hi−1 + hi)y
′′i + hiy
′′i+1 =
6
hi(yi+1 − yi)−
6
hi−1
(yi − yi−1) (4.17)
fur i = 1, 2, . . . , n− 1.
4.5 Spline Interpolation 55
lineares Gleichungssystem fur y′′1 , y′′2 , . . . , y
′′n−1
y′′0 , y′′n frei wahlbar!
y′′0 = y′′n = 0: naturlicher Spline
Beispiel 4.20 n = 52(h0 + h1) h1 0 0
h1 2(h1 + h2) h2 00 h2 2(h2 + h3) h3
0 0 h3 2(h3 + h4)
·
y′′1y′′2y′′3y′′4
= r
mit ri =6
hi(yi+1 − yi)−
6
hi−1
(yi − yi−1)
Koeffizientenmatrix hat Tridiagonalgestalt
Beispiel 4.21 Gesucht ist naturliche kubischen Spline-Interpolierende durch die Punkte(0, 0), (1, 1), (2, 0), (3, 1). Es gilt n = 3 und h0 = h1 = 1. Die Koeffizentenmatrix ergibt sichzu (
2(h0 + h1) h1
h1 2(h1 + h2)
)=
(4 11 4
)mit der rechten Seite
r1 = 6(y2 − y1)− 6(y1 − y0) = −12
r2 = 6(y3 − y2)− 6(y2 − y1) = 12.
Das Gleichungssystem lautet dann(4 11 4
)(y′′1y′′2
)=
(−1212
)mit der Losung
y′′1 = −4, y′′2 = 4, y′′0 = y′′3 = 0
Einsetzen in (4.15) ergibt:
s0(x) = −2/3x3 + 5/3x
s1(x) = 4/3x3 − 6x2 + 23/3x− 2
s2(x) = −2/3x3 + 6x2 − 49/3x+ 14.
mit dem Graphen
56 4 Numerik
Definition 4.7 Eine n× n Matrix A heißt diagonal dominant, falls
|aii| >n∑
k=1k 6=i
|aik|
fur i = 1, 2, . . . , n
Satz 4.9 Jedes lineare Gleichungssystem A · x = b ist eindeutig losbar, wenn A diagonaldominant ist. Bei der Gauß’schen Elimination sind keine Zeilen- oder Spaltenvertauschungennotig.
Satz 4.10 Die Rechenzeit fur das Gauß’sche Eliminationsverfahren bei Tridiagonalgestaltvon A ist linear in der Lange n von A.
Beweis: (siehe Ubungen)
Satz 4.11 Spline-Interpolation: Seien x0 < x1 < . . . < xn. Dann existiert eine eindeutigekubische Spline-Interpolierende s(x) mit y′′0 = y′′n = 0 (naturlicher Spline). Diese laßt sichnach oben angegebenem Verfahren in linearer Zeit (O(n)) berechnen (unter Verwendung desTridiagonalalgorithmus, siehe Ubung).
Tridiagonalalgorithmusb1 c1 0 · · · 0
c1. . . . . . 0
...
0. . . . . . . . . 0
... 0. . . . . . cn−1
0 · · · 0 cn−1 bn
· x =
d1
d2...
dn−1
dn
Elimination:
m := ck−1/bk−1
bk := bk −m · ck−1
dk := dk −m · dk−1
k = 2, . . . , n
Ruckwartseinsetzen:
dn := dn/bndk := (dk − ckdk+1)/bkxk = dk
k = n− 1, . . . , 1
4.5 Spline Interpolation 57
Beweis:
1. Existenz und EindeutigkeitSeien x0 < x1 < . . . < xn ⇒ hi = xi+1 − xi > 0
⇒ 2(hi−1 + hi) > hi−1 + hi
⇒ Matrix diagonal dominant und eindeutig losbar
⇒ ai, bi, ci, di eindeutig bestimmt
⇒ Spline-Interplierende eindeutig bestimmt
2. Rechenzeit (siehe Ubungen)
Andere Randbedingungen:
1. y′′0 = y′′n = 0 (naturlicher Spline)
2. y′′0 = s′′(x0), y′′n = s′′(xn) (s′′ vorgegeben)
3. y′′0 = y′′1 , y′′n = y′′n−1 (s′′ konstant am Rand)
4. s′ am Rand vorgegeben (beste Wahl wenn s′(x0), s′(xn) bekannt)
5. falls y0 = yn : y′0 = y′n, y′′0 = y′′n (periodische Randbedingung)
y
x
y0=yn
xnx0
Abbildung 4.15: Periodische Randbedingung bei der Spline-Interpolation.
4.5.2 Interpolation beliebiger Kurven
Beispiel 4.22 Tragflachenprofil:
gegeben: Wertetabelle
k xk yk1 x1 y1
2 x2 y2...
......
n xn yn
Die Kurve ist keine Funktion, daher naive Interpolation nicht anwendbar.⇒ Parameterdarstellung (Paramter t)
58 4 Numerik
y
x
... P4P3
P2
P0P1
Abbildung 4.16: Parametrischer Plot von gegebenen Wertepaaren.
(xk, yk)
(tk, xk) (tk, yk)
���
@@@R
(tk, xk), (tk, yk) eindeutig, wenn (tk) fur k = 1, . . . , n streng monoton wachsend!
Einfachste Wahl von tk: tk = k
k tk xk tk yk0 0 x0 0 y0
1 1 x1 1 y1
2 2 x2 2 y2...
......
......
n n xn n yn
ideale Wahl von tk: Bogenlangegute Wahl von tk:
t0 = 0,
tk = tk−1 + ||Pk − Pk−1||= tk−1 +
√(xk − xk−1)2 + (yk − yk−1)2 k = 1, 2, . . . , n
Berechnung der Splinekurve
1. Berechnung der Splinefunktion fur (tk, xk) ⇒ x(t)
2. Berechnung der Splinefunktion fur (tk, yk) ⇒ y(t)
3. Splinekurve definiert durch:x = x(t)y = y(t)fur 0 ≤ t ≤ tn
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 59
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen
gegeben: nichtlineare Gleichung f(x) = 0
gesucht: Losung(en) (Wurzeln)
4.6.1 Naherungswerte, Startmethoden
Zeichnen des Graphen von f(x), Wertetabelle
Beispiel 4.23
f(x) =(x
2
)2
− sinx
xPi/2 Pi1 2
1
sin(x)
x
-0.6
1,9
21
f(x)
2(x / 2)
Abbildung 4.17: Graphen zum Finden des Startwertes.
Tabelle:
x (x/2)2 sinx f(x)1,6 0,64 0.9996 < 01.8 0.81 0.974 < 02.0 1.00 0.909 > 0
⇒ Nullstelle in [1.8; 2.0]allgemein: wenn f stetig und f(a) · f(b) < 0⇒ f hat eine Nullstelle in [a, b].
Intervallhalbierung
Voraussetzungen:
Sei f : [a, b]→ R stetig und f(a) · f(b) < 0.
Sei ohne Beschrankung der Allgemeinheit f(a) < 0, f(b) > 0 (sonst nehme man −f(x))
Algorithmus:
mk = 12(ak−1 + bk−1)
(ak, bk) =
{(mk, bk−1) falls f(mk) < 0(ak−1,mk) falls f(mk) > 0
(Nullstelle gefunden falls f(mk) = 0)!
60 4 Numerik
x
yyyy
a=a0
b=b0m(k+1)
m(k+2)
mk
Abbildung 4.18: Nullstelle im Intervall [a,b] kann mit Hilfe des Intervallhalbierungsverfahrens schnellermittelt werden..
Satz 4.12 Sei f : [a, b]→ R stetig mit f(a) ·f(b) < 0. Dann konvergiert das Intervallhalbie-rungsverfahren gegen eine Nullstelle x von f . Nach n Schritten ist x mit einer Genauigkeitvon b−a
2n bestimmt.
Zum Beweis von Satz 4.12 werden noch folgende Definition und Satz benotigt:
Definition 4.8 Eine Folge (an) heißt Cauchyfolge, wenn gilt:
∀ε > 0 : ∃N ∈ N : ∀n,m ≥ N : |am − an| < ε
Satz 4.13 In R konvergiert jede Cauchyfolge.
Beweis von Satz 4.12:
1. Konvergenzgeschwindigkeit:n-ter Schritt:
(bn − an) =1
2(bn−1 − an−1) = . . . =
1
2n(b0 − a0) =
1
2n(b− a).
2. Konvergenz:
x = mn+1 ±1
2(bn − an) = mn+1 ±
1
2n+1(b− a)
Fur m ≥ n+ 1 gilt
|am − an| ≤ bn − an =1
2n(b− a) < ε fur n groß genug.
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 61
⇒ (an), (bn) sind Cauchyfolgen ⇒ (an), (bn) konvergent mit
limn→∞
an = limn→∞
bn = x
wegen f(an) < 0 < f(bn) und Stetigkeit von f .
⇒ limn→∞ f(an) = f(x) ≤ 0limn→∞ f(bn) = f(x) ≥ 0
}f(x) = 0
Bemerkung:
1. Bei jedem Schritt wird die Genauigkeit verdoppelt, bzw. der Abstand zur Losung hal-biert.⇒ pro Schritt wird die Genauigkeit um eine binare Stelle verbessert.wegen 10−1 ≈ 2−3.3 sind ca. 3.3 Schritte notig, um eine Dezimalstelle genauer zu wer-den.⇒ langsame Konvergenz! (Beispiel: fur 12 Stellen Genauigkeit ca. 40 Schritte notig)
2. Konvergenz langsam, weil nur das Vorzeichen von f benutzt wird, f(an), f(bn)wird nie benutzt!⇒ bessere Verfahren benutzen f(x), f ′(x), f ′′(x), . . .
3. Intervallhalbierungsverfahren auch auf unstetige Funktionen anwendbar⇒ Ubungen
4. Diskrete Variante von Intervallhalbierung:Bisektion (=effizientes Suchverfahren in geordneten Dateien)
T (n) ≈ log2(n) statt T (n) ≈ n
mit n=Zahl der Eintrage in der Datei.
5. Intervallhalbierungsverfahren global konvergent!
warum log2(n) Schritte?Sei n = b− a die Zahl der Eintrage in der Datei.
⇒ bk − ak ≈1
2k(b− a) =
n
2k
Zahl der Schritte bis bk − ak ≤ 1
⇒ n
2k≤ 1
⇒ 2k ≥ n
k ≥ log2 n
62 4 Numerik
y
y=x
xx0
f(x0)
y=f(x)
y
y=x
x
y=f(x)
x0
f(x0)
x0 x1 x2 x3
f(x0)
f(x1)
f(x2)f(x3)
y
y=x
y=f(x)
x
y
y=x
x
y=f(x)
x0
f(x0)
Abbildung 4.19: je zwei Beispiele divergenter und konvergenter Iterationen.
4.6.2 Fixpunktiteration
Ziel: Losung von Gleichungen der Form
x = f(x) (Fixpunktgleichung)
Iterative Losung:
x0 = a
xn+1 = f(xn) (n = 0, 1, 2, . . .)
Beispiel 4.24 In Abb. 4.19 ist das Losen der Fixpunktgleichung x = f(x) fur verschiedeneFunktionen f grafisch dargestellt.
Definition 4.9 Eine Funktion f : [a, b] → [a, b] ∈ R heißt kontrahierend auf [a,b],wenn eine (Lipschitz-)Konstante L mit 0 < L < 1 existiert mit |f(x) − f(y)| ≤ L|x − y|∀x, y ∈ [a, b]
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 63
Lemma 4.4 Ist f : [a, b] → [a, b] differenzierbar, so ist f kontrahierend auf [a, b] mit Lip-schitzkonstante L genau dann, wenn gilt:
∀x ∈ [a, b] : |f ′(x)| ≤ L < 1
Beweis:“→”: sei |f(x)− f(y)| ≤ L|x− y| ∀x, y ∈ [a, b]
⇒ ∀x, y :|f(x)− f(y)||x− y|
≤ L
⇒ limx→y
|f(x)− f(y)||x− y|
= |f ′(y)| ≤ L
“←”: (schwieriger ⇒ weggelassen)
Beispiel 4.25
f(x) =1
2
(x+
a
x
)
y=x
x
y=f(x)
sqrt(2)
f(x)
a
Abbildung 4.20: .
f ′(x) =1
2− a
2x2
f ′(x) > −1
1
2− a
2x2> −1
3
2>
a
2x2
x >
√a
3
64 4 Numerik
a=2:
x >
√2
3≈ 0.817
f ist kontrahierend auf [√
a3
+ ε,∞] fur ε > 0.
Satz 4.14 Banachscher Fixpunktsatz: Sei f : [a, b] → [a, b] ⊂ R kontrahierend. Danngilt
1. f besitzt genau einen Fixpunkt s ∈ [a, b].
2. Fur jeden Startwert x0 aus [a, b] konvergiert die Fixpunktiteration gegen s.
3. Es gilt die Fehlerabschatzung:
|s− xk| ≤Lk−l
1− L|xl+1 − xl| fur 0 ≤ l < k
Fur l = 0 gilt
|s− xk| ≤Lk
1− L|x1 − x0| (a priori Abschatzung)
sowie fur l = k − 1 :
|s− xk| ≤L
1− L|xk − xk−1| (a posteriori Abschatzung).
Beweis:
|xk+1 − xk| = |f(xk)− f(xk−1)| ≤ L|xk − xk−1|= L|f(xk−1)− f(xk−2)| ≤ L2|xk−1 − xk−2|= . . .
= Lk−l|xl+1 − xl| fur 0 ≤ l ≤ k
fur l = 0:|xk+1 − xk| ≤ Lk|x1 − x0|
|xk+m − xk| = |xk+m−xk+m−1 + xk+m−1︸ ︷︷ ︸=0
− . . .+ . . .︸ ︷︷ ︸=0
−xk| =
∣∣∣∣∣k+m−1∑i=k
xi+1 − xi
∣∣∣∣∣≤
k+m−1∑i=k
|xi+1 − xi| ≤ Lk(Lm−1 + Lm−2 + . . .+ L+ 1)|x1 − x0|
= Lk1− Lm
1− L|x1 − x0| → 0 fur k →∞
⇒ (xk) Cauchyfolge ⇒ (xk) konvergent
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 65
fur s = limn→∞ xn gilt f(s) = f(limn→∞ xn) = limn→∞ f(xn) = limn→∞ xn+1 = s⇒ s ist Fixpunkt von f und s ist eindeutig, da fur s1, s2 mit s1 = f(s1), s2 = f(s2) gilt:
|s1 − s2| = |f(s1)− f(s2)| ≤ L|s1 − s2| wegen L < 1⇒ s1 = s2
Fehlerabschatzung siehe [8] S. 188
Beispiel 4.26
f(x) =1
2
(x+
a
x
)a = 5, x0 = 2
f kontrahierend auf [2,∞] mit L = 0.5.Satz 4.14 (3) mit l = k − 1 :
|s− xk| ≤L
1− L|xk − xk−1| (a posteriori Abschatzung)
⇒ |√
5− xk| ≤0.5
1− 0.5|xk − xk−1| = |xk − xk−1|
n xn (xn − xn−1) ≥ (√
5− xn)0 21 2.25 0.252 2.2361111 0.01393 2.2360679779 0.0000434 2.2360679775 0.00000000042
0.00000000042 (a posteriori)0.031 (a priori)Bemerkung:
Satz 4.14 (3) liefert Abschatzung des Fehlers ohne Kenntnis des Grenzwertes!
Beispiel 4.27f(x) = exp (−x) = x
f : A→ A, A = [0.5, 0.69]
L = maxx∈A|f ′(x)| = max
x∈A| − e−x|
= e−0.5 ≈ 0.606531 < 1
k xk0 0.551 0.5772 0.5623 0.5704 0.565...
...12 0.56712420
......
20 0.5671430921 0.5671434022 0.56714323
Satz 4.14 (3) mit l = 0:
|s−xk| ≤Lk
1− L|x1−x0| (a priori Abschatzung)
Berechnung von k, wenn |s− xk| ≤ ε = 10−6
k ≥log(ε(1−L)|x1−x0|
)logL
≈ 22.3
Fehler nach 12 Schritten:
a priori: |s− x12| ≤ 1.70 · 10−4
a posteriori: |s− x12| ≤ 8.13 · 10−5 (besser!)
66 4 Numerik
y=x
x
f(x)
1
y=exp(-x)
Abbildung 4.21: .
Ergebnis:
Die Iteration im ersten Beispiel konvergiert viel schneller als die im zweiten Beispiel.
4.6.3 Konvergenzverhalten/ Konvergenzordnung
Definition 4.10 εk := xk − s heißt Abbruchfehler
Fixpunktsatz (f kontrahierend):
|εk+1| = |xk+1 − s| = |f(xk)− f(s)| ≤ L|xk − s| = L|εk|
⇒ Fehler verkleinert sich pro Schritt um den Faktor L!
Satz 4.15 f : [a, b] → [a, b] erfulle die Voraussetzungen von Satz 4.14 und sei stetig diffe-renzierbar mit f ′(x) 6= 0 ∀x ∈ [a, b]. Dann gilt:
limk→∞
εk+1
εk= f ′(s)
Beweis:siehe [8] S.190Folgerungen:εk+1 ≈ qεk mit q := f ′(s) (Konvergenzquotient)(xk) heißt linear konvergent mit Konvergenzquotient |q|.⇒ nach je m Schritten Fehler εk+m ≈ 1
10εk
m =?
εk+m ≈ qmεk = 10−1εk
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 67
⇒ m log10 |q| ≤ −1⇒ m ≥ −1
log10 |q|
|q| = |f ′(s)| 0.316 0.562 0.75 0.891 0.944 0.972m 2 4 8 20 40 80
Satz 4.16 f wie in Satz 4.14 gegeben mit f ′(s) = 0, ∀x ∈ [a, b]f ′′(x) 6= 0 und f ′′ stetig auf[a, b]. Dann gilt:
limk→∞
εk+1
ε2k
=1
2f ′′(s)
Folgerung:
fur k →∞ : εk+1 ≈ pε2k mit p :=
1
2f ′′(s)
⇒ quadratische Konvergenz (Konvergenzordnung=2)Zahl der korrekten Stellen verdoppelt sich in jedem Schritt (wenn p ≈ 1), da
εk+1 = pε2k ⇔ log εk+1 = log p+ 2 log εk
⇔ log εk+1
log εk=
log p
log εk︸ ︷︷ ︸≈0
+2
Beispiel 4.28
εk+1 = 10−8, εk = 10−4
Beweis von Satz 4.16:
εk+1 = xk+1 − s = f(xk)− f(s) = f(s+ εk)− f(s)
= f(s) + εkf′(s)︸ ︷︷ ︸
=0
+1
2ε2kf′′(s+ θkεk)− f(s)
=1
2ε2kf′′(s+ θkεk) mit 0 < θk < 1
wegen f ′′(x) 6= 0 ∀x ∈ [a, b] und x0 6= s gilt:
∀k > 0 : xk − s = εk 6= 0
⇒ εk+1
ε2k
=1
2f ′′(s+ θkεk) k = 0, 1, 2, . . .
limk→∞
εk+1
ε2k
=1
2limk→∞
f ′′(s+ θkεk) =1
2f ′′(s+ lim
k→∞(θkεk)︸ ︷︷ ︸=0
) =1
2f ′′(s)
68 4 Numerik
f(x)
xx(k)x(k+1)
Abbildung 4.22: .
4.6.4 Das Newtonverfahren
gesucht: Losungen von f(x) = 0
Tangente: T (x) = f(xk) + (x− xk)f ′(xk)
T (xk+1) = 0⇒ f(xk) + (xk+1 − xk)f ′(xk) = 0
⇒ (xk+1 − xk)f ′(xk) = −f(xk)
xk+1 = xk −f(xk)
f ′(xk)(4.18)
k = 0, 1, 2, . . .
mit F (x) := x− f(x)
f ′(x)wird (4.18) zur Fixpunktiteration
xk+1 = F (xk) mit F (s) = s (Fixpunkt)
Satz 4.17 Sei f : [a, b] → R dreimal stetig differenzierbar und ∃s ∈ [a, b] : f(s) = 0, sowie∀x ∈ [a, b] : f ′(x) 6= 0 und f ′′(s) 6= 0. Dann existiert ein Intervall I = [s − δ, s + δ] mitδ > 0 auf dem F : I → I kontrahierend ist. Fur jedes x0 ist (xk) nach (4.18) quadratischkonvergent.
Beweis:
4.6 Nullstellenberechnung/ Nichtlineare Gleichungen 69
1. F ist kontrahierend in einer Umgebung von s, d.h. |F ′(x)| < 1 fur s− δ ≤ x ≤ s+ δ
F ′(x) = 1− f ′(x)2 − f(x)f ′′(x)
f ′(x)2=f(x)f ′′(x)
f ′(x)2(4.19)
⇒ F ′(s) =0f ′′(s)
f ′(s)2= 0.
wegen der Stetigkeit von F ′ existiert ein δ > 0 mit
F ′(x) ≤ L < 1 ∀x ∈ [s− δ, s+ δ] =: I
⇒ F ist kontrahierend in I⇒ lim
k→∞xk = s
2. Konvergenzordnung:
Anwendung von Satz 4.16 auf F : F ′(s) = 0
aus (4.19) folgt:
F ′′(x) =f ′(x)2f ′′(x) + f(x)f ′(x)f ′′′(x)− 2f(x)f ′′(x)2
f ′(x)3
⇒ F ′′(s) =f ′(s)2f ′′(s)
f ′(s)3=f ′′(s)
f ′(s)
Nach Satz 4.16 ist (xk) auf I quadratisch konvergent genau dann, wenn f ′′(s) 6= 0.(sonst noch hohere Konvergenzordnung)
70 4 Numerik
4.7 Numerische Integration und Monte Carlo Simula-
tion
Numerische Integration ist in der Anwendung sehr wichtig, aber die analytische (symbolische)Integration ist immer vorzuziehen, wenn moglich.
4.7.1 Die Trapezregel
xa=x x ........ x x ........ x =b
h
0 1 i-1 i n
aquidistante Zerlegung von [a, b] durch x0 = a, x1 = a+ h, x2 = a+ 2h, ..., xn = a · n · h = b
Schrittweite: h =(b− a)
n
Naherung: Flache eines Trapezes =
xi∫xi−1
f(x) dx ≈ h · f(xi−1) + f(xi)
2
Es gilt:
Satz 4.18 (Trapezregel)Sei f : [a, b]→ R zweimal stetig differenzierbar . Dann gilt
b∫a
f(x) dx = h ·(f(x0)
2+ f(x1) + f(x2) + ...+ f(xn−1) +
f(xn)
2
)︸ ︷︷ ︸T (h)
−∆T (h)
mit |∆T (h)| ≤ (b− a)M2
12h2 mit M2 = max{|f ′′(x)| : x ∈ [a, b]}
Bemerkung: Bei Halbierung von h(h→ h2) verdoppelt sich der Rechenaufwand (2n Funk-
tionsauswertungen), wobei sich der Fehler um den Faktor 4 verringert: ∆T (h
2) ≈ ∆T (h)
4
Beispiel 4.29 Trapezregel zur Approximation des bestimmten Integrals
4.7 Numerische Integration und Monte Carlo Simulation 71
T (h) =∑
Trapezflachen (siehe Abb. 4.23)
Abbildung 4.23: Trapezregel bei halber Schrittweite h/2..
Fehler: ∆T (h) = T (h)−∫ b
a
f(x)dx ≈ ch2 ∼ h2
⇒ ∆T (2h) ≈ 4ch2 ≈ 4∆T (h)
∆T (2h)−∆T (h) ≈ 3∆T (h)
⇒ T (2h)− T (h) ≈ 3∆T (h)
∆T (h) ≈ 1
3(T (2h)− T (h))
⇒∫ b
a
f(x)dx = T (h)−∆T (h) ≈ T (h)−[
1
3(T (2h)− T (h))
]
∫ b
a
f(x)dx ≈ 4
3T (h)− 1
3T (2h)
Bessere Naherung als T(h) → Richardson-Extrapolation
Beispiel 4.30 Numerische Differentiation
f ′(x) ≈ f(x+ h)− f(x)
h≈ f(x+ h)− f(x− h)
2h
Zentrale Differenz (siehe Abb. 4.24):
f ′(x) = limh→0
f(x+ h2)− f(x− h
2)
h
f ′′(x) = limh→0
f ′(x+ h2)− f ′(x− h
2)
h= lim
h→0
f(x+ h)− f(x)− f(x) + f(x− h)
h2
72 4 Numerik
y
xx-h x x+h
f(x)
symmetrisches Intervall
asymmetrisches Intervall
f’(x)
Abbildung 4.24: Zentrale Differenz.
f ′′(x) = limh→0
f(x+ h)− 2f(x) + f(x− h)
h2≈ f(x+ h)− 2f(x) + f(x− h)
h2
f(x) = a0 + a1x+ a2x2 + · · ·
= f(x0) +1
1!f ′(x0)(x− x0) +
1
2!f ′′(x0)(x− x0)2 + · · ·
4.7.2 Computersimulation (Monte-Carlo-Methoden)
Fur viele komplexe Anwendungen ist die Modellierung z.B. durch Differentialgleichungenentweder nicht moglich oder viel zu rechenaufwendig. Man behilft sich hier durch direkteSimulation des jeweiligen Prozesses mit Hilfe eines stochastischen Modells. Solche Modellewerden u.a. verwendet in den Gebieten
• statische Physik (Vielteilchenphysik)
• Hydrodynamik
• Meteologie
• Straßenverkehr
• Warteschlangensysteme
Beispiel 4.31 (Methode 1) Berechnung der Flache unter einer Kurve (siehe Abb. 4.25)
∫ b
a
f(x)dx ≈ Anzahl der Treffer unterhalb der Kurve
Anzahl der Treffer im Rechteck·B ·H
Beispiel 4.32 (Methode 2) Nach dem Mittelwertsatz der Integralrechnung gilt∫ b
a
f(x) dx = (b− a) ·M, (4.20)
4.7 Numerische Integration und Monte Carlo Simulation 73
y
xa b
f(x)
Kanone
H
B
*
Abbildung 4.25: Flachenberechnung mit Hilfe der Monte-Carlo-Methode.
wobei M der Mittelwert von f im Intervall [a, b] ist. Nun diskretisierten wir das Intervall mitden Stutzstellen x1, . . . , xn und berechnen den Mittelwert von f auf den Stutzstellen nach
A =1
n
n∑i=1
f(xi).
Aufgrund der Definition des Riemannintegrals gilt nun fur feine Diskretisierung A ≈ M .Damit kann man in (4.20) M ersetzen und erhalt∫ b
a
f(x) dx =b− an
n∑i=1
f(xi).
Die Stutzstellen xi werden nun meist zufallig gewahlt. (warum?)
Beide vorgestellte Methoden sind bei eindimensionalen Integralen der Trapezregel klar un-terlegen. Jedoch bei hoheren Dimensionen zeigen sich die Vorteile in Form von wesentlichkurzeren Rechenzeiten.
Kapitel 5
Ubungsaufgaben
5.1 Computeralgebra
Aufgabe 1 Programmieren Sie die Fakultatsfunktion mit Mathematica.
a) Schreiben Sie ein iteratives Programm, das die Formel n! = n · (n−1) · . . . ·1 berechnet.
b) Schreiben Sie ein rekursives Programm, das die Formel
n! =
{n · (n− 1)! falls n > 1
1 falls n = 1
berechnet, analog wie bei dem Wurzelbeispiel im Skript.
c) fac[n_] := Module[{a, b},
For[{a = 1; b = n}, b > 1, b--,
a = a * b];
If[n < 0, Print["Not defined"], a]
]
fac::usage = "fac[n] computes the factorial of n"
d) Fac[0] := 1;
Fac[n_] := n * Fac[n - 1] /; n > 1
Fac[_] := Print["Not defined"];
Fac::usage = "Fac[n] computes the factorial of n"
Aufgabe 2 Berechnen Sie√
714 nur mitttels Multiplizieren und Dividieren auf mindestenssechs Dezimalstellen.
5.2 Zufallszahlen
Aufgabe 3
a) Warum ist die Periode eines linearen Kongruenzgenerators nach oben beschrankt durchden Wert des Moduls m? Wie mußte man den Generator bei festem Modul m abandern,um die Periodendauer wesentlich langer zu machen.
b) Betrachten Sie Generatoren der Form xn = (xn−1 + xn−2) mod m und finden Sie Fallefur x0 und m, bei denen die Periode langer als m ist.
5.3 Numerik 75
c) Betrachten Sie Generatoren der Form xn = (xn−1 + xn−2 + xn−3) mod m und findenSie Falle fur x0 und m, bei denen die Periode langer als m2 ist.
d) Untersuchen Sie nun Generatoren der Form xn = (xn−1 + xn−2 + . . .+ x0) mod m mitx0 = 1 auf Periodizitat.
e) Beweisen Sie per Induktion: Wenn x1 = x0 = 1 und fur n ≥ 2 gilt xn = 2 · xn−1, danngilt xn = 2n−1 fur n ≥ 1 .
Aufgabe 4 Berechnen Sie Erwartungswert und Standardabweichung einer echten binarenZufallsvariable.
Aufgabe 5
a) Implementieren Sie den erwahnten linearen Kongruenzgenerator der Form
xn = (axn−1 + b) mod m
mit a = 7141, b = 54773 und m = 259200 in einer Programmiersprache Ihrer Wahl.
b) Testen Sie die mit diesem Generator erzeugten Bits auf Symmetrie und Periodizitat.
c) Wiederholen Sie die Tests nach Anwendung des Neumann-Filters.
d) Zeichnen Sie jeweils die Dichtefunktion einer Summe von 10, 100, 1000, 10 000 guterZufallsbits. Verwenden Sie hierfur den in Mathematica eingebaute Funktion Random.Bestimmen Sie dann fur jede der Summen die empirische Standardabweichung.
Aufgabe 6
a) Warum ist der Symmetrietest nicht ausreichend, um die Qualitat eines Zufallszahlen-generators zu testen?
b) Schlagen Sie andere Tests vor, um die Qualitat eines PRNG fur kryptographischeAnwendungen zu testen.
c) Was konnen Sie theoretisch sagen uber die Periode des BBS-Generators?
Aufgabe 7 Zeigen Sie, dass sich die Lange einer endlichen Bit-Folge (an)n∈{0,1} mit unab-hangigen Bits durch Anwendung des Neumann-Filters um etwa den Faktor p(1−p) verkurzt,wenn der relative Anteil von Einsen gleich p ist. (Satz 2.5)
5.3 Numerik
Aufgabe 8 Berechnen Sie die p-Norm ‖x‖p des Vektors x = (1, 2, 3, 4, 5) fur die Wertep = 1, 2, . . . , 50.
Aufgabe 9
a) Schreiben Sie ein Mathematica-Programm, das mittels LinearSolve ein lineares Glei-chungssystem (LGS) symbolisch lost und wenden Sie dieses auf LGS mit bis zu 7Gleichungen an.
b) Zeigen Sie empirisch, dass die Lange der Losungsformel etwa exponentiell mit der Zahlder Gleichungen des LGS wachst.
76 5 Ubungsaufgaben
Aufgabe 10 Zeigen Sie, dass sich die Addition des k-fachen einer beliebigen Zeile i einerquadratischen Matrix A zu einer anderen Zeile j als Produkt A ·G mit einer quadratischenMatrix G darstellen laßt. Geben Sie die Matrix G an.
Aufgabe 11 Berechnen Sie fur die Matrix
A =
1 2 31 0 12 1 1
die Matrizen L und U der LU-Zerlegung. Bestimmen Sie dann die Losungen von Ax = b furdie rechten Seiten (1, 1, 1)T und (3, 1, 0)T .
5.3 Numerik 77
Aufgabe 12
a) Gegeben seien die Punkte (−1, 1), (0, 0) und (1, 1). Bestimmen Sie das Interpolations-polynom durch diese drei Punkte.
b) Gegeben seien die Punkte (−1, 1), (0, 0), (1, 1), (2, 0). Bestimmen Sie das Interpolati-onspolynom durch diese vier Punkte.
Aufgabe 13
a) Schreiben Sie ein Mathematica-Programm, das eine Tabelle aller Koeffizienten desInterpolationspolynoms vom Grad n einer beliebigen Funktion f in einem beliebigenIntervall [a, b] berechnet.
Hilfreich hierbei sind die Mathematica-Funktionen Expand und Coefficient. Uber-geben Sie den Funktionsnamen, den Grad des Polynoms sowie die Wertetabelle alsParameter an das Programm.
b) Schreiben Sie zur Erzeugung der Wertetabelle je ein Programm fur den aquidistantenFall sowie eines fur die Tschebyscheff-Abszissen.
Aufgabe 14
a) Wenden Sie das Programm aus Aufgabe 13 an auf die Interpolation der Funktionf(x) := e−x
2im Intervall [−2, 10] und berechnen Sie das Polynom bis zum Grad 10.
Die Stutzstellen sind “aquidistant” zu verteilen.
Aufgabe 15
a) Berechnen Sie die Maximumnorm der Abweichung zwischen dem Interpolationspoly-nom p und f aus Aufg. 14 auf einem aquidistanten Gitter mit 100 Stutzstellen.
b) Vergleichen Sie die aquidistante Interpolation mit der Tschebyscheff-Interpolation, so-wie mit der Taylorreihe von f vom Grad 10 (entwickelt um x0 = 0 und x0 = 4, benutzenSie hierzu die Funktion Series) bezuglich der Maximumnorm des Approximationsfeh-lers.
Aufgabe 16 Mit der Methode der kleinsten Quadrate sollen die Koeffizienten a1, a2 derFunktion f(x) = a1
x2 + a2
(x−9)2anhand von den gegebenen Punkten (1, 6), (2, 1), (7, 2), (8, 4)
bestimmt werden.
a) Stellen Sie die Normalgleichungen auf.
b) Berechnen Sie die Koeffizienten a1, a2.
c) Zeichnen Sie f im Intervall (0, 9) zusammen mit den Punkten in ein Diagramm.
Aufgabe 17
78 5 Ubungsaufgaben
a) Schreiben Sie ein Mathematica-Programm zur Bestimmung der Koeffizienten a1 . . . akeiner Funktion
f(x) = a1f1(x) + a2f2(x) + · · ·+ akfk(x)
nach der Methode der kleinsten Quadrate. Ubergabeparameter des Programms sindeine Wertetabelle mit Datenpunkten, sowie ein Vektor mit den Namen der Basisfunk-tionen f1, . . . , fk. Versuchen Sie ohne For-Schleifen zu arbeiten und benutzen Sie dieFunktion LinearSolve.
b) Testen Sie das Programm, indem Sie mit Hilfe einer Geradengleichung 100 Punkteauf einer Geraden erzeugen, und dann Ihr Programm anwenden um die Koeffizientender Geraden zu bestimmen. Wiederholen Sie den Test mit leicht verrauschten Daten(Addition einer kleinen Zufallszahl zu den Datenwerten).
c) Bestimmen Sie das Polynom 4. Grades, welches die Summe der Fehlerquadrate furfolgende Wertetabelle minimiert (Tabelle im Web http://www.hs-weingarten.de/
~ertel/vorlesungen/mathi/mathi-ueb15.txt):
8 -16186.19 -2810.82
10 773.87511 7352.3412 11454.513 15143.314 13976.15 15137.116 10383.417 14471.9
18 8016.5319 7922.0120 4638.3921 3029.2922 2500.2823 6543.824 3866.3725 2726.6826 6916.4427 8166.62
28 10104.29 15141.830 15940.531 19609.532 22738.33 25090.134 29882.635 31719.736 38915.637 37402.3
38 41046.639 37451.140 37332.241 29999.842 24818.143 10571.644 1589.8245 -17641.946 -37150.2
d) Berechnen Sie zu c) die Summe der Fehlerquadrate. Bestimmen sie dann die Koeffizi-enten einer Parabel und berechnen Sie erneut die Summe der Fehlerquadrate. WelchenUnterschied stellen Sie fest?
e) Geben Sie ein Verfahren an, mit dem Sie bei mehreren moglichen Satzen von Basis-funktionen experimentell bestimmen konnen, welcher der “beste” ist .
f) Suchen Sie eine Funktion, welche einen noch kleineren Fehler erzeugt.
Aufgabe 18
a) Andern Sie die rechte Seite der ersten Gleichung des Gleichungssystems am Beginnvon Abschnitt 4.4.5 so ab, dass es eindeutig losbar wird.
b) Welche Begingung muss gelten, damit ein lineares Gleichungssystem mit n Unbekann-ten und m > n Gleichungen eindeutig losbar ist?
Aufgabe 19 Verwenden Sie Satz 4.8 zur Losung des Gleichungssystems x1 = 1, x1 = 2, x2 =5 , x2 = 9 , x3 = −1 , x3 = 1 nach der Methode der kleinsten Quadrate.
Aufgabe 20 Gegeben seien die zwei Punkte (1, 1) und (2, 0) zur Berechnung einer kubischenSplinefunktion mit naturlichen Randbedingungen (y′′0 = y′′n = 0).
a) Wieviele Zeilen und Spalten hat hier die zur Bestimmung der y′′-Variablen verwendeteTridiagonalmatrix? (Begrundung!)
b) Bestimmen Sie die Splinefunktion indem Sie die Koeffizienten ai, bi, ci, di berechnen.
5.3 Numerik 79
Aufgabe 21 Gegeben seien die Punkte (−1, 1), (0, 0) und (1, 1).
a) Bestimmen Sie die beiden kubischen Teilsplines mit naturlichen Randbedingungen.
b) Warum ist s0(x) = x2 und s1(x) = x2 keine kubische Splinefunktion mit naturlichenRandbedingungen? Argumentieren Sie ohne Bezug auf die korrekte Losung.
Aufgabe 22 Wie verandert sich die Koeffizientenmatrix fur die Spline-Interpolation, wennstatt der Randbedingungen y′′0 = y′′n = 0 die Randbedingungen y′′0 = y′′1 , y′′n = y′′n−1 (2.Ableitung konstant am Rand) gefordert werden? Andern Sie die Koeffizientenmatrix ausBeispiel 7.1 im Skript entsprechend ab.
Aufgabe 23 Programmieren Sie den Tridiagonalalgorithmus.
Aufgabe 24 Schreiben Sie ein Programm zur Berechnung eines naturlichen kubischen Splineaus einer gegebenen Wertetabelle.
Aufgabe 25 Wenden Sie das Programm aus Aufgabe 24 an auf die Interpolation derFunktion f(x) := e−x
2im Intervall [−2, 10] auf einem aquidistanten Gitter mit 11 Punkten.
Aufgabe 26 Iterierte Funktionensysteme (IFS):
a) Berechnen Sie die Wertetabellen der beiden Folgen (xn), (yn) mit
xn+1 = a yn + b
yn+1 = c xn + d
x0 = y0 = 1
bis n = 20, wobei Sie die Parameterwerte a = 0.9, b = −0.9, c = −0.9, d = 0.9benutzen.
b) Verbinden Sie die Punkte (x0, y0) . . . (xn, yn) durch eine kubische Splinefunktion (natur-licher Spline). Wahlen Sie als Paramter fur die Parameterdarstellung den euklidischenAbstand der Punkte.
Aufgabe 27 Zur Berechnung von√a kann die Iteration xn+1 = a/xn mit a > 0, x0 > 0
versucht werden.
a) Stellen Sie die Interationsfolge grafisch dar.b) Begrunden Sie anhand der Zeichnung weshalb die Folge nicht konvergiert.c) Beweisen Sie, daß diese Folge nicht konvergiert.d) Wie muß man die Iterationsvorschrift xn+1 = a/xn verandern, so daß die Folge kon-
vergiert.
Aufgabe 28
a) Was heißt Konvergenz einer Folge (xn)n∈N? (Definition!)b) Geben Sie je eine konvergente, eine divergente sowie eine alternierende konvergente
und eine alternierende divergente Folge an.c) Geben Sie mindestens ein einfaches Konvergenzkriterium fur Folgen an.
80 5 Ubungsaufgaben
Aufgabe 29 Wenden sie das Intervallhalbierungsverfahren auf die Funktion
f(x) =x(1− x)
1− x2
mit dem Anfangsintervall [−4,−1/2] an. Berechnen Sie den Grenzwert der Folge auf minde-stens 4 Dezimalstellen. Begrunden Sie das uberraschende Ergebnis.
Aufgabe 30 Gesucht sind die Losungen der Gleichung
tanx = cosx (5.1)
im Intervall [0, π/2].
a) Zeigen Sie, daß die Gleichung (5.1) in [0, π/2] genau eine Losung hat.b) Im Folgenden soll die Gleichung (5.1) durch Fixpunktiteration gelost werden. Dazu
verwenden Sie die Form:x = f(x) := arctan(cosx) (5.2)
Geben Sie eine moglichst kleine Lipschitzschranke fur f und ein zugehoriges Teilinter-vall von [0, π/2] an.
c) Geben Sie eine a priori Abschatzung an fur die Zahl der Iterationsschritte bis eineGenauigkeit von mindestens 10−3 erreicht ist.
d) Berechnen Sie die Iterationsfolge (xn) der Fixpunktiteration mit dem Startwert x0 =π/4 bis n = 10.
e) Geben Sie nun mit Hilfe der a posteriori Abschatzung nach 8 Schritten ein Intervallan, in dem die Nullstelle mit Sicherheit liegt.
f) Warum ist die Umformung der Gleichung (5.1) in x = arccos(tanx) weniger gunstigals die oben verwendete?
g) Geben Sie ein moglichst einfaches Mathematica Programm (3-4 Befehle!) an, welchesdie Iterationsfolge berechnet und in eine Tabelle speichert.
Literaturverzeichnis
[1] G. Strang. Introduction to linear algebra. Wellesley Cambridge Pr, 3rd edition, 2003.4.2
[2] W. Cheney and D. Kincaid. Numerical mathematics and computing. ThomsonBrooks/Cole, 2007.
[3] S.M. Ross. Introduction to probability and statistics for engineers and scientists. Aca-demic Press, 2009.
[4] M. Brill. Mathematik fur Informatiker. Hanser Verlag, 2001. Sehr gutes Buch, das auchdiskrete Mathematik beinhaltet.
[5] M. Knorrenschild. Numerische Mathematik. Hanser Verlag, 2005.
[6] F. Reinhardt and H. Soeder. dtv–Atlas zur Mathematik, Band 1: Algebra und Grund-lagen. Deutscher Taschenbuchverlag, Munchen, 1977. Umfassende Darstellung der ge-samten Mathematik mit allen wichtigen Teilgebieten. Viele, didaktisch gut ausgewahlteBeispiele.
[7] H. Spath. Numerik. Vieweg, 1994. Leicht verstandlich, voraussichtlich werden grosereTeile der Vorlesung aus diesem Buch entnommen.
[8] H. R. Schwarz. Numerische Mathematik. Teubner Verlag, 1988. Gutes Buch, sehrausfuhrlich. 4.6.2, 4.6.3
[9] S. Wolfram. Mathematica, A System for Doing Mathematics by Computer. AddisonWesley, 1991. Das Standardwerk des Mathematica-Entwicklers. Daneben gibt es vieleandere Bucher uber Mathematica.
[10] P. J. Fleming and J. J. Wallace. How not to Lie with Statistics: The Correct Way toSummarize Benchmark Results. Comm. of the ACM, 29(3):218–221, 1986.
[11] J.E. Smith. Characterizing Computer Performance with a Single Number. Communi-cations of the ACM, 31(10):1202–1206, 1988.
[12] J. Aczel. Lectures on Functional Equations and Their Applications, pages 148–151,240–244, 291. Academic Press, New York/London, 1966.
[13] W. Ertel. On the Definition of Speedup. In PARLE’94, Parallel Architectures andLanguages Europe, Lect. Notes in Comp. Sci. 817, pages 289–300. Springer, Berlin/NewYork, 1994.
[14] D.E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Program-ming, . Addison-Wesley, 1969. Neue Auflage 1998.
82 LITERATURVERZEICHNIS
[15] U. Maurer. A universal statistical test for random bit generators. Journal of Crypto-graphy, 5(2):89–105, 1992. 2.1.1
[16] G. Marsaglia. A current view of random number generators. In Computer Science andStatistics: The Interface., pages 3–10. Elsevier Science, 1985.
[17] B. Jun and P. Kocher. The intel random number generator (white paper). http:
//developer.intel.com/design/security/rng/rngppr.htm, 1999. 2.4
[18] W. Ertel and E. Schreck. Real random numbers produced by a maxtor disk drive.http://erde.fbe.fh-weingarten.de/ertel/rrng/maxtor.html, 2000. 2.4
[19] J. von Neumann. Various techniques used in connection with random digits. In vonNeumann’s Collected Works, volume 5. Pergamon Press, 1963.
[20] L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random numbergenerator. SIAM Journal of Computing, 15(2):364–383, 1986. 2.2.2
[21] M. Li and P. Vitanyi. Two decades of applied kolmogorov complexity. In 3rd IEEEConference on Structure in Complexity theory, pages 80–101, 1988. 2.4
[22] B. Schneier. Angewandte Kryptogrphie. Addison-Wesley, 1996. Deutsche Ubersetzung.2.2
[23] The intel random number generator. Intel Platform Security Division, http://
developer.intel.com/design/security/rng/rngppr.htm, 1999. 2.4
