3 Polynomial approximations - exact data

Here and in subsections 4 and 5 we consider cases where, rather than knowing an expression for the function, we have a list of point values. Sometimes it is good enough to find a polynomial that passes near these points (like putting a straight line through experimental data). Such a polynomial is an approximating polynomial and this case follows in subsection 4. Here and in subsection 5 we deal with the case where we want a polynomial to pass exactly through the given data, that is, an interpolating polynomial .

3.1 Lagrange interpolation

Suppose that we know (or choose to sample) a function $f$ exactly at a few points and that we want to approximate how the function behaves between those points. In its simplest form this is equivalent to a dot-to-dot puzzle (see Figure 1(a)), but it is often more desirable to seek a curve that does not have“corners" in it (see Figure 1(b)).

Let us suppose that the data are in the form $\left(x_1,f_1\right)$ , $\left(x_2,f_2\right)$ , $\left(x_3,f_3\right)$ , …, these are the points plotted as crosses on the diagrams above. (For technical reasons, and those of common sense, we suppose that the $x$ -values in the data are all distinct.)

Our aim is to find a polynomial which passes exactly through the given data points. We want to find $p\left(x\right)$ such that

$p\left(x_1\right)=f_1,p\left(x_2\right)=f_2,p\left(x_3\right)=f_3,\dots$

There is a mathematical trick we can use to achieve this. We define Lagrange polynomials $L_1$ , $L_2$ , $L_3$ , $\dots$ which have the following properties:

$\begin{array}{ccccccccccc}{L}_1\left(x\right)\hfill & \hfill =\hfill & 1,\hfill & \hfill & \text{at }x=x_1,\hfill & \hfill & L_1\left(x\right)\hfill & \hfill =\hfill & 0,\hfill & \hfill & \text{at }x=x_2,x_3,x_4\dots \hfill \\ L_2\left(x\right)\hfill & \hfill =\hfill & 1,\hfill & \hfill & \text{at }x=x_2,\hfill & \hfill & L_2\left(x\right)\hfill & \hfill =\hfill & 0,\hfill & \hfill & \text{at }x=x_1,x_3,x_4\dots \hfill \\ L_3\left(x\right)\hfill & \hfill =\hfill & 1,\hfill & \hfill & \text{at }x=x_3,\hfill & \hfill & L_3\left(x\right)\hfill & \hfill =\hfill & 0,\hfill & \hfill & \text{at }x=x_1,x_2,x_4\dots \hfill \\ \hfill & \hfill ⋮\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill ⋮\hfill \end{array}$

Each of these functions acts like a filter which “turns off" if you evaluate it at a data point other than its own. For example if you evaluate $L_2$ at any data point other than $x_2$ , you will get zero.

Furthermore, if you evaluate any of these Lagrange polynomials at its own data point, the value you get is 1. These two properties are enough to be able to write down what $p\left(x\right)$ must be:

$p\left(x\right)=f_1{L}_1\left(x\right)+f_2{L}_2\left(x\right)+f_3{L}_3\left(x\right)+\dots$

and this does work, because if we evaluate   $p$   at one of the data points, let us take $x_2$ for example, then

$p\left(x_2\right)=f_1\underset{=0}{\underset{⏟}{L_1\left(x_2\right)}}+f_2\underset{=1}{\underset{⏟}{L_2\left(x_2\right)}}+f_3\underset{=0}{\underset{⏟}{L_3\left(x_2\right)}}+\cdots =f_2$

as required. The filtering property of the Lagrange polynomials picks out exactly the right $f$ -value for the current $x$ -value. Between the data points, the expression for $p$ above will give a smooth polynomial curve.

This is all very well as long as we can work out what the Lagrange polynomials are. It is not hard to check that the following definitions have the right properties.

In each case the numerator ensures that the filtering property is in place, that is that the functions switch off at data points other than their own. The denominators make sure that the value taken at the remaining data point is equal to 1.

Figure 2

Figure 2 shows $L_1$ and $L_2$ in the case where there are five data points (the $x$ positions of these data points are shown as large dots). Notice how both $L_1$ and $L_2$ are equal to zero at four of the data points and that $L_1\left(x_1\right)=1$ and $L_2\left(x_2\right)=1$ .

In an implementation of this idea, things are simplified by the fact that we do not generally require an expression for $p\left(x\right)$ . (This is good news, for imagine trying to multiply out all the algebra in the expressions for $L_1$ , $L_2$ , ….) What we do generally require is   $p$   evaluated at some specific value. The following Example should help show how this can be done.

Example 3

Let $p\left(x\right)$ be the polynomial of degree 3 which interpolates the data

