3.2 Lagrange Polynomials

To create a function that interpolates through prescribed points

Suppose $n\ge 1$ and $x_0,x_1,...,x_n$ are $n$ distinct real numbers.

We use the notation $P_n(x)$ for the polynomial of least degree interpolating the points:

Setting $p_i(x)=\prod _{j=0,j\ne i}^n(x-x_j)=(x-x_0)(x-x_1)\dots (x-x_{i-1})(x-x_{i+1})\dots (x-x_n)$

Lagrange Polynomial is the interpolating polynomial of least degree passing though $n+1$ points (since we index at 0).

Error

Setting $a=min(x_0,...,x_n,x)$ and $b=max(x_0,...,x_n,x),$ we have the following result. If $f$ has $n+1$ derivatives on $(a,b)$ and $f,f\prime ,f\prime \prime ,...,f(n)$ are all continuous on $[a,b]$, then there is a value ${\xi }_x\in (a,b)$ such that:

To find max error over the entire interval we usually look at a graph of:

To get $\underset{x\in [a,b]}{max}|h(x)|$

And then we look at $\underset{{\xi }_x\in [a,b]}{max}|f^{n+1}({\xi }_x)|$

and take $\underset{x\in [a,b]}{max}|h(x)|\cdot \underset{{\xi }_x\in [a,b]}{max}|f^{n+1}({\xi }_x)|$

Uniqueness

The polynomial $P_n$ of least degree interpolating the data $(x_i,y_i)$ for $i=0,1,...,n$ exists and is unique. Moreover, the interpolating polynomial of degree at most $n$ is equal to $P_n$ .

Proof idea

We know $P_n$ exists since $L_n(x)$ interpolates the data and has degree at most $n$.
Suppose that $P_n(x)$ and $q(x)$ are both polynomials of degree at most n, such that they each pass through all of the points $(x_i,y_i)$ for $i=0,1,...,n$.
Then the function $(P_n-q)(x)$ is a polynomial of degree at most $n$, such that it passes through the points $(x_i,0)$ for $i=0,1,...,n$. That is, it has $n+1$ zeros! Thus $(P_n-q)(x)$ must be the zero polynomial, and so $P_n(x)=q(x)$.

Sidi's Method: Root-Finding

In the secant method we had the formula:

Now considering in Lagrange form we have:

We see that the denominator is of the secant method is the slop of our interpolating polynomial.

Sidi's $k^{th}$ degree method then takes the derivative of a higher order interpolating polynomial.

where $p_{n,k}$ is the interpolating polynomial passing through

so we have the derivative of a trailing interpolating polynomial.
When $k=1$ this is the secant method.

Neville's Method: Recursive Construction

Suppose $P_{k,l}$ is the polynomial of degree at most $l$ interpolating the data

Then, by definition, $P_{0,n}$ is the polynomial of degree at most n interpolating the data

Moreover, this polynomial can be computed using the recursive formula:

noting that $m+1$ is the degree. $P_{0,n}(x)=L_n(x)$