14.4. ITERATIVE METHODS FOR LINEAR SYSTEMS 401

Corollary 14.4.5 Suppose T : E→ E, for some constant C

|Tx−Ty| ≤C |x−y| ,

for all x,y ∈ E, and for some N ∈ N,∣∣T Nx−T Ny∣∣≤ r |x−y| ,

for all x,y ∈ E where r ∈ (0,1). Then there exists a unique fixed point for T and it is stillthe limit of the sequence,

{T kx1

}for any choice of x1.

Proof: From Lemma 14.4.4 there exists a unique fixed point for T N denoted here as x.Therefore, T Nx= x. Now doing T to both sides,

T NTx= Tx.

By uniqueness, Tx= x because the above equation shows Tx is a fixed point of T N andthere is only one fixed point of T N . In fact, there is only one fixed point of T because afixed point of T is automatically a fixed point of T N .

It remains to show T kx1 → x, the unique fixed point of T N . If this does not happen,there exists ε > 0 and a subsequence, still denoted by T k such that∣∣∣T kx1−x

∣∣∣≥ ε

Now k = jkN+rk where rk ∈{0, · · · ,N−1} and jk is a positive integer with limk→∞ jk =∞.Then there exists a single r ∈ {0, · · · ,N−1} such that for infinitely many k,rk = r. Takinga further subsequence, still denoted by T k it follows∣∣T jkN+rx1−x

∣∣≥ ε (14.14)

However,T jkN+rx1 = T rT jkNx1→ T rx= x

and this contradicts 14.14. ■Now return to our system Ax= b. Recall it was a fixed point of T where

x= B−1Cx+B−1b≡ Tx

Then the fundamental theorem on convergence is the following. First note the following.

T 2x = B−1C(B−1Cx+b

)+B−1b

=(B−1C

)2+ e2 (b)

where e2 (b) does not depend on x. Similarly,

T nx=(B−1C

)n+ en (b) (14.15)

where en (b) does not depend on x. Thus

|T nx−T ny| ≤∣∣∣∣∣∣(B−1C

)n∣∣∣∣∣∣ |x−y| .