Análisis Numérico Iteración de Punto Fijo

UNIVERSIDAD AUTÓNOMA DE NUEVO LEÓN

FACULTAD DE CIENCIAS FÍSICO-MATEMÁTICAS

José Alfredo Gallegos Chavarría (1383375)

Iteración de Punto Fijo

SAN NICOLÁS DE LOS GARZA, 16 DE MARZO DE 2012

Análisis Numérico
Iteración de Punto Fijo

Introducción

        El método de Iteración de Punto Fijo (también conocido como el método de aproximaciones sucesivas) es un método usable para obtener una raíz para una determinada ecuación f(x) = 0 no necesariamente lineal, donde f(x) es una función real sobre x y siempre y cuando se cumplan algunas reglas de convergencia. El método de Punto Fijo realiza cálculos iterativos para encontrar un “punto fijo” en la gráfica de la ecuación (básicamente una intersección entre gráficas, como veremos más a detalle dentro de poco), para lo cual utiliza una ligera transformación del polinomio original (pasar de f(x) = 0 a g(x) = x) y una aproximación inicial dada o “tanteada” del valor del polinomio al evaluarlo en el punto fijo.

Definimos, para este método, un punto fijo, para una cierta función g, como un valor determinado a, para el cual se cumple que a = g(a) (de ahí la necesidad de transformar f(x) = 0 a g(x) = x).

[pic 1]

Por ejemplo, en la imagen anterior tenemos trazadas las gráficas de y = x y y = x2. Dese cuenta como en los puntos (0, 0), y (1, 1) tenemos casos en que se cumple, para ambas gráficas que x = f(x), si consideramos cada miembro por separado como una función. Estos pueden ser considerados puntos fijos, y el análisis del mismo nos puede ayudar a encontrar raíces (como en el caso de (0, 0), en donde tenemos una intersección con el eje X) para polinomios de grados distintos a meramente primer y segundo grado.

La existencia del dicho para una función en particular se determina por medio del Teorema del Punto Fijo:

• Si…

• g es continua en [a, b], con a, b ∈ R, y
• g(x) ∈ [a, b] ∀ x ∈ [a, b]

• entonces g tiene por lo menos un punto fijo en [a, b], y…
• Si además g’(x) existe para todo x ∈ [a, b], y |g’(x)| ≤ K < 1 para todo x ∈ [a, b] con K constante…
• entonces g tiene un único punto fijo x ∈ [a, b]

En este tratado explicaré algunos datos y haré observaciones sobre el método de iteración de punto fijo, e igualmente presentaré un programa en C++ que permite encontrar raíces de polinomios por medio del método, del cual usted debió haber recibido una copia física. Se explican también las decisiones de diseño y lógica del programa.

Notas Históricas

El método ya era conocido por varias civilizaciones antiguas, como la babilónica (año 1700 a. C.) o la arábiga (circa 1400 d. C.). En este último caso, por ejemplo, el eminente Jamshid al-Kashi elaboró una tabla trigonométrica con iteraciones de punto fijo, así como la cultura de Babilonia ya conocía una aproximación adecuadamente exacta al valor de la raíz cuadrada de 2 por medio del método.

Explicación y algoritmo del método

 El método de Punto Fijo tiene el siguiente algoritmo:

1. Dada una ecuación no necesariamente lineal (grado n) f(x) = 0, para encontrar su raíz real, transforme a la forma:

[pic 2]

(Es posible lograr esta transformación de varias maneras: despeje, sumar x en cada miembro de la ecuación, u otras operaciones elementales)

1. Después, dada una aproximación de la raíz inicial x0, obtenida por tanteo, obtenemos g(x0). x0 debe cumplir el criterio de convergencia:

[pic 3]

El resultado de dicha operación es x1:

[pic 4]

 para i = 0, 1, 2…[pic 5]

1. Realice cálculos sucesivos como sea deseado para obtener más aproximaciones del punto fijo. Dichos cálculos pueden resultar en dos casos:

1. xi+1 = xi, en cuyo caso ya hemos encontrado la raíz de la ecuación, o
2. xi+1 ≠ xi en cuyo caso se realiza una nueva iteración del proceso usando el resultado de xi+1 hasta que sea el primer caso.

Podemos introducir la noción de un error aproximado entre iteraciones del método, que corresponde con la forma tradicional del error que hemos usado para otros métodos numéricos en casos anteriores:

[pic 6]

El cual es un porcentaje el cual podemos usar como un margen de error; considerar que si la evaluación de un xi determinado se encuentra en el rango de la tolerancia deseada de error en el cálculo se ha llegado o no a una solución aceptable.

Análisis programático

He programado una aplicación pequeña que permite ver el método en acción, lo cual realicé usando el lenguaje de programación C/C++ debido a su versatilidad, increíble madurez y soporte de terceros tanto en el lenguaje, su sintaxis y sus recursos y librerías, gran portabilidad y por el hecho de que es el lenguaje que me resulta favorito. Aparte, pretendo llevar uniformidad con los trabajos presentados anteriormente en el curso en lo que consta a estilo de programación y lenguaje elegido.

El producto presentado es completamente de mi diseño y edición; no obstante un documento disponible en el internet sobre el método de iteración de Punto Fijo incluye una implementación en Javascript, que me resultó de inspiración al hacer mi programa, si bien no es código abierto. El documento es de la autoría del maestro Tomeu Barceló del Departamento de Matemáticas de la Universidad Autónoma de Madrid, y se incluye como referencia al final de mi tratado.

Se ha limitado otra vez el grado máximo del polinomio posible de tratar en el programa a 5 debido a que casos superiores pueden resultar de excesiva complejidad computacional, debido a las operaciones recursivas hechas y al número de datos manejados. Por una similar razón, se ha limitado el número máximo de iteraciones del programa a 75, para evitar procesos demasiado largos. Igualmente, el programa se ha diseñado alrededor de la solución de raíces de polinomios en términos de potencias de x, debido a la complejidad alrededor de implementar un parseador de texto de la entrada estándar en nuestro programa, que está en una aplicación de consola, para manejar términos exponenciales/logarítmicos/trigonométricos de x y el hecho de que requeriría la implementación de funcionalidades de librerías de terceros.

...