20.4 Interpolation 569
When quadratic interpolation is used for each triple of neighbouring points we have
piecewise quadratic interpolation, as illustrated in Figure 20.6 for the points listed in
Table 20.4 (compare with Figures 20.5, 20.7, and 20.8).
Newton’s method of divided differences
The interpolating polynomialp
n(x)through (n 1 + 11 ) given points can be expressed in
a simple way in terms of divided differences. The first and second divided differences are
(20.19)
and in general
(20.20)
Equation (20.17) forp
1(x)is then
p
1(x) 1 = 1 y
01 + 1 (x 1 − 1 x
0)f[x
0, x
1]
= 1 p
0(x) 1 + 1 (x 1 − 1 x
0)f[x
0, x
1] (20.21)
and (20.18) forp
2(x)can be rewritten as
p
2(x) 1 = 1 y
01 + 1 (x 1 − 1 x
0)f[x
0, x
1] 1 + 1 (x 1 − 1 x
0)(x 1 − 1 x
1)f[x
0, x
1, x
2]
= 1 p
1(x) 1 + 1 (x 1 − 1 x
0)(x 1 − 1 x
1)f[x
0,x
1,x
2] (20.22)
In general,
p
k+ 1(x) 1 = 1 p
k(x) 1 + 1 (x 1 − 1 x
0)(x 1 − 1 x
1) -(x 1 − 1 x
k)f[x
0, x
1, =,x
k+ 1] (20.23)
The relations amongst the divided differences are demonstrated in Table 20.5 for
5 points. Column D
1contains the first divided differences, column D
2the second
divided differences, and so on. Each divided difference is the difference of its ‘parents’
in the column on its left, divided by the difference of the extreme values of x.
fx x x
fx x x fx x x
kkk[]
[][ ]
0112 01 1,, , =
,,, − ,,,
−...
......
xxx
k−
0fx x
yy
xx
fx x x
fx x f
[] [ ]
[][
01101001212,=
−
−
,,,=
,−xxx
xx
0120,
−
]
0
1
2
123
...............
........
...............................
...
..
...
...
..
...
...
...
..
...
...
..
...
..y
x
..........................................................................................................
........
.......
.....
....
....
....
...
...
...
...
..
...
...
..
..
..
..
..
...
.
..
..
..
..
..
.
..
..
.
..
.
..
.
..
................
........
.....
.....
....
....
....
...
...
....
...
...
...
...
...
...
...
...
...
...
...
...
...........................................................................................................................................................................................
...
....
...
..
...
...
..
...
...
..
...
..
..
...
..
..
...
..
...
..
...
..
...
...
..
....
...
...
....
....
.....
..................................................................................................
...
....
...
..
....
...
..
....
...
....
...
..
....
...
.......
...
........
..
...
......
...
...
...
...
..
....
....................................................................................................
..
...
....
...
....
...
..
.....
..
....
...
...
....
...
....................Figure 20.6