Homework 6 Solutions

Igor Yanovsky (Math 151B TA)

Section 11.4, Problem 1: For the boundary-value problem

y 00 = −(y 0 )2 − y + log x,
1 ≤ x ≤ 2, (1)
y(1) = 0, y(2) = log 2,
write the nonlinear system and formulas for Newton’s method.

Solution: We divide [1, 2] into N + 1 subintervals whose endpoints are xi = 1 + ih, for
i = 0, 1, . . . , N + 1, and consider the discretization of the boundary-value problem in (1):

y 00 (xi ) = −(y(xi )0 )2 − y(xi ) + log xi . (2)

Replacing y 00 (xi ) and y 0 (xi ) by appropriate centered difference formulas, equation (2)
becomes:
µ ¶2
y(xi+1 ) − 2y(xi ) + y(xi−1 ) h2 (4) y(xi+1 ) − y(xi−1 ) h2 000
− y (ξi ) = − − y (ηi )
h2 12 2h 6
−y(xi ) + log xi ,

for some ξi and ηi in the interval (xi−1 , xi+1 ).

The difference method results when the error terms are deleted and the boundary condi-
tions are employed:

w0 = 0, wN +1 = log 2,

and
µ ¶2
wi+1 − 2wi + wi−1 wi+1 − wi−1
− − − wi + log xi = 0, (3)
h2 2h

for each i = 1, 2, . . . , N . Multiplying (3) by h2 , we obtain

µ ¶
wi+1 − wi−1 2
−wi+1 + 2wi − wi−1 − − h2 wi + h2 log xi = 0,
2
which can be written as:
µ ¶2
wi+1 − wi−1
−wi+1 + 2wi − wi−1 − − h2 wi + h2 log xi = 0,
2
or
1¡ 2 2
¢
−wi−1 + 2wi − wi+1 − wi−1 − 2wi−1 wi+1 + wi+1 − h2 wi + h2 log xi = 0.
4

1
Thus, the N × N nonlinear system is:
1¡ 2 ¢
−0 + 2w1 − w2 −0 − 2 · 0 · w2 + w22 − h2 w1 + h2 log x1 = 0,
4
1¡ ¢
−w1 + 2w2 − w3 − w12 − 2w1 w3 + w32 − h2 w2 + h2 log x2 = 0,
4
1¡ ¢
−w2 + 2w3 − w4 − w22 − 2w2 w4 + w42 − h2 w3 + h2 log x3 = 0,
4
.. ..
. .
1¡ 2 2
¢
−wN −2 + 2wN −1 − wN − wN −2 − 2wN −2 wN + wN − h2 wN −1 + h2 log xN −1 = 0,
4
1¡ 2 2
¢
−wN −1 + 2wN − log 2 − wN −1 − 2wN −1 log 2 + (log 2) − h2 wN + h2 log xN = 0,
4
where we designate the left-hand side of the first equation as F1 (w1 , . . . , wN ), the second
equation as F2 (w1 , . . . , wN ), . . ., the last equation as FN (w1 , . . . , wN ). Also, we designate
F~ = (F1 , . . . , FN )T and w~ = (w1 , . . . , wN )T .

We use Newton’s method for nonlinear systems to approximate the solution to the
(k) (k) (k)
system F~ (w)
~ = 0 above. A sequence of iterates w ~ (k) = (w1 , w2 , . . . , wN )T is generated
that converges to the solution of this system. The Jacobian matrix J for this system is
 ∂F ∂F1 ∂F1 ∂F1 
1
···
 ∂w1 ∂w2 ∂w3 ∂wN 
 
 
 ∂F2 ∂F2 ∂F2 ∂F2 
 ··· 
 ∂w ∂w ∂w ∂w 
 1 2 3 N 
 .. .. .. .. .. 
 . . . . . 
J(w1 , . . . , wN ) = 
 .. .. .. .. ..


 . . . . . 
 
 ∂FN −1 ∂FN −1 ∂FN −1 ∂FN −1 
 · · · 
 ∂w1 ∂w2 ∂w3 ∂wN 
 
 
 ∂F ∂FN ∂FN ∂FN 
