CLASE 29.07¶

Metodos para encontrar raices.¶

El método de bisección parte de un intervalo $[a,b]$ donde $f(a)f(b)<0$ y usa la fórmula:

$$ x = \frac{a+b}{2} $$

Luego se evalúa:

$$ \text{Si } f(a)f(x) < 0 \Rightarrow b = x $$

$$ \text{Caso contrario } a = x $$

Esto se repite hasta que $|b-a| < \text{tolerancia}$ o $f(x)=0$.

Resumido:

  1. Calcular el punto medio: $x = (a+b)/2$.
  2. Si $f(a)f(x) < 0$, la raíz está en $[a,x]$ ⇒ $b = x$.
  3. Si no, la raíz está en $[x,b]$ ⇒ $a = x$.

Secante¶

El método de la secante para encontrar raíces de una función $f(x) = 0$ utiliza la fórmula:

$$ x_{k+1} = x_k - f(x_k)\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} $$

O también se puede escribir como:

$$ x_{k+1} = \frac{x_{k-1} f(x_k) - x_k f(x_{k-1})}{f(x_k) - f(x_{k-1})} $$

  • Necesitas dos aproximaciones iniciales $x_{k-1}$ y $x_k$. sino
  • A partir de ellas calculas $x_{k+1}$ y sigues iterando hasta cumplir la tolerancia.

El método de Newton-Raphson para encontrar raíces de una función $f(x) = 0$ usa la fórmula:

$$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} $$

¿Dónde puede dar error?¶

  1. Si $f'(x_k) = 0$

    • La fórmula implica una división entre $f'(x_k)$. Si la derivada es cero, el método falla (división por cero).

  2. Si $f'(x_k)$ es muy pequeño

    • Puede provocar grandes saltos en la aproximación y la iteración puede divergir.

  3. Si la raíz es múltiple

    • La convergencia es más lenta y puede incluso fallar.

  4. Si la aproximación inicial $x_0$ está lejos de la raíz

    • El método puede divergir o ir hacia otra raíz.
In [3]:
import numpy as np
import matplotlib.pyplot as plt

def metodos_numericos_rectas():
    # Función y su derivada
    def f(x):
        return x**3 - x - 2

    def df(x):
        return 3*x**2 - 1

    # Rango para graficar la función
    x_vals = np.linspace(-2, 3, 400)
    y_vals = f(x_vals)

    fig, axs = plt.subplots(1, 3, figsize=(18, 5))
    titulos = ["Bisección", "Newton-Raphson", "Secante"]

    # ================== MÉTODO DE BISECCIÓN ==================
    a, b = 1, 2
    axs[0].plot(x_vals, y_vals, label="f(x)")
    axs[0].axhline(0, color="gray", linestyle="--")

    for _ in range(5):
        x = (a + b) / 2
        # Recta del intervalo
        axs[0].plot([a, b], [f(a), f(b)], "r-", alpha=0.5)
        axs[0].scatter([x], [f(x)], color="red")
        if f(a) * f(x) < 0:
            b = x
        else:
            a = x

    axs[0].set_title(titulos[0])

    # ================== MÉTODO NEWTON-RAPHSON ==================
    x = 1.5
    axs[1].plot(x_vals, y_vals, label="f(x)")
    axs[1].axhline(0, color="gray", linestyle="--")

    for _ in range(5):
        if df(x) == 0:
            break
        # Puntos y tangente
        y = f(x)
        axs[1].scatter([x], [y], color="blue")
        # Tangente: y = f(x) + f'(x)(X - x)
        X_line = np.linspace(x-1, x+1, 20)
        axs[1].plot(X_line, y + df(x) * (X_line - x), "b-", alpha=0.5)
        x = x - f(x)/df(x)

    axs[1].set_title(titulos[1])

    # ================== MÉTODO DE LA SECANTE ==================
    x0, x1 = 1, 2
    axs[2].plot(x_vals, y_vals, label="f(x)")
    axs[2].axhline(0, color="gray", linestyle="--")

    for _ in range(5):
        axs[2].scatter([x1], [f(x1)], color="green")
        # Dibujar recta secante
        axs[2].plot([x0, x1], [f(x0), f(x1)], "g-", alpha=0.5)
        if f(x1) - f(x0) == 0:
            break
        x2 = x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0))
        x0, x1 = x1, x2

    axs[2].set_title(titulos[2])

    plt.show()

# Llamar función
metodos_numericos_rectas()
No description has been provided for this image

Comparación de métodos¶

Método Ventajas Desventajas
Bisección (pendiente) Convergencia lenta
Newton-Raphson Convergencia rápida (cuando $x_0$ está cerca de la raíz) LLegan a fallar
Secante Convergencia rápida y no requiere derivada LLegan a fallar

Desarrollo del cálculo del número de iteraciones en Bisección¶

  1. Contexto: El método de bisección parte de un intervalo $[a, b]$ donde sabemos que $f(a) \cdot f(b) < 0$, es decir, la raíz está dentro del intervalo. En cada iteración el intervalo se reduce a la mitad.

  2. Longitud del intervalo después de $n$ iteraciones: Al dividir a la mitad el intervalo en cada paso, la longitud del intervalo después de $n$ pasos es:

    $$ L_n = \frac{b - a}{2^n} $$

  3. Precisión deseada: Queremos que la longitud del intervalo sea menor o igual a la precisión deseada $\varepsilon$:

    $$ L_n \leq \varepsilon $$

    Entonces:

    $$ \frac{b - a}{2^n} \leq \varepsilon $$

  4. Despejamos $n$:

    Multiplicamos ambos lados por $2^n$:

    $$ b - a \leq \varepsilon \cdot 2^n $$

    Dividimos entre $\varepsilon$:

    $$ \frac{b - a}{\varepsilon} \leq 2^n $$

    Tomamos logaritmo base 2 en ambos lados (recordando que $\log_2(2^n) = n$):

    $$ \log_2 \left( \frac{b - a}{\varepsilon} \right) \leq n $$

  5. Interpretación: El número mínimo de iteraciones necesarias para asegurar una precisión $\varepsilon$ es:

    $$ n \geq \log_2 \left( \frac{b - a}{\varepsilon} \right) $$

Resumen:¶

$$ \boxed{ n = \left\lceil \log_2 \left( \frac{b - a}{\varepsilon} \right) \right\rceil } $$

(donde $\lceil \cdot \rceil$ indica que redondeamos hacia arriba porque el número de iteraciones es entero).

Claro, aquí te explico por qué y cómo pueden fallar los métodos de Newton-Raphson y Secante por divergencia o ciclos:

1. Newton-Raphson: causas de fallo¶

  • Derivada cercana o igual a cero Cuando $f'(x_k)$ es cero o muy pequeño, el paso

    $$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} $$

    puede dar saltos muy grandes, alejándose de la raíz.

  • Elección mala de $x_0$ (punto inicial) Si el punto inicial está lejos de la raíz real, la iteración puede desviarse o incluso ir hacia otra raíz o infinito.

  • Raíz múltiple o plana Cuando la raíz no es simple, la convergencia se vuelve lenta o errática, incluso puede no converger.

  • Funciones con comportamiento complicado Funciones con múltiples raíces, oscilaciones o singularidades pueden causar que la iteración oscile sin converger (ciclos).

2. Método de la Secante: causas de fallo¶

  • Diferencia en el denominador cero o cercana a cero En

    $$ x_{k+1} = x_k - f(x_k) \frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})} $$

    si $f(x_k) \approx f(x_{k-1})$, la división se hace muy grande o indefinida, causando inestabilidad.

  • Malos puntos iniciales $x_0, x_1$ Pueden provocar que la secuencia diverja o entre en ciclos.

  • Funciones no bien comportadas Igual que Newton, funciones con raíces múltiples, oscilaciones o discontinuidades pueden causar ciclos o divergencia.

¿Qué es un ciclo?¶

Un ciclo ocurre cuando la iteración vuelve a un punto anterior y repite un conjunto finito de valores (por ejemplo: $x_3 = x_1$, $x_4 = x_2$, etc.), sin acercarse a la raíz. Es un tipo de no convergencia.

Resumen rápido¶

Método Causas de divergencia o ciclos
Newton-Raphson Derivada cero o muy pequeña, mal punto inicial, raíz múltiple, oscilaciones
Secante División por cero (o casi), malos puntos iniciales, función irregular

Representacion Vectorial¶

$$ X = \begin{pmatrix} x \\ y \end{pmatrix} \in \mathbb{R}^2, \quad F(X) = \begin{pmatrix} f_1(x,y) \\ f_2(x,y) \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$

Vamos a resolver y encontar los ceros , para ello encontramos el jacobiano

$$ J_F(X) = \begin{pmatrix} \frac{\partial f_1}{\partial x} & \frac{\partial f_1}{\partial y} \\ \frac{\partial f_2}{\partial x} & \frac{\partial f_2}{\partial y} \end{pmatrix} $$

El metodo de nwton para funciones de ese tipo sera el siguiente tenemos que el original funcion le aplicamos la funcion del jabociano

$$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} $$

Esto es newton la original . Pero la division por matrices no existe. Asi que vamos a hacer es hacer la multiplicacion de la inversa de la matriz derivada.

