(1)    a) What is computational complexity? How can we quantify it?

b) What is computational accuracy? How can we quantify it? [2 marks]

(2)    Describe Horner’s Method, and why it is used. Illustrate its use in evaluating the polynomial p(x) = −2x3 + x2 + ^2x

at x =  . [3 marks]

(3)    Evaluate the expression

x2 − 1

for x = 1.001 by computing every step to four significant figures, and determine the relative error of the solution. Rewrite the above equation in order to avoid catastrophic cancellation errors, and compute the improved approximation with accuracy of four significant figures. [4 marks]

(4)    Let Li (x), 0 < i < n, denote the Lagrange basis functions associated to interpolation nodes x0 , . . . ,xn , with xi  = i for i = 0, . . . ,n. Show that for all x 2 R,

L1 (x)+4L2 (x)+9L3 (x)+ ··· + n2 Ln (x) = x2 . [3 marks]

(5)    Compute the polynomial p(x) that interpolates the data

(xi ,yi ) = (0, 7), (1, 7), (2, 5), (3, 1)

by use of a divided difference table. What is the degree of the resulting polynomial? Suppose that one of the four points is removed, leading to an updated interpolant p(x). What would be the value of p(4)? [4 marks]

(6)    Consider the function f(x) = exp(2x) on the interval [0, 1]. State the formula for the com- posite trapezium rule for approximating the integral R01 exp(2x) dx with n intervals.

Find, with justification, a number of intervals n such that the integration error of the method will be less than 10 −2 , making sure to define all terms used. [4 marks]