Kurs:Numerik I/Lösung der Normalengleichung

Mehrdimensionale Taylorentwicklung

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

$F(x)=F(x_0)+⟨\mathrm{\nabla }F(x_0),x-x_0⟩+\frac{1}{2}⟨{\mathrm{H}}_F(x_0)\cdot (x-x_0),x-x_0⟩$

Dabei ist $\mathrm{\nabla }F(x_0)$ der Gradient von $F$ an der Stelle $x_0$ und ${\mathrm{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)=\underset{=F(0_V)}{\underbrace{b^{T}b}}-{\underset{=\mathrm{\nabla }F(0_V)}{\underbrace{(2A^{T}b)}}}^{T}x+\frac{1}{2}(\underset{H_F(0_V)}{\underbrace{(2A^{T}A)}}x{)}^{T}x$

Mehrdimensionale Taylorentwicklung

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

$F(x)=\underset{=F(0_V)}{\underbrace{\Vert b{\Vert }_2^2}}-⟨\underset{=\mathrm{\nabla }F(0_V)}{\underbrace{2A^{T}b}},x⟩+\frac{1}{2}⟨\underset{H_F(0_V)}{\underbrace{(2A^{T}A)}}x,x⟩$

Rang der Matrix

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

• im Entwicklungspunkt $x_0:=0_V$ den Gradienten $\mathrm{\nabla }F(0_V)=-2A^T$,
• an der Stelle $x$ den Gradienten $\mathrm{\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 {ℝ}^k$ Minimalpunkt von $F$ ist, ist die Bedingung $\mathrm{\nabla }F(x^{*})=0$ bzw. äquivalent dazu, dass $x^{*}$ die sog. Normalgleichungen

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

erfüllt. Nach dem Lemma zur Lösbarkeit der Normalengleichung ist dabei die (von $x$ unabhängige) Matrix ${\mathrm{\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 {ℝ}^{n\times k}$ mit $n\ge k$ und $\mathrm{Rang}(A)=k$. Dann besitzt das lineare Ausgleichsproblem

$\underset{x\in {ℝ}^k}{\min }\Vert b-Ax{\Vert }_2$

eine eindeutige Lösung $x^{*}\in {ℝ}^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 {ℝ}^{k\times k}$ ist mit $A\in {ℝ}^{n\times k}$ und $n\ge k$ eine symmetrische Matrix, da die Kompomenten bestehen aus den Skalarprodukten der Spaltenvektor $a_i\in {ℝ}^n$ von $A$ mit:

$A^{T}A=(⟨a_i,a_j⟩{)}_{1\le i,j\le k}\in {ℝ}^{k\times k}$

Die Symmetrie des Skalarprodukte $⟨x,y⟩=⟨y,x⟩$ für $x,y\in {ℝ}^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 {ℝ}^{n\times k}$ und $n>k$ ist nicht quadratisch. Wenn der Rang von $A$ allerdings $k$, hat $A^{T}A\in {ℝ}^{k\times k}$ auch den Rang $k$ und die Matrix $A^{T}A\in {ℝ}^{k\times k}$ ist invertierbar. Mit der Normalengleichung, $\hat{A}:=A^{T}A\in {ℝ}^{k\times k}$ $\hat{b}:=A^{T}b\in {ℝ}^k$ gilt für die eindeutige Lösung $x\in {ℝ}^k$ von $\hat{A}x=\hat{b}$

$x={\hat{A}}^{-1}\hat{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,\dots ,n)$ mit $n\ge 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,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,t\in ℝ$

und die gesuchten optimalen Koeffizienten der Geradengleichung werden durch den Vektor $x:=(x_1,x_2)\in {ℝ}^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,\dots ,y_n{)}^T\in {ℝ}^n,d:=(t_1,t_2,\dots ,t_n{)}^T\in {ℝ}^n$

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

$e:=(1,1,\dots ,1{)}^T\in {ℝ}^n$

Beispiel - Definition der Matrix A - 4

Nun hat $A\in {ℝ}^{n\times 2}$ in diesem Fall die Gestalt $A=\left(\begin{array}{cc}e& d\end{array}\right)$. Da der erste Spaltenvektor $e$ nur als Komponenten die 1 besitzt und die Zeitpunkte in $d=(t_1,\dots ,t_n)$ paarweise verschieden sind, hat die Matrix den Rang 2.

Beispiel - Berechnung der symmetrischen Matrix - 5

Weiter ist dann

$A^{T}A=\left(\begin{array}{c}{e}^T\\ d^T\end{array}\right)\left(\begin{array}{cc}e& d\end{array}\right)=\left(\begin{array}{cc}{e}^{T}e& e^{T}d\\ e^{T}d& d^{T}d\end{array}\right),A^{T}b=\left(\begin{array}{c}{e}^{T}b\\ d^{T}b\end{array}\right).$

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

Beispiel - Inverse Matrix zur symmetrischen Matrix - 6

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

$B^{-1}={\left(\begin{array}{cc}{b}_{11}& b_{12}\\ b_{12}& b_{22}\end{array}\right)}^{-1}=\frac{1}{b_{11}{b}_{22}-b_{12}^2}\left(\begin{array}{cc}{b}_{22}& -b_{12}\\ -b_{12}& b_{11}\end{array}\right).$

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}\left(\begin{array}{cc}{d}^{T}d& -e^{T}d\\ -e^{T}d& e^{T}e\end{array}\right)\left(\begin{array}{c}{e}^{T}b\\ d^{T}b\end{array}\right)$

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}\left(\begin{array}{c}\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{array}\right).$

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

Dabei hat man

$e^{T}e=n,e^{T}d=\sum _{j=1}^n{t}_j,e^{T}b=\sum _{j=1}^n{y}_j,d^{T}d=\sum _{j=1}^n{t}_j^2,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}\left(\begin{array}{c}\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{array}\right).$

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

Beispielsweise für die $n=8$ Wertepaare

$\begin{array}{ccccccccc}{t}_j& 1& 2& 3& 4& 5& 6& 7& 8\\ y_j& 1.75& 2.18& 2.63& 3.24& 3.69& 4.16& 4.55& 5.29\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,\sum _{j=1}^8{y}_j=27.49,\sum _{j=1}^8{t}_j^2=204,\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}\left(\begin{array}{c}204\cdot 27.49-36\cdot 144.54\\ 8\cdot 144.54-36\cdot 27.49\end{array}\right)=\left(\begin{array}{c}1.203929\\ 0.496071\end{array}\right).$

Die Ausgleichsgerade zu den gegebenen Daten lautet folglich

$z(x^{*},t):=1.203929+0.496071t,t\in ℝ.$

Beispiel - Maximaler Fehler der Lösung - 14

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

$\underset{1\le j\le 8}{\max }\frac{|y_j-z(x^{*},t_j)|}{|z(x^{*},t_j)|}=0.016243$

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:=\left(\begin{array}{cccc}1& t_1& \dots & t_1^{k-1}\\ 1& t_2& \dots & t_2^{k-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& t_k& \dots & t_k^{k-1}\end{array}\right).$

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 {ℝ}^{n\times n}$ eine positiv definite Matrix, dann sind alle Eigenwerte positiv.

Beweis

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

$0<⟨Ax,x⟩=⟨\lambda \cdot x,x⟩=\lambda \cdot \underset{>0}{\underbrace{⟨x,x⟩}}$

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 $\mathrm{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 $\mathrm{Rang}(A)<k$ nur positiv semidefinit, denn es gilt für alle $x\in {ℝ}^k\setminus \{0_v\}$:

$⟨A^{T}Ax,x⟩=(A^{T}Ax{)}^{T}x=x^T{A}^{T}Ax=(Ax{)}^{T}Ax=⟨Ax,Ax⟩\ge 0$

Lemma - Konditionszahl Normalengleichung

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

${\mathrm{cond}}_2(A^{T}A)=({\mathrm{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 {ℝ}^{k\times k}$ gilt für die Eigenwerte ${\lambda }_i:={\lambda }_i(B)>0$ $(i=1,\dots ,k)$.

Beweis 1 - Eigenwert der inversen Matrix

Weiter hat wegen

$B{x}^i={\lambda }_i{x}^i\iff B^{-1}{x}^i=\frac{1}{{\lambda }_i}{x}^i$

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

Beweis 2 - Berechnung der Konditionszahl

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

${\mathrm{cond}}_2(B)=\Vert B{\Vert }_2{\Vert B^{-1}\Vert }_2=\frac{{\lambda }_{m}ax}{{\lambda }_{\min }},$

$\mathrm{cond}(A)=(\underset{\Vert x\Vert =1}{\max }\Vert Ax\Vert )/(\underset{\Vert x\Vert =1}{\min }\Vert Ax\Vert ).$

wobei ${\lambda }_{\max }=\underset{\Vert x\Vert =1}{\max }\Vert Ax\Vert$ und ${\lambda }_{\min }=\underset{\Vert x\Vert =1}{\min }\Vert Ax\Vert$ 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 }\Vert x{\Vert }_2^2\le x^{T}Bx\le {\lambda }_{\max }\Vert x{\Vert }_2^2,x\in {ℝ}^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 }=\underset{\Vert x{\Vert }_2=1}{\min }{x}^{T}Bx,{\lambda }_{\max }=\underset{\Vert x{\Vert }_2=1}{\max }{x}^{T}Bx.$

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

Beweis 5 - Satz zur Berechnung der Konditionszahl

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

${\mathrm{cond}}_2(A^{T}A)=\frac{{\lambda }_{\max (}{A}^{T}A)}{{\lambda }_{\min (}{A}^{T}A)}=\frac{\max {\mathrm{\backslash limits}}_{\Vert x{\Vert }_2=1}{x}^T(A^{T}A)x}{\min {\mathrm{\backslash limits}}_{\Vert x{\Vert }_2=1}{x}^T(A^{T}A)x}=\frac{\max {\mathrm{\backslash limits}}_{\Vert x{\Vert }_2=1}\Vert Ax{\Vert }_2^2}{\min {\mathrm{\backslash limits}}_{\Vert x{\Vert }_2=1}\Vert Ax{\Vert }_2^2}=[{\mathrm{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,\dots ,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.