Proces Grama-Schmidta - Gram–Schmidt process

Pierwsze dwa etapy procesu Grama-Schmidta

W matematyce , szczególnie w algebrze liniowej i analizie numerycznej , proces Grama-Schmidta jest metodą ortonormalizacji zbioru wektorów w przestrzeni produktu wewnętrznego , najczęściej przestrzeni euklidesowej R ⁿ wyposażonej w standardowy iloczyn skalarny . Proces Grama-Schmidta bierze skończony , liniowo niezależny zbiór wektorów S = { v ₁ , …, v _k } dla k ≤ n i generuje ortogonalny zbiór S′ = { u ₁ , …, u _k }, który obejmuje to samo k- wymiarowa podprzestrzeń R ⁿ jako S .

Metoda nosi imię Jørgena Pedersena Grama i Erharda Schmidta , ale Pierre-Simon Laplace znał ją przed Gramem i Schmidtem. W teorii dekompozycji grup Liego jest uogólniony przez dekompozycję Iwasawy .

Zastosowanie procesu Gram-Schmidt wektorów kolumnowych pełnej kolumny rang macierzy daje QR rozkładu (nie rozkłada się w produkt prostopadłe i w trójkątnym matrycy ).

Proces Grama-Schmidta

Zmodyfikowany proces Grama-Schmidta wykonywany na trzech liniowo niezależnych, nieortogonalnych wektorach bazy dla R ³ . Kliknij na zdjęcie, aby uzyskać szczegółowe informacje. Modyfikację omówiono w sekcji Stabilność liczbowa tego artykułu.

Operator projekcji definiujemy przez

${\ Displaystyle \ mathrm {proj} _ {\ mathbf {u}} (\ mathbf {v} ) = {\ frac {\ langle \ mathbf {u} \ mathbf {v} \ rangle} {\ langle \ mathbf { u} ,\mathbf {u} \rangle }}{\mathbf {u} },}$

gdzie oznacza iloczyn skalarny wektorów u i v . Operator ten rzutuje wektor v prostopadle na linię rozpiętą przez wektor u . Jeśli u = 0 , definiujemy , tzn. mapą projekcji jest mapa zerowa, wysyłająca każdy wektor do wektora zerowego. ${\ Displaystyle \ langle \ mathbf {u} \ mathbf {v} \ rangle}$${\displaystyle \mathrm {projekt} _{\mathbf {0}}(\mathbf {v}):=\mathbf {0}}$${\ Displaystyle \ operatorname {projekt} _ {\ mathbf {0}}}$

Proces Grama-Schmidta działa wtedy w następujący sposób:

${\ Displaystyle {\ zacząć {wyrównany} \ mathbf {u} _ {1} i = \ mathbf {v} _ {1} i \ mathbf {e} _ {1} i = {\ Frac {\ mathbf {u } _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {v} _{2}-\mathrm {projekt} _{\mathbf {u} _{1}}(\mathbf {v} _{2}),&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}} {\|\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}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\\mathbf {u} _{4} &=\mathbf {v} _{4}-\mathrm {projekt} _{\mathbf {u} _{1}}(\mathbf {v} _{4})-\mathrm {projekt} _{\mathbf {u} _{2}}(\mathbf {v} _{4})-\mathrm {projekt} _{\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}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}.\end{wyrównany}}}$

Sekwencja u ₁ , ..., U _k jest wymagany system prostopadłych wektorów oraz wektorów znormalizowane e ₁ , ..., e _k tworzą orto względem normalnego zestawu. Obliczanie sekwencji U ₁ , ..., U _k jest znany jako Gram-Schmidt ortogonalizacji , zaś obliczanie sekwencji e ₁ , ..., e _k jest znany jako Gram-Schmidt orthonormalization jako wektory są znormalizowane.

Aby sprawdzić, czy te wzory dają sekwencję ortogonalną, najpierw oblicz , zastępując powyższy wzór u ₂ : otrzymujemy zero. Następnie użyj tego do obliczenia ponownie, zastępując wzór za u ₃ : otrzymujemy zero. Ogólny dowód przebiega przez indukcję matematyczną . ${\ Displaystyle \ langle \ mathbf {u} _ {1} \ mathbf {u} _ {2} \ rangle}$${\ Displaystyle \ langle \ mathbf {u} _ {1} \ mathbf {u} _ {3} \ rangle}$

