2.3 Método del Punto fijo

Punto fijo

Ejercicio

Analítico

1. Método del Punto fijo - ¿Qué es?

Referencia: Burden 2.2 p41, Chapra 6.1 p143, Rodríguez 3.2 p44

El método del punto fijo es un método abierto, también llamado de iteración de un punto o sustitución sucesiva, que reordena la ecuación planteada para raíces de ecuaciones

f(x) = 0

separando una x al lado izquierdo de la igualdad.

x = g(x)

Esto permite buscar la intersección entre la recta Identidad y=x y la curva g(x), que es lo que quedó del lado derecho de la igualdad.
Una representación gráfica del proceso de muestra en la gráfica.

Observe que la raíz de f(x) se encuentra en el mismo valor de x donde ocurre la intersección entre la recta identidad y=x , en color verde, y la función g(x), en color naranja. Como referencia, se usa la linea vertical en x=raíz en color morado.

El método consiste en establecer un punto inicial x₀ para la búsqueda, a partir del cual se calcula el valor g(x₀). En la siguiente iteración el nuevo valor para x es g(x₀), que se refleja en la recta identidad y nuevamente se usa para calcular g(x).

El resultado iterativo se muestra en la figura animada, donde se observa que el resultado es convergente.

1.1 Ejemplos en gráficas

Se muestran algunos ejemplos para destacar lo indicado de forma gráfica.

Ejemplo 1

f(x):e^{-x} - x = 0

se reordena para tener:

x = e^{-x}

g(x) = e^{-x}

Ejemplo 2

f(x): x^2 - 2x -3 = 0

se reordena para tener:

x = \frac {x^2 - 3}{2}

g(x) = \frac {x^2 - 3}{2}

Ejemplo 3

f(x): \sin (x) = 0

puede ser complicado despejar x, por lo que se simplifica el proceso sumando x en ambos lados.

x = \sin (x) + x

g(x) = \sin (x) + x

El método proporciona una fórmula para predecir un valor nuevo de x en función del valor anterior:

x_{i+1} = g(x_i)

con error aproximado calculado como:

\epsilon_a = \left| \frac{x_{i+1} - x_i}{x_{i+1}} \right| 100\%

Tarea

Plantee como usar los siguientes conceptos:

¿cuál sería el valor de tolerancia?
¿parámetros de inicio?
compare con con otro método conocido
Revisar el resultado cuando no se cumple que |g'(x)|<1

2. Ejercicio

Referencia: Burden 2.2 p41, Chapra 6.1 p143, Rodríguez 3.2 p44

Encontrar la solución a la ecuación, usando el método del punto fijo, considerando tolerancia de 0.001

f(x): e^{-x} - x = 0

3. Desarrollo Analítico - ejemplo paso a paso

Al igual que los métodos anteriores, es conveniente determinar el intervalo [a,b] donde es posible evaluar f(x). Se revisa si hay cambio de signo en el intervalo para buscar una raíz. Para el ejemplo, el intervalo de observación será [0,1], pues f(0)=1 es positivo y f(1)=-0.63 es negativo.

Para el punto fijo, se reordena la ecuación para para tener una ecuación con la variable independiente separada. Se obtiene por un lado la recta identidad y=x, por otro se tiene la función g(x).

f(x): e^{-x} - x = 0

x = e^{-x}

g(x) = e^{-x}

Se buscará la intersección entre las dos expresiones .

Se puede iniciar la búsqueda por uno de los extremos del intervalo [a,b].

iteración 1

- iniciando desde el extremo izquierdo c=a,

c = 0

- se determina el valor nuevo de gc=g(c) ,

g(c) = g(0) = e^{-0} = 1

- se determina la diferencia de la aproximación o error = |gc-c|

tramo = |1-0| = 1

- se proyecta en la recta identidad, como el nuevo punto de evaluación

c = g(c) = 1

- se repite el proceso para el nuevo valor de c, hasta que el error sea menor al tolerado. En caso que el proceso no converge, se utiliza un contador de iteraciones máximo, para evitar tener un bucle infinito.

iteración 2

c = 1

g(c) = g(1) = e^{-1} = 0.3678

tramo =|0.3678 - 1|= 0.6322

El nuevo valor de c=0.3678

Se observa también que el valor absoluto de tramo disminuye entre iteraciones.

iteración 3

c = 0.3678

g(c) = e^{-0.3678} = 0.6922

tramo =|0.6922-0.3678|= 0.3244

El nuevo valor de c=0.6922

Se observa también que el valor absoluto de tramo disminuye en cada iteración, por lo que el método es convergente.

La tabla resumen de las iteraciones:

iteración	c	g(c)	\|tramo\|
1	0	1.0	1
2	1.0	*0.3678*	0.6322
3	*0.3678*	0.6922	0.3244
4	0.6922	...
5

El proceso realizado en la tabla se muestra en la gráfica, para una función que converge.

Ejemplo: Método Punto fijo No converge