N
···
∂w1 ∂w2 ∂w3 ∂wN
 1

2 − h2 −1 + 2 · 0 − 12 w2 0 ··· 0
 
 
 .. .. 
 −1 − 1 w1 + 1 w3 2 − h2 −1 + 12 w1 − 21 w3 . . 
 2 2 
 .. 
 0 . 
 
 .. .. .. 
= . . . .
 
 .. 
 . 0 
 
 .. .. 1 1 1 

 . . −1 − 2 wN −2 + 2 wN 2− h2 −1 + 2 wN −2 − 21 wN 

 
0 0 0 ··· 2 − h2

We can now use the Netwon’s method for nonlinear systems

¡ (k−1) ¢ ¡ (k−1) ¢
~ (k) = w
w ~ (k−1) − J −1 w
~ F~ w
~ .

2
Section 7.1, Problem 1: Find ||x||∞ and ||x||2 for the following vectors:
a) x = (3, −4, 0, 32 )T ;
c) x = (sin k, cos k, 2k )T for a fixed positive integer k.

Solution: The L∞ and L2 norms for the vector x = (x1 , x2 , . . . , xn )T are defined by
||x||∞ = max |xi |,
1≤i≤n
½X
n ¾1
2
||x||2 = x2i .
i=1

a) For x = (3, −4, 0, 32 )T :

n ¯ 3 ¯o
¯ ¯
||x||∞ = max |3|, | − 4|, |0|, ¯ ¯ = 4,
r 2
³ 3 ´2
||x||2 = 32 + (−4)2 + 02 + = 5.22015325.
2

c) For x = (sin k, cos k, 2k )T , k is a positive integer :

© ª
||x||∞ = max | sin k|, | cos k|, |2k | = 2k ,
q p
||x||2 = sin2 k + cos2 k + (2k )2 = 1 + 4k .

Section 7.1, Problem 2(a): Verify that the function || · ||1 , defined on Rn by
n
X
||x||1 = |xi |,
i=1

is a norm on Rn .

Solution:
(i) For all x ∈ Rn ,
n
X
||x||1 = |xi | ≥ 0. X
i=1

(ii) If x = 0, then
n
X n
X
||x||1 = |xi | = 0 = 0. X
i=1 i=1
P
If ||x||1 = 0, we have ni=1 |xi | = 0, and thus, x = 0. X
(iii) For all α ∈ R and x ∈ Rn ,
n
X n
X n
X
||αx||1 = |αxi | = |α||xi | = |α| |xi | = |α| ||x||1 . X
i=1 i=1 i=1

(iii) For all x, y ∈ Rn ,

n
X n
X n n
¡ ¢ X X
||x + y||1 = |xi + yi | ≤ |xi | + |yi | = |xi | + |yi | = ||x||1 + ||y||1 . X
i=1 i=1 i=1 i=1

Thus, || · ||1 is a norm on Rn .

3
Section 7.1, Problem 2(c): Prove that for all x ∈ Rn , ||x||1 ≥ ||x||2 .

Solution: Let x = (x1 , x2 , . . . , xn )T , and note that

¡ ¢2
|x1 | + |x2 | + . . . + |xn | ≥ x21 + x22 + . . . + x2n ,

or
µX
n ¶2 X
n
|xi | ≥ x2i ,
i=1 i=1
or
n
X µX
n ¶1
2
|xi | ≥ x2i ,
i=1 i=1

which means that ||x||1 ≥ ||x||2 .

Section 7.1, Problem 4(c): Find || · ||∞ for the following matrix:
 
2 −1 0
A =  −1 2 −1  .
0 −1 2

Solution: We have
n
X
||A||∞ = max |aij |.
1≤i≤n
j=1

