Rayleighova kvocientová iterace - Rayleigh quotient iteration

Rayleighova kvocientová iterace je algoritmus vlastních čísel což rozšiřuje myšlenku inverzní iterace pomocí Rayleighův kvocient získat stále přesnější vlastní číslo odhady.

Rayleighova kvocientová iterace je iterační metoda, to znamená, že poskytuje sled přibližných řešení, která konverguje ke skutečnému řešení v limitu. Je zaručena velmi rychlá konvergence a pro získání přiměřené aproximace není v praxi zapotřebí více než několik iterací. Rayleighův kvocient iterační algoritmus kubicky konverguje pro hermitovské nebo symetrické matice, daný počáteční vektor, který je dostatečně blízko k vlastní vektor z matice to je analyzováno.

Algoritmus

Algoritmus je velmi podobný inverzní iteraci, ale nahradí odhadovanou vlastní hodnotu na konci každé iterace Rayleighovým kvocientem. Začněte výběrem nějaké hodnoty ${ displaystyle mu _ {0}}$ jako počáteční odhad vlastního čísla pro hermitovskou matici ${ displaystyle A}$. Počáteční vektor ${ displaystyle b_ {0}}$ musí být také dodáno jako počáteční odhad vlastního vektoru.

Vypočítejte další aproximaci vlastního vektoru ${ displaystyle b_ {i + 1}}$ podle

${ displaystyle b_ {i + 1} = { frac {(A- mu _ {i} I) ^ {- 1} b_ {i}} { | (A- mu _ {i} I) ^ {-1} b_ {i} |}},}$
kde ${ displaystyle I}$ je matice identity a nastaví další aproximaci vlastního čísla na Rayleighův kvocient aktuální iterace rovný
${ displaystyle mu _ {i + 1} = { frac {b_ {i + 1} ^ {*} Ab_ {i + 1}} {b_ {i + 1} ^ {*} b_ {i + 1} }}.}$

Pro výpočet více než jedné vlastní hodnoty lze algoritmus kombinovat s deflační technikou.

U velmi malých problémů je výhodné vyměnit inverzní matice s doplnit, který přinese stejnou iteraci, protože se rovná inverzní až do irelevantní stupnice (konkrétně inverzní k determinantu). Adjugát je snazší vypočítat explicitně než inverzní (i když je inverzní snazší použít na vektor pro problémy, které nejsou malé), a je numericky zřetelnější, protože zůstává dobře definovaný jako konvergující vlastní hodnota.

Příklad

Zvažte matici

${ displaystyle A = left [{ begin {matrix} 1 & 2 & 3 1 & 2 & 1 3 & 2 & 1 end {matrix}} right]}$

pro které jsou přesná vlastní čísla ${ displaystyle lambda _ {1} = 3 + { sqrt {5}}}$, ${ displaystyle lambda _ {2} = 3 - { sqrt {5}}}$ a ${ displaystyle lambda _ {3} = - 2}$, s odpovídajícími vlastními vektory

${ displaystyle v_ {1} = left [{ begin {matrix} 1 varphi -1 1 end {matrix}} right]}$, ${ displaystyle v_ {2} = left [{ begin {matrix} 1 - varphi 1 end {matrix}} right]}$ a ${ displaystyle v_ {3} = doleva [{ začátek {matice} 1 0 1 konec {matice}} doprava]}$.

(kde ${ displaystyle textstyle varphi = { frac {1 + { sqrt {5}}} {2}}}$ je zlatý řez).

Největší vlastní hodnota je ${ displaystyle lambda _ {1} přibližně 5 236}}$ a odpovídá libovolnému vlastnímu vektoru úměrnému ${ displaystyle v_ {1} přibližně vlevo [{ začátek {matice} 1 0,6180 1 konec {matice}} vpravo].}$

Začínáme s počátečním odhadem vlastního čísla

${ displaystyle b_ {0} = left [{ begin {matrix} 1 1 1 end {matrix}} right], ~ mu _ {0} = 200}$.

Poté se získá první iterace

${ displaystyle b_ {1} přibližně doleva [{ začátek {matice} -0,57927 - 0,57348 - 0,57927 konec {matice}} doprava], ~ mu _ {1} přibližně 5,3355 }$

druhá iterace,

${ displaystyle b_ {2} přibližně doleva [{ začátek {matice} 0,64676 0,40422 0,64676 konec {matice}} doprava], ~ mu _ {2} přibližně 5,2418}$

a třetí,

${ displaystyle b_ {3} přibližně doleva [{ začátek {matice} -0,64793 - 0,44545 - 0,64793 konec {matice}} vpravo], ~ mu _ {3} přibližně 5,2361 }$

ze kterého je patrná kubická konvergence.

Implementace oktávy

Následuje jednoduchá implementace algoritmu v Oktáva.

funkceX =rayleigh(A, epsilon, mu, x)X = X / norma(X);  % operátor zpětného lomítka v Octave řeší lineární systém  y = (A - mu * oko(řádky(A))) \ X;   lambda = y' * X;  mu = mu + 1 / lambda  chybovat = norma(y - lambda * X) / norma(y)  zatímco err> epsilon    X = y / norma(y);    y = (A - mu * oko(řádky(A))) \ X;    lambda = y' * X;    mu = mu + 1 / lambda    chybovat = norma(y - lambda * X) / norma(y)  koneckonec

Viz také

• Iterace výkonu
• Inverzní iterace

Reference

• Lloyd N. Trefethen a David Bau, III, Numerická lineární algebra, Společnost pro průmyslovou a aplikovanou matematiku, 1997. ISBN  0-89871-361-7.
• Rainer Kress, "Numerická analýza", Springer, 1991. ISBN  0-387-98408-9