psie
- 315
- 40
- TL;DR Summary
- I'm reading Linear Algebra by Friedberg et al. They have a section on conditioning and the Rayleigh quotient. At the end, there's an exercise with a couple of true or false statement, and I'm stuck with two of them, since the answer at the back of the book seems contradictory to me.
Conditioning doesn't refer to hair conditioners in this case, but what happens to the solution of a system of linear equations ##Ax=b## when we change say the vector ##b## slightly to ##b'##. If the relative change in ##b##, that is ##\frac{\|b-b'\|}{\|b\|}##, is close to the relative change in ##x##, i.e. ##\frac{\|x-x'\|}{\|x\|}##, the system is called well-conditioned; otherwise it is ill-conditioned. If ##A## is invertible and ##b\neq 0##, then we have $$\frac1{\operatorname{cond}(A)}\frac{\|b-b'\|}{\|b\|}\leq \frac{\|x-x'\|}{\|x\|}\leq \operatorname{cond}(A)\frac{\|b-b'\|}{\|b\|},$$where ##\operatorname{cond}(A)=\|A\| \|A^{-1}\|## is the condition number of ##A##. This number is ##\geq 1## and depends on the matrix norm (the preceding inequality, however, holds for any norm satisfying ##\|Ax\|\leq\|A\| \|x\|## I think). I know at least for the Euclidean norm, that ##\|A\|## equals the square root of the largest eigenvalue of ##A^\ast A##, where ##A^\ast## is the conjugate transpose. I've heard that computing ##\operatorname{cond}(A)## is a tricky business in general.
Anyway, now I'm faced with the following two statements:
My book says (a) is false. I agree, since if it is well-conditioned, the relative change in ##b## and ##x## has ratio near ##1## or at least ##1## plus some remainder that isn't very large in absolute value (my book gives a somewhat loose definition of well- and ill-conditioned systems, so I'm not very familiar what counts as ill-conditioned in terms of numbers). By the displayed inequality above, if we divide ##\frac{\|b-b'\|}{\|b\|}##, then we obtain $$\frac1{\operatorname{cond}(A)}\leq 1+h \leq \operatorname{cond}(A)$$where ##|h|\geq0## is small. I don't see that the preceding inequality implies that the condition number has to be small, so I conclude the statement is false.
Now notice, I think (b) is just the contrapositive of (a). However, my book claims it is true. It has been wrong before, but here I'm not so sure anymore.
Anyway, now I'm faced with the following two statements:
(a) If ##Ax=b## is well-conditioned, then ##\operatorname{cond}(A)## is small.
(b) If ##\operatorname{cond}(A)## is large, then ##Ax=b## is ill-conditioned.
My book says (a) is false. I agree, since if it is well-conditioned, the relative change in ##b## and ##x## has ratio near ##1## or at least ##1## plus some remainder that isn't very large in absolute value (my book gives a somewhat loose definition of well- and ill-conditioned systems, so I'm not very familiar what counts as ill-conditioned in terms of numbers). By the displayed inequality above, if we divide ##\frac{\|b-b'\|}{\|b\|}##, then we obtain $$\frac1{\operatorname{cond}(A)}\leq 1+h \leq \operatorname{cond}(A)$$where ##|h|\geq0## is small. I don't see that the preceding inequality implies that the condition number has to be small, so I conclude the statement is false.
Now notice, I think (b) is just the contrapositive of (a). However, my book claims it is true. It has been wrong before, but here I'm not so sure anymore.