Since
n
X
|a1j | = |a11 | + |a12 | + |a13 | = |2| + | − 1| + |0| = 3,
j=1
Xn
|a2j | = |a21 | + |a22 | + |a23 | = | − 1| + |2| + | − 1| = 4,
j=1
n
X
|a3j | = |a31 | + |a32 | + |a33 | = |0| + | − 1| + |2| = 3,
j=1

we have ||A||∞ = max{3, 4, 3} = 4.

Section 7.1, Problem 7: Show by example that || · ||~ , defined by ||A||~ = max |aij |,
1≤i,j≤n
does not define a matrix norm.

Solution: A function
· ||¸ · ||~ is a matrix
· norm
¸ only if it satisfies
· definition
¸ 7.8 on page 424.
1 1 1 0 2 0
Consider A = and B = . Then, AB = . We have ||A||~ = 1,
0 0 1 0 0 0
||B||~ = 1, and ||AB||~ = 2, and thus, ||AB||~ ≥ ||A||~ ||B||~ , which contradicts one of
the conditions for being a norm.

4
Section 7.1, Problem 9(a): The Frobenius norm (which is not a natural norm) is
defined for an n × n matrix A by
µX n Xn ¶1
2
2
||A||F = |aij | .
i=1 j=1

Show that || · ||F is a matrix norm.

Solution: For all n × n matrices A and B and all real numbers α, we have:
(i)
µXn X n ¶1
2
2
||A||F = |aij | ≥ 0. X
i=1 j=1

(ii)
µX
n X
n ¶1
2
2
||A||F = |aij | = 0 if and only if A is a 0 matrix. X
i=1 j=1

(iii)
n X
X n n X
X n n X
X n
||αA||2F = |α aij | = 2 2
|α| |aij | = |α|2 2
|aij |2 = |α|2 ||A||2F .
i=1 j=1 i=1 j=1 i=1 j=1
⇒ ||αA||F = |α| ||A||F . X
n
X ³X
n ´1 ³ X
n ´1
2 2
(iv) Here, we will use Cauchy-Schwarz Inequality: xi yi ≤ x2i yi2 .
i=1 i=1 i=1
n X
X n
||A + B||2F = |aij + bij |2
i=1 j=1
n X
X n
≤ (|aij | + |bij |)2
i=1 j=1
Xn X n ³ ´
2 2
= |aij | + 2|aij ||bij | + |bij |
i=1 j=1
Xn X n n X
X n n X
X n
= |aij |2 + 2 |aij ||bij | + |bij |2 ≤ (Cauchy-Schwarz)
i=1 j=1 i=1 j=1 i=1 j=1
Xn X n ³Xn X n ´1 ³ Xn X n ´1 n X
X n
2 2
≤ |aij |2 + 2 |aij |2 |bij |2 + |bij |2
i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1
µ³ X
n X
n ´1 ³X n X
n ´ 1 ¶2
2 2
= |aij |2 + |bij |2
i=1 j=1 i=1 j=1
¡ ¢2
= ||A||F + ||B||F .
⇒ ||A + B||F ≤ ||A||F + ||B||F . X
(v) Note that
 Pn Pn Pn 
Pk=1 a1k bk1 Pk=1 a1k bk2 · · · ··· Pk=1 a1k bkn
 n n n 
 k=1 a2k bk1 k=1 a2k bk2 · · · ··· k=1 a2k bkn 
 .
.. .. .. 
AB =  . . .

 .. .. .. 
 
Pn . Pn . Pn Pn .
k=1 ank bk1 k=1 ank bk2 · · · k=1 ank bk,n−1 k=1 ank bkn
5
 n ¯X
n X
X n ¯2 X n µX
n X n ¶2
¯ ¯
||AB||2F = ¯ aik bkj ¯ ≤ |aik bkj | ≤ (Cauchy-Schwarz)
i=1 j=1 k=1 i=1 j=1 k=1
Xn X n µX n n
X ¶
2 2
≤ |aik | |bkj | ...
i=1 j=1 k=1 k=1
³XXn n ´³ X X
n n ´
≤ |aij |2 |bij |2 = ||A||2F ||B||2F .
i=1 j=1 i=1 j=1
⇒ ||AB||F ≤ ||A||F ||B||F . X