Cuando la 'x' a separar en la expresión f(x) es otra, el resultado no siempre será convergente. Si para el ejercicio anterior se hubiese despejado la 'x' en el exponencial, la expresión g(x) se obtiene como:

f(x): e^{-x} - x = 0

e^{-x} = x

\ln\Big(e^{-x}\Big) = \ln(x)

-x= \ln(x)

x= -\ln(x)

Al revisar la gráfica del algoritmo se observa que también se cumple que la raíz de f(x) coincide en el valor x con la intersección entre la identidad y g(x).

Sin embargo al realizar las iteraciones se tiene que:

iteración 1

c = 0.5
gc = -ln(0.5) = 0.6931
tramo = | 0.6931-0.5| =0.1931

iteración 2

c = 0.6931
gc = -ln(0.6931) = 0.3665
tramo = | 0.3665-0.6931| = 0.3266

iteración 3

c = 0.3665
gc = -ln(0.3665) = 1.0037
tramo = | 1.0037-0.3665| = 0.6372

Se observa que el tramo o error aumenta en cada iteración, con lo que se concluye que de esta forma, la aplicación del método no es convergente.

4. Algoritmo en Python para el método del Punto Fijo

El algoritmo en Python requiere: la función gx, el punto inicial, la tolerancia, y el número de iteraciones máxima, iteramax. En el algoritmo se añade f(x) como una referencia para la gráfica del método en el intervalo.

El resultado del algoritmo se presenta como:

raíz en:  0.5669089119214953
errado :  0.0006477254067881466
itera  :  14

Instrucciones en Python

# Método del punto fijo
# g(x) se obtiene al despejar una x de f(x)
# el valor inicial c, se puede revisar con la gráfica
import numpy as np

# INGRESO
fx = lambda x: np.exp(-x) - x
gx = lambda x: np.exp(-x)

c = 0  # valor inicial
tolera = 0.001
iteramax = 40

# PROCEDIMIENTO
tramo = 2*tolera # al menos una iteracion
i = 0  # iteración inicial
while tramo>=tolera and i<iteramax:
    gc = gx(c)
    tramo = abs(gc-c)
    c = gc
    i = i + 1

if (i>=iteramax): # Valida convergencia
    c = np.nan

# SALIDA
print('raíz en: ', c)
print('errado : ', tramo)
print('itera  : ', i)

Para obtener la gráfica básica se determinan los puntos para cada función fx y gx. Como los valores de c y gc cambiaron durante el algoritmo, para la siguiente sección es necesario volver a escribirlos u obtener una copia de los valores en otra variable para reutilizarlos en ésta sección.

5. Gráfica en Python

Se añaden las siguiente instrucciones al algoritmo anterior:

# GRAFICA ------------------------
import matplotlib.pyplot as plt
 
a = 0  # intervalo de gráfica en [a,b]
b = 1
muestras = 21
titulo = 'Punto Fijo'
 
# calcula los puntos para fx y gx
xk = np.linspace(a,b,muestras)
fk = fx(xk)
gk = gx(xk)
 
plt.plot(xk,fk, label='f(x)',
         linestyle='dashed')
plt.plot(xk,gk, label='g(x)')
plt.plot(xk,xk, label='y=x')
plt.plot(c,c, 'o')
plt.axvline(c, color='magenta',
            linestyle='dotted')
plt.axhline(0)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title(titulo)
plt.grid()
plt.legend()
plt.tight_layout()
plt.show()

6. Algoritmo en Python como Función para el Método del Punto Fijo

El resultado del algoritmo como una función y mostrando la tabla de resultados por iteraciones es:

Método del Punto Fijo
i ['xi', 'gi', 'tramo']
0 [0. 1. 1.]
1 [1.       0.367879 0.632121]
2 [0.367879 0.692201 0.324321]
3 [0.692201 0.500474 0.191727]
4 [0.500474 0.606244 0.10577 ]
5 [0.606244 0.545396 0.060848]
6 [0.545396 0.579612 0.034217]
7 [0.579612 0.560115 0.019497]
8 [0.560115 0.571143 0.011028]
9 [0.571143 0.564879 0.006264]
10 [0.564879 0.568429 0.003549]
11 [0.568429 0.566415 0.002014]
12 [0.566415 0.567557 0.001142]
13 [0.567557 0.566909 0.000648]
Método del Punto Fijo
iteraciones: 14
raíz en:  0.5669089119214953
errado: 0.0006477254067881466

Instrucciones en Python

# Método del punto fijo
# g(x) se obtiene al despejar una x de f(x)
# el valor inicial c, se puede revisar con la gráfica
import numpy as np

