<< . .

. 36
( : 95)



. . >>

0 ’1 0
1 0 0 1 0
   
2 3 ’2 1   1
0 0 0
   
A1 =   , A2 =  .
 ’1 0 ’2 0   0
0 1 0
° » ° »
1 ’1 14 1 0 0 0

[Solution : A1 , reducible; A2 , irreducible.]
5. Provide an estimate of the number of complex eigenvalues of the matrix
® 
’4 0 0 0.5 0
 
22 4 ’3 1 
 
 
A =  0.5 0 0 0 .
’1
 
 
 0.5 0 3 0
0.2
° »
’1
2 0.5 3 4

[Hint : Check that A can be reduced to the form

M1 M2
A=
0 M3

where M1 ∈ R2—2 and M2 ∈ R3—3 . Then, study the eigenvalues of blocks M1
and M2 using the Gershgorin theorems and check that A has no complex
eigenvalues.]
6. Let A ∈ Cn—n be a diagonal matrix and let A = A + E be a perturbation
of A with eii = 0 for i = 1, . . . , n. Show that
n
|»i (A) ’ »i (A)| ¤ |eij |, i = 1, . . . , n. (5.71)
j=1



7. Apply estimate (5.71) to the case in which A and E are, for µ ≥ 0, the
matrices
1 0 0 µ
A= , E= .
0 2 µ 0

[Solution : σ(A) = {1, 2} and σ(A) = {(3 “ 1 + 4µ2 )/2}.]
242 5. Approximation of Eigenvalues and Eigenvectors

8. Check that ¬nding the zeros of a polynomial of degree ¤ n with real coef-
¬cients
n
ak xk = a0 + a1 x + ... + an xn , an = 0, ak ∈ R, k = 0, . . . n
pn (x) =
k=0

is equivalent to determining the spectrum of the Frobenius matrix C ∈
Rn—n associated with pn (known as the companion matrix)
® 
’(an’1 /an ) ’(an’2 /an ) . . . ’(a1 /an ) ’(a0 /an )
 
1 0 ... 0 0
 
 
0 1 ... 0 0
C=  .(5.72)
 
. . . .
..
° »
. . . .
.
. . . .
0 0 ... 1 0

An important consequence of the result above is that, due to Abel™s theo-
rem, there exist in general no direct methods for computing the eigenvalues
of a given matrix, for n ≥ 5.
9. Show that if matrix A ∈ Cn—n admits eigenvalue/eigenvector pairs (», x),
then the matrix UH AU, with U unitary, admits eigenvalue/eigenvector
pairs », UH x . (Similarity transformation using an orthogonal matrix).
10. Suppose that all the assumptions needed to apply the power method are
satis¬ed except for the requirement ±1 = 0 (see Section 5.3.1). Show that
in such a case the sequence (5.17) converges to the eigenvalue/eigenvector
pair (»2 , x2 ). Then, study experimentally the behaviour of the method,
computing the pair (»1 , x1 ) for the matrix
® 
1 ’1 2
 
A =  ’2 0 5 .
° »
6 ’3 6

For this, use Program 26, taking q(0) = 1T / 3 and q(0) = w(0) / w(0) 2 ,
respectively, where w(0) = (1/3)x2 ’ (2/3)x3 .
[Solution : »1 = 5, »2 = 3, »3 = ’1 and x1 = [5, 16, 18]T , x2 = [1, 6, 4]T ,
x3 = [5, 16, 18]T .]
11. Show that the companion matrix associated with the polynomial pn (x) =
xn + an xn’1 + . . . + a1 , can be written in the alternative form (5.72)
® 
0
0 a1
 ’1 
0 a2
 
 
.. .. ..
A= .
. . .
 
 
’1
° »
0 an’1
0 ’1 an

12. (From [FF63]) Suppose that a real matrix A ∈ Rn—n has two maximum
module complex eigenvalues given by »1 = ρeiθ and »2 = ρe’iθ , with
5.13 Exercises 243

θ = 0. Assume, moreover, that the remaining eigenvalues have modules
less than ρ. The power method can then be modi¬ed as follows:
let q(0) be a real vector and q(k) be the vector provided by the power
(k)
method without normalization. Then, set xk = qn0 for some n0 , with
1 ¤ n0 ¤ n. Prove that

xk xk+2 ’ x2 »3
k+1
+O
2 k
ρ= ,
xk’1 xk+1 ’ x2 ρ
k


ρxk’1 + r’1 xk+1 »3
+O k
cos(θ) = .
2xk ρ

[Hint : ¬rst, show that

»3
xk = C(ρk cos(kθ + ±)) + O k
,
ρ

where ± depends on the components of the initial vector along the direc-
tions of the eigenvectors associated with »1 and »2 .]
13. Apply the modi¬ed power method of Exercise 12 to the matrix
® 
1 ’1 4 1
4
A=° 1 0 »,
0
0 1 0

and compare the obtained results with those yielded by the standard power
method.
14. (Taken from [Dem97]). Apply the QR iteration with double shift to com-
pute the eigenvalues of the matrix
® 
00 1
°1 0 0 ».
A=
01 0

Run Program 37 setting toll=eps, itmax=100 and comment about the
form of the obtained matrix T(iter) after iter iterations of the algorithm.
[Solution : the eigenvalues of A are the solution of »3 ’ 1 = 0, i.e.,

σ(A) = 1, ’1/2 ± 3/2i . After iter=100 iterations, Program 37 yields
the matrix
® 
’1
0 0
T(100) = ° 1 0 »,
0
0 ’1 0

which means that the QR iteration leaves A unchanged (except for sign
changes that are non relevant for eigenvalues computation). This is a simple
but glaring example of matrix for which the QR method with double shift
fails to converge.]
6
Root¬nding for Nonlinear Equations




This chapter deals with the numerical approximation of the zeros of a real-
valued function of one variable, that is

given f : I = (a, b) ⊆ R ’ R, ¬nd ± ∈ C such that f (±) = 0. (6.1)

The analysis of problem (6.1) in the case of systems of nonlinear equations
will be addressed in Chapter 7.
Methods for the numerical approximation of a zero of f are usually iter-
ative. The aim is to generate a sequence of values x(k) such that

lim x(k) = ±.
k’∞

The convergence of the iteration is characterized by the following de¬nition.

De¬nition 6.1 A sequence x(k) generated by a numerical method is
said to converge to ± with order p ≥ 1 if

|x(k+1) ’ ±|
∃C > 0 : ¤ C, ∀k ≥ k0 , (6.2)
|x(k) ’ ±|p
where k0 ≥ 0 is a suitable integer. In such a case, the method is said to be
of order p. Notice that if p is equal to 1, in order for x(k) to converge to
± it is necessary that C < 1 in (6.2). In such an event, the constant C is
called the convergence factor of the method.
Unlike the case of linear systems, convergence of iterative methods for
root¬nding of nonlinear equations depends in general on the choice of the
246 6. Root¬nding for Nonlinear Equations

initial datum x(0) . This allows for establishing only local convergence re-
sults, that is, holding for any x(0) which belongs to a suitable neighborhood
of the root ±. Methods for which convergence to ± holds for any choice of
x(0) in the interval I, are said to be globally convergent to ±.


6.1 Conditioning of a Nonlinear Equation
Consider the nonlinear equation f (x) = •(x) ’ d = 0 and assume that f
is a continuously di¬erentiable function. Let us analyze the sensitivity of
¬nding the roots of f with respect to changes in the datum d.
The problem is well posed only if the function • is invertible. In such a
case, indeed, one gets ± = •’1 (d) from which, using the notation of Chapter
2, the resolvent G is •’1 . On the other hand, (•’1 ) (d) = 1/• (±), so that
formula (2.7) for the approximate condition number (relative and absolute)
yields
|d| 1
K(d) , Kabs (d) . (6.3)
|±||f (±)| |f (±)|

The problem is thus ill-conditioned when f (±) is “small” and well-condi-
tioned if f (±) is “large”.
The analysis which leads to (6.3) can be generalized to the case in which
± is a root of f with multiplicity m > 1 as follows. Expanding • in a Taylor
series around ± up to the m-th order term, we get
m
•(k) (±)
(δ±)k + o((δ±)m ).
d + δd = •(± + δ±) = •(±) +
k!
k=1

Since •(k) (±) = 0 for k = 1, . . . , m ’ 1, we obtain

δd = f (m) (±)(δ±)m /m!

so that an approximation to the absolute condition number is
1/m
m!δd 1
Kabs (d) . (6.4)
|δd|
f (m) (±)

Notice that (6.3) is the special case of (6.4) where m = 1. From this it also
follows that, even if δd is su¬ciently small to make |m!δd/f (m) (±)| < 1,
Kabs (d) could nevertheless be a large number. We therefore conclude that
the problem of root¬nding of a nonlinear equation is well-conditioned if ±
is a simple root and |f (±)| is de¬nitely di¬erent from zero, ill-conditioned
otherwise.
Let us now consider the following problem, which is closely connected
with the previous analysis. Assume d = 0 and let ± be a simple root of f ;
6.1 Conditioning of a Nonlinear Equation 247

moreover, for ± = ±, let f (ˆ ) = r = 0. We seek a bound for the di¬erence
ˆ ± ˆ
± ’ ± as a function of the residual r. Applying (6.3) yields
ˆ ˆ