$\begin{array}{ccccc}\hfill x\hfill & \hfill 0.8\hfill & \hfill 1\hfill & \hfill 1.4\hfill & \hfill 1.6\hfill \\ ̲& ̲& ̲& ̲& ̲\\ \hfill f\left(x\right)\hfill & \hfill -1.82\hfill & \hfill -1.73\hfill & \hfill -1.40\hfill & \hfill -1.11\hfill \end{array}$

Evaluate $p\left(1.1\right)$ .

Solution

We are interested in the Lagrange polynomials at the point $x=1.1$ so we consider

$L_1\left(1.1\right)=\frac{\left(1.1-x_2\right)\left(1.1-x_3\right)\left(1.1-x_4\right)}{\left(x_1-x_2\right)\left(x_1-x_3\right)\left(x_1-x_4\right)}=\frac{\left(1.1-1\right)\left(1.1-1.4\right)\left(1.1-1.6\right)}{\left(0.8-1\right)\left(0.8-1.4\right)\left(0.8-1.6\right)}=-0.15625.$

Similar calculations for the other Lagrange polynomials give

$L_2\left(1.1\right)=0.93750,L_3\left(1.1\right)=0.31250,L_4\left(1.1\right)=-0.09375,$

and we find that our interpolated polynomial, evaluated at $x=1.1$ is

Task!

Let $p\left(x\right)$ be the polynomial of degree 3 which interpolates the data

$\begin{array}{ccccc}\hfill x\hfill & \hfill 0.1\hfill & \hfill 0.2\hfill & \hfill 0.3\hfill & \hfill 0.4\hfill \\ ̲& ̲& ̲& ̲& ̲\\ \hfill f\left(x\right)\hfill & \hfill 0.91\hfill & \hfill 0.70\hfill & \hfill 0.43\hfill & \hfill 0.52\hfill \end{array}$

Evaluate $p\left(0.15\right)$ .

Answer

The next Example is very much the same as Example 3 and the Task above. Try not to let the specific application, and the slight change of notation, confuse you.

Example 4

A designer wants a curve on a diagram he is preparing to pass through the points

$\begin{array}{ccccc}\hfill x\hfill & \hfill 0.25\hfill & \hfill 0.5\hfill & \hfill 0.75\hfill & \hfill 1\hfill \\ ̲& ̲& ̲& ̲& ̲\\ \hfill y\hfill & \hfill 0.32\hfill & \hfill 0.65\hfill & \hfill 0.43\hfill & \hfill 0.10\hfill \end{array}$

He decides to do this by using an interpolating polynomial $p\left(x\right)$ . What is the $y$ -value corresponding to $x=0.8$ ?

Solution

We are interested in the Lagrange polynomials at the point $x=0.8$ so we consider

$L_1\left(0.8\right)=\frac{\left(0.8-x_2\right)\left(0.8-x_3\right)\left(0.8-x_4\right)}{\left(x_1-x_2\right)\left(x_1-x_3\right)\left(x_1-x_4\right)}=\frac{\left(0.8-0.5\right)\left(0.8-0.75\right)\left(0.8-1\right)}{\left(0.25-0.5\right)\left(0.25-0.75\right)\left(0.25-1\right)}=0.032.$

Similar calculations for the other Lagrange polynomials give

$L_2\left(0.8\right)=-0.176,L_3\left(0.8\right)=1.056,L_4\left(0.8\right)=0.088,$

and we find that our interpolated polynomial, evaluated at $x=0.8$ is

In this next Task there are five points to interpolate. It therefore takes a polynomial of degree 4 to interpolate the data and this means we must use five Lagrange polynomials.

Task!

The hull drag $f$ of a racing yacht as a function of the hull speed, $v$ , is known to be

$\begin{array}{cccccc}\hfill v\hfill & \hfill 0.0\hfill & \hfill 0.5\hfill & \hfill 1.0\hfill & \hfill 1.5\hfill & \hfill 2.0\hfill \\ ̲& ̲& ̲& ̲& ̲& ̲\\ \hfill f\hfill & \hfill 0.00\hfill & \hfill 19.32\hfill & \hfill 90.62\hfill & \hfill 175.71\hfill & \hfill 407.11\hfill \end{array}$

(Here, the units for $f$ and $v$ are N and $\text{m}{\text{s}}^{-1}$ , respectively.)

Use Lagrange interpolation to fit this data and hence approximate the drag corresponding to a hull speed of $2.5\text{m}{\text{s}}^{-1}$ .

Answer

The following Example has time $t$ as the independent variable, and two quantities, $x$ and $y$ , as dependent variables to be interpolated. We will see however that exactly the same approach as before works.

Example 5

