Modification methods for inverting matrices and solving systems of linear algebraic equations
Author:
D. Goldfarb
Journal:
Math. Comp. 26 (1972), 829852
MSC:
Primary 65F10; Secondary 65F30
MathSciNet review:
0317527
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Modification methods for inverting matrices and solving systems of linear algebraic equations are developed from Broyden's rankone modification formula. Several algorithms are presented that take as few, or nearly as few, arithmetic operations as Gaussian elimination and are well suited for the handling of data. The effect of rounding errors is discussed briefly. Some of these algorithms are essentially equivalent to, or ``compact'' forms of, such known methods as Sherman and Morrison's modification method, Hestenes' biorthogonalization method, GaussJordan elimination, Aitken's belowtheline elimination method, Purcell's vector method, and its equivalent, Pietrzykowski's projection method, and the bordering method. These methods are thus shown to be directly related to each other. Iterative methods and methods for inverting symmetric matrices are also given, as are the results of some computational experiments.
 [1]
A. C. Aitken, ``Studies in practical mathematics. I. The evaluation with application of a certain triple product matrix,'' Proc. Roy Soc. Edinburgh Sect. A, v. 57, 1936/37, pp. 172181.
 [2]
M.
S. Bartlett, An inverse matrix adjustment arising in discriminant
analysis, Ann. Math. Statistics 22 (1951),
107–111. MR 0040068
(12,639c)
 [3]
E.
Bodewig, Matrix calculus, NorthHolland Publishing Company,
Amsterdam, 1956. MR 0080363
(18,235e)
 [4]
