Lanczos biortogonalisering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. august 2017; verifikation kræver 1 redigering .

Lanczos biortogonalisering - i lineær algebra , processen med at konstruere et par biortogonale baser for to Krylov underrum

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

${\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}\}.$

Metoden blev foreslået af den ungarske fysiker og matematiker Cornelius Lanczos og er en udvidelse af Lanczos ortogonaliseringsprocedure til det tilfælde, hvor matricen ikke er symmetrisk . $EN$

Teoretisk underbygning af metoden

Definition. Systemer af vektorer og kaldes biortogonale hvis ${\displaystyle \{x_{i}\}_{i=1}^{m))$ ${\displaystyle \{y_{i}\}_{i=1}^{m))$ $\forall i\neq j\;(x_{i},y_{j})=0.$

Sætning .
Lad vektorerneogsådan, atog lad systemerne af vektorerogvære defineret af relationerne:

v_{1}

w_{1}

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

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

{\displaystyle \{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

Derefter

Systemer og er biortogonale. ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$
Hvert af systemerne og er lineært uafhængige og danner grundlag i hhv . ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$ $K_{m}(v_{1},A)$ $K_{m}(w_{1},A^{T})$

Bevis

Den første påstand om sætningen er bevist ved metoden til matematisk induktion .

Faktisk, parret af vektorer og opfylder biortogonalitet betingelse. $v_{1}$ $w_{1}$

Lad os nu antage, at de biortogonale sæt og allerede er blevet konstrueret , og så vil vi vise, at for vektoren defineret af relationen, har vi ${\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}.$

Gang udtrykket skalært med $v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$ ${\displaystyle w_{k))$

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

Hvis så, ved induktionshypotesen, det sidste skalarprodukt forsvinder og $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.

Hvis da $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}).

Ved induktionshypotesen forsvinder alle fire skalarprodukter; for alle skalære produkter i andet og tredje led er lig med nul, og derefter $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

På lignende måde er det bevist, at for $(v_{k},w_{i+1})=0$ $k={\overline {1,i)).$

For at bevise den anden påstand af sætningen bemærker vi, at den følger direkte af den . Det er kun tilbage at vise vektorernes lineære uafhængighed $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}.$

Antag tværtimod, at der er koefficienter for hvilke

\gamma _{k},

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

At kompilere skalarprodukter med vektorer, får vi $w_{k},k={\overline {1,i)),$

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

og da, ved den tidligere beviste biortogonalitet , skal alle koefficienter være nul. Lignende argumenter for at fuldføre beviset for sætningen. $(v_{k},w_{k})\neq 0,$ $\gamma _{k}$ ${\displaystyle w_{1},...,w_{m))$

Kommentar. Den største ulempe ved Lanczos biortogonalisering er muligheden for en situation , hvor fortsættelsen af processen i dette tilfælde bliver umulig på grund af koefficientens usikkerhed $(v_{i},w_{i})=0;$ $\beta _{i+1}.$

Lanczos biortogonaliseringsalgoritme

Vi vælger to vektorer så $v_{1},\ w_{1}$ $(v_{1},w_{1})=1.$
Vi tror $\beta _{1}=\delta _{1}\equiv 0,\ w_{0}=v_{0}\equiv 0$
For gør: $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}){\ mathcal {j}}^{1/2}$ . Hvis så 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}$
Slut på cyklus kl . $j$

Lanczos biortogonalisering

Teoretisk underbygning af metoden

Lanczos biortogonaliseringsalgoritme

Links