In der Mathematik, besonders geradlinigen Algebra und numerischen Analyse, ist der Prozess des Gramms-Schmidt eine Methode für orthonormalising eine Reihe von Vektoren in einem Skalarprodukt-Raum, meistens der Euklidische Raum R. Der Prozess des Gramms-Schmidt nimmt einen begrenzten, linear unabhängigen Satz S = {v, …, v} dafür und erzeugt einen orthogonalen Satz, der denselben k-dimensional Subraum von R wie S abmisst.

Die Methode wird nach dem Gramm von Jørgen Pedersen und Erhard Schmidt genannt, aber es ist früher in der Arbeit von Laplace und Cauchy erschienen. In der Theorie von Lüge-Gruppenzergliederungen wird es durch die Zergliederung von Iwasawa verallgemeinert.

Die Anwendung des Prozesses des Gramms-Schmidt zu den Spaltenvektoren einer vollen Säule reiht sich auf Matrix gibt die QR Zergliederung nach (es wird in einen orthogonalen und eine Dreiecksmatrix zersetzt).

Der Prozess des Gramms-Schmidt

Wir definieren den Vorsprung-Maschinenbediener durch

:

wo ‹ v, u › zeigt das Skalarprodukt der Vektoren v und u an. Dieser Maschinenbediener plant den Vektoren v orthogonal auf die Linie, die durch den Vektoren u abgemessen ist.

Der Prozess des Gramms-Schmidt arbeitet dann wie folgt:

:

\begin {richten }\aus

\mathbf {u} _1 & = \mathbf {v} _1, & \mathbf {e} _1 & = {\\mathbf {u} _1 \over \| \mathbf {u} _1 \|} \\

\mathbf {u} _2 & = \mathbf {v} _2-\mathrm {proj} _ {\\mathbf {u} _1 }\\, (\mathbf {v} _2),

& \mathbf {e} _2 & = {\\mathbf {u} _2 \over \| \mathbf {u} _2 \|} \\

\mathbf {u} _3 & = \mathbf {v} _3-\mathrm {proj} _ {\\mathbf {u} _1 }\\, (\mathbf {v} _3)-\mathrm {proj} _ {\\mathbf {u} _2 }\\, (\mathbf {v} _3), & \mathbf {e} _3 & = {\\mathbf {u} _3 \over \| \mathbf {u} _3 \|} \\

\mathbf {u} _4 & = \mathbf {v} _4-\mathrm {proj} _ {\\mathbf {u} _1 }\\, (\mathbf {v} _4)-\mathrm {proj} _ {\\mathbf {u} _2 }\\, (\mathbf {v} _4)-\mathrm {proj} _ {\\mathbf {u} _3 }\\, (\mathbf {v} _4), & \mathbf {e} _4 & = {\\mathbf {u} _4 \over \| \mathbf {u} _4 \|} \\

& {}\\\\vdots & & {}\\\\vdots \\

\mathbf {u} _k & = \mathbf {v} _k-\sum_ {j=1} ^ {k-1 }\\mathrm {proj} _ {\\mathbf {u} _j }\\, (\mathbf {v} _k), & \mathbf {e} _k & = {\\mathbf {u} _k\over \| \mathbf {u} _k \|}.

\end {richten }\aus</Mathematik>

Die Folge u..., u ist das erforderliche System von orthogonalen Vektoren, und die normalisierten Vektoren e..., e bilden einen orthonormalen Satz. Die Berechnung der Folge u..., u ist als Gramm-Schmidt orthogonalization bekannt, während die Berechnung der Folge e..., e als Gramm-Schmidt orthonormalization bekannt ist, weil die Vektoren normalisiert werden.

Um

zu überprüfen, dass diese Formeln eine orthogonale Folge zuerst nachgeben, rechnen Sie &lsaquo; u, u &rsaquo; durch das Ersetzen der obengenannten Formel für u: Wir bekommen Null. Dann verwenden Sie das&lsaquo zu rechnen; u, u &rsaquo; wieder durch das Auswechseln gegen die Formel u: Wir bekommen Null. Der allgemeine Beweis geht durch die mathematische Induktion weiter.

Geometrisch geht diese Methode wie folgt weiter: Um u zu schätzen, plant es v orthogonal auf den Subraum U erzeugt durch u..., u, der dasselbe als der Subraum ist, der durch v..., v erzeugt ist. Der Vektor u wird dann definiert, um der Unterschied zwischen v und diesem Vorsprung, versichert zu sein, zu allen Vektoren im Subraum U orthogonal zu sein.

Der Prozess des Gramms-Schmidt gilt auch für eine linear unabhängige zählbar unendliche Folge {v}. Das Ergebnis ist ein orthogonaler (oder orthonormal) Folge {u} solch dass für die natürliche Zahl n:

die algebraische Spanne von v..., v ist dasselbe als dieser von u..., u.

