COMPUTATIONAL MATHEMATICS
Saturday, 28 May 2016: 9.30am - 11.30am
This paper is divided into TWO sections as follows:
Section A: Six short questions, each marked out of 10.
Candidates may attempt all SIX questions but are advised
that they cannot obtain a total of more than FORTY marks
on this section.
Section B: Three longer questions each marked out of 30.
Candidates may not attempt more than TWO of the THREE
questions in this section.
Candidates are advised to show their working on their
scripts. Marks might then be allocated for use of a correct
method, even if the numerical or algebraic result is incorrect.
Calculators: Approved calculators are permitted.
Turn over
MA584/16 2
SECTION A
These questions will each be marked out of 10. Candidates
may attempt all SIX questions but are advised that they
cannot obtain a total of more than FORTY MARKS on this
section.
1. We consider the following integral: Z
1
1
e x2=2dx;
and we want to approximate it using the composite trapezoidal rule, with n subintervals and
step h = (b a)=n. Bearing in mind that the error for a twice di erentiable function on [a;b]
is given by
jE[f]j= b a12 h2jf00( )j;
with 2 (a;b), determine the step h needed to compute the integral with an error smaller
than 10 4.
[10 marks]
2. We consider the following two matrices:
A =
0
B@ 0 1=2 01=2 0 1=2
0 1=2 0
1
CA; B =
0
B@0 1 01 0 1
0 1 0
1
CA:
Determine if the methods of Jacobi and Gauss-Seidel converge with these two matrices as the
iteration matrix of the method. Please justify your answer.
[10 marks]
3.
(a) Compute the xed point(s) of the iteration
xn+1 = xn2 + 52x
n
:
[4 marks]
(b) Use the general result for convergence of a xed point iteration to determine if there
is convergence for a given initial value x0 in a suitable neighbourhood of each xed
point. If there is convergence, what is the expected order?
[6 marks]
4.
(a) De ne the Lagrange interpolating polynomial and the associated interpolation error
for a given function f(x) that is known at a set of points x0;:::;xn in an interval
[a;b].
3 MA584/16
[5 marks]
(b) Construct the Lagrange interpolating polynomial for the function
f(x) = 1p1 + 3x2
with nodes x0 = 1, x1 = 0 and x2 = 1. Use this polynomial to get an approximate
value for the number 2=p7.
[5 marks]
5.
(a) Write out the classical Simpson’s rule and apply it to the following integral:
Z =2
0
cos2xdx
[5 marks]
(b) Compare the previous result with the exact value of the integral. What are the
absolute and relative errors?
[5 marks]
6.
(a) Compute the LU decomposition of the following matrix:
A =
0
B@ 2 4 1 2 5 5
4 7 9
1
CA:
[6 marks]
(b) Use the previous result to solve the system Ax = b, with
b =
0
B@ 1 1
3
1
CA:
[4 marks]
Turn over
MA584/16 4
SECTION B
These questions will each be marked out of 30. Candidates
may not attempt more than TWO of the THREE questions.
7. In this problem, we consider the following function:
f(x) = 4x+ex;
whose plot is shown in Figure 1.
-1 -0.50 0.51 1.52 2.53-2
02
46
810
Figure 1: Plot of the function f(x) = 4x+ex.
(a) Give suitable initial intervals for each root for starting the bisection algorithm. Please
justify your decisions.
[5 marks]
(b) Given an initial interval [a;b] that contains one root of f(x), how many iterations
(approximately) would you expect to need in the bisection method in order to ap-
proximate that root with an absolute error smaller than 10 6?
[5 marks]
(c) Newton’s method has been implemented for this example, and the next table shows
some results and the absolute error, measured as jxn+1 xnj at each iteration.
Value (Newton) Error Value (Newton) Error
x0 = 1 1:0000e+ 00 x0 = 3 5:0266e 01
x1 = 0 3:3333e 01 x1 = 2:4973e+ 00 2:6512e 01
x2 = 3:3333e 01 2:3913e 02 x2 = 2:2322e+ 00 7:3611e 02
x3 = 3:5725e 01 1:5647e 04 x3 = 2:1586e+ 00 5:2894e 03
x4 = 3:5740e 01 6:8081e 09 x4 = 2:1533e+ 00 2:6210e 05
x5 = 3:5740e 01 0 x5 = 2:1533e+ 00 6:4134e 10
x6 = 3:5740e 01 0 x6 = 2:1533e+ 00 4:4409e 16
5 MA584/16
Taking into account these results, can you determine (in each case) if the method is
converging to the roots of f(x), and if so with what order?
[5 marks]
(d) Check that the solutions of f(x) = 0 coincide with the solutions of x = g1(x) and of
x = g2(x), with
g1(x) = e
x
4 ; g2(x) = log(4x):
[5 marks]
(e) Using the general result of convergence for the xed point method, and with a starting
point close to each one of the roots, would you use g1(x) and/or g2(x) in a xed point
iteration? Please justify your answer.
[10 marks]
8. In this problem, we consider a Gaussian quadrature rule with two nodes and two weights:
Z 1
1
f(x)dx w1f(x1) +w2f(x2):
(a) What is the maximum degree of exactness of this rule?
[5 marks]
(b) Imposing this maximum degree of exactness, compute the values of xi and wi, for
i = 1;2.
[10 marks]
(c) The error term for this Gaussian quadrature formula can be written as follows:
jE2j 1135 max
x2[ 1;1]
jf(iv)(x)j;
where f(iv)(x) is the fourth derivative of f(x). Using f(x) = log(2 +x), compute the
numerical value of the integral using the quadrature rule. Knowing that the exact
value of the integral is 3 log 3 2, is the absolute error consistent with the previous
bound?
[10 marks]
(d) Consider now a similar Gaussian quadrature but on the interval [ 2;2]:
Z 2
2
f(t)dt d1f(t1) +d2f(t2)
Without solving the system again, can you give these new nodes and weights in terms
of the original ones?
[5 marks]
Turn over
MA584/16 6
9. We consider the matrix
A =
0
BB
B@
2 1 0 0
1 2 1 0
0 1 2 1
0 0 1 2
1
CC
CA:
(a) Write the iteration matrices for the Jacobi and Gauss-Seidel methods for A.
[10 marks]
(b) Compute the spectral radius of the iteration matrix for the Jacobi method.
[10 marks]
(c) Can you use the previous result to estimate the error:
kx x(k)k2
kx x(0)k2;
in the k-th step of the Jacobi iteration, for some initial value x(0)? What is the
approximate value of this ratio for k = 2;4;8?
[10 marks