Geometrycznie metoda ta przebiega następująco: aby obliczyć u _i , rzutuje v _i prostopadle na podprzestrzeń U generowaną przez u ₁ , …, u _{i −1} , która jest taka sama jak podprzestrzeń generowana przez v ₁ , …, v _{i -1} . Wektor U _i jest definiowana jako różnica pomiędzy v _i i ten występ, na pewno być ortogonalne do wszystkich wektorów w podprzestrzeni U .

Proces Grama-Schmidta stosuje się również do liniowo niezależnej przeliczalnie nieskończonej sekwencji { v _i } _i . Wynikiem jest ortogonalny (lub ortonormalny) ciąg { u _i } _i taki, że dla liczby naturalnej n : rozpiętość algebraiczna v ₁ , …, v _n jest taka sama jak rozpiętość u ₁ , …, u _n .

Jeśli proces Grama-Schmidta zostanie zastosowany do sekwencji zależnej liniowo, wyprowadza wektor 0 na i- tym kroku, zakładając, że v _i jest kombinacją liniową v ₁ , …, v _{i -1} . Jeśli ma zostać wytworzona baza ortonormalna, algorytm powinien przetestować na wyjściu wektory zerowe i odrzucić je, ponieważ żadna wielokrotność wektora zerowego nie może mieć długości 1. Liczba wektorów wyprowadzonych przez algorytm będzie wtedy wymiarem przestrzeni zajmowanej przez oryginalne dane wejściowe.

Wariant procesu Grama-Schmidta z wykorzystaniem rekurencji pozaskończonej zastosowanej do (prawdopodobnie nieskończenie) nieskończonej sekwencji wektorów daje zestaw wektorów ortonormalnych z takim, że dla dowolnego , zakończenie rozpiętości jest takie samo jak . W szczególności, po zastosowaniu do (algebraicznej) bazy przestrzeni Hilberta (lub, bardziej ogólnie, bazy dowolnej gęstej podprzestrzeni), daje (funkcjonalno-analityczną) bazę ortonormalną. Zauważ, że w ogólnym przypadku często zachodzi ścisła nierówność , nawet jeśli zbiór początkowy był liniowo niezależny, a rozpiętość nie musi być podprzestrzenią rozpiętości (raczej jest podprzestrzenią jej uzupełnienia). ${\ Displaystyle (v_ {\ alfa}) _ {\ alfa <\ lambda}}$${\ Displaystyle (u_ {\ alfa}) _ {\ alfa <\ kappa}}$${\ Displaystyle \ kappa \ leq \ lambda}$${\ Displaystyle \ alfa \ leq \ lambda}$${\ Displaystyle \ {u_ {\ beta}: \ beta <\ min (\ alfa, \ kappa) \}}$${\ Displaystyle \ {v_ {\ beta}: \ beta <\ alfa \}}$${\ Displaystyle \ kappa < \ lambda }$${\ Displaystyle (u_ {\ alfa}) _ {\ alfa <\ kappa}}$${\ Displaystyle (v_ {\ alfa}) _ {\ alfa <\ lambda}}$

Przykład

Przestrzeń euklidesowa

Rozważ następujący zestaw wektorów w R ² (z konwencjonalnym iloczynem skalarnym )

${\ Displaystyle S = \ lewo \ {\ mathbf {v} _ {1} = {\ zacząć {bmatrix} 3 \ \ 1 \ koniec {bmatrix}}, \ mathbf {v} _ {2} = {\ zacząć { bmatrix}2\\2\end{bmatrix}}\right\}.}$

Teraz wykonaj Grama-Schmidta, aby otrzymać ortogonalny zbiór wektorów:

${\ Displaystyle \ mathbf {u} _ {1} = \ mathbf {v} _ {1} = {\ zacząć {bmacierz} 3 \ \ 1 \ koniec {bmacierz}}}$

${\ Displaystyle \ mathbf {u} _ {2} = \ mathbf {v} _ {2} - \ mathrm {projekt} _ {\ mathbf {u} _ {1}} (\ mathbf {v} _ {2} )={\begin{bmatrix}2\\2\end{bmatrix}}-\mathrm {proj} _{\left[{\begin{smallmatrix}3\\1\end{smallmatrix}}\right]}{ \begin{bmatrix}2\\2\end{bmatrix}}={\begin{bmatrix}2\\2\end{bmatrix}}-{\frac {8}{10}}{\begin{bmatrix}3 \\1\koniec{bmatrycy}}={\początek{bmatrycy}-2/5\\6/5\koniec{bmatrycy}}.}$

