1. Note:  Please give brief answers to these questions.   Long explanations are not necessary.

(a)  Give the general definition of the relative forward error, relative backward error and relative condition number.

[Solution, seen, 7 marks] Let f : V - W be a function mapping between two vector spaces V and W . Let f˜ be an approximate evaluation of f , f (x) = y and f˜(x) = y˜ .

The relative forward error E is defined as

|y - y˜|

|y|   .

The relative backward error η(y˜) is defined as

η(y˜) = min {∈ : f (x + ∆x) = y˜, |∆x| ≤ ∈|x|} The relative condition number κ(x) is defined as

κ =δ(l) lδ(s)xl(u)δ  ╱ / 、

(b) Define the machine precision ∈mach  and explain what it means.

[Solution,  seen,  6  marks] The machine precision ∈ is defined as ∈mach   = b1-p , where b is the base of the number system, and p is the precision in the mantissa (p = 53 in double precision). ∈mach  is the maximum relative error of rounding a number to the nearest floating point number, hence Ix - fl(x)I ≤ I∈mach IIxI, where x e A and fl(x) is its nearest floating point number.

(c)  Compute the relative condition number of f (x) = ′x at x = 2.

[Solution, seen similar, 6 marks] For a differentiable function the relative condition κ is given by

If/ (x)I . IxI

If (x)I    .

In this case we obtain

κ(2) =      2      = 1

(d)  State the fundamental axiom of floating point arithmetic.

[Solution, seen 6 marks] Define xoy = fl(x .y), where . is one of +, -, × , ÷ . Then for all x, y e r (the set of floating point numbers) there exists ∈ with I∈I ≤ ∈mach  such that

x o y = (x . y)(1 + ∈).

2.   (a) Let Ax = b and  = b with  = A + δA, A e An ×n . Show that to first order

|x - |             |δA|

|x|                 |A| ,

where κ(A) = |A| . |A|-1  is the matrix condition number of A.

[Solution, seen, 5 marks] With δx =  - x we have

(A + δA)(x + δx) = b,

which gives

Aδx = -δAx.

Multiplying with A-1  and taking norms we obtain

|δx| ≤ |A-1 ||δA||x| = κ(A) |x|,

from which we obtain the wanted result through division by |x|.

(b) Let A e An ×n be nonsingular, and b, c e An , and α e A. Assuming that the LU decomposition of A without pivoting is known show that the LU decomposition

of

 = ┌ATc   α(b)┐

can be computed in O(n2 ) operations. Under what condition on b, c, α does a nonsingular LU decomposition of  exist?

[Solution, seen, 5 marks] We write the unknown LU decomposition as

┌ATc   α(b)┐ = ┌eT(L)     1┐ ┌ U   δ(u)┐ ,

where e, u e An  and δ e A.

We can compute the unknown entries eT , u and δ as u = L-1 b, eT  = cT U-1 , δ = α -eT u = α - c  AT-1 b. These operations only involve forward substitutions with L and UT  and can therefore be efficiently performed in O(n2 ) operations. A nonsingular LU decomposition exists if δ  0, hence α  cT A-1 b.  [not seen, 8 marks]

(c)  Given a nonsingular matrix A e An ×n .

(i) Proof the Sherman-Morrison formula

(A + uvT )-1  = A-1 - 

if 1 + vT A-1u  0.

[Solution, unseen, 10 marks]

We have

(A + uvT ) ┌A-1 - ┐ = I -  + uvT A-1 - uvT   = I - ┌  - uvT A-1 ┐ = I - u ┌  - 1┐ vT A-1  =

I

Similarly, we show that

┌A-1 - ┐ (A + uvT ) =

I - A-1u ┌  - 1┐ vT  =

I

Hence, the formula holds.

(ii) Assume the LU decomposition (without pivoting) of A is known. Describe an algorithm that solves the linear system of equations Bx = c with B = A + uvT , 1 + u  AT-1v  0, as efficiently as possible in O(n2 ) operations. It is not necessary to use Python in your answer.

