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