http://www.oelinger.de Home Maria Oelinger   sitemap
	zurück zur Übersicht Prüfungsprotokoll Hauptdiplomprüfung Mathematik Fach: Numerik I Prüfer: Prof. Dr. F. Pittnauer, Universität Duisburg Datum: 24.10.2000 Dauer: ca. 30 Min Note: sehr gut Fragenkatalog: 5-Min-Thema: Banachscher Fixpunktsatz mit Beweis. Sei f eine stark kontrahierende Abbildung eines vollständigen metrischen Raumes (X, d) in sich. Dann besitzt f genau einen Fixpunkt in X. Existenz Idee: Zeigen, dass I (f, x 0) eine Cauchy-Folge auf X ist und damit konvergiert. Wähle x 0  X und bilde I (f, x 0). Da f kontrahierend ist, gilt (wegen d (x n, x n – 1) = d (f (x n – 1), f (x n))  ( f) n • d (x n – 1, x n) ) : d (x n, x n + 1)    f • d (x n – 1, x n)  …  ( f) n • d (x 0, x 1) Sei nun o. B. d. A. m > n: d (x n, x m)  d (x n, x n + 1) + ... + d (xm – 1, x m) Dreiecksungleichung für Metrik d  (( f) n + ( f) n + 1 … + ( f) m – 1 ) • d (x 0, x 1) nach obiger Abschätzung = ( f) n • [1 + ( f) 1 + … + ( f) m – n – 1 ] • d (x 0, x 1) = ( f) n • d (x 0, x 1) • =0,…,m–n–1( f)   ( f) n • d (x 0, x 1) • =0,…,( f)  positive Werte zur Summe addiert =  •d (x 0, x 1) geometrische Reihe D.h. der Abstand der Folgeglieder wird beliebig klein (da 0  f < 1) und damit =>   I (f, x 0) ist Cauchy-Folge =>   es ex. lim n x n = x*  X x* = lim n x n = lim n f (x n – 1) = f (lim n x n – 1 ) = f (x*) Eindeutigkeit x*, y*  X seien Fixpunkte. Dann gilt: d (x*, y*) = d [f (x*), f (y*)]   f • d (x*, y*) <=> (1 –  f) • d (x*, y*)  0     (1 –  f) > 0, da 0  f) < 1 und d (x, y)  0, da d Metrik ist d (x*, y*) = 0   <=>   x* = y*         Wo finden wir eine Anwendung des Satzes? Also Übergang vom Banachschen Fixpunktsatz zu linearen Gleichungssystemen: Wann sind die Voraussetzungen erfüllt, dass die Abb x = Ax + b stark kontrahierend ist? A quadratisch, regulär, Spektralradius  (A) < 1 (Kontraktionszahl). Ist das Kriterium  (A) < 1 hinreichend für Konvergenz? Ja Welcher Raum ist das? Rn oder Cn Sind diese Räume denn vollständig? Ja, z.B. d (x, y) = || x - y ||   (Vektornorm, Metrik)   Manchmal ist die Kontraktionszahl aber nah bei 1, was tut man dann?   Die Konvergenz ist dann nicht so gut, also verwendet man Relaxationsfaktoren.   Was ist eine stark kontrahierende Abbildung?   f: XX eines metrischen Raumes (X, d) in sich, die dehnungsbeschränkt ist, d.h. d [f (x), f (y)]  k • d (x, y)    x, y  X und festes 0  k <  gilt mit Dehnungszahl  f := inf { k | k erfüllt obige Bedingung}, für stark kontrahierendes f ist 0   f < 1   Welches Relaxationsverfahren kennen Sie? JOR-Verfahren mit Voraussetzung: A  Mn (R) mit diag (A) = I ist regulär. Zerlegung: A = M – N mit M = (1/) • I, N = ((1/) – 1) • I + J 1     mit   R \ {0} Iteration: x (0)  R n, x (k+1) = J  • x (k) + b,   wobei JOR-Matrix J  = (1 – ) • I + J 1 und optimaler Relaxationsfaktor  0 ist dann: Falls (J 0)  (J)   für alle R \ {0} mit  (J) < 1 gilt. Explizit: Für symetrisches und positiv-definites A = I – J  Mn (R) mit den Eigenwerten 0 <  1   2  …   n ist  0 = 2 / ( 1 +  n) der optimale Relaxationsfaktor des JOR-Verfahrens, und es gilt:  (J 0 ) = ((n – 1) / (1 + n)) < 1 Konvergenz: Für symetrisches und positiv-definites A = I – J  Mn (R) mit den Eigenwerten 0 < 1  2  …  n konvergiert das JOR-Verfahren für alle   R mit 0 <  < 2/n   gegen die Lösung von Ax = b. Lemma von Kahan: Was folgt für daraus?   Dass es aus dem Intervall (0, 2) sein muss.   Wie sieht es bei mehrdimensionalen Gleichungssystemen aus? Da stand ich auf dem Schlauch und wusste nicht, was gemeint war.   Newton-Verfahren Zusammenhang mit Banachschem Fixpunktsatz (Welche Kontraktionszahl haben wir hier? - Wusste ich leider auch nicht.) Iterationsvorschrift: x 0  [a, b] x n+1 = x n – (F (x n)/F' (x n))   (n  N 0) Dabei ist F: [a, b]R eine einmal stetig differenzierbare Abbildung. Konvergenz Die Abbildung F: [a, b]R sei zweimal stetig differenzierbar und es gelte (i) F (a) • F (b) < 0   (ii) F' (x)  0 für alle x  [a, b] (iii) F (x 0) • F'' (x) > 0 für alle x  [a, b] und ein festes x 0  [a, b] Dann konvergiert das Newton-Verfahren mit dem Startwert x 0 monoton gegen die einzige einfache Nullstelle x*  (a, b) von F mit dem Konvergenzgrad  = 2 und dem asymptotischen Fehlerkoeffizienten q  M'' / 2m'.  Dabei ist 0 < m' = min axb | F' (x) | <  und 0 < M'' = Max axb | F'' (x) | < . Was ist ? Konvergenzgrad der Nullfolge positiver Zahlen (rn) nN0  := sup {c  R | lim sup n (rn+1 / rnc) < } Was ist rn? rn = d (x n, x*) mit Nullstelle x* Wahl des Startwertes x 0: Gut oder schlecht? Wie würden Sie das einem Schüler erkären? Anhand der Skizze erklären, wie die Tangenten auf den Nullpunkt zulaufen, Schnitt mit der x-Achse ist neuer Wert für die Iteration.   Newton-Verfahren mehrdimensional Sei D  Rn offene Menge und F: DRn stetig differenzierbare Abbildung, ferner sei die Jacobi-Matrix F' (x (k)) regulär für alle k  N0. Iteration: x (0)  D x (k+1) = x (k) – (F' (x (k) ))–1 • F (x (k) )    (k  N0)   Konvergenz über Satz von Newton-Kantorowitsch D  Rn sei offene Menge und D0  D konvex. Ferner sei F: DRn gegeben mit (i) F ist auf D stetig und auf D0 differenzierbar (ii) Es existiert ein x (0)  D 0 und Konstanten r, , , , h = (1/2) •       mit Br (x (0)) = { x  Rn ; || x – x (0) || < r }  D0, 0 < h < 1 und r =  / (1 – h) (iii) || F' (x) – F' (y) ||   • || x – y ||    für alle x, y  D0 (iv) [F' (x)]–1 existiert und || [F' (x)]–1 ||     gilt für alle x  D0 (v) || [F' (x (0))]–1 • F (x (0)) ||   Dann gelten (1) Für die Punkte x (0), x (k+1) = x (k) + [F' (x (k) )]–1 • F (x (k) )    mit k  N0 gilt: x (k)  Br (x (0) ) für alle k  N0 (2) Es existiert x* = lim k x (k) und es gilt: x*  Br (x (0) ) und F (x*) = 0 (3) Die Vektorfolge x (0), x (k+1) (s.o.) mit k  N0 hat den Konvergenzgrad  = 2 und es gilt die Fehlerabschätzung (Keine Sorge, in der Prüfung war es nicht ganz so ausfü.) Was ist das für eine Kugel Br (x (0) ), wieso brauchen wir die? Anhand der Skizze gezeigt, dass es wichtig ist, dass man in der Nähe der gesuchten Nullstelle startet: Sonst läuft man Gefahr, eine andere Nullstelle zu erwischen.   Satz von Ostrowski Die Abbildung G: RnRn erfülle die Bedingungen (i) Es existiert ein Fixpunkt x* = G (x*)  Rn (ii) G ist stetig differenhzierbar in einer Umgebung von x* (iii)  (G' (x*)) < 1 Dann konvergiert das Banachsche Iterationsverfahren für jeden genügend nahe bei x* liegenden Startvektor x 0  Rn gegen den Fixpunkt x* geometrisch mit dem asymptotischen Fehlerkoeffizienten  =  (G' (x*)). (Die Bedingung (ii) habe ich weggelassen bzw. für die dritte einfach vorausgesetzt.)   zurück zur Übersicht Feel free to send me email: maria@oelinger.de
	© 2000 Maria Oelinger cand. math. Prüfungsprotokoll Letzte Änderung: 28.11.2000 address: http://www.oelinger.de/maria/numerik/protokoll.htm