Technische Universität Berlin Wintersemester 07/08 Fakultät II – Institut für Mathematik PD Dr. M. Ehrhardt Dipl.–Ing. C. Schröder

9. Übungsblatt zur VL “Numerik für Informatiker” (Ausgleichsrechnung)

\underline{1. Aufgabe} (3 Punkte)

Sei

A = [\begin{matrix}1 & 1 \\ 0 & 10^{−10} \\ 0 & 0 \end{matrix}] , b_{1} = [\begin{matrix}1 \\ 10^{−10} \\ 0 \end{matrix}] , b_{2} = [\begin{matrix}0 \\ 1 \\ 1 \end{matrix}]  (1)

a) Gebe eine QR-Zerlegung von A an.

Berechne die Lösungen x_{1}, x_{2} der Ausgleichsprobleme ∥Ax_{i} − b_{i}∥ = min in 16-stelliger Arithmetik mittels

b) Normalengleichungen.

c) QR-Zerlegung.

\underline{2. Aufgabe} (5 Punkte)

Berechnen Sie die Ausgleichsgeraden zu den Wertepaaren

a) \begin{matrix}x_{i} & 1 & 2 & 3 & 5 \\ y_{i} & 4.1 & 5.9 & 8.1 & 11 \end{matrix}  b) \begin{matrix}x_{i} & 2 & 4 & 5 & 6 \\ y_{i} & 8.1 & 5.9 & 5.1 & 4.1 \end{matrix}  c) \begin{matrix}x_{i} & 2 & 4 & 5 & 6 \\ y_{i} & 1 & 9 & 11 & 14 \end{matrix} .

Lösen Sie die entstehenden linearen Ausgleichsprobleme mittels QR-Zerlegung. Hinweis: Bei c) kann man von b) profitieren.

\underline{3. Aufgabe} (5 Punkte)

Es soll die Funktion der Form f_{λ_{1},λ_{2},λ_{3}}(x) = λ_{1}x + λ_{2}\sqrt{x + 1} + λ_{3}(x − 5)^{2} bestimmt wer-

den, die die Wertepaare \begin{matrix}x_{i} & 1 & 2 & 3 & 5 & 5.5 & 6 & 6.5 & 7 & 8 \\ y_{i} & 16.5 & 11 & 8 & 7.5 & 8.5 & 10 & 12.5 & 15 & 22 \end{matrix} am besten appro-

ximiert im Sinne der Summe der kleinsten Fehlerquadrate. Bestimmen Sie dazu Matrix A und rechte Seite b des linearen Ausgleichsproblems. Berechne (nicht notwendigerweise per Hand, sondern z.B. mit Matlabs qr Befehl) eine QR-Zerlegung von [A|b] und gebe R an. Berechne aus R die optimalen Werte für λ_{1}, λ_{2}, λ_{3}.

\underline{4. Aufgabe} (5 Punkte)

Es soll die Funktion der Form f_{λ_{1},λ_{2}}(x) = e^{λ_{1}x+λ_{2}} bestimmt werden, die die Wertepaare

\begin{matrix}x_{i} & 0 & 1 & 2 & 3 & 4 \\ y_{i} & 3 & 1 & 0.5 & 0.2 & 0.05 \end{matrix} am besten approximiert im Sinne der Summe der kleinsten

Fehlerquadrate.

a) Schreiben Sie das Ausgleichsproblem als Quadratmittelproblem um. Geben Sie also eine Funktion F (λ) an, für die das Problem die Form ∥F (λ)∥_{2}^{2} = min annimmt.

b) Bestimmen Sie die Jacobi-Matrix DF (λ). c). Bestimmen Sie Matrix und rechte Seite des linearen Ausgleichsproblems das im ersten Schritt des Gauß-Newton-Verfahrens zum Startvektor λ^{(0)} = [ \begin{matrix}1 \\ −1.5 \end{matrix} ] gelöst wird. (Nach der eigentlichen Lösung ist nicht gefragt.)

d) Die Lösung des linearen Ausgleichsproblems in c) lautet [ \begin{matrix}1.99 \\ 1.892 \end{matrix} ]. Geben Sie die Iterationsvorschriften und die ersten Iterierten des Gauß-Newton-Verfahrens und des gedämpften Gauß-Newton-Verfahrens an.

\underline{5. Aufgabe} (2 Punkte)

Wahr oder falsch (ohne Begründung; Antwort richtig: 0.5 Punkte, falsch: −0.5 Punkte)

a) In exakter Arithmetik liefern Normalengleichungen und QR-Zerlegung immer dasselbe Ergebnis eine linearen Ausgleichsproblems.

b) In endlicher Arithmetik sollte man die QR-Zerlegung der Normalengleichungen vorziehen, da die Matrix A^{⊤}A wesentlich mehr Speicherplatz benötigt, als Q und R zusammen.

Außer den Größenunterschieden gibt es auch Unterschiede in der Genauigkeit. Sei n_{data} die Anzahl der korrekten Nachkommastellen von A und b. Sei n_{QR} und n_{A^{T} A} die Anzahl der korrekten Nachkommastellen der Lösung x, berechnet mittels QR-Zerlegung, bzw. Normalengleichung. Es gelten die Daumenregeln:

c) Die QR-Lösung ist doppelt so genau, wie die Normalengleichungslösung, aber hoechstens so genau, wie die Eingangsdaten n_{QR} = min(2n_{A^{T} A}, n_{data}).

d) Die QR-Lösung verliert halb soviele Stellen, wie die Normalengleichungslösung, n_{data} − n_{QR} = \frac{1}{2}(n_{data} − n_{A^{T} A}).

\underline{Praktische Aufgabe} (10 Punkte)

a) Modifizieren Sie die Routine qr inplace von Blatt 5 (entweder Ihre Lösung oder die

Musterlösung unter http://www.math.tu-berlin.de/~ehrhardt/NumInf/UE.html) so

dass auch rechteckige Matrizen A ∈ ℝ^{n×m} behandelt werden koennen. Sie können annehmen, daß die ersten min(m, n) Spalten von A linear unabhängig sind.

b) Schreiben Sie eine Routine linearLeastSquares, die für eine rechteckige Matrix A und eine rechte Seite b die Lösung des linearen Ausgleichsproblems ∥b − Ax∥_{2} = min berechnet. Die Routine sollte den dreieckigen Faktor R der QR-Zerlegung von [A|b] benutzen. (entweder a) oder Matlabs qr.

c) Implementieren Sie die gedämpfte Gauss-Newton-Methode für das Problem aus Aufgabe 4. Benutzen Sie Ihre Routine linearLeastSquares aus Aufgabe b) für die auftretenden linearen Ausgleichsprobleme.

Abgabe - in der Vorlesung am 21. Dezember oder

- vorher im Briefkasten zwischen den Räumen MA470, MA471

Besprechung im Tutorium am 7. Januar