C.
G. Broyden, A class of methods for solving
nonlinear simultaneous equations, Math.
Comp. 19 (1965),
577–593. MR 0198670
(33 #6825), http://dx.doi.org/10.1090/S00255718196501986706
 [5]
P. D. Crout, ``A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients,'' Trans. Amer. Inst. Elect. Engrs., v. 60, 1941, pp. 12351240.
 [6]
J. E. Dennis, Jr., On the Convergence of Broyden's Method for Nonlinear Systems of Equations, Technical Report #6948, Dept. of Comput. Sci., Cornell University, Ithaca, N.Y., 1969.
 [7]
M. H. Doolittle, Method Employed in the Solution of Normal Equations and the Adjustment of Triangulation, U.S. Coast Guard and Geodetic Survey Report, 1878, pp. 115120.
 [8]
W.
J. Duncan, Some devices for the solution of large sets of
simultaneous linear equations, Philos. Mag. (7) 35
(1944), 660–670. MR 0012914
(7,84b)
 [9]
P. S. Dwyer, Linear Computations, Wiley, New York, 1951. MR 13, 283.
 [10]
A. P. Eršov(Ershov), ``On a method for inverting matrices,'' Dokl. Akad. Nauk SSSR, v. 100, 1955, pp. 209211. (Russian) MR 16, 1082.
 [11]
D.
K. Faddeev and V.
N. Faddeeva, Computational methods of linear algebra,
Translated by Robert C. Williams, W. H. Freeman and Co., San
FranciscoLondon, 1963. MR 0158519
(28 #1742)
 [12]
L.
Fox, An introduction to numerical linear algebra, Monographs
on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 0164436
(29 #1733)
 [13]
L.
Fox, H.
D. Huskey, and J.
H. Wilkinson, Notes on the solution of algebraic linear
simultaneous equations, Quart. J. Mech. Appl. Math. 1
(1948), 149–173. MR 0026421
(10,152i)
 [14]
C. F. Gauss, ``Supplementum theoriae combinationis observationum erroribus minimis obnoxiae,'' Werke. Band IV, Gottingen, 1873, pp. 5593.
 [15]
D.
Goldfarb, Modification methods for inverting
matrices and solving systems of linear algebraic equations, Math. Comp. 26 (1972), 829–852. MR 0317527
(47 #6074), http://dx.doi.org/10.1090/S00255718197203175274
 [16]
J.
Greenstadt, Variations on variablemetric methods.
(With discussion), Math. Comp. 24 (1970), 1–22. MR 0258248
(41 #2895), http://dx.doi.org/10.1090/S00255718197002582484
 [17]
Magnus
R. Hestenes, Iterative computational methods, Comm. Pure Appl.
Math. 8 (1955), 85–95. MR 0068313
(16,863b)
 [18]
Magnus
R. Hestenes, Inversion of matrices by biorthogonalization and
related results, J. Soc. Indust. Appl. Math. 6
(1958), 51–90. MR 0092215
(19,1080d)
 [19]
Harold
Hotelling, Some new methods in matrix calculation, Ann. Math.
Statistics 14 (1943), 1–34. MR 0007851
(4,202g)
 [20]
Alston
S. Householder, The theory of matrices in numerical analysis,
Blaisdell Publishing Co. Ginn and Co. New YorkTorontoLondon, 1964. MR 0175290
(30 #5475)
 [21]
M. A. Jenkins, The Solution of Linear Systems of Equations and Linear Least Squares Problems in APL, IBMNew York Scientific Center, Technical Report #3202989, 1970.
 [22]
V.
V. Kljuev and N.
I. KokovkinŠčerbak, On the minimization of the
number of arithmetic operations for solving linear algebraic systems of
equations, Ž. Vyčisl. Mat. i Mat. Fiz.
5 (1965), 21–33 (Russian). MR 0172453
(30 #2672)
 [23]
G. Kron, Diakoptics, Macdonald, London, 1963.
 [24]
J.
Morris, An escalator process for the solution of linear
simultaneous equations, Philos. Mag. (7) 37 (1946),
106–120. MR 0018423
(8,287a)
 [25]
Joseph
Morris, The Escalator Method in Engineering Vibration
Problems, John Wiley & Sons, Inc., New York, N. Y., 1947. MR 0023613
(9,382d)
 [26]
T. Pietrzykowski, Projection Method, Zakladu Aparatów Matematycznych Polskiej Akad. Nauk. Praca A8 (as reported in Householder [20]).
 [27]
M.
J. D. Powell, A theorem on rank one modifications to a matrix and
its inverse, Comput. J. 12 (1969/1970),
288–290. MR 0245190
(39 #6502)
 [28]
M.
J. D. Powell, A new algorithm for unconstrained optimization,
Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis.,
1970) Academic Press, New York, 1970, pp. 31–65. MR 0272162
(42 #7043)
 [29]
Everett
W. Purcell, The vector method of solving simultaneous linear
equations, J. Math. Physics 32 (1953), 180–183.
MR
0059065 (15,471h)
 [30]
Jack
Sherman, Computations relating to inverse matrices,
Simultaneous linear equations and the determination of eigenvalues,
National Bureau of Standards Applied Mathematics Series, No. 29, U. S.
Government Printing Office, Washington, D. C., 1953,
pp. 123–124. MR 0057026
(15,164f)
 [31]
J. Sherman & W. J. Morrison, ``Adjustment of an inverse matrix corresponding to changes in a given column or row of the original matrix,'' Ann. Math. Statist., v. 20, 1949, p. 621.
 [32]
Jack
Sherman and Winifred
J. Morrison, Adjustment of an inverse matrix corresponding to a
change in one element of a given matrix, Ann. Math. Statistics
21 (1950), 124–127. MR 0035118
(11,693d)
 [33]
Volker
Strassen, Gaussian elimination is not optimal, Numer. Math.
13 (1969), 354–356. MR 0248973
(40 #2223)
 [34]
Herbert
S. Wilf, Matrix inversion by the annihilation of rank, J. Soc.
Indust. Appl. Math. 7 (1959), 149–151. MR 0107968
(21 #6689)
 [35]
Herbert
S. Wilf, Matrix inversion by the method of rank annihilation,
Mathematical methods for digital computers, Wiley, New York, 1960,
pp. 73–77. MR 0117911
(22 #8685)
 [36]
J.
H. Wilkinson, Rounding errors in algebraic processes,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
(28 #4661)
 [37]
Max
A. Woodbury, Inverting modified matrices, Statistical Research
Group, Memo. Rep. no. 42, Princeton University, Princeton, N. J., 1950. MR 0038136
(12,361d)
 [38]
G. Zielke, ``Inversion of modified symmetric matrices,'' J. Assoc. Comput. Mach., v. 15, 1968, pp. 402408.
 [1]
 A. C. Aitken, ``Studies in practical mathematics. I. The evaluation with application of a certain triple product matrix,'' Proc. Roy Soc. Edinburgh Sect. A, v. 57, 1936/37, pp. 172181.
 [2]
 M. S. Bartlett, ``An inverse matrix adjustment arising in discriminant analysis,'' Ann. Math. Statist., v. 22, 1951, pp. 107111. MR 12, 639. MR 0040068 (12:639c)
 [3]
 E. Bodewig, Matrix Calculus, NorthHolland, Amsterdam, 1956. MR 18, 235. MR 0080363 (18:235e)
 [4]
 C. G. Broyden, ``A class of methods for solving nonlinear simultaneous equations,'' Math. Comp., v. 19, 1965, pp. 577593. MR 33 #6825. MR 0198670 (33:6825)
 [5]
 P. D. Crout, ``A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients,'' Trans. Amer. Inst. Elect. Engrs., v. 60, 1941, pp. 12351240.
 [6]
 J. E. Dennis, Jr., On the Convergence of Broyden's Method for Nonlinear Systems of Equations, Technical Report #6948, Dept. of Comput. Sci., Cornell University, Ithaca, N.Y., 1969.
 [7]
 M. H. Doolittle, Method Employed in the Solution of Normal Equations and the Adjustment of Triangulation, U.S. Coast Guard and Geodetic Survey Report, 1878, pp. 115120.
 [8]
 W. J. Duncan, ``Some devices for the solution of large sets of simultaneous linear equations,'' Philos. Mag., (7), v. 35, 1944, pp. 660670. MR 7, 84. MR 0012914 (7:84b)
 [9]
 P. S. Dwyer, Linear Computations, Wiley, New York, 1951. MR 13, 283.
 [10]
 A. P. Eršov(Ershov), ``On a method for inverting matrices,'' Dokl. Akad. Nauk SSSR, v. 100, 1955, pp. 209211. (Russian) MR 16, 1082.
 [11]
 D. K. Faddeev & V. N. Faddeeva, Computational Methods of Linear Algebra, Fizmatgiz, Moscow, 1960; English transl., Freeman, San Francisco, Calif., 1963. MR 28 #1742. MR 0158519 (28:1742)
 [12]
 L. Fox, An Introduction to Numerical Linear Algebra, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1964. MR 29 #1733. MR 0164436 (29:1733)
 [13]
 L. Fox, H. D. Huskey & J. H. Wilkinson, ``Notes on the solution of algebraic linear simultaneous equations,'' Quart. J. Mech. Appl. Math., v. 1, 1948, pp. 149173. MR 10, 152. MR 0026421 (10:152i)
 [14]
 C. F. Gauss, ``Supplementum theoriae combinationis observationum erroribus minimis obnoxiae,'' Werke. Band IV, Gottingen, 1873, pp. 5593.
 [15]
 D. Goldfarb, Modification Methods for Inverting Matrices and Solving Systems of Linear Algebraic Equations, IBMPhiladelphia Scientific Center, Technical Report #3202998, 1971. MR 0317527 (47:6074)
 [16]
 J. Greenstadt, ``Variations on variablemetric methods (with discussion),'' Math. Comp., v. 24, 1970, pp. 122. MR 41 #2895. MR 0258248 (41:2895)
 [17]
 M. R. Hestenes, ``Iterative computational methods,'' Comm. Pure Appl. Math., v. 8, 1955, pp. 8595. MR 16, 863. MR 0068313 (16:863b)
 [18]
 M. R. Hestenes, ``Inversion of matrices by biorthogonalization and related results,'' J. Soc. Indust. Appl. Math., v. 6, 1958, pp. 5190. MR 19, 1080. MR 0092215 (19:1080d)
 [19]
 H. Hotelling, ``Some new methods in matrix calculation,'' Ann. Math. Statist., v. 14, 1943, pp. 134. MR 4, 202. MR 0007851 (4:202g)
 [20]
 A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, Waltham, Mass., 1964. MR 30 #5475. MR 0175290 (30:5475)
 [21]
 M. A. Jenkins, The Solution of Linear Systems of Equations and Linear Least Squares Problems in APL, IBMNew York Scientific Center, Technical Report #3202989, 1970.
 [22]
 V. V. Kljuev & N. I. KokovkinŠčerbak, ``On the minimization of the number of arithmetic operations for solving linear algebraic systems of equations,'' Ž. Vyčisl. Mat. i Mat. Fiz., v. 5, 1965, pp. 2233 = U.S.S.R. Comput. Math. and Math. Phys., v. 5, 1965, pp. 2543. MR 30 #2672. MR 0172453 (30:2672)
 [23]
 G. Kron, Diakoptics, Macdonald, London, 1963.
 [24]
 J. Morris, ``An escalator process for the solution of linear simultaneous equations,'' Philos. Mag., (7), v. 37, 1946, pp. 106120. MR 8, 287. MR 0018423 (8:287a)
 [25]
 J. Morris, The Escalator Method in Engineering Vibration Problems, Wiley, New York, 1947. MR 9, 382. MR 0023613 (9:382d)
 [26]
 T. Pietrzykowski, Projection Method, Zakladu Aparatów Matematycznych Polskiej Akad. Nauk. Praca A8 (as reported in Householder [20]).
 [27]
 M. J. D. Powell, ``A theorem on rank one modifications to a matrix and its inverse,'' Comput. J., v. 12, 1969/70, pp. 288290. MR 39 #6502. MR 0245190 (39:6502)
 [28]
 M. J. D. Powell, ``A new algorithm for unconstrained optimization,'' in Nonlinear Programming, J. B. Rosen, O. L. Mangasarian & K. Ritter (Editors), Academic Press, New York, 1970, pp. 3165. MR 0272162 (42:7043)
 [29]
 E. W. Purcell, ``The vector method of solving simultaneous linear equations,'' J. Mathematical Phys., v. 32, 1953, pp. 180183. MR 15, 471. MR 0059065 (15:471h)
 [30]
 J. Sherman, Computations Relating to Inverse Matrices. Simultaneous Linear Equations and the Determination of Eigenvalues, Nat. Bur. Standards Appl. Math. Ser., no. 29, U. S. Government Printing Office, Washington, D.C., 1953, pp. 123124. MR 15, 164. MR 0057026 (15:164f)
 [31]
 J. Sherman & W. J. Morrison, ``Adjustment of an inverse matrix corresponding to changes in a given column or row of the original matrix,'' Ann. Math. Statist., v. 20, 1949, p. 621.
 [32]
 J. Sherman & W. J. Morrison, ``Adjustment of an inverse matrix corresponding to a change in one element of a given matrix,'' Ann. Math. Statist., v. 21, 1950, pp. 124127. MR 11, 693. MR 0035118 (11:693d)
 [33]
 V. Strassen, ``Gaussian elimination is not optimal,'' Numer. Math., v. 13, 1969, pp. 354356. MR 40 #2223. MR 0248973 (40:2223)
 [34]
 H. S. Wilf, ``Matrix inversion by the annihilation of rank,'' J. Soc. Indust. Appl. Math., v. 7, 1959, pp. 149151. MR 21 #6689. MR 0107968 (21:6689)
 [35]
 H. S. Wilf, ``Matrix inversion by the method of rank annihilation,'' in Mathematical Methods for Digital Computers, Wiley, New York, 1960, pp. 7377. MR 22 #8685. MR 0117911 (22:8685)
 [36]
 J. H. Wilkinson, Rounding Errors in Algebraic Processes, PrenticeHall, Englewood Cliffs, N.J., 1963. MR 28 #4661. MR 0161456 (28:4661)
 [37]
 M. A. Woodbury, Inverting Modified Matrices, Statistical Research Group Memo. Report, no. 42, Princeton University, Princeton. N.J., 1950. MR 12, 361; see also Householder [20]. MR 0038136 (12:361d)
 [38]
 G. Zielke, ``Inversion of modified symmetric matrices,'' J. Assoc. Comput. Mach., v. 15, 1968, pp. 402408.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F10,
65F30
Retrieve articles in all journals
with MSC:
65F10,
65F30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197203175274
PII:
S 00255718(1972)03175274
Article copyright:
© Copyright 1972
American Mathematical Society
