Lanczos biortogonalisering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 augusti 2017; verifiering kräver 1 redigering .

Lanczos biortogonalisering - i linjär algebra , processen att konstruera ett par biortogonala baser för två Krylov-delrum

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

och

${\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 föreslogs av den ungerske fysikern och matematikern Cornelius Lanczos och är en förlängning av Lanczos ortogonaliseringsförfarande till fallet där matrisen inte är symmetrisk . $A$

Teoretisk belägg för metoden

Definition. System av vektorer och kallas biortogonala if ${\displaystyle \{x_{i}\}_{i=1}^{m))$ ${\displaystyle \{y_{i}\}_{i=1}^{m))$ $\forall i\neq j\;(x_{i},y_{j})=0.$

Teorem .
Låt vektorernaochsådana attoch låt vektorsystemenochdefinieras av relationerna:

v_{1}

w_{1}

(v_{1},w_{1})\nev 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

Sedan

System och är biortogonala. ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$
Vart och ett av systemen och är linjärt oberoende och utgör en grund i resp . ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$ $K_{m}(v_{1},A)$ $K_{m}(w_{1},A^{T})$

Bevis

Det första påståendet av satsen bevisas av metoden för matematisk induktion .

Faktum är att paret av vektorer och uppfyller biortogonalitetsvillkoret. $v_{1}$ $w_{1}$

Låt oss nu anta att de biortogonala uppsättningarna och redan har konstruerats , och då kommer vi att visa att för vektorn som definieras av 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=\överlinje {1,i}.$

Multiplicera uttrycket 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}).

Om sedan, genom induktionshypotesen, den sista skalära produkten försvinner och $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.

Om då $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}).

Enligt induktionshypotesen försvinner alla fyra skalära produkter; för alla skalära produkter i den andra och tredje termen är lika med noll, och sedan $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å liknande sätt är det bevisat att för $(v_{k},w_{i+1})=0$ $k={\overline {1,i)).$

För att bevisa det andra påståendet i satsen noterar vi att det följer direkt av det.Det återstår bara att visa vektorernas linjära oberoende $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ärtom att det finns koefficienter för vilka

\gamma _{k},

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

Att sammanställa skalära produkter med vektorer får vi $w_{k},k={\overline {1,i)),$

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

och eftersom, genom den tidigare bevisade biortogonaliteten , måste alla koefficienter vara noll. Liknande argument för att komplettera beviset för satsen. $(v_{k},w_{k})\nev 0,$ $\gamma _{k}$ ${\displaystyle w_{1},...,w_{m))$

Kommentar. Den största nackdelen med Lanczos biortogonalisering är möjligheten till en situation där fortsättningen av processen i detta fall blir omöjlig på grund av koefficientens osäkerhet $(v_{i},w_{i})=0;$ $\beta _{i+1}.$

Lanczos biortogonaliseringsalgoritm

Vi väljer två vektorer så att $v_{1},\ w_{1}$ $(v_{1},w_{1})=1.$
Vi tror $\beta _{1}=\delta _{1}\equiv 0,\ w_{0}=v_{0}\equiv 0$
För att göra: $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}$ . Om då STOPP $\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}$
Cykelns slut av . $j$

Länkar

Metoder för att lösa högdimensionella SLAE: Handledning