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
  • Cubic 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 (such as Gaussian elimination).
  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
  

• 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
  $$\boxed{P_1(x)=y_1L_1(x)+y_2L_2(x)}$$

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

• Quadratic interpolation
  $$\boxed{P_2(x)=y_1L_1(x)+y_2L_2(x)+y_3L_3(x)}$$
  where $L_s$ are not the same with the previous $L_s$!

  $$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)}.$$

• Cubic interpolation
• Suppose we have a table of data with four pairs of $x$- and $f(x)$-values, with $x_i$ indexed by variable $i$:

  

  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_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 7.1 (first four points) and use it to find the interpolated value for $x=3.0$.

Table 7.3: Fitting a polynomial to data.

x	f(x)
3.2	22.0
2.7	17.8
1.0	14.2
4.8	38.3
5.6	51.7

$$P_3(x)=\frac{(x-2.7)(x-1.0)(x-4.8)}{(3.2-2.7)(3.2-1.0)(3.2-4.8)}22.0+$$

$$\frac{(x-3.2)(x-1.0)(x-4.8)}{(2.7-3.2)(2.7-1.0)(2.7-4.8)}17.8+$$

$$\frac{(x-3.2)(x-2.7)(x-4.8)}{(1.0-3.2)(1.0-2.7)(1.0-4.8)}14.2+$$

$$\frac{(x-3.2)(x-2.7)(x-1.0)}{(4.8-3.2)(4.8-2.7)(4.8-1.0)}38.3$$

• Carrying out the arithmetic, $P_3(3.0)=20.21$.
• 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)$$
  $$where~~\boxed{L_j(x)={\prod_{k=1,k\neq j}^n} \frac{x-x_k}{x_j-x_k}}$$

Example py-file: Interpolation of gasoline prices. Lagrange Interpolation. myLagInt_gasoline.py

Figure 7.3: Lagrange Polynomial Interpolation - Gasoline Case.

• 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.