Biortogonalizarea Lanczos

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 25 august 2017; verificarea necesită 1 editare .

Biortogonalizarea Lanczos - în algebra liniară , procesul de construire a unei perechi de baze biortogonale pentru două subspații Krylov

${\mathcal {K}}_{m}(v_{1},A)=span\{v_{1},Av_{1},A^{2}v_{1},..., A^{m-1}v_{1}\}$

și

${\mathcal {K}}_{m}(w_{1},A^{T})=span\{w_{1},A^{T}w_{1},(A^{T} })^{2}w_{1},...,(A^{T})^{m-1}w_{1}\}.$

Metoda a fost propusă de fizicianul și matematicianul maghiar Cornelius Lanczos și este o extensie a procedurii de ortogonalizare Lanczos în cazul în care matricea nu este simetrică . $A$

Fundamentarea teoretică a metodei

Definiție. Sistemele de vectori și se numesc biortogonale dacă $\{x_{i}\}_{i=1}^{m)$ ${\displaystyle \{y_{i}\}_{i=1}^{m))$ $\forall i\neq j\;(x_{i},y_{j})=0.$

Teorema .
Fie vectoriișiastfel încâtși sistemele de vectorișisă fie definite de relațiile:

v_{1}

w_{1}

(v_{1},w_{1})\neq 0

\{v_{i}\}_{i=1}^{m)

\{w_{i}\}_{i=1}^{m)

v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},\v_{0}=0;

w_{i+1}=A^{T}w_{i}-\alpha _{i}w_{i}-\beta _{i}w_{i-1},\w_{0}= 0;

\alpha _{i}={\frac {(Av_{i},w_{i})}{(v_{i},w_{i})))

\beta _{i}={\frac {(v_{i},w_{i})}{(v_{i-1},w_{i-1}))),\beta _{1 }=0

Apoi

Sisteme și sunt biortogonale. $\{v_{i}\}_{i=1}^{m)$ $\{w_{i}\}_{i=1}^{m)$
Fiecare dintre sisteme și este liniar independent și formează o bază în și respectiv. $\{v_{i}\}_{i=1}^{m)$ $\{w_{i}\}_{i=1}^{m)$ $K_{m}(v_{1},A)$ $K_{m}(w_{1},A^{T})$

Dovada

Prima afirmație a teoremei este demonstrată prin metoda inducției matematice .

Într-adevăr, perechea de vectori și satisface condiția de biortogonalitate. $v_{1}$ $w_{1}$

Să presupunem acum că mulțimile biortogonale și au fost deja construite și apoi vom arăta că pentru vectorul definit de relație, avem ${\mathcal {f}}v_{1},...,v_{i}{\mathcal {g}}$ ${\mathcal {f}}w_{1},...,w_{i}{\mathcal {g}}$ $v_{{i+1}}$ $v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$ $(v_{{i+1}},w_{k})=0,k=\overline {1,i}.$

Înmulțiți scalar expresia cu $v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$ $w_{k)$

(v_{i+1},w_{k})=(Av_{i},w_{k})-\alpha _{i}(v_{i},w_{k})-\beta _ {i}(v_{i-1},w_{k}).

Dacă atunci, prin ipoteza de inducție, ultimul produs scalar dispare și $k=i,$

(v_{i+1},w_{i})=(Av_{i},w_{i})-\alpha _{i}(v_{i},w_{i})=(Av_{ i},w_{i})-{\frac {(Av_{i},w_{i})}{(v_{i},w_{i})}}(v_{i},w_{i}) =0.

Dacă atunci $k<i,$

(v_{i+1},w_{k})=(v_{i},A^{T}w_{k})-\beta _{i}(v_{i-1},w_{ k})=(v_{i},w_{k+1}+\alpha _{k}w_{k}+\beta _{k}w_{k-1})-\beta _{i}(v_ {i-1},w_{k})=

=~(v_{i},w_{{k+1}})+\alpha _{k}(v_{i},w_{k})+\beta _{k}(v_{i},w_{ {k-1}})-\beta _{i}(v_{{i-1}},w_{k}).

Prin ipoteza de inducție, pentru toate cele patru produse scalare dispar; pentru toate produsele scalare din al doilea și al treilea termeni sunt egale cu zero și apoi $k<i-1$ $k=i-1$

(v_{{i+1}},w_{{i-1}})=(v_{i},w_{i})-\beta _{i}(v_{{i-1}},w_{ {i-1}})=(v_{i},w_{i})-{\frac {(v_{i},w_{i})}{(v_{{i-1}},w_{{ i-1}})}}(v_{{i-1}},w_{{i-1}})=0

În mod similar, se demonstrează că pt $(v_{k},w_{i+1})=0$ $k={\overline {1,i)).$

Pentru a demonstra a doua afirmaţie a teoremei , observăm că ea decurge direct din ea . Rămâne doar să arătăm independenţa liniară a vectorilor. $v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},v_{0}=0$ $span{\mathcal {f}}v_{1},v_{2},...v_{m}{\mathcal {g}}=K_{m}(v_{1},A).$ $v_{1},...,v_{m}.$

Să presupunem dimpotrivă că există coeficienți pentru care

\gamma _{k},

\gamma _{1}v_{1}+\gamma _{2}v_{2}+...+\gamma _{m}v_{m}=0.

Compilând produse scalare cu vectori, obținem $w_{k},k={\overline {1,i)),$

\gamma _{k}(v_{k},w_{k})=0,k={\overline {1,i)),

și deoarece, prin biortogonalitatea demonstrată anterior , toți coeficienții trebuie să fie zero. Argumente similare pentru completarea demonstrației teoremei. $(v_{k},w_{k})\neq 0,$ $\gamma _{k}$ $w_{1},...,w_{m)$

Cometariu. Principalul dezavantaj al biortogonalizării Lanczos este posibilitatea unei situații în care, în acest caz, continuarea procesului devine imposibilă din cauza incertitudinii coeficientului $(v_{i},w_{i})=0;$ $\beta _{i+1}.$

Algoritmul de biortogonalizare Lanczos

Alegem doi vectori astfel încât $v_{1},\w_{1}$ $(v_{1},w_{1})=1.$
Noi credem $\beta _{1}=\delta _{1}\equiv 0,\ w_{0}=v_{0}\equiv 0$
Pentru a face: $j=1,2,...,m$
$\alpha _{j}=(Av_{j},w_{j})$
${\hat {v}}_{j+1}=Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}$
${\hat {w}}_{j+1}=A^{T}w_{j}-\alpha _{j}w_{j}-\delta _{j}w_{j-1}$
$\delta _{j+1}={\mathcal {j}}({\hat {v}}_{j+1}, {\hat {w}}_{j+1}){\ matematic {j}}^{1/2}$ . Dacă atunci STOP $\delta _{j+1}=0,$
$\beta _{j+1}=({\hat {v}}_{j+1}, {\hat {w}}_{j+1})/\delta _{j+1}$
$v_{j+1}={\hat {v}}_{j+1}/\delta _{j+1}$
$w_{j+1}={\hat {w}}_{j+1}/\beta _{j+1}$
Sfârșitul ciclului până la . $j$

Link -uri

Metode de rezolvare a SLAE de dimensiuni mari: Tutorial