Lagrangian Polynomials

• Straightforward approach-the Lagrangian polynomial.
• The simplest way to exhibit the existence of a polynomial for interpolation with unevenly spaced data.
  • Linear interpolation
  • Quadratic interpolation
• Lagrange polynomials have two important advantages over interpolating polynomials.
  1. the construction of the interpolating polynomials does not require the solution of a system of equations.
  2. the evaluation of the Lagrange polynomials is much less susceptible to roundoff.

• Linear interpolation
  
  $$P_1(x)=c_1x+c_2$$
  
  

• put the values
  
  $$\begin{array}{rl} y_1= &c_1x_1+c_2 \\ \hline y_2= &c_1x_2+c_2 \\ \hline \end{array}$$
  
  

• then

  
  

  $$c_1=\frac{y_2-y_1}{x_2-x_1}$$
  
  

  
  

  $$c_2=\frac{y_1x_2-y_2x_1}{x_2-x_1}$$
  
  

• substituting back and rearranging
  
  $$P_1(x)=y_1\frac{x-x_2}{x_1-x_2}+y_2\frac{x-x_1}{x_2-x_1}$$
  
  

• redefining as
  
  $$P_1(x)=y_1L_1(x)+y_2L_2(x)$$
  
  

• where Ls are the first-degree Lagrange interpolating polynomials.

• Quadratic interpolation
  
  $$P_2(x)=y_1L_1(x)+y_2L_2(x)+y_3L_3(x)$$
  
  
  where Ls are not the same with the previous Ls!!!

  
  

  $$L_1(x)=\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)},$$
  
  

  
  

  $$L_2(x)=\frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)},$$
  
  

  
  

  $$L_3(x)=\frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}.$$
  
  

• In general

  
  

  $$P_{n-1}(x)=$$
  
  

  
  

  $$y_1L_1(x)+y_2L_2(x)+\ldots+y_nL_n(x)=$$
  
  

  
  

  $$\sum_{j=1}^ny_jL_j(x)$$
  
  

  
  

  $$L_j(x)={\prod_{k=1,k\neq j}^n} \frac{x-x_k}{x_j-x_k}$$
  
  

• 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} \hline i & x & f(x) \\ \hline 0 & x_0 & f... ...& f_1 \\ 2 & x_2 & f_2 \\ 3 & x_3 & f_3 \\ \hline \end{array}$$
  
  

  Through these four data pairs we can pass a cubic.

   
  

• The Lagrangian form 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... ...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.
  
  $$P_3(x)=\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x... ...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$$
  
  

• 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 1 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;

  
• Example m-file: Interpolation of gasoline prices with Lagrange Polynomials. (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter3/demoGasLag.mdemoGasLag.m http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter3/lagrint.mlagrint.m)

• 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)$?
• 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.