CONTINUE TO THE NEXT PAGE.

6
Section 7.1, Problem 9(c): For any matrix A, show that ||A||2 ≤ ||A||F ≤ n1/2 ||A||2 .

Solution: The definitions of || · ||F and || · ||2 norms are:

µX
n X n ¶1
2
2
||A||F = |aij | .
i=1 j=1

||A||2 = max ||Ax||2 .

||x||2 =1

Note, that Ax is a vector:

 Pn 
a1j xj
Pj=1
 n 
 j=1 a2j xj 
Ax =  .. .
 
Pn .
j=1 anj xj

Thus, we have
µX
n ³X
n ´2 ¶ 12
||Ax||2 = aij xj .
i=1 j=1

¶ We first show that ||A||2 ≤ ||A||F .

For vector x, such that ||x||2 = 1, we have
n ³X
X n ´2
||Ax||22 = aij xj ≤ (Cauchy-Schwarz)
i=1 j=1
Xn µ³ Xn ´1 ³ X
n ´ 1 ¶2
2 2
≤ a2ij x2j
i=1 j=1 j=1
n µ³ X
X n ´³ X
n ´¶
= a2ij x2j
i=1 j=1 j=1
n
X X ³ n ´
= a2ij · ||x||22
i=1 j=1
n ³X
X n ´
= a2ij · 1
i=1 j=1
X n X n
= a2ij
i=1 j=1

= ||A||2F .
We showed that, ||Ax||2 ≤ ||A||F for all x, such that ||x||2 = 1.
Thus, max ||Ax||2 ≤ ||A||F , or ||A||2 ≤ ||A||F .
||x||2 =1

· We now show that ||A||F ≤ n1/2 ||A||2 .

1
Let xi = √ for all 1 ≤ i ≤ n. Then,
n
n ³X
X n ´2 n X
X n n n
1 1 XX 2 1
||A||2 = max ||Ax||2 = aij xj = a2ij = aij = ||A||F .
||x||2 =1 n n n
i=1 j=1 i=1 j=1 i=1 j=1

Thus, ||A||F ≤ n1/2 ||A||2 .

7
Section 7.3, Problem 2(c): Find the first two iterations of the Jacobi method for the
following linear system, using x(0) = 0:

4x1 + x2 − x3 + x4 = −2,
x1 + 4x2 − x3 − x4 = −1,
−x1 − x2 + 5x3 + x4 = 0,
x1 − x2 + x3 + 3x4 = 1.

Solution: The linear system Ax = b given by

E1 : 4x1 + x2 − x3 + x4 = −2,
E2 : x1 + 4x2 − x3 − x4 = −1,
E3 : −x1 − x2 + 5x3 + x4 = 0,
E4 : x1 − x2 + x3 + 3x4 = 1

has the unique solution x = (−0.75342, 0.041096, −0.28082, 0.69178).

To convert Ax = b to the form x = T x + c, solve equation E1 for x1 , E2 for x2 , E3 for
x3 , E4 for x4 , to obtain
x1 = − 41 x2 + 14 x3 − 14 x4 − 12 ,
x2 = − 14 x1 + 41 x3 + 14 x4 − 14 ,
1 1
x3 = 5 x1 + 5 x2 − 15 x4 ,
1 1 1
x4 = − 3 x1 + 3 x2 − 3 x3 + 13 .
Then Ax = b can be written in the form x = T x + c, with
   1 
0 − 14 1
4 − 14 −2
 −1 0 1 1   −1 
T =
 1
4 4 4  and c =   0 .
4 
5
1
5 0 − 15 
− 13 1
3 − 13 0 1
3

