Graphics Programs Reference
In-Depth Information
%USAGE:a=newtonCoeff(xData,yData)
% xData = x-coordinates of data points.
% yData = y-coordinates of data points.
n = length(xData);
a = yData;
fork=2:n
a(k:n) = (a(k:n) - a(k-1))./(xData(k:n) - xData(k-1));
end
Initially, a contains the y -values of the data,sothat it is identical to the second
column in Table 3.1. Each pass through the for-loopgenerates the entries in the next
column, which overwrite the corresponding elements of a . Therefore, a ends up con-
taining the diagonaltermsofTable 3.1; i.e., the coefficients of the polynomial.
Neville's Method
Newton's method of interpolation involves two steps: computation of the coefficients,
followedbyevaluation of the polynomial. This works well if the interpolationiscarried
out repeatedlyat different values of x using the same polynomial. If only one point is
to be interpolated, amethod thatcomputes the interpolant in a single step,such as
Neville's algorithm, is abetter choice.
Let P k [ x i ,
x i + 1 ,...,
x i + k ] denote the polynomialofdegree k that passes through
the k
+
1datapoints ( x i ,
y i )
,
( x i + 1 ,
y i + 1 )
,...,
( x i + k ,
y i + k ).Forasingle datapoint, we
have
P 0 [ x i ]
=
y i
(3.7)
The interpolant based on two datapoints is
( x
x i + 1 ) P 0 [ x i ]
+
( x i
x ) P 0 [ x i + 1 ]
P 1 [ x i ,
x i + 1 ]
=
x i
x i + 1
It iseasilyverified that P 1 [ x i ,
x i + 1 ] passes through the two datapoints; that is,
P 1 [ x i ,
x i + 1 ]
=
y i when x
=
x i ,
and P 1 [ x i ,
x i + 1 ]
=
y i + 1 when x
=
x i + 1 .
The three-point interpolant is
( x
x i + 2 ) P 1 [ x i ,
x i + 1 ]
+
( x i
x ) P 1 [ x i + 1 ,
x i + 2 ]
P 2 [ x i
,
x i + 1
,
x i + 2 ]
=
x i + 2
To show thatthis interpolant does intersect the datapoints, we first substitute x
x i
=
x i ,
obtaining
P 2 [ x i ,
x i + 1 ,
x i + 2 ]
=
P 1 [ x i ,
x i + 1 ]
=
y i
Search WWH ::

Custom Search