Kap. 7: Ausgleichsrechnung (kleinste Quadrate)

7.1Normalgleichungen

7.1.1 Wenn es keine exakte Lösung gibt

Stell dir vor, du misst im Labor vier Punkte und suchst die Gerade, die am besten durchpasst. Kein gerades Lineal trifft alle vier Punkte exakt, denn jede Messung hat ihren kleinen Fehler. Was heißt dann überhaupt beste Lösung? Genau diese Frage beantwortet die Ausgleichsrechnung.

Bis jetzt haben wir lineare Gleichungssysteme $A\mathbf{x} = \mathbf{c}$ gelöst, bei denen es höchstens so viele Gleichungen wie Unbekannte gab. In realen Anwendungen ist es oft umgekehrt: Man hat viel mehr Gleichungen als Unbekannte. Jede Messung liefert eine Gleichung, aber gesucht sind nur wenige Modellparameter. Ein solches System heißt überbestimmt: $A \in \mathbb{R}^{m \times n}$ mit $m > n$ (mehr Zeilen als Spalten).

Bei einem überbestimmten System gibt es in aller Regel kein $\mathbf{x}$ , das alle $m$ Gleichungen gleichzeitig erfüllt. Der Grund ist anschaulich: Wir haben mehr Bedingungen als Stellschrauben, also lassen sich nicht alle Bedingungen exakt einhalten. Statt nach einer exakten Lösung zu suchen, fragen wir: Welches $\mathbf{x}$ kommt allen Gleichungen so nahe wie möglich?

Um den Fehler messen zu können, setzen wir alles auf eine Seite. Wir definieren den Residuenvektor $\mathbf{r} = A\mathbf{x} - \mathbf{c}$ . Seine Einträge $r_1, r_2, \ldots, r_m$ heißen Residuen (von lateinisch residuum, der Rest). Jedes $r_i$ ist der Rest, der in Gleichung $i$ übrig bleibt, also der Betrag, um den diese Gleichung verfehlt wird. Wäre $A\mathbf{x} = \mathbf{c}$ exakt lösbar, so wäre $\mathbf{r} = \mathbf{0}$ . Bei einem überbestimmten System ist das fast nie der Fall, und unser Ziel wird, $\mathbf{r}$ insgesamt so klein wie möglich zu machen.

Überbestimmtes System

A\mathbf{x} = \mathbf{c}, \qquad A \in \mathbb{R}^{m \times n},\; \mathbf{c} \in \mathbb{R}^m,\; \mathbf{x} \in \mathbb{R}^n,\quad m > n

Mehr Gleichungen (m) als Unbekannte (n). Meist keine exakte Lösung.

Fehlergleichungen und Residuen

A\mathbf{x} - \mathbf{c} = \mathbf{r}, \qquad \mathbf{r} = \begin{pmatrix} r_1 \\ r_2 \\ \vdots \\ r_m \end{pmatrix}

rᵢ = Rest in Gleichung i. Exakte Lösung würde r = 0 bedeuten.

Notation Notation: A, x, c, r

A \in \mathbb{R}^{m \times n}

Koeffizientenmatrix (m Zeilen, n Spalten),

\mathbf{x} \in \mathbb{R}^n

gesuchter Vektor,

\mathbf{c} \in \mathbb{R}^m

rechte Seite (Messwerte),

\mathbf{r} \in \mathbb{R}^m

Residuenvektor.

Definition Überbestimmtes System

A\mathbf{x} = \mathbf{c}

mit

m > n

: mehr Gleichungen als Unbekannte. In der Regel ohne exakte Lösung; gesucht ist die beste Näherung.

Definition Residuum
Der Rest

r_i

in Gleichung

i

, gesammelt im Residuenvektor

\mathbf{r} = A\mathbf{x} - \mathbf{c}

. Misst, wie stark eine Gleichung verfehlt wird.

Querverweis Verweise
→ 1.2.3 Wann ist ein LGS exakt lösbar?

7.1.2 Die Normalgleichungen: kleinste Fehlerquadrate

Welches $\mathbf{x}$ macht den Gesamtfehler am kleinsten? Dafür brauchen wir zuerst ein einziges Maß für die Größe des ganzen Residuenvektors $\mathbf{r}$ , nicht für jedes $r_i$ einzeln. Wir nehmen die Länge von $\mathbf{r}$ , also seine euklidische Norm (die gewöhnliche Pfeillänge im Raum). Diese Länge wollen wir minimieren.

