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

0 Usuarios y 2 Visitantes están viendo este tema.

05 Febrero, 2012, 12:10 am
Leído 2799 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Supongamos que se quiere resolver el sistema \( Ax=b \) (se asume \( A \) no singular) mediante cierto método iterativo dado por:

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

en donde la matriz \( M \) es invertible.

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

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

\( \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} \)

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

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

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

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

Pruebe que si \( \displaystyle q^{(k)}=\frac{ \left\|{e^{(k+1)}}\right\|}{ \left\|{e^{(k)}}\right\|} \) se cumple \( q^{(k)}\xrightarrow[k\xrightarrow{}+\infty]\,{\left |{\lambda_n}\right |} \) (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 \( e^{(k)}=Q\cdot e^{(k-1)}=Q\cdot Q\cdot e^{(k-2)}=\cdots =Q^k\cdot e^{(0)} \). Ahora al error en el paso 0 lo puedo expresar como combinación lineal de los vectores propios: \( e^{(0)}=\displaystyle \sum_{j=1}^nc_jv_j \). Entonces \( \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 \). Entonces llegamos a que:

\( \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 \)

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

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

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

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

Entonces \( {  \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 |}  } \) (en este paso lo que hice fue dividir numerador y denominador entre \( \left |{(\lambda_n)^k}\right | \))

Esto fue para mostrar que \( \displaystyle \left(\frac{\lambda_j}{\lambda_n}\right)^k\rightarrow{}0 \) para \( j<n \) pero para que eso sea cierto debe cumplirse \( \displaystyle \left |\frac{\lambda_j}{\lambda_n}\right |<1 \) (desigualdad estricta). Eso podría concluirlo si la letra del problema fuera \( \left |{\lambda_1}\right |<\left |{\lambda_2}\right |< \cdots<\left |{\lambda_n}\right | \) pero es \( \leq \) 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
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Febrero, 2012, 03:17 am
Respuesta #1

HernanV

  • FIUBA
  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,059
  • Karma: +2/-0
  • Sexo: Masculino
Hay algo que yo no entiendo. En este paso \( \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} \), ¿no estas intentando dividir vectores?.
\( \displaystyle\vec{\nabla}\times\mathbf{E}+\frac{\partial\mathbf{B}}{\partial t}=\vec{0} \)

05 Febrero, 2012, 03:11 pm
Respuesta #2

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hay algo que yo no entiendo. En este paso \( \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} \), ¿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?
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Febrero, 2012, 03:36 pm
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Si se tiene la convergencia en la norma-1, se tiene la convergencia en cualquier otra norma ya que todas las normas en \( \mathbb{R}^n \)  son equivalentes.

Eso es verdad. Si \( \displaystyle \frac{ \left\|{e^{(k+1)}}\right\|}{ \left\|{e^{(k)}}\right\|} \) 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...
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Febrero, 2012, 03:43 pm
Respuesta #4

HernanV

  • FIUBA
  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,059
  • Karma: +2/-0
  • Sexo: Masculino
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.
\( \displaystyle\vec{\nabla}\times\mathbf{E}+\frac{\partial\mathbf{B}}{\partial t}=\vec{0} \)

05 Febrero, 2012, 03:55 pm
Respuesta #5

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
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?).

Sí, pero creo que el ejercicio apunta a algo más general. En la letra no se dice en ningún momento que el radio espectral es menor a 1 (no es parte de las hipótesis). El radio espectral prodría ser 5 por ejemplo. En dicho caso lo que pasa es que en cada iteración el error se hace 5 veces más grande que en la iteración anterior. Entonces lógicamente no converge. Lo único "extra" que aparece en la letra es la mención de los vectores propios, algo así como diciendo: "esto tiene que ser usado". Interpreté que venía por el lado de expresar \( e^{(0)} \) como combinación lineal de los \( v_i \), pero no sé si será así.

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

¿Por qué dices la norma infinito? Si no indica nada, capaz que es la norma usual, o sea, la norma-2.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

08 Febrero, 2012, 03:06 pm
Respuesta #6

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

10 Febrero, 2012, 11:13 am
Respuesta #7

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print