General Vector Norms and the Associated matrix Norm

In this section we extend the concept of norm that we defined earlier. We

have already introduced the vector norm defined for x ∈ Rn by
X n
2
(1) kxk = x2i
k=1
In conjunction with this we have introduced the associated matrix norm
by kAk = maxkxk=1 kAxk and noted that
(2) kAk2 = max{|λ| : λ is an eigenvalue of AT A}
The above definition is only one example of a vector norm and its as-
sociated matrix norm. More generally, a vector norm, generically denoted
by kxk, is a real-valued function that satisfies these three axioms for all x,
y ∈ Rn and all c ∈ R:
• kxk ≥ 0 and = 0 if and only if x = 0 (the zero vector).
• kcxk = |c|kxk
• kx + yk ≤ kxk + kyk (triangle inequality).
The commonly used vector norms Rn are
Pn
• the 1-norm: kxk1 = q i=1 |xi |
Pn 2
• the 2-norm: kxk2 = i=1 xi . This is the norm we defined by
formula (1).
• the infinity norm: kxk∞ = max{|xi | : i = 1, 2, . . . , n}

When a vector arises as a matrix transform of another vector, that is

when y = Ax for some n × n matrix A, it is often important to estimate the
norm of y in terms of x. The concept of matrix norm is helpful in this
respect. Here are the basic facts.
The matrix norm relative to a given vector norm (or subordinate
to a given vector norm) is defined by kAk = max{kAxk : kxk ≤ 1} =
max{kAxk : kxk = 1}. The main property of a matrix norm is that it is
the smallest number K such that kAxk ≤ Kkxk holds for all x.
In other words, if someone claims to have proven that kAxk ≤ Kkxk
holds for all values of x, then you can reply that K is no smaller than kAk.
Bottom line: for all x we can assert that kAxk ≤ kAkkxk.
Here are formulas for the matrix norms relative to commonly used norms:
P
• kAk∞ = max{ nj=1 |aij | : i = 1, 2, . . . , n} = the max of all absolute
row sums. P
• kAk1 = max{ ni=1 |aij | : j = 1, 2, . . . , n} = the max of all absolute
column sums.
• kAk22 = max{λ : λ is an eigenvalue of AT A} (this one is a little
harder to compute)
• if A is real and symmetric, kAk2 = max{|λ| : λ is an eigenvalue of
A}. This is a special case of the previous formula.
1
The Discrete Second Derivative Matrix c 2007 Stephen Demko
°
· ¸
−1 3
For example if A = , then you can always assert that kAxk∞ ≤
2 −2.5
4.5kxk∞ since kAk∞ = 4.5. Similarly, kAxk1 ≤ 5.5kxk1 .

The Discrete Second Derivative Matrix

In this section, we derive a matrix that governs a great deal of our dealings
with partial differential equations. We go on the study its eigenvalues and
eigenvectors and draw some important conclusions.
The Central Difference Approximation to u00 . If u(x) is a sufficiently
differentiable function, then the standard central difference approxima-
tion to u00 (x) is
1
u00 (x) = 2 [u(x + h) − 2u(x) + u(x − h)] + O(h2 )
h
We can approximate the second derivative to u on an interval [a, b] as
follows:
(1) divide [a, b] into N intervals of equal length by the equally spaced
partition points xi :
a = x0 < x1 < . . . xN = b
where xi − xi−1 = (b − a)/N = h. With this we have the formulas for
1≤i≤N −1
1
u00 (xi ) = 2 [u(xi+1 ) − 2u(xi ) + u(xi−1 )] + O(h2 )
h
If u(a) = L and u(b) = R, then the global relationship expressed by the
equations above can be written in matrix form as

(3)
 
u00 (x1 )    u(x )   
L
−2 1 0 0 ... 0 1
 u00 (x2 )   1  u(x2 )  0
   −2 1 0 ... 0   
 ..   0  ..   .. 
  1 −2 1 ... 0  .
 . = 1   .  1   2
 ..  h2 
 ..
. ..
.
..
.
..
.
..
.
..  
 .  + h2  .  + O(h )
 .   .  ..   .. 
  0    
u00 (xN −2 ) 0 ... 1 −2 1  u(xN −2 ) 0
00
u (xN −1 ) 0 0 ... 0 1 −2 u(xN −1 ) R

In (3), the O(h2 ) quantity is the error vector whose contents are unknown,
but whose magnitude is known to be of order h2 as h → 0.
Let’s write the above system as
1
(4) u00 = 2 Au + b + O(h2 )
h
Notice that we have incorporated the h12 term into the vector b.
From this we can see that if we want to find a solution to the two-point
boundary value problem u00 (x) = f (x) with u(a) = L and u(b) = R, we can
drop the O(h2 ) vector and replace the vector carrying the u00 values with
2
The Discrete Second Derivative Matrix c 2007 Stephen Demko
°

the right hand side of the above and solve the system below for the vector
of ui values. Note that the ui s are the entities that we actually find. They
are not the values u(xi ), but are hopefully close to them.

      
−2 1 0 0 ... 0 u1 f (x1 ) L
 1 −2 1 0 ...   u 
0  2    f (x 2 )   0
 . .  .
1  0 1 −2 1 ... 0   
  ..   .. 
 1  
 .. 
 . . . . . .    =