Anschaulich: $\|\mathbf{r}\|_2$ ist die Gesamtlänge des Fehlervektors. Sie wird genau dann klein, wenn alle einzelnen Reste $r_i$ klein sind. Schreibt man die Norm aus, ist sie die Wurzel aus der Summe der Fehlerquadrate. Daher der Name Methode der kleinsten Quadrate: Wir minimieren $r_1^2 + r_2^2 + \cdots + r_m^2$ .

Jetzt das zentrale Resultat. Statt das Minimierungsproblem direkt anzugehen, gibt es ein erstaunlich einfaches lineares Gleichungssystem, dessen Lösung genau das gesuchte beste $\mathbf{x}$ liefert. Es heißt die Normalgleichungen und entsteht, indem man $A\mathbf{x} = \mathbf{c}$ von links mit $A^{\mathsf{T}}$ (der Transponierten von $A$ ) multipliziert. Die Lösungen dieses Systems stimmen mit den Lösungen des Minimierungsproblems überein.

Warum funktioniert das? Die Projektion auf den Spaltenraum. Erinnere dich an die Spaltensicht: $A\mathbf{x}$ ist eine Linearkombination der Spalten von $A$ . Alles, was $A$ erreichen kann, liegt im Spaltenraum $\operatorname{im}(A)$ . Liegt $\mathbf{c}$ nicht in diesem Raum (der überbestimmte Fall), so ist der nächstgelegene erreichbare Punkt der Schatten (die senkrechte Projektion) von $\mathbf{c}$ auf den Spaltenraum. Der Residuenvektor $\mathbf{r} = A\mathbf{x} - \mathbf{c}$ steht dann senkrecht auf allem, was $A$ erzeugen kann. Genau diese Senkrecht-Bedingung schreibt sich als $A^{\mathsf{T}}\mathbf{r} = \mathbf{0}$ , und das ist umgestellt die Normalgleichung $A^{\mathsf{T}} A \mathbf{x} = A^{\mathsf{T}} \mathbf{c}$ .

Warum quadrieren wir, statt einfach die Beträge zu summieren? Zwei Gründe. Erstens ist das Quadrat überall glatt und differenzierbar, der Betrag hat an der Null einen Knick; das macht das Minimieren rechnerisch sauber und führt direkt auf ein lineares System. Zweitens zählen große Abweichungen durch das Quadrat stärker, ein Ausreißer fällt also deutlich ins Gewicht. Deshalb "kleinste Quadrate" und nicht "kleinste Beträge".

Ist der Rang von $A$ voll, also $\operatorname{rang}(A) = n$ , so hat das Minimierungsproblem eine eindeutige Lösung. Anschaulich heißt voller Rang: Die Spalten von $A$ sind linear unabhängig, die Projektion landet auf genau einem Punkt, und dazu gehört genau ein Koeffizientenvektor $\mathbf{x}$ .

2-Norm des Residuums (zu minimieren)

\|\mathbf{r}\|_2 = \|A\mathbf{x} - \mathbf{c}\|_2

Euklidische Länge des Fehlervektors. Klein ⇔ alle Reste klein.

Summe der Fehlerquadrate

\|\mathbf{r}\|_2 = \sqrt{r_1^2 + r_2^2 + \cdots + r_m^2} \;\longrightarrow\; \min

Wurzel aus der Summe der Quadrate aller m Residuen. Minimieren ⇔ kleinste Quadrate.

!!!

Normalgleichungen (Theorem)

A^{\mathsf{T}} A\, \mathbf{x} = A^{\mathsf{T}} \mathbf{c}

Lösungen dieses LGS = Lösungen von ‖Ax - c‖₂ = min. Bei Rang(A) = n eindeutig.

Formel Schlüsselformel

A^{\mathsf{T}} A\, \mathbf{x} = A^{\mathsf{T}} \mathbf{c}

Die Normalgleichungen. Multipliziere

A\mathbf{x} = \mathbf{c}

von links mit

A^{\mathsf{T}}

. Ihre Lösung minimiert die Summe der Fehlerquadrate.

Notation Notation: ‖·‖₂
Die euklidische Norm (2-Norm):

\|\mathbf{r}\|_2 = \sqrt{r_1^2 + \cdots + r_m^2}

, die gewöhnliche Pfeillänge von

\mathbf{r}

. Manche Texte schreiben kurz

\|\mathbf{r}\|

Merke Merke
Residuum ⟂ Spaltenraum. Der beste Fehler steht senkrecht auf allem, was

A

erreichen kann.

