Re: Some more results Message #17 Posted by Rodger Rosenbaum on 13 Jan 2006, 7:26 a.m., in response to message #16 by Palmer O. Hanson, Jr.
Palmer said:
"The TI-59 and TI-95 are thirteen digit machines. The TI-59 exhibits the famous anomaly in which multiplication is not always commutative, and in addition does not use an add/subtract guard digit. In the TI-95 multiplication is commutative and there is a guard digit. Solutions for Valentin' original problem from the ML-02 program in the Master Library module of the TI-59 and from the matrix routines in the Mathematics module for the TI-95 follow:
TI-59 TI-95
1.740824864135 0.6835858242542
0.9999066058071 1.000039889642
1.660533625121 0.7178790660364
1.664307494855 0.7162672061226
1.000458374646 0.9998042233199
0.3357027223239 1.283728430019
-0.3898635477583 1.593625498008
Both solutions are substantially degraded relative to those from the Model 100 and TI-85. For both machines the product of matrix A and the solution vector X yields values which are within 3e-11 of the values in matrix B.
How Many Exact Answers to Valentin's original problem from the HP-28S (or from any other machine)
Multiply the A matrix by a vector of all ones and it is not surprising that the result will be exactly the B matrix. Multiply the A matrix by a vector which includes the solution from the TI-95 rounded to twelve digits, Voila! The result is exactly the B matrix. I'm suggesting that on any machine there are probably an infinite number of vectors which can be multiplied by the A matrix and yield the exact B matrix."
Valentin's original problem has, as he says, a unique solution. This is when doing continuous, traditional arithmetic. The discretized arithmetic of calculators spawns the spurious solutions of which you have given an example. Another is:
x1 = .220440311016
x2 = 1.00009827737
x3 = .304929663701
x4 = .300958473026
x5 = .999517658758
x6 = 1.6990307756
x7 = 2.46253405849
Notice that this one is even further from [1 1 1 1 1 1 1]. I was able to generate lots of them.
The product of A times the X you gave, and the one I gave, has non-zero digits out to the 15th place, and the loss of these in the rounding process makes it appear that the X is a solution, but only in the discretized arithmetic of the calculator; it's not a true solution.
However, I doubt that there are an infinite number of these false solutions. The HP28, for example, has a 12 digit mantissa; this means that it can represent all possible 12 digit integers, of which there are 10^12 positive and (10^12)-1 negative. The HP28 has 999 possible exponents. Therefore a total of about 2*999*10^12 numbers can be represented on it, somewhat short of infinity. :-)
But, back to the original purpose I had when I started this thread. I noticed that a slightly different perturbation of the column matrix has even greater effect. Change the third element of the column matrix in Valentin's original problem from 45 to 45.1--now the exact solution is:
x1 = -2128901625
x2 = 268387
x3 = -1898169427
x4 = -1909014362
x5 = -1317226
x6 = 1908985003
x7 = 3994038147
This is a tremendous change in the solution for an apparently insignificant change in one element.
Try something I described in an earlier post; add .1 to the {3,7} element of the A matrix, and subtract .1 from the {7,7} element. This tiny change reduces the condition number of the A matrix from about 3E12 to about 400, and using this slightly perturbed A matrix with the perturbed column matrix mentioned just above gives a HP48G solution:
x1 = 1.20999247798
x2 = 1.01325966115
x3 = 1.26616078717
x4 = 1.29157926088
x5 = .997263593179
x6 = .690061410742
x7 = .499897531935
This isn't as close to [1 1 1 1 1 1 1] as we would like, but given what the solution was with just the third element in the column matrix perturbed and using the original A matrix, this inprovement is an astounding result considering that only two tiny perturbations were made to the A matrix.
My purpose here is to show that with proper techniques we can find reasonable solutions to very ill-conditioned systems. Systems as badly conditioned as Valentin's example are unlikely to occur in practice; they must be artificially constructed. But, if we can handle them, then we can certainly handle the ones we encounter in real life problems.
Palmer, it would be good if you tried solving the system on your various calculators, consisting of the column matrix perturbed in the third element, and the {3,7} and {7,7} elements of the A matrix perturbed as I described. I think you will find that you don't get wildly varying results with these changes. For example, on my HP48S, which uses the same matrix routines as the HP28, I get about 9 or 10 digit agreement with the solution posted above, whether I use the divide key or invert the A matrix and multiply times the column matrix.
We've seen repeatedly how ill-conditioned systems are not correctly solved (exactly), and the more digits your calculator has, the better the results. This is to be expected. But now we should move on to new pastures and learn how to deal with these ill-conditioned systems, even with calculators that don't do arithmetic with lots of digits.
My favorite way to handle them involves the use of the singular value decomposition. Routines written in Fortran for the SVD can be found at:
http://www.netlib.org/lapack/single/
These could be most easily implemented on a machine that has Basic rather than keystroke programming. Or, you could just get an HP48G which has the SVD and lots more built-in. I find the HP48G very handy for experimenting with advanced matrix algebra.
The book, "Numerical Recipes", has a good section on the use of the SVD for dealing with ill-conditioned systems. I hope I can stir up some interest in this.
|