Lektion 8.3

Das Gram-Schmidt-Verfahren

35 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • aus einem Vektor den Anteil in Richtung eines anderen Vektors abziehen, sodass der Rest senkrecht steht,

  • das Gram-Schmidt-Verfahren herleiten und mit ihm aus linear unabhängigen Vektoren eine Orthonormalbasis machen,

  • das Verfahren im R3\mathbb{R}^3 und in einem Polynomraum mit Integral-Skalarprodukt vollständig durchrechnen,

  • begründen, warum jeder endlichdimensionale euklidische Vektorraum eine Orthonormalbasis hat.

Vorausgesetzt: Orthogonalität und Orthonormalbasen, Skalarprodukt und Norm, Basis und Dimension

Mit einer Orthonormalbasis (ONB) sind Koordinaten Skalarprodukte, und jedes Skalarprodukt rechnet sich wie das Standardskalarprodukt. Aber wo bekommt man eine her?

Zwei Beispiele, bei denen keine ONB auf der Hand liegt. Erstens die Ebene U={x∈R3:x1+x2+x3=0}U = \{x \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\}. Eine Basis ist schnell gefunden, etwa (1,−1,0)T(1, -1, 0)^T und (1,0,−1)T(1, 0, -1)^T, aber diese beiden stehen nicht senkrecht: Ihr Skalarprodukt ist 11.

Zweitens der Raum P2P_2 der reellen Polynome vom Grad höchstens 22 mit ⟨p,q⟩=∫−11p(x)q(x) dx\langle p, q\rangle = \int_{-1}^1 p(x)q(x)\,dx. Die vertraute Basis 1,x,x21, x, x^2 ist nicht orthogonal, denn ⟨1,x2⟩=∫−11x2 dx=23\langle 1, x^2\rangle = \int_{-1}^1 x^2\,dx = \frac{2}{3}.

Gesucht ist ein Verfahren, das aus irgendeiner Basis eine ONB macht und dabei möglichst wenig verändert. Die Idee stammt von Jørgen Pedersen Gram und Erhard Schmidt: Man nimmt die Vektoren der Reihe nach und entfernt von jedem den Anteil, der in Richtung der schon behandelten Vektoren zeigt.

Vermute zuerst

Im R2\mathbb{R}^2 sind w1=(1,1)Tw_1 = (1, 1)^T und v2=(2,3)Tv_2 = (2, 3)^T gegeben. Man möchte ein Vielfaches λw1\lambda w_1 von v2v_2 abziehen, sodass v2−λw1v_2 - \lambda w_1 senkrecht auf w1w_1 steht. Welches Vielfache ist das?

Schritt für Schritt

Herleitung des Verfahrens

Gegeben sind linear unabhängige Vektoren v1,…,vmv_1, \dots, v_m in einem euklidischen Vektorraum VV. Gesucht sind orthonormale q1,…,qmq_1, \dots, q_m, sodass für jedes kk die ersten kk neuen Vektoren denselben Raum aufspannen wie die ersten kk alten: span(q1,…,qk)=span(v1,…,vk)\mathrm{span}(q_1, \dots, q_k) = \mathrm{span}(v_1, \dots, v_k).

  1. Erster Vektor: Er muss nur normiert werden. Es ist v1≠0v_1 \neq 0, weil die Familie linear unabhängig ist.

    q1=v1∥v1∥q_1 = \frac{v_1}{\|v_1\|}
Schritt 1 von 5
Satz

Gram-Schmidt-Verfahren

Es seien v1,…,vmv_1, \dots, v_m linear unabhängige Vektoren in einem euklidischen Vektorraum VV. Man setzt nacheinander für k=1,…,mk = 1, \dots, m

wk=vk−∑i=1k−1⟨vk,qi⟩qiundqk=wk∥wk∥w_k = v_k - \sum_{i=1}^{k-1}\langle v_k, q_i\rangle q_i \quad\text{und}\quad q_k = \frac{w_k}{\|w_k\|}

(für k=1k = 1 ist die Summe leer, also w1=v1w_1 = v_1). Dann ist stets wk≠0w_k \neq 0, die Familie q1,…,qmq_1, \dots, q_m ist orthonormal, und für jedes kk gilt span(q1,…,qk)=span(v1,…,vk)\mathrm{span}(q_1, \dots, q_k) = \mathrm{span}(v_1, \dots, v_k).

Beispiel

Zwei Vektoren in der Ebene