Querverweis Verweise
→ 4.3 Norm und Skalarprodukt
→ 2.3 Transponierte Aᵀ
→ Analysis 6.1 Kleinste Quadrate (als Integral)

7.1.3 Beispiel: Ausgleichspolynom durch vier Messpunkte

Jetzt rechnen wir es einmal komplett durch. Im Labor wurden vier Messpunkte aufgenommen: an den Stellen $x_i = -1, 0, 1, 2$ die Werte $y_i = 0, 1, 3, 4$ . Gesucht ist ein quadratisches Polynom $f(x) = a\,x^2 + b\,x + c$ , das die Summe der Fehlerquadrate in $y$ -Richtung minimiert. Wir suchen also die drei Koeffizienten $a, b, c$ , sodass die Kurve möglichst gut durch die vier Punkte läuft.

Der Fehler in $y$ -Richtung am Punkt $i$ ist $f(x_i) - y_i$ , also der vertikale Abstand zwischen Kurve und Messpunkt. Minimiert wird die Summe dieser quadrierten Abstände.

Zielgröße: Summe der Fehlerquadrate in y-Richtung

\sum_{i=1}^{4} \big[\, f(x_i) - y_i \,\big]^2 \;\longrightarrow\; \min

Vertikaler Abstand Kurve - Messpunkt, quadriert und über alle vier Punkte summiert.

Lösungsweg, Ausgleichspolynom durch vier Punkte

Schritt 1: Ansatzfunktionen festlegen

Das Polynom $f(x) = a\,x^2 + b\,x + c$ ist eine Linearkombination dreier fester Bausteine. Diese Bausteine heißen Ansatz- oder Basisfunktionen; ihre Gewichte sind die gesuchten Koeffizienten.

Die drei Basisfunktionen sind:

$\alpha(x) = x^2, \qquad \beta(x) = x, \qquad \gamma(x) = 1$
Schritt 2: Matrix A aufstellen

Jede Zeile von $A$ gehört zu einem Messpunkt und enthält die Ansatzfunktionen, an dieser Messstelle ausgewertet. So wird aus „Polynom durch Punkte" ein lineares System in $a, b, c$ .

Für $x_i = -1, 0, 1, 2$ ergeben die Zeilen $\big(\alpha(x_i)\;\beta(x_i)\;\gamma(x_i)\big) = \big(x_i^2\;x_i\;1\big)$ :

$A = \begin{pmatrix} \alpha(-1) & \beta(-1) & \gamma(-1) \\ \alpha(0) & \beta(0) & \gamma(0) \\ \alpha(1) & \beta(1) & \gamma(1) \\ \alpha(2) & \beta(2) & \gamma(2) \end{pmatrix} = \begin{pmatrix} 1 & -1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 4 & 2 & 1 \end{pmatrix}$
Schritt 3: Unbekannten- und Messvektor

Der gesuchte Koeffizientenvektor sammelt $a, b, c$ ; die rechte Seite sammelt die gemessenen $y$ -Werte. Damit steht das überbestimmte System $A\mathbf{x} = \mathbf{f}$ ( $4$ Gleichungen, $3$ Unbekannte).

Koeffizienten und Messwerte:

$\mathbf{x} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}, \qquad \mathbf{f} = \begin{pmatrix} 0 \\ 1 \\ 3 \\ 4 \end{pmatrix}$
Schritt 4: Normalgleichungen ansetzen

Wir wenden direkt das Resultat aus 7.1.2 an: von links mit $A^{\mathsf{T}}$ multiplizieren. Weil hier der Messvektor $\mathbf{f}$ heißt, steht auf der rechten Seite $A^{\mathsf{T}}\mathbf{f}$ statt $A^{\mathsf{T}}\mathbf{c}$ , die Rolle ist dieselbe.

Die Normalgleichungen lauten:

$A^{\mathsf{T}} A\, \mathbf{x} = A^{\mathsf{T}} \mathbf{f}$
Schritt 5: Mit Aᵀ ausschreiben

Wir setzen $A^{\mathsf{T}}$ (Zeilen werden Spalten) auf beiden Seiten ein, damit nur noch Zahlen multipliziert werden müssen.

$\begin{aligned} &\begin{pmatrix} 1 & 0 & 1 & 4 \\ -1 & 0 & 1 & 2 \\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & -1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 4 & 2 & 1 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \end{pmatrix} \\[4pt] &= \begin{pmatrix} 1 & 0 & 1 & 4 \\ -1 & 0 & 1 & 2 \\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 3 \\ 4 \end{pmatrix} \end{aligned}$
Schritt 6: Das 3×3-System ausmultiplizieren