..   ..    ..  −  
h2  .. . . .. .. ..  h2  ... 
  .   .   
0 0 . . . 1 −2 1  uN −2  f (xN −2 ) 0
0 0 ... 0 1 −2 uN −1 f (xN −1 ) R
We can write this system as h12 Aû = f − b. We want to compare the
vectors u and û. Since u00 = f (as function and as vectors), we have
1
Au = f − b + O(h2 )
h2
1
Aû = f − b
h2
Subtracting gives
1
A(u − û) = O(h2 )
h2
u − û = A−1 (O(h4 ))
For a general norm we can conclude ku − ûk ≤ kAkO(h2 ). However, we
can be more precise here, because it can be verified that if A−1 = (rij ), then
for i ≤ j
i(N − j)
rij = rji =
N
With this one can prove that kA k∞ ≤ (b − a)2 /2h2 and conclude that
−1

(5) ku − ûk∞ = O(h2 )

Eigenanalysis of The Discrete Second Derivative Matrix. For the

stability analysis of numerical solutions of parabolic PDEs it is important
to know how the powers of certain functions of A behave. In addition more
detailed knowledge of the eigenvalues and eigenvectors of A can lead to a
better understanding of the properties and limits of some methods.
Recall that the matrix A introduced above is an (N − 1) × (N − 1) real
symmetric matrix. We can write A = (S−2I) where I is the (N −1)×(N −1)
 
0 1 0 ... 0
1 0 1 . . . 0
 .. .. .. .
 . . . .. 
identity matrix and S = 0 
. . . . . 
 .. . . . . . . .. 
0 ... 0 1 0
3
The Discrete Second Derivative Matrix c 2007 Stephen Demko
°

By the Spectral Mapping Theorem, once we know the eigenvalues and

eigenvectors of S, we will be able to derive them for A via the function
g(z) = z − 2: the eigenvalues of A are the values g(λ) as λ runs over the
set of eigenvalues of S. The eigenvector of A corresponding to g(λ) is the
eigenvector of S corresponding to λ. Finally, the eigenvectors of S can be
chosen to be orthonormal. We will produce a set of orthogonal eigenvectors,
they may have to be normalized.
Now using the elementary trigonometric identity
sin(x − y) + sin(x + y) = 2 sin x cos y = (2 cos y) sin x,
one can
 show that
 the eigenvalues of S are 2 cos jπ
N and the eigenvectors are
j
v (1)
 v j (2) 
  ijπ
vj =  ..  where v j (i) = sin N .
 . 
v j (N − 1)
Note that vj is the function sin jπx sampled at the points i/N for i =
1, . . . , N − 1. Therefore, the vector v1 is positive, and the general vector vj
has j − 1 sign changes with vN −1 oscillating most rapidly. The reader might
want to sketch a few instances of graphs of sin jπx and note how the values
at the points i/N behave.
Also, one observes from Taylor expansions of cos x at 0 and π that distance
of the extreme eigenvalues from the ends of the interval can be bounded:
λ1 = 2 cos N π
= 2 − O(N −2 ) = 2 − O(h2 ) and λN −1 = 2 cos (N −1)π
N = −2 +
O(N −2 ) = −2 + O(h2 ). Note that the eigenvalues close to −2 correspond
to the higher frequency eigenvectors.
Implications for A. We have that σ(S) ⊂ (−2, 2) where (a, b) denotes the
open interval {x : a < x < b} and A = S − 2I, so σ(A) ⊂ (−4, 0).
Comments on Computing Eigenvalues and Eigenvectors with Mat-
lab. If B is an n × n matrix, then the command [U,D] = eig(B) produces
eigenvectors as the columns of U with corresponding eigenvalues on the di-
agonal of D. This is the case for at least the case of symmetric B. In this
case the matrix U has orthonormal columns. Suppose the column vectors
of U are ui for 1 ≤ i ≤ n. Then, every x ∈ Rn has an expansion
x = c1 u1 + c2 u2 + · · · + cn ub
where ci = uTi x. The vector that holds the ci can be calculated as U T x. If
the ui are the orthonormal eigenvectors of our matrix A, as defined earlier,
then the number ck is a measure of the contribution of the k th eigenvector
to x
EXERCISES. In the following α is a parameter. It is always positive. In
Rn we define the standard unit basis vector ek for k = 1, 2, . . . n as the vector
with 0’s everywhere except in the k th coordinate where it is 1. ek (j) = 1 if
and only if i = j, otherwise ek (j) = 0.
4
The Discrete Second Derivative Matrix c 2007 Stephen Demko
°

1. Define fα (z) = 1+αz. Let M = f (A) For different values of n (take them
even, say n = 10, 50, 100) investigate the behavior of M k en/2 as k grows.
Take the following values of α: 0.25, 0.5, 0.75, 1.00.
1
2. Repeat the investigations of problem 1 using gα (z) = 1−αz instead of f .
3. Repeat the investigations of problem 1 using hα (z) = 1+0.5αz
1−0.5αz instead of
f.
Things to look for: Does the process settle down? Does it blow up?
when? why? In the cases that it settles down, does it do so with oscillations
or without oscillations.
Explain what you see in terms of the eigenanalysis of the appropriate
matrix.