Lektion 8.4

Orthogonale Projektion und kleinste Quadrate

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • das orthogonale Komplement eines Unterraums bestimmen,

  • einen Vektor orthogonal auf einen Unterraum projizieren, mit einer Orthonormalbasis oder über das Komplement,

  • beweisen, dass die orthogonale Projektion der Punkt mit dem kleinsten Abstand ist,

  • ein unlösbares Gleichungssystem Ax=bAx = b über die Normalgleichungen ATAx=ATbA^TAx = A^Tb bestmöglich lösen,

  • eine Ausgleichsgerade durch Messpunkte berechnen.

Vorausgesetzt: Das Gram-Schmidt-Verfahren, Orthogonalität und Orthonormalbasen, Rang einer Matrix und Lösbarkeit

Bei einem Versuch misst du vier Wertepaare (xi,yi)(x_i, y_i): (0,1)(0, 1), (1,2)(1, 2), (2,2)(2, 2), (3,4)(3, 4). Sie liegen ungefähr auf einer Geraden y=c0+c1xy = c_0 + c_1x, aber nicht genau. Setzt man die vier Punkte ein, entsteht ein Gleichungssystem mit vier Gleichungen und zwei Unbekannten:

c0=1,c0+c1=2,c0+2c1=2,c0+3c1=4.c_0 = 1, \quad c_0 + c_1 = 2, \quad c_0 + 2c_1 = 2, \quad c_0 + 3c_1 = 4.

Aus den ersten beiden folgt c0=1c_0 = 1, c1=1c_1 = 1, und dann ist die dritte Gleichung falsch. Das System hat keine Lösung. Welche Gerade ist dann die beste?

Die Antwort ist eine geometrische: Man sucht im Unterraum aller möglichen „rechten Seiten“, die eine Gerade liefern kann, den Punkt, der dem Messvektor am nächsten liegt. Wie man in einer Ebene den nächsten Punkt zu einem gegebenen Punkt findet, weißt du aus der Schule: Man fällt das Lot. Diese Lektion macht daraus ein Werkzeug für jeden euklidischen Vektorraum.

Wie im ganzen Kapitel ist VV ein euklidischer Vektorraum; im Rn\mathbb{R}^n ist das Standardskalarprodukt gemeint.

Vermute zuerst

Im R2\mathbb{R}^2 sei UU die Gerade durch 00 in Richtung u=(1,1)Tu = (1, 1)^T. Welcher Punkt von UU liegt am nächsten an v=(2,0)Tv = (2, 0)^T?

Definition

Orthogonales Komplement

Es sei U⊆VU \subseteq V ein Unterraum. Das orthogonale Komplement von UU ist

U⊥={v∈V:⟨v,u⟩=0 fu¨r alle u∈U}.U^\perp = \{ v \in V : \langle v, u\rangle = 0 \text{ für alle } u \in U\}.

U⊥U^\perp ist wieder ein Unterraum: Es ist 0∈U⊥0 \in U^\perp, und aus ⟨v,u⟩=⟨v′,u⟩=0\langle v, u\rangle = \langle v', u\rangle = 0 folgt ⟨λv+μv′,u⟩=0\langle \lambda v + \mu v', u\rangle = 0. Außerdem ist U∩U⊥={0}U \cap U^\perp = \{0\}, denn ein xx in beiden erfüllt ⟨x,x⟩=0\langle x, x\rangle = 0.

Wird UU von u1,…,uku_1, \dots, u_k aufgespannt, genügt es, die Orthogonalität zu den uiu_i zu prüfen: Ist ⟨v,ui⟩=0\langle v, u_i\rangle = 0 für alle ii, dann ist vv wegen der Linearität orthogonal zu jeder Linearkombination der uiu_i.

Beispiel

Komplemente im R³

