Gram-Schmidtův proces

Gram - Schmidtův proces transformuje sekvenci lineárně nezávislých vektorů na ortonormální systém vektorů a to takovým způsobem, že každý vektor je lineární kombinací vektorů . ${\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{n))$ ${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$ $\mathbf{e}_j$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Klasický Gram-Schmidtův proces

Algoritmus

Nechť jsou lineárně nezávislé vektory a nechť je operátor projekce vektoru na vektor definovaný jako ${\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{n))$ $\mathbf {proj} _{\mathbf {b} }\,\mathbf {a}$ ${\mathbf {a}}$ ${\mathbf {b}}$

{\mathbf {proj}}_{{{\mathbf {b}}}}\,{\mathbf {a}}={\langle {\mathbf {a}},{\mathbf {b}}\rangle \ přes \langle {\mathbf {b)),{\mathbf {b}}\rangle }{\mathbf {b)),

kde je skalární součin vektorů a . $\langle {\mathbf {a}},{\mathbf {b}}\rangle$ ${\mathbf {a}}$ ${\mathbf {b}}$

Klasický Gram-Schmidtův proces se provádí následovně:

{\begin{array}{lclr}\mathbf {b} _{1}&=&\mathbf {a} _{1}&(1)\\\mathbf {b} _{2}&= &\mathbf {a} _{2}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{2}&(2)\\\mathbf {b} _{3}&=&\mathbf {a} _{3}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{3}-\mathbf {proj } _{\mathbf {b} _{2}}\,\mathbf {a} _{3}&(3)\\&\tečky &&\\\mathbf {b} _{n}&=&\mathbf {a} _{n}-\mathbf {proj} _{\mathbf {b} _{1}}\,\mathbf {a} _{n}-\mathbf {proj} _{\mathbf {b} _ {2}}\,\mathbf {a} _{n}-\tečky -\mathbf {proj} _{\mathbf {b} _{n-1}}\,\mathbf {a} _{n}& (n)\end{array}}

Na základě každého vektoru lze získat normalizovaný vektor jednotkové délky , definovaný jako $\mathbf {b} _{j}\;(j=1\ldots n)$ $\mathbf{e}_j$

{\mathbf {e}}_{j}={{\mathbf {b}}_{j} \over \|{\mathbf {b}}_{j}\|}

Výsledky Gram-Schmidtova procesu:

${\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{n))$ je soustava ortogonálních vektorů popř

${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$ je systém ortonormálních vektorů.

Výpočet se nazývá Gram-Schmidtova ortogonalizace a Gram-Schmidtova ortonormalizace. ${\displaystyle \mathbf {b} _{1},\;\ldots ,\;\mathbf {b} _{n))$ ${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e} _{n))$

Geometrická interpretace

Zvažte vzorec (2), druhý krok algoritmu. Jeho geometrické znázornění je na Obr. jeden:

získání projekce vektoru na ; ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$
výpočet , tedy kolmice , která se promítá na . Tato kolmice je vektor vypočítaný ve vzorci (2) ; ${\mathbf {a}}_{2}-{\mathbf {proj}}_{({\mathbf {b}}_{1}}}{\mathbf {a}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
přesunutí vektoru získaného v kroku 2 do počátku. Tento pohyb je na obrázku proveden pouze pro názornost; ${\mathbf {b}}_{2}$

Obrázek ukazuje, že vektor je ortogonální k vektoru , protože je to kolmice, na kterou se promítá . ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {a}}_{2}$ ${\mathbf {b}}_{1}$

Zvažte vzorec (3), třetí krok algoritmu, v následující verzi:

{\begin{array}{lcr}{\mathbf {b}}_{3}={\mathbf {a}}_{3}-({\mathbf {proj}}_{{{\mathbf {b} }_{1))}{\mathbf {a}}_{3}+{\mathbf {proj}}_{({\mathbf {b}}_{2}}}{\mathbf {a}}_ {3})&&(6)\\\end{pole}}

Jeho geometrické znázornění je na Obr. 2:

získání projekce vektoru na ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$
získání projekce vektoru na ; ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{2}$
výpočet součtu , tedy promítání vektoru do roviny tvořené vektory a . Tato rovina je na obrázku vystínována šedě; ${\mathbf {proj}}_{{{\mathbf {b}}_{1}}}{\mathbf {a}}_{3}+{\mathbf {proj}}_{{{\mathbf {b }}_{2}}}{\mathbf {a}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$
výpočet , tedy kolmice, která se promítá do roviny tvořené vektory a . Tato kolmice je vektor vypočítaný ve vzorci (6) ; ${\mathbf {a}}_{3}-({\mathbf {proj}}_{({\mathbf {b}}_{1}}}{\mathbf {a}}_{3}+{\ mathbf {proj}}_{{{\mathbf {b}}_{2}}}{\mathbf {a}}_{3})$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{3}$
stěhování přijaté k původu. Tento pohyb je na obrázku proveden pouze pro názornost. Nejedná se o matematickou operaci, a proto se neodráží ve vzorci (6). ${\mathbf {b}}_{3}$

Obrázek ukazuje, že vektor je ortogonální k vektorům a , protože je to kolmice, podél které se promítá do roviny tvořené vektory a . ${\mathbf {b}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$ ${\mathbf {b}}_{3}$ ${\mathbf {a}}_{3}$ ${\mathbf {b}}_{1}$ ${\mathbf {b}}_{2}$

V Gram-Schmidtově procesu se tedy projekce provádí ortogonálně na nadrovinu překlenutou vektory . Vektor se pak vypočítá jako rozdíl mezi a jeho projekcí. To znamená , že je to kolmice od k nadrovině překlenutá vektory . Proto je ortogonální k vektorům tvořícím tuto nadrovinu. ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{{j-1}}$ ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{j}$ ${\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{{j-1}}$ ${\mathbf {b}}_{j}$

Zvláštní příležitosti

Gram-Schmidtův proces lze také aplikovat na nekonečnou sekvenci lineárně nezávislých vektorů.

Kromě toho lze Gram-Schmidtův proces aplikovat na lineárně závislé vektory. V tomto případě vytváří (nulový vektor) v kroku , pokud se jedná o lineární kombinaci vektorů . Aby se zachovala ortogonalita výstupních vektorů a aby se zabránilo dělení nulou během ortogonalizace, musí algoritmus vyřadit nulové vektory. Počet vektorů vytvořených algoritmem se bude rovnat rozměru podprostoru generovaného vektory (tj. počtu lineárně nezávislých vektorů, které lze odlišit od původních vektorů). $\mathbf {0}$ $j$ ${\mathbf {a}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{{j-1}}$

Vlastnosti

Přechodová matice z do je horní trojúhelníková matice . ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$ ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$

Součin délek se rovná objemu rovnoběžnostěnu postaveného na vektorech soustavy jako na hranách. ${\mathbf {b}}_{1},\;\ldots ,\;{\mathbf {b}}_{j}$ ${\mathbf {a}}_{1},\;\ldots ,\;{\mathbf {a}}_{j}$

Gram-Schmidtův proces pro sloupcové vektory matice z určuje ekvivalenci homotopie . $GL(n)$ $GL(n)\to O(n)$

Další výklady

Gram-Schmidtův proces lze interpretovat jako rozklad nedegenerované čtvercové matice na součin ortogonální (nebo unitární v případě hermitovského prostoru ) a horní trojúhelníkové matice s kladnými diagonálními prvky, QR rozklad , což je zvláštní případ rozkladu Iwasawa .

Literatura

Beklemishev DV Kurz analytické geometrie a lineární algebry. — M .: Nauka .

Odkazy

https://www.youtube.com/watch?v=GhhpG1tCQLU Animace procesu v letadle