Sprawdzamy, czy wektory u ₁ i u ₂ są rzeczywiście ortogonalne:

${\ Displaystyle \ langle \ mathbf {u} _ {1} \ mathbf {u} _ {2} \ rangle = \ lewo \ langle {\ zacząć {bmatryca} 3 \ \ 1 \ koniec {bmacierz}} {\ begin{bmatrix}-2/5\\6/5\end{bmatrix}}\right\rangle =-{\frac {6}{5}}+{\frac {6}{5}}=0,}$

zauważając, że jeśli iloczyn skalarny dwóch wektorów wynosi 0, to są one ortogonalne.

W przypadku wektorów niezerowych możemy następnie znormalizować wektory, dzieląc ich rozmiary, jak pokazano powyżej:

${\ Displaystyle \ mathbf {e} _ {1} = {\ Frac {1} {\ sqrt {10}}} {\ zacząć {bmatrix} 3 \ \ 1 \ koniec {bmatrix}}}$

${\ Displaystyle \ mathbf {e} _ {2} = {\ Frac {1} {\ sqrt {40 \ ponad 25}}} {\ zacząć {bmatrix} -2/5 \ \ 6/5 \ koniec {bmatrix} }={\frac {1}{\sqrt {10}}}{\begin{bmatryca}-1\\3\end{bmatryca}}.}$

Nieruchomości

Oznacz przez wynik zastosowania procesu Grama-Schmidta do zbioru wektorów . Daje to mapę . ${\ Displaystyle \ operatorname {GS} (\ mathbf {v} _ {1}, \ kropki, \ mathbf {v} _ {k})}$${\ Displaystyle \ mathbf {v} _ {1} \ kropki \ mathbf {v} _ {k}}$${\ Displaystyle \ operatorname {GS} \ dwukropek (\ mathbf {R} ^ {n}) ^ {k} \ do (\ mathbf {R} ^ {n}) ^ {k}}$

Posiada następujące właściwości:

• Jest ciągły
• Jest to zachowanie orientacji w tym sensie, że .${\ Displaystyle \ nazwa operatora {lub} (\ mathbf {v} _ {1}, \ kropki, \ mathbf {v} _ {k}) = \ nazwa operatora {lub} (\ nazwa operatora {GS} (\ mathbf {v}) _{1},\kropki,\mathbf {v} _{k}))}$
• Dojeżdża z mapami ortogonalnymi:

Niech będzie ortogonalny (w odniesieniu do danego iloczynu skalarnego). Potem będzie ${\ Displaystyle g \ dwukropek \ mathbf {R} ^ {n} \ do \ mathbf {R} ^ {n}}$

${\ Displaystyle \ operatorname {GS} (g (\ mathbf {v} _ {1}), \ kropki, g (\ mathbf {v} _ {k})) = \ lewo (g (\ operator {GS}) ( \mathbf {v} _{1},\dots ,\mathbf {v} _{k})_{1}),\dots ,g(\operatorname {GS} (\mathbf {v} _{1}, \dots ,\mathbf {v} _{k})_{k})\right)}$

Dalej sparametryzowana wersja procesu Grama-Schmidta daje (silne) wycofanie odkształcenia ogólnej grupy liniowej na grupę ortogonalną . ${\ Displaystyle \ operatorname {GL} (\ mathbf {R} ^ {n})}$${\ Displaystyle O (\ mathbf {R} ^ {n})}$

Stabilność numeryczna

Gdy proces ten jest realizowany na komputerze, wektory często nie są całkowicie ortogonalne ze względu na błędy zaokrąglania . W przypadku opisanego powyżej procesu Grama-Schmidta (czasami określanego jako „klasyczny Gram-Schmidt”) ta utrata ortogonalności jest szczególnie zła; dlatego mówi się, że (klasyczny) proces Grama-Schmidta jest numerycznie niestabilny . ${\ Displaystyle \ mathbf {u} _ {k}}$

Proces Grama-Schmidta można ustabilizować przez niewielką modyfikację; ta wersja jest czasami określana jako zmodyfikowana Gram-Schmidt lub MGS. Takie podejście daje taki sam wynik jak oryginalna formuła w arytmetyce dokładnej i wprowadza mniejsze błędy w arytmetyce o skończonej precyzji. Zamiast obliczać wektor u _k as

${\ Displaystyle \ mathbf {u} _ {k} = \ mathbf {v} _ {k} - \ nazwa operatora {projekt} _ {\ mathbf {u} _ {1}} (\ mathbf {v} _ {k} )-\nazwa operatora {projekt} _{\mathbf {u} _{2}}(\mathbf {v} _{k})-\cdots -\nazwa operatora {projekt} _{\mathbf {u} _{k- 1}}(\mathbf {v} _{k}),}$

jest obliczany jako

${\ Displaystyle {\ zacząć {wyrównany} \ mathbf {u} _ {k} ^ {(1)} i = \ mathbf {v} _ {k} - \ operatorname {proj} _ {\ mathbf {u} _ { 1}}(\mathbf {v} _{k}),\\\mathbf {u} _{k}^{(2)}&=\mathbf {u} _{k}^{(1)}- \operatorname {proj} _{\mathbf {u} _{2}}\left(\mathbf {u} _{k}^{(1)}\right),\\&\;\;\vdots \\ \mathbf {u} _{k}^{(k-2)}&=\mathbf {u} _{k}^{(k-3)}-\operatorname {proj} _{\mathbf {u} _ {k-2}}\left(\mathbf {u} _{k}^{(k-3)}\right),\\\mathbf {u} _{k}^{(k-1)}& =\mathbf {u} _{k}^{(k-2)}-\operatorname {proj} _{\mathbf {u} _{k-1}}\left(\mathbf {u} _{k} ^{(k-2)}\right),\\\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}^{(k-1)}}{\po lewej \|\mathbf {u} _{k}^{(k-1)}\right\|}}\end{wyrównany}}}$

Ta metoda jest używana w poprzedniej animacji, gdy pośredni wektor v ' ₃ jest używany podczas ortogonalizacji niebieskiego wektora v ₃ .

Oto kolejny opis zmodyfikowanego algorytmu. Biorąc pod uwagę wektory , w pierwszym kroku tworzymy wektory usuwając składowe wzdłuż kierunku . W formułach . Po tym kroku mamy już dwa z naszych pożądanych wektorów ortogonalnych , a mianowicie , ale również stworzyliśmy ortogonalne do . Następnie ortogonalizujemy pozostałe wektory względem . Oznacza to, że obliczamy przez odejmowanie . Teraz zapisaliśmy wektory, w których pierwsze trzy wektory już są, a pozostałe wektory są już prostopadłe do . Jak powinno być teraz jasne, następny krok jest ortogonalizowany przeciwko . Postępując w ten sposób znajdujemy pełny zbiór wektorów ortogonalnych . Jeśli pożądane są wektory ortonormalne, to normalizujemy na bieżąco, tak aby mianowniki we wzorach odejmowania zamieniły się w jedynki. ${\displaystyle v_{1},v_{2},\kropki,v_{n}}$${\ Displaystyle v_ {1}, v_ {2} ^ {(1)}, \ kropki, v_ {n} ^ {(1)}}$${\displaystyle v_{1}}$${\ Displaystyle v_ {k} ^ {(1)}: = v_ {k} - {\ Frac {\ langle V_ {k}, v_ {1} \ rangle} {\ langle V_ {1}, V_ {1} \rangle }}v_{1}}$${\displaystyle u_{1},\kropki,u_{n}}$${\displaystyle u_{1}=v_{1},u_{2}=v_{2}^{(1)}}$${\ Displaystyle v_ {3}^ {(1)}, \ kropki, v_ {n} ^ {(1)}}$${\displaystyle u_{1}}$${\ Displaystyle u_ {2} = v_ {2} ^ {(1)}}$${\ Displaystyle v_ {3} ^ {(2)}, v_ {4} ^ {(2)}, \ kropki, v_ {n} ^ {(2)}}$${\ Displaystyle V_ {k} ^ {(2)}: = v_ {k} ^ {(1)} - {\ Frac {\ langle V_ {k} ^ {(1)}, u_ {2} \ rangle} {\langle u_{2},u_{2}\rangle }}u_{2}}$${\ Displaystyle v_ {1}, v_ {2} ^ {(1)}, v_ {3} ^ {(2)}, v_ {4} ^ {(2)}, \ kropki, v_ {n} ^ { (2)}}$${\displaystyle u_{1},u_{2},u_{3}}$${\displaystyle u_{1},u_{2}}$${\ Displaystyle v_ {4} ^ {(2)}, \ kropki, v_ {n} ^ {(2)}}$${\displaystyle u_{3}=v_{3}^{(2)}}$${\displaystyle u_{1},\kropki,u_{n}}$

