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