Converxencia de algoritmos (e II) (previo)

Na entrada anterior analizamos os algoritmos con solución dependente de h real. Falemos agora dos algoritmos que constrúen unha sucesión x_n que aproxima α cando n tende a infinito. Empezamos por definir a converxencia:

Un algoritmo dise converxente a α se \displaystyle\lim_{n\rightarrow +\infty}x_n=\alpha.

Para ver que a sucesión x_n tende a α, é suficiente con ver que \displaystyle \lim_{n\rightarrow +\infty}x_n=\alpha, considerando a n como variable real.

Para comparar algoritmos converxentes que constrúen aproximacións x_n e y_n de α:

Dise que x_n converxe a α tan rápidamente como y_n se existen constantes C e N, tales que \left|x_n-\alpha\right| \leq C\left|y_n-\alpha\right| para todo n>N.

notación de Landau permite neste caso escribir que x_n-\alpha=O(y_n-\alpha). A orde de converxencia neste tipo de algoritmos defínese así:

Un algoritmo converxente a α dise de orde p se existen constantes C e N tales que |x_{n+1}-\alpha|\leq C\left|x_n-\alpha\right|^p para todo n>N.

Contrariamente á definición que demos para o outro tipo de algoritmos, aquí a orde de converxencia implica a reducción do erro entre cada dúas iteracións consecutivas, seguindo unha potencia p-ésima. Para probar a converxencia, bastaría ver que \displaystyle\frac{x_{n+1}-\alpha}{(x_n-\alpha)^p} está limitado cando n tende a infinito.

Exercicio: O algoritmo que produce a sucesión \displaystyle\frac{n+1}{n^2} para aproximar α=0 converxe linearmente.

Para calcular o límite de \displaystyle\frac{(n+2)/(n+1)^2}{(n+1)/n^2}=\frac{(n+2)n^2}{(n+1)^3} cando n tende a infinito, dividimos numerador e denominador por n^3 para eliminar a indeterminación, obtendo como resultado o valor  1.

Exercicio: Demostra que o algoritmo que produce a sucesión \displaystyle\frac{5}{n}+\exp(-n) para aproximar α=0 converxe linearmente.

Como a exponencial é crecente, exp(-(n+1))<exp(-n); polas propiedades da desigualdade, 1/(n+1)<1/n. Por tanto, tense que |xn+1-0|<|xn-0|, para calquer n.

Bibliografía

A bibliografía recomendada para este apartado de conceptos básicos de cálculo numérico é:

Advertisements
Esta entrada foi publicada en Cálculo numérico. Ligazón permanente.

Deixar unha resposta

introduce os teu datos ou preme nunha das iconas:

Logotipo de WordPress.com

Estás a comentar desde a túa conta de WordPress.com. Sair / Cambiar )

Twitter picture

Estás a comentar desde a túa conta de Twitter. Sair / Cambiar )

Facebook photo

Estás a comentar desde a túa conta de Facebook. Sair / Cambiar )

Google+ photo

Estás a comentar desde a túa conta de Google+. Sair / Cambiar )

Conectando a %s