Blatt 04-Loesung - NumMathe PDF

Preview

Summary

NumMathe...

Description

Dr. Frank S. Attia, Dr. Florian Leydecker, M.Sc. Jan Philipp Thiele

Numerische Mathematik für Ingenieure (SS 2018) Lösungshinweise zu Blatt 4,

04. Mai 2018

Themen (a) Konvergenz linearer Iterationsverfahren - Charakterisierung: Kapitel 3.4.1 - Hinreichendes Kriterium: Kapitel 3.4.2 - Fehlerabschätzung: Kapitel 3.4.3 (b) Eigenschaften von Matrizen - Kondition: Definition 3.6 - Eigenwerte: Definition 4.1 - Ähnlichkeit: Kapitel 4.1.1 - Hauptachsentransformation 4.2 - Kreissatz von Gerschgorin: Satz 4.9

Präsenzaufgaben (Vorlesung) Aufgabe 4.1

[Berechnung von k kp -Matrix-Normen und Konditionszahl]

Berechnen Sie für   1 3 −3 die Normen kBk1 und kBk∞ , 00 1   21 (b) die Matrizen B = 0 1 und C = BT B: kBk2 und kCk2 sowie die Konditionszahl κ2 (C). 00 (a) die Matrix B =

Aufgabe 4.2

[Lineare Iterationsverfahren: Fehlerabschätzungen]

Man betrachte das lineare Gleichungssystem Ax = b mit   8 1 1 A = 2 7 1  , 1 −1 5

  20 b = 26 . 4

(a) Zeigen Sie, dass die Gauß-Seidel-Verfahren und das Jacobi-Verfahren zur iterativen Lösung des LGS für jeden beliebigen Startvektor konvergieren. Wie lautet die Iterationsmatrix für das Jacobi-Verfahren? (b) Starten Sie mit x(0) = (1, 2, 1)T und berechnen Sie mit dem Jacobi-Verfahren sowie dem Gauß-SeidelVerfahren x(1) . Wieviele Schritte sind mit dem Jacobi-Verfahren (höchstens) nötig, um die Genauigkeit von 0.001 in allen Komponenten zu erhalten (a priori-Abschätzung)? Benutzen Sie die ∞-Norm. (c) Berechnen Sie mit dem Jacobi-Verfahren die Iterierte x(2) und schätzen Sie den Fehler kx(2) − xk∞ im nachhinein (a posteriori) ab. Hinweis: Rechnen Sie auf 4 Stellen genau.

Kurzteil Aufgabe 4.3 Zeigen Sie: Genau dann ist A ∈ Cn×n regulär, wenn λ = 0 kein Eigenwert von A ist. Lösung. Vorbemerkung: Die Begriffe regulär und invertierbar werden in dieser Vorlesung synonym verwendet. Es gilt A ist regulär ⇐⇒ det A 6= 0 ⇐⇒ det(0E − A) 6= 0 ⇐⇒ χA (0) 6= 0 ⇐⇒ 0 ist kein EW von A. Die erste Äquivalenz steht im Skript [s. 1. Abschnitt Lineare Gleichungssysteme und die LR-Zerlegung mit Spaltenpivotwahl aus dem Kapitel Direkte Verfahren zur Lösung linearer Gleichungssysteme]. Alternativ: Dies folgt schon aus der Definition eines Eigenwerts: Es gilt λ

0 ist kein Eigenwert von A

⇐⇒ ⇐⇒

⇐⇒