Algorytm

Poniższy algorytm MATLAB implementuje ortonormalizację Grama-Schmidta dla wektorów euklidesowych. Wektory v ₁ , ..., v _k (kolumny macierzy Vtak, że V(:,j)jest j p wektor) otrzymują wektorów ortonormalnych (Kolumny U), które obejmują ten sam podprzestrzeni.

function [U]=gramschmidt(V)
[n,k] = size(V);
U = zeros(n,k);
U(:,1) = V(:,1)/norm(V(:,1));
for i = 2:k
    U(:,i)=V(:,i);
    for j=1:i-1
        U(:,i)=U(:,i)-(U(:,j)'*U(:,i)) 
               /(norm(U(:,j)))^2 * U(:,j);
    end
    U(:,i) = U(:,i)/norm(U(:,i));
end
end

Kosztem tego algorytmu jest asymptotycznie O( nk ² ) operacji zmiennoprzecinkowych, gdzie n jest wymiarowością wektorów ( Golub i Van Loan 1996 , §5.2.8).

Przez eliminację Gaussa

Jeśli wiersze { v ₁ , …, v _k } są zapisane jako macierz , to zastosowanie eliminacji Gaussa do rozszerzonej macierzy spowoduje powstanie ortogonalizowanych wektorów w miejsce . Jednak macierz musi zostać doprowadzona do postaci schodkowej rzędów , używając tylko operacji na wierszu polegającej na dodaniu wielokrotności skalarnej jednego wiersza do drugiego. Na przykład biorąc jak wyżej, mamy ${\ Displaystyle A}$${\ Displaystyle \ lewo [AA ^ {\ mathsf {T}} | A \ prawo]}$${\ Displaystyle A}$${\ Displaystyle AA ^ {\ mathsf {T}}}$${\ Displaystyle \ mathbf {v} _ {1} = {\ zacznij {bmatrix} 3 i 1 \ koniec {b macierzy}}, \ mathbf {v} _ {2} = {\ zacznij {bmatrix} 2 i 2 \ koniec {bmatrix}} }$

${\ Displaystyle \ lewo [AA ^ {\ mathsf {T}} | A \ prawo] = \ lewo [ {\ rozpocząć {tablica} {rr | rr} 10 i 8 i 3 i 1 \ \ 8 i 8 i 2 i 2 \ koniec {tablica}} \ prawej]}$

A sprowadzenie tego do postaci schodkowej rzędów daje

${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {rr | rr} 1 i 0,8 i 0,3 i 0,1 \ \ 0 i 1 i – 0,25 i 0,75 \ koniec {tablica}} \ prawej]}$

Znormalizowane wektory to

${\ Displaystyle \ mathbf {e} _ {1} = {\ Frac {1} {\ sqrt {0,3 ^ {2} + 0,1 ^ {2}}}} {\ zacząć {bmatrix} 0,3 i 0,1 \ end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3&1\end{bmatrix}}}$

${\ Displaystyle \ mathbf {e} _ {2} = {\ Frac {1} {\ sqrt {0,25 ^ {2} + 0,75 ^ {2}}}} {\ zacząć {bmatrix} - 0,25 i 0,75 \end{bmatrix}}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}-1&3\end{bmatrix}}.}$

jak w powyższym przykładzie.

Wzór determinujący

Wynik procesu Grama-Schmidta może być wyrażony w nierekurencyjnej formule z wyznacznikami .

${\ Displaystyle \ mathbf {e} _ {j} = {\ Frac {1} {\ sqrt {D_ {j-1} D_ {j}}}} {\ zacząć {vmatrix} \ langle \ mathbf {v} _ {1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2} \rangle &\langle \mathbf {v} _ {2},\mathbf {v} _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\ mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}}$

${\ Displaystyle \ mathbf {u} _ {j} = {\ Frac {1} {D_ {j-1}}} {\ zacząć {vmatrix} \ langle \ mathbf {v} _ {1} \ mathbf {v } _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf { v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2} \rangle &\langle \mathbf {v} _{2},\mathbf {v } _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1} \rangle \\\mathbf {v} _{1}&\mathbf {v} _{2} &\cdots &\mathbf {v} _{j}\end{vmatrix}}}$

gdzie D ₀ =1 oraz, dla j ≥ 1, D _j jest wyznacznikiem Grama

