Algoritmos estables (previo)

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:

h = 10.^(-13:-1);
f = @(x) x.^2;
loglog(h, abs(2-(f(1+h)-f(1))./h)/2)

Se h>1e-8, o erro dominante é o do método numérico, que se reduce linearmente. Para h máis pequeno, 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ínase así ao algoritmo que, en cada etapa, amplifica 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:

x=zeros(1,16); x(1)=1; x(2)=1/3;
for n=2:15  
  x(n+1) = 13*x(n)/3-4*x(n-1)/3;
end

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

Iterante Valor Erro abs. Erro rel.
x_1 1 0 0%
x_2 0.33333 0 0%
x_3 0.11111 5.5511e-17 4.99e-14%
x_4 0.037037 2.2204e-16 5.99e-13%
x_{15} 7.3411e-08 3.7194e-09 5.33%
x_{16} 3.8108e-08 1.4878e-08 64.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.

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