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

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

${\mathcal{K}}_m(v_1,A)=span\{v_1,A{v}_1,A^2{v}_1,...,A^{m-<!--\; -\; -->1}{v}_1\}$${\mathcal {K}}_{m}(v_{1},A)=img\{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\}.$${\mathcal {K}}_{m}(w_{1},A^{T})=img\{w_{1},A^{T}w_{1},(A^{T})^{2}w_{1},...,(A^{T})^{m-1}w_{1}\}.$

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

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

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

Теорема. Пусть векторы $v_1$$v_{1}$  и $w_1$$w_{1}$  таковы, что $(v_1,w_1)\ne <!--\; \ne \; -->0$$(v_{1},w_{1})\neq 0$  и пусть системы векторов $\{v_i{\}}_{i=1}^m$$\{v_{i}\}_{i=1}^{m}$  и $\{w_i{\}}_{i=1}^m$$\{w_{i}\}_{i=1}^{m}$  определяются соотношениями: $v_{i+1}=A{v}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i{v}_i-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i{v}_{i-<!--\; -\; -->1},v_0=0;$$v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},\ v_{0}=0;$  $w_{i+1}=A^T{w}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i{w}_i-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i{w}_{i-<!--\; -\; -->1},w_0=0;$$w_{i+1}=A^{T}w_{i}-\alpha _{i}w_{i}-\beta _{i}w_{i-1},\ w_{0}=0;$  ${\mathrm{\alpha <!--\; \alpha \; -->}}_i=\frac{(A{v}_i,w_i)}{(v_i,w_i)}$$\alpha _{i}={\frac {(Av_{i},w_{i})}{(v_{i},w_{i})}}$  ${\mathrm{\beta <!--\; \beta \; -->}}_i=\frac{(v_i,w_i)}{(v_{i-<!--\; -\; -->1},w_{i-<!--\; -\; -->1})},{\mathrm{\beta <!--\; \beta \; -->}}_1=0$$\beta _{i}={\frac {(v_{i},w_{i})}{(v_{i-1},w_{i-1})}},\beta _{1}=0$  Тогда Системы $\{v_i{\}}_{i=1}^m$$\{v_{i}\}_{i=1}^{m}$  и $\{w_i{\}}_{i=1}^m$$\{w_{i}\}_{i=1}^{m}$  являются биортогональными. Каждая из систем $\{v_i{\}}_{i=1}^m$$\{v_{i}\}_{i=1}^{m}$  и $\{w_i{\}}_{i=1}^m$$\{w_{i}\}_{i=1}^{m}$  является линейно-независимой и образует базис в $K_m(v_1,A)$$K_{m}(v_{1},A)$  и $K_m(w_1,A^T)$$K_{m}(w_{1},A^{T})$  соответственно.

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

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

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

Предположим теперь, что уже построены биортогональные наборы $\mathcal{f}{v}_1,...,v_i\mathcal{g}$${\mathcal {f}}v_{1},...,v_{i}{\mathcal {g}}$  и $\mathcal{f}{w}_1,...,w_i\mathcal{g}$${\mathcal {f}}w_{1},...,w_{i}{\mathcal {g}}$ , и далее покажем, что для вектора $v_{i+1}$$v_{{i+1}}$ , определяемого соотношением $v_{i+1}=A{v}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i{v}_i-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i{v}_{i-<!--\; -\; -->1},$$v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$  имеет место $(v_{i+1},w_k)=0,k=\stackrel{¯<!--\; ¯\; -->}{1,i}.$$(v_{{i+1}},w_{k})=0,k=\overline {1,i}.$ 

Умножим выражение $v_{i+1}=A{v}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i{v}_i-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i{v}_{i-<!--\; -\; -->1},$$v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$  скалярно на $w_k$$w_{k}$ 

$(v_{i+1},w_k)=(A{v}_i,w_k)-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i(v_i,w_k)-<!--\; -\; -->{\mathrm{\beta <!--\; \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,$$k=i,$  то по предположению индукции последнее скалярное произведение обращается в ноль и

$(v_{i+1},w_i)=(A{v}_i,w_i)-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i(v_i,w_i)=(A{v}_i,w_i)-<!--\; -\; -->\frac{(A{v}_i,w_i)}{(v_i,w_i)}(v_i,w_i)=0.$$(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)-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i(v_{i-<!--\; -\; -->1},w_k)=(v_i,w_{k+1}+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{w}_k+{\mathrm{\beta <!--\; \beta \; -->}}_k{w}_{k-<!--\; -\; -->1})-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i(v_{i-<!--\; -\; -->1},w_k)=$$(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})+{\mathrm{\alpha <!--\; \alpha \; -->}}_k(v_i,w_k)+{\mathrm{\beta <!--\; \beta \; -->}}_k(v_i,w_{k-<!--\; -\; -->1})-<!--\; -\; -->{\mathrm{\beta <!--\; \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$$k=i-1$  равны нулю все скалярные произведения во втором и третьем слагаемых, и тогда

$(v_{i+1},w_{i-<!--\; -\; -->1})=(v_i,w_i)-<!--\; -\; -->{\mathrm{\beta <!--\; \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_{{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$$(v_{k},w_{i+1})=0$  для $k=\stackrel{¯<!--\; ¯\; -->}{1,i}.$$k={\overline {1,i}}.$ 

Чтобы доказать второе утверждение теоремы, заметим, что непосредственно из $v_{i+1}=A{v}_i-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_i{v}_i-<!--\; -\; -->{\mathrm{\beta <!--\; \beta \; -->}}_i{v}_{i-<!--\; -\; -->1},v_0=0$$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).$$img{\mathcal {f}}v_{1},v_{2},...v_{m}{\mathcal {g}}=K_{m}(v_{1},A).$  Остаётся лишь показать линейную независимость векторов $v_1,...,v_m.$$v_{1},...,v_{m}.$ 

Предположим от противного, что существуют коэффициенты ${\mathrm{\gamma <!--\; \gamma \; -->}}_k,$$\gamma _{k},$  для которых ${\mathrm{\gamma <!--\; \gamma \; -->}}_1{v}_1+{\mathrm{\gamma <!--\; \gamma \; -->}}_2{v}_2+...+{\mathrm{\gamma <!--\; \gamma \; -->}}_m{v}_m=0.$$\gamma _{1}v_{1}+\gamma _{2}v_{2}+...+\gamma _{m}v_{m}=0.$ 

Составляя скалярные произведения с векторами $w_k,k=\stackrel{¯<!--\; ¯\; -->}{1,i},$$w_{k},k={\overline {1,i}},$  получим

${\mathrm{\gamma <!--\; \gamma \; -->}}_k(v_k,w_k)=0,k=\stackrel{¯<!--\; ¯\; -->}{1,i},$$\gamma _{k}(v_{k},w_{k})=0,k={\overline {1,i}},$ 

а так как по ранее доказанной биортогональности $(v_k,w_k)\ne <!--\; \ne \; -->0,$$(v_{k},w_{k})\neq 0,$  то все коэффициенты ${\mathrm{\gamma <!--\; \gamma \; -->}}_k$$\gamma _{k}$  должны быть нулевыми. Аналогичные рассуждения для $w_1,...,w_m$$w_{1},...,w_{m}$  завершают доказательство теоремы.

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

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

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

СсылкиПравить

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