Even very small systems of linear equations can be hard to solve!
A variety of difficulties arise in solving some systems of linear algebraic equations. We will present several such difficulties here in the simplest possible form: two equations in two unknowns.
(To see how our solvers work on these systems, scroll down to the bottom.)
0. A typical system with no difficulties.
1*x + 1* y = 2
1*x – 1*Y = 0
This is the kind of situation one sees in High School Algebra classes. Easy to solve.
1. A variable may not actually be involved in the solution. For example,
1*x + 0*y = 1
2*x + 0*y = 2
In this case, y simply isn’t involved, and can’t be solved for. Solving for x is easy with either equation (x=1) but when you substitute x=1 into the other equation you just get 0 = 0, which is true, but not helpful. Of course, you can see that this could happen with a larger system of equation also. So, can this problem be solved? Yes: x=1, y=anything is a solution. Most solvers will automatically compute y=0, but some may crash.
2. One equation may not be usable. For example,
1*x + 1*y = 2
0*x + 0*y = 0
In this case the second equation is completely useless. On the other hand, any x and y we pick would satisfy it! If we ignore the useless equation then a solution is easy: x=1 and y=1, for example. Such systems of equations present problems to some solvers, but more sophisticated ones, like autoreg(), return the so-called “pseudoinverse” in such cases, which is x=1, y=1.
3. Sometimes a system of equations is simply under-determined. This situation is much like the situation just above, but is actually much simpler to diagnose and solve. In such cases there is not enough information present to compute a particular solution. For example: consider if we just have ONE equation but TWO unknowns:
1x + 2y = 2
We can see that x=1, y=0.5 works fine as a solution. But so does x=0, y=1, and x=2, y=0, or x=-1, y=1.5, etc. We have to add some rule for picking an appropriate solution among all the possible solutions. The usual way to do this is to pick the solution with the smallest sum of squares. That is, the smallest possible value of x*x + y*y. In this case that solution turns out to be x=0.4, y = 0.8.
4. The equations may be dependent. That is, one or more of the equations may be combinations of the other equations. For example,
1*x + 1*y = 2
2*x + 2*y = 4
In this case the second equation is just 2 times the first. When you attempt to eliminate the x term in the second equation, by subtracting the first equation from it twice, look what you get:
1*x + 1*y = 2
0*x + 0*y = 0
This last equation is, again, true, but useless. (Like case 2 above.) As above, sophisticated solvers will return the pseudoinverse solution: x=1, y=1.
5. The equations may not be consistent. In the case just above, the equations were dependent, but at least agreed. What if the equations are dependent again, but also disagree? For example,
1*x + 1*y = 2
2*x + 2*y = 6
When we subtract the first equation times 2 from the second, we get
1*x + 1*y = 2
0*x + 0*y = 2
and the second equation cannot be satisfied. This system cannot be solved exactly. Equation 1 by itself would result in x=1,y=1, while equation 2 by itself would result in x=1.5, y=1.5. However, an approximate solution can be computed by finding the solution which makes the right hand side results come as close as possible to the given 2 and 6. By “close”, we mean again, that the sum of the square of the errors has the smallest possible sum of squares. That answer is x=1.2625, y=1.2625, and plugging those values in the equations, we get
1*x + 1*y = 2.5250
2*x + 2*y =5.0500
6. The equations may be independent, and consistent, but result in an unreasonable answer. Often this is due to what we call an ill-conditioned system of equations. For example, consider these two:
1*x + 1*y = 2
1*x + 1.01*y = 3
When we solve this by the usual elimination and substitution method, we get x= -98 and y=100. This is a surprising answer since by looking at each equation alone we would have guessed that the solution values would be near 1 (*). And a negative answer such as -98 may be completely unacceptable. For example, if x and y represent amounts of physical entities such as light, then a negative number is plain wrong. An approximate solution can be computed by “regularization” of the problem. This is the kind of problem that autoreg() was designed to solve. It also solves all the other cases listed here, though you should always check the result when giving autoreg() a hard problem, to assure that the answer is acceptable for your purposes.
(*) Looking closer, one can see that an increase of 0.01*y in the second equation resulted in a change in the right hand side of 1.0…. implying that y must be about 100.)
7. Sometimes a system of equations is simply over-determined. That is, there are more equations than need to determine a solution, and we have no reason to eliminate any particular equation. We would like a solution that somehow “comes closest” to solving all of the equations. For example,
1*x + 2 *y = 15
2*x + 2*y = 16
-1*x + 1*y = 6
The solution to this system is easy: x=1, y=7. And, we are in luck: that solution satisfies all three equations exactly. But that is not the typical case. More typically, we would have something like
1*x + 2 *y = 15.1
2*x + 2*y = 15.9
-1*x + 1*y = 6.5
And if we try x=1, y=7 in this set of equation, we will not quite solve the equations. Instead we will get 0.1 too little for the first equation, 0.1 too much for the first equation, and 0.5 too much for the first equation. We can do better than that. In particular, we can compute a solution which minimizes the sum of the square of these errors. Such solutions are called “least squares” solutions. Solvers like autoreg() automatically give this “least squares” result in this very common situation.
8. Sometimes a system of equation produces negative answers, when that is unacceptable. This is often due to poor data on the right hand side, or may be due to trying to solve for a larger number of values that the data supports. (Such as solving a 5 row, 20 column underdetermined problem, when 5 rows by 5 columns might be better.)
1*x + 1*y = 0.9
1*x - 1*y = 1.1
The answer to this system is easily computed to be x=1, y= -0.1. If we demand that the solution be non-negative, as autregnn() allows, then the computes answer will be x=1, y=0.
When we have larger systems of equations we may have two or more of the above difficulties in the one set of equations. For example, it would not be surprising for a set of equations to be underdetermined (case 6), and not independent (case 3) and ill-conditioned (case 5). That’s what makes developing solvers for these interesting.
---------------------
How ARLS Works on
These Small Systems of Equations
1. A
typical problem without difficulties
1*x +
1*y = 2
1*x - 1*y = 0
Our
programs return x=1, y=1.
2. Missing
Variable.
1*x +
0*y = 1
2*x +
0*y = 2
Our
programs return x=1, y=0. This is the minimum norm solution.
3. Effectively
missing equation.
1*x +
1*y = 2
0*x +
0*y = 0
Our
programs return x=1, y=1. This is the minimum norm solution.
4. Dependent
but consistent equations.
1*x +
1*y = 2
2*x +
2*y = 4
Our
programs return x=1, y=1. This is the minimum norm solution.
5. Dependent
and inconsistent equations.
1*x +
1*y = 2
2*x +
2*y = 6
Our
programs recognize the problem as ill-conditioned, apply an
automatic regularization method and give x=1.2625, y=1.2625. This is reasonable
behavior.
6. Independent,
consistent, but unreasonable equations.
1*x +
1*y = 2
1*x +
1.01*y = 3
Our programs recognize the problem as
ill-conditioned, apply an automatic regularization method and return x=1.1165,
y=1.1334.
7. An
under-determined system.
1x + 2y
= 2
Our programs return the minimum-norm
solution, x=0.4, y=0.8. This is actually an
easy problem.
8. An
over-determined system
1*x + 2
*y = 15.1
2*x +
2*y = 15.9
-1*x +
1*y = 6.5
Our
programs return x=0.7276. y=7.2069. When you substitute these values
into the equations, the resulting right side values
are: 15.141, 15.869, and 6.479, which is excellent!