4 ms·

I thought the OP would reference the fact that errors in solving a linear system don't combine and magnify to produce unusable results beyond say a 10x10 system

by mturmon 15y ago

I thought the OP would reference the fact that errors in solving a linear system don't combine and magnify to produce unusable results beyond say a 10x10 system. At the outset of numerical linear algebra, say in the 1940s [until 1948], it was not known whether errors would blow up or not. [best bound was 4^n where n is matrix order] Turned out they did not (if you do things remotely right) but even von Neumann [in a 1947 paper, with others] was surprised that large (say 20x20, at that time) linear systems could be solved accurately. [edits in braces: This history, and more, is in www.maths.manchester.ac.uk/~higham/talks/twge96.ps.gz ; Higham wrote probably the best and most comprehensive up-to-date book on the accuracy of numerical linear algebra.]

eru 15y ago
Don't you still have to look out for ill-conditioned matrices?
- InclinedPlane 15y ago
  If you use inverses then you can run into such problems, which is a good reason not to use them.
- mturmon 15y ago
  Yes, in some sense (see below) you do care about A. But back then, everyone was worried even about well-conditioned systems. As of the mid 1940s the best error bound on cumulative roundoff error was 4^n where n is matrix order. That 4^n would be a multiplier on top of condition number (which at the time had not been formalized, it was Turing who did that). Anyway, the dependence on matrix size turned out to be order n^2, and in practice more like O(n). * * * Also, the bounds on solving A x = b for x, knowing b and A, work differently than solving for the inverse of A. Sometimes for a given A and b, you can compute x above quite accurately, but you can't compute inv(A) accurately and multiply by b to get x. It depends on the how the "difficult directions" in A interact with b. This is one reason numerical analysts always ask, "Do you really need to invert A?" Because of this, the actual condition number of A (i.e., the norm of A times that of inv(A)) does not enter into the bounds on solving A x = b. The bounds depend on a different norm. In fact, there are several forms of the error bound -- known as backward and forward errors -- depending on what you need. * * * Incidentally, this is the kind of stuff that's covered in Golub and Van Loan, or in Trefethen and Bao, but not in a standard Abstract Linear Algebra book. For instance, Strang's book spends only one chapter on numerical linear algebra.
  - eru 15y ago
    Thanks. Incidentally, this is the kind of stuff that I should still remember from university.

by mturmon 15y ago

eru 15y ago

Don't you still have to look out for ill-conditioned matrices?

InclinedPlane 15y ago
If you use inverses then you can run into such problems, which is a good reason not to use them.
mturmon 15y ago
Yes, in some sense (see below) you do care about A. But back then, everyone was worried even about well-conditioned systems. As of the mid 1940s the best error bound on cumulative roundoff error was 4^n where n is matrix order. That 4^n would be a multiplier on top of condition number (which at the time had not been formalized, it was Turing who did that). Anyway, the dependence on matrix size turned out to be order n^2, and in practice more like O(n). * * * Also, the bounds on solving A x = b for x, knowing b and A, work differently than solving for the inverse of A. Sometimes for a given A and b, you can compute x above quite accurately, but you can't compute inv(A) accurately and multiply by b to get x. It depends on the how the "difficult directions" in A interact with b. This is one reason numerical analysts always ask, "Do you really need to invert A?" Because of this, the actual condition number of A (i.e., the norm of A times that of inv(A)) does not enter into the bounds on solving A x = b. The bounds depend on a different norm. In fact, there are several forms of the error bound -- known as backward and forward errors -- depending on what you need. * * * Incidentally, this is the kind of stuff that's covered in Golub and Van Loan, or in Trefethen and Bao, but not in a standard Abstract Linear Algebra book. For instance, Strang's book spends only one chapter on numerical linear algebra.
- eru 15y ago
  Thanks. Incidentally, this is the kind of stuff that I should still remember from university.