Iteración de punto fijo

La idea

Muchas ecuaciones se pueden reescribir en la forma x = g(x). Un punto que cumple esa igualdad se llama punto fijo de g, y la manera más directa de buscarlo es iterar: xₙ₊₁ = g(xₙ). Si la sucesión converge y g es continua, su límite es un punto fijo, es decir, una solución de la ecuación original. Escribir x² − x − 2 = 0 como x = √(x + 2) o como x = x² − 2 son dos elecciones válidas de g, pero con comportamientos opuestos: la primera converge a 2 y la segunda huye de él.

El teorema del punto fijo aclara cuál funciona: si g es continua, lleva un intervalo [a, b] dentro de sí mismo y |g'(x)| ≤ k < 1 en él, la iteración converge al único punto fijo desde cualquier x₀ del intervalo, con error eₙ ≤ kⁿ e₀. La condición esencial es |g'(r)| < 1: cuanto más cerca de 0 esté la pendiente en el punto fijo, más rápido converge (la convergencia es lineal con razón |g'(r)|). Si |g'(r)| > 1 el punto fijo es repulsor y la iteración se aleja aunque empiece a un paso de él.

El diagrama de telaraña lo hace visible: desde (x₀, 0) se sube hasta la curva y = g(x), se va en horizontal hasta la diagonal y = x, y se repite. Cuando |g'| < 1 la telaraña se enrolla hacia el punto fijo (en espiral si g' es negativa, en escalera si es positiva); cuando |g'| > 1 se desenrolla hacia fuera. El método de Newton es un caso particular con g(x) = x − f(x)/f'(x), que cumple g'(r) = 0: por eso converge tan deprisa. Esta misma idea, iterar una aplicación contractiva, es la base de PageRank, de las cadenas de Markov y de la programación dinámica.

Fórmulas clave

• Iteraciónxₙ₊₁ = g(xₙ)
• Condición de convergencia local|g'(r)| < 1 ⇒ converge para x₀ cercano a r
• Cota del error|xₙ − r| ≤ kⁿ |x₀ − r|, k = máx |g'|
• Razón de convergenciaeₙ₊₁ / eₙ → |g'(r)|
• Newton como punto fijog(x) = x − f(x)/f'(x), g'(r) = 0

Dónde se aplica

El algoritmo PageRank de Google es una iteración de punto fijo sobre el vector de importancia de las páginas: se aplica la matriz de enlaces hasta que el vector deja de cambiar. En economía, el equilibrio de un mercado (el precio en que oferta e igualan demanda) se calcula iterando la función de respuesta, y en teoría de juegos el equilibrio de Nash es un punto fijo de la mejor respuesta de cada jugador. En ingeniería de fluidos, el factor de fricción de Colebrook se obtiene iterando la fórmula implícita, y en aprendizaje automático el algoritmo EM y la ecuación de Bellman del aprendizaje por refuerzo son iteraciones contractivas.

Con programación (Python)

import math

def punto_fijo(g, x0, nombre, max_iter=60, tol=1e-8, cada=1):
    print(nombre)
    x = x0
    for n in range(1, max_iter + 1):
        xn = g(x)
        if not math.isfinite(xn) or abs(xn) > 1e6:
            print("  ¡diverge en la iteración", n, "!")
            return None
        if n % cada == 0 or abs(xn - x) < tol:
            print(f"  n={n:2d}  x={xn:.10f}")
        if abs(xn - x) < tol:
            print("  convergió en", n, "iteraciones")
            return xn
        x = xn
    return x

# x² − x − 2 = 0 (raíces 2 y −1) escrita de dos maneras como x = g(x)
punto_fijo(lambda x: math.sqrt(x + 2), 3.0, "g1(x) = sqrt(x+2), g1'(2) = 0.25")
punto_fijo(lambda x: x*x - 2, 2.1, "g2(x) = x^2 - 2, g2'(2) = 4", max_iter=8)
c = punto_fijo(math.cos, 1.0, "g3(x) = cos x", max_iter=100, cada=10)
print("cos(c) - c =", math.cos(c) - c)

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Método de Newton-Raphson · Método de bisección · Cadenas de Markov