Kurs:Numerik I/Lösung der Normalengleichung

Mehrdimensionale Taylorentwicklung

Für die mehrdimensionale Tailorentwicklung von einer quadratischen Funktion mit dem Vektor $x_{0}\in \mathbb {R} ^{k}$ als Entwicklungspunkt gilt:

$F(x)=F(x_{0})+\left\langle \nabla F(x_{0}),x-x_{0}\right\rangle +{\frac {1}{2}}\left\langle \operatorname {H} _{F}(x_{0})\cdot (x-x_{0}),x-x_{0}\right\rangle$

Dabei ist $\nabla F(x_{0})$ der Gradient von $F$ an der Stelle $x_{0}$ und $\operatorname {H} _{F}(x_{0})$ die Hesse-Matrix von $F$ an der Stelle $x_{0}$.

Ausgangsfunktion der Ausgleichsrechnung

Im Allgemeinen wurde aus der linearen Ausgleichsrechnung die folgende Gleichung hergeleitet

$F(x)=\underbrace {b^{T}b} _{=F(0_{V})}-{\underbrace {(2A^{T}b)} _{=\nabla F(0_{V})}}^{T}x+{\frac {1}{2}}(\underbrace {(2A^{T}A)} _{H_{F}(0_{V})}x)^{T}x$

Mehrdimensionale Taylorentwicklung

Diese wird nun als mehrdimensionale Taylorentwicklung einer quadratischen Funktion $F:\mathbb {R} ^{k}\to \mathbb {R}$ interpretiert.

$F(x)=\underbrace {\|b\|_{2}^{2}} _{=F(0_{V})}-\langle \underbrace {2A^{T}b} _{=\nabla F(0_{V})},x\rangle +{\frac {1}{2}}\langle \underbrace {(2A^{T}A)} _{H_{F}(0_{V})}x,x\rangle$

Rang der Matrix

Wir betrachten nun die obige quadratische Funktion, wobei wir $\operatorname {Rang} (A)=k$ voraussetzen. $F$ hat

• im Entwicklungspunkt $x_{0}:=0_{V}$ den Gradienten $\nabla F(0_{V})=-2A^{T}$,
• an der Stelle $x$ den Gradienten $\nabla F(x)=2A^{T}Ax-2A^{T}b,$ und
• die Hesse-Matrix $H_{F}(x)=2A^{T}A.$

Normalengleichung

Notwendige Bedingung, dass $x^{*}\in \mathbb {R} ^{k}$ Minimalpunkt von $F$ ist, ist die Bedingung $\nabla F(x^{*})=0$ bzw. äquivalent dazu, dass $x^{*}$ die sog. Normalgleichungen

$A^{T}Ax=A^{T}b\quad {\mbox{ (Normalengleichung) }}$

erfüllt. Nach dem Lemma zur Lösbarkeit der Normalengleichung ist dabei die (von $x$ unabhängige) Matrix $\nabla ^{2}F(x):=H_{F}(x)$ positiv definit, so dass die eindeutige Lösung $x^{*}$ der Normalgleichungen auch der einzige (globale) Minimalpunkt von $F$ ist.

Satz - Lösbarkeit der Normalengleichung

Sei $A\in \mathbb {R} ^{n\times k}$ mit $n\geq k$ und $\operatorname {Rang} (A)=k$. Dann besitzt das lineare Ausgleichsproblem

$\min _{x\in \mathbb {R} ^{k}}\|b-Ax\|_{2}$

eine eindeutige Lösung $x^{*}\in \mathbb {R} ^{k}$ und diese ist eindeutige Lösung des linearen Gleichungssystems

$A^{T}Ax=A^{T}b.$

Bemerkung - Symmetrie der Matrix

Die Matrix $A^{T}A\in \mathbb {R} ^{k\times k}$ ist mit $A\in \mathbb {R} ^{n\times k}$ und $n\geq k$ eine symmetrische Matrix, da die Kompomenten bestehen aus den Skalarprodukten der Spaltenvektor $a_{i}\in \mathbb {R} ^{n}$ von $A$ mit:

$A^{T}A={\big (}\langle a_{i},a_{j}\rangle {\big )}_{1\leq i,j\leq k}\in \mathbb {R} ^{k\times k}$

Die Symmetrie des Skalarprodukte $\langle x,y\rangle =\langle y,x\rangle$ für $x,y\in \mathbb {R} ^{n}$ liefert die Symmetrie der Matrix.

Bemerkung - Gleichungssystem mit invertierbarer Matrix

Die Invertierbarkeit von Matrizen bzgl. Matrixmultiplation betrachtet auf einem Matrizenraum von quadratischen betrachten bzgl. einer inneren Verknüpfung. $A\in \mathbb {R} ^{n\times k}$ und $n>k$ ist nicht quadratisch. Wenn der Rang von $A$ allerdings $k$, hat $A^{T}A\in \mathbb {R} ^{k\times k}$ auch den Rang $k$ und die Matrix $A^{T}A\in \mathbb {R} ^{k\times k}$ ist invertierbar. Mit der Normalengleichung, ${\widehat {A}}:=A^{T}A\in \mathbb {R} ^{k\times k}$ ${\widehat {b}}:=A^{T}b\in \mathbb {R} ^{k}$ gilt für die eindeutige Lösung $x\in \mathbb {R} ^{k}$ von ${\widehat {A}}x={\widehat {b}}$

$x={\widehat {A}}^{-1}{\widehat {b}}=(A^{T}A)^{-1}A^{T}b$

Beispiel

Wir betrachten dazu ein Beispiel der Ausgleichsrechnung.

Beispiel - Ausgleichsgerade 1

Wir betrachten den Fall der sog. Ausgleichsgeraden. Wenn die $y_{j}$ $(j=1,\ldots ,n)$ mit $n\geq 2$ ungefähr auf einer Geraden liegen, macht es Sinn, polynomiale Ansatzfunktionen bis zum Grad 1 zu verwenden. D.h. als Ansatzfunktionen wählt man

$v_{1}(t):=1,\quad v_{2}(t):=t$

mit $k=2$.

Beispiel - Ausgleichsgerade - 2

Somit erhält man approximierende Funktion $z$ über

$z(x,t):=x_{1}+x_{2}t,\quad t\in \mathbb {R}$

und die gesuchten optimalen Koeffizienten der Geradengleichung werden durch den Vektor $x:=(x_{1},x_{2})\in \mathbb {R} ^{2}$ definiert.

Beispiel - Daten zu Zeitpunkten - 3

Als Daten haben wir z.B. wieder Daten $y_{i}$ zum Zeitpunkt $t_{i}$ erhoben, für die nun die Ausgleichsgerade gesucht wird. Dazu definiert man:

$b:=(y_{1},y_{2},\ldots ,y_{n})^{T}\in \mathbb {R} ^{n},\quad d:=(t_{1},t_{2},\ldots ,t_{n})^{T}\in \mathbb {R} ^{n}$

und den Spaltenvektor $e$, dessen Komponenten nur aus 1 besteht mit

$e:=(1,1,\ldots ,1)^{T}\in \mathbb {R} ^{n}$

Beispiel - Definition der Matrix A - 4

Nun hat $A\in \mathbb {R} ^{n\times 2}$ in diesem Fall die Gestalt $A={\begin{pmatrix}e&d\end{pmatrix}}$. Da der erste Spaltenvektor $e$ nur als Komponenten die 1 besitzt und die Zeitpunkte in $d=(t_{1},\ldots ,t_{n})$ paarweise verschieden sind, hat die Matrix den Rang 2.

Beispiel - Berechnung der symmetrischen Matrix - 5

Weiter ist dann

$A^{T}A={\begin{pmatrix}e^{T}\\d^{T}\end{pmatrix}}{\begin{pmatrix}e&d\end{pmatrix}}={\begin{pmatrix}e^{T}e&e^{T}d\\e^{T}d&d^{T}d\end{pmatrix}},\quad A^{T}b={\begin{pmatrix}e^{T}b\\d^{T}b\end{pmatrix}}.$

