1.  Consider the following matrix A and vector b

l −4 −4 −4 − 1 」 l −23 」

Find the unit lower triangular matrix L and upper triangular matrix U such that A = LU. Find the vector y such that Ly = b and find x such that Ux = y.  Verify that x is a solution to Ax = b.  Show all computational steps.

Solution. First let’s do Gaussian elimination by row operations.

4

''(l) 4 9(4) 1 ''(」)

1

−4l

Then we solve Ly = b with forward substitution.  Since each ljj  = 1 for j = 1, 2, 3, 4, we have

y1 = b1 = −23,

y2 = b2  − l21y1  = − 114 − 7 · ( −23) = 47,

y3 = b3  − l31y1 − l32y2 = −507 − 7 · ( −23) − ( −6) · 47 = −64,

y4  = b4  − l41y1 − l42y2 − l43y3  = −273 − 7 · ( −23) − 4 · 47 − 5 · ( −64) = 20. So y = [−23, 47, −64, 20]T .

We solve Ux = y with backward substitution.

x4 = y4 /u44 = 20/(−4) = −5,

x3 = (y3 − u34x4 )/u33 = ( −64 − 2 · ( −5))/9 = 6,

x2 = (y2 − u24x4 − u23x3 )/u22 = (47 − 2 · ( −5) − 7 · 6)/(− 15) = − 1,

x1 = (y1 − u14x4 − u13x3 − u12x2 )/u11 = ( −23 − ( − 1) · ( −5) − ( −4) · 6 − ( −4) · ( − 1))/(−4) = 2.

So x = [2, − 1, 6, −5]T .

Finally, we verify that Ax = b.

Ax = ' −28