[Solution  unseen,  5  marks] An LU decomposition of A in the form A = LU is known. We can now solve the system Bx = c in the following steps:

A.  Solve Ax1  = c by forward and backward substitution.  0(n2 ) opera- tions.

B.  Solve A = u by forward and backward substitution.  0(n2 ) opera- tions.

C.  Compute x2  = 之 . 0(n) operations.

D. x = x1 - x2 . 0(n) operations.

3. Let A e Am ×n  with m > n and rank(A) = n and b e Am . We define the following least-squares problem:

Find  e An , such that

|A - b|2  = min |Ax - b|2 .                                      (1)

xeA我

(a)   (i)  Show that  = (AT A)-1 AT b.

[Solution, seen, 5 marks]

Let  =  + ∈. We have

|A - b|2(2)  = |A - b|2(2) + 2∈T  YAT A - AT b, + ∈  A  A∈.TT

It follows that a necessary condition for a stationary point at ∈ = 0 is given as AT A - AT b = 0. From the condition that rank(A) = n it follows that ∈  A  A∈ >TT 0 for all ∈  0. It hence follows that the necessary condition is also sufficient for a minimizer, completing the proof.

(ii)  Starting from the Singular Value Decomposition of A show that the con-

dition number of AT A is given by κ(AT A) = ( σ(σ)我(之))2 .

[Solution, seen, 5 marks] Let A = UΣVT  be the SVD of A. Then the SVD of AT A is given as AT A = V ΣT ΣVT .  Hence, the singular values of AT A are the squares of the singular values of A and the condition number

is therefore κ(AT A) = ( σ(σ)我(之))2 .

(iii) Let A = QR with Q e Am ×n , R e An ×n . Show that  = R = QT b. What is the condition number of this linear system of equations?  Justify your answer.

[Solution, seen, 5 marks] We substitute A = QR into AT A = AT b to obtain RT R = RT QT b or equivalently R = QT b since R is nonsingular as follows from the rank condition. The singular values of R are the same as the singular values of A since σj (A)2  = σj (AT A) = σj (RT R) = σ(R)2 for j = 1, . . . , n. Hence, κ(R) = κ(A).

(b) Let the data points xj with associated values yj be given for j = 0, . . . , n-1. We want to find a linear relationship, such that αxj +β s yj  for all j. Formulate an associated least-squares problem and explicitly compute α and β in dependence of the values xj  and yj .

[Solution, unseen, 10 marks] We can write this problem in the form of the

least-squares problem (1) with A =  ┐T , b =  Yy0     . . .   yn-1,T

and x = Yβ   α,T . The normal equation is hence given as

┐ ┌  ┐α(β) = ┌

We can directly invert this system to obtain

┐

┌  ┐α(β) =  ┌ -

j xj

j xj

-  nj xj ┐

┐

CONTINUED

giving

n    j xj yj  -    j xj       j yj

n    j xj(2) - ╱   j xj、2      ,

β =       j xj(2)       j yj  -    j xj       j xj yj

n    j xj(2) - ╱   j xj、2.

4.   (a) Prove that every square matrix A e cn ×n  has a Schur decomposition.             [Solution, seen, 7 marks] We prove the Schur decomposition by induction on the dimension. For n = 1 the statement is trivial. Now consider A e cn ×n . Let λ be an eigenvalue with associated eigenvector x. Assume that |x|2  = 1. Now define the unitary matrix Q e cn ×n  by

Q = Yx   Qˆ, ,

where Qˆ is a unitary basis of the orthogonal complement to the space spanned by x. We now have

QH AQ = ┌ 0(λ)   HwB┐ .

Let B  = P PT   be the Schur decomposition of the matrix B  e cn-1×n-1 .

Then

A = Q ┌ 1   P┐ ┌ 0(λ)   Hw┐ ┌ 1   PH ┐ QH

is a Schur decomposition of A.

(b) Let A e cn ×n . For z e c the following statements are given.

(i) z is an eigenvalue of A + δA for some δA with |δA|2  ≤ ∈ .               (ii) There exists a vector u e cm  with |(A - zI)u|2  ≤ ∈ and |u|2  = 1.

