348 CHAPTER 13. NORMS

Lemma 13.6.4 Suppose T : E → E where E is a Banach space with norm |·|. Also suppose

|Tx− Ty| ≤ r |x− y| (13.20)

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

Tx = x. (13.21)

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

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

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

∣∣ ≤ 1

1− r

∣∣x1 − Tx1∣∣ . (13.23)

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

∣∣ . (13.24)

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, 13.24 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

rj∣∣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.