Numerik I Wintersemester 97/98 Dr. Walter Oevel 25. 11 1997

Ü b u n g s b l a t t 6

Aufgabe 18: (Monotone Konvergenz des Newton-Verfahrens bei Polynomen) Es sei p(x) = x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0} ein reelles Polynom mindestens 2. Grades mit reellen Nullstellen x_{1} ≥ x_{2} ≥ … ≥ x_{N} und komplexen (eventuell übereinstimmenden) Nullstellenpaaren ξ_{1}, ξ̄_{1}, .., ξ_{M}, ξ̄_{M} . Es sei x_{1} ≥ max{Re(ξ_{1}), .., Re(ξ_{M})} (mit Re(.) =Realteil). Zeige, daß für jeden Startpunkt x^{(0)} > x_{1} die Newton-Iteration x^{(i+1)} = x^{(i)} − p(x^{(i)})/p′(x^{(i)}) monoton fallend gegen x_{1} konvergiert. (3)

Anleitung: Mit p(x) = (x − x_{1}) ⋯ (x − x_{N})( (x − ξ_{1})(x − ξ̄_{1}) ) ⋯ ( (x − ξ_{M})(x − ξ̄_{M}) ) folgt

\frac{p′(x)}{p(x)} = \frac{1}{x − x_{1}} + ⋯ + \frac{1}{x − x_{N}} + \frac{2(x − Re(ξ_{1}))}{(x − ξ_{1})(x − ξ̄_{1})} + ⋯ + \frac{2(x − Re(ξ_{M}))}{(x − ξ_{M})(x − ξ̄_{M})} .

Hiermit läßt sich leicht zeigen, daß die x^{(i)} monoton fallen und x_{1} nicht unterschreiten können.

Aufgabe 19: (Implementierungsaufgabe: das Newton-Maehly-Verfahren, 12 Punkte) Implementiere das Maehly-Verfahren zur automatischen Berechnung sämtlicher Nullstellen eines reellen Polynoms p(x) = a_{0}x^{n} + ⋯ + a_{n−1}x + a_{n} ohne komplexen Nullstellen. Eingabedaten: die Koeffizienten a_{0}, …, a_{n}, Ausgabedaten: alle Nullstellen x_{1} ≥ x_{2} ≥ … ≥ x_{n}. Intern sollen Funktionsauswertungen von p(x) und p′(x) über das Horner-Schema erfolgen.

a) Teste das Programm mit den Polynomen

\begin{matrix}p_{1}(x) = (x − 7)(x − 6) ⋯ (x − 1) = x^{7} − 28 x^{6} + 322 x^{5} − 1960 x^{4} + 6769 x^{3} \\ −13132 x^{2} + 13068 x − 5040 , \end{matrix}

p_{2}(x) = (x−3)(x−2)^{3}(x−1)(x+1)^{2} = x^{7}−8x^{6}+20x^{5}−6x^{4}−41x^{3}+38x^{2}+20x−24 .

b) Bestimme alle Eigenwerte der Matrix A = ( \begin{matrix}4 & 0 & 0 & 1 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 1 & 0 & 0 & α \end{matrix} ) mit α =

M/7 777 777, M= deine (bzw. eine eurer) Matrikelnummer(n). Das charakteristische Polynom von A ist

p_{3}(λ) = det(A − λ 1I ) = λ^{4} − (α + 9)λ^{3} + (9α + 25)λ^{2} − (26α + 19)λ + (24α − 6).

Beachte, daß A als symmetrische Matrix nur reelle Eigenwerte hat, sodaß p_{3} keine komplexen Nullstellen haben kann.

c) Betrachte das (eigentlich nicht zulässige) Polynom p_{4}(x) = p_{2}(x) + 0.001. Das Programm müßte alle 5 reellen Wurzeln finden. Versuche, die Lage der beiden nicht gefundenen Nullstellen in der komplexen Ebene mit Hilfe der gefundenen reellen Wurzeln zu ermitteln. (Hinweis: für p(x) = x^{n} + a_{1} x^{n−1} + ⋯ + a_{n} = ∏(x − z_{i}) folgt ∑ z_{i} = −a_{1} und ∏ z_{i} = (−1)^{n}a_{n}.)

Die Bearbeitung von Aufgabe 19 ist getrennt bis Mittwoch, 17. Dez., abzugeben (Quelltext des Programms (hinreichend gut dokumentiert!) und Rechenergebnisse). Zur Erzwingung eines “copyright-Prinzips” zwischen den bearbeitenden Kleingruppen G_{i} wird nach folgendem Algorithmus bewertet: sollten wir den Eindruck gewinnen, daß verschiedene Gruppen G_{1}, G_{2}, … dieselben –nicht durch unabhängige Arbeit erzeugten– Resultate liefern, so wird die Mächtigkeit |G| der vereinigten Gruppe G = G_{1} ∪ G_{2} ∪ … betrachtet. Jedem Element in G wird dann die mit min{3, |G|}/|G| multiplizierte Punktzahl zugeschrieben, die die abgelieferte Lösung erreicht.

Aufgabe 20: (Zur Blockzerlegung von Matrizen)

a) Es seien a bzw. b invertierbare Matrizen der Dimension n_{1} × n_{1} bzw. n_{2} × n_{2}. Stelle die Inverse der aus diesen Blöcken aufgebauten (n_{1} +n_{2})×(n_{1} +n_{2})-Matrix

( \begin{matrix}a & O \\ c & b \end{matrix} ) mittels a^{−1} und b^{−1} dar (O ist ein Block aus trivialen Einträgen). (2)

b) Zeige, daß die Inverse einer unteren Dreiecksmatrix wieder eine untere Dreiecksmatrix ist. Anleitung: Induktion nach der Dimension, a) liefert den Induktonsschritt. (1)

c) Leite aus a),b) einen Algorithmus zur Berechnung der Inversen einer unteren Dreiecksmatrix ab, formuliere ihn in Pseudo-Code. Wieviele Multiplikationen werden bei einer (n × n)-Matrix benötigt? (3)

Aufgabe 21: (Strassens Matrixmultiplikation) Betrachte den Strassen-Algorithmus zur Multiplikation zweier 2^{m} × 2^{m}-Matrizen. Zeige, daß 7^{m} skalare Multiplikation und 6×(7^{m} −4^{m}) skalare Additionen auszuführen sind. Anleitung: aus der Zerlegung in Blöcke halber Dimension ergibt sich eine Rekursionsrelation zwischen M(m) und M(m − 1), wo M(m) die Anzahl der skalaren Multiplikationen ist. Analog für die Additionen. (2)

Abgabe: Mittwoch, 10. 12. 97, in den Übungsgruppen/Büro D1.329