1
Kabs (0) .
|f (±)|

Therefore, letting δx = ± ’ ± and δd = r in the de¬nition of Kabs (see
ˆ ˆ
(2.5)), we get

|ˆ ’ ±| |ˆ|
± r
, (6.5)
|±| |f (±)||±|

where the following convention has been adopted: if a ¤ b and a c, then
we write a c. If ± has multiplicity m > 1, using (6.4) instead of (6.3) and
proceeding as above, we get
1/m
|ˆ ’ ±|
± m!
|ˆ|1/m .
r (6.6)
|±| |f (m) (±)||±|m


These estimates will be useful in the analysis of stopping criteria for itera-
tive methods (see Section 6.5).
A remarkable example of a nonlinear problem is when f is a polynomial
pn of degree n, in which case it admits exactly n roots ±i , real or complex,
each one counted with its multiplicity. We want to investigate the sensitivity
of the roots of pn with respect to the changes of its coe¬cients.
To this end, let pn = pn + qn , where qn is a perturbation polynomial of
ˆ
degree n, and let ±i be the corresponding roots of pn . A direct use of (6.6)
ˆ ˆ
yields for any root ±i the following estimate
1/m
|ˆ i ’ ±i |
± m!
|qn (ˆ i )|1/m = S i ,
i
Erel = ± (6.7)
|±i | (m)
|pn (±i )||±i |m

where m is the multiplicity of the root at hand and qn (ˆ i ) = ’pn (ˆ i ) is
± ±
the “residual” of the polynomial pn evaluated at the perturbed root.

Remark 6.1 A formal analogy exists between the a priori estimates so
far obtained for the nonlinear problem •(±) = d and those developed in
Section 3.1.2 for linear systems, provided that A corresponds to • and b
to d. More precisely, (6.5) is the analogue of (3.9) if δA=0, and the same
holds for (6.7) (for m = 1) if δb = 0.

Example 6.1 Let p4 (x) = (x ’ 1)4 , and let p4 (x) = (x ’ 1)4 ’ µ, with 0 < µ
ˆ 1.

4
The roots of the perturbed polynomial are simple and equal to ±i = ±i + µ,
ˆ
where ±i = 1 are the (coincident) zeros of p4 . They lie with intervals of π/2 on

the circle of radius 4 µ and center z = (1, 0) in the complex plane.
248 6. Root¬nding for Nonlinear Equations

The problem is stable (that is limµ’0 ±i = 1), but is ill-conditioned since
ˆ


|±i ’ ±i |
ˆ
= 4 µ, i = 1, . . . 4,
|±i |

For example, if µ = 10’4 the relative change is 10’1 . Notice that the right-side


of (6.7) is just 4 µ, so that, in this case, (6.7) becomes an equality.


Example 6.2 (Wilkinson). Consider the following polynomial

p10 (x) = Π10 (x + k) = x10 + 55x9 + . . . + 10!.
k=1


Let p10 = p10 + µx9 , with µ = 2’23 1.2 · 10’7 . Let us study the conditioning of
ˆ
¬nding the roots of p10 . Using (6.7) with m = 1, we report for i = 1, . . . , 10 in
Table 6.1 the relative errors Erel and the corresponding estimates S i .
i

These results show that the problem is ill-conditioned, since the maximum
relative error for the root ±8 = ’8 is three orders of magnitude larger than
the corresponding absolute perturbation. Moreover, excellent agreement can be

observed between the a priori estimate and the actual relative error.

i
Si i
Si
i Erel i Erel
3.039 · 10’13 3.285 · 10’13 6.956 · 10’5 6.956 · 10’5
1 6
7.562 · 10’10 7.568 · 10’10 1.589 · 10’4 1.588 · 10’4
2 7
7.758 · 10’8 7.759 · 10’8 1.984 · 10’4 1.987 · 10’4
3 8
1.808 · 10’6 1.808 · 10’6 1.273 · 10’4 1.271 · 10’4
4 9
1.616 · 10’5 1.616 · 10’5 3.283 · 10’5 3.286 · 10’5
5 10
TABLE 6.1. Relative error and estimated error using (6.7) for the Wilkinson
polynomial of degree 10




6.2 A Geometric Approach to Root¬nding
In this section we introduce the following methods for ¬nding roots: the
bisection method, the chord method, the secant method, the false position
(or Regula Falsi) method and Newton™s method. The order of the presen-
tation re¬‚ects the growing complexity of the algorithms. In the case of the
bisection method, indeed, the only information that is being used is the sign
of the function f at the end points of any bisection (sub)interval, whilst
the remaining algorithms also take into account the values of the function

<< . .

. 36
( : 95)



. . >>