6C (Numerical Analysis)

Solution

x_{0}, \dots, x_{m}

, define the degree-

m

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

It is the leading coefficient of the unique degree-at-most-

m

p_{n} (x) = f [x_{0}] + \sum_{m = 1}^{n} f [x_{0}, \dots, x_{m}] \prod_{i = 0}^{m - 1} (x - x_{i}) .

The partial polynomial

p_{m}

agrees with

p_{m - 1}

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

. Moreover, the explicit formula for the divided difference gives

f [x_{0}, \dots, x_{m}] = \frac{f ( x _{m} ) - p _{m - 1} ( x _{m} )}{\prod _{i = 0}^{m - 1} ( x _{m} - x _{i} )},

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

. Induction shows that

p_{n} (x_{j}) = f (x_{j})

for every

j

For the recursion, substitute the explicit formulas for

f [x_{1}, \dots, x_{m}]

and

f [x_{0}, \dots, x_{m - 1}]

. For an interior index

j

f (x_{j})

in their difference is

\frac{1}{( x _{j} - x _{m} ) \prod _{1 \leq k \leq m - 1 k \neq = j} ( x _{j} - x _{k} )} - \frac{1}{( x _{j} - x _{0} ) \prod _{1 \leq k \leq m - 1 k \neq = j} ( x _{j} - x _{k} )} = \frac{x _{m} - x _{0}}{\prod _{0 \leq k \leq m k \neq = j} ( x _{j} - x _{k} )} .

The endpoint terms satisfy the same identity directly. Dividing by

x_{m} - x_{0}

therefore gives

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

There are no discussions about this article yet.

There are currently no matching articles.