Da der Rang der Matrix $A$ 2 ist, besitzt auch die symmetrische Matrix $A^{T}A\in \mathbb {R} ^{2\times 2}$ den Rang 2.

Beispiel - Inverse Matrix zur symmetrischen Matrix - 6

Für eine symmetrische invertierbare Matrix $B\in \mathbb {R} ^{2\times 2}$ kann man die Inverse explizit angeben:

$B^{-1}={\begin{pmatrix}b_{11}&b_{12}\\b_{12}&b_{22}\end{pmatrix}}^{-1}={\frac {1}{b_{11}b_{22}-b_{12}^{2}}}{\begin{pmatrix}b_{22}&-b_{12}\\-b_{12}&b_{11}\end{pmatrix}}.$

Beispiel - Lösung der Normalengleichung - 7

Somit lautet die Lösung der Normalgleichungen $A^{T}Ax=A^{T}b$ in diesem Fall

$x^{*}:=\left(A^{T}A\right)^{-1}A^{T}b={\frac {1}{(e^{T}e)(d^{T}d)-(e^{T}d)^{2}}}{\begin{pmatrix}d^{T}d&-e^{T}d\\-e^{T}d&e^{T}e\end{pmatrix}}{\begin{pmatrix}e^{T}b\\d^{T}b\end{pmatrix}}$

Beispiel - Berechnung der Lösung - 8

Durch algebraische Umformungen erhält man demzufolge

$x^{*}={\frac {1}{(e^{T}e)(d^{T}d)-(e^{T}d)^{2}}}{\begin{pmatrix}\left(d^{T}d\right)\left(e^{T}b\right)-\left(d^{T}b\right)\left(e^{T}d\right)\\(e^{T}e)(d^{T}b)-(e^{T}d)(e^{T}b)\end{pmatrix}}.$

Beispiel - Berechnung von Termen in der Lösung - 9

Dabei hat man

$e^{T}e=n,\quad e^{T}d=\sum _{j=1}^{n}t_{j},\quad e^{T}b=\sum _{j=1}^{n}y_{j},\quad d^{T}d=\sum _{j=1}^{n}t_{j}^{2},\quad d^{T}b=\sum _{j=1}^{n}t_{j}y_{j}.$

Beispiel - Einsetzung von Termen in die Lösung - 10

Durch Einsetzen erhält man:

$x^{*}={\frac {1}{n\cdot \left(\sum _{j=1}^{n}t_{j}^{2}\right)-\left(\sum _{j=1}^{n}t_{j}\right)^{2}}}{\begin{pmatrix}\left(\sum _{j=1}^{n}t_{j}^{2}\right)\left(\sum _{j=1}^{n}y_{j}\right)-\left(\sum _{j=1}^{n}t_{j}y_{j}\right)\left(\sum _{j=1}^{n}t_{j}\right)\\n\left(\sum _{j=1}^{n}t_{j}y_{j}\right)-\left(\sum _{j=1}^{n}t_{j}\right)\left(\sum _{j=1}^{n}y_{j}\right)\end{pmatrix}}.$

Beispiel - Berechnung der Ausgleichsgerade für konkrete Wertepaare - 11

Beispielsweise für die $n=8$ Wertepaare

${\begin{array}{|l||c|c|c|c|c|c|c|c|}\hline t_{j}&1&2&3&4&5&6&7&8\\\hline y_{j}&1.75&2.18&2.63&3.24&3.69&4.16&4.55&5.29\\\hline \end{array}}$

Beispiel - Berechnung von Termen in der Lösung - 12

Wendet man die obigen Überlegungen auf die Beispieldaten an, erhält man

$\sum _{j=1}^{8}t_{j}=36,\quad \sum _{j=1}^{8}y_{j}=27.49,\quad \sum _{j=1}^{8}t_{j}^{2}=204,\quad \sum _{j=1}^{8}t_{j}y_{j}=144.54.$

Beispiel - Berechnung von Termen in der Lösung - 13

Über Einsetzung in die Vektordefinition von $x^{*}$ ergibt sich somit

