Biortogonalización de Lanczos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de agosto de 2017; la verificación requiere 1 edición .

Biortogonalización de Lanczos : en álgebra lineal , el proceso de construcción de un par de bases biortogonales para dos subespacios de Krylov

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

El método fue propuesto por el físico y matemático húngaro Cornelius Lanczos y es una extensión del procedimiento de ortogonalización de Lanczos al caso donde la matriz no es simétrica . $A$

Justificación teórica del método

Definición. Los sistemas de vectores y se denominan biortogonales si ${\displaystyle \{x_{i}\}_{i=1}^{m))$ ${\displaystyle \{y_{i}\}_{i=1}^{m))$ $\forall i\neq j\;(x_{i},y_{j})=0.$

teorema _
Sean los vectoresytales quey sean los sistemas de vectoresydefinidos por las relaciones:

v_{1}

w_{1}

(v_{1},w_{1})\neq 0

{\displaystyle \{v_{i}\}_{i=1}^{m))

{\displaystyle \{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

Después

Los sistemas y son biortogonales. ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$
Cada uno de los sistemas y es linealmente independiente y forma una base en y respectivamente. ${\displaystyle \{v_{i}\}_{i=1}^{m))$ ${\displaystyle \{w_{i}\}_{i=1}^{m))$ $K_{m}(v_{1},A)$ $K_{m}(w_{1},A^{T})$

Prueba

La primera afirmación del teorema se demuestra por el método de inducción matemática .

De hecho, el par de vectores y satisface la condición de biortogonalidad. $v_{1}$ $w_{1}$

Supongamos ahora que los conjuntos biortogonales y ya han sido construidos , y luego mostraremos que para el vector definido por la relación, tenemos ${\mathcal {f}}v_{1},...,v_{i}{\mathcal {g}}$ ${\mathcal {f}}w_{1},...,w_{i}{\mathcal {g}}$ $v_{{yo+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}.$

Multiplica la expresión escalarmente por $v_{i+1}=Av_{i}-\alpha _{i}v_{i}-\beta _{i}v_{i-1},$ ${\ Displaystyle w_ {k}}$

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

Si entonces, por la hipótesis de inducción, el último producto escalar se anula y ${\ estilo de visualización k = yo,}$

(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.

si entonces ${\ estilo de visualización 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}).

Por la hipótesis de inducción, porque los cuatro productos escalares se anulan; para todos los productos escalares en el segundo y tercer términos son iguales a cero, y luego ${\ estilo de visualización k <i-1}$ ${\ estilo de visualización 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

De manera similar, se prueba que para ${\ estilo de visualización (v_ {k}, w_ {i + 1}) = 0}$ $k={\overline {1,i)).$

Para probar la segunda afirmación del teorema , notemos que de ella se sigue directamente , sólo resta mostrar la independencia lineal de los vectores $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}.$

Supongamos, por el contrario, que existen coeficientes para los cuales

{\ estilo de visualización \ gamma _ {k},}

\gamma _{1}v_{1}+\gamma _{2}v_{2}+...+\gamma _{m}v_{m}=0.

Compilando productos escalares con vectores, obtenemos $w_{k},k={\overline {1,i)),$

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

y dado que, por la biortogonalidad previamente probada , todos los coeficientes deben ser cero. Argumentos similares para completar la demostración del teorema. $(v_{k},w_{k})\neq 0,$ $\gamma _{k}$ ${\ estilo de visualización w_ {1},..., w_ {m}}$

Comentario. La principal desventaja de la biortogonalización de Lanczos es la posibilidad de una situación en la que, en este caso, la continuación del proceso se vuelve imposible debido a la incertidumbre del coeficiente. ${\ estilo de visualización (v_ {i}, w_ {i}) = 0;}$ ${\ estilo de visualización \ beta _ {i + 1}.}$

Algoritmo de biortogonalización de Lanczos

Elegimos dos vectores de modo que $v_{1},\w_{1}$ ${\ estilo de visualización (v_ {1}, w_ {1}) = 1.}$
Creemos $\beta _{1}=\delta _{1}\equiv 0,\ w_{0}=v_{0}\equiv 0$
para hacer: $j=1,2,...,m$
${\ estilo de visualización \ alfa _ {j} = (Av_ {j}, w_ {j})}$
${\sombrero {v}}_{j+1}=Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}$
${\sombrero {w}}_{j+1}=A^{T}w_{j}-\alpha _{j}w_{j}-\delta _{j}w_{j-1}$
$\delta _{j+1}={\mathcal {j}}({\sombrero {v}}_{j+1},{\sombrero {w}}_{j+1}){\ matemática {j}}^{1/2}$ . Si entonces PARE ${\ estilo de visualización \ delta _ {j + 1} = 0,}$
$\beta _{j+1}=({\sombrero {v}}_{j+1},{\sombrero {w}}_{j+1})/\delta _{j+1}$
$v_{j+1}={\sombrero {v}}_{j+1}/\delta _{j+1}$
$w_{j+1}={\sombrero {w}}_{j+1}/\beta _{j+1}$
Fin de ciclo por . $j$

Enlaces

Métodos para resolver SLAE de alta dimensión: Tutorial