2. Lineare Gleichungssysteme: direkte und iterative Lösungsverfahren Problem (P2): Löse Ax = b, A ∈ Rn und b ∈ R. 2.1 Satz: Die folgenden Aussagen sind äquivalent: (i) Ax = b ist für jedes b eindeutig lösbar; (ii) Rang(A) = n; (iii) det(A) 6= 0; (iv) Alle Eingenwerte von A sind ungleich Null; (v) A ist invertierbar; (vi) Ax = 0 hat eine eindeutige Lösung x = 0. Konditionszahlen einer Matrix, Matrixnormen 2.2 Definition: Eine Abbildung k · k : Rn×n → [0, ∞) heißt Matrixnorm, wenn (i) kAk > 0 für alle A ∈ Rn×n , A 6= 0; (ii) kα · Ak = |α| · kAk für alle A ∈ Rn×n , α ∈ R; (iii) kA + Bk ≤ kAk + kBk für alle A, B ∈ Rn×n . Eine Matrixnorm k · k auf Rn×n heißt verträglich mit einer Vektornorm k · k′ auf Rn , wenn gilt kAxk′ ≤ kAk · kxk′ für alle A ∈ Rn×n , x ∈ Rn . 2.3 Definition: Sei A ∈ Rn×n invertierbar. Konditionszahl cond(A) von A ist definiert durch cond(A) = kAkkA−1 k. Beispiele: kAk∞ = max 1≤j≤n kAk1 = max 1≤k≤n n X |ajk | (Zeilensummennorm), k=1 n X |ajk | (Spaltensummennorm). j=1 Sei A ∈ Rn×n symmetrisch, dann gilt kAk2 = max{|λ| : λ Eigenwert von A} (Spektralnorm). Die Matrixnormen k · k1 , k · k2 bzw. k · k∞ sind verträglich mit den entsprechenden Vektornormen k · k1 , k · k2 bzw. k · k∞ . 2.4 Fehleranalyse, Kondition Problem (P2): Löse Ax = b, A ∈ Rn×n und b ∈ Rn . f Löse Ae ex = e e ∈ Rn×n und e Problem (P2): b, A b ∈ Rn . Kondition: Vergleiche den Ausgabefehler kx − xek mit den Eingabefehler e und kb − e kA − Ak bk, wobei die Lösungen x und e x von Ax = b bzw. e Ae x =e b ohne Rundungsfehler (exakt) berechnet werden; Hilfsatz: Sei B ∈ Rn×n mit kBk < 1. Dann ist die Matrix I + B invertierbar, und es gilt k(I + B)−1 k ≤ 1 . 1 − kBk Störungssatz: Die Matrix A ∈ Rn×n sei invertierbar, und es sei 1 . kA−1 k e < kA − Ak e ebenfalls invertierbar, und für den relativen Fehler Dann ist die Matrix A der Lösung von Ax = b gilt ! e kx − e xk kb − e bk kA − Ak cond(A) . ≤ + e kxk kbk kAk 1 − cond(A) · kA−Ak kAk Bemerkung: Ist cond(A) · xk kx − e kxk k∆Ak kAk << 1, so wird . cond(A) e kb − e bk kA − Ak + kbk kAk ! , d.h. cond(A) ist der Verstärkungsfaktor, mit dem sich die Eingabefehler e und b − e A−A b auf x − e x auswirken. 2.5 Eliminationsverfahren Satz (Cramersche Regel): Sei A ∈ Rn×n regulär. Die Lösung x von Ax = b ergibt sich als a1,1 . . . a1,j−1 b1 a1,j+1 . . . a1,n .. .. .. .. det ... . . . . an,1 . . . an,j−1 bn an,j+1 . . . an,n , j = 1, . . . , n. xj = det(A) Rechner mit 108 Gleitkommaoperationen pro Sekunde n Rechenzeit 10 0.4 s 12 1 min 14 36 Stunden 16 41 Tage 18 38 Jahre 20 16000 Jahre Gauß-Elimination mit Pivotierung und Äquilibrierung/Zeilenskalierung Beispiel (Gauß-Elimination mit Pivotierung): (P2) 0.Initialisierung Löse 3 2 1 6 x1 2 x2 7 . 3 · = 1 x3 4 1 1 1 [A[0] ; b[0] ] = [A; b] 1.Schritt Pivotierung (keine Pivotierung erforderlich): 1 0 [1] [1] Gauß-Elimination: [A ; b ] = −2/3 1 −1/3 0 [0] [0] [0] [0] [Ap ; bp ] = I · [A ; b ] 0 [0] [0] 0 · [Ap ; bp ] 1 2.Schritt 1 0 0 Pivotierung: = 0 0 1 · [A[1] ; b[1] ] 0 1 0 1 0 0 [1] [1] [2] [2] 0 1 0 · [Ap ; bp ] Gauß-Elimination: [A ; b ] = 0 −1/2 1 3 1 6 x1 2 0 2/3 −1 x2 10/3 . ⇒ Löse Ax = b ⇔ Löse · = 0 0 −1/2 x3 4 [1] [1] [Ap ; bp ] Definitionen+Eigenschaften: (i) Permutationsmatrix Pi ,j ist die Einheitsmatrix I mit vertauschten i−ten und j−ten Zeilen. Die Matrixmultiplikation Pi ,j · A vertauscht i−te und j−te Zeilen von A. (ii) Pivotsuche: Aus Gründen der numerischen Stabilität trifft man gewöhnlich die Wahl ar (k),k = max |aj,k | , k = 1, . . . , n − 1, r (k) ∈ {k, . . . , n}. k≤j≤n Das Element ar (k),k heißt Pivotelement. (iii) Pivotierung (k-ter Schritt): Pivotsuche und Zeilenvertauschung [A[k−1] ; bp[k−1] ] = Pk,r (k) · [A[k−1] ; b [k−1] ] p mit 1 ≤ k ≤ r (k) ≤ n. Algorithmus: (Gauß-Elimination mit Pivotierung) Gegeben: A ∈ Rn×n invertierbar, b ∈ Rn . Initialisierung: [A[0] ; b [0] ] = [A; b] Für k = 1, . . . , n − 1: [k−1] [k−1] Pivotsuche: ar (k),k = max aj,k , k ≤ r (k) ≤ n k≤j≤n [k−1] Pivotierung: [Ap [k−1] ; bp ] = Pk,r (k) · [A[k−1] ; b [k−1] ] [k−1],p Gauß-Elimination: mit gj,k = aj,k [A ; b ] = [k] [k] [k−1],p /ak,k 1 .. .1 −gk+1,k .. . −gn,k 1 .. . 1 , j = k + 1, . . . , n, · [A[k−1] ; b [k−1] ] p p Bemerkungen: (i) A[n−1] ist eine obere Dreiecksmatrix. (ii) Ax = b ist äquivalent zu A[n−1] · x = b [n−1] . (iii) Man braucht a priori nicht zu wissen, ob A invertierbar ist. Ist [k−1] ar (k),k = 0 für ein k = 1, . . . , n − 1, dann ist A singulär und der Algorithmus muss abgebrochen werden. Lemma: Sei A ∈ Rn×n invertierbar, b ∈ Rn . Die zur Lösung von Ax = b mit Hilfe des Gauß-Eliminationsverfahren erforderliche Anzahl von 3 arithmetischen Operationen ist ≈ n3 . Satz (Numerische Stabilität der Gauß-Elimination): Seien A ∈ Rn×n invertierbar und b ∈ Rn . Das Gleichungssystem A · x = b wird mit Gauß-Elimination mit Pivotierung gelöst. Dann ist die unter dem Einfluss von Rundungsfehlern tatsächlich berechnete Lösung e x die exakte Lösung e·e des Gleichungssystems A x = b mit e ∞ kA − Ak ≤ 1.01 · 2n−1 · (n3 + 2n2 ) · eps. kAk∞ Äquilibrierung/Zeilenskalierung: Man kann manchmal die Konditionszahl einer invertierbaren Matrix A ∈ Rn×n verkleinern, indem man die Matrix A mit einer Diagonalmatrix !−1 d11 n X .. D = |ajk | , , djj = . k=1 dnn von links multipliziert (skaliert). Das Problem (P2) Löse Ax = b, hat die selbe Lösung als DAx = Db. A ∈ Rn×n , b ∈ Rn , 2.6 Iterationsverfahren: Jacobi- und Gauß-Seidel-Verfahren Fixpunkt-Iteration: Mit einer beliebigen invertierbaren Matrix C ∈ Rn×n gilt die Äquivalenz Ax = b ⇔ Cx = Cx − Ax + b ⇔ x = (I − C −1 A)x + C −1 b. Man versucht C so zu wählen, dass • zu gegebenem Vektor x [k] , k ≥ 0, der neue Vektor x [k+1] = (I − C −1 A)x [k] + C −1 b mit wenig Aufwand zu berechnen ist; • die Iterationsfunktion φ : Rn → Rn , φ(x) = (I − C −1 A)x + C −1 b kontrahierend ist und eine möglichst kleine Kontraktionszahl besitzt. Darstellung der Iterationsfunktion: Die Matrix A wird in drei Teile zerlegt gemäß A = L + D + R mit 0 a L = 21 .. . an1 ··· .. . .. . ··· ··· .. . an,n−1 0 a11 .. . 0 , D = .. .. . . 0 0 0 .. .. . . ··· ··· .. . .. . 0 0 0 . .. . . . , R = .. . 0 ann 0 a12 .. . ··· ··· .. . .. . ··· a1n .. . . an−1,n 0 Proposition: a) Die Iterationsfunktion des Jacobi-Verfahrens (JV) lautet φJV (x) = (I − D −1 A)x + D −1 b = −D −1 (L + R)x + D −1 b. b) Die Iterationsfunktion des Gauß-Seidel-Verfahrens (GSV) lautet φGSV (x) = (I − (L + D)−1 A)x + (L + D)−1 b = −(L + D)−1 Rx + (L + D)−1 b. Verglichen mit der allgemeinen Form φ(x) = (I − C −1 A)x + C −1 b, werden hier also die folgenden Matrizen C verwendet: C = D, ajj = 6 0, j = 1, . . . , n. C = L + D ajj 6= 0, j = 1, . . . , n. (JV) (GSV) Konvergenzanalyse der Folge x [k+1] = φ(x [k] ), k ≥ 0: Definition: Die Iterationsfunktion φ : Rn → Rn heißt kontrahierend, falls es eine Norm k · k existiert, so dass für alle x, y ∈ Rn gilt kφ(x) − φ(y )k ≤ Lkx − y k mit der Kontraktionszahl 0 ≥ L = kI − C −1 Ak < 1. Satz: Die Matrizen A und C seien invertierbar. Dann sind die folgenden Aussagen äquivalent: (i) Die Folge (x [k] )k∈N0 konvergiert bei beliebigem Startvektor x [0] ∈ Rn gegen die Lösung x ∗ von Ax = b. (ii) Die Iterationsmatrix B = I − C −1 A hat den Spektralradius ρ(B) = max{|λ| : λ Eigenwert von B} < 1. (iii) Es gibt eine (natürliche) Matrixnorm k · k auf Rn×n mit kBk < 1. Beweisidee ((iii ) ⇒ (i )): Banachscher Fixpunktsatz: Sei φ : Rn → Rn kontrahierend mit der Kontraktionszahl 0 ≤ L < 1. • • Dann hat x = φ(x) genau eine Lösung x ∗ ∈ Rn . Für jeden Startwert x [0] ∈ Rn konvergiert die Folge (x [k] )k∈N0 mit x [k+1] = φ(x [k] ), k ≥ 0, gegen x ∗ . Beweisidee (Äquivalenz von (ii ) und (iii )): Hilfssatz: Gegeben sei die Matrix B ∈ Rn×n . • Für jede natürliche Matrixnorm k · k : Rn×n → R gilt ρ(B) ≤ kBk. • Zur Matrix B ∈ Rn×n und beliebigem ǫ > 0 existiert eine natürliche Matrixnorm k · k : Rn×n → R so, dass für den Spektralradius ρ(B) gilt kBk ≤ ρ(B) + ǫ. Bemerkungen: (i) Der Banachscher Fixpunktsatz liefert auch die folgenden Fehlerabschätzungen: für k ≥ 0 gelten kx [k+1] − x [k] k ≤ kx [k] − x ∗ k ≤ L kx [k] − x [k−1] k (a posteriori) 1−L Lk kx [1] − x [0] k (a priori) 1−L (ii) Die Matrixnormen k · kp , p = 1, 2, ∞ sind natürliche Matrixnormen. (iii) Satz: Falls die Matrix A ∈ Rn×n stark diagonaldominant ist, d.h. |ajj | > n X |ajk | für alle j = 1, . . . , n, k=1 k6=j dann konvergieren die beiden Jacobi- und Gauß-Seidel-Verfahren für jeden Startvektor x [0] ∈ Rn .
© Copyright 2025 ExpyDoc