Teorema sobre la velocidad de convergencia en un método iterativo

(1/2) > >>

pierrot:
Supongamos que se quiere resolver el sistema [texx]Ax=b[/texx] (se asume [texx]A[/texx] no singular) mediante cierto método iterativo dado por:

[texx]\left\{\begin{array}{l}{ X^{(0)} }\\ {M\cdot X^{(k+1)}=(M-A)\cdot X^{(k)}+b,\quad k\geq 0}\end{array}\right.[/texx]

en donde la matriz [texx]M[/texx] es invertible.

Si suponemos que la sucesión [texx]\{X^{(k)}\}_{k\in \mathbb{N}}[/texx] es convergente, se tendría:

[texx]M\cdot X^{(\infty)}=(M-A)\cdot X^{(\infty)}+b\Longleftrightarrow{}A\cdot X^{(\infty)}=b\Longleftrightarrow{}X^{(\infty)}=x[/texx]

[texx]\begin{align}M\cdot X^{(k+1)}=(M-A)\cdot X^{(k)}+b \\ M\cdot X^{(\infty)}=(M-A)\cdot X^{(\infty)}+b\end{align}[/texx]

Restando [texx](2)[/texx] a [texx](1)[/texx] se tiene que [texx]M\cdot \big(X^{(k+1)}-X^{(\infty)}\big)=(M-A)\cdot \big(X^{(k)}-X^{(\infty)}\big)[/texx]. Si se llama [texx]e^{(k)}=X^{(k)}-X^{(\infty)}[/texx] al error en el paso [texx]k[/texx]-ésimo queda:

[texx]M\cdot e^{(k+1)}=(M-A)\cdot e^{(k)}\Longleftrightarrow{} e^{(k+1)}=M^{-1}(M-A)\cdot e^{(k)}[/texx]. Llamando [texx]Q=M^{-1}(M-A)[/texx] se tiene que el método es convergente si y sólo si [texx]\rho (Q)<1[/texx] (radio espectral menor a uno).

Hasta aquí un breve contexto en el que está inmerso el ejercicio. Dice así:

Sean [texx]\left |{\lambda_1}\right |\leq \left |{\lambda_2}\right |\leq \cdots\leq \left |{\lambda_n}\right |[/texx] los valores propios de la matriz [texx]Q=M^{-1}(M-A)[/texx] asociada a cierto método iterativo, y [texx]v_1,v_2,\dots,v_n[/texx] vectores propios asociados a los [texx]\lambda_i[/texx].

Pruebe que si [texx]\displaystyle q^{(k)}=\frac{ \left\|{e^{(k+1)}}\right\|}{ \left\|{e^{(k)}}\right\|}[/texx] se cumple [texx]q^{(k)}\xrightarrow[k\xrightarrow{}+\infty]\,{\left |{\lambda_n}\right |}[/texx] (o sea, el radio espectral es un indicador de la velocidad de convergencia).

Para la demostración lo que hice fue lo siguiente:

Sabemos que [texx]e^{(k)}=Q\cdot e^{(k-1)}=Q\cdot Q\cdot e^{(k-2)}=\cdots =Q^k\cdot e^{(0)}[/texx]. Ahora al error en el paso 0 lo puedo expresar como combinación lineal de los vectores propios: [texx]e^{(0)}=\displaystyle \sum_{j=1}^nc_jv_j[/texx]. Entonces [texx]\displaystyle e^{(k)}=Q^k\cdot e^{(0)}=Q^k\cdot \sum_{j=1}^nc_jv_j=\sum_{j=1}^nc_j\cdot Q^kv_j=\sum_{j=1}^nc_j\cdot (\lambda_j)^kv_j[/texx]. Entonces llegamos a que:

[texx]\displaystyle e^{(k+1)}=\sum_{j=1}^nc_j\cdot (\lambda_j)^{k+1}v_j,\qquad e^{(k)}=\sum_{j=1}^nc_j\cdot (\lambda_j)^kv_j[/texx]

Si se tiene la convergencia en la norma-1, se tiene la convergencia en cualquier otra norma ya que todas las normas en [texx]\mathbb{R}^n[/texx] son equivalentes. Así que pasemos a estudiar:

[texx]\displaystyle \lim_{k\to +\infty}\frac{ \left\|{e^{(k+1)}}\right\|_1}{ \left\|{e^{(k)}}\right\|_1}[/texx]

Llamemos [texx]e^{(k+1)}(i)[/texx] a la entrada [texx]i[/texx]-ésima del vector [texx]e^{(k+1)}[/texx]. Es decir,

[texx]e^{(k+1)}=\left[\begin{array}{ccc}{e^{(k+1)}(1)}\\{e^{(k+1)}(2)}\\\vdots\\e^{(k+1)}(n)\end{array}\right][/texx]. La entrada [texx]i[/texx]-ésima en virtud de lo dicho anteriormente será [texx]\displaystyle e^{(k+1)}(i)=\sum_{j=1}^nc_j\cdot (\lambda_j)^{k+1}\cdot v_j(i)[/texx]

Entonces [texx]{  \displaystyle \lim_{k\to +\infty}\frac{ \left\|{e^{(k+1)}}\right\|_1}{ \left\|{e^{(k)}}\right\|_1}=\lim_{k\to +\infty}\frac{\sum_{i=1}^n \left |{e^{(k+1)}(i)}\right |}{\sum_{i=1}^n \left |{e^{(k)}(i)}\right |}=\lim_{k\to +\infty}\frac{\displaystyle \sum_{i=1}^n \left |{\sum_{j=1}^nc_j\cdot (\lambda_j)^{k+1}\cdot v_j(i)}\right |}{\displaystyle \sum_{i=1}^n \left |{\sum_{j=1}^nc_j\cdot (\lambda_j)^{k}\cdot v_j(i)}\right |}=\lim_{k\to +\infty}\frac{\displaystyle \sum_{i=1}^n \left |{\sum_{j=1}^nc_j\cdot \lambda_j\cdot \left(\frac{\lambda_j}{\lambda_n}\right)^{k}\cdot v_j(i)}\right |}{\displaystyle \sum_{i=1}^n \left |{\sum_{j=1}^nc_j\cdot \left(\frac{\lambda_j}{\lambda_n}\right)^{k}\cdot v_j(i)}\right |}  }[/texx] (en este paso lo que hice fue dividir numerador y denominador entre [texx]\left |{(\lambda_n)^k}\right |[/texx])

Esto fue para mostrar que [texx]\displaystyle \left(\frac{\lambda_j}{\lambda_n}\right)^k\rightarrow{}0[/texx] para [texx]j<n[/texx] pero para que eso sea cierto debe cumplirse [texx]\displaystyle \left |\frac{\lambda_j}{\lambda_n}\right |<1[/texx] (desigualdad estricta). Eso podría concluirlo si la letra del problema fuera [texx]\left |{\lambda_1}\right |<\left |{\lambda_2}\right |< \cdots<\left |{\lambda_n}\right |[/texx] pero es [texx]\leq[/texx] en todos los casos... :-\

Mi pregunta es: ¿está bien lo que hice? ¿hay alguna manera de arreglarlo, o la demostración va por otro lado?

Desde ya, muchas gracias.

PD. Pido disculpas a los moderadores, en especial a administrador por darle problemas nuevamente, ya que creo que este hilo lo más adecuado sería que estuviera en el subforo de métodos numéricos, si bien es cierto que está directamente relacionado con álgebra lineal.

Editado

HernanV:
Hay algo que yo no entiendo. En este paso [texx]\displaystyle \frac{e^{(k+1)}}{e^{(k)}}=\frac{\sum_{i=1}^nc_i\cdot (\lambda_i)^{k+1}v_i}{\sum_{i=1}^nc_i\cdot (\lambda_i)^kv_i}[/texx], ¿no estas intentando dividir vectores?.

pierrot:
Cita de: HernanV en 04/02/2012, 11:17:08 pm

Hay algo que yo no entiendo. En este paso [texx]\displaystyle \frac{e^{(k+1)}}{e^{(k)}}=\frac{\sum_{i=1}^nc_i\cdot (\lambda_i)^{k+1}v_i}{\sum_{i=1}^nc_i\cdot (\lambda_i)^kv_i}[/texx], ¿no estas intentando dividir vectores?.


Hola HernanV, antes que nada muchísimas gracias por contestar. Está perfecto lo que dices; como estaba antes, estaba mal expresado. Fijate ahora a ver que te parece. Igual mi idea sigue siendo la misma. El problema es que no puedo concluir. ¿Cómo hago?

pierrot:
Cita de: pabloN en 04/02/2012, 08:10:37 pm

Si se tiene la convergencia en la norma-1, se tiene la convergencia en cualquier otra norma ya que todas las normas en [texx]\mathbb{R}^n[/texx]  son equivalentes.


Eso es verdad. Si [texx]\displaystyle \frac{ \left\|{e^{(k+1)}}\right\|}{ \left\|{e^{(k)}}\right\|}[/texx] converge para alguna norma, entonces converge para cualquier otra norma (por equivalencia de normas). ¿Pero convergen a lo mismo? Creo que no tiene por qué. En dicho caso, tendría que haberse especificado la norma. Capaz que era la norma-2...

HernanV:
Te comento lo que veo, aunque no estoy seguro de que "el problema" este allí.

Sabes que el método es convergente si y sólo si el mayor autovalor de Q es en módulo menor que 1. O sea, eso lo sabes, lo podes dar por sentado que es así (¿verdad?).

Respecto de la norma, yo consideraría la norma infinito.

Navegación

[0] Índice de Mensajes

[#] Página Siguiente