1.7 Ill-conditioned Algebraic Systems and Function Approximation

1.7.1. Introduction.

The Gaussian elimination algorithm can have a large number of operations. If one goes to the trouble of counting operations for the forward sweep, you will discover that there are order n³/3 operations. So, if the number of unknowns doubles the number of operations increases by a factor of 8. Or, if n = 200, then there are approximately 8/3 million operations! Certainly, one might begin to worry about the accumulation of roundoff error.

Some problems are very sensitive to small changes in data. That is, for small changes in data one will observe large change in the solution. The changes in the data could be either due to approximate empirical data or due to the use of floating point numbers approximation of real numbers. A simple illustration is depicted in the figure below where two lines are nearly parallel. If the intercepts with the vertical axis vary just a little, then the intersection will vary a great deal. Hence, the solution of the corresponding 2D system will vary a great deal.

Figure: Ill-conditioned System

Return to Section TOC
Go to Next Subsection