domingo, 10 de noviembre de 2013

Métodos iterativos para resolver ecuaciones (VI): el método del punto fijo


Otro método iterativo para la resolución numérica de ecuaciones es el denominado método del punto fijo. Este método e basa en convertir la ecuación f(x)=0 en otra de la forma g(x)=x, despejando alguna de las ocurrencias de x en la ecuación original.

En el ejemplo que estamos utilizando en esta serie de entradas
 
podemos despejar el término de mayor grado, quedando la ecuación

De forma gráfica podemos ver la ecuación g(x)=x como el punto de corte de la función g(x) con la recta y=x.
Comenzando en un punto inicial x[0], las iteraciones consisten en ir aplicando la función g(x) al resultado de la anterior iteración (x[1]=g(x[0]), x[2]=g(x[1]), ...) hasta que la diferencia entre dos iteraciones sucesivas sea tan pequeña como queramos. El método se llama del punto fijo porque una solución de la ecuación original debe cumplir que sea invariante al aplicarle la función g(x) (es decir, g(x)=x).

Este método algorítmicamente es muy sencillo, en wxMaxima se implementa con las instrucciones:
while abs(x[0]-x[1])>prec do(x[1]:x[0], x[0]:float(g(x[0])));
Donde x[0] es el punto inicial, prec la precisión definida y x[1] una variable auxiliar para controlar la diferencia entre iteraciones consecutivas.

Gráficamente podemos ver el recorrido del algoritmo en las siguientes animaciones de ejemplo:
 http://ma1.eii.us.es/miembros/ajimenez/AN/TEO/Anima/img_tema1/V9_AN_Tema1_an60.gif
http://ma1.eii.us.es/miembros/ajimenez/AN/TEO/Anima/img_tema1/V9_AN_Tema1_an66.gif

Sin embargo, el método del punto fijo tiene una gran exigencia para asegurar la convergencia: que la derivada de la función g(x) sea, en valor absoluto, menor que 1 en un entorno del punto de cada iteración.

Podemos observar gráficamente un caso de no convergencia en la siguiente animación:
http://ma1.eii.us.es/miembros/ajimenez/AN/TEO/Anima/img_tema1/V9_AN_Tema1_an72.gif


Incluimos esta consideración en el algoritmo (en negrita) y aprovechamos para ejecutarlo completo con el ejemplo de esta serie.

p(x):=x^5+3*x^4−2*x^3−x^2+5*x−3;
q(x):=(-3*x^4+2*x^3+x^2-5*x+3)^(1/5);
define(q1(x),diff(q(x),x,1));
prec:10^(-4);
x[0]:2;
x[1]:x[0]+2*prec;
while abs(x[0]-x[1])>prec do(if abs(q1(x[0]))>=1 then print("El método puede no converger"), x[1]:x[0], x[0]:float(q(x[0])));
    El método puede no converger
    done
float(x[0]);
    −3.350772866871043

Obsérvese que en una de las iteraciones la derivada del punto era mayor o igual que uno por lo que ha salido el mensaje avisando que el método puede no converger. A pesar de esto, el método ha convergido hacia una de las soluciones de la ecuación inicial.

Personalmente, de todos los métodos analizados hasta el momento en esta serie, el método del punto fijo es el que menos me ha gustado, pero siempre está bien conocer un método más para poder valorar su idoneidad en función de cada caso.

Para finalizar esta entrada dejo algunas preguntas abiertas por si alguien quiere investigar un poco más. ¿Variando el punto inicial el método converge hacia otra solución? ¿Qué pasa si despejamos la x de cualquier otro término de la ecuación?

No hay comentarios: