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

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

${\displaystyle {\mathcal {K}}_{m}(v_{1},A)=span\{v_{1},Av_{1},A^{2}v_{1},...,A^{m-1}v_{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}\}.}$

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

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

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

Теорема

Пусть векторы ${\displaystyle v_{1}}$ и ${\displaystyle w_{1}}$ таковы, что ${\displaystyle (v_{1},w_{1})\neq 0}$ и пусть системы векторов ${\displaystyle \{v_{i}\}_{i=1}^{m}}$ и ${\displaystyle \{w_{i}\}_{i=1}^{m}}$ определяются соотношениями:

${\displaystyle v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},\ v_{0}=0;}$ ${\displaystyle w_{i+1}=A^{T}w_{i}-\alpha _{i}w_{i}-\beta _{i}w_{i-1},\ w_{0}=0;}$ ${\displaystyle \alpha _{i}={\frac {(Av_{i},w_{i})}{(v_{i},w_{i})}}}$ ${\displaystyle \beta _{i}={\frac {(v_{i},w_{i})}{(v_{i-1},w_{i-1})}},\beta _{1}=0}$

Тогда

• Системы ${\displaystyle \{v_{i}\}_{i=1}^{m}}$ и ${\displaystyle \{w_{i}\}_{i=1}^{m}}$ являются биортогональными.
• Каждая из систем ${\displaystyle \{v_{i}\}_{i=1}^{m}}$ и ${\displaystyle \{w_{i}\}_{i=1}^{m}}$ является линейно-независимой и образует базис в ${\displaystyle K_{m}(v_{1},A)}$ и ${\displaystyle K_{m}(w_{1},A^{T})}$ соответственно.

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

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

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

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

Умножим выражение ${\displaystyle v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},}$ скалярно на ${\displaystyle w_{k}}$

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

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

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

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

${\displaystyle (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})=}$ ${\displaystyle =~(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}).}$

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

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

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

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

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

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

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

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

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

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

1. Выбираем два вектора ${\displaystyle v_{1},\ w_{1}}$, так чтобы ${\displaystyle (v_{1},w_{1})=1.}$
2. Полагаем ${\displaystyle \beta _{1}=\delta _{1}\equiv 0,\ w_{0}=v_{0}\equiv 0}$
3. Для ${\displaystyle j=1,2,...,m}$ делать:
4. ${\displaystyle \alpha _{j}=(Av_{j},w_{j})}$
5. ${\displaystyle {\hat {v}}_{j+1}=Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}}$
6. ${\displaystyle {\hat {w}}_{j+1}=A^{T}w_{j}-\alpha _{j}w_{j}-\delta _{j}w_{j-1}}$
7. ${\displaystyle \delta _{j+1}={\mathcal {j}}({\hat {v}}_{j+1},{\hat {w}}_{j+1}){\mathcal {j}}^{1/2}}$. Если ${\displaystyle \delta _{j+1}=0,}$ то СТОП
8. ${\displaystyle \beta _{j+1}=({\hat {v}}_{j+1},{\hat {w}}_{j+1})/\delta _{j+1}}$
9. ${\displaystyle v_{j+1}={\hat {v}}_{j+1}/\delta _{j+1}}$
10. ${\displaystyle w_{j+1}={\hat {w}}_{j+1}/\beta _{j+1}}$
11. Конец цикла по ${\displaystyle j}$.

Ссылки

• Методы решения СЛАУ большой размерности: Учебное пособие