** Root Finding 4**

** clear all**

**5.4 Newton Forward Diﬀerences and Lagrange PolynomialsPolynomials**

*We shall now discuss the operation of ﬁtting an N*^{th} order polynomial through
*N + 1 points and remark again this will yield a unique answer. We consider*
*the set of data points: (x*_{0}*, f*_{0}*), (x*_{1}*, f*_{1}), *· · · , (x**N**, f** _{N}*). We now introduce the

*diﬀerence operator ∆ such that*

*∆f*_{0}*= f*_{1}*− f*0*or in general ∆f*_{j}*= f*_{j}_{+1}*− f**j**.*

*These are called forward diﬀerences, since points forward of the current value*
are used (there are also backward diﬀerences and central diﬀerences, which
we shall meet in our discussion of the solution of diﬀerential equations). We
consider the composition of the operator whereby

*∆*^{2}*f*_{0}*= ∆(∆f*_{0}*) = ∆(f*_{1}*− f*_{0}*) = ∆f*_{1}*− ∆f*_{0}

*= (f*_{2}*− f*_{1})*− (f*_{1}*− f*_{0})

*= f*_{2}*− 2f*_{1}*+ f*_{0}*.*

*Of course we can now proceed to deﬁne ∆*^{n}*f*_{0}in an iterative manner.

We introduce the polynomial
*f (x) = f*_{0}*+ (x− x*_{0})*∆f*_{0}

*h* +*(x− x*_{0}*)(x− x*_{1})
2!

*∆*^{2}*f*_{0}

*h*^{2} +*· · · ,*

*which will ultimately terminate after N terms. Alternatively this can be written*
as:

*We consider the data values to be equally spaced, so the value of ∆x**j* *is h∀j.*

This analysis can be extended to irregularly spaced points, but we shall not attempt that here.

We are now able to construct the polynomial (5.1) for a set of points. We start with a simple example.

**Example 5.1 Let us consider the points (0, 1), (1, 3) and (2, 4). Here we have***three points and as such we would expect to obtain a quadratic. We use a tabular*
*form, which gives:*

*x* *f* *∆f* *∆*^{2}*f*

*0* *1* *2* *−1*

*1* *3* *1*

*2* *4*

*Thus we have*

It is possible to prove that the polynomial (5.1) goes through each of the set of points, but we shall not include that proof here. We remark that vari-ous conclusions can be drawn from the data by using the forward diﬀerences;

for instance whether it was generated using a polynomial (in which case the diﬀerences truncate).

We now construct a polynomial which goes through a set of points which are not necessarily evenly spaced. Let us consider the polynomial

*f (z)* = *(z− x*_{2}*)(z− x*_{3}*)(z− x*_{4})
It is worth pausing at this point and checking that this curve goes through
*each of the points (x*_{j}*, f*_{j}*). For example for j = 3, we set z = x*_{3} and only the
third term is non-zero and we have

*f (x*_{3}) = *(x*_{3}*− x*1*)(x*_{3}*− x*2*)(x*_{3}*− x*4)

*(x*_{3}*− x*_{1}*)(x*_{3}*− x*_{2}*)(x*_{3}*− x*_{4})*f*_{3}= 1*× f*3*= f*_{3}*.*

*Hence the value of the polynomial at z = x*_{3}*is f*_{3}(as we would hope). This is an
**example of a Lagrange polynomial; which could have equally been written**
as

This is a convenient way to write out the cubic we require (as it is relatively easily extended to higher-order cases) and in order to evaluate it we can use the MATLAB code:

**'**

**&**

**$**

**%**
ip = 1:4;

f_z = 0.0;

for ii = 1:4

jj = find(ip˜=ii);

prod = f(ip(ii));

for kk = jj

prod = prod *(z-x(ip(kk)))/(x(ip(ii))-x(ip(kk)));

end

f_z = f_z + prod;

end

This code probably needs some explanation.

**– Firstly we set up a vector ip=1:4 which runs from one to four,**

**– and then we have a new variable f z which will ultimately contain our**
*estimate of the function at the point z.*

**– We now run through the terms in Equation (5.2).**

**– Inside the loop we construct a vector jj = find(ip***∼=ii), which now *
con-tains the indices of the locations in vector ip which are not equal to the
current value of ii. The initial value of the variable prod is set equal to the
function evaluated at the corresponding grid point ip(1) etc.

**– We then go through the individual terms in the product**

**– and then ﬁnally add this onto the value f z until we have gone through the**
four terms.

This code has been written in this way so it could be extended to as many points as we want.

*For z = 0.6 we ﬁnd a value of f z=0.6386, which is shown on the ﬁgure as*
an asterisk:

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

−5

−4

−3

−2

−1 0 1 2

As mentioned we can write this expression as a summation of products and
*this is easily extended to N points as*

*f (z)≈*
*N*

*i*=1

*f**i*

*N*
*j*=1
*j**=i*

*z− x**j*

*x*_{i}*− x**j*

*.*

Consider the code:

**'**

**&**

**$**

**%**
function [value] = poly_int(z,N)

global x f

imax = length(x);

if mod(N,2) ˜= 0

disp(’ N should be even ’) break

elseif N >= imax;

disp(’Too many points used’) break

end M = N/2;

[ibottom,itop] = findrange(x,z,N);

ip = ibottom:itop;

il = 1:N;

f_z = 0.0;

for ii = 1:N

jj = find(il˜=ii);

prod = f(ip(ii));

for kk = jj

prod = prod *(z-x(ip(kk))) ...

/(x(ip(ii))-x(ip(kk)));

end

f_z = f_z + prod;

end

value = f_z;

And now test the code using^{1}

1 We have re-introduced the command isempty, which is true if its argument is empty.

**'**

**&**

**$**

**%**
global x f

load data.dat x = data(:,1);

f = data(:,2);

N = length(x);

xmin = x(1); xmax = x(N);

xtest = linspace(xmin,xmax,20);

for ii = 1:20

[ftest(ii)] = poly_int(xtest(ii),N);

end

plot(x,f,’r’,xtest,ftest,’b’) This gives the plot

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

−6

−5

−4

−3

−2

−1 0 1 2

As you can see using six points works quite well at ﬁtting the data. Although as we will see in subsequent examples using high-order polynomials can lead to signiﬁcant errors.

**5.4.1 Linear Interpolation/Extrapolation**

*We consider the simplest case wherein we have two points (x*_{1}*, y*_{1}*) and (x*_{2}*, y*_{2}).

The straight line through these is given by
*y =* *x− x*_{2}

*x*_{1}*− x*2*y*_{1}+ *x− x*_{1}
*x*_{2}*− x*1*y*_{2}*,*

which here we have constructed in a Lagrange polynomial style. We note that
*the answer is independent of the process here and provided x*_{1} *
= x*_{2} we will
always get a straight line. This can be continued for quadratics and higher
order functions.

This is a plot of the data we shall use for this discussion:

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

−5

−4

−3

−2

−1 0 1 2

This was obtained using the commands:

**'**

**&**

**$**

**%**
clear all

load ’data.dat’

plot(data(:,1),data(:,2),’o’,’MarkerSize’,12) hold on

plot(data(:,1),data(:,2)) hold off

grid on

print -dps2 data.ps

The ﬁrst two commands merely load the data as discussed in the previous section (the code to generate this data is given on page 137). The next command plots the data (the ﬁrst column against the second) using circles, whose size is speciﬁed by ’MarkerSize’ (and set equal to 12). We then hold the ﬁgure on which stops any future plotting commands overwriting the ﬁgure. Instead

they augment the current image. The next plotting command adds the straight lines. We then turn the holding off so the ﬁgure will be destroyed if we execute another plot command. We also add a grid to the ﬁgure.

Finally, we print the results to a Postscript ﬁle so that it can be included in another document (for instance this text) or sent to a printer. There are many options for this command, for instance we could use print -djpeg90 data.jpg to generate a JPEG ﬁle.

As mentioned above for convenience we can extract the data from the array data using:

x = data(:,1);

f = data(:,2);

clear data