Solutions to Problem Sheet 7

MATH20602
Numerical Analysis 1
March xx, 2014
Solutions to Problem Sheet 7
Solution (7.1)
By definition of an operator norm,
kAxk
.
x6=0 kxk
kAk = sup
In particular, for any x 6= 0, kAxk ≤ kAk kxk. Now
kABxk
kAk kBxk
kBxk
≤ sup
= kAk sup
= kAk kBk .
kxk
kxk
x6=0
x6=0
x6=0 kxk
kABk = sup
Because of the triangle inequality for the vector norm,
k(A + B)xk = k(Ax) + (Bx)k ≤ kAxk + kBxk .
Now,
kA + Bk = sup
x6=0
kAxk + kBxk
k(A + B)xk
≤ sup
kxk
kxk
x6=0
kAxk
kBxk
+ sup
= kAk + kBk .
x
x6=0
x6=0 kxk
≤ sup
Solution (7.2)
18.
kAk1 = 18, kAk∞ = 24. kBk1 = kAk∞ = 24. kBk∞ = kAk1 =
P
Solution (7.3) Let f (A) = supj i |aij |, where aij is row i column j entry of A.
We show that kAk1 = f (A).
P
Let ej = (0, . . . , 0, 1, . . . , 0) (1 in jth position). Note that kAej k1 = i |aij | (the
1-norm of the j-th column of A).
Step 1 Show that kAk
P1 ≤ f (A).
Consider a general x =
xj ej with kxk1 = 1.
X
kAxk1 ≤
kAxj ej k1
(by triangle inequality)
j
≤
X
|xj | kAej k1
(by linearity of norm)
j
≤ sup kAej k1
j
= sup
j
X
|xj | = sup kAej k1
j
j
X
(as kxk1 = 1)
|aij | = f (A).
i
Step 2 Show that kAk1 ≥ f (A).
To do this, it is sufficient to find an xPsuch that kAxk1 / kxk1 ≥ f (A). Let x = ej
where j maximises the column sum i |aij |. Then kxk1 = 1, Ax is the jth column
of A, and kAxk1 = f (A). Hence kAk1 ≥ f (A).
Together the two arguments above show kAk1 = f (A).
In the example matrices, kAk1 equals 6 and 12.
1
MATH20602
Solution (7.4)
Numerical Analysis 1
March xx, 2014
First of all, note that since D and L + D are non-singular, we have
det(D) 6= 0,
det(L + D) 6= 0.
For the eigenvalues of the Jacobi matrix TJ = −D −1 (L + D) we get, using the
multiplicativity of the determinant,
det(λ1 − TJ ) = 0 ⇔ det(D) det(λ1 − TJ ) = 0
⇔ det(D(λ1 − TJ )) = 0
⇔ det(λD + D −1 D(L + U )) = 0
⇔ det(λD + L + U ) = 0.
For the Gauss-Seidel matrix TGS = −(L + D)−1 U we get
det(λ1 − TGS ) = 0 ⇔ det(L + D) det(λ1 − TGS ) = 0
⇔ det((L + D)(λ1 − TGS )) = 0
⇔ det(λ(L + D) + (L + D)−1 (L + D)U ) = 0
⇔ det(λ(L + D) + U ) = 0.
To compute the 2-norm of the Gauss-Seidel matrix TGS , we use the spectral radius
characterisation
>
kTGS k = ρ(TGS
TGS )1/2 .
The matrix A is separated as

2
L + D = −1
0
0
2
−1

0
0 ,
2
and we need to compute the determinant of

2λ −1
−λ 2λ
0 −λ

0
U = 0
0
−1
0
0

0
−1 ,
2

0
−1 .
2λ
Expanding along the first row gives
det(λ(D + L) + U ) = 2λ(4λ2 − λ) + (−2λ2 ) = 4λ2 (2λ − 1) = 0.
The non-zero eigenvalue is thus λ = 1/2 and ρ(TGS ) = 1/2.
2

Download Report