(iii) σn (zI - A) ≤ ∈, where σn (zI - A) is the smallest singular value of zI - A. (iv)  |(zI - A)-1 |2  > ∈ -1 .

Prove that these statements are equivalent by showing that (i) - (ii) - (iii) - (iv) - (i).

[Solution, seen, 8 marks]

(i) - (ii): From (A + δA)u = zu we have (A - zI)u = -δAu for an eigenvector u with |u|2  = 1. Taking norms we obtain |(A - zI)u|2  ≤ ∈ .

(ii) - (iii): This follows from

|(zI - A)|2          |(A - zI)u|2

(iii) - (iv): We have |(zI - A)-1 |2  = [σn (zI - A)]-1  > ∈ -1 .

(iv) - (i):  From (iii) it follows that there exist unit norm vectors u, and v such that (zI - A)-1u = -1v for some  ≤ ∈. It follows that (zI - A)v = u. Rearranging gives (A + uvH )v = zv and hence z is an eigenvalue of (A + δA) with |δA|2  =  ≤ ∈ .

(c) Let A e cn ×n  be diagonalizable, that is A = VΛV-1  for some diagonal matrix Λ and nonsingular matrix V .  Let δA e cn ×n  be an arbitrary perturbation matrix.  Based on the equivalence of the statements (i) and (iv) above prove

that for every eigenvalue z of A +δA it holds that Iz - λI ≤ |V |2 |V-1 |2 |δA|2 for some eigenvalue λ of A.

[Solution, unseen, 10 marks] If z is an eigenvalue of A +δA with |δA|2  = ∈ then |(zI - A)-1 |2  > ∈ -1 . Using A = VΛV-1  we have

∈ -1  ≤ |(zI - A)-1 |2  ≤ |V |2 |V-1 |2 |(zI - Λ)-1 |2  = |V |2 |V-1 |2 Iz - λI-1     for some eigenvalue λ of A, The statement follows by multiplying with ∈Iz - λI.

5.   (a) Let f be a function defined in the interval [a, b].  Let xk  e [a, b], k = 0, . . . , n with xi   xj  for all i  j. Write down the Lagrange interpolation polynomial p of degree n that interpolates f in the points xk .

[Solution, 3 marks, seen] We define

Lk (x) =      ←      (x - xj )

j=0,...,n,jk

Then

p(x) =           f (xk )Lk (x).

k=0,...,n

(b) Let xi , i = 0, . . . , N + 1 be distinct interpolation points and yi  be associated function values.   Let q be the interpolation polynomial associated with the points xj  j = 0, . . . , N and r the interpolation polynomial associated with the points xe , e = 1, . . . , N + 1. Show that

(x - x0 )r(x) - (x - xN+1)q(x)

xN+1 - x0

is the Lagrange interpolation polynomial for the points xi , i = 0, . . . , N + 1.   [Solution, 7 marks, seen] For xj , j = 1, . . . , N we have r(xj ) = q(xj ) and hence, p(xj ) = yj . Furthermore, p(x0 ) = q(x0 ) = y0 , and p(xN+1) = r(xN+1) = yN+1.   Hence, p is the unique interpolation polynomial at all interpolation points xj , j = 0, . . . , N + 1.

(c) Let T be the unit triangle with vertices (0, 0), (1, 0), (1, 1). We want to evaluate

the integral

←                       ← 1 ← x

numerically. Given a quadrature rule of the form

n

In (f) :=       f (ξj )ωj

j=0

to approximate a function f in the interval [0, 1], show that

←T g(x, y)dxdy s i,j g(ξi , ξj ξi )ξi ωi ωj .

Hint: Use a transformation of the form y = xµ to rewrite the integral over T as a double integral, where both integrals run from 0 to 1 and repeatedly apply the quadrature rule for a single integral.

[Solution, unseen, 5 marks] We have

←T g(x, y)dydx = ←0 1 ←0 x g(x, y)dydx = ←0 1 ←0 1 g(x, µx)xC(d)O(µd)N(x)T(.)INUED