Page 41 - Matrix Analysis & Applied Linear Algebra

1.6 Ill-Conditioned Systems 33
1.6 ILL-CONDITIONED SYSTEMS

Gaussian elimination with partial pivoting on a properly scaled system is perhaps
the most fundamental algorithm in the practical use of linear algebra. However,
it is not a universal algorithm nor can it be used blindly. The purpose of this
section is to make the point that when solving a linear system some discretion
must always be exercised because there are some systems that are so inordinately
sensitive to small perturbations that no numerical technique can be used with
confidence.
Example 1.6.1
Consider the system
.835x + .667y = .168,
.333x + .266y = .067,

for which the exact solution is

x = 1 and y = −1.
ˆ
If b 2 = .067 is only slightly perturbed to become b 2 = .066, then the exact
solution changes dramatically to become

ˆ x = −666 and ˆ y = 834.

This is an example of a system whose solution is extremely sensitive to
a small perturbation. This sensitivity is intrinsic to the system itself and is
not a result of any numerical procedure. Therefore, you cannot expect some
“numerical trick” to remove the sensitivity. If the exact solution is sensitive to
small perturbations, then any computed solution cannot be less so, regardless of
the algorithm used.

Ill-Conditioned Linear Systems
A system of linear equations is said to be ill-conditioned when
some small perturbation in the system can produce relatively large
changes in the exact solution. Otherwise, the system is said to be well-
conditioned.

It is easy to visualize what causes a 2 × 2 system to be ill-conditioned.
Geometrically, two equations in two unknowns represent two straight lines, and
the point of intersection is the solution for the system. An ill-conditioned system
represents two straight lines that are almost parallel.