www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen
   Einstieg
   
   Index aller Artikel
   
   Hilfe / Dokumentation
   Richtlinien
   Textgestaltung
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
GramSchmidt
Mach mit! und verbessere/erweitere diesen Artikel!
Artikel • Seite bearbeiten • Versionen/Autoren

GramSchmidt

Gram Schmidt


Beschreibung

Das Gram-Schmidt-Verfahren dient dazu, eine Orthonormale Basis eines Vektorraums zu berechnen. Man möchte erreichen, dass die Basisvektoren paarweise senkrecht aufeinander stehen (also dass die Basisvektoren im Skalarprodukt mit den anderen 0 ergeben), und dass sie die Länge 1 haben, also normiert sind.


Algorithmus 1 (standard)

Das Verfahren unterteilt man in zwei Schritte:

1) Orthogonalisierung
2) Normalisierung

1) Orthogonalisierung

Man nehme sich den ersten Basisvektor $ v_1 $, und halte diesen fest.
Dann nehme man sich der Reihe nach den zweiten, dritten, i.ten Basisvektor, und berechne $ v_{2}'=v_2-\frac{<v_2,v_1>}{<v_1,v_1>}v_1 $
Dann nehme man sich den dritten Basisvektor und berechne $ v_{3}'=v_3-\frac{<v_3,v_1>}{<v_1,v_1>}v_1 $
Das führe man allgemein fort, man berechne also für alle i von 2 bis #Basisvektoren $ v_{i}'=v_i-\frac{<v_i,v_1>}{<v_1,v_1>}v_1 $

Nun hat man erreicht, dass die Basisvektoren $ v_{i} $, i=2,...,#Basisvektoren senkrecht auf dem ersten Basisvektor stehen.

Als nächstes ist zu erreichen, dass der die restlichen Basisvektoren $ v_{i} $, i=3,...,#Basisvektoren senkrecht auf dem zweiten stehen.
Dazu ist der obige Algorithmus mit den neuen Basisvektoren weiter zu verwenden, allerdings sehen die Indizes nun so aus:
$ v_{3}''=v_3'-\frac{<v_3',v_2'>}{<v_2',v_2'>}v_2 $, allgemein:

$ v_{i}''=v_i'-\frac{<v_i',v_2'>}{<v_2',v_2'>}v_2 $

Wenn man so alle weiteren Basisvektoren orthogonalisiert hat, wiederhole man diesen Schritt nocheinmal, denn nun muss man erreichen, dass der vierte, fünfte usw. Basisvektor auf dem dritten senkrecht steht.

Dies ist das Standardverfahren. Es gibt allerdings einen schöneren Algorithmus:


Algorithmus 2

Dieser Algorithmus ist im wesentlichen der oben vorgestellte Algorithmus, aber er verläuft viel einheitlicher und schneller und m.E. auch sicherer ab.

Diesen Algorithmus möchte ich anhand eines Beispieles zeigen, da es so deutlich leichter ist, ihn zu verstehen:

Gegeben seien die Basisvektoren $ v_1:=\pmat{0\\1\\0} $ $ v_2:=\pmat{1\\1\\1} $ $ v_3:=\pmat{0\\0\\1} $

Nun fassen wir die drei Basisvektoren zu einer Matrix zusammen:

Sei $ A:=\pmat{0&1&0\\1&1&0\\0&1&1} $
Nun berechnen wir $ (A\cdot{}e_1)^t\cdot{}A $, also berechnen wir das Produkt aus dem Transponierten der ersten Spalte der Matrix mit der Matrix selbst:

$ \pmat{0&1&0}\cdot{}\pmat{0&1&0\\1&1&0\\0&1&1}=\pmat{1&1&0} $

Dies kann man auch als Skalarprodukt der ersten Spalte mit allen drei Spalten verstehen.

Nun schreiben wir den eben berechneten Vektor unter die Matrix, und versuchen, durch elementare Spaltentransformationen Nullen in dem eben erzeugten Vektor zu erzeugen:
$ \pmat{0&1&0\\1&1&0\\0&1&1} $
$ \pmat{1&1&0} $

Man versucht nun, in der zweiten Spalte in der unteren Matrix eine 0 zu erzeugen. Das geht, indem man das -1 fach der ersten Spalte zur zweiten Spalte addiert. Die Matrix schaut dann so aus:

$ \pmat{0&1&0\\1&0&0\\0&1&1} $