Für die Gerade U=span((1,1,1)T)U = \mathrm{span}\bigl((1, 1, 1)^T\bigr) ist U⊥={x:x1+x2+x3=0}U^\perp = \{x : x_1 + x_2 + x_3 = 0\}, eine Ebene. Für die Ebene U=span(e1,e2)U = \mathrm{span}(e_1, e_2) ist U⊥=span(e3)U^\perp = \mathrm{span}(e_3), die x3x_3-Achse.

Allgemein im Rm\mathbb{R}^m: Ist U=span(u1,…,uk)U = \mathrm{span}(u_1, \dots, u_k) und A=(u1∣⋯∣uk)A = (u_1 \mid \dots \mid u_k) die Matrix mit diesen Spalten, dann sind die Bedingungen ⟨x,ui⟩=uiTx=0\langle x, u_i\rangle = u_i^Tx = 0 genau die Zeilen des Systems ATx=0A^Tx = 0:

U⊥={x∈Rm:ATx=0}=Kern ATU^\perp = \{x \in \mathbb{R}^m : A^Tx = 0\} = \mathrm{Kern}\,A^T

Das orthogonale Komplement berechnet man also mit dem Gauß-Verfahren. Gegenbeispiel zur Anschauung: Ein Komplement im Sinn von „alles, was nicht in UU liegt“ ist U⊥U^\perp nicht. Der Vektor (1,0,1)T(1, 0, 1)^T liegt weder in span(e1,e2)\mathrm{span}(e_1, e_2) noch auf der x3x_3-Achse.

Satz

Orthogonale Zerlegung

Es sei U⊆VU \subseteq V ein endlichdimensionaler Unterraum (VV selbst darf unendlichdimensional sein, etwa C[a,b]C[a, b]). Dann lässt sich jedes v∈Vv \in V eindeutig schreiben als

v=u+wmit u∈U, w∈U⊥.v = u + w \quad \text{mit } u \in U,\ w \in U^\perp.

Ist q1,…,qkq_1, \dots, q_k eine ONB von UU, dann ist u=∑i=1k⟨v,qi⟩qiu = \sum_{i=1}^k\langle v, q_i\rangle q_i. Ist VV endlichdimensional, gilt außerdem dim⁡U⊥=dim⁡V−dim⁡U\dim U^\perp = \dim V - \dim U.

Definition

Orthogonale Projektion

Für einen endlichdimensionalen Unterraum U⊆VU \subseteq V heißt die Abbildung

PU:V→V,v↦u(der Anteil aus U in der Zerlegung v=u+w)P_U: V \to V, \quad v \mapsto u \quad (\text{der Anteil aus } U \text{ in der Zerlegung } v = u + w)

die orthogonale Projektion auf UU. Mit einer ONB q1,…,qkq_1, \dots, q_k von UU ist PU(v)=∑i⟨v,qi⟩qiP_U(v) = \sum_i\langle v, q_i\rangle q_i; daran sieht man, dass PUP_U linear ist. Das Bild ist UU, der Kern ist U⊥U^\perp, und PU(PU(v))=PU(v)P_U(P_U(v)) = P_U(v): Ein Vektor aus UU bleibt beim Projizieren, wie er ist.

Kennzeichnung ohne Formel: PU(v)P_U(v) ist der Vektor u∈Uu \in U, für den v−uv - u senkrecht auf UU steht. Diese Beschreibung hängt nur von UU ab, nicht von der gewählten ONB.

Projektion auf die Gerade durch b
xyzabproj
a⃗⋅b⃗\vec{a} \cdot \vec{b}
5
∣a⃗∣ ∣b⃗∣ cos⁡φ|\vec{a}|\,|\vec{b}|\,\cos\varphi
5
φ\varphi
33,9°

Das Skalarprodukt ist 5>05 > 0: Der Winkel ist spitz, die Projektion von a⃗\vec{a} zeigt in dieselbe Richtung wie b⃗\vec{b}.

Der Pfeil proj ist die orthogonale Projektion von a auf die Gerade U, die von b aufgespannt wird. Die gestrichelte Strecke von a zur Spitze von proj ist der Rest a minus proj, der auf U senkrecht steht.

