1.  This question is concerned with applications of divided difference tables and Newton polynomials

in root finding algorithms . The notation fk  = f(ck ) is used throughout .  Suppose that f(c) = 0

and let c0 ,c1 , . . . be a sequence of approximations to c. Consider the Newton polynomial through the three points (cj ,fj ), (cj ≠ 1 ,fj ≠ 1 ) and (cj ≠2 ,fj ≠2 ), i .e.

Pj (x) = fj + f[cj ,cj ≠ 1](x ≠ cj )+ f[cj ,cj ≠ 1 ,cj ≠2](x ≠ cj )(x ≠ cj ≠ 1 ).                  ( ú )

In general, cj+1  is taken to be the root of Pj (x) that is closer to cj . The ordering of the points has been set to make it clear that cj+1  = cj  if fj  = 0.

(a)   (i)  Let Áj  = cj  ≠ c . Write down an expression for f(x) as a Taylor series about x = c and then set x = cj .  Use the resulting expression to show that

f[cj ,ck ] =   ∆jk(p)      and    f[cj ,ck ,c¸ ] = Áj   Á¸    1∆jk(p) ≠ ∆k(p)¸ 2,

for distinct integers j , k and ¸, with ∆jk(p)  = Áj(p) ≠ Ák(p)

Áj  ≠ Ák .

(ii)  Obtain polynomial expressions for ∆j(2)k  and ∆j(3)k  and simplify these as far as possible .

(iii)  Show that

(b)   (i)  Using the results of part (a), find the coeicients of f\ (c), f\\ (c) and f\\\ (c) on the right-hand side of ( ú ) in the case where j = 2 and x = c3 . Write your answers in terms of Á0 , . . . , Á3 .  Hence show that

≠f\ (c)Á3  ¥  +  ËÁ3(2)(Á0 + Á1 + Á2 ) ≠ Á3 (Á0 Á 1 + Á1 Á2 + Á0 Á2 )+ Á2 Á 1 Á0 È .

(ii)  Explain why the leading-order relationship must be

≠f\ (c)Á3  ¥ Á2 Á 1 Á0 ,

and hence show that if Áj+1  ¥ AÁj(—)  for a constant A , then — is the real solution of the

equation r3  = r2  + r +1 .

(iii) What conclusions can be drawn about the rate of convergence of the sequence c0 ,c1 , . . . towards c?  How does it compare to the secant and Newton– Raphson methods?

2.  The Cn  quadrature rule for the interval [≠1, 1] uses the points at which Tn ≠ 1 (t) = ±1 as its nodes

(here  Tn ≠ 1   is  the  Chebyshev  polynomial  of degree  n ≠ 1) .   The  C3   rule  is just  Simpson’s  rule

because T2 (t) = 2t2  ≠ 1 .

(a)   (i)  Find the nodes and weights for the C5  quadrature rule.

(ii)  Determine the first nonzero coeicient Sj  for the C5  rule.

(iii)  If the C5  rule and the five-point Newton– Cotes rule are applied on the same number of subintervals, what approximate relationship do you expect the two errors to satisfy?

(iv)  Suppose that the C5  rule has been applied on N subintervals, and that all of the function evaluations have been stored.  How many new function evaluations are required to apply the C9  rule on the same set of subintervals? Justify your answer.

(b)  Consider the approximation

⁄≠11 g(t)dt ¥ÿ(n) wq g(tq ).

where tq  and wq  are the nodes and weights for the Cn  quadrature rule. Assume that n is odd, and let k = (n ≠ 1)/2.

(i)  Set g(t) = T2j(t), and then make the substitution t = cos ◊ to evaluate the integral . Hence show that

 ≠ 2j  1 = wq cos A B,    j = 0, 1, . . . ,k .

(ii)  Consider the operator

Sk [cj ] =  ≠  +ÿ(k) cj .

j=0

It can be shown (proof: exercise for fun) that

Sk Ccos A BD = 0,    for    q = 2, . . . ,n ≠ 1.

Apply Sk  to the result of part (i) and hence show that

w1  = 4k21≠ 1 .

This result should agree with your calculation from part (a) .

(c)   (i) Write a Maple procedure that takes as its arguments a function f, real numbers a and b and a number of subintervals, N . As its result, it should return the approximate value of

I = ⁄ab f(x)dx,

calculated using the C5  rule.

(ii) Test your procedure using          I1  = ⁄03  dx

and N = 10. Calculate a second estimate using the five-point Newton– Cotes rule, also with N = 10. Verify that the ratio of the errors is in agreement with your theoretical prediction from part (a) .

(iii)  Repeat the calculations from part (ii) using a second integral chosen arbitrarily.  Do not use a polynomial for f(x), but make sure there is no possibility of division by zero etc.

The numerical methods package provides a five point Newton– Cotes procedure; you can also download the procedure code from Canvas (five_pt_NC.mw) .