Mostrar la convergencia de un algoritmo dentro de los pasos$m$

Question

Estoy tratando de demostrar que el siguiente algoritmo salidas a la solución del problema $Ax=b$.

Suposiciones $A$ es simétrica positiva definida de tamaño $n \times n$ con $m$ distintos autovalores. Los valores propios son conocidos, pero sus respectivos vectores propios y el número de veces que cada vector propio que se repite no es conocido.

entonces

\begin{align} \text{for } &i = 0,\dots, m\\ &r_i = b - Ax_i\\ &x_{i+1} = x_i + \frac{1}{\lambda_i}r_i\\ \text{end} \end{align}

este algoritmo debe converger en $m$ pasos

Lo que he hecho hasta ahora:

Mi objetivo ha sido mostrar que $||x-x_m|| = 0$ , lo que en términos mostrará que $x-x_m = 0$, que completa la prueba.

\begin{align} e_m &= x - x_m\\ &= x - x_{m-1} + x_m -x_{m-1}\\ &= e_{n-1} + \frac{1}{\lambda_{n-1}}r_{n-1}\\ & = e_0 + \sum_{i=1} ^{m-1} \frac{1}{\lambda_{i}}r_{i} \end{align}

En este punto, traté de tomar la norma, pero que no me lleve a nada, creo que me falta algo. Agradecería algunas ideas y orientación.

Answer 1

Podemos expresar el error inicial $e_0$ como una combinación lineal de los vectores propios $v_j$ correspondientes a los autovalores $\lambda_j$: $$ e_0=\sum_{j=1}^mc_jv_j. $$ No importa que los autovalores puede ser repetido. Siempre hay algunos autovector $v_j$ que podemos tomar desde el espacio propio de $\lambda_j$ para hacer la combinación lineal.

La inicial residual $r_0$ es entonces $$ r_0=Ae_0=\sum_{j=1}^mc_j\lambda_jv_j. $$

Ahora para el error de $e_1$, tenemos $$ e_1=e_0-\frac{1}{\lambda_1}r_0 =\sum_{j=1}^mc_jv_j-\frac{1}{\lambda_1}\sum_{j=1}^mc_j\lambda_jv_j =\sum_{j=2}^m c_j\frac{\lambda_j}{\lambda_1}v_j=\sum_{j=2}^m\tilde{c}_j v_j. $$ Tenga en cuenta que la componente correspondiente a $v_1$ desaparecido.

De esta manera, se puede demostrar que los $e_i$ no tiene componente en los subespacios propios correspondientes a los valores propios $\lambda_1,\ldots,\lambda_i$ y, por tanto, $e_m$ es cero.