Lagrangian Polynomials

• straightforward approach-the Lagrangian polynomial, the simplest way to exhibit the existence of a polynomial for interpolation with unevenly spaced data.
• Suppose we have a table of data with four pairs of $x$- and $f(x)$-values, with $x_i$ indexed by variable $i$:
  $$\begin{array}{rrr} i & x & f(x) \hline 0 & x_0 & f_0 \\ ... ...& f_1 \\ 2 & x_2 & f_2 \\ 3 & x_3 & f_3 \hline \end{array}$$

• Here we do not assume uniform spacing between the x-values, nor do we need the $x$-values arranged in a particular order. The x-values must all be distinct, however.
• Through these four data pairs we can pass a cubic. The Lagrangian form for this is
  $$P_3(x)=\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)}f_0+\frac{(x-x_0)(x-x_2)(x-x_3)}{(x_1-x_0)(x_1-x_2)(x_1-x_3)}f_1$$
  $$+\frac{(x-x_0)(x-x_1)(x-x_3)}{(x_2-x_0)(x_2-x_1)(x_2-x_3)}f_2+\frac{(x-x_0)(x-x_1)(x-x_2)}{(x_3-x_0)(x_3-x_1)(x_3-x_2)}f_3$$

• This equation is made up of four terms, each of which is a cubic in $x$; hence the sum is a cubic.
• The pattern of each term is to form the numerator as a product of linear factors of the form $(x - x_i)$, omitting one $x_i$ in each term, the omitted value being used to form the denominator by replacing $x$ in each of the numerator factors.
• In each term, we multiply by the $f_i$
• It will have $n + 1$ terms when the degree is $n$.
• Fit a cubic through the first four points of the preceding table and use it to find the interpolated value for $x=3.0$. Carrying out the arithmetic, $P_3(3.0)=20.21$.
• MATLAB gets interpolating polynomials readily. The cubic fitted to the first four points;

  >> x=[3.2 2.7 1.0 4.8]; y=[22.0 17.8 14.2 38.3];
  >> p=polyfit(x,y,3)
  >> xval=polyval(p,3.0)
  

• Error of Interpolation; When we fit a polynomial $P_n(x)$ to some data points, it will pass exactly through those points, but between those points $P_n(x)$ will not be precisely the same as the function $f(x)$ that generated the points (unless the function is that polynomial). How much is $P_n(x)$ different from $f(x)$? How large is the error of $P_n(x)$?
• An algorithm for interpolation from a Lagrange polynomial:
  
• It is most important that you never fit a polynomial of a degree higher than 4 or 5 to a set of points. If you need to fit to a set of more than six points, be sure to break up the set into subsets and fit separate polynomials to these.
• You cannot fit a function that is discontinuous or one whose derivative is discontinuous with a polynomial. This is because every polynomial is everywhere continuous and has continuous derivatives.