$$ X_{k+1} = X_k - J_F(X_k)^{-1} F(X_k) $$

Esto ultimo es la ecuacion del metodo de newton en varias variables

Y la condicion de paro es $$ |x_{k+1} - x_k| < tol $$

Ejemplo¶

image.png

Este usando el codigo de newton extendido para R*n se puede usar para encontrar los interceptos.

Clase 31.07¶

Fundamentos para la optimización unidimensional (1D)¶

Unimodalidad¶

Una función es unimodal si dentro de un intervalo cerrado $[a, b]$ presenta un único mínimo local, que en este caso también es mínimo global en ese intervalo. Es decir, si aplicamos un algoritmo de optimización, éste siempre convergerá a ese único mínimo.

Unimodal entonces sabemos que hay un mínimo; entonces si aplico un algoritmo sobre eso va a llegar a un único mínimo posible dentro de un intervalo entre $a$ y $b$.

Sin embargo, una función puede no ser unimodal en todo su dominio:

Obvio la función completa no es unimodal, pero respecto al único intervalo se vuelve unimodal y se trabaja en otro intervalo. Realmente, el unimodal es en un intervalo.

Además, incluso si la función presenta picos, saltos o discontinuidades, puede ser considerada unimodal dentro del intervalo si presenta un solo mínimo:

Las funciones pueden ser unimodales con picos o saltos, pero esto no le interesa [al algoritmo], incluso si no es continua. Sino el punto donde hay un mínimo, la función puede ser unimodal.

Esto es clave porque algunos algoritmos de optimización exigen esta propiedad:

Esto es importante porque el algoritmo a ver pide que sea unimodal, un solo mínimo. El proceso es esbozar la gráfica y darse una idea de dónde está el mínimo para aplicarlo.

Bimodalidad y multimodalidad¶

Una función es bimodal si presenta dos mínimos locales distintos. Se extiende a multimodal cuando tiene más de dos mínimos locales.

Bimodal: dos puntos locales Multimodal: múltiples mínimos o máximos locales

En estos casos, los algoritmos de búsqueda de mínimos pueden converger a diferentes resultados dependiendo del punto de inicio o del intervalo seleccionado. Por eso se busca acotar la función a un intervalo donde sea unimodal.

Algoritmos de optimización 1D¶

A diferencia de métodos para encontrar ceros de funciones, los algoritmos de optimización 1D buscan el mínimo de una función en un intervalo dado.

En lugar de darme los ceros, me darán el mínimo de la función con un intervalo de trabajo o un punto inicial. Dependiendo del algoritmo puede que pidamos que sea unimodal, diferenciable o que tenga su derivada.

Se estudian métodos que permiten obtener estos mínimos eficientemente, sin calcular derivadas (en algunos casos) ni hacer búsquedas exhaustivas.

Receta general para métodos de optimización 1D¶

Para aplicar cualquier método de optimización unidimensional se necesita:

  1. Intervalo o punto inicial: Indica dónde se buscará el mínimo.
  2. Ecuación de actualización: Define cómo se generan nuevos puntos.
  3. Criterio de paro: Por número máximo de iteraciones o tolerancia.

Esto trata para meter algoritmos de funciones para saber estos mínimos...

Método de la Razón Áurea (Golden Section Search)¶

¿Por qué "razón áurea"?¶

Por ejemplo, $(1 + \sqrt{5}) / 2 \approx 1.618$. Tienen que ver con la proporción áurea, un valor relacionado al Renacimiento, Fibonacci, etc. Esto se llama así porque en una parte del algoritmo aparece este número.

Objetivo¶

Minimizar una función $f: [a, b] \to \mathbb{R}$, que sea unimodal en $[a, b]$.

Esquema del algoritmo¶

Si no lo es [unimodal], nuestro trabajo es acortar el intervalo donde sí lo sea.

Se parte del intervalo inicial $[a_0, b_0]$ y se escogen dos nuevos puntos:

$$ a_1 = c, \quad b_1 = d $$

La condición es que debe haber simetría entre la distancia $a_0 - a_1$ y $b_0 - b_1$, es decir, simétrico en esas distancias.

Estos puntos se colocan usando una proporción $p < \frac{1}{2}$, típicamente:

$$ p = \frac{\sqrt{5} - 1}{2} $$

De modo que:

$$ c = b - (b - a)\cdot p, \quad d = a + (b - a)\cdot p $$

Luego:

  • Si $f(c) < f(d)$, el mínimo está en $[a, d]$
  • Si $f(c) > f(d)$, el mínimo está en $[c, b]$

Estos dos nuevos puntos lo que me indican es elegir un nuevo lugar de trabajo más pequeño que el original.

Algoritmo en pseudocódigo¶