Wenn der Prozess des Gramms-Schmidt auf eine lineare abhängig Folge, es Produktionen der 0 Vektor auf dem Ith-Schritt angewandt wird, annehmend, dass v eine geradlinige Kombination dessen ist. Wenn eine orthonormale Basis erzeugt werden soll, dann sollte der Algorithmus für Nullvektoren in der Produktion prüfen und sie verwerfen, weil kein Vielfache eines Nullvektoren eine Länge 1 haben kann. Die Zahl der Vektor-Produktion durch den Algorithmus wird dann die Dimension des durch die ursprünglichen Eingänge abgemessenen Raums sein.

Eine Variante des Prozesses des Gramms-Schmidt mit transfinitem recursion hat für (vielleicht unzählbar) unendliche Folge von Vektoren gegolten

Beispiel

Denken Sie den folgenden Satz von Vektoren in R (mit dem herkömmlichen Skalarprodukt)

:

Führen Sie jetzt Gramm-Schmidt durch, um einen orthogonalen Satz von Vektoren zu erhalten:

::

Wir überprüfen, dass die Vektoren u und u tatsächlich orthogonal sind:

:

die Anmerkung, dass, wenn das Punktprodukt von zwei Vektoren 0 dann ist, sie orthogonal sind.

Wir können dann die Vektoren normalisieren, indem wir ihre Größen, wie gezeigt, oben austeilen:

::

= {1\over\sqrt {10}} \begin {pmatrix}-1 \\3\end {pmatrix}. </Mathematik>

Numerische Stabilität

Wenn dieser Prozess auf einem Computer durchgeführt wird, sind die Vektoren häufig, wegen Rundungsfehler nicht ziemlich orthogonal. Für den Prozess des Gramms-Schmidt, wie beschrieben, oben (manchmal gekennzeichnet als "klassisches Gramm-Schmidt") ist dieser Verlust von orthogonality besonders schlecht; deshalb wird es gesagt, dass der (klassische) Prozess des Gramms-Schmidt numerisch nicht stabil ist.

Der Prozess des Gramms-Schmidt kann durch eine kleine Modifizierung stabilisiert werden; diese Version wird manchmal modifiziertes Gramm-Schmidt oder MG genannt.

Diese Annäherung gibt dasselbe Ergebnis wie die ursprüngliche Formel in der genauen Arithmetik und führt kleinere Fehler in der Arithmetik der begrenzten Präzision ein.

Anstatt den Vektoren u als zu schätzen

:

es wird als geschätzt

:

\mathbf {u} _k^ {(1)} &= \mathbf {v} _k - \mathrm {proj} _ {\\mathbf {u} _1 }\\, (\mathbf {v} _k), \\

\mathbf {u} _k^ {(2)} &= \mathbf {u} _k^ {(1)} - \mathrm {proj} _ {\\mathbf {u} _2} \, (\mathbf {u} _k^ {(1)}), \\

& \, \, \, \vdots \\

\mathbf {u} _k^ {(k-2)} &= \mathbf {u} _k^ {(k-3)} - \mathrm {proj} _ {\\mathbf {u} _ {k-2}} \, (\mathbf {u} _k^ {(k-3)}), \\

\mathbf {u} _k^ {(k-1)} &= \mathbf {u} _k^ {(k-2)} - \mathrm {proj} _ {\\mathbf {u} _ {k-1}} \, (\mathbf {u} _k^ {(k-2)}).

\end {richten} </Mathematik> {aus}

Jeder Schritt findet einen Vektoren orthogonal dazu. So ist auch orthogonalized gegen irgendwelche Fehler, die in der Berechnung dessen eingeführt sind.

Algorithmus

Der folgende Algorithmus führt das stabilisierte Gramm-Schmidt orthonormalization durch. Die Vektoren v, …, v werden durch orthonormale Vektoren ersetzt, die denselben Subraum abmessen.

: für j von 1 bis k tun

:: weil ich von 1 bis j  1 tue

::: (entfernen Sie Bestandteil in der Richtung v)

:: als nächstes ich

:: (normalisieren Sie)

: folgender j

Die Kosten dieses Algorithmus sind asymptotisch 2nk, Punkt-Operationen schwimmen lassend, wo n der dimensionality der Vektoren ist.

Bestimmende Formel

Das Ergebnis des Prozesses des Gramms-Schmidt kann in einer nichtrekursiven Formel mit Determinanten ausgedrückt werden.

:

\langle \mathbf {v} _1, \mathbf {v} _1 \rangle & \langle \mathbf {v} _2, \mathbf {v} _1 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _1 \rangle \\

\langle \mathbf {v} _1, \mathbf {v} _2 \rangle & \langle \mathbf {v} _2, \mathbf {v} _2 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _2 \rangle \\

\vdots & \vdots & \ddots & \vdots \\

\langle \mathbf {v} _1, \mathbf {v} _ {j-1} \rangle & \langle \mathbf {v} _2, \mathbf {v} _ {j-1} \rangle & \dots

