Wikipedie

Gramova–Schmidtova ortogonalizace: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Čebyšev byl Rus, takže normální transkripce azbuky; mezijazykové odkazy
přeformulace úvodu bez zbytečného pojmenování parametrů, jazyková oprava
Řádek 1:
{{Upravit}}
'''Gramův-Schmidtův proces''' neboli '''Gramova-Schmidtova ortogonalizace''' (nesprávně<ref>{{Citace elektronické monografie
 
| titul = Internetová jazyková příručka
Gram-Schmidtův proces (algoritmus), případně Gramova-Schmidtova ortogonalizace je teoretická i výpočetní metoda k nalezení [[Ortonormální báze|ortonormální báze]] podprostoru <math>\mathrm{span}\{v_1,\ldots,v_n\}</math> nějakého prostoru <math>\mathcal{V}</math> se [[Skalární součin|skalárním součinem]]; <math>v_1,\ldots,v_n\in\mathcal{V}</math>.
| url = http://prirucka.ujc.cas.cz/?id=400#nadpis1
| datum vydání =
| datum aktualizace =
| datum přístupu = 2011-10-31
| vydavatel = Ústav pro jazyk český Akademie věd ČR
}}</ref> ''Gram-Schmidtova ortogonalizace'') je metoda, která v daném [[unitární prostor|unitárním prostoru]] (neboli [[vektorový prostor|vektorovém prostoru]] se [[skalární součin|skalárním součinem]]) umožňuje pro zadanou [[konečná množina|konečnou množinu]] [[vektor]]ů nalézt [[Ortonormální báze|ortonormální bázi]] [[podprostor]]u jimi generovaného.
 
== Algoritmus ==
 
Uvažujme pro jednoduchost <math>\mathbb{R}^m</math> reálný linerární vektorový prostor sloupcových vektorů o <math>m</math> složkách (se standardním skalarnímskalárním součinem). Nechť <math>a_1,\ldots,a_n\in\mathbb{R}^m</math> jsou, opět pro jednoduchost, lineárně nezávislé, tedy <math>n\leq m</math>. Úkolem je nalézt ortonormální bázi <math>q_1,\ldots,q_n</math> <math>n</math>-rozměrného podprostoru <math>\mathbb{R}^m</math>, který vektory <math>a_i</math> generují; má tedy platit
 
:<math>\mathrm{span}\{a_1,\ldots,a_n\}=\mathrm{span}\{q_1,\ldots,q_n\},\qquad \langle q_k,q_j\rangle=q_j^Tq_k = \delta_{k,j}</math>
Řádek 50 ⟶ 56:
:13: '''end'''
 
Tato varianta algoritmu se nazývá '''klasický GramGramův-Schmidtův algoritmus (CGS)''' a je novější než varianta původní, dnes zvaná '''modifikovaný GramGramův-Schmidtův algoritmus (MGS)'''. MGS získáme z výše popsaného CGS prostým vypuštěním řádků 07 a 08, tedy, spojením obou vnitřních cyklů.
 
=== Varianty algoritmu a jejich chování ===
Řádek 66 ⟶ 72:
První projekce odpovídá výpočtu pomocí CGS, druhá postupná výpočtu pomocí MGS. Je zřejmé že CGS ortogonalizace (projekce) se počítá paralelně do všech směrů najednou, kdežto sekvenční ortogonalizace (projekce) MGS umožňuje v <math>j</math>-tém kroku částečně eliminovat chyby vzniklé zaokrouhlováním v předchozích krocích <math>(j-1),\ldots,2,1</math>.
 
Řešením v praxi používaným bývá tzv. '''klasický GramGramův-Schmidtův algoritmus s iteračním zpřesněním (ICGS)''', který obsahuje dvě vnitřní smyčky jako CGS (je tedy paralelizovatelný), ale obě smyčky se provedou dvakrát (čímž se výrazně zlepší numerické vlastnosti, ztráta ortogonality mezi vektory <math>q_i</math> je pak dokonce menšní než u MGS).
 
=== Vztah GramGramova-Schmidtova algoritmu a QR rozkladu ===
 
Srovnáním sloupcových vektorů <math>a_k,\;q_j</math> a koeficientů <math>r_{j,k}</math> do matic,
Řádek 82 ⟶ 88:
== Ortogonální polynomy ==
 
GramGramův-Schmidtův algoritmus lze aplikovat na prvky libovolného prostoru se skalánímskalárním součinem. Uvažujeme například prostor polynomů <math>\mathcal{P}(a,b)</math> se skalárním součinem
 
:<math>\langle p(x),q(x)\rangle_w = \int_a^b p(x)q(x)w(x)dx</math>,
 
kde <math>w(x)</math> je nějaká váhová funkce. Aplike GramGramova-Schmidtova algoritmus na sadu vektorů (polynomů) <math>1,x,x^2,\ldots,x^{n-1}</math> (v tomto pořadí) dostáváme, pro vhodně volené <math>a,\,b</math> a váhovou funkci <math>w(x)</math> libovolnou sadu [[Ortogonální polynomy|ortogonálních polynomů]] (normalizovanou vzhledem k normě indukované daným skalárním součinem).
 
Pro <math>a=-1,\,b=1,\,w(x)=1</math> GramGramův-Schmidtův algoritmus generuje [[Legenderovy polynomy]],
pro <math>a=-1,\,b=1,\,w(x)=(1-x^2)^{-1/2}</math> dostaneme [[Čebyševovy polynomy]] prvního druhu,
atd.
 
== Reference ==
<references/>
 
[[Kategorie:Lineární algebra]]
Citováno z „https://cs.wikipedia.org/wiki/Gramova–Schmidtova_ortogonalizace“