Wir führen die Vorhersage zu Ende: v1=(1,1)Tv_1 = (1, 1)^T, v2=(2,3)Tv_2 = (2, 3)^T. Es ist w1=v1w_1 = v_1 mit ⟨w1,w1⟩=2\langle w_1, w_1\rangle = 2, und wie oben berechnet w2=v2−52w1=12(−1,1)Tw_2 = v_2 - \frac{5}{2}w_1 = \frac{1}{2}(-1, 1)^T. Den Faktor 12\frac{1}{2} darf man vor dem Normieren weglassen, er verschwindet beim Normieren ohnehin.

q1=12(11),q2=12(−11)q_1 = \frac{1}{\sqrt 2}\begin{pmatrix} 1 \\ 1 \end{pmatrix}, \qquad q_2 = \frac{1}{\sqrt 2}\begin{pmatrix} -1 \\ 1 \end{pmatrix}

Das Ergebnis hängt nur wenig von v2v_2 ab: Jeder Vektor v2v_2 oberhalb der Geraden durch v1v_1 (im Sinn von ⟨v2,q2⟩>0\langle v_2, q_2\rangle > 0) liefert dasselbe q2q_2. Das Verfahren behält von v2v_2 nur die Information, auf welcher Seite der Geraden span(v1)\mathrm{span}(v_1) es liegt.

Kurz geprüft

Du wendest das Verfahren auf v1,v2,v3v_1, v_2, v_3 an und erhältst w3=0w_3 = 0. Was folgt daraus?

Schritt für Schritt

Beispiel im R³

Wir orthonormalisieren v1=(1,1,0)Tv_1 = (1, 1, 0)^T, v2=(1,0,1)Tv_2 = (1, 0, 1)^T, v3=(0,1,1)Tv_3 = (0, 1, 1)^T bezüglich des Standardskalarprodukts. (Die drei sind linear unabhängig; das bestätigt das Verfahren, weil kein wkw_k verschwindet.)

  1. Es ist ∥v1∥=2\|v_1\| = \sqrt 2.

    q1=12(110)q_1 = \frac{1}{\sqrt 2}\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}
Schritt 1 von 4
Schritt für Schritt

Beispiel im Polynomraum

Im Raum P2P_2 mit ⟨p,q⟩=∫−11p(x)q(x) dx\langle p, q\rangle = \int_{-1}^1 p(x)q(x)\,dx orthogonalisieren wir 1,x,x21, x, x^2. Wir rechnen ohne Wurzeln mit der Formel aus dem Hinweis oben. Nützlich: ∫−11xk dx=2k+1\int_{-1}^1 x^k\,dx = \frac{2}{k+1} für gerades kk und 00 für ungerades kk.

  1. Erster Vektor: w1=1w_1 = 1 mit ⟨w1,w1⟩=∫−111 dx=2\langle w_1, w_1\rangle = \int_{-1}^1 1\,dx = 2.

Schritt 1 von 5
Kurz geprüft

Wende das Verfahren (ohne Normieren) auf 1,x1, x im Raum der Polynome vom Grad höchstens 11 an, diesmal mit ⟨p,q⟩=∫01p(x)q(x) dx\langle p, q\rangle = \int_0^1 p(x)q(x)\,dx. Gib w2w_2 an.

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

Satz

Existenz von Orthonormalbasen

Es sei VV ein endlichdimensionaler euklidischer Vektorraum.

  • VV besitzt eine Orthonormalbasis.
  • Jede orthonormale Familie q1,…,qmq_1, \dots, q_m in VV lässt sich zu einer Orthonormalbasis q1,…,qnq_1, \dots, q_n von VV ergänzen.
Häufige Fehler

Gegen die falschen Vektoren projiziert

Typische Rechenfehler beim Verfahren:

  • Man zieht von v3v_3 die Anteile in Richtung der alten Vektoren v1,v2v_1, v_2 ab statt in Richtung von q1,q2q_1, q_2 (oder w1,w2w_1, w_2).
  • Man zieht nur den Anteil in Richtung des letzten Vektors ab, also nur ⟨v3,q2⟩q2\langle v_3, q_2\rangle q_2.
  • Man rechnet mit nicht normierten wiw_i, vergisst aber die Division durch ⟨wi,wi⟩\langle w_i, w_i\rangle.
Richtig ist