${\ Displaystyle D_ {j} = {\ zacząć {vmatrix} \ langle \ mathbf {v} _ {1} \ mathbf {v} _ {1} \ rangle i \ langle \ mathbf {v} _ {2}, \mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1 },\mathbf {v} _{2} \rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2} \rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j }\rangle \end{vmatrix}}.}$

Zauważ, że wyrażenie na u _k jest wyznacznikiem „formalnym”, tj. macierz zawiera zarówno skalary, jak i wektory; znaczenie tego wyrażenia jest zdefiniowane jako wynik ekspansji kofaktora wzdłuż rzędu wektorów.

Wyznacznik wzór Grama-Schmidta jest obliczeniowo wolniej (wykładniczo wolniej) niż algorytmy rekurencyjne opisane powyżej; ma to głównie znaczenie teoretyczne.

Alternatywy

Inne algorytmy ortogonalizacji używają transformacji Householder lub Givens rotacji . Algorytmy wykorzystujące transformacje Householder są bardziej stabilne niż stabilizowany proces Grama-Schmidta. Z drugiej strony, proces Grama-Schmidta wytwarza th ortogonalizowany wektor po iteracji, podczas gdy ortogonalizacja przy użyciu odbić Householdera wytwarza wszystkie wektory tylko na końcu. To sprawia, że ​​tylko proces Grama-Schmidta ma zastosowanie do metod iteracyjnych, takich jak iteracja Arnoldiego . ${\displaystyle j}$${\displaystyle j}$

Jeszcze inna alternatywa jest motywowana użyciem rozkładu Choleskiego do odwracania macierzy równań normalnych do liniowych najmniejszych kwadratów . Niech będzie pełną macierzą rang kolumn , której kolumny muszą być ortogonalizowane. Macierz jest hermitowska i dodatnio określona , więc można ją zapisać w oparciu o rozkład Choleskiego . Dolna macierz trójkątna ze ściśle dodatnimi wpisami diagonalnymi jest odwracalna . Wtedy kolumny macierzy są ortonormalne i obejmują tę samą podprzestrzeń, co kolumny macierzy pierwotnej . Jawne użycie produktu sprawia, że ​​algorytm jest niestabilny, zwłaszcza jeśli liczba warunków produktu jest duża. Niemniej jednak algorytm ten jest stosowany w praktyce i zaimplementowany w niektórych pakietach oprogramowania ze względu na jego wysoką wydajność i prostotę. ${\ Displaystyle V}$${\ Displaystyle V ^ {*} V}$${\ Displaystyle V ^ {*} V = LL ^ {*}}$${\ Displaystyle L}$${\ Displaystyle U = V \ lewo (L ^ {-1} \ po prawej) ^ {*}}$${\ Displaystyle V}$${\ Displaystyle V ^ {*} V}$

W mechanice kwantowej istnieje kilka schematów ortogonalizacji o cechach lepiej dostosowanych do niektórych zastosowań niż oryginalny Gram-Schmidt. Mimo to pozostaje popularnym i skutecznym algorytmem nawet największych obliczeń struktur elektronicznych.

Bibliografia

Źródła

• Bau III, Dawid; Trefethen, Lloyd N. (1997), Numeryczna algebra liniowa , Filadelfia: Towarzystwo Matematyki Przemysłowej i Stosowanej, ISBN 978-0-89871-361-9.
• Golub, Gene H .; Van Loan, Charles F. (1996), Obliczenia macierzy (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Greub, Werner (1975), Algebra Liniowa (wyd. 4), Springer.
• Soliverez, CE; Gagliano, E. (1985), "Ortonormalizacja na płaszczyźnie: podejście geometryczne" (PDF) , Mex. J. Fiz. , 31 (4): 743–758.

Zewnętrzne linki

• „Ortogonalizacja” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Harvey Mudd College Math Tutorial na temat algorytmu Grama-Schmidta
• Najwcześniejsze znane zastosowania niektórych słów matematyki: G Wpis „Ortogonalizacja Grama-Schmidta” zawiera pewne informacje i odniesienia do pochodzenia metody.
• Prezentacje: Proces Grama Schmidta w płaszczyźnie i proces Grama Schmidta w przestrzeni
• Aplet ortogonalizacji Grama-Schmidta
• Ortogonalizacja metodą NAG Grama-Schmidta n wektorów rzędu m rutyna
• Dowód: Raymond Puzio, Keenan Kidwell. „dowód algorytmu ortogonalizacji Grama-Schmidta” (wersja 8). PlanetMath.org.