$A^{\mathsf{T}} A$ ist die symmetrische $3 \times 3$ -Matrix, $A^{\mathsf{T}} \mathbf{f}$ die neue rechte Seite. Aus vier Gleichungen sind jetzt genau drei geworden.

Ausgerechnet:

$\begin{aligned} &\begin{pmatrix} 18 & 8 & 6 \\ 8 & 6 & 2 \\ 6 & 2 & 4 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \end{pmatrix} \\[4pt] &= \begin{pmatrix} 19 \\ 11 \\ 8 \end{pmatrix} \end{aligned}$
Schritt 7: 3×3-LGS lösen

Dieses kleine quadratische System löst man wie gewohnt mit dem Gaußverfahren.

Die Lösung ist:

$a = 0, \qquad b = \tfrac{7}{5}, \qquad c = \tfrac{13}{10}$
Schritt 8: Ausgleichspolynom hinschreiben

Koeffizienten in den Ansatz einsetzen. Weil $a = 0$ herauskam, fällt der quadratische Term weg, die beste „Parabel" ist hier eine Gerade.

Das Ausgleichspolynom lautet:

$f(x) = \tfrac{7}{5}\,x + \tfrac{13}{10}$
Schritt 9: Restlänge (Residuenlänge) ausrechnen

Wie gut passt die Gerade wirklich? Das misst die Länge des Residuenvektors $\mathbf{r}$ . Wir werten $f(x_i) - y_i$ an allen vier Messstellen aus und nehmen die euklidische Norm (vergleiche 7.1.2).

Mit $f(x) = \tfrac{7}{5}\,x + \tfrac{13}{10}$ und den Messstellen $x_i = -1, 0, 1, 2$ :

$\begin{aligned} \mathbf{r} &= \begin{pmatrix} f(-1) - 0 \\ f(0) - 1 \\ f(1) - 3 \\ f(2) - 4 \end{pmatrix} = \begin{pmatrix} -\tfrac{1}{10} \\ \tfrac{3}{10} \\ -\tfrac{3}{10} \\ \tfrac{1}{10} \end{pmatrix} \\[4pt] \|\mathbf{r}\|_2^2 &= \tfrac{1 + 9 + 9 + 1}{100} = \tfrac{1}{5} \\[4pt] \|\mathbf{r}\|_2 &= \sqrt{\tfrac{1}{5}} = \tfrac{\sqrt{5}}{5} \approx 0{,}447 \end{aligned}$

Notation Notation: drei Rollen von x
Achtung,

x

tritt hier in drei Bedeutungen auf:

\mathbf{x} = (a, b, c)^{\mathsf{T}}

der Koeffizientenvektor (fett),

x

das Argument des Polynoms

f(x)

(skalar), und

x_i

die Messstellen. Im Fließtext immer mitlesen, welche gemeint ist.

Notation Notation: f statt c
In diesem Beispiel heißt der Messvektor

\mathbf{f}

