342 CHAPTER 14. NUMERICAL SOLUTIONS OF LINEAR SYSTEMSProposition 14.4.3 Suppose A is invertible, b 4 0, Ax = b, and Ax, = b, where|A—Ai|| <1/||A™"|x; —x 1 A,—A b—bIIx! (1—||A~! (Ai —A)]||) |All |bProof: It follows from the assumptions thatAx — Ajx+A ,x—A x; =b—by.HenceA, (x—x1) = (A —A)x+b—by.Now A; = (A+ (A; —A)) and so by the above lemma, A;' exists and so(x—x,) =A,' (A; —A)x+A,'(b—b1)=(A+(A1—A)) (Ay —A)x+(A+(A1—A)) | (b—bi),By the estimate in Lemma 14.4.2,ja“_ < A,—A b—by,||)-I|x xi || < 1—||A-! (Ay —A)|| (|| 1 Il IxI] + || il)Dividing by ||x||,IIx—xi | A" ( |b —bil|< _ \|Ay —A]| + ——— (14.12)| 1—||A~' (Ai —A)| Ix|Now b = Ax =A (A™'b) and so ||b|| < ||A|| ||A~'b]] and solIx|| = ||A~"D|| > ||bl| / A].Therefore, from 14.12,IIx—xil] A" (4 Ai ~All NAT a)IIx] ~~ 1 |[A~* (Ar —A)|| I|Al| |b]a7 (al . bil) 2~ 1=||AT(Ar—A)|| (AI |b]This shows that the number, ||A~'|| ||A|| , controls how sensitive the relative change inthe solution of Ax = b is to small changes in A and b. This number is called the conditionnumber. It is bad when it is large because a small relative change in b, for example, couldyield a large relative change in x.