COMP-205 / Homework 2 / Problem #2
Stability of Solving a 2x2 Linear System of Equations using Cramer's Rule
Kenny Hoff
1/29/97
Simply put, the problem is very ill-conditioned and is neither forward or backwards stable. We will show this by means of a geometric argument.
Instead of thinking in terms of a linear system, just imagine this as finding the intersection point of two lines in the implicit form Ax+By+C=0. This is very similar to the point-normal form in that (A,B) is the normal to the line, C is basically the distance along this normal to the line, and (x,y) is a point on the line. Solving the system of two of these line equations for (x,y) results in the intersection point of the lines. If the det of the matrix formed by A and B equals zero then it is singular, the lines are parallel, the lines do not intersect, and the system is unsolvable. In this scenario, instability is quite easy to show.
First, the easiest to show is forward instability. This means that a slight perturbation in the inputs (A,B,C) results in a radical change in the intersection point. Geometrically, this means that if I move or rotate one of the lines only slightly, the intersection point will jump wildly. Imagine two lines that are exactly parallel and very close to each other. The lines do not intersect so their intersection point is considered "at infinity", but if we only rotate one of the lines a little, suddenly there can be an intersection point. We have gone from "infinite" to "quite close" with only a small perturbation in the inputs! This is VERY forward instable.
Now to show that it is backwards unstable we must show that a radical change in the inputs can result in the same intersection point. At first this seems almost surely in contradiction with the forward instability argument - not really. Previously, we showed that when we have a configuration of lines near the singular case (parallel lines), we can have a VERY different resulting intersection point from only a small movement in the lines. We are now showing that major changes in line orientations can result in the same intersection point. This was is also quite clear since there are surely an infinite pair of lines that intersect at a common point. Imagine the lines radiating out from this common point in a radial pattern. This would suggest that any amount of alteration in the inputs can result in the same output! One way to illustrate this using the equations is as follows:
If we are given the system of equations in the following form:
Ax=B A=[A1 B1] B=[C1]
[A2 B2] [C2]
where x is the intersection point that we are solving for.
If we keep x fixed, choose an arbitrary A, and always choose B as Ax. Then almost ANY choice of A will result in a system that has x as its intersection point. This amounts to nothing more than finding the entire set of lines that intersect at a common point.
To answer the question directly from the equations used in Cramer's Rule:
det(A) = A1*B2 - B1*A2
x = [ (B2*C1 - B1*C2) / det(A) ] [ (-A2*C1 + A1*C2) / det(A) ]
From this alone, we can see that when the lines are near parallel the det(A) is nearly zero and the system is nearly singular. When det(A) is near zero, there is a high potential of error in the form of "catastrophic cancellation" in the subtraction of two very similar values (A1*B2 is almost equal to B1*A2). The det(A) therefore has a high potential for error and is then divided into other values for the computation of x. The small value can have a dramatic effect on the resulting x (dividing a very small number into a larger number - possibly approaches infinity).
We can look at this result in yet another way. In forward instability, a slight change in the domain of a function results in a large change in the range. In backwards instability, a slight change in the range can come from a large change in the domain. What does this mean to us? Simply put, our domain is the set of line configurations (inputs of line equation coefficients) and the range of our system is the possible intersection points of the given lines. We have suggested that the system is forward unstable because a slight change in the configuration of the lines can result in a large difference in the intersection point, and that the system is backwards unstable since large variations in the given line configurations can have the exact same intersection point.