(weil die gemessene Funktion „f" ist). Er spielt dieselbe Rolle als rechte Seite wie das

\mathbf{c}

aus der Theorie.

Definition Ausgleichspolynom
Polynom

f(x) = a\,x^2 + b\,x + c

, dessen Koeffizienten die Summe der vertikalen Fehlerquadrate

\sum_i [f(x_i) - y_i]^2

minimieren.

Merke Merke
Matrix

A

aufstellen: jede Zeile ist ein Messpunkt, jede Spalte eine Ansatzfunktion, ausgewertet an diesem Punkt.

Prüfungstipp Manche Aufschriebe drucken die Summe als

\sum_{i=4}^{4}

. Das ist ein Druckfehler; gemeint ist

\sum_{i=1}^{4}

über alle vier Messpunkte.

7.2QR-Zerlegung

7.2.1 QR-Zerlegung: warum und das Kochrezept

Warum noch ein zweites Verfahren, wenn die Normalgleichungen doch schon funktionieren? Der Grund ist numerische Genauigkeit. Beim Aufstellen von $A^{\mathsf{T}} A$ werden Zahlen quadriert und aufsummiert. Das verschlechtert die Kondition der Matrix: Kleine Rundungsfehler in den Daten werden in der Lösung stark verstärkt. Für präzise Anwendungen (etwa am Computer mit endlicher Rechengenauigkeit) sind die Normalgleichungen deshalb oft zu ungenau. Die QR-Zerlegung umgeht $A^{\mathsf{T}} A$ komplett und ist numerisch stabil.

Die Idee steckt im folgenden Satz: Jede Matrix $A$ lässt sich als Produkt $A = QR$ schreiben. Dabei ist $Q$ eine orthogonale Matrix und $R$ eine Matrix in Treppenform, oben eine quadratische obere Dreiecksmatrix $R_0$ , darunter nur Nullen. Genauer: Zu $A \in \mathbb{R}^{m \times n}$ mit $n \le m$ existiert eine orthogonale Matrix $Q \in \mathbb{R}^{m \times m}$ , sodass $A = QR$ gilt.

Was heißt orthogonal, und warum hilft das? Eine quadratische Matrix $Q$ heißt orthogonal, wenn ihre Spalten paarweise senkrecht und auf Länge $1$ normiert sind. Die entscheidende Eigenschaft: Bei einer orthogonalen Matrix ist die Inverse gleich der Transponierten, $Q^{-1} = Q^{\mathsf{T}}$ . Außerdem ist eine orthogonale Abbildung längentreu: Multiplizieren mit $Q$ (oder $Q^{\mathsf{T}}$ ) ändert die Länge eines Vektors nicht, $\|Q^{\mathsf{T}}\mathbf{r}\|_2 = \|\mathbf{r}\|_2$ . Genau deshalb dürfen wir das Problem mit $Q^{\mathsf{T}}$ drehen, ohne den Fehler zu verfälschen. Als orthogonales $Q$ nutzt man in der Praxis oft Givens-Rotationsmatrizen (Drehmatrizen), weil sie numerisch besonders stabil sind. Ist $\operatorname{rang}(A) = n$ , so ist $R_0$ regulär (invertierbar).

Wann brauche ich das? Immer dann, wenn es auf Genauigkeit ankommt, also bei großen oder schlecht konditionierten Problemen und bei jeder seriösen numerischen Software. Für eine schnelle Handrechnung mit kleinen Zahlen tun es die Normalgleichungen auch; die QR-Zerlegung ist die robuste Variante.

Das eigentliche Verfahren ist ein festes Kochrezept aus vier Schritten. Es löst die Fehlergleichungen $A\mathbf{x} - \mathbf{c} = \mathbf{r}$ direkt, ohne $A^{\mathsf{T}} A$ je zu bilden.

!!!

QR-Zerlegung (Theorem)

A = QR, \qquad A \in \mathbb{R}^{m \times n},\; n \le m,\quad Q \in \mathbb{R}^{m \times m}\ \text{orthogonal}

Q orthogonal (Q⁻¹ = Qᵀ, längentreu), R in Treppenform.

Blockstruktur von R

R = \begin{pmatrix} R_0 \\ 0 \end{pmatrix}, \qquad R_0 \in \mathbb{R}^{n \times n}\ \text{obere Dreiecksmatrix}

Oben die quadratische obere Dreiecksmatrix R₀, darunter lauter Nullen.

Kochrezept der QR-Zerlegung (4 Schritte)

Schritt 1: A in Treppenform drehen

Wir multiplizieren $A$ von links mit $Q^{\mathsf{T}}$ . Das dreht das Koordinatensystem so, dass $A$ oben dreieckig wird und unten nur Nullen übrig bleiben.

Ergebnis ist die Treppenmatrix $R$ :

$R = Q^{\mathsf{T}} A$
Schritt 2: Rechte Seite mitdrehen

Dieselbe Drehung muss auch auf die rechte Seite $\mathbf{c}$ wirken, sonst beschreiben beide Seiten nicht mehr dasselbe System.

Der gedrehte Vektor heißt $\mathbf{d}$ :

$\mathbf{d} = Q^{\mathsf{T}} \mathbf{c}$
Schritt 3: Kleines Dreieckssystem lösen

Nur der obere $n \times n$ -Block zählt für die Lösung. Mit $\mathbf{d}_0$ als den oberen $n$ Zeilen von $\mathbf{d}$ löst man das Dreieckssystem durch Rückwärtseinsetzen.

Lösen nach $\mathbf{x}$ :

$R_0\, \mathbf{x} = \mathbf{d}_0 \qquad (\mathbf{d}_0 = \text{obere } n \text{ Zeilen von } \mathbf{d})$
Schritt 4: Minimalen Fehler gratis ablesen

Die unteren $m - n$ Zeilen von $\mathbf{d}$ lassen sich durch kein $\mathbf{x}$ wegmachen, sie sind der unvermeidbare Rest. Weil $Q^{\mathsf{T}}$ längentreu ist, ist ihre Länge genau die minimale Fehlerlänge.

Mit $\mathbf{d}_1$ als den unteren $m - n$ Zeilen von $\mathbf{d}$ :

$\|\mathbf{r}\|_2 = \|\mathbf{d}_1\|_2$

Notation Notation: Q orthogonal

Q

orthogonal heißt: Spalten paarweise senkrecht und auf Länge

1

. Folge:

Q^{-1} = Q^{\mathsf{T}}

und

Q

ist längentreu. Gerechnet wird mit

Q^{\mathsf{T}}

(

R = Q^{\mathsf{T}} A

\mathbf{d} = Q^{\mathsf{T}} \mathbf{c}

Notation Notation: R₀, d₀, d₁

R_0

obere

n \times n

-Dreiecksmatrix,

\mathbf{d}_0

obere

n

Zeilen von

\mathbf{d}

(fürs LGS),

\mathbf{d}_1

untere

m - n

Zeilen von

\mathbf{d}

(für den Fehler).

Formel Auf einen Blick: 4 Schritte

\begin{aligned} R &= Q^{\mathsf{T}} A \\ \mathbf{d} &= Q^{\mathsf{T}} \mathbf{c} \\ R_0 \mathbf{x} &= \mathbf{d}_0 \\ \|\mathbf{r}\|_2 &= \|\mathbf{d}_1\|_2 \end{aligned}

QR-Kochrezept kompakt.

\mathbf{d}_0

obere

n

\mathbf{d}_1

untere

m - n

Zeilen.

Merke Merke
QR vermeidet

A^{\mathsf{T}} A

und ist deshalb numerisch stabil. Bevorzugt für genaue Anwendungen.

Querverweis Verweise
→ 2.6 Orthogonale Matrizen und Givens-Rotation
→ 4.4 Gram-Schmidt (Orthogonalisieren)
→ 9.1 Singulärwertzerlegung (nächster Schritt)

7.2.2 Beispiel: Ausgleichsproblem mit Givens-Rotation

Jetzt das Kochrezept an einem konkreten Fall. Gegeben sind die drei Fehlergleichungen $x_1 + x_2 - 1 = r_1$ , $x_2 - 3 = r_2$ , $x_2 - 4 = r_3$ . Gesucht ist die Lösung des Ausgleichsproblems mit der QR-Zerlegung. Das Lehrreiche an diesem Beispiel: Die Rotationsmatrix $Q^{\mathsf{T}}$ ist noch nicht fertig gegeben, wir müssen ihren Drehwinkel $\varphi$ selbst bestimmen.

Zuerst bringen wir das Problem in die Form $A\mathbf{x} - \mathbf{c} = \mathbf{r}$ , lesen also $A$ und $\mathbf{c}$ aus den Gleichungen ab. Danach folgen die vier Schritte des Kochrezepts.

Lösungsweg, QR-Zerlegung mit selbst bestimmtem Winkel

Schritt 1: A und c ablesen

Die Koeffizienten der $x_1, x_2$ bilden die Spalten von $A$ ; die Zahlen auf der anderen Seite bilden $\mathbf{c}$ . Aus $x_1 + x_2 - 1 = r_1$ usw. folgt direkt:

$A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \\ 0 & 1 \end{pmatrix}, \qquad \mathbf{c} = \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix}$
Schritt 2: Givens-Rotation ansetzen

$A$ ist $3 \times 2$ , also wählt man $Q^{\mathsf{T}}$ als $3 \times 3$ -Givens-Rotation. Sie dreht nur in der unteren $(2,3)$ -Ebene, lässt die erste Zeile in Ruhe und soll den störenden Eintrag in der letzten Zeile beseitigen.

Ansatz mit noch unbekanntem Winkel $\varphi$ :

$Q^{\mathsf{T}} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos(\varphi) & \sin(\varphi) \\ 0 & -\sin(\varphi) & \cos(\varphi) \end{pmatrix}$
Schritt 3: Qᵀ A ausrechnen

Wir multiplizieren aus, um zu sehen, welcher Eintrag vom Winkel abhängt. Ziel ist $Q^{\mathsf{T}} A = R$ in Treppenform.

Es ergibt sich:

$Q^{\mathsf{T}} A = \begin{pmatrix} 1 & 1 \\ 0 & \cos(\varphi) + \sin(\varphi) \\ 0 & \cos(\varphi) - \sin(\varphi) \end{pmatrix}, \qquad R_0 = \begin{pmatrix} 1 & 1 \\ 0 & \cos(\varphi) + \sin(\varphi) \end{pmatrix}$
Schritt 4: Winkel φ aus der Nullbedingung

Damit $R$ wirklich Treppenform hat, muss die letzte Zeile verschwinden. Der Eintrag dort ist $\cos(\varphi) - \sin(\varphi)$ , also setzen wir ihn null. Das bestimmt den Winkel; nichts wird geraten.

Aus $\cos(\varphi) - \sin(\varphi) = 0$ folgt:

$\cos(\varphi) = \sin(\varphi) \;\Longrightarrow\; \varphi = \tfrac{\pi}{4}$
Schritt 5: R fertig einsetzen

Mit $\varphi = \pi/4$ ist $\cos(\varphi) + \sin(\varphi) = \sqrt{2}$ und die letzte Zeile wird null.

Die fertige Treppenmatrix:

$Q^{\mathsf{T}} A = \begin{pmatrix} 1 & 1 \\ 0 & \sqrt{2} \\ 0 & 0 \end{pmatrix}$
Schritt 6: rechte Seite drehen (d = Qᵀ c)

Dieselbe Rotation mit $\varphi = \pi/4$ (also $\cos(\varphi) = \sin(\varphi) = \tfrac{\sqrt{2}}{2}$ ) auf $\mathbf{c}$ anwenden.

Es ergibt sich:

$\begin{aligned} \mathbf{d} = Q^{\mathsf{T}} \mathbf{c} &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & \tfrac{\sqrt{2}}{2} & \tfrac{\sqrt{2}}{2} \\ 0 & -\tfrac{\sqrt{2}}{2} & \tfrac{\sqrt{2}}{2} \end{pmatrix} \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix} \\[4pt] &= \begin{pmatrix} 1 \\ \tfrac{7\sqrt{2}}{2} \\ \tfrac{\sqrt{2}}{2} \end{pmatrix} \end{aligned}$
Schritt 7: Dreieckssystem R₀ x = d₀ lösen

