Gaussian Elimination: When Is Scaling Beneficial?
For the linear system Ax = b, the ordered pair (D, F) of nonsingular diagonal matrices determine a scaling of the system through the two equations D(AF) y = Db, y = F-1x. When scaling is implemented along with partial pivoting (PP) to solve Ax = b by Gaussian elimination (GE), it is well known that certain ordered pairs (D, F) produce better computed solutions than those obtained in the absence of scaling, while others produce worse solutions. The two most common explanations of this fact are (1) (D, F) modifies (magnifies or reduces) the classical condition number of A, and (2) (D, F) modifies the magnitudes of the elements of A. In case (2), if a scaling yields entries of approximately the same magnitude, it is called an equilibration. Here, the underlying hyperplane geometry of both the sweepout phase and the back-substitution phase of GE is used to achieve a new level of understanding. We present what we believe to be a better explanation of how scaling or equilibration influences PP in the selection of pivot equations, a process critical to both phases of GE.
Poole, George; and Neal, Larry. 1992. Gaussian Elimination: When Is Scaling Beneficial?. Linear Algebra and Its Applications. Vol.162-164(C). 309-324. https://doi.org/10.1016/0024-3795(92)90382-K ISSN: 0024-3795