# M2AA3 Chapter 3, Lesson 1 - Lagrange Interpolation


```python
import sympy as sp
```

Given points $\{(z_i, f_i) \}_{i=0}^n$, where $\forall i, z_i, f_i \in \mathbb{C}$, and $z_i$ are distinct. We would like to find a polynomial $p_n \in \mathbb{P}_n$ such that $\forall i, p_n(z_i) = f_i$.

The following polynomials work:
$$p_n(z) = \sum_{i=0}^n f_i l_i(z)$$ where $l_i (z)$ is the Largrange's basis function
$$l_i(z) = \prod_{\substack{0 \leq k \leq n \\ k \neq i}} \frac{z - z_k}{z_i - z_k}$$
The function 'lagrange' inputs 'zs' (list of $z_i$) and 'fs' (list of $f_i$) and output polynomials. 


```python
x = sp.symbols('x')
l = sp.Function('l')
p = sp.Function('p')
```

Step 1 - Find Largrange Basis


```python
def basis(zs,i):
    
    # Initialization
    zi = zs[i]
    l = 1
    
    # Loop for Product
    for zj in zs:
        if zj != zi:
            l = l * (x-zj)/(zi-zj)
    
    l = sp.simplify(l)
    return l
```

Step 2 - Find Polynomial


```python
def lagrange(zs,fs):
    
    # Initialization
    p = 0
    
    # Loop for Sum
    for i in range(len(fs)):
        p += fs[i]*basis(zs,i)
    
    p = sp.simplify(p)
    return p
```

Example - Use the following data to find the largrange polynomial.


```python
xs = [-1, 0, 2, 5]
ys = [-3, -1, 4, 1]
```


```python
lagrange(xs,ys)
```




    -13*x**3/90 + 14*x**2/45 + 221*x/90 - 1



aa4925ccce3cedd3f6cabef43debd9cfecf6d530
ipynb
Jupyter Notebook
M2AA3/M2AA3-Polynomials/Lesson 01 - Basics/Largrange Interpolation.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
2021-05-16T04:08:34.000Z
2021-11-27T12:56:10.000Z
M2AA3/M2AA3-Polynomials/Lesson 01 - Basics/Largrange Interpolation.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
M2AA3/M2AA3-Polynomials/Lesson 01 - Basics/Largrange Interpolation.ipynb
ImperialCollegeLondon/Random-Stuff
219bc0e26ea6f5ee7548009c849959b268f54821
MIT
2020-03-31T00:23:13.000Z
2020-05-13T15:01:46.000Z
Qwen/Qwen-72B
1. YES
2. YES