Биортогонализация Ланцоша


Биортогонализация Ланцоша — в линейной алгебре процесс построения пары биортогональных базисов для двух подпространств Крылова

K m ( v 1 , A ) = s p a n { v 1 , A v 1 , A 2 v 1 , . . . , A m − 1 v 1 } {displaystyle {mathcal {K}}_{m}(v_{1},A)=span{v_{1},Av_{1},A^{2}v_{1},...,A^{m-1}v_{1}}}

и

K m ( w 1 , A T ) = s p a n { w 1 , A T w 1 , ( A T ) 2 w 1 , . . . , ( A T ) m − 1 w 1 } . {displaystyle {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}}.}

Метод был предложен венгерским физиком и математиком Корнелием Ланцошем и является расширением процедуры ортогонализации Ланцоша на случай, когда матрица A {displaystyle A} несимметрична.

Теоретическое обоснование метода

Определение. Системы векторов { x i } i = 1 m {displaystyle {x_{i}}_{i=1}^{m}} и { y i } i = 1 m {displaystyle {y_{i}}_{i=1}^{m}} называются биортогональными, если ∀ i ≠ j ( x i , y j ) = 0. {displaystyle forall i eq j;(x_{i},y_{j})=0.}

Доказательство

Первое утверждение теоремы доказывается методом математической индукции.

Действительно, пара векторов v 1 {displaystyle v_{1}} и w 1 {displaystyle w_{1}} удовлетворяет условию биортогональности.

Предположим теперь, что уже построены биортогональные наборы f v 1 , . . . , v i g {displaystyle {mathcal {f}}v_{1},...,v_{i}{mathcal {g}}} и f w 1 , . . . , w i g {displaystyle {mathcal {f}}w_{1},...,w_{i}{mathcal {g}}} , и далее покажем, что для вектора v i + 1 {displaystyle v_{i+1}} , определяемого соотношением v i + 1 = A v i − α i v i − β i v i − 1 , {displaystyle v_{i+1}=Av_{i}-alpha _{i}v_{i}-eta _{i}v_{i-1},} имеет место ( v i + 1 , w k ) = 0 , k = 1 , i ¯ . {displaystyle (v_{i+1},w_{k})=0,k={overline {1,i}}.}

Умножим выражение v i + 1 = A v i − α i v i − β i v i − 1 , {displaystyle v_{i+1}=Av_{i}-alpha _{i}v_{i}-eta _{i}v_{i-1},} скалярно на w k {displaystyle w_{k}}

( v i + 1 , w k ) = ( A v i , w k ) − α i ( v i , w k ) − β i ( v i − 1 , w k ) . {displaystyle (v_{i+1},w_{k})=(Av_{i},w_{k})-alpha _{i}(v_{i},w_{k})-eta _{i}(v_{i-1},w_{k}).}

Если k = i , {displaystyle k=i,} то по предположению индукции последнее скалярное произведение обращается в ноль и