$x^{*}={\frac {1}{8\cdot 204-36^{2}}}{\begin{pmatrix}204\cdot 27.49-36\cdot 144.54\\8\cdot 144.54-36\cdot 27.49\end{pmatrix}}={\begin{pmatrix}1.203\ 929\\0.496\ 071\end{pmatrix}}.$

Die Ausgleichsgerade zu den gegebenen Daten lautet folglich

$z(x^{*},t):=1.203\ 929+0.496\ 071t,\quad t\in \mathbb {R} .$

Beispiel - Maximaler Fehler der Lösung - 14

Der maximale relative Fehler der $z(x^{*},t_{j})$ bezüglich der $y_{j}$ beträgt

$\max _{1\leq j\leq 8}{\frac {|y_{j}-z(x^{*},t_{j})|}{|z(x^{*},t_{j})|}}=0.016\ 243$

bzw. ungefähr 1.6%.

Normalengleichung für höhere k

Für $k>2$ könnte man die Normalgleichungen (4.10) mittels einer Cholesky-Zerlegung lösen. Diese selbst ist, wie man zeigen kann, numerisch stabil. Leider ist das Ausgleichproblem selbst aber häufig schlecht konditioniert.

Vandermonde-Matrix - Ansatzfunktionen

Man betrachte z. B. die Matrix $A$, die sog. Vandermonde-Matrix, die man für $n=k$ im Fall der Wahl der Monome (4.6) als Ansatzfunktionen erhält:

$A:={\begin{pmatrix}1&t_{1}&\ldots &t_{1}^{k-1}\\1&t_{2}&\ldots &t_{2}^{k-1}\\\vdots &\vdots &\ddots &\vdots \\1&t_{k}&\ldots &t_{k}^{k-1}\end{pmatrix}}.$

Einfluss auf die Konditionszahl

Für $t\in [0,1]$ unterscheiden sich die Funktionen $t^{r-1}$ und $t^{r}$ bereits für nicht allzu großes $r$ kaum, so dass die $r$-te und $(r+1)$-te Spalten in $A$ für solche $r$ nahezu linear abhängig sind. Die oft große Kondition von $A$ geht außerdem noch im Fall $n=k$ bei der Lösung der Normalgleichungen quadratisch ein, denn es gilt:

Lemma - Eigenwerte positiv definiter Matrizen

Sei $A\in \mathbb {R} ^{n\times n}$ eine positiv definite Matrix, dann sind alle Eigenwerte positiv.

Beweis

Sei $\lambda$ ein Eigenwert der Matrix $A\in \mathbb {R} ^{n\times n}$ und $x\in \mathbb {R} ^{n}$ ein beliebiger Eigenvektor. Dann gilt mit $x\not =0_{V}$ und der positiven Definitheit:

$0<\langle Ax,x\rangle =\langle \lambda \cdot x,x\rangle =\lambda \cdot \underbrace {\langle x,x\rangle } _{>0}$

Damit ist auch $\lambda >0$. q.e.d.

Bemerkung - Normalengleichung - Taylorentwicklung

Durch die Darstellung der Funktion $F$ in der mehrdimensionalen Taylorentwicklung ist $2\cdot A^{T}A$ die Hesse-Matrix. Die $k\times k$-Matrix $A^{T}A$ ist mit $\operatorname {Rang} (A)=k$ positiv definit, denn dann müssen alle Eigenwerte von 0 verschieden sein.

Bemerkung - positiv semidefinit

Die $k\times k$-Matrix $A^{T}A$ ist im Allgemeinen nur $\operatorname {Rang} (A)<k$ nur positiv semidefinit, denn es gilt für alle $x\in \mathbb {R} ^{k}\setminus \{0_{v}\}$:

$\langle A^{T}Ax,x\rangle =(A^{T}Ax)^{T}x=x^{T}A^{T}Ax=(Ax)^{T}Ax=\langle Ax,Ax\rangle \geq 0$

Lemma - Konditionszahl Normalengleichung

Für eine reguläre Matrix $A\in \mathbb {R} ^{k\times k}$ gilt für die Konditionszahl