Algoritmo: (Golden search)
Inputs: [a₀, b₀]: intervalo de búsqueda.
Outputs: x mínimo global de f en [a₀, b₀].

For k = 0, 1, 2, ... hasta que se cumpla criterio de paro:
    cₖ = bₖ − (bₖ − aₖ)(√5−1)/2  
    dₖ = aₖ + (bₖ − aₖ)(√5−1)/2

    xₖ₊₁ = ½(cₖ + dₖ)

    If f(cₖ) < f(dₖ):
        aₖ₊₁ = aₖ, bₖ₊₁ = dₖ
    Else:
        aₖ₊₁ = cₖ, bₖ₊₁ = bₖ

Return xₖ₊₁

Código en Python¶

(ya lo incluías, no se modifica)

Interpolación Parabólica¶

Motivación¶

Supongamos una parábola:

$$ f(x) = ax^2 + bx + c $$

El mínimo de esa parábola (si $a > 0$) está en:

$$ x = -\frac{b}{2a} $$

Esto nos sirve para entender el segundo algoritmo "Interpolación parabólica".

¿Cómo se construye la parábola?¶

Le doy tres puntos: $x_0$, $x_1$, $x_2$ y sus respectivos $y_i = f(x_i)$. Entonces construimos una parábola que pase por esos tres puntos.

Una función cuadrática es suficiente para pasar por tres puntos distintos. Si esos puntos son cercanos al mínimo, entonces la parábola se aproxima a la función cerca del mínimo real.

Sistema de ecuaciones lineal¶

Buscamos los coeficientes $a_k$, $b_k$, $c_k$ de la parábola:

$$ f(x) = a_k x^2 + b_k x + c_k $$

Dado:

$$ (x_k, f(x_k)), \quad (x_{k+1}, f(x_{k+1})), \quad (x_{k+2}, f(x_{k+2})) $$

El sistema se representa como:

$$ \begin{pmatrix} 1 & x_k & x_k^2 \\ 1 & x_{k+1} & x_{k+1}^2 \\ 1 & x_{k+2} & x_{k+2}^2 \end{pmatrix} \begin{pmatrix} c_k \\ b_k \\ a_k \end{pmatrix} = \begin{pmatrix} f(x_k) \\ f(x_{k+1}) \\ f(x_{k+2}) \end{pmatrix} $$

Alternativa: Fórmulas explícitas¶

O simplemente se pueden quemar las fórmulas:

$$ \begin{aligned} c_k &= \frac{(x_{k+1} - x_{k+2})f(x_k) + (x_{k+2} - x_k)f(x_{k+1}) + (x_k - x_{k+1})f(x_{k+2})} {(x_k - x_{k+1})(x_{k+1} - x_{k+2})(x_{k+2} - x_k)} \\ \\ b_k &= \frac{(x_{k+1}^2 - x_{k+2}^2)f(x_k) + (x_{k+2}^2 - x_k^2)f(x_{k+1}) + (x_k^2 - x_{k+1}^2)f(x_{k+2})} {(x_k - x_{k+1})(x_{k+1} - x_{k+2})(x_{k+2} - x_k)} \\ \\ a_k &= \frac{(x_{k+1}x_{k+2}^2 - x_{k+2}x_{k+1}^2)f(x_k) + (x_{k+2}x_k^2 - x_kx_{k+2}^2)f(x_{k+1}) + (x_kx_{k+1}^2 - x_{k+1}x_k^2)f(x_{k+2})} {(x_k - x_{k+1})(x_{k+1} - x_{k+2})(x_{k+2} - x_k)} \end{aligned} $$

Validación¶

Antes de calcular el nuevo $x = -b_k / 2a_k$, es fundamental verificar que:

$a_k > 0$. Si no, entonces el mínimo no está bien definido (la parábola se abre hacia abajo) → se debe lanzar error o cambiar puntos.

Método de Newton para Optimización¶

Fundamento¶

Recordando Newton para ceros:

$$ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} $$

Ahora queremos encontrar el mínimo de $f$, lo cual ocurre cuando $f'(x) = 0$. Entonces, buscamos ceros de la derivada:

Entonces si quiero el mínimo $f'(x) = 0$, es decir, $x$ es mínimo de $f$, se debe cumplir lo anterior.

Aplicamos Newton a la derivada:

$$ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} $$

Este método converge rápidamente cuando se cumplen las condiciones necesarias, pero:

Tendremos las mismas desventajas de Newton: derivada igual a cero, ciclos, divergencia, etc.

Observación¶

Sirve también para encontrar máximos si el segundo derivado es negativo, pero aquí lo usamos para mínimos.

El resto del código y estructura ya lo habías puesto completo y está bien.