Métodos de proyección para resolver SLAE

Los métodos de proyección para resolver SLAE son una clase de métodos iterativos en los que el problema de proyectar un vector desconocido en un espacio determinado se resuelve de manera óptima con respecto a algún otro espacio.

Planteamiento del problema

Consideremos SLAE donde es una matriz cuadrada de dimensión Sea y sean subespacios bidimensionales del espacio . Es necesario encontrar un vector tal que , es decir, se cumplió la condición: $Ax=b,$ $A$ $norte.$ $k$ $L$ $metro$ $R^{n}.$ $\tilde{x} \in K$ $bA\tilde{x} \perp L,$

$\forall l\in L: (A\tilde{x} ,l)=(b,l),$

llamada condición de Petrov-Galyorkin.

Si se conoce la aproximación inicial , entonces la solución debe proyectarse en un espacio afín . Representemos y denotemos la discrepancia de la aproximación inicial como $x_{0}$ $x_{0}+K.$ $\tilde{x} =x_0+ \delta$ $r_{0}=b-Ax_{0}.$

$bA{\tilde {x}}=bA(x_{0}+\delta )=b-Ax_{0}-A\delta =(b-Ax_{0})-A\delta =r_{0 }-A\delta .$

Entonces, el enunciado del problema se puede formular de la siguiente manera: es necesario encontrar tal que , p . se cumplió la condición: $\delta\en K,$ $r_0 -A \delta \perp L ,$

${\tilde {x}}=x_{0}+\delta ,\ \delta \in K$

$\forall l\in L:(r_0-A \delta,l)=0$

Aproximación general a la construcción de métodos de proyección

Introduzcamos bases de matrices en los espacios y $k$ ${\ estilo de visualización L:}$

$V=[v_{1},v_{2},...,v_{m}]$ - matriz de tamaño compuesta por vectores de columna de base espacial - matriz de tamaño compuesta por vectores de columna de base espacial $n \veces m$ $k$ $W=[w_{1},w_{2},...,w_{m}]$ $n \veces m$ $l$

Entonces el vector solución también se puede escribir: $\delta\ = Vy$ $\tilde{x}$

$\tilde{x} = x_0 + Vy,$

donde es el vector de coeficientes. ${\ Displaystyle y \ en R ^ {m}}$

Entonces la expresión se puede reescribir como: $(r_0-A\delta\,l)=0$

$W^T (r_0-A \delta\ )= \bar{0},$

de donde y ${\displaystyle W^{T}AVy=W^{T}r_{0))$

$y=(W^{T}AV)^{-1}W^{T}r_{0},$

Por lo tanto, la solución debe refinarse de acuerdo con la fórmula:

$x_{1}=x_{0}+V(W^{T}AV)^{-1}W^{T}r_{0},$

Vista general de cualquier método de clase de proyección:

Hazlo hasta encontrar una solución.

Elija un par de subespacios y $k$ $l$
Construcción para y bases y $k$ $L$ $V=[v_{1},v_{2},...,v_{m}]$ $W=[w_{1},w_{2},...,w_{m}].$
$r_{0}=b-Ax_{0}.$
$y=(W^{T}AV)^{-1}W^{T}r_{0}.$
$x_{1}=x_{0}+Vy.$

La elección de los espacios y el método de construcción de bases para ellos determinan completamente el esquema computacional del método. $k$ $L$

Elección de los subespacios K y L

El caso de los subespacios unidimensionales K y L

En el caso de que los espacios y sean unidimensionales, sus bases matriciales son vectores: y y la expresión se puede reescribir como $k$ $L$ ${\ estilo de visualización V = [v]}$ ${\ estilo de visualización W = [w]}$ $\tilde{x} = x_0 + Vy,$

$x_{k+1} = x_k + \gamma_k\ v_k,$

donde es un coeficiente desconocido, que se encuentra fácilmente a partir de la condición de ortogonalidad $\gamma_k\$ $r_k - A( \gamma_k\ v_k ) \perp w_k :$

$(r_k - \gamma_k\ Av_k,w_k) =(r_k , w_k) - \gamma_k\ (Av_k,w_k)= \bar{0},$

dónde $\gamma_k\ = \frac {(r_k , w_k)}{(Av_k,w_k)}.$

Métodos con la elección de subespacios unidimensionales y : $k$ $L$

Método de descenso más pronunciado
Método de reducción residual más rápido
Método de Gauss-Seidel
Métodos de clase ABS

En problemas prácticos, métodos que usan espacios unidimensionales y tienen una convergencia bastante lenta. $k$ $L$

Métodos tipo Krylovsky

Los métodos de tipo Krylov (o métodos del subespacio de Krylov ) son métodos para los que se elige el subespacio de Krylov como subespacio: $k$

${\mathcal {K}}_{m}(r_{0},A)=span\{r_{0},Ar_{0},A^{2}r_{0},..., A^{m-1}r_{0}\},$

donde es la discrepancia de la aproximación inicial. Las diferentes versiones de los métodos del subespacio de Krylov están condicionadas por la elección del subespacio ${\displaystyle r_{0}=b-Ax_{0))$ $l$

Desde el punto de vista de la teoría de la aproximación, las aproximaciones obtenidas en los métodos del subespacio de Krylov tienen la forma $\tilde{x},$

$A^{-1}b\approx {\tilde {x}}=x_{0}+q_{m-1}(A)r_{0},$

donde es un polinomio de grado Si ponemos , entonces ${\ Displaystyle q_ {m-1}}$ ${\ estilo de visualización m-1.}$ ${\ estilo de visualización x_ {0} = 0,}$