Probier es aus

Beispiel

Projektion auf eine Ebene über das Komplement

Gesucht ist PU(v)P_U(v) für v=(1,2,6)Tv = (1, 2, 6)^T und die Ebene U={x∈R3:x1+x2+x3=0}U = \{x \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\}. Statt erst eine ONB der Ebene zu bauen, nutzt man U⊥=span(n)U^\perp = \mathrm{span}(n) mit n=(1,1,1)Tn = (1, 1, 1)^T. Aus v=PU(v)+PU⊥(v)v = P_U(v) + P_{U^\perp}(v) folgt PU(v)=v−PU⊥(v)P_U(v) = v - P_{U^\perp}(v), und die Projektion auf eine Gerade kennst du:

PU⊥(v)=⟨v,n⟩⟨n,n⟩n=93(111),PU(v)=(126)−(333)=(−2−13)P_{U^\perp}(v) = \frac{\langle v, n\rangle}{\langle n, n\rangle}n = \frac{9}{3}\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, \qquad P_U(v) = \begin{pmatrix} 1 \\ 2 \\ 6 \end{pmatrix} - \begin{pmatrix} 3 \\ 3 \\ 3 \end{pmatrix} = \begin{pmatrix} -2 \\ -1 \\ 3 \end{pmatrix}

Probe: −2−1+3=0-2 - 1 + 3 = 0, also PU(v)∈UP_U(v) \in U, und v−PU(v)=(3,3,3)Tv - P_U(v) = (3, 3, 3)^T ist ein Vielfaches von nn. Der Abstand von vv zur Ebene ist ∥(3,3,3)T∥=33\|(3, 3, 3)^T\| = 3\sqrt 3, wie mit der Hesseschen Normalform aus der Schule: ∣⟨v,n⟩∣∥n∥=93\frac{|\langle v, n\rangle|}{\|n\|} = \frac{9}{\sqrt 3}.

Satz

Bestapproximation

Es sei U⊆VU \subseteq V ein endlichdimensionaler Unterraum und v∈Vv \in V. Dann ist PU(v)P_U(v) der eindeutig bestimmte Vektor in UU mit kleinstem Abstand zu vv: Für alle u∈Uu \in U gilt

∥v−PU(v)∥≤∥v−u∥,mit Gleichheit nur fu¨r u=PU(v)\|v - P_U(v)\| \leq \|v - u\|, \quad \text{mit Gleichheit nur für } u = P_U(v)
Beispiel

Beste lineare Näherung einer Funktion

In C[−1,1]C[-1, 1] mit ⟨f,g⟩=∫−11fg dx\langle f, g\rangle = \int_{-1}^1 fg\,dx suchen wir die Funktion g(x)=c0+c1xg(x) = c_0 + c_1x, die f(x)=x2f(x) = x^2 im Sinn dieses Abstands am besten annähert. Der Unterraum UU der Polynome vom Grad höchstens 11 hat nach der letzten Lektion die orthogonale Basis 1,x1, x mit ⟨1,1⟩=2\langle 1, 1\rangle = 2 und ⟨x,x⟩=23\langle x, x\rangle = \frac{2}{3}. Mit ⟨x2,1⟩=23\langle x^2, 1\rangle = \frac{2}{3} und ⟨x2,x⟩=0\langle x^2, x\rangle = 0 ist

PU(x2)=2/32⋅1+02/3⋅x=13P_U(x^2) = \frac{2/3}{2}\cdot 1 + \frac{0}{2/3}\cdot x = \frac{1}{3}

Die beste Näherung ist die Konstante 13\frac{1}{3}, die keine Steigung hat: Der Graph von x2x^2 ist symmetrisch, und jede Steigung würde auf einer Seite so viel verschlechtern, wie sie auf der anderen verbessert. Der Fehler x2−13x^2 - \frac{1}{3} ist genau das dritte Polynom aus dem Gram-Schmidt-Beispiel, und der kleinste Abstand ist 8/45≈0,42\sqrt{8/45} \approx 0{,}42.