$\mathbf{d}_0$ sind die oberen zwei Zeilen von $\mathbf{d}$ . Das $2 \times 2$ -Dreieckssystem löst man durch Rückwärtseinsetzen (zuerst $x_2$ , dann $x_1$ ).

Das System und seine Lösung:

$\begin{aligned} &\begin{pmatrix} 1 & 1 \\ 0 & \sqrt{2} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ \tfrac{7\sqrt{2}}{2} \end{pmatrix} \\[4pt] &\Longrightarrow\; \mathbf{x} = \begin{pmatrix} -\tfrac{5}{2} \\ \tfrac{7}{2} \end{pmatrix} \end{aligned}$

Ist die Rotationsmatrix $Q$ bereits gegeben, wird es noch kürzer. Dann entfällt das Bestimmen des Winkels, und man rechnet $R = Q^{\mathsf{T}} A$ und $\mathbf{d} = Q^{\mathsf{T}} \mathbf{c}$ direkt aus. Der folgende Fall zeigt das.

Lösungsweg, QR mit bereits gegebenem Q

Schritt 1: A, c und Q

Aus den Fehlergleichungen $4x_1 + x_2 - 9 = r_1$ , $7x_1 + x_2 - 12 = r_2$ , $4x_1 + 4x_2 - 15 = r_3$ liest man $A$ und $\mathbf{c}$ ab; die orthogonale Matrix $Q$ ist hier gegeben.