An animator working on a computer generated cartoon has decided that her main character’s right index finger should pass through the following $\left(x,y\right)$ positions on the screen at the following times $t$

$\begin{array}{ccccc}\hfill t\hfill & \hfill 0\hfill & \hfill 0.2\hfill & \hfill 0.4\hfill & \hfill 0.6\hfill \\ ̲& ̲& ̲& ̲& ̲\\ \hfill x\hfill & \hfill 1.00\hfill & \hfill 1.20\hfill & \hfill 1.30\hfill & \hfill 1.25\hfill \\ \hfill y\hfill & \hfill 2.00\hfill & \hfill 2.10\hfill & \hfill 2.30\hfill & \hfill 2.60\hfill \end{array}$

Use Lagrange polynomials to interpolate these data and hence find the $\left(x,y\right)$ position at time $t=0.5$ . Give $x$ and $y$ to 2 decimal places.

Solution

In this case $t$ is the independent variable, and there are two dependent variables: $x$ and $y$ . We are interested in the Lagrange polynomials at the time $t=0.5$ so we consider

$L_1\left(0.5\right)=\frac{\left(0.5-t_2\right)\left(0.5-t_3\right)\left(0.5-t_4\right)}{\left(t_1-t_2\right)\left(t_1-t_3\right)\left(t_1-t_4\right)}=\frac{\left(0.5-0.2\right)\left(0.5-0.4\right)\left(0.5-0.6\right)}{\left(0-0.2\right)\left(0-0.4\right)\left(0-0.6\right)}=0.0625$

Similar calculations for the other Lagrange polynomials give

$L_2\left(0.5\right)=-0.3125,L_3\left(0.5\right)=0.9375,L_4\left(0.5\right)=0.3125$

These values for the Lagrange polynomials can be used for both of the interpolations we need to do. For the $x$ -value we obtain

and for the $y$ value we get

3.2 Error in Lagrange interpolation

When using Lagrange interpolation through $n$ points $\left(x_1,f_1\right),\left(x_2,f_2\right),\dots ,\left(x_n,f_n\right)$ the error, in the estimate of $f\left(x\right)$ is given by

$E\left(x\right)=\frac{\left(x-x_1\right)\left(x-x_2\right)\dots \left(x-x_n\right)}{n!}{f}^{\left(n\right)}\left(\eta \right)$ where $\eta \in \left[x,x_1,x_n\right]$

N.B. The value of $\eta$ is not known precisely, only the interval in which it lies. Normally $x$ will lie in the interval $\left[x_1,x_n\right]$ (that’s interpolation ). If $x$ lies outside the interval $\left[x_1,x_n\right]$ then that’s called extrapolation and a larger error is likely.

Of course we will not normally know what $f$ is (indeed no $f$ may exist for experimental data). However, sometimes $f$ can at least be estimated. In the following (somewhat artificial) example we will be told $f$ and use it to check that the above error formula is reasonable.

Example 6

In an experiment to determine the relationship between power gain ( $G$ ) and power output ( $P$ ) in an amplifier, the following data were recorded.

1. Use Lagrange interpolation to fit an appropriate quadratic, $q\left(x\right)$ , to estimate the gain when the output is 6.5. Give your answer to an appropriate accuracy.
2. Given that $G\equiv 10{log}_{10}\left(P∕5\right)$ show that the actual error which occurred in the Lagrange interpolation in 1. lies withing the theoretical error limits.

Solution