[ 2(2)8(8)

−88   −45

5(1) = .

2. For the following matrix and vector

l —15(5)

A = ' 5 [

— 15     —5

—51    —51

—51   —224

— 12 —69

—69 '  ,    b = ' 410 ' ,

—37l           [ — 151l

find a unit lower triangular matrix L, a diagonal matrix D such that A = LDLT .  Find the vector y such that Ly = b, find w such that Dw = y, and find x such that LTx = w, Verify that x is a solution to Ax = b.  Show all computational steps.

Solution. First let’s do Gaussian elimination by row operations to obtain the LU decompo-

Since A is a symmetric matrix, we have U = DLT, where

So the above matrices L, D satisfy A = LDLT .

Then we solve Ly = b with forward substitution.  Since each ljj  = 1 for j = 1, 2, 3, 4, we have y1 = b1 = 25,

y2 = b2  — l21y1  = 3 — 3 · 25 = —72,

y3 = b3  — l31y1 — l32y2  = —410 — 1 · 25 — 6 · ( — 72) = —3,

y4  = b4 — l41y1 — l42y2 — l43y3  = — 151 — 0 · 25 — 2 · ( — 72) — ( — 1) · ( —3) = — 10. So y = [25, —72, —3, — 10]T . Then we solve Dw = y for w.

w1 = y1 /d11  = 25/( — 5) = —5,

w2 = y2 /d22  = — 72/( —6) = 12,

w3 = y3 /d33  = —3/( —3) = 1,

w4 = y4 /d44  = — 10/( — 10) = 1.

We get w = [ —5, 12, 1, 1]T . And we compute for the solution to LTx = w by

x4 = w4 = 1,

x3  = w3  — l43x4 = 1 — ( — 1) · 1 = 2,

x2  = w2  — l42x4  — l32x3  = 12 — 2 · 1 — 6 · 2 = —2,

x4  = w1  — l41x4  — l31x3  — l21x2 = —5 — 0 · 1 — 1 · 2 — 3 · ( — 2) = — 1. Then x = [ — 1, —2, 2, 1]T . Finally we verify that Ax = b with the above x.

l —15(5)

Ax = ' 5 [

— 15     —5

—51    —51

—51   —224

— 12 —69

—012 —2(1) 3(25)

69 '  '   2   '   =  '   410 '  .

—37l[ 1 l     [ — 151l

3. Let A be a symmetric positive definite matrix. Show that there exist a unit lower triangular matrix L and a diagonal matrix D such that A = LDLT, where D has positive diagonal entries.

Proof. Consider the Cholesky decomposition of A: A = RTR, where R is an upper triangle matrix with positive diagonal entries.  We can express R = D(ˆ)LT  with a diagonal matrix D and a unit lower triangle matrix L.  Let D :=D(ˆ)2.  The D is diagonal and each diagonal entry

is positive. We have

A = RTR = (D(ˆ)LT)T (D(ˆ)LT) = LDLT .

4. Let A =  [0 A22(A11 A12)] be a 2 × 2 block matrix, for submatrices A11 ∈ Rn1 ×n1 , A12 ∈ Rn1 ×n2 ,

A22   ∈ Rn2 ×n2 .   The  0 is  a zero matrix of dimension n2  × n1 .   Suppose  A11   =  L1U1   and A22   = L2U2  are LU factorizations, where L1, L2  are unit lower triangular and U1, U2  are upper triangular. Use L1, L2 , U1 , U2 , A12  to construct a LU factorization for A.

Solution. Denote the LU factorization of A in form of block matrices,

[0(A11)   A(A)2(1)2(2)] = [L(L)2(1)1(1)     L22(0)][0(U11)   U22(U12)],

石                                            >             石                                          >石                                          >

A                              L                        U

where L11, L22  are unit lower triangle matrices and U11, U22  are upper triangle matrices.  It implies that

A11 = L11U11,    A12  = L11U12 ,    0 = L21U11,    A22  = L21U12 + L22U22 .

Since the LU factorization of A2, A2  are unique, by comparing the terms of A1  = L1U1  and A22 = L2U2, we have

L11 = L1,    L21 = 0,    L22 = L2

U11 = U1,    U12  = L1(−)1 A12,    U22  = U2 .

So the LU factorization of A is

A = [0(L)1

5.  For p ≥ 1, define the function

L(0)2][0(U)1

L1 U2(−1 A)12] .

∥x∥p  :=^p |x1 |p + ··· + |xn|p.

Show that this is a norm function on Rn  and p ∥x∥p  = ∥x∥∞ .

Proof. First, we prove that ∥x∥p  is a norm function.

(a)  For every x ∈ Rn , ∥x∥p   =  ^p |x1 |p + ··· + |xp|p  ≥ |xi|  ≥ 0 for all i = 1,...,n.  When x = 0, it is clear that ∥x∥p  = 0.  Conversely, if ∥x∥p  = 0, then 0 = ∥x∥p  ≥ |xi|  ≥ 0 for all

i = i,...,n, so x = 0.

(b)  For every c ∈ R and every x ∈ Rn ,

∥cx∥p = ^p |cx1 |p + ··· + |cxn|p  = ^p |c|p · (|x1 |p + ··· + |xn|p ) = |c|∥x∥p.

(c)  For every x,y ∈ Rn, denote ˆ(x) = x/(∥x∥p+ ∥y∥p) and ˆ(y) = y/(∥x|p+ ∥y∥p), then

∥x + y∥p  ≤ ∥x∥p+ ∥y∥p  ⇔ ∥ˆ(x) + ˆ(y)∥ ≤ ∥ˆ(x)∥p+ ∥ˆ(y)∥p = 1.

Let λ := ∥ˆ(x)∥p, then ∥ˆ(y)∥p = 1 − λ, and 0 ≤ λ, 1 − λ ≤ 1. We have

"

∥ˆ(x) + ˆ(y)∥p(p) = "λ ·

=

≤

+ (1 − λ) · p(p)

' λ · + (1 − λ) · p

(λ + (1 − λ)p

≤ λ + (1 − λ) ≤ λ + (1 − λ) = 1.

The second last inequality holds due to the convexity of the function f(x) = xp , p ≥ 1, and the last inequality holds since ∥ˆ(x)∥p+ ∥ˆ(y)∥p  = 1.

Then we prove that limp→+∞∥x∥p  = ∥x∥∞. For every x ∈ Rn , we assume that |x1 | ≥ |xi| for all i = 1,...,n without loss of generality.  Then ∥x∥∞  = |x1 | and for all p ≥ 1,

√p 1 ≤ ∥∥x(x)∥ ∞ = 1p 1 + x(x)1(2) p + ··· + || x(x)1(n)|| p ≤ √p n.

Since √pn → 1 asp → ∞ , we get limp→∞∥x∥p  = ∥x∥∞ .

6.  Suppose A has the Cholesky factorization A  =  RTR,  for a nonsingular upper triangular matrix R. Show that ∥x∥A  := √xTAx gives a norm function.

Solution. With the Cholesky factorization A = RTR, we have

∥x∥A = √xTAx = √xTRTRx = 4 ∥Rx∥2(2) = ∥Rx∥2 ,

where ∥·∥2 is a norm function we proved in Question 5.  Then let us verify that  ∥x∥A = ∥Rx∥2 is also a norm function.

(a)  For every x ∈ Rn ,  ∥x∥A  = ∥Rx∥2   ≥ 0 and  ∥Rx∥2  = 0 if and only if Rx = 0.  Since R is nonsingular, Rx = 0 if and only if x = 0.  So  ∥x∥A  = 0 if and only if x = 0.

(b)  For every c ∈ R, x ∈ Rn , ∥cx∥A = ∥R(cx)∥2 = |c|∥Rx∥2 =  |c|∥x∥A .

(c)  For every x,y ∈ Rn, we have

∥x + y∥A = ∥R(x + y)∥2 = ∥Rx + Ry∥2 ≤ ∥Rx∥2  + ∥Ry∥2 = ∥x∥A + ∥y∥A .

7. For a square matrix A = (aij)1≤i,j≤n, define the function

∥A∥max  :=  max  |aij| .

Show that ∥A∥maxis a norm function in the matrix space Rn×n , but