Kurz geprüft

Wie groß ist der Abstand des Punktes e1=(1,0,0)Te_1 = (1, 0, 0)^T von der Ebene U={x∈R3:x1+x2+x3=0}U = \{x \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\}? (Auf zwei Nachkommastellen.)

Schritt für Schritt

Von der Bestapproximation zu den Normalgleichungen

Gegeben sind A∈Rm×nA \in \mathbb{R}^{m \times n} mit Spalten a1,…,ana_1, \dots, a_n und b∈Rmb \in \mathbb{R}^m. Das System Ax=bAx = b hat vielleicht keine Lösung. Gesucht ist ein x^∈Rn\hat x \in \mathbb{R}^n, für das der Fehler ∥Ax^−b∥\|A\hat x - b\| so klein wie möglich ist. Weil ∥Ax^−b∥2\|A\hat x - b\|^2 die Summe der Quadrate der Einträge ist, heißt das die Methode der kleinsten Quadrate.

  1. Die Vektoren AxAx sind genau die Linearkombinationen der Spalten: Sie bilden den Unterraum U=Bild A=span(a1,…,an)U = \mathrm{Bild}\,A = \mathrm{span}(a_1, \dots, a_n) des Rm\mathbb{R}^m.

Schritt 1 von 4
Satz

Normalgleichungen

Es seien A∈Rm×nA \in \mathbb{R}^{m\times n} und b∈Rmb \in \mathbb{R}^m.

  • x^\hat x minimiert ∥Ax−b∥\|Ax - b\| genau dann, wenn ATAx^=ATbA^TA\hat x = A^Tb.
  • Die Normalgleichungen sind immer lösbar.
  • Sind die Spalten von AA linear unabhängig (Rang nn), dann ist ATAA^TA invertierbar, und die Lösung x^=(ATA)−1ATb\hat x = (A^TA)^{-1}A^Tb ist eindeutig.
Schritt für Schritt

Die Ausgleichsgerade zu den Messpunkten

Zurück zu den Punkten (0,1)(0, 1), (1,2)(1, 2), (2,2)(2, 2), (3,4)(3, 4) und dem Ansatz y=c0+c1xy = c_0 + c_1x. Gesucht sind c0,c1c_0, c_1, für die die Summe der Quadrate der Abweichungen in yy-Richtung ∑i(yi−c0−c1xi)2\sum_i (y_i - c_0 - c_1x_i)^2 minimal ist.

  1. Das System in Matrixform: Die erste Spalte gehört zu c0c_0 (lauter Einsen), die zweite zu c1c_1 (die xix_i).

    A=(10111213),b=(1224)A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix}, \qquad b = \begin{pmatrix} 1 \\ 2 \\ 2 \\ 4 \end{pmatrix}
Schritt 1 von 4
Kurz geprüft

Bei jeder Ausgleichsgeraden y=c0+c1xy = c_0 + c_1x, die mit den Normalgleichungen berechnet wird, ist die Summe der Residuen r1+⋯+rmr_1 + \dots + r_m gleich 00. Warum?

Häufige Fehler

Normalgleichungen falsch gekürzt

Zwei verbreitete Fehlschlüsse:

  • „Aus ATAx^=ATbA^TA\hat x = A^Tb kürzt man ATA^T und erhält Ax^=bA\hat x = b.“ Oder gleich: „x^=A−1b\hat x = A^{-1}b.“
  • „Die Ausgleichsgerade macht die senkrechten Abstände der Punkte zur Geraden möglichst klein.“
Richtig ist

ATA^T ist eine n×mn \times m-Matrix mit n<mn < m und hat einen großen Kern; man darf sie nicht kürzen. Eine Inverse A−1A^{-1} gibt es für nicht quadratisches AA gar nicht. Hätte Ax^=bA\hat x = b eine Lösung, wäre die Rechnung überflüssig.

