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

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

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

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

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

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

Теорема. Пусть векторы $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$ Тогда Системы $\{v_{i}\}_{i=1}^{m}$ и $\{w_{i}\}_{i=1}^{m}$ являются биортогональными. Каждая из систем $\{v_{i}\}_{i=1}^{m}$ и $\{w_{i}\}_{i=1}^{m}$ является линейно-независимой и образует базис в $K_{m}(v_{1},A)$ и $K_{m}(w_{1},A^{T})$ соответственно.

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

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

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

Предположим теперь, что уже построены биортогональные наборы ${\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}}.$

Умножим выражение $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}).$

Если $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.$

Если же $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}).$

По предположению индукции, при $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$

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

Чтобы доказать второе утверждение теоремы, заметим, что непосредственно из $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}.$

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

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

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

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

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

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

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

Ссылки

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