( v i + 1 , w i ) = ( A v i , w i ) − α i ( v i , w i ) = ( A v i , w i ) − ( A v i , w i ) ( v i , w i ) ( v i , w i ) = 0. {displaystyle (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.}

Если же k < i , {displaystyle k<i,} то

( v i + 1 , w k ) = ( v i , A T w k ) − β i ( v i − 1 , w k ) = ( v i , w k + 1 + α k w k + β k w k − 1 ) − β i ( v i − 1 , w k ) = {displaystyle (v_{i+1},w_{k})=(v_{i},A^{T}w_{k})-eta _{i}(v_{i-1},w_{k})=(v_{i},w_{k+1}+alpha _{k}w_{k}+eta _{k}w_{k-1})-eta _{i}(v_{i-1},w_{k})=} =   ( v i , w k + 1 ) + α k ( v i , w k ) + β k ( v i , w k − 1 ) − β i ( v i − 1 , w k ) . {displaystyle =~(v_{i},w_{k+1})+alpha _{k}(v_{i},w_{k})+eta _{k}(v_{i},w_{k-1})-eta _{i}(v_{i-1},w_{k}).}

По предположению индукции, при k < i − 1 {displaystyle k<i-1} все четыре скалярные произведения обращаются в ноль; при k = i − 1 {displaystyle k=i-1} равны нулю все скалярные произведения во втором и третьем слагаемых, и тогда

( v i + 1 , w i − 1 ) = ( v i , w i ) − β i ( v i − 1 , w i − 1 ) = ( v i , w i ) − ( v i , w i ) ( v i − 1 , w i − 1 ) ( v i − 1 , w i − 1 ) = 0 {displaystyle (v_{i+1},w_{i-1})=(v_{i},w_{i})-eta _{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}

Аналогичным образом доказывается, что ( v k , w i + 1 ) = 0 {displaystyle (v_{k},w_{i+1})=0} для k = 1 , i ¯ . {displaystyle k={overline {1,i}}.}

Чтобы доказать второе утверждение теоремы, заметим, что непосредственно из v i + 1 = A v i − α i v i − β i v i − 1 , v 0 = 0 {displaystyle v_{i+1}=Av_{i}-alpha _{i}v_{i}-eta _{i}v_{i-1},v_{0}=0} следует s p a n f v 1 , v 2 , . . . v m g = K m ( v 1 , A ) . {displaystyle span{mathcal {f}}v_{1},v_{2},...v_{m}{mathcal {g}}=K_{m}(v_{1},A).} Остаётся лишь показать линейную независимость векторов v 1 , . . . , v m . {displaystyle v_{1},...,v_{m}.}

Предположим от противного, что существуют коэффициенты γ k , {displaystyle gamma _{k},} для которых γ 1 v 1 + γ 2 v 2 + . . . + γ m v m = 0. {displaystyle gamma _{1}v_{1}+gamma _{2}v_{2}+...+gamma _{m}v_{m}=0.}

Составляя скалярные произведения с векторами w k , k = 1 , i ¯ , {displaystyle w_{k},k={overline {1,i}},} получим

γ k ( v k , w k ) = 0 , k = 1 , i ¯ , {displaystyle gamma _{k}(v_{k},w_{k})=0,k={overline {1,i}},}

а так как по ранее доказанной биортогональности ( v k , w k ) ≠ 0 , {displaystyle (v_{k},w_{k}) eq 0,} то все коэффициенты γ k {displaystyle gamma _{k}} должны быть нулевыми. Аналогичные рассуждения для w 1 , . . . , w m {displaystyle w_{1},...,w_{m}} завершают доказательство теоремы.

Замечание. Основным недостатком биортогонализации Ланцоша является возможность возникновения ситуации, когда ( v i , w i ) = 0 ; {displaystyle (v_{i},w_{i})=0;} при этом продолжение процесса становится невозможным из-за неопределённости коэффициента β i + 1 . {displaystyle eta _{i+1}.}

Алгоритм биортогонализации Ланцоша

  • Выбираем два вектора v 1 ,   w 1 {displaystyle v_{1}, w_{1}} , так чтобы ( v 1 , w 1 ) = 1. {displaystyle (v_{1},w_{1})=1.}
  • Полагаем β 1 = δ 1 ≡ 0 ,   w 0 = v 0 ≡ 0 {displaystyle eta _{1}=delta _{1}equiv 0, w_{0}=v_{0}equiv 0}
  • Для j = 1 , 2 , . . . , m {displaystyle j=1,2,...,m} делать:
  • α j = ( A v j , w j ) {displaystyle alpha _{j}=(Av_{j},w_{j})}
  • v ^ j + 1 = A v j − α j v j − β j v j − 1 {displaystyle {hat {v}}_{j+1}=Av_{j}-alpha _{j}v_{j}-eta _{j}v_{j-1}}
  • w ^ j + 1 = A T w j − α j w j − δ j w j − 1 {displaystyle {hat {w}}_{j+1}=A^{T}w_{j}-alpha _{j}w_{j}-delta _{j}w_{j-1}}
  • δ j + 1 = j ( v ^ j + 1 , w ^ j + 1 ) j 1 / 2 {displaystyle delta _{j+1}={mathcal {j}}({hat {v}}_{j+1},{hat {w}}_{j+1}){mathcal {j}}^{1/2}} . Если δ j + 1 = 0 , {displaystyle delta _{j+1}=0,} то СТОП
  • β j + 1 = ( v ^ j + 1 , w ^ j + 1 ) / δ j + 1 {displaystyle eta _{j+1}=({hat {v}}_{j+1},{hat {w}}_{j+1})/delta _{j+1}}
  • v j + 1 = v ^ j + 1 / δ j + 1 {displaystyle v_{j+1}={hat {v}}_{j+1}/delta _{j+1}}
  • w j + 1 = w ^ j + 1 / β j + 1 {displaystyle w_{j+1}={hat {w}}_{j+1}/eta _{j+1}}
  • Конец цикла по j {displaystyle j} .


  • Имя:*
    E-Mail:
    Комментарий:
    Информационный некоммерческий ресурс fccland.ru ©
    При цитировании информации ссылка на сайт обязательна.
    Копирование материалов сайта ЗАПРЕЩЕНО!