convergencia de iteración

Question

Al resolver la ecuación lineal $x=Ax+b$ (donde $x$ es un vector desconocido, $A$ es una matriz, y $b$ es un vector constante), se suele utilizar la iteración siguiente:

$x_{k+1}=Ax_k +b$ .

¿Lo anterior $x_k$ es convergente a $x$ cuando el radio espectral de $A$ es menos de 1? Si es así, ¿podría dar una razón. Gracias.

Answer 1

La existencia y la singularidad se han mostrado anteriormente; así que lo que sigue mostrará que la iteración converge independientemente de la diagonizabilidad de $A$ . Es simplemente la prueba del teorema del punto fijo de Banach (demostrado en el Análisis numérico ) aplicado a la situación en cuestión. Deje que $||A||_{2}:= \sup_ {||x||_{2}=1} ||Ax||_{2}$ donde $||x||_{2}^{2}:=x_{1}^{2}+x_{2}^{2}+ \cdots + x_{n}^{2}$ . Esto define una norma sobre el espacio de las matrices. Además, hay pruebas bien conocidas (de nuevo encontradas en Kress) de que $$ ||A||_{2}^{2} = \rho (A^{*}A) $$ Si $ \mu\in \mathbb {C}$ es un valor propio de $A$ Entonces $| \mu |^{2}$ es un valor propio de $A^{*}A$ . Así que si cada valor propio de $A$ es $<1$ entonces cada valor propio de $A^* A$ es también $<1$ . Por lo tanto $ \rho (A)<1$ implica $||A||_{2}= \sqrt { \rho (A^{*}A)} <1$ . Luego $$ ||x_{n+1}-x_{n}||_{2} = ||Ax_{n}+b-(Ax_{n-1}+b)||_{2} = ||A(x_{n}-x_{n-1})||_{2} \le ||A||_{2}||x_{n}-x_{n-1}||_{2} $$ Podemos hacer lo mismo con $||x_{n}-x_{n-1}||_{2}$ y así sucesivamente, para conseguir $$ ||x_{n+1}-x_{n}||_{2} \le ||A||_{2}^{n}||x_{1}-x_{0}||_{2}. $$ Desde $||A||_{2}<1$ , $||x_{n+1}-x_{n}||_{2} \to 0$ que no es suficiente para probar que $x_{n} \to x$ . Necesitamos la condición más fuerte que $\{x_{n}\}_{n=1}^{ \infty }$ es una secuencia caucásica, es decir, que $||x_{n}-x_{m}||_{2} \to 0$ para $n,m \to \infty $ . Así que asume $m>n$ . Luego $$ \begin {align*} ||x_{n}-x_{m}||_{2} &= ||x_{n}-x_{n+1}+x_{n+1} -x_{n+2}+x_{n+2} + \cdots +x_{m-1}-x_{m}||_{2} \\ & \le ||x_{n}-x_{n+1}||_{2}+||x_{n+1}-x_{n+2}||_{2} + \cdots ||x_{m-1}-x_{m}||_{2} \\ & \le ||A||_{2}^{n}||x_{1}-x_{0}||_{2} + ||A||_{2}^{n+1}||_{2}||x_{1}-x_{0}|| + \cdots +||A||_{2}^{m-1}||x_{1}-x_{0}||_{2} \\ & \le \frac {||A||_{2}^{n}}{1-||A||_{2}} ||x_{1}-x_{0}||_{2} \to 0 \end {align*}$$ como $n \to \infty $ . Así que, de hecho, forma una secuencia caucásica. El espacio $ \mathbb {R}^{n}$ está completo, por lo que existe una única $x \in \mathbb {R}^{n}$ de tal manera que $x_{n} \to x$ .

Recuerdo haber luchado contra este teorema durante mucho tiempo en la escuela de postgrado, y lo que te he dado aquí es una versión mal escrita de lo que Kress escribe. Así que espero que esto ayude.

Answer 2

La prueba de este resultado se muestra a menudo en el libro de análisis numérico elemental. Aquí hay un bosquejo.

Primero muestras que existe un punto fijo único para $x = g(x) = Ax + b$ . El punto fijo $x$ satisface $x = g(x)$ si y sólo si $(I-A)x = b$ que te da existencia y unicidad si $I-A$ es invertible. Los valores propios $ \mu $ de $I-T$ satisface $$ \det ((I-T) - \mu I) = 0 \quad \Longleftrightarrow \quad \det (T - (1- \mu ) I) = 0 $$ para que $ \rho (T) = \max_ {i=1}^n | \lambda_i | < 1$ implica $|1- \mu | < 1$ y hemos terminado.

Ahora que tenemos existencia y unicidad, $x_{k+1} = Ax_k + b$ significa $x_{k+1} - x = A(x_k - x)$ . Supongamos en este punto que $A$ es diagonal, de modo que el error puede ser escrito como $$ x_0 - x = \sum_ {i=1}^n \gamma_i v_i $$ lo que significa $$ x_{k+1} - x = A(x_k - x) = \sum_ {i=1}^n \gamma_i \lambda_i ^k v_i $$ por inducción en $k$ . Por lo tanto, desde $| \lambda_i ^k| = | \lambda_i |^k \to 0$ como $k \to \infty $ (porque $| \lambda_i | < 1$ ), sabemos que el "término de error" $x_k - x$ va a $0$ así que tu algoritmo converge.

Debo decir que aunque no tengo pruebas cuando $A$ no es diagonal.

Espero que eso ayude,

Answer 3

Aquí hay un camino peatonal para este problema: Como $x$ está de alguna manera relacionado con el "mundo" generado por $A$ y por $b$ hacemos el "Ansatz" $$x= \sum_ {k=0}^ \infty c_k\ A^k\, b$$ con coeficientes indeterminados $c_k$ . La ecuación dada requiere $$ \sum_ {k=0}^ \infty c_k\ A^k\, b= \sum_ {k=0}^ \infty c_k\ A^{k+1}\, b = \sum_ {k=1}^ \infty c_{k-1}\ A^k\, b +b\ ,$$ o $$c_0 b+ \sum_ {k=1}^ \infty (c_k-c_{k-1})\ A^k\, b = b\ .$$ Esto se resuelve para lo que sea $A$ y $b$ poniendo $c_k=1$ $\ (k \geq 0)$ asumiendo que la serie infinita es convergente. Por lo tanto, tenemos $$x= \sum_ {k=0}^ \infty A^k\ b\ ,$$ que de hecho tiene sentido cuando el radio espectral de $A$ es $<1$ . Pero podemos decir más: Bajo este supuesto existe el mapa $B:=(I-A)^{-1}\ $ y la solución que hemos encontrado no es otra que el desarrollo de $x=B\, b$ en una serie geométrica.