Implement Lagrange's interpolation formula.
Imagine we have \(n+1\) measurements of some quantity \(y\) that depends on \(x\) :
\(\left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right), \ldots,\left(x_{n},
y_{n}\right)\). We may think of \(y\) as a function of \(x\) and ask what \(y\) is at
some arbitrary point \(x\) not coinciding with any of the \(x_{0}, \ldots,
x_{n}\). This problem is known as interpolation. One way to solve this problem
is to fit a continuous function that goes through all the \(n+1\) points and
then evaluate this function for any desired \(x\). A candidate for such a
function is the polynomial of degree \(n\) that goes through all the points.
This polynomial can be written
$$
p_{L}(x)=\sum_{k=0}^{n} y_{k} L_{k}(x)
$$
where
$$
L_{k}(x)=\prod_{i=0, i \neq k}^{n} \frac{x-x_{i}}{x_{k}-x_{j}}
$$
The \(\Pi\) notation corresponds to \(\sum\), but the terms are multiplied, e.g.,
$$
\prod_{i=0, i \neq k}^{n} x_{i}=x_{0} x_{1} \cdots x_{k-1} x_{k+1} \cdots
x_{n}
$$
The polynomial \(p_{L}(x)\) is known as Lagrange's interpolation formula, and
the points \(\left(x_{0}, y_{0}\right), \ldots,\left(x_{n}, y_{n}\right)\) are
called interpolation points.
Make a function Lagrange \(\left(x\right.\), points) that evaluates \(p_{L}\) at
the point x, given \(n+1\) interpolation points as a two-dimensional array
points, such that points \([i, 0]\) is the \(x\) coordinate of point number \(i\)
and points \([i, 1]\) is the corresponding \(y\) coordinate.
To verify the program, we observe that \(L_{k}\left(x_{k}\right)=1\) and that
\(L_{k}\left(x_{i}\right)=0\) for \(i \neq k\), implying that
\(p_{L}\left(x_{k}\right)=y_{k}\). Write a function verify (points) that
computes \(\left|p_{L}\left(x_{k}\right)-y_{k}\right|\) at all the interpolation
points and checks that the value is approximately zero. Call verify with 5
equally spaced points along the curve \(y=\sin (x)\) for \(x \in[0, \pi]\). Then
evaluate \(p_{L}(x)\) for an \(x\) in the middle of two interpolation points and
compare the value of \(p_{L}(x)\) with the exact one: \(\sin (x)\). Name of
program file: Lagrange_polynomial1.py.