Es ist:

$\begin{aligned} A &= \begin{pmatrix} 4 & 1 \\ 7 & 1 \\ 4 & 4 \end{pmatrix}, \quad \mathbf{c} = \begin{pmatrix} 9 \\ 12 \\ 15 \end{pmatrix}, \\[4pt] Q &= \tfrac{1}{9}\begin{pmatrix} 4 & -1 & 8 \\ 7 & -4 & -4 \\ 4 & 8 & -1 \end{pmatrix} \end{aligned}$
Schritt 2: R = Qᵀ A

Mit $Q^{\mathsf{T}}$ (Zeilen und Spalten von $Q$ vertauscht) von links multiplizieren. Die letzte Zeile wird null, $R$ ist also in Treppenform.

Ergebnis:

$\begin{aligned} R = Q^{\mathsf{T}} A &= \tfrac{1}{9}\begin{pmatrix} 4 & 7 & 4 \\ -1 & -4 & 8 \\ 8 & -4 & -1 \end{pmatrix}\begin{pmatrix} 4 & 1 \\ 7 & 1 \\ 4 & 4 \end{pmatrix} \\[4pt] &= \begin{pmatrix} 9 & 3 \\ 0 & 3 \\ 0 & 0 \end{pmatrix} \end{aligned}$
Schritt 3: d = Qᵀ c

