Solution

For distinct nodes, define the divided difference by

f [x_{0}, \dots, x_{k}] = \sum_{j = 0}^{k} \frac{f ( x _{j} )}{\prod _{0 \leq i \leq k i \neq = j} ( x _{j} - x _{i} )} .

This is the coefficient of

x^{k}

k + 1

data points.

Let

p_{k}

denote that interpolating polynomial. The difference

p_{k} - p_{k - 1}

vanishes at

x_{0}, \dots, x_{k - 1}

, so

p_{k} (x) - p_{k - 1} (x) = c_{k} \prod_{i = 0}^{k - 1} (x - x_{i}) .

The Lagrange formula shows that the leading coefficient of

p_{k}

f [x_{0}, \dots, x_{k}]

, whereas

p_{k - 1}

has degree at most

k - 1

. Hence

c_{k} = f [x_{0}, \dots, x_{k}]

. Starting with

p_{0} = f (x_{0})

p_{n} (x) = f (x_{0}) + k = 1 \sum n f [x_{0}, \dots, x_{k}] i = 0 \prod k - 1 (x - x_{i}) .

The divided-difference recurrence is

f [x_{0}, \dots, x_{k}] = \frac{f [ x _{1} , \dots , x _{k} ] - f [ x _{0} , \dots , x _{k - 1} ]}{x _{k} - x _{0}} .

For three nodes, the triangular table is

f [x_{0}] f [x_{1}] f [x_{2}] ⟶ ⟶ f [x_{0}, x_{1}] ⟶ f [x_{0}, x_{1}, x_{2}] f [x_{1}, x_{2}]

where each entry in a new column uses the two adjacent entries to its left. There are

n

first differences,

n - 1

second differences, and so on, each requiring one division. The exact total is

n + (n - 1) + \dots + 1 = \frac{n ( n + 1 )}{2} .

Solved by gpt-5.6-sol high.

 Ancestors (10)