Die Methode der kleinsten Quadrate minimiert ∑(yi−c0−c1xi)2\sum (y_i - c_0 - c_1x_i)^2, also die Abstände in yy-Richtung, im Bild der Messpunkte senkrecht zur xx-Achse. Die Orthogonalität, die dabei entsteht, findet im Rm\mathbb{R}^m der Messwerte statt (r⊥Bild Ar \perp \mathrm{Bild}\,A), nicht in der Zeichenebene der Punkte.

Zusammenfassung

  • U⊥U^\perp besteht aus allen Vektoren, die auf ganz UU senkrecht stehen; im Rm\mathbb{R}^m ist U⊥=Kern ATU^\perp = \mathrm{Kern}\,A^T, wenn die Spalten von AA den Raum UU aufspannen.

  • Für endlichdimensionales UU zerfällt jedes vv eindeutig in v=u+wv = u + w mit u∈Uu \in U, w∈U⊥w \in U^\perp; endlichdimensional ist dim⁡U⊥=dim⁡V−dim⁡U\dim U^\perp = \dim V - \dim U.

  • PU(v)=∑i⟨v,qi⟩qiP_U(v) = \sum_i\langle v, q_i\rangle q_i für eine ONB von UU; gekennzeichnet durch PU(v)∈UP_U(v) \in U und v−PU(v)⊥Uv - P_U(v) \perp U.

  • Bestapproximation: PU(v)P_U(v) ist der eindeutige Punkt von UU mit kleinstem Abstand zu vv (Beweis mit Pythagoras).

  • Oft ist PU(v)=v−PU⊥(v)P_U(v) = v - P_{U^\perp}(v) schneller, etwa bei einer Ebene mit Normalenvektor.

  • Kleinste Quadrate: ∥Ax−b∥\|Ax - b\| ist minimal genau für die Lösungen von ATAx=ATbA^TAx = A^Tb; bei linear unabhängigen Spalten ist die Lösung eindeutig.

  • Ausgleichsgerade y=c0+c1xy = c_0 + c_1x: AA hat die Spalten (1,…,1)T(1, \dots, 1)^T und (x1,…,xm)T(x_1, \dots, x_m)^T; die Residuen sind orthogonal zu beiden.

Übungen

Aufgabe 1Multiple Choice

Es sei U=span((1,2,0)T)⊆R3U = \mathrm{span}\bigl((1, 2, 0)^T\bigr) \subseteq \mathbb{R}^3. Welche Menge ist U⊥U^\perp?

Aufgabe 2Numerisch

Wie groß ist der Abstand des Punktes v=(3,1,2)Tv = (3, 1, 2)^T von der Ebene U={x∈R3:x1+2x2+2x3=0}U = \{x \in \mathbb{R}^3 : x_1 + 2x_2 + 2x_3 = 0\}?

Aufgabe 3Numerisch

Zu den Punkten (1,1)(1, 1), (2,3)(2, 3), (3,7)(3, 7) wird eine Ausgleichsgerade durch den Ursprung, y=mxy = mx, gesucht. Bestimme mm mit den Normalgleichungen.

Aufgabe 4Numerisch

Bestimme die Steigung c1c_1 der Ausgleichsgeraden y=c0+c1xy = c_0 + c_1x durch die Punkte (−1,1)(-1, 1), (0,1)(0, 1), (1,4)(1, 4).

Aufgabe 5Term eingeben

In C[−1,1]C[-1, 1] mit ⟨f,g⟩=∫−11fg dx\langle f, g\rangle = \int_{-1}^1 fg\,dx: Welche Funktion g(x)=c0+c1xg(x) = c_0 + c_1x nähert f(x)=x3f(x) = x^3 am besten an?

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Aufgabe 6Freitext

Es sei VV endlichdimensional und U⊆VU \subseteq V ein Unterraum. Beweise (U⊥)⊥=U(U^\perp)^\perp = U.