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