In Newtons form of the interpolation polynomial we need to compute the coefficients, c0 = f[x0],c1 = f[x0,x1],...,cn = f[x0,x1,...,xn]. In the table of divided differences we proceed column by column and the needed coefficients are in the uppermost di- agonal. A simple 1D array, c of size n + 1, can be used to store and compute these values. We just have to compute them from bottom to top to avoid losing values we have already computed. The following pseudocode does precisely this: for j = 0,1...,n cj =fj; end for k = 1,...n for j = n, n 1, . . . k cj = (cj cj1)/(xj xjk); end end

The evaluation of the interpolation polynomial in Newtons form can be then done with the Horner-like scheme seen in class:

p = cn for j = n 1, n 2, . . . , 0

p=cj +(xxj)p; end

(a) Write computer codes to compute the coefficients c0, c1, . . . , cn and to evaluate the corresponding interpolation polynomial at an arbitrary point x. Test your codes and turn in a run of your test. (b) Consider the function f(x) = ex2 for x [1,1] and the nodes xj = 1+j(2/10), j = 0,1,...,10. Use your code(s) in (a) to evaluate P10(x) at the points x j = 1 + j(2/100), j = 0, 1, . . . , 100 and plot the error f(x) P10(x).

In Newton's form of the interpolation polynomial we need to compute the coefficients, Co = fFol , ci = f[ao, x1j, . . . , cn-fFo, xi, . . . , Xn]. In the table of divided differences we proceed column by column and the needed coefficients are in the uppermost di agonal. A simple 1D array, c of size n + 1, can be used to store and compute these values. We just have to compute them from bottom to top to avoid losing values we have already computed. The following pseudocode does precisely thiS: recisely this: for j = 0.1 ,n end for k 1,n for j = n,n-1, k end end