1.  In this question, we assume that your calculator can only perform the four elementary

arithmetic operations, + , − ,  × and ÷ .  In particular, your calculator cannot compute

We want to calculate an approximation of cos(π/5),  using  polynomial  interpolation through the three points x1  = π/6, x2  = π/4 and x3  = π/3.

(a)  Calculate the three Lagrange polynomials, defined such that Lk (xi ) = δik  where δik  is the Kronecker delta. Write your results in the form

Lk (x) = ak  ( )2  + bk   + ck  for k ∈ {1, 2, 3},

where ak , bk  and ck  are integers.                                                         [6 marks]

(b)  Calculate the polynomial P (x) that interpolates the function f (x) = cos x at x1 , x2  and x3 . Write the result in the form

P (x) = α ( )2  + β + γ,                                        (1)

where the coefficients α , β and γ depend explicitly on ^2 and ^3, which would have to be estimated numerically in the next part of the question.      [2 marks]

(c)  Write down a Newton’s step to approximate any radical number of the form ^k η ,

where k  is an integer and η  a positive real number .  Use this algorithm to find an

approximation to ^2  accurate to within  10 −4 .  Then, calculate an approximation

to ^3, with the same level of accuracy, by means of another root-finding method

of your choice .  (In your estimation of the error, recall that ^2 and ^3 are assumed

unknown.)                                                                                                    [7 marks]

(d)  Find an approximation to cos(π/5) by evaluating P (π/5) using equation (1) and your numerical estimations of ^2 and ^3 from part (1.c).                 [2 marks]

(e)  Bound the error  in your  approximation of cos(π/5)  using the error formula for

Lagrange interpolation and π ≈ 3. 14159 .                                                 [3 marks]

2.    (a) Give the definition of the double root of a function and sketch the graph of a function with two roots: a simple root, marked , and a double root, marked x∗ .

[3 marks]

(b)  Find an unseen example of a function, f , with a double root, x∗ . The function f should not be a polynomial but could be any rational and transcendental function. Perform enough iterations of Newton’s algorithm, written as a fixed-point iteration xn+1  = g(xn ), to infer the order and rate of convergence of the sequence of data produced. Prove this assertion by writing a Taylor series for g about x∗ , in powers

of (xn  − x∗ ) .                                                                                     [7 marks]

f (x)

h(x) =

(2)

based on your choice of f  in part 2.b.  Perform enough iterations of Newton’s algorithm for h(x) to infer the order of convergence of the improved method. Prove that the order and rate of convergence of the improved method are consistent with the values suggested by your numerical data.                                  [10 marks]

3.  The coefficients of the polynomial P (x) = a0 +a1 x +a2 x2 +a3 x3  interpolating the four distinct points (xi , fi ), for i ∈ {1, 2, 3, 4}, satisfy the linear system

Vp = f,                                                             (3)

where pT  = (a0 , a1 , a2 , a3 ), fT  = (f1 , f2 , f3 , f4 ) and V is the Vandermonde matrix.

Keep all rational numbers in your calculations as fractions, not as decimal numbers.

(a)  Showing all your working throughout, find the LU-factorisation of the matrix

\1(1)   1   4(1)    1

  1      1      1      1    

(1     α     α     α )

where α is an arbitrary number.                                                          [6 marks]

(b) Write down the Vandermonde matrix, V , for the four points x1   = − 1, x2   = 2 ,

(c)  Using the results from part (3.b), solve equation (3) for p, where the components of the right-hand side vector f are the last four digits of your student ID number. Then write the  polynomial  interpolating the four data  points  (xi , fi ),  for i  ∈ {1, 2, 3, 4}. (No marks will be given for using Lagrange interpolation.)     [5 marks]

(d)  Using the results from part (3.b), calculate the Lagrange polynomials L4 (x) and L3 (x) defined such that Lk (xi ) = δik  where δik  is the Kronecker delta. (No marks will be given for using the formula for Lagrange polynomials.)

The last two Lagrange polynomials are

L1 (x) = −  +  −     and   L2 (x) = −  +  .                   (4)

Without computing the inverse of the Vandermonde matrix V , explain how to find V −1   using of the coefficients of the Lagrange polynomials and write down the result.                                                                                                  [6 marks]

4.    (a)  Consider the n-point Newton-Cote quadrature rule

 f(x)dx ≈  wi f(xi ).

(5)

Give the general form function, show that

(b) The quadrature rule

of the expected error term.   By considering a constant

wi  = h.

[3 marks]

h(h) f(x)dx = w1 f(x1 ) + w2 f(x2 ) + E

(6)

can be made exact for all cubic polynomials, by using a suitable choice of weights and points, respectively wi  and xi , i ∈ {1, 2}.

• Write down four equations satisfied by w1 , w2 , x1  and x2 .

•  Combine two of these equations to show that x2   =  −x1   and  hence that

•  Calculate the weights and then the value of the quadrature points.

•  Find the error term and write the quadrature rule (6). What class of quadra- ture rules does it belong to?                                                          [9 marks]

(c)  Consider the polynomial P (x) = a0  + a1 x + a2 x2  + a3 x3 , where the coefficients ai , i ∈ {0, 1, 2, 3} are the last four digits of your student ID number.  Compute the definite integral ∫1 P (x)dx and its approximation using the quadrature rule obtained in part (4.b). Discuss your results.                                        [3 marks]

(d) We want to find a three-point formula,

f(x)dx = w1 f(x1 ) + w2 f(x2 ) + w3 f(x3 ) + E,    x1  < x2  < x3 ,      (7)

−h

h(h) f(x)dx = h(h) f(−x)dx.

(8)

The quadrature rule should also possess such a property of integrals.  Using this

argument of symmetry, show that x2  = 0 and find relations between x1  and x3 ; and between w1  and w3 .  Then, calculate the weights and points that make this rule exact for polynomials of the highest degree possible. Find the error term and write the quadrature formula (7).                                                        [5 marks]