Mathe II für Informatiker Sommersemester 02 Walter Oevel 25. 4. 2002

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

Mit ∗ gekennzeichnete Aufgaben können zum Sammeln von Bonuspunkten verwendet werden. Lösungen sind per Web-Formular unter http://math-www.upb.de/~walter (⟶ Lehre SS 02 ⟶ Übungen) bis spätestens Do, 2.5.02, abzuliefern.

Aufgabe 7: (Schnelle komplexe Multiplikation) In einer Software-Umgebung stehe reelle Arithmetik zur Verfügung. Die Kosten der Addition/Subtraktion reeller Zahlen sei gegenüber den Kosten einer Multiplikation vernachlässigbar. Es soll in dieser Umgebung die Arithmetik für komplexe Zahlen implementiert werden, welche als Listen [x, y] von Real- und Imaginärteil dargestellt werden. Die Definition

[x_{1}, y_{1}] · [x_{2}, y_{2}] = [x_{1} · x_{2} − y_{1} · y_{2}, x_{1} · y_{2} + y_{1} · x_{2}]

der komplexen Multiplikation (x_{1} + i · y_{1}) · (x_{2} + i · y_{2}) benötigt vier reelle Multiplikationen. Finde einen Weg, das komplexe Produkt über geeignete Zwischenergebnisse mit nur 3 reellen Multiplikationen zu berechnen. Hinweis: Betrachte (x_{1} + y_{1}) · (x_{2} + y_{2}).

Aufgabe 8: (Faktorpolynome, Horner–Schema) Betrachte das Polynom p(x) = x^{n} − 1. Für jedes n ∈ ℕ läßt sich der Linearfaktor x − 1 abspalten (warum?). Bestimme für beliebiges n die explizite Form des Faktorpolynoms p(x)/(x − 1). Hinweis: Durchlaufe das Horner–Schema.

Aufgabe 9: (MuPAD) Lies die MuPAD–Hilfeseiten zu factor und expand. Faktorisiere die Polynome x^{n} − 1 für n = 2, 3, …, 10. Benutze expand, um die in Aufgabe 8 gefragte Form des Faktorpolynoms p(x)/(x − 1) zu verifizieren.

Aufgabe 10*: (Polynomwurzeln. 1 Bonuspunkt) Seien M_{1}, …, M_{7} die Ziffern der Matrikelnummer (von links nach rechts). Das Polynom p(x) = x^{4} − 2 · M_{5} · x^{3} + (2 − M_{7}^{2}) · x^{2} − 4 · M_{5} · x − 2 · M_{7}^{2} hat stets die komplexe Nullstelle \sqrt{2} · i. Bestimme alle Nullstellen! Hinweis: Satz 1.19 liefert eine zweite Nullstelle. Nach Abspalten zweier Linearfaktoren sind nur noch die Nullstellen eines quadratischen Faktorpolynoms zu suchen. Relevante MuPAD-Funktionen: factor, solve.

Aufgabe 11: (Zum Horner-Schema) Das Horner-Schema ist für die Auswertung ”dicht besetzter“ Polynome (fast alle Koeffizienten sind ungleich 0) ein guter und schneller Algorithmus. Diskutiere die Situation für ”dünn besetzte“ Polynome (fast alle Koeffizienten sind 0) anhand des Beispiels x^{n} − 1.

Aufgabe 12: (Vietascher Wurzelsatz)

a) Seien x_{1}, …, x_{k} die unterschiedlichen Wurzeln des Polynoms p(x) = a_{n} ·x^{n} +⋯+a_{1} ·x+a_{0} mit den Vielfachheiten n_{1}, …, n_{k}, wobei n = n_{1} + ⋯ + n_{k} und a_{n} ≠ 0 gelte. Zeige:

x_{1}^{n_{1}} · x_{2}^{n_{2}} · . . . · x_{k}^{n_{k}} = (−1)^{n} · \frac{a_{0}}{a_{n}} .

b) Betrachte p(x) = 3 · x^{3} − 51 · x^{2} − 3 x + 51. Die Werte x_{1,2} = ±1 sind Nullstellen. Finde die dritte Wurzel ohne Polynomdivision.

Aufgabe 13: (Schranken für Polynomwurzeln. Für Ehrgeizige, anspruchsvoll!) Sei z eine (eventuell komplexe) Wurzel des Polynoms p(x) = a_{n} · x^{n} + ⋯ + a_{1} · x + a_{0}, a_{n} ≠ 0. Zeige

|z| ≤ max \{|\frac{a_{0}}{a_{n}} | , 1 + |\frac{a_{1}}{a_{n}} | , 1 + |\frac{a_{2}}{a_{n}} | , …, 1 + |\frac{a_{n−1}}{a_{n}} |\} .

Anleitung: Zeige, dass

|a_{n} · z^{n}| >^{(∗)} |a_{n−1}| · |z^{n−1}| + ⋯ + |a_{1}| · |z| + |a_{0}| ( ≥ |a_{n−1} · z^{n−1} + ⋯ + a_{1} · z + a_{0}|)

gilt, wenn |z| größer als die angegebene Schranke ist (damit kann z keine Nullstelle sein). Zeige (∗) per Induktion nach j:

|a_{n}| · |z^{j}| > |a_{j−1}| · |z^{j−1}| + ⋯ + |a_{1}| · |z| + |a_{0}| für alle j = 1, …, n.

Aufgabe 14*: (Matrixdiagonalisierung. 1 Bonuspunkt. Zum Knobeln. Rechenintensiv!) Seien M_{1}, …, M_{7} wie üblich die Ziffern der Matrikelnummer. Finde drei unterschiedliche 3×3 Matrizen, deren Quadrat die Matrix A mit den folgenden Einträgen ergibt:

A_{11} = 4 + (M_{2} − 1) · (M_{2} − 5) · (M_{2} + 3) · M_{6},
A_{12} = M_{6} · (1 − M_{2}) · (M_{2} − 5),
A_{13} = (M_{2} − 1) · (M_{2} − 5),
A_{21} = (M_{2} + 3) · (M_{2} + 2) · (M_{2} + 6) · (3 · M_{6} + M_{2} · M_{6} − 1),
A_{22} = 16 + M_{2} · (8 + M_{2}) − M_{6} · (M_{2} + 2) · (M_{2} + 3) · (M_{2} + 6),
A_{23} = (M_{2} + 2) · (M_{2} + 3) · (M_{2} + 6),
A_{31} = 7 · M_{6} · (M_{2} + 3) · (2 · M_{2} + 1) · (3 · M_{6} + M_{2} · M_{6} − 1),
A_{32} = 7 · M_{6} · (2 · M_{2} + 1) · (1 − 3 · M_{6} − M_{2} · M_{6}),
A_{33} = (M_{2} − 3)^{2} + 7 · M_{6} · (M_{2} + 3) · (2 · M_{2} + 1).

Anleitung: Die Aufgabe ist leicht zu lösen, wäre A eine Diagonalmatrix. Also: diagonalisiere A. (Die Diagonalisierung ist rechenintensiv. Es bietet sich an, dies mit MuPAD mittels der Funktion linalg::eigenvectors zu tun.) Zur Kontrolle: A hat stets nur ganzzahlige Eigenwerte und ist diagonalisierbar. Löse die Aufgabe für die Diagonalmatrix der Eigenwerte von A. Wie lassen sich aus den ”Wurzeln“ der Diagonalmatrix die ”Wurzeln“ von A konstruieren? Relevante MuPAD-Funktionen: matrix, linalg::eigenvectors. Matrizen werden mittels * multipliziert. Eine Matrix T wird mittels 1/T oder T^(-1) invertiert.