<jupyter_start><jupyter_text>INF-285 / ILI-285  Desafío 4 SCT 2020-1  Instrucciones- El desafío es individual, por lo cual se considera que todo el código entregado es de elaboración propia y no ha sido compartido de forma alguna.- Las consultas sobre el desafío se deben realizar por medio de la plataforma Aula. **No está permitido publicar código en consultas de Aula**.- El desafío debe ser realizado en Jupyter Notebook (Python3) utilizando este archivo como base.- Debe utilizar arreglos de ```NumPy``` junto a las funciones y bibliotecas que se ponen a disposición en este archivo.- Se debe respetar las firmas de las funciones, sus parámetros y retornos. Para eso se incluye un detalle de cada función tanto de las entregadas como las que deberá implementar. En caso de no seguir estas instrucciones, el desafío no podrá evaluarse.- Se evaluará la correcta utilización de librerias ```NumPy```, ```SciPy```, entre otras, así como la correcta implementación de algoritmos de forma vectorizada.- Evitar la impresión de mensajes salvo que se solicite en el enunciado.- El archivo de entrega debe denominarse **ROL-desafio-numero.ipynb**. **De no respetarse este formato existirá un descuento de 50 puntos**- La fecha de entrega es el **30 de julio a las 10:00 hrs**,  posteriormente existirá un descuento lineal hasta las 11:00 hrs del mismo día.  IntroducciónEn este desafío vamos a comparar el rendimiento de la interpolación polinomial utilizando **Intepolación de Lagrange** e **Interpolación Baricéntrica**. Recordar que estamos buscando un polinomio interpolador de la forma:\begin{equation}    P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1}+a_{n}x^{n}= \sum_{i=0}^{n}a_ix^i,\end{equation}que se construye conociendo el conjunto de puntos $S=\{(x_0, y_0),(x_1, y_1), \dots, (x_n, y_n)\}$. Interpolación de LagrangeEl polinomio interpolador de Lagrange se define como:\begin{equation*}    P(x) = y_{0}L_{0}(x) + y_{1}L_{1}(x) + \dots + y_{n} L_{n}(x) = \displaystyle \sum_{k=0}^{n} y_{k} L_{k}(x),\end{equation*}con\begin{equation*}    L_k(x) = \frac{l_k(x)}{l_k(x_k)} \quad \text{y} \quad l_k(x) = \prod_{i=0, i\neq k}^{n}(x-x_i)= (x-x_1)(x-x_2)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n).\end{equation*}     Interpolación BaricéntricaEl polinomio interpolador utilizando **Interpolación Baricéntrica** se calcula de la siguiente manera:\begin{equation*}    P(x)=l(x)\,\sum_{k=0}^n y_k\,\dfrac{w_k}{(x-x_k)}        =\dfrac{\displaystyle{\sum_{k=0}^n} y_k\dfrac{w_k}{(x-x_k)}}        {\displaystyle{\sum_{k=0}^n} \dfrac{w_k}{(x-x_k)}},\end{equation*}donde $l(x)=\displaystyle{\prod_{i=0}^n(x-x_i)}$ y $w_k=\dfrac{1}{l_k(x_k)}$.<jupyter_code>import time
import numpy as np
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Implementación Implemente la función ```lagrange(x_i, y_i)``` que recibe como parámetros los puntos de interpolación $x_i, y_i$ y retorna el polinomio interpolador $L(x)$.Asegúrese que su polinomio pueda evaluar arreglos de ```NumPy```.<jupyter_code>def lagrange(x_i, y_i):
    """
    Compute Interpolating Polynomial using Lagrange

    Parameters
    -----------
    x_i     : (n, ) array
             Data x_i to interpolate
    y_i     : (n, ) array
             Data y_i to interpolate

    Returns
    -------
    L     : Lambda function
            Lagrange interpolating polynomial
    """
    ...<jupyter_output><empty_output><jupyter_text>Implemente la función ```barycentric(x_i, y_i)``` que recibe como parámetros los puntos de interpolación $x_i, y_i$ y retorna el polinomio interpolador $B(x)$.Asegúrese que su polinomio pueda evaluar arreglos de ```NumPy```.<jupyter_code>def barycentric(x_i, y_i):
    """
    Compute Interpolating Polynomial using Barycentric interpolation

    Parameters
    -----------
    x_i     : (n, ) array
             Data x_i to interpolate
    y_i     : (n, ) array
             Data y_i to interpolate

    Returns
    -------
    B     : Lambda function
            Barycentric interpolation
    """
    ...<jupyter_output><empty_output><jupyter_text>Pruebas Para que pueda probar sus funciones se ponen a disposición las siguientes funciones:<jupyter_code>f1 = lambda x: 2 * x + 3 
f2 = lambda x: np.sin(x) ** 3 
f3 = lambda x: np.exp(x) 
f4 = lambda x: np.exp(-x ** 2)
f5 = lambda x: np.sinc(x)
f6 = lambda x: 1 + x * 0
f7 = lambda x: 1 / (1 + 25 * x ** 2)<jupyter_output><empty_output><jupyter_text>Datos a interpolarAcá puede seleccionar la función de la celda anterior que estime conveniente para probar su interpolación.<jupyter_code>f = f5<jupyter_output><empty_output><jupyter_text>Se generarán puntos equispaciados $x_i$ en un intervalo indicado y luego se evaluaran dichos puntos en una función $f$ para generar puntos $y_i$.<jupyter_code>N_i = 11
x_a, x_b = -2 * np.pi, 2 * np.pi
x_i = np.linspace(x_a, x_b, N_i)
y_i = f(x_i)<jupyter_output><empty_output><jupyter_text>InterpolaciónPara probar su interpolación, utilice las siguientes celdas.<jupyter_code>Pl = lagrange(x_i, y_i)
Pb = barycentric(x_i, y_i)<jupyter_output><empty_output><jupyter_text>VisualizaciónUtilice este código para visualizar su interpolación.<jupyter_code>N_e = 200
x_e = np.linspace(x_a, x_b, N_e)
y_e = f(x_e)
plt.figure(figsize=(12, 6))
plt.plot(x_e, y_e, 'b-', label=r"$f(x)$")
plt.plot(x_i, y_i, 'rd', label="Puntos para interpolar")
plt.plot(x_e, Pl(x_e), 'm--', label=r'$P_L(x)$')
plt.plot(x_e, Pb(x_e), 'k-.', label=r'$P_B(x)$')
plt.grid(True)
plt.legend()
plt.xlabel(r'$x$')
plt.ylabel(r'$y$')
plt.show()<jupyter_output><empty_output><jupyter_text>Comparar tiempo de evaluacionDiseñe un experimento de manera que pueda mostrar la complejidad computacional en la **evaluación** de sus interpoladores. Recuerde que la complejidad de evaluar un polinomio utilizando Lagrange debería ser del orden $O(n^2)$ mientras que al usar Interpolación Baricéntrica $O(n)$.<jupyter_code>x_a, x_b = -2 * np.pi, 2 * np.pi # Interpolation domain
N_exp = 5
Nt = 2 ** np.arange(3, 9)
N = Nt.shape[-1]
times_el = np.zeros(N)
times_eb = np.zeros(N)
# Evaluation time<jupyter_output><empty_output><jupyter_text>Visualización tiemposPuede utilizar este código para visualizar los tiempos de evaluación.<jupyter_code>plt.figure(figsize=(12, 6))
plt.plot(Nt, times_el, 'rx', label="Lagrange")
plt.plot(Nt, times_eb, 'gd', label="Barycentric")
plt.plot(Nt, 1e-4 * Nt, label=r"$O(n)$") # Puede ajustar el coeficiente 1e-4
plt.plot(Nt, 1e-4 * Nt ** 2, label=r"$O(n^2)$") # Puede ajustar el coeficiente 1e-4
plt.xscale('log')
plt.yscale('log')
plt.ylabel("Time [s]")
plt.xlabel("Number of evaluation points")
plt.grid(True)
plt.legend()
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13486693730266125, 'fraction_numerical': 0.015185686362952939, 'mean_word_length': 4.589915966386554, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '55335', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 2662, 'n_tokens_neox': 2556, 'n_words': 698, 'path': 'desafios/desafio_4.ipynb', 'repo_name': 'DoVirgo/INF-285', 'size': '6651'}