Converxencia de algoritmos

Se temos un problema cunha solución real α, interésanos ter un criterio para decidir cal é o mellor algoritmo (estable) para buscar esa solución.

Hai dous tipos de algoritmos:

  • os que, dado un parámetro real h>0, constrúen unha aproximación x(h) de α onde, xeralmente, a aproximación é mellor cando h tende a 0; o algoritmo explicado na entrada anterior para calcular a derivada dunha función é deste tipo. Tamén están
  • os que, dado un parámetro natural n, constrúen unha aproximación x_n de α onde, xeralmente, a aproximación é mellor canto maior é n; o algoritmo da entrada anterior que calculaba as potencias de 1/3 entra nesta categoría se se usa para calcular α=0, xa que \displaystyle\lim_{n\rightarrow\infty}(1/3)^n=0, ¡aínda que na práctica debe desbotarse por ser inestable!.

Nesta entrada ocuparémonos do primeiro tipo, deixando para máis adiante o segundo. A primeira propiedade que todo algoritmo debe ter é a de converxer á solución correcta:

Un algoritmo dise converxente a α se \displaystyle\lim_{h\rightarrow 0^+}x(h)=\alpha.

Dados dous algoritmos converxentes, que constrúen aproximacións x(h) e y(h) de α, consideraremos mellor o que, a partir dun H dado, constrúa aproximacións mellores que o outro. Formalmente,

Dise que x(h) converxe a α tan rápidamente como y(h) se existen constantes reais C e H, tales que \left|x(h)-\alpha\right| \leq C\left|y(h)-\alpha\right| para todo 0<h<H.

É dicir, x(h) presenta a vantaxe de converxer tan rápidamente, ou máis, que y(h). Usando a notación de Landau, pódese escribir que x(h)-α = O(y(h)-α).

É util clasificar a rapidez dos algoritmos comparándoa coa converxencia polinomial:

Un algoritmo converxente a α dise de orde p se x(h)-\alpha=O(h^p).

A converxencia de orde 1 chámase linear e a de orde 2, cuadrática. En xeral, canto maior é o p, máis rápidamente converxe o algoritmo.

Estas converxencias poden probarse usando límites: se \displaystyle\lim_{h\rightarrow o^+}\frac{x(h)-\alpha}{h^p} é finito daquela a converxencia de x(h) é de orde p.

Exercicio: Demostra que x(h) = exp(-1/h) converxe a 0 con orde p, para calquer p natural.

Facendo un cambio de variable, vese que \displaystyle\lim_{h\rightarrow 0^+}\frac{e^{-1/h}}{h^p}=\lim_{x\rightarrow+\infty}\frac{x^p}{e^x}. Usando a regra de L’Hôpital p veces, obtense que o límite é cero.

Exercicio: Demostra que x(h) = h/log(h) converxe a 0 con orde 1, pero non con orde 2.

O límite \displaystyle \lim_{h\rightarrow o^+} \frac{h/\log(h)-0}{h} é cero, xa que logo, finito. Porén, pódese ver pola regra de L’Hôpital, que o límite \displaystyle\lim_{h\rightarrow o^+}\frac{h/\log(h)-0}{h^2} é infinito.

Na entrada seguinte, veremos estes mesmos conceptos para o segundo tipo de algoritmos.

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

One Response to Converxencia de algoritmos

  1. Pingback: Converxencia de algoritmos (e II) (previo) | fundmat

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