Question 1 (Floating point arithmetic, 10 marks). True or false? +1/-1

1. Let (•)3  denote base 3 representation. It holds that

(120)3 + (111)3 = (1001)3 .

2. Let (•)2  denote binary representation. It holds that 

(1000)2  × (0.101)2 = (101.01)2 .

3. In Julia, Float64(.25)  ==  Float32(.25) evaluates to true.

4.  The spacing (in absolute value) between successive double-precision (Float64) floating point numbers is constant.

5.  The machine epsilon is the smallest strictly positive number that can be represented in a floating point format.

6. Let F64  ⊂ R denote the set of double-precision floating point numbers.  If x ∈ F64 , then x admits a finite decimal representation.

7. Let x be a real number. If x ∈ F64, then 2x ∈ F64 .

8.  The following equality holds

(0.101)2 = 7

9. In Julia, 256.0  +  2.0*eps(Float64)  ==  256.0 evaluates to true.

10.  The set F64  of double-precision floating point numbers contains twice as many real numbers as the set F32  of single-precision floating point numbers.

11. Let x and y be two numbers in F64 .   The result of the machine addition x  y  is sometimes exact and sometimes not, depending on the values of x and y .

Question 2 (Iterative method for linear systems, 10 marks). Assume that A ∈ Rn×n  is a nonsingular matrix and that b ∈ Rn . We wish to solve the linear system

Ax = b                                                                (1)

using an iterative method where each iteration is of the form

Mxk+1 = Nxk + b.

Here A = M − N is a splitting of A such that M is nonsingular, and xk  ∈ Rn denotes the k-th iterate of the numerical scheme.

1.  (3 marks) Let ek  := xk − x∗, where x∗ is the exact solution to (1). Prove that ek+1 = M−1 Nek .

2.  (3 marks) Let L = ∥M−1 N∥∞ . Prove that

∀k ∈ N,        ∥ek∥∞ ≤ Lk ∥e0 ∥∞ .

3.  (1 mark) Is the condition ∥M−1 N∥∞ < 1 necessary for convergence when x0  x∗?

4.  (3 marks) Assume that A is strictly row diagonally dominant, in the sense that

n

∀i ∈ {1, . . . ,n},        |aii| >   对  |aij|.

j=1,ji

Show that, in this case, the inequality  ∥M−1 N∥∞ <  1 holds for the Jacobi method, i.e. when M contains just the diagonal of A.  You may take for granted the following expression for the ∞-norm of a matrix X ∈ Rn×n :

n

∥X∥∞ = 1 对 |xij|.

j=1

5.  (Bonus +1) Write down a few iterations of the Jacobi method when

A = ( 0(1)

Is the method convergent?

1(2)) ,

b ( )1(1) ,

x0 = ( )0(0) .

Question 3  (Nonlinear equations, 10 marks). Assume that x* ∈ Rn  is a solution to the equation

F(x) = x,

where F : Rn  → Rn  is a smooth nonlinear function.  We consider the following fixed-point iterative method for approximating x*:

xk+1 = F(xk).                                                          (2)

1.  (8 marks) Assume in this part that F satisfies the local Lipschitz condition

Ax ∈ B6(x*),        ∥F(x) − F(x*)∥ ≤ L∥x − x*∥,                          (3)

with 0 ≤ L < 1 and 6 > 0.  Here B6(x*) denotes the open ball of radius 6 centered at x*. Show that the following statements hold:

•  (2 marks) There is no fixed point of F in B6(x*) other than x*.

•  (2 marks) If x0  ∈ B6(x*), then all the iterates (xk)k∈N  belong to B6(x*).

•  (3 marks) If x0  ∈ B6(x*), then the sequence (xk)k∈N  converges to x* and Ak ∈ N,        ∥xk− x*∥ ≤ Lk ∥x0 − x*∥ .

2.  (3 marks) Explain with an example how the iterative scheme (2) can be employed for solving a nonlinear equation of the form

f(x) = 0.

3.  (Bonus +1) Let JF : Rn → Rn×n  denote the Jacobian matrix of F . Show that if

Ax ∈ B6(x*),        ∥JF(x)∥ ≤ L,

then the local Lipschitz condition (3) is satisfied.

Question 4  (Error estimate for eigenvalue problem, 10 marks). Let  ∥.∥ denote the Eu- clidean norm, and assume that A ∈ Rn×n  is symmetric and nonsingular.

1.  (5 marks) Describe with words and pseudocode a simple numerical method for calcu- lating the eigenvalue of A of smallest modulus, as well as the corresponding eigenvector.

2.  (1 mark) Let M ∈ Rn×n  denote a nonsingular symmetric matrix. Prove that

Ax ∈ Rn ,        ∥Mx∥ ≥ ∥M−1∥−1∥x∥ .                                    (4)

Let λmin(M) denote the eigenvalue of M of smallest modulus. Deduce from (4) that

Ax ∈ Rn ,        ∥Mx∥ ≥ |λmin(M)|∥x∥ .                                   (5)

3.  (4 marks) Assume that  ∈ R and  ∈ Rn  are such that

∥A − ∥ = e > 0,        ∥∥ = 1.                                       (6)

Using (5), prove that there exists an eigenvalue λ of A such that

|λ − | ≤ e.

4.  (Bonus +1) Show that, in the more general case where A = VDV−1  is diagonalizable but not necessarily Hermitian, equation (6) implies the existence of an eigenvalue λ

of A with

| − λ| ≤ ∥V∥∥V−1∥e.

Hint: Introduce r = A −  and rewrite

∥∥ = ∥(A − I)−1r∥ = ∥V(D − I)−1V−1r∥ .

Question 5 (Interpolation error, 10 marks). Let u denote the function

u: [0, 2π] → R;

x '→ cos(x).

Let pn: [0, 2π] → R denote the interpolating polynomial of u through at the nodes

2πi

1.  (3 marks) Using a method of your choice, calculate pn  for n = 2.

2.  (6 marks) Let n ∈ N>0  and en(x) := u(x) − pn(x). Prove that

Ax ∈ [0, 2π],        |en(x)| ≤  |ω(x)| 

where we introduced

ωn(x) :=u(x − xi).

i=0

Hint: You may find it useful to introduce the function

g(t) = en(t)ωn(x) − en(x)ωn(t).

3.  (1 mark) Does the maximum absolute error

En  :=   sup  |en(x)|

北 ∈[0,2π]

tend to zero in the limit as n → ∞?

(Bonus +1) Using the Gregory–Newton formula, find a closed expression for the sum

n

S(n) =工 k2 .

k=1