Algoritmos estables

Calquer método numérico é susceptible de sufrir os tipos de erro comentados nos preliminares de cálculo numérico. Consideremos, por exemplo, unha fórmula para aproximar a derivada de f(x). Para h positivo, tomamos

\displaystyle\frac{f(x+h)-f(x)}h

como aproximación de f'(x). Por unha banda, está o erro do método numérico: a formula anterior só e unha aproximación de f'(x), mellor canto máis pequeno é h. Pola outra, o erro computacional medra ao reducirse h, por cancelación das cifras significativas no numerador.

Podemos velo coa función y = x² no contorno de x=1. Pintamos nunha gráfica de escala logarítmica o erro relativo cometido respecto do valor exacto , y'(1)=2, para distintos valores de h:

sage: var('h')
sage: plot_loglog(abs(2-(f(1+h)-f(1))/h)/2, (h,1.e-13,0.1))

erro_derivada_sage

Mentras o o erro dominante é o do método numérico, que se reduce linearmente. Para h moi pequenos, o erro computacional domina ao anterior.

Aínda que calquer método numérico pode verse afectado, hai algúns especialmente nefastos: os algoritmos inestables. Denomínanse así aos algoritmos que, en cada etapa, amplifican os erros cometidos na etapa anterior.

Como exemplo, usemos a seguinte relación de recurrencia:

\left\{\begin{array}{l}\displaystyle x_0=1, \ \ x_1=\frac 13,\\ \displaystyle x_{n+1}=\frac{13}3x_n-\frac 43 x_{n-1},\ \ n\geq 1.\end{array}\right.

Exercicio: Demostra por inducción que x_n=(1/3)^n.

Aínda que matemáticamente a relación devolve as potencias de 1/3, implementada nun ordenador, dá lugar a un algoritmo inestable:

sage: x = [1., 1/3.]*10
sage: for n in [1..18]:
....: x[n+1] = 13*x[n]/3-4*x[n-1]/3.
sage: [100*abs((1/3.)**n-x[n])/x[n] for n in range(len(x))]

A seguinte táboa mostra o valor obtido e o relativo cometido en cada iteración:

Iterante Valor Erro abs. Erro rel.
x_0 1 0 0%
x_1 0.33333 0 0%
x_2 0.11111 5.5511e-17 4.99e-14%
x_3 0.037037 2.2898e-16 6.18e-13%
x_{15} 7.3411e-08 3.7194e-09 5.06%
x_{16} 3.8108e-08 1.4878e-08 39.04%

O algoritmo resultante é inestable: o erro no cálculo de x_{n-1} e x_n amplifícase ao multiplicarse por 13/3 e 4/3, números maiores que un.

Na seguinte entrada tentaremos dar resposta á seguinte pregunta: se temos dous algoritmos estables para buscar a solución dun problema, ¿cal deles é mellor?

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

3 Responses to Algoritmos estables

  1. Pingback: Perda de cifras significativas | fundmat

  2. Pingback: Converxencia de algoritmos (novo) | fundmat

  3. Pingback: Diferenzas entre o cálculo simbólico e o numérico | 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