&

\langle \mathbf {v} _j, \mathbf {v} _ {j-1} \rangle \\

\mathbf {v} _1 & \mathbf {v} _2 & \dots & \mathbf {v} _j \end {vmatrix} </Mathematik>

:\langle \mathbf {v} _1, \mathbf {v} _1 \rangle & \langle \mathbf {v} _2, \mathbf {v} _1 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _1 \rangle \\\langle \mathbf {v} _1, \mathbf {v} _2 \rangle & \langle \mathbf {v} _2, \mathbf {v} _2 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _2 \rangle \\\vdots & \vdots & \ddots & \vdots \\\langle \mathbf {v} _1, \mathbf {v} _ {j-1} \rangle & \langle \mathbf {v} _2, \mathbf {v} _ {j-1} \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _ {j-1} \rangle \\\mathbf {v} _1 & \mathbf {v} _2 & \dots & \mathbf {v} _j \end {vmatrix} </Mathematik>

wo D =1 und, für j  1, D die Gramm-Determinante ist

:\langle \mathbf {v} _1, \mathbf {v} _1 \rangle & \langle \mathbf {v} _2, \mathbf {v} _1 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _1 \rangle \\\langle \mathbf {v} _1, \mathbf {v} _2 \rangle & \langle \mathbf {v} _2, \mathbf {v} _2 \rangle & \dots & \langle \mathbf {v} _j, \mathbf {v} _2 \rangle \\\vdots & \vdots & \ddots & \vdots \\

\langle \mathbf {v} _1, \mathbf {v} _j \rangle & \langle \mathbf {v} _2, \mathbf {v} _j\rangle & \dots

&

\langle \mathbf {v} _j, \mathbf {v} _j \rangle \end {vmatrix}. </Mathematik>

Bemerken Sie, dass der Ausdruck für u eine "formelle" Determinante ist, d. h. die Matrix beide Skalare enthält

und Vektoren; die Bedeutung dieses Ausdrucks wird definiert, um das Ergebnis einer cofactor Vergrößerung entlang zu sein

die Reihe von Vektoren.

Die bestimmende Formel für das Gramm-Schmidt ist rechenbetont langsamer als die rekursiven Algorithmen, die oben beschrieben sind;

es ist hauptsächlich vom theoretischen Interesse.

Alternativen

Andere orthogonalization Algorithmen verwenden Wohnungsinhaber-Transformationen oder Folgen von Givens. Die Algorithmen mit Wohnungsinhaber-Transformationen sind stabiler als der stabilisierte Prozess des Gramms-Schmidt. Andererseits erzeugt der Prozess des Gramms-Schmidt den th orthogonalized Vektor nach der th Wiederholung, während orthogonalization verwendendes Wohnungsinhaber-Nachdenken alle Vektoren nur am Ende erzeugt. Das macht nur den Prozess des Gramms-Schmidt anwendbar für wiederholende Methoden wie die Wiederholung von Arnoldi.

Und doch wird eine andere Alternative durch den Gebrauch der Zergliederung von Cholesky motiviert, für die Matrix der normalen Gleichungen im geradlinigen kleinste Quadrate umzukehren. Lassen Sie, eine volle Säulenreihe-Matrix zu sein, welche Säulen orthogonalized sein müssen. Die Matrix ist Hermitian und positiv bestimmt, so kann es als das Verwenden der Zergliederung von Cholesky geschrieben werden. Die niedrigere Dreiecksmatrix mit ausschließlich positiven diagonalen Einträgen ist invertible. Dann sind Säulen der Matrix orthonormal und messen denselben Subraum wie die Säulen der ursprünglichen Matrix ab. Der ausführliche Gebrauch des Produktes macht den Algorithmus nicht stabil besonders, wenn die Bedingungszahl des Produktes groß ist. Dennoch wird dieser Algorithmus in der Praxis verwendet und in einigen Softwarepaketen wegen seiner hohen Leistungsfähigkeit und Einfachheit durchgeführt.

In der Quant-Mechanik gibt es mehrere orthogonalization Schemas mit Eigenschaften, die besser für Anwendungen angepasst sind als das Gramm-Schmidt ein. Die wichtigsten unter ihnen sind das Symmetrische und der Kanonische orthonormalization (sieh Solivérez & Gagliano).

. . . .

Links

• Universitätsmathetutorenkurs von Harvey Mudd auf dem Algorithmus des Gramms-Schmidt
• Frühster bekannter Gebrauch von einigen der Wörter der Mathematik: G Der Zugang "Hat Gramm-Schmidt orthogonalization" etwas Information und Verweisungen auf den Ursprüngen der Methode.
• Demos: Der Prozess von Gram Schmidt im Flugzeug und Gram Schmidt geht im Raum in einer Prozession
• Gramm-Schmidt orthogonalization applet