Abgezogen wird immer in die Richtungen der schon orthogonalisierten Vektoren, und zwar in alle: wk=vk−∑i<k⟨vk,qi⟩qiw_k = v_k - \sum_{i<k}\langle v_k, q_i\rangle q_i. Nur weil q1,…,qk−1q_1, \dots, q_{k-1} paarweise orthogonal sind, stört das Abziehen eines Anteils die schon erreichte Orthogonalität zu den anderen nicht. Die viv_i sind nicht orthogonal, dort funktioniert die Rechnung nicht. Eine schnelle Probe nach jedem Schritt: ⟨wk,wj⟩=0\langle w_k, w_j\rangle = 0 für alle j<kj < k.

Außerdem hängt das Ergebnis von der Reihenfolge ab: Beginnt man mit v3v_3 statt mit v1v_1, entsteht eine andere ONB. Das ist kein Fehler, nur eine andere Wahl.

Zusammenfassung

  • Der Anteil von vv in Richtung w≠0w \neq 0 ist ⟨v,w⟩⟨w,w⟩w\frac{\langle v, w\rangle}{\langle w, w\rangle}w; zieht man ihn ab, steht der Rest senkrecht auf ww.

  • Gram-Schmidt: wk=vk−∑i<k⟨vk,qi⟩qiw_k = v_k - \sum_{i<k}\langle v_k, q_i\rangle q_i, dann qk=wk∥wk∥q_k = \frac{w_k}{\|w_k\|}.

  • Aus linear unabhängigen v1,…,vmv_1, \dots, v_m entstehen orthonormale q1,…,qmq_1, \dots, q_m mit gleichem Spann für jedes Anfangsstück.

  • Ein wk=0w_k = 0 zeigt, dass vkv_k von den vorigen Vektoren linear abhängt.

  • Mit nicht normierten wiw_i zu rechnen und am Ende zu normieren spart Wurzeln.

  • Im Polynomraum mit ∫−11pq dx\int_{-1}^1 pq\,dx liefert das Verfahren aus 1,x,x21, x, x^2 die Polynome 11, xx, x2−13x^2 - \frac{1}{3} (bis auf Faktoren Legendre-Polynome).

  • Jeder endlichdimensionale euklidische Vektorraum hat eine ONB, und jede orthonormale Familie lässt sich zu einer ONB ergänzen.

Übungen

Aufgabe 1Multiple Choice

Der erste Schritt des Verfahrens für v1=(3,4)Tv_1 = (3, 4)^T im R2\mathbb{R}^2 liefert

Aufgabe 2Numerisch

Im R3\mathbb{R}^3 seien v1=(1,0,1)Tv_1 = (1, 0, 1)^T und v2=(2,1,0)Tv_2 = (2, 1, 0)^T. Berechne w2=v2−⟨v2,v1⟩⟨v1,v1⟩v1w_2 = v_2 - \frac{\langle v_2, v_1\rangle}{\langle v_1, v_1\rangle}v_1 und gib ∥w2∥2\|w_2\|^2 an.

Aufgabe 3Multiple Choice

Welches Paar ist eine ONB der Ebene U={x∈R3:x1+x2+x3=0}U = \{x \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\} (Standardskalarprodukt)?

Aufgabe 4Term eingeben

Setze das Polynom-Beispiel fort: Im Raum der Polynome vom Grad höchstens 33 mit ⟨p,q⟩=∫−11p(x)q(x) dx\langle p, q\rangle = \int_{-1}^1 p(x)q(x)\,dx sind w1=1w_1 = 1, w2=xw_2 = x, w3=x2−13w_3 = x^2 - \frac{1}{3} schon orthogonal. Berechne w4w_4 aus v4=x3v_4 = x^3 (ohne Normieren).

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

Aufgabe 5Freitext

Zeige: Ist v1,…,vmv_1, \dots, v_m schon eine orthogonale Familie mit allen vi≠0v_i \neq 0, dann liefert das Gram-Schmidt-Verfahren einfach qk=vk∥vk∥q_k = \frac{v_k}{\|v_k\|}.

Aufgabe 6Freitext

Es sei A∈Rn×nA \in \mathbb{R}^{n\times n} invertierbar mit den Spalten a1,…,ana_1, \dots, a_n. Wende das Verfahren auf die Spalten an und zeige: Es gibt eine orthogonale Matrix QQ und eine obere Dreiecksmatrix RR mit positiven Diagonaleinträgen, sodass A=QRA = QR (QR-Zerlegung).