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

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

$~ \mathcal{K}_m (v_1,A) = span \mathcal {f} v_1, Av_1, A^2 v_1, ..., A^{m-1} v_1 \mathcal {g}$

и

$~ \mathcal{K}_m (w_1,A^T) = span \mathcal {f} w_1, A^Tw_1, (A^T)^2 w_1, ..., (A^T)^{m-1} w_1 \mathcal {g} .$

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

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

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

Теорема. Пусть векторы $~v_1$ и $~w_1$ таковы, что $(v_1,w_1)\ne 0$ и пусть системы векторов $\mathcal {f} v_i \mathcal {g} _ {i=1}^m$ и $\mathcal {f} w_i \mathcal {g} _ {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$ Тогда Системы $\mathcal {f} v_i \mathcal {g} _ {i=1}^m$ и $\mathcal {f} w_i \mathcal {g} _ {i=1}^m$ являются биортогональными. Каждая из систем $\mathcal {f} v_i \mathcal {g} _ {i=1}^m$ и $\mathcal {f} w_i \mathcal {g} _ {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) \ne 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$.

Ссылки

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

Для улучшения этой статьи желательно?: Проверить достоверность указанной в статье информации. Переработать оформление в соответствии с правилами написания статей.