*Chuck Norris doesn't need Lagrange interpolation. He glares at the scattered points, and they align themselves perfectly along his will, forming a pure, limpid straight line.*

# Polynomial Lagrange interpolation

In the previous section, we saw that `n` points can fully define a polynomial of degree at most `n-1`. In this section, we will see how we can find the coefficients of such a polynomial from the coordonates of these `n` points.

One way to do this is to use the [Lagrange interpolation method](https://en.wikipedia.org/wiki/Lagrange_polynomial). Although this Wikipedia page looks impressive, the recipe to follow is actually quite simple.

We want to find a polynomial `P` of degree at most `2`, which satisfies the `3` following constraints:

- `P(-1) = 4`
- `P(2) = 1`
- `P(3) = 4`

To do that, we'll build 3 sub-polynomials (one per constraint) `P₁`,`P₂` and `P₃` of degree at most `2`.

These 3 sub-polynomials must follow these sub-constraints:

| x | P₁(x) | P₂(x) | P₃(x) |
| -- | ----- | ----- | ----- |
| -1 | 4 | 0 | 0 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 0 | 4 |

Each sub polynomial evaluates to `0` in all constraint points but one.

Finally, we set:
$$
P(x) = P_1(x) + P_2(x) + P_3(x)
$$

Let's quickly check, reffering to the previous tab, that `P` respects all its contraints:

$$
P(-1) = P_1(-1) + P_2(-1) + P_3(-1) = 4 + 0 + 0 = 4
$$

$$
P(2) = P_1(2) + P_2(2) + P_3(2) = 0 + 1 + 0 = 1
$$

$$
P(3) = P_1(3) + P_2(3) + P_3(3) = 0 + 0 + 4 = 4
$$

We just verified that `P` respect its 3 constraints. Now, let's build `P₁`, `P₂` and `P₃`.

#### Building `P₁`.
Using the [factorised form](https://hackmd.io/H1DpZdKdTf2KmF5MhYz_zg?both#Factorised-form), we can define `P₁` as:
$$
P_1(x) = A(x-2)(x-3)
$$

`P₁` already satisfies contraints
$$
P_1(2) = P_1(3) = 0
$$

Now let's find `A` such as
$$
P_1(-1) = 4
$$

We have the following equation:
$$
P_1(-1) = A(-1 - 2)(-1 - 3) = 4
$$

Which gives us
$$
A = \frac{1}{3}
$$

And finally
$$
P_1(x) = \frac{1}{3}(x-2)(x-3)
$$

`P₁` now satisfies its 3 sub-constraints.

#### Building `P₂`.
Using the [factorised form](https://hackmd.io/H1DpZdKdTf2KmF5MhYz_zg?both#Factorised-form), we can define `P2` as:
$$
P_2(x) = B(x+1)(x-3)
$$

`P2` already satisfies contraints
$$
P_2(-1) = P_2(3) = 0
$$

Now let's find `B` such as
$$
P_2(2) = 1
$$

We have the following equation:
$$
P_2(2) = B(2 + 1)(2 - 3) = 1
$$

Which gives us
$$
B = -\frac{1}{3}
$$

And finally
$$
P_2(x) = -\frac{1}{3}(x+1)(x-3)
$$

`P₂` now satisfies its 3 sub-constraints.

#### Building `P3`.
Using the [factorised form](https://hackmd.io/H1DpZdKdTf2KmF5MhYz_zg?both#Factorised-form), we can define `P2` as:
$$
P_3(x) = C(x+1)(x-2)
$$

`P₃` already satisfies contraints
$$
P_3(-1) = P_3(2) = 0
$$

Now let's find `C` such as
$$
P_3(3) = 4
$$

We have the following equation:
$$
P_3(3) = C(3 + 1)(3 - 2) = 4
$$

Which gives us
$$
C = 1
$$

And finally
$$
P_3(x) = (x+1)(x-2)
$$

`P₃` now satisfies its 3 sub-constraints.

#### Building P

As previously seen,

$$
P(x) = P_1(x) + P_2(x) + P_3(x)
$$

Replacing `P₁`, `P₂` and `P₃` by their respective expression, we get:

$$
P(x) = \frac{1}{3}(x-2)(x-3) - \frac{1}{3}(x+1)(x-3) + (x+1)(x-2)
$$

After expansion and simplification, we obtain:

$$
P(x) = x^2 - 2x + 1
$$

#### Checking P
Let's quickly check that `P` does respect the 3 constraints:

$$
P(-1) = (-1)^2 - 2*(-1) + 1 = 4
$$

$$
P(2) = 2^2 - 2*2 + 1 = 1
$$

$$
P(3) = 3^2 - 2*3 + 1 = 4
$$

We now know how to build a polynomial of degree at most `n-1` from `n` constraints.