For initial approximation, we let x(0) = (0, 0, 0, 0)T . Then x(1) is given by
(1) (0) (0) (0)
x1 = − 14 x2 + 41 x3 − 14 x4 − 12 = −0.5,
(1) (0) (0) (0)
x2 = − 14 x1 + 41 x3 + 14 x4 − 14 = −0.25,
(1) (0) (0) (0)
x3 = 15 x1 + 51 x2 − 15 x4 = 0,
(1) (0) (0) (0)
x4 = − 31 x1 + 31 x2 − 31 x3 + 13 = 1/3.

The next iterate, x(2) , is given by

(2) (1) (1) (1)
x1 = − 41 x2 + 41 x3 − 14 x4 − 12 = −0.52083,
(2) (1) (1) (1)
x2 = − 14 x1 + 41 x3 + 14 x4 − 14 = −0.041667,
(2) (1) (1) (1)
x3 = 15 x1 + 51 x2 − 15 x4 = −0.21667,
(2) (1) (1) (1)
x4 = − 13 x1 + 31 x2 − 31 x3 + 13 = 0.41667.

8
Section 7.3, Problem 4(c): Find the first two iterations of the Gauss-Seidel method
for the following linear system, using x(0) = 0:

4x1 + x2 − x3 + x4 = −2,
x1 + 4x2 − x3 − x4 = −1,
−x1 − x2 + 5x3 + x4 = 0,
x1 − x2 + x3 + 3x4 = 1.

Solution: In section 7.3, Problem 2(c), we used Jacobi method to solve the linear system
above. The following equations were used:
(k) (k−1) (k−1) (k−1)
x1 = − 14 x2 + 14 x3 − 14 x4 − 21 ,
(k) (k−1) (k−1) (k−1)
x2 = − 14 x1 + 14 x3 + 14 x4 − 41 ,
(k) (k−1) (k−1) (k−1)
x3 = 51 x1 + 51 x2 − 15 x4 ,
(k) 1 (k−1) 1 (k−1) 1 (k−1) 1
x4 = − 3 x1 + 3 x2 − 3 x3 +3.
(k) (k)
However, since for i > 1, x1 , . . . , xi−1 have already been computed, these are probably
(k−1) (k−1)
better approximations to the actual solutions x1 , . . . , xi−1 than x1 , . . . , xi−1 . Hence,
Gauss-Seidel uses the most recently available approximations to x1 , . . . , xi−1 in a calcula-
tion of the next iterate:
(k) (k−1) (k−1) (k−1)
x1 = − 14 x2 + 14 x3 − 14 x4 − 21 ,
(k) (k) (k−1) (k−1)
x2 = − 14 x1 + 41 x3 + 14 x4 − 41 ,
(k) (k) (k) (k−1)
x3 = 51 x1 + 51 x2 − 15 x4 ,
(k) (k) (k) (k)
x4 = − 13 x1 + 31 x2 1
− 3 x3 +3.1

For initial approximation, we let x(0) = (0, 0, 0, 0)T . Then x(1) is given by
(1) (0) (0) (0)
x1 = − 14 x2 + 41 x3 − 14 x4 − 12 = −0.5,
(1) (1) (0) (0)
x2 = − 14 x1 + 41 x3 + 14 x4 − 14 = −0.125,
(1) (1) (1) (0)
x3 = 15 x1 + 51 x2 − 15 x4 = −0.125,
(1) (1) (1) (1)
x4 = − 13 x1 + 31 x2 − 31 x3 + 13 = 0.5.

The next iterate, x(2) , is given by

(2) (1) (1) (1)
x1 = − 41 x2 + 41 x3 − 14 x4 − 12 = −0.625,
(2) (2) (1) (1)
x2 = − 14 x1 + 41 x3 + 14 x4 − 14 = 0,
(2) (2) (2) (1)
x3 = 51 x1 + 51 x2 − 15 x4 = −0.225,
(2) 1 (2) 1 (2) 1 (2)
x4 = − 3 x1 + 3 x2 − 3 x3 + 13 = 0.61667.

Comparing x(2) to the exact solution x = (−0.75342, 0.041096, −0.28082, 0.69178), we see
that Gauss-Seidel method gave more accurate results than Jacobi method.