Numerical Analysis | Part IB, 2002

Let fC[a,b]f \in C[a, b] and let n+1n+1 distinct points x0,,xn[a,b]x_{0}, \ldots, x_{n} \in[a, b] be given.

(a) Define the divided difference f[x0,,xn]f\left[x_{0}, \ldots, x_{n}\right] of order nn in terms of interpolating polynomials. Prove that it is a symmetric function of the variables xi,i=0,,nx_{i}, i=0, \ldots, n.

(b) Prove the recurrence relation

f[x0,,xn]=f[x1,,xn]f[x0,,xn1]xnx0f\left[x_{0}, \ldots, x_{n}\right]=\frac{f\left[x_{1}, \ldots, x_{n}\right]-f\left[x_{0}, \ldots, x_{n-1}\right]}{x_{n}-x_{0}}

(c) Hence or otherwise deduce that, for any iji \neq j, we have

f[x0,,xn]=f[x0,,xi1,xi+1,,xn]f[x0,,xj1,xj+1,,xn]xjxi.f\left[x_{0}, \ldots, x_{n}\right]=\frac{f\left[x_{0}, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{n}\right]-f\left[x_{0}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}\right]}{x_{j}-x_{i}} .

(d) From the formulas above, show that, for any i=1,,n1i=1, \ldots, n-1,

f[x0,,xi1,xi+1,,xn]=γf[x0,,xn1]+(1γ)f[x1,,xn],f\left[x_{0}, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{n}\right]=\gamma f\left[x_{0}, \ldots, x_{n-1}\right]+(1-\gamma) f\left[x_{1}, \ldots, x_{n}\right],

where γ=xix0xnx0\gamma=\frac{x_{i}-x_{0}}{x_{n}-x_{0}}.

Typos? Please submit corrections to this page on GitHub.