Modification methods for inverting matrices and solving systems of linear algebraic equations

Author:
D. Goldfarb

Journal:
Math. Comp. **26** (1972), 829-852

MSC:
Primary 65F10; Secondary 65F30

DOI:
https://doi.org/10.1090/S0025-5718-1972-0317527-4

MathSciNet review:
0317527

Full-text 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 rank-one 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, Gauss-Jordan elimination, Aitken's below-the-line 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. 172-181.**[2]**M. S. Bartlett, ``An inverse matrix adjustment arising in discriminant analysis,''*Ann. Math. Statist.*, v. 22, 1951, pp. 107-111. MR**12**, 639. MR**0040068 (12:639c)****[3]**E. Bodewig,*Matrix Calculus*, North-Holland, 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. 577-593. 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. 1235-1240.**[6]**J. E. Dennis, Jr.,*On the Convergence of Broyden's Method for Nonlinear Systems of Equations*, Technical Report #69-48, 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. 115-120.**[8]**W. J. Duncan, ``Some devices for the solution of large sets of simultaneous linear equations,''*Philos. Mag.*, (7), v. 35, 1944, pp. 660-670. 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. 209-211. (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. 149-173. MR**10**, 152. MR**0026421 (10:152i)****[14]**C. F. Gauss, ``Supplementum theoriae combinationis observationum erroribus minimis obnoxiae,''*Werke*. Band IV, Gottingen, 1873, pp. 55-93.**[15]**D. Goldfarb,*Modification Methods for Inverting Matrices and Solving Systems of Linear Algebraic Equations*, IBM-Philadelphia Scientific Center, Technical Report #320-2998, 1971. MR**0317527 (47:6074)****[16]**J. Greenstadt, ``Variations on variable-metric methods (with discussion),''*Math. Comp.*, v. 24, 1970, pp. 1-22. MR**41**#2895. MR**0258248 (41:2895)****[17]**M. R. Hestenes, ``Iterative computational methods,''*Comm. Pure Appl. Math.*, v. 8, 1955, pp. 85-95. 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. 51-90. MR**19**, 1080. MR**0092215 (19:1080d)****[19]**H. Hotelling, ``Some new methods in matrix calculation,''*Ann. Math. Statist.*, v. 14, 1943, pp. 1-34. 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*, IBM-New York Scientific Center, Technical Report #320-2989, 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. 22-33 =*U.S.S.R. Comput. Math. and Math. Phys.*, v. 5, 1965, pp. 25-43. 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. 106-120. 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. 288-290. 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. 31-65. MR**0272162 (42:7043)****[29]**E. W. Purcell, ``The vector method of solving simultaneous linear equations,''*J. Mathematical Phys.*, v. 32, 1953, pp. 180-183. 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. 123-124. 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. 124-127. MR**11**, 693. MR**0035118 (11:693d)****[33]**V. Strassen, ``Gaussian elimination is not optimal,''*Numer. Math.*, v. 13, 1969, pp. 354-356. 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. 149-151. 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. 73-77. MR**22**#8685. MR**0117911 (22:8685)****[36]**J. H. Wilkinson,*Rounding Errors in Algebraic Processes*, Prentice-Hall, 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. 402-408.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F10,
65F30

Retrieve articles in all journals with MSC: 65F10, 65F30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1972-0317527-4

Article copyright:
© Copyright 1972
American Mathematical Society