$A^{-1}b\aprox. q_{m-1}(A)b.$

En otras palabras, se aproxima ${\ estilo de visualización A ^ {-1} b}$ $q_{m-1}(A)b.$

Aunque la elección del subespacio no afecta el tipo de aproximación polinomial, tiene un impacto significativo en la eficiencia del método. Hasta la fecha, hay 2 formas de seleccionar un subespacio que dan los resultados más efectivos: $L$ ${\ estilo de visualización L,}$

${\ estilo de visualización L = K}$ y $L=AK$
$L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})$

{\ estilo de visualización L = K}

L=AK

teorema _
Si la matriz A es simétrica y definida positiva, entonces el problema de diseñar un SLAEen cualquier subespacioortogonalmente al subespacioes equivalente al problema de minimizar el funcional

hacha=b

k

{\ estilo de visualización L = K}

$\Phi_1(x) = \parallel x- \tilde{x} \parallel_A^2,$

dónde $\parallel x \parallel_A^2 = (Ax,x).$

Prueba

En virtud de la definición positiva de la matriz , la funcional alcanza su mínimo en y es estrictamente convexa. Donde $A$ $\Phi_{1}(x)$ $x= \tilde{x}$

\Phi_1(x)=(A(x- \tilde{x}),x- \tilde{x})= (Ax,x)-(A \tilde{x},x)-(Ax, \tilde{ x})+(A \tilde{x},\tilde{x})=

=(Ax,x)-(Ax,\tilde{x})-(b,x)+(b,\tilde{x})= x^TAx-\tilde{x}^TAx-b^Tx+b ^T\tilde{x}.

Debido a la simetría de la matriz , es verdadera y el funcional es igual a $A$ ${\tilde {x}}^{T}Ax=b^{T}A(A^{-1})x=b^{T}x,$

\Phi_1(x)=x^TAx-2b^Tx+b^T\tilde{x}.

Por la hipótesis del teorema, por lo tanto, el Funcional es estrictamente convexo. El problema de minimización formulado en la condición se reduce así a encontrar ${\ estilo de visualización K = L,}$ ${\ estilo de visualización V = W.}$ $\Phi_{1}(x)$

y=\arg \min_{y}\Phi_{1}(x_{0}+Vy).

Consideremos este problema. Debido a la convexidad, basta encontrar un punto estacionario del funcional, es decir resolver el sistema ${\ estilo de visualización \ Psi (y) = \ Phi _ {1} (x_ {0} + Vy),}$ ${\mathcal {r}}\Psi(y)=0.$

\Psi (y)=(x_{0}+Vy)^{T}A(x_{0}+Vy)-2b^{T}(x_{0}+Vy)+b^{T} {\tilde {x}}=

=(x_{0}^{T}Ab^{T})x_{0}-b^{T}x_{0}+2(x_{0}^{T}Ab^{T}) Vy+y^{T}(V^{T}AV)y+b^{T}{\tilde {x}}=

=y^{T}(V^{T}AV)y-r_{0}^{T}x_{0}-b^{T}x_{0}-2r_{0}^{T} Vy+b^{T}{\tilde {x}}.

El gradiente de esta funcional es Igualándolo a cero, obtenemos ${\mathcal {r}}\Psi _{1}(y)=2V^{T}AVy-2V^{T}r_{0}.$

y=(V^{T}AV)^{-1}V^{T}r_{0},

que es exactamente igual a la expresión si le ponemos $y=(W^{T}AV)^{-1}W^{T}r_{0},$ ${\ estilo de visualización V = W.}$

teorema _
Si la matriz A no es degenerada, entonces el problema de diseñar un SLAEen cualquier subespacioortogonalmente al subespacioes equivalente al problema de minimizar el funcional

hacha=b

k

L=AK

$\Phi_2(x) = \parallel r_x \parallel_2^2.$

Prueba

Sustituyendo la relación por las bases en la fórmula, obtenemos: ${\displaystyle y=(W^{T}AV)^{-1}W^{T}r_{0))$ ${\ estilo de visualización W = AV,}$

y=(V^{T}A^{T}AV)^{-1}V^{T}A^{T}r_{0}.

Esto significa que la situación bajo consideración es equivalente a la elección del sistema simetrizado. ${\ estilo de visualización L = K}$ $A^{T}Ax=A^{T}b.$

Dada la proporción

\parallel x- \tilde{x} \parallel_{A^TA}^2 = (A^TA (x- \tilde{x}),(x- \tilde{x}))_2=(A(x- \tilde{x}),A(x- \tilde{x} ))_2=(r_x,r_x)_2= \parallel r_x \parallel_2^2

y aplicando el teorema anterior a tal sistema, obtenemos la afirmación formulada en la condición.

L={\mathcal {K}}_{m}({\tilde {r}}_{0},A^{T})

Para construir cada nuevo vector , el algoritmo de ortogonalización de Arnoldi requiere encontrar productos internos y el mismo número de operaciones de combinación lineal. $v_{k}$ $(k-1)$

Literatura

Saad Y. Métodos iterativos para sistemas lineales dispersos. — 2ª edición. - Sociedad SIAM de Matemática Industrial y Aplicada, 2003. - P. 477. -ISBN 0898715342.
Balandin M.Yu., Shurina E.P. Métodos para la resolución de SLAEs de alta dimensión. - Novosibirsk: NSTU, 2000. - S. 70.
Golub J., Van Lone C. Computación matricial. - Moscú: Mir, 1999.
Ilyin V.P. Métodos de factorización incompleta para la resolución de sistemas lineales. - Moscú: Fizmatlit, 1995.

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel Método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento