Root Finding 4
clear all
5.4 Newton Forward Differences and Lagrange PolynomialsPolynomials
We shall now discuss the operation of fitting an Nth order polynomial through N + 1 points and remark again this will yield a unique answer. We consider the set of data points: (x0, f0), (x1, f1), · · · , (xN, fN). We now introduce the difference operator ∆ such that
∆f0= f1− f0or in general ∆fj = fj+1− fj.
These are called forward differences, since points forward of the current value are used (there are also backward differences and central differences, which we shall meet in our discussion of the solution of differential equations). We consider the composition of the operator whereby
∆2f0= ∆(∆f0) = ∆(f1− f0) = ∆f1− ∆f0
= (f2− f1)− (f1− f0)
= f2− 2f1+ f0.
Of course we can now proceed to define ∆nf0in an iterative manner.
We introduce the polynomial f (x) = f0+ (x− x0)∆f0
h +(x− x0)(x− x1) 2!
∆2f0
h2 +· · · ,
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 ∆xj 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 ∆2f
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 differences;
for instance whether it was generated using a polynomial (in which case the differences 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− x2)(z− x3)(z− x4) It is worth pausing at this point and checking that this curve goes through each of the points (xj, fj). For example for j = 3, we set z = x3 and only the third term is non-zero and we have
f (x3) = (x3− x1)(x3− x2)(x3− x4)
(x3− x1)(x3− x2)(x3− x4)f3= 1× f3= f3.
Hence the value of the polynomial at z = x3is f3(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 finally 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 find a value of f z=0.6386, which is shown on the figure 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
fi
N j=1 j=i
z− xj
xi− xj
.
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 using1
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 fitting the data. Although as we will see in subsequent examples using high-order polynomials can lead to significant errors.
5.4.1 Linear Interpolation/Extrapolation
We consider the simplest case wherein we have two points (x1, y1) and (x2, y2).
The straight line through these is given by y = x− x2
x1− x2y1+ x− x1 x2− x1y2,
which here we have constructed in a Lagrange polynomial style. We note that the answer is independent of the process here and provided x1 = x2 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 first 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 first column against the second) using circles, whose size is specified by ’MarkerSize’ (and set equal to 12). We then hold the figure on which stops any future plotting commands overwriting the figure. Instead
they augment the current image. The next plotting command adds the straight lines. We then turn the holding off so the figure will be destroyed if we execute another plot command. We also add a grid to the figure.
Finally, we print the results to a Postscript file 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 file.
As mentioned above for convenience we can extract the data from the array data using:
x = data(:,1);
f = data(:,2);
clear data