$\operatorname {cond} _{2}(A^{T}A)=(\operatorname {cond} _{2}(A))^{2}.$

Dabei bezeichnet der Index 2 an der Konditionszahl, dass die Euklidische Norm bzw. $l_{2}$-Norm verwendet wurde.

Beweis

Nach dem Lemma über Eigenwerte positiv definiter Matrix $B\in \mathbb {R} ^{k\times k}$ gilt für die Eigenwerte $\lambda _{i}:=\lambda _{i}(B)>0$ $(i=1,\ldots ,k)$.

Beweis 1 - Eigenwert der inversen Matrix

Weiter hat wegen

$Bx^{i}=\lambda _{i}x^{i}\Leftrightarrow B^{-1}x^{i}={\frac {1}{\lambda _{i}}}x^{i}$

für Eigenvektoren $x^{i}$ zu ${\frac {1}{\lambda _{i}}}$ $(i=1,\ldots ,k)$ besitzt.

Beweis 2 - Berechnung der Konditionszahl

Es gilt folglich nach Satz zur Berechnung der Konditionszahl erhält man:

$\operatorname {cond} _{2}(B)=\|B\|_{2}\left\|B^{-1}\right\|_{2}={\frac {\lambda _{m}ax}{\lambda _{\min }}},$

$\operatorname {cond} (A)=\left(\max _{\|x\|=1}\|Ax\|\right)/\left(\min _{\|x\|=1}\|Ax\|\right).$

wobei $\lambda _{\max }=\max _{\|x\|=1}\|Ax\|$ und $\lambda _{\min }=\min _{\|x\|=1}\|Ax\|$ den größten bzw. kleinsten Eigenwert von $B$ bezeichnen.

Beweis 3 - Orthonormalbasis aus Eigenvektoren

Indem man $x$ mittels einer Orthonormalbasis von Eigenvektoren darstellt, kann man ferner die Abschätzungen

$\lambda _{\min }\|x\|_{2}^{2}\leq x^{T}Bx\leq \lambda _{\max }\|x\|_{2}^{2},\quad x\in \mathbb {R} ^{k}$

beweisen, wobei offenbar Gleichheit in der ersten bzw. zweiten Ungleichung für einen zu $\lambda _{\min }$ bzw. $\lambda _{\max }$ gehörenden Eigenvektor angenommen wird.

Beweis 4 - Orthonormalbasis aus Eigenvektoren

Folglich schließt man

$\lambda _{\min }=\min _{\|x\|_{2}=1}x^{T}Bx,\quad \lambda _{\max }=\max _{\|x\|_{2}=1}x^{T}Bx.$

Wendet man diese Ergebnisse auf das Lemma über Eigenwerte positiv definiter Matrizen auf die positiv definite Matrix $A^{T}A\in \mathbb {R} ^{k\times k}$ an,

Beweis 5 - Satz zur Berechnung der Konditionszahl

so erhält man mit dem Satz zur Berechnung der Konditionszahl

$\operatorname {cond} _{2}(A^{T}A)={\frac {\lambda _{\max(}A^{T}A)}{\lambda _{\min(}A^{T}A)}}={\frac {\max \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}{\min \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}}={\frac {\max \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}{\min \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}}=[\operatorname {cond} _{2}(A)]^{2}.$

q.e.d.

Bemerkung - Cholesky-Zerlegung

Es ist daher große Vorsicht bei Anwendung der Cholesky-Zerlegung für die Lösung der Normalgleichungen geboten. Prinzipiell ist sie nur zu empfehlen, wenn große Residuen $b_{i}-(Ax)_{i}$ $(i=1,\ldots ,n)$ in der Lösung des Ausgleichsproblems zu erwarten sind (s. Deuflhard/Hohmann). Sicherer ist es aber, so vorzugehen, wie es im folgenden Abschnitt beschrieben ist.

Siehe auch

• linearen Ausgleichsrechnung
• mehrdimensionale Taylorentwicklung
• Gradient
• Hesse-Matrix
• positiv semidefinit

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/L%C3%B6sung%20der%20Normalengleichung
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.