z}|{ Ax = | 0{z x} ist eindeutig lösbar (mit x = 0) =0

Jedes LGS Ax = b ist eindeutig lösbar

A ist invertierbar.

Aufgabe 4.4 Es sei λ ∈ C ein Eigenwert von A ∈ Cn×n . Zeigen Sie, dass Vielfache und Summen von Eigenvektoren (die nicht den Nullvektor ergeben) von A zu λ wieder Eigenvektoren von A zu λ sind. Lösung. Es seien v, w ∈ Cn zwei Eigenvektoren von A zu λ und α ∈ C. Dann gilt: A(v + w) = Av + Aw = λv + λw = λ(v + w), A(αv) = αAv = αλv = λ(αv) Somit sind auch v + w und αv Eigenvektoren von A zu λ, falls diese nicht der Nullvektor sind. Aufgabe 4.5 Wieviele reelle Matrizen A ∈ R4×4 gibt es, die genau die Eigenwerte 2 (Vielfachheit 3) und i (Vielfachheit 1) haben? Lösung. Es gibt keine solche Matrix, da mit i auch −i ein Eigenwert von A sein müsste. Denn: Eigenwerte sind die Nullstellen des charakteristischen Polynoms det(λI − A) der Matrix A. Komplexe Nullstellen von Polynomen mit reellwertigen Koeffizienten kommen aber immer nur in komplex konjugierten Paaren vor, d. h. zu jeder komplexen Nullstelle z = a + bi des Polynoms ist auch ¯z = a − bi eine komplexe Nullstelle des Polynoms. Alternativ: Ax = λx

⇐⇒

Ax = λx

⇐⇒

Ax = λx

⇐⇒

A x = λ¯ x .

Bei reellwertiger Matrix ist also x EV zum EW λ genau dann, wenn x EV zum EW λ ist.

Aufgabe 4.6 Folgern Sie aus dem Gerschgorinschen Kreissatz, dass strikt diagonaldominante Matrizen regulär sind. Lösung. Sei A ∈ Rn×n eine strikt zeilendiagonaldominante Matrix. Der i-te Zeilenkreis ist X    |aij|. mit ri = Ki = z ∈ C  |z − aii| 6 ri j6=i

Da A strikt zeilendiagonaldominant ist, haben wir ri < |aii |, also 0 ∈ / Ki. Daher kann nach dem Satz von Gerschgorin 0 kein EW von A sein, d. h. A ist regulär. Für strikt spaltendiagonaldominante Matrizen argumentiert man analog mit Spaltenkreisen. Aufgabe 4.7 Zeigen Sie: Es sei A ∈ Rn×n und A = BC mit einer invertierbaren Matrix B. Dann ist eA := CB ähnlich zu A.

Lösung.

e −1 = BCBB−1 = BC = A. BAB Aufgabenteil Aufgabe 4.8 Sei A ∈ R

n×n

[Kondition] . Man zeige:

(a) (A ist invertierbar und x ist Eigenvektor von A zum EW λ) ⇐⇒ (A ist invertierbar und x ist Eigenvektor von A−1 zum EW λ−1 ). Was bedeutet das für kAk2 und kA−1 k2 ? (b) Ist A symmetrisch und invertierbar und λ1 (bzw. λn ) ein Eigenwert von A mit kleinstem (bzw. größtem) |λ | Betrag, dann ist κ2 (A) = |λn1 | . Man berechne −1

(c) die Ausdrücke kHk2 , kH k2 und κ2 (H) für die Hilbert-Matrix H mit H = (d) die Ausdrücke kGk2 , kG−1 k2 und κ2 (G) für die Matrix G mit G =





 12 . 01

1 2 1 1 2 3

1

 ,

Lösung. (a) A invertierbar und x EV von A zum EW λ ⇔ ⇔ ⇔

siehe seite 52

Ax = λx, x 6= 0 x = λA−1 x, x = 6 0 1 x = A−1 x, x 6 0 = λ

|A−1 · | · λ1

1 EW um EV x von A−1 λ

Da die EWte von M := AT A positiv sind (da A invertierbar ist, kann 0 kein EW von A sein, und M ist somit nicht nur positiv semidefinit sondern sogar positiv definit)   √ −1 √ √ 1 −1 √ = min λ kAk2 = max λ, kA k2 = max −1 λ = max λ EW von M λ EW von M λ EW von M λ EW von M λ

(b) A symmetrisch ⇒ kAk2 =

max

λ EW von A

|λ|

1 |λ| = max | | = kA k2 = max λ EW von A λ λ EW von A−1 max |λ| |λn | = κ2 (A) = kAk2 · kA−1 k2 = min |λ| |λ1 | −1



min

λ EW von A

−1 |λ|

(c) 

H=

EW-Berechnung bei Matrix wie S.52. Nicht verwirren lassen mit EW Berechnung von Vektoren

1 2 1 1 2 3

1

Zuerst berechnen wir die EWte von H (symmetrisch)     λ − 1 − 1  1 1 2   − = (λ − 1) λ − |λI − H| =  1 − 2 λ − 13  3 4 4 1 ! 4 1 1 = λ2 − λ + − = λ2 − λ + =0 12 3 3 4 3 pq-Formel: λ1,2

2 = ± 3

r

4 2 1 = ± − 12 9 3

r

√ √ 2 3 16 4 ± 13 13 = ± − = 36 36 6 6 3

λ1 ≈ 0.0657,

λ2 ≈ 1.2676

1 = 15.2207 0.0657 κ2 (H) = kHk2 kH−1 k2 ≈ 1.2676 · 15.2207 = 19.2938

H symmetrisch ⇒ kHk2 ≈ 1.2676,

(d)

kH−1 k2 ≈

  12 G= 01 Zuerst benötigen wir GT G da G nicht symmetrisch ist.      10 12 12 GT G = = 21 01 25 EWte   λ − 1 −2   = (λ − 1)(λ − 5) − 4 = λ2 − λ − 5λ + 5 − 4 = λ2 − 6λ + 1 = 0 |λI − GT G| =  −2 λ − 5

pq-Formel

√ √ 9−1=3± 8 r q q √ √ 2 √ |λ| = 3 + 2 2 = 1+ 2 =1+ 2 kG k2 = max λ1,2 = 3 ±

kG−1 k2 = ⇒



λ EW von GT G

min

λ EW von GT G

−1/2 |λ| =p

√ 1+ 2 ≈ 5.8284 κ2 (G) = √ 2−1

1

1 √ =√ 2 −1 3−2 2

[Konditionszahlen linearer Gleichungssysteme]  −20  Wir betrachten die Matrix A = 10 1 11 und vergleichen die Kondition von Matrizen/Umformungen, die beim Lösen des LGS Ax = b unter Verwendung der Algorithmen „LR-Zerlegung“ A = . . . und „LR-Zerlegung mit Spaltenpivotsuche“ PA = . . . mit P = P1 vorkommen (vergl. Beispiel 2.3 im Skript). Aufgabe 4.9

(a) Bestimmen Sie die Konditionszahlen κ∞ (A−1 ) und κ∞ ((PA)−1 ) für das Lösen des LGS Ax = b, bzw. PAx = Pb. (Verwenden Sie die Zeilensummennorm.) ˆ −1 (b) Bestimmen Sie die Frobeniusmatrix L−1 1 bzw. L1 des ersten Schrittes des Gaußalgorithmus ohne bzw. mit Spaltenpivotsuche und berechnen Sie sowohl die Konditionszahlen beider Frobeniusmatrizen als auch die Konditionszahlen des Lösens der resultierenden linearen Gleichungssysteme L−11 Ax = L1−1b und ˆ −1 Lˆ −1 1 (P1 A)x = L 1 P1 b Lösung. Bezeichnungen/Erkenntnisse vorab: man ist nach einem Schrittt fertig; also gilt im Algorithmus mit Spaltenpivotsuche P1 = P und ˆL1 = L1 [aber 6= L1 aus dem GA ohne Spaltenpivotsuche], weshalb wir bei ˜ = PA = P1 A. Spaltenpivotsuche zur Unterscheidung die Schreibweise ˆ L1 wählen. Außerdem setzen wir A (a) Zunächst berechnen wir die im Folgenden benötigten Matrizen     1 1 1 −1 1 −1 ˜A−1 = A−1 = −20 . und 1 − 10−20 −10−20 1 10 − 1 −1 10−20 2 ≈ 2 und somit κ∞ (A−1 ) = kA−1 k∞ kAk∞ ≈ 4. Analog Es ist kAk∞ = 2 und kA−1 k∞ = |10−20 −1| 2 ˜ ∞ = 2 und k A ˜ −1 k∞ = berechnen wir k Ak ≈ 2 und erhalten somit ebenfalls κ∞ ( ˜A−1 ) ≈ 4. |1−10−20 |

ˆ −1 (b) Die Umformungsmatrizen L−1 1 und L1 , welche im ersten Schritt des Gaußalgorithmus angewandt werden, sind gegeben durch     1 0 1 0 −1 ˆ = L L1−1 = , und 1 −10−20 1 −1020 1

20 20 40 −20 ˆ −1 mit Konditionszahlen κ∞ (L−1 )(1+10−20 ) ≈ 1. 1 ) = (1+10 )(1+10 ) ≈ 10 und κ ∞ (L 1 ) = (1+10 Ferner berechnen sich die Konditionszahlen des Lösens des LGS mit    −20   −1 −1 10 1 1 1 − 1020 −1 L−1 , , L A = A = 1 1 0 10−20 0 1 − 1020 10−20 − 1      −1 −1 1 1 1 − 10−20 −1 ˜ ˜= 1 ˆ A A = L Lˆ −1 , 1 1 1 − 10−20 0 1 0 1 − 10−20

und unter Berechnung der zugehörigen Zeilensummennormen der Matrizen kL−11 Ak∞ = |1−1020 | ≈ 1020 , 1+|1−10−20 | 1+|1−1020 | −1 ˜ ˆ −1 ˜ −1 ≈ 1020 , k Lˆ −1 k(L−1 1 Ak∞ = 2 und k(L 1 A) k∞ = |1−10−20 | ≈ 2 zu 1 A) k∞ = |10−20 −1| 40 −1 −1 κ∞ ((L1−1A)−1 ) = k(L−1 1 A) k∞ kL1 Ak∞ ≈ 10 , ˜ −1 ) = k(Lˆ −1 A) ˜ −1 k∞ kLˆ −1Ak ˜ ∞ ≈ 4. κ∞ ((Lˆ1−1 A) 1 1

Man erkennt anhand der Konditionszahlen leicht, dass ohne Spalten-Pivot-Suche sowohl die Umformung als auch das Lösen des umgeformten LGS L−1 (die Multiplikation) mit der Matrix L−1 1 A wesentlich 1 schlechter konditioniert ist, als die Vorgehensweise beim Gaußalgorithmus mit Spalten-Pivot-Suche.

Aufgabe 4.10 [Lineare Iterationsverfahren für LGSe, vgl. Aufgabe 3.10] Zur näherungsweisen Lösung von Ax = b und für die Matrix/den Vektor 

1 0.5 1 A = 0.5 1 1 , −2 2 1



4 b = 4 . 1

(a) untersuche man die Konvergenz des Jacobi- und Vorwärts-Gauß-Seidel-Verfahrens zur Lösung von Gleichungen Ax = ˜b, b˜ ∈ R3 , für beliebige Startvektoren.

(b) führe man jetzt die Konvergenzanalyse noch für das rGS-Verfahren und das sGS-Verfahren durch. Welche der vier genannten Verfahren konvergieren? (c) Welches der Verfahren ist für diese Matrix A im Hinblick auf die Fehlerentwicklung (vgl. Skript, Charakterisierung d. Konvergenz) am besten geeignet? Welches im Hinblick auf die Anzahl der Rechenoperationen, die für einen Schritt des Verfahrens notwendig sind? Welches insgesamt? Lösung. Vorüberlegung zu den Konvergenzuntersuchungen: Die Matrix A ist nicht symmetrisch, also lassen sich die hinreichenden Kriterien, die auf symmetrisch positiver Definitheit von A basieren, nicht verwenden. Weiter ist die Matrix weder Zeilen- noch Spaltendiagonaldominant. Die entsprechenden Kriterien lassen sich also auch nicht verwenden. Das bedeutet auch, dass sich für das Jacobi-Verfahren das hinreichende Kriterium mit k · k∞ nicht verwenden lässt. Die Verfahrensmatrix M ist jeweils M = I − NA = −N(A − N−1 ) (a) MJac

     0 0.5 1 0 0.5 1 100 = − 0 1 0 0.5 0 1 = −0.5 0 1 −2 2 0 001 −2 2 0 {z } | {z } | =D−1

=(L+R)

Es ist kMJack1 = 2.5 > 1, so dass wir auch dieses Kriterium nicht verwenden können. Als nächstes bestimmen wir den Spektralradius.  mit p= unendlich nicht    1 geprüft, da dass nur kleiner  x + 0 0.5  eins ist, wenn strikt χMJac (x) = det(xI − MJac) = det(xI + (−MJac )) =  0.5 x + 0 1  zeilendiagonaldominant  −2 2 x+0  1 1 ! χMJac (x) = x3 + (−1) + 1 − ( x) − 2x + 2x = x3 − x = 0. 4 4

Also x = 0 oder x2 − 14 = 0, d. h. die EWe sind − 12 , 0 und 21 . Also ist ρ(MJac) = max(| − 12 |, |0|, | 21 |) < 1 und somit konvergiert das Jacobi-Verfahren für beliebige Startvektoren. vGS: M = I − NA = −N(A − N−1 )

MvGS

−1  1 00 0 = − 0.5 1 0  0 −2 2 1 0 | {z }| 

=(D+L)−1

   0 0.5 1 0.5 1 0 1 = −0 −0.25 0.5 0 1.5 1 0 0 {z } =R

Weder ist kMvGS k1 < 1, noch ist kMvGSk∞ < 1. Ein EW ist offensichtlich Null (Blockstruktur der Matrix: 1×1-Block oben links, die 0). Für die anderen beiden EWe:

 x − 0.25 0.5   χRestblock (x) = det(xI − Restblock) = det(xI + (−Restblock)) =    1.5 x + 1

3 ! χRestblock (x) = x2 + x − 1 = 0 4 p p Die anderen beiden EWe sind − 38 ± 1 + 9/64 und ρ(M) = |− 38 − 1 + 9/64| > 1, was gleichbedeutend damit ist, dass das vGS-Verfahren nicht für beliebige Startvektoren konvergiert. Bemerkung: Da (1, 0, 0)T EV zum EW 0 ist, erhielte man ab dem 1 Schritt immer die exakte Lösung und das Verfahren kovergierte, wenn die Startnährung so gewählt wäre, dass der Startfehler ein Vielfaches des ersten Einheitsvektors wäre, d. h. wenn also „zufällig“ nur die erste Komponente des Startvektors falsch wäre. (b) rGS-Verfahren: M = I − NA = −N(A − N−1 )

MrGS



1  =− 0 0 |

  −1  0.75 −1 0 0 00 0.5 1 1 1  0.5 0 0 = − 2.5 −2 0  −2 2 0 −2 2 0 0 1 {z }| {z } =L

=(D+R)−1

Die Eigenwerte sind dieselben wie die der Matrix (1. und 3. Spalte tauschen und 1. und 3. Zeile tauschen)   0 2 −2 − 0 −2 2.5  0 −1 0.75

weswegen wir den EW 0 und die EWe der Restmatrix über

  x − 2 2.5    χRestblock (x) = det(xI − Restblock) = det(xI + (−Restblock)) =  −1 x + 0.75

bekommen.

25 ! 5 5 χRestblock (x) = x2 − x + 1 = (x − )2 + 1 − =0 4 8 | {z64} >0

Man könnte an dieser Stelle die beiden (komplexwertigen) Eigenwerte berechnen und würde |λ1 | = |λ2 | = 1 erhalten. Somit ist ρ(MrGS) = 1, was gleichbedeutend damit ist, dass das rGS-Verfahren nicht für beliebige Startvektoren konvergiert. Alternativ kann man den Koeffizienten des konstanten Terms des charakteristischen Polynoms betrachten: 5 χRestblock (x) = x2 − x + 1 = (x − λ1 )(x − λ2 ) = x2 − λ1 x − λ2 x + λ1 λ2 4 !

Man erhält wegen λ1 λ2 = 1, dass mindestens ein Eigenwert vom Betrag größer oder gleich 1 ist, d.h. ρ(MrGS) > 1 und und somit die obige Aussage, dass das rGS-Verfahren nicht für beliebige Startvektoren konvergiert. Dies lässt sich analog auch für Polynome höheren Grades ausnutzen. sGS-Verfahren: MsGS = MrGSMvGS

MsGS

    0.75 −1 0 0 0.5 1 0 0.625 0.25 =  2.5 −2 0  0 −0.25 0.5  = 0 1.75 1.5  0 1.5 1 −2 2 0 0 −1.5 −1 

Also ist ein EW 0, die anderen berechnen sich aus

Koeffizienten-Vgl.

1 3 1 9 ! 3 χRestblock (x) = x2 − x + = (x − )2 + − =0 64 4 2 8 2 | {z } >0

q

1 . Alternativ kann man wie folgt Man kann die EWe direkt berechnen und erhält |λ1 | = |λ2 | = 2 argumentieren: Die (komplexen) Eigenwerte einer reellwertigen Matrix treten immer in konjugiert komplexen Paaren auf. Folglich giltqλ1 = ¯λ2 und somit λ1 λ2 = λ1λ¯1 = |λ1 |2 . Weiterhin ist (s.o.) λ1 λ2 = 12 .

Zusammen folgt |λ1 | = |λ2 | =

1 . 2

Insgesamt erhält man ρ(MsGS) = √1 2 , was gleichbedeutend damit ist, dass das sGS-Verfahren für beliebige Startvektoren konvergiert. Von den vier Verfahren konvergieren also nur das Jacobi- und das symmetrische Gauß-Seidel-Verfahren.

(c) Im Hinblick auf die Charakterisierung der Konvergenz ist das Jacobi-Verfahren zu bevorzugen wegen ρ(MJac) = 21 < √1 2 = ρ(MsGS). Für das Jacobi-Verfahren ist zu erwarten, dass sich langfristig der Fehler etwa wie ( 12 )k verhält, also dass sich der Fehler bei jeder Iteration etwa halbiert. Für das sGSVerfahren ist zu erwarten, dass sich langfristig der Fehler etwa wie ( 1√2 )k verhält, also dass sich langfristig der Fehler nach jeder zweiten Iteration etwa halbiert. Auch hinsichtlich der Rechenoperationen ist das Jacobi-Verfahren zu bevorzugen: eine Iteration vom vGSbzw. rGS-Verfahren besteht jeweils aus genauso vielen flops wie eine Iteration des Jacobi-Verfahrens (bei gleicher rechter Seite und der gleichen Iterierten). Der Rechenaufwand einer Iteration ist also etwa doppelt so groß. Als Fazit lässt sich also sagen, dass zu erwarten ist, dass (nach einigen wenigen Iterationen) das symmetrische Gauß-Seidel-Verfahren etwa viermal soviel Rechnenaufwand verursacht wie das Jacobi-Verfahren, um die gleiche Fehlerreduktion zu erreichen. Aufgabe 4.11 [Konvergenz linearer Iterationsverfahren] In dieser Aufgabe soll die Konvergenz der linearen Iterationsverfahren mit folgenden Fehlerfortpflanzungsmatrizen untersucht werden.       1 0 0 −2/3 0 −1/4 0 0 0372  0 1/2 1/4 0  0 7 2 3  −1/4 0 −1/4 0       M1 =   0 −1/4 0 −1/4  , M2 = 0 2 5 5  , M3 =  0 1/4 1/2 0  . 2/3 0 0 −1/3 0 0 −1/4 0 0165

Welche der Verfahren konvergieren für beliebige Startvektoren/rechte Seiten und welche nicht? Lösung. M1 : Hier sieht man, dass bspw. für die k · k1 -Norm gilt:

1 1 + 1,

5 > 1 + 1,

3>1+1

⇒ Jacobi-Verfahren und Gauß-Seidel-Verfahren konvergieren für jeden beliebigen Startvektor.   −1   0 −1 1 300   −1 0 −1 MJac = −D−1 A (LA + RA ) = − 0 5 0 1 −1 0 003 1     1 0 −1 1 00 0 3 −31 3 = −  0 51 0  −1 0 −1 =  15 0 15  1 −1 0 0 0 31 − 13 13 0

(b) Jacobi-Verfahren:

DA x(1) = b − (LA + RA )x(0) ⇒

3 0 0 050 0 03

x(1) =



6 −8 8



−

 −1  −2 −1

.

 1 1 7 6 + 1 · 2 + (−1) · 1 = · 7 = 3 3 3  1 6 (1) −8 +1·1 +1·1 =− x2 = 5 5  1 (1) 8 −1·1+1·2 =3 x3 = 3  3 0 0  7  (DA + LA )x(1) = b − RA x(0) ⇒ −1 5 0 x(1) = −7 .

(1) x1 =

Gauß-Seidel-Verfahren: (1) x1 =

7 3

1 −1 3

8

  7 14 1 7 1 7− =− = − ((−1) · + (−1) · 1 + 8) = − 5 3 15 3 5       14 1 14 71 7 7 1 (1) (+1) · + (−1) · − −8 =− x3 = − + −8 = 3 3 15 3 15 3 45

(1) x2

(c) Falls L := kMJac k∞ < 1, so gilt: kx(k) − x∗ k∞ 6

Lk kx(1) − x(0) k∞ , 1−L

wobei x∗ = A−1 b.

Man berechnet hier L = max

2

3

, 52 ,

2 3



=

2 , 3

kx(1) − x(0) k∞ = max

4 3

 16 , 2 + 56 , 2 = 5

und erhält somit: Lk 16 ! 6 0.0001 = 10−4 · 1−L 5 5(1 − L) 5 Lk 6 = 48 · 104 16 · 104 5 k ln L 6 ln 48 · 104 ln 5 4 ≈ 28.3 k > 48·10 ln 32

⇐⇒ ⇐⇒ ⇐⇒ Für k > 29 mit k ∈ N gilt k > Genauigkeit von 0.0001 erreicht.

ln

5 48·104 ln 32

≈ 28.3. Das heißt nach spätestens 29 Schritten hat man eine

Aufgabe 4.14

[Eigenwertabschätzung nach Gerschgorin]

Finden Sie durch Betrachten von Gerschgorin-Zeilen-/Spaltenkreisen möglichst genaue Abschätzungen für die Eigenwerte der Matrix

A=



 1 − 12 1 1  3 − 10 10  . 2 6 57  5 1 1 0 − 10 5 10 3 2

0

 1  10 −1 2

Lösung. Bezeichnet K(x, R) den Kreis um x mit Radius R, so berechnen sich die Zeilenkreise Ki aus der Definition in der Vorlesung n X Ki := {z ∈ C| |z − aii| 6 ri} mit ri := |aij| j=1 j6=i

zu

3 23 3 ), K3 = K(6, ), K4 = K(10, ). 10 10 10 Beispielhafte Rechnung: Die 2. Zeile der Matrix enthält die Einträge K1 = K(0, 3), K2 = K(3,

a21 =

1 1 1 , a22 = 3, a23 = − , a24 = , 10 10 10

1 Somit ist K2 = K(a22 , r2 ) = K(3, r2 ) mit r2 = | 101 | + | − 10 | + | 101 | = 103 . Zusammenhängende Mengen sind K1 ∪ K2 , K3 sowie K4 . K1 ∪ K2 enthält somit genau 2 Eigenwerte, die anderen beiden Mengen jeweils genau einen.

3

1 2

4

Da A irreduzibel ist und sich nicht alle Ränder Zeilenkreise in mindestens einem Punkt schneiden kann kein Eigenwert auf dem Rand eines Kreises liegen. Für die Spaltenkreise ˜Ki ergi...