Dieselbe Multiplikation auf die rechte Seite anwenden.

Ergebnis:

$\begin{aligned} \mathbf{d} = Q^{\mathsf{T}} \mathbf{c} &= \tfrac{1}{9}\begin{pmatrix} 4 & 7 & 4 \\ -1 & -4 & 8 \\ 8 & -4 & -1 \end{pmatrix}\begin{pmatrix} 9 \\ 12 \\ 15 \end{pmatrix} \\[4pt] &= \begin{pmatrix} 20 \\ 7 \\ 1 \end{pmatrix} \end{aligned}$
Schritt 4: obere Blöcke und Lösung

$R_0$ und $\mathbf{d}_0$ sind die oberen zwei Zeilen. Das $2 \times 2$ -Dreieckssystem $R_0 \mathbf{x} = \mathbf{d}_0$ durch Rückwärtseinsetzen lösen.

Mit $R_0 = \begin{pmatrix} 9 & 3 \\ 0 & 3 \end{pmatrix}$ und $\mathbf{d}_0 = \begin{pmatrix} 20 \\ 7 \end{pmatrix}$ :

$R_0\, \mathbf{x} = \mathbf{d}_0 \;\Longrightarrow\; \mathbf{x} = \begin{pmatrix} \tfrac{13}{9} \\ \tfrac{7}{3} \end{pmatrix}$

Merke: eindeutig oder ganze Lösungsschar?

Nicht jedes Ausgleichsproblem hat eine eindeutige Lösung. Betrachte den Fall mit $A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ , $\mathbf{c} = (1, 2, 1)^{\mathsf{T}}$ und einer gegebenen orthogonalen $Q$ . Hier liefert das Kochrezept $R_0 = R = \begin{pmatrix} -\sqrt{2} & -\tfrac{3\sqrt{2}}{2} & -\sqrt{2} \\ 0 & -\tfrac{\sqrt{6}}{2} & 0 \\ 0 & 0 & 0 \end{pmatrix}$ und $\mathbf{d}_0 = \big(-\tfrac{3\sqrt{2}}{2},\, -\tfrac{\sqrt{6}}{2},\, 0\big)^{\mathsf{T}}$ .

Weil $R_0$ eine Nullzeile hat, ist $\operatorname{rang}(A) < n$ , und das System $R_0 \mathbf{x} = \mathbf{d}_0$ hat unendlich viele Lösungen, eine ganze einparametrige Lösungsschar $\mathbf{x} = (-\tfrac{3}{2}, 1, 0)^{\mathsf{T}} + t\,(-1, 0, 1)^{\mathsf{T}}$ mit $t \in \mathbb{R}$ .

Vergleiche das mit den beiden Beispielen oben (eindeutige Lösung): Ob das Ausgleichsproblem eindeutig lösbar ist, hängt allein am Rang von $A$ , genau wie schon bei den Normalgleichungen (voller Rang $\Rightarrow$ eindeutig).

Notation Notation: φ (Drehwinkel)

\varphi

ist der Drehwinkel der Givens-Rotation. Er wird so gewählt, dass der zu eliminierende Matrixeintrag verschwindet.

Definition Givens-Rotationsmatrix
Orthogonale Drehmatrix, die nur in einer Koordinatenebene dreht. Mit ihr lässt sich gezielt ein einzelner Matrixeintrag auf null bringen. Numerisch stabil.

Merke Merke
Letzte Zeile von

R

null setzen

\Rightarrow

Gleichung für den Winkel

\varphi

. Hier

\cos(\varphi) = \sin(\varphi)

, also

\varphi = \tfrac{\pi}{4}

Prüfungstipp

\mathbf{d}_0

= obere

n

Zeilen von

\mathbf{d}

(fürs LGS). Der Rest

\mathbf{d}_1

ist der Fehler, nicht Teil der Gleichung.

Querverweis Verweise
→ 7.1.2 Normalgleichungen (Vergleich)
→ 2.6 Orthogonale Matrizen

Aufgaben mit Musterlösungen

Aufgaben zu diesem Kapitel folgen.

Die Aufgaben für dieses Kapitel werden in einer zukünftigen Version ergänzt.

MerkeErst selbst rechnen, dann Lösung prüfen!