Algoritmo iterativo

Se utilizan para:

• Encontrar el valor de una función en un punto
• Resolver una ecuación

Idea caminando hacia la solución:

$$ x_{t+1} = x_t + Paso(x_{t})$$

Es iterativo por que, desde la solución doy un paso y busco una nueva solución

Cuando paro: por ejemplo, cuando

$$|x_{t+1} - x_{t}| < \text{tolerancia}$$

Programación de un algoritmo iterativo

Assumption: conocemos la derivada de la función

$$\frac{\partial{f(x)}}{\partial{x}} = lim_{\Delta \rightarrow 0} \frac{f(x+\Delta)-f(x)}{\Delta}$$

En el punto $a$ la podemos escribir como

$$\frac{\partial{f(a)}}{\partial{x}} = lim_{ x\rightarrow a} \frac{ f(x)-f(a)}{(x-a)}$$

Si quitamos el límite, esto es una aproximación a la derivada, y despejamos $f(x)$ llegamos a</span>

$$f(x) \approx f(a) + \frac{\partial f(a)}{\partial x} (x-a)$$

Esta expresión me dice que puedo aproximar la función $$f(\cdot)$$ en el punto $x$ por una ecuación lineal </span>

$$f(a) + \frac{\partial f(a)}{\partial x} (x-a)$$

para un $a$ cercano a $x$.

Esta última expersión es la base de muchos algoritmos iterativos.

Ejemplo: Encontrar el valor de una función: raiz cuadrada

Algoritmo de la raiz cuadrada de Heron

Aplicamos la ecuación de aproximación de la función en el punto $x$

$$f(x) \approx f(a) + \frac{\partial f(a)}{\partial x} (x-a)$$$$ \sqrt{x} \approx \sqrt{a} + \frac{x-a}{2\sqrt{a}}$$

Utilicemos esta última expresión para hallar la raiz cuadrada de $21$, que es $4.58257569495584$

1.- Elegimos un punto cercano a $21$ cuya derivada conozco, e.g., $25$.

2.- Aplicando la formula de arriba llegamos a

$$ \sqrt{x} = \sqrt{21} \approx \sqrt{a} + \frac{x-a}{2\sqrt{a}} = \sqrt{25} + \frac{21-25}{2\sqrt{25}}$$$$f(x) \approx 4.6 $$

3.- Voy a llamar a la solución anterior $r_0 = 4.6$ y voy a iterar de la siguiente manera

$$r_{1} = r_{0} + \frac{21-r^2_{0}}{2 r_0}$$
$$r_{1} = 4.6 + \frac{21-4.6^2}{2 4.6}$$ y obtenemos como solución: $r_1 = 4.582608695652174$

4.- Ahora, iteramos de nuevo:

$$r_{2} = r_{1} + \frac{21-r^2_{1}}{2 r_1}$$
$$r_{1} = 4.582608695652174 + \frac{24-4.582608695652174^2}{2 4.582608695652174}$$ y obtenemos como solución: $r_1 = 4.582575695074664$

5.- Repitiria los proceso anteriores hasta que establezca una tolerancia o un numero de iteraciones

$$ |r_t - r_{t-1}|< tolerancia$$$$ |4.582575695074664 - 4.582608695652174|< tolerancia$$

La solución de Python es: np.sqrt(21) = 4.58257569495584

Vamos a programarlo

import numpy as np

Aproximación lineal

$$ \sqrt{x} \approx \sqrt{a} + \frac{x-a}{2 \times \sqrt{a}}$$

# Doc string 
def approx_sqrt(x, a):
    """Esto approxima la raiz cuadrada por una ecuacion lineal"""
    app = np.sqrt(a) + (x-a)*(1/(2*np.sqrt(a)))
    return app

approx_sqrt.__doc__ 

approx_sqrt(21,25)

Iteraciones

$$r_{1} = r_{0} + \frac{x-r^2_{0}}{2 r_0}$$

def iter_sqrt(x,r):
    r_t = r + (x-r**2)*(1/(2*r))
    return r_t

iter_sqrt(21, 4.6)

x = 21
a = 25
r_0 = approx_sqrt(x,a)
print(r_0)
r_1 =  iter_sqrt(x,r_0)
print(r_1)
r_2 =  iter_sqrt(x,r_1)
print(r_2)

# Typo Booleano
type(x > a)

iter = 10
tol = 0.00001

x = 21
a = 25

r_0 = approx_sqrt(x,a)
iteracion = 1

#loop for 
while iteracion < iter:

    r_1 = iter_sqrt(x,r_0)
    dif = abs(r_1 - r_0)
        
    if dif < tol:
        break

    r_0 = r_1
    # f-strings
    print(f"La iteración es {iteracion} y el valor de la diferencia es {dif}")
    iteracion = iteracion + 1

        
print(r_1)
print(r_1**2)