1. For a quadratic, $q\left(x\right)$ , we need to fit three points and those most appropriate (nearest $6.5$ ) are for $P$ at $5,7,8$ : $$\begin{array}{rcll}q\left(6.5\right)& =& \frac{\left(6.5-7\right)\left(6.5-8\right)}{\left(5-7\right)\left(5-8\right)}\times 0.00& \\ & +& \frac{\left(6.5-5\right)\left(6.5-8\right)}{\left(7-5\right)\left(7-8\right)}\times 1.46& \\ & +& \frac{\left(6.5-5\right)\left(6.5-7\right)}{\left(8-5\right)\left(8-7\right)}\times 2.04& \\ & =& 0+1.6425-0.5100& \\ & =& 1.1325\text{working to }4\text{d.p.}& \\ & \approx & 1.1\text{(rounding to sensible accuracy)}& \end{array}$$
2. We use the error formula

   $E\left(x\right)=\frac{\left(x-x_1\right)\dots \left(x-x_n\right)}{n!}{f}^{\left(n\right)}\left(\eta \right),\eta \in \left[x,x_1,\dots ,x_n\right]$

   Here $f\left(x\right)\equiv G\left(x\right)={log}_{10}\left(P∕5\right)$ and $n=3$ :

   $$\begin{array}{rcll}\frac{d\left({log}_{10}\left(P∕5\right)\right)}{dP}& =& \frac{d\left({log}_{10}\left(P\right)-{log}_{10}\left(5\right)\right)}{dP}=\frac{d\left({log}_{10}\left(P\right)\right)}{dP}& \\ & =& \frac{d}{dP}\left(\frac{lnP}{ln10}\right)=\frac{1}{ln10}\frac{1}{P}& \end{array}$$

   So $\frac{d^3}{d{P}^3}\left({log}_{10}\left(P∕5\right)\right)=\frac{1}{ln10}\frac{2}{P^3}$ .

   Substituting for $f^{\left(3\right)}\left(\eta \right)$ :

   $$\begin{array}{rcll}E\left(6.5\right)& =& \frac{\left(6.5-6\right)\left(6.5-7\right)\left(6.5-8\right)}{6}\times \frac{10}{ln10}\times \frac{2}{{\eta }^3},\eta \in \left[5,8\right]& \\ & =& \frac{1.6286}{{\eta }^3}\eta \in \left[5,8\right]& \end{array}$$

   Taking $\eta =5$ : $E_{\text{max}}=0.0131$

   Taking $\eta =8$ :      $E_{\text{min}}=0.0031$

   $$\begin{array}{rcll}\text{Taking }x=6.5:E_{\text{actual}}=G\left(6.5\right)-q\left(6.5\right)& =& 10{log}_{10}\left(6.5∕5\right)-1.1325& \\ & =& 1.1394-1.1325& \\ & =& 0.0069& \end{array}$$

   The theory is satisfied because $E_{\text{min}}<E_{\text{actual}}<E_{\text{max}}$ .

Task!

1. Use Lagrange interpolation to estimate $f\left(8\right)$ to appropriate accuracy given the table of values below, by means of the appropriate cubic interpolating polynomial

   $x$	2	5	7	9	10
   $f\left(x\right)$	0.980067	0.8775836	0.764842	0.621610	0.540302

   Answer

   The most appropriate cubic passes through $x$ at $5,7,9,10$

   $x=8x_1=5,x_2=7,x_3=9,x_4=10$

   $$\begin{array}{rcll}p\left(8\right)& =& \frac{\left(8-7\right)\left(8-9\right)\left(8-10\right)}{\left(5-7\right)\left(5-9\right)\left(5-10\right)}\times 0.877583& \\ & +& \frac{\left(8-5\right)\left(8-9\right)\left(8-10\right)}{\left(7-5\right)\left(7-9\right)\left(7-10\right)}\times 0.764842& \\ & +& \frac{\left(8-5\right)\left(8-7\right)\left(8-10\right)}{\left(9-5\right)\left(9-7\right)\left(9-10\right)}\times 0.621610& \\ & +& \frac{\left(8-5\right)\left(8-7\right)\left(8-9\right)}{\left(10-5\right)\left(10-7\right)\left(10-9\right)}\times 0.540302& \\ & =& -\frac{1}{20}\times 0.877583+\frac{1}{2}\times 0.764842+\frac{3}{4}\times 0.621610-\frac{1}{5}\times 0.540302& \\ & =& 0.6966689& \end{array}$$

   Suitable accuracy is $0.6967$ (rounded to $4$  d.p.).

2. Given that the table in 1. represents $f\left(x\right)\equiv cos\left(x∕10\right)$ , calculate theoretical bounds for the estimate obtained:

   Answer

   $E\left(8\right)=\frac{\left(8-5\right)\left(8-7\right)\left(8-9\right)\left(8-10\right)}{4!}{f}^{\left(4\right)}\left(\eta \right),5\le \eta \le 10$

   $f\left(\eta \right)=cos\left(\frac{\eta }{10}\right)\text{so}{f}^{\left(4\right)}\left(\eta \right)=\frac{1}{10^4}cos\left(\frac{\eta }{10}\right)$

   $E\left(8\right)=\frac{1}{4\times 10^4}cos\left(\frac{\eta }{10}\right),\eta \in \left[5,10\right]$

   $E_{\text{min}}=\frac{1}{4\times 10^4}cos\left(1\right)E_{\text{max}}=\frac{1}{4\times 10^4}cos\left(0.5\right)$

   This leads to

   $0.696689+0.000014\le \text{True Value}\le 0.696689+0.000022$

   $\Rightarrow 0.696703\le \text{True Value}\le 0.696711$

   We can conclude that the True Value is $0.69670$ or $0.69671$ to $5$  d.p. or $0.6967$ to $4$  d.p. (actual value is $0.696707$ ).