# INF-285 / ILI-285
## Desafío 1, v1.01
### SCT 2020-1

# Introducción

En el siguiente desafío estudiaremos el comportamiento de $2$ algoritmos para obtener el punto fijo $r$ de funciones $g(x)$, es decir, $r=g(r)$.
Es importante destacar que el punto fijo de una función no es lo mismo que la raíz de una función, sin embargo sí están muy relacionados.
Solo a modo de recordatorio, la raíz de una función $f(x)$ es encontrar un $\hat{x}$ tal que $f(\hat{x})=0$.

## Iteración de Punto Fijo

El algoritmo llamado Iteración de Punto Fijo (IPF o *FPI*, *Fixed Point Iteration* del inglés) se define de la siguiente forma:
\begin{align*}
  x_0 &= \text{"Initial guess''},\\
  x_{i+1} &= g(x_i), \quad i\in {1,2,3,\dots}.
\end{align*}

El cual puede o no puede converger a su punto fijo $r=g(r)$ dependiendo del comportamiento de $g(x)$ entorno al punto fijo $r$.
En el caso de que la iteración de punto fijo diverja, uno debiera buscar otra forma de encontrar el punto fijo, la otra manera se explica a continuación.

## Método de la Bisección

En el caso de que la iteración de punto fijo diverja o simplemente converja muy lento, podemos usar convenientemente el Método de la Bisección.
Para poder utilizar el Método de la Bisección, debemos adaptarlo, dado que es un algoritmo diseñado para buscar raíces de una función, no puntos fijos de una función.
La adaptación consiste en escribir convenientemente la búsqueda de un punto fijo como la búsqueda de una raíz de la siguiente forma,
\begin{equation}
  f(x) = x - g(x),
\end{equation}

donde podemos comprobar que si evaluamos la función $f(x)$ en el punto fijo de $g(x)$ obtenemos la equivalencia,
\begin{equation}
  f(r) = r - g(r)=0.
\end{equation}

Por lo tanto, ¡hemos exitosamente conectado un problema de punto fijo con un problema de búsqueda de ceros!

**De esta forma ambos métodos podrían ser útiles si necesitamos encontrar puntos fijos de funciones**.

Comentario: ¿Puede visualizar ahora el como utilizar búsqueda de puntos fijos para encontrar raíces de funciones?

# Ejercicio



```python
# Bibliotecas necesarias
import numpy as np
import matplotlib.pyplot as plt
```

Se solicita implementar una rutina ```obtener_punto_fijo``` que reciba la función $g(x)$, un intervalo $[a, b]$ y un ```n_iter```, que indica el máximo número de iteraciones que pueden utilizar los métodos de bisección y punto fijo.
Notar que los métodos deben retornar la secuencia de soluciones obtenidas hasta que se logra la convergencia, es necesario que cuando se logre el punto fijo no se retorne una secuencia de valores repetidos, si no que se trunque el vector de salida hasta donde empezó a repetirse el valor respectivo, de otra forma se estará dividiendo por $0$ en la explicación incluida más adelante.

El retorno de la rutina debe ser la mejor solución aproximada ```x_sol```, y una estructura del tipo 
```[('biseccion', tasa_bisección), ('punto fijo', tasa_punto_fijo)]```, donde se reporta el algoritmo (en el orden solicitado) y la tasa de convergencia respectiva.
Por lo tanto la firma de la función debería quedar como:
```python
  def obtener_punto_fijo(g, a, b, n_iter):
    # Su algoritmo...

    resultado = [('biseccion', tasa_biseccion), ('punto fijo', tasa_punto_fijo)]
    x_sol = ...
    return x_sol, resultado
```

La idea es que su algoritmo permita retornar la solución asociada al método con mejor *tasa de convergencia*.

Para que pueda calcular la *tasa de convergencia* se pone a disposición la función ```obtener_tasa(ratio)```, que recibe un arreglo con los cocientes de la estimación numérica de los errores en cada iteración. Los cuales deben ser obtenidos de la siguiente forma:
\begin{equation}
  ratio_i = \frac{|x_{i+1} - x_i|}{|x_i - x_{i-1}|}
\end{equation}


```python
def obtener_tasa(ratio):
  hist, bin_edges = np.histogram(ratio, bins=10000)
  k = np.argmax(hist)
  return np.round((bin_edges[k] + bin_edges[k+1]) / 2, 5)
```

Además, para que pueda probar el funcionamiento de su procedimiento, se ponen a disposición las siguientes funciones y los intevalos donde debe buscar el punto fijo:


```python
g1 = lambda x: np.cos(x) # Intervalo: [0, 1]
g2 = lambda x: 3 / (x-2) # Intervalo: [-3, 0]
g3 = lambda x: (x + 10.) ** (1 / 4) # Intervalo: [0, 2]
g4 = lambda x: 3 + 2 * np.sin(x) # Intervalo: [-5, 5]
g5 = lambda x: np.cos(x) / np.exp(x) # Intervalo: [0, 4]
g6 = lambda x: (np.exp(x) + x ** 3 + 4 * x ** 2 + 2 * x + 2) / (x ** 2 + 3 * x - 3) # Intervalo: [-1, 0]
g7 = lambda x: np.exp((np.exp(-x) / 3)) # Intervalo: [0, 2]
g8 = lambda x: -0.5 * x + 3 / 2 # Intervalo: [0, 1]
g9 = lambda x: (x ** 3 - 5) / 2 # Intervalo: [2, 3]
g10 = lambda x: -1 + 1.5 * x # Intervalo: [0,10]
g11 = lambda x: 0.7 + 1.7 * x # Intervalo: [-10,10]
```

Se incluye a continuación el enunciado de la función que usted debe entregar:


```python
def ratio(arreglo):
    x = arreglo[1:len(arreglo)-1]
    x_i_minus = arreglo[0:(len(arreglo)-2)]
    x_i_plus  = arreglo[2:]
    valores = abs(x_i_plus - x)/abs(x-x_i_minus)
    return valores

def bisection(f, a, b, n_iter):
  # CONSIDERE el caso que f(a) * f(b) sea positivo
  # RECUERDE no incluir valores repetidos al final de la secuencia del arreglo de salida para no tener errores igual a 0
    funcioncita = lambda x : x - f(x)
    if funcioncita(a)*funcioncita(b) > 0:
        return
    i = 0
    iteraciones = []
    while i < n_iter:
        c = (b+a)/2
        if funcioncita(c) == 0:
            iteraciones.append(c)
            ratios = ratio(np.array(iteraciones))
            return (c,ratios)
        else:
            if funcioncita(a)*funcioncita(c) < 0:
                b = c
            else:
                a = c
        if iteraciones == []:
            iteraciones.append(c)
        elif iteraciones[-1] != c:
            iteraciones.append(c)
        i+=1
    ratios = ratio(np.array(iteraciones))
    return (c,ratios)


```


```python
def fpi(g, x_0, n_iter):
  # CONSIDERE que el metodo puede no converger
  # RECUERDE no incluir valores repetidos al final de la secuencia del arreglo de salida para no tener errores igual a 0
    x =  x_0 # Calcular los valores de x para cada iteracion
    iteraciones=[]
    errores = []
    i = 0
    while i < n_iter:
        try:
            x_calc = g(x)
        except OverflowError:
            return None
        if x_calc == x and (x_calc not in iteraciones):
            iteraciones.append(x_calc)
        elif x_calc == x and (x_calc in iteraciones):
            i = n_iter
        else:
            iteraciones.append(x_calc)
        x = x_calc
        i+=1
    ratios = ratio(np.array(iteraciones))
    
    return (x_calc,ratios)

```


```python
def obtener_punto_fijo(g, a, b, n_iter):
    data_fpi = fpi(g,(a+b/2),100)
    data_bi = bisection(g,a,b,100)
    tasa_biseccion = obtener_tasa(data_bi[1]) # Debe obtenerla
    if data_fpi == None:
        tasa_punto_fijo = float("inf")
    else:
        tasa_punto_fijo = obtener_tasa(data_fpi[1]) # Debe obtenerla
    resultado = [('biseccion', tasa_biseccion), ('punto fijo', tasa_punto_fijo)]
    if tasa_biseccion < tasa_punto_fijo:
        x_sol = data_bi[0]
    elif tasa_biseccion > tasa_punto_fijo:
        x_sol = data_fpi[0]
    return x_sol, resultado

print(obtener_punto_fijo(g1,0,1,100))
print(obtener_punto_fijo(g2,-3,0,100))
print(obtener_punto_fijo(g3,0,2,100))
print(obtener_punto_fijo(g4,-5,5,100))
print(obtener_punto_fijo(g5,0,4,100))
print(obtener_punto_fijo(g6,-1,0,100))
print(obtener_punto_fijo(g7,0,2,100))
print(obtener_punto_fijo(g8,0,1,100))
print(obtener_punto_fijo(g9,2,3,100))
print(obtener_punto_fijo(g10,0,10,100))
print(obtener_punto_fijo(g11,-10,10,100))

```

    (0.7390851332151607, [('biseccion', 0.50005), ('punto fijo', 0.67361)])
    (-1.0, [('biseccion', 0.49999), ('punto fijo', 0.33333)])
    (1.8555845286409378, [('biseccion', 0.50005), ('punto fijo', 0.03913)])
    (3.0943834130492776, [('biseccion', 0.50005), ('punto fijo', 0.99999)])
    (0.5177573636824583, [('biseccion', 0.50005), ('punto fijo', 0.81266)])
    (-0.579158906050837, [('biseccion', 0.50005), ('punto fijo', 2e-05)])
    (1.1154480172165406, [('biseccion', 0.50005), ('punto fijo', 0.12187)])
    (1.0, [('biseccion', 0.50002), ('punto fijo', 0.49999)])
    (2.094551481542327, [('biseccion', 0.50002), ('punto fijo', inf)])
    (2.0, [('biseccion', 0.50001), ('punto fijo', 1.5)])
    (-1.0, [('biseccion', 0.50001), ('punto fijo', 1.7)])



```python

```

d2ec809768d2d581937344406dca2f72b5586d4c
ipynb
Jupyter Notebook
desafios/desafio_1.ipynb
Felipitoo/CC
2ce7bac8c02b5ef7089e752f2143e13a4b77afc2
BSD-3-Clause
desafios/desafio_1.ipynb
Felipitoo/CC
2ce7bac8c02b5ef7089e752f2143e13a4b77afc2
BSD-3-Clause
desafios/desafio_1.ipynb
Felipitoo/CC
2ce7bac8c02b5ef7089e752f2143e13a4b77afc2
BSD-3-Clause
Qwen/Qwen-72B
1. YES
2. YES