def puntofijo(gx,c,tolera,iteramax=50,vertabla=True, precision=6):
    """
    g(x) se obtiene al despejar una x de f(x)
    máximo de iteraciones predeterminado: iteramax
    si no converge hasta iteramax iteraciones
    la respuesta es NaN (Not a Number)
    """
    itera = 0 # iteración inicial
    tramo = 2*tolera # al menos una iteracion

    tabla=[]
    if vertabla==True:
        print('Método del Punto Fijo')
        print('i', ['xi','gi','tramo'])
        np.set_printoptions(precision)
    
    while (tramo>=tolera and itera<=iteramax):
        gc = gx(c)
        tramo = abs(gc-c)
        
        unafila = np.array([c,gc,tramo])
        tabla.append(unafila)
        if vertabla==True:
            print(itera,unafila)
        c = gc
        itera = itera + 1
    respuesta = c
    # Valida respuesta
    if itera>=iteramax:
        respuesta = np.nan
        print('itera: ',itera,
              'No converge,se alcanzó el máximo de iteraciones')
    tabla = np.array(tabla,dtype=float)
    return(respuesta,tabla)

# PROGRAMA ----------------------
# INGRESO
fx = lambda x: np.exp(-x) - x
gx = lambda x: np.exp(-x)
 
c = 0  # valor inicial
tolera = 0.001
iteramax = 15
 
# PROCEDIMIENTO
c,tabla = puntofijo(gx,c,tolera,
                    iteramax,vertabla=True)
n = len(tabla)
errado = tabla[n-1,2]

# SALIDA
print('Método del Punto Fijo')
print('iteraciones:',n)
print('raíz en: ', c)
print('errado:',errado)

7. Gráfica en Python para la función de punto fijo

La sección para la gráfica requiere el intervalo [a,b] para el eje x, además presenta las variantes:

Las muestras para la gráfica de f(x), con la marca de un punto de la raíz.

Para el caso de realizar la gráfica de una iteración particular, usar la variable itera_graf. Por ejemplo para las gráficas presentadas en cada iteración en la sección de desarrollo analítico.

Las instrucciones que se añaden al algoritmo como función son:

# GRAFICA --------------------
import matplotlib.pyplot as plt
 
a = 0  # intervalo de gráfica en [a,b]
b = 1
muestras = 21
itera_graf = 2 #n-1 # iteración en gráfica
titulo = 'Punto Fijo'
 
# calcula los puntos para fx y gx
xk = np.linspace(a,b,muestras)
fk = fx(xk)
gk = gx(xk)

plt.plot(xk,fk, label='f(x)',
         linestyle='dashed')
plt.plot(xk,gk, label='g(x)')
plt.plot(xk,xk, label='y=x')

if itera_graf==(n-1): # iteración final
    plt.plot(c,c,'D',color='orange',label='c')

    plt.axvline(c, color='magenta',
                linestyle='dotted')
if itera_graf<(n-1): # una iteración en gráfica
    [c,gc,tramo] = tabla[itera_graf]
    [c1,gc1,tramo1] = tabla[itera_graf+1]
    titulo = titulo + ', itera='+str(itera_graf)
    plt.plot(c,c,'o',color='red',label='c')
    plt.plot(c,gc,'o',color='green',label='g(c)')
    plt.plot(gc,gc,'o',color='orange',label='c[i+1]')

    dx = c1-c # largo de flecha
    dy = gc-c
    plt.arrow(c,c, 0,dy,
              length_includes_head = True,
              head_width = 0.05*abs(dy),
              head_length = 0.1*abs(dy))
    plt.arrow(c,gc,dx,0,
              length_includes_head = True,
              head_width = 0.05*abs(dx),
              head_length = 0.1*abs(dx))
    
plt.axhline(0,color='gray')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title(titulo)
plt.grid()
plt.legend()
plt.tight_layout()
plt.show()

8. Función en librería Scipy.optimize.fixed_point

El método del punto fijo se encuentra disponible en la librería Scipy, en la sección de optimización. Requiere la función g(x), el punto inicial c, la tolerancia y el número máximo de iteraciones:

>>> import numpy as np
>>> import scipy as sp
>>> gx = lambda x: np.exp(-x)
>>> c = 0
>>> sp.optimize.fixed_point(gx,c,xtol=0.001,maxiter=15)
array(0.5671432948307147)

El valor predeterminado de iteraciones máxima es 500 y la tolerancia predeterminada es xtol=1e-08

https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fixed_point.html

Tarea

Revisar lo que sucede cuando el valor inicial a esta a la derecha de la raíz.
Validar que la función converge, revisando que |g'(x)|<1, o que la función g(x) tenga pendiente menor a pendiente de la recta identidad.

2.3 Método del Punto fijo

1. Método del Punto fijo - ¿Qué es?

1.1 Ejemplos en gráficas

Ejemplo 1

Ejemplo 2

Ejemplo 3

2. Ejercicio

3. Desarrollo Analítico - ejemplo paso a paso

Ejemplo: Método Punto fijo No converge

4. Algoritmo en Python para el método del Punto Fijo

5. Gráfica en Python

6. Algoritmo en Python como Función para el Método del Punto Fijo

7. Gráfica en Python para la función de punto fijo

8. Función en librería Scipy.optimize.fixed_point

Métodos Numéricos

Análisis Numérico