Nun berechnet man wieder einen ähnlichen Zeilenvektor wie oben, nur, dass man diesmal die transponierte zweite Spalte der Matrix mit obigen, neuen Matrix multipliziert:

$ \pmat{1&0&1}\cdot{}\pmat{0&1&0\\1&0&0\\0&1&1}=\pmat{0&2&1} $

Die erste Null in dem Zeilenvektor muss dort stehen, denn das zeigt ja gerade an, dass die ersten beiden Vektoren senkrecht aufeinander stehen. Das ist ja auch unser Ziel.

Nun nehmen wir uns wieder den obigen Zeilenvektor, und schreiben ihn unter unsere Matrix:

$ \pmat{0&1&0\\1&0&0\\0&1&1} $
$ \pmat{0&2&1} $

Nun versuchen wir, in der letzen Spalte in dem Zielenvektor eine "0" zu erzeugen. Dazu addieren wir das -1/2-fache der zweiten Zeile zur dritten. Dann schaut die neue Matrix so aus:

$ \pmat{0&1&-1/2\\1&0&0\\0&1&1/2} $

Berechnet man nun die Skalarprodukte jedes Vektors mit dem anderen, so wird man feststellen, dass alle Skalarprodukte 0 sind. So ist dieser Algorithmus auch konstruiert. Dies zeigt uns an, dass nun die Basisvektoren paarweise senkrecht aufeinander stehen.

Hinweis: Sollte es mehr als drei Basisvektoren geben, so fahre man dann mit dem obigen Algorithmus fort, indem man den transponierten dritten Spaltenvektor der neuen Matrix mit der Matrix multipliziert, und das verfahren wiederholt, so lange, bis man an der letzten Spalte angekommen ist.

Nun hat man eine Orthogonalbasis erzeugt. Es fehlt noch, dass die Basisvektoren normiert sind. Das ist aber sehr einfach:

Gegeben sind nun die orthogonalen Basisvektoren

$ v_1=\pmat{0\\1\\0} $, $ v_2=\pmat{1\\0\\1} $, $ v_3=\pmat{-1/2\\0\\1/2}=1/2\pmat{-1\\0\\1} $

Nun berechne man die Beträge der Vektoren, und teile dann die Vektoren durch diese, so dass die Basisvektorn die normierte Länge 1 haben.

$ |v_1|=\sqrt{1} \Rightarrow v_1'=\pmat{0\\1\\0} $
$ |v_2|=\sqrt{1^2+0^2+1^2}=\sqrt{2} \Rightarrow v_2'=\frac{1}{\sqrt{2}}\pmat{1\\0\\1} $

Hinweis zum dritten Basisvektor: Man zieht in der Regel Skalare aus dem Vektor heraus, so dass man im Vektor dann nur noch ganzzahlige Werte stehen hat. Da es sich hier um Basisvektoren handelt, wo nur die Richtung entscheidend ist, lässt man dann diese Skalare im weiteren einfach weg:
$ v_3:=\pmat{-1\\0\\1} $
$ |v_3|=\sqrt{(-1)^2+0^2+1^2}=\sqrt{2} \Rightarrow v_3'=\frac{1}{\sqrt{2}}\pmat{-1\\0\\1} $


Also hat man die drei Basisvektoren orthonormalisiert, die nun so aussehen:

$ v_1'=\pmat{0\\1\\0} $

$ v_2'=\pmat{\sqrt{2}/2\\0\\\sqrt{2}/2} $

$ v_3'=\pmat{-\sqrt{2}/2\\0\\\sqrt{2}/2} $


Ausblick

Nun hat man eine Orthonormale Basis gefunden. Steckt man diese Vektoren wieder in eine Matrix, so erhält man eine Orthonormale Matrix, für die gilt: $ QQ^t=1 $, 1 ist die Einheitsmatrix.

Mit dieser Information kann man wunderbar die QR-Faktorisierung durchführen, denn A=QR, Q hat man gegeben durch die Matrix oben, und es gilt dann: $ A=QR => Q^{-1}A=R $ und mit dem Wissen, dass $ Q^{-1}=Q^t $ lässt sich sehr einfach R berechnen, wobei R eine obere Dreiecksmatrix ist.


Erstellt: Mo 18.02.2008 von Kroni
Letzte Änderung: Mo 18.02.2008 um 13:27 von Kroni
Artikel • Seite bearbeiten • Versionen/Autoren • Titel ändern • Artikel löschen • Quelltext

^ Seitenanfang ^
www.mathebank.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]