400 CHAPTER 14. ANALYSIS OF LINEAR TRANSFORMATIONS

for some r ∈ (0,1). Then there exists a unique fixed point, x ∈ E such that

Tx= x. (14.10)

Letting x1 ∈ E, this fixed point x, is the limit of the sequence of iterates,

x1,Tx1,T 2x1, · · · . (14.11)

In addition to this, there is a nice estimate which tells how close x1 is to x in terms ofthings which can be computed.∣∣x1−x

∣∣≤ 11− r

∣∣x1−Tx1∣∣ . (14.12)

Proof: This follows easily when it is shown that the above sequence,{

T kx1}∞

k=1 is aCauchy sequence. Note that ∣∣T 2x1−Tx1∣∣≤ r

∣∣Tx1−x1∣∣ .Suppose ∣∣∣T kx1−T k−1x1

∣∣∣≤ rk−1 ∣∣Tx1−x1∣∣ . (14.13)

Then ∣∣∣T k+1x1−T kx1∣∣∣ ≤ r

∣∣∣T kx1−T k−1x1∣∣∣

≤ rrk−1 ∣∣Tx1−x1∣∣= rk ∣∣Tx1−x1∣∣ .By induction, this shows that for all k ≥ 2, 14.13 is valid. Now let k > l ≥ N.∣∣∣T kx1−T lx1

∣∣∣ =

∣∣∣∣∣k−1

∑j=l

(T j+1x1−T jx1)∣∣∣∣∣≤ k−1

∑j=l

∣∣T j+1x1−T jx1∣∣≤

k−1

∑j=N

r j ∣∣Tx1−x1∣∣≤ ∣∣Tx1−x1∣∣ rN

1− r

which converges to 0 as N→ ∞. Therefore, this is a Cauchy sequence so it must convergeto x ∈ E. Then

x= limk→∞

T kx1 = limk→∞

T k+1x1 = T limk→∞

T kx1 = Tx.

This shows the existence of the fixed point. To show it is unique, suppose there wereanother one, y. Then

|x−y|= |Tx−Ty| ≤ r |x−y|and so x= y.

It remains to verify the estimate.∣∣x1−x∣∣ ≤ ∣∣x1−Tx1∣∣+ ∣∣Tx1−x

∣∣= ∣∣x1−Tx1∣∣+ ∣∣Tx1−Tx∣∣

≤∣∣x1−Tx1∣∣+ r

∣∣x1−x∣∣

and solving the inequality for∣∣x1−x

∣∣ gives the estimate desired. ■The following corollary is what will be used to prove the convergence condition for the

various iterative procedures.