The Quasi-Newton Least Squares Method: A New and Fast Secant Method Analyzed for Linear Systems
Authors:
- Rob HaeltermanRHRob Haelterman
- Joris DegrooteJoris Degroote
- Dirk Van HeuleDHDirk Van Heule
- Jan VierendeelsJVJan Vierendeels
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 47 (3) , 2347-2368
Abstract
We present a new quasi-Newton method that can solve systems of equations of which no information is known explicitly and which requires no special structure of the system matrix, like positive definiteness or sparseness. The method builds an approximate Jacobian based on input-output combinations of a black box system, uses a rank-one update of this Jacobian after each iteration, and satisfies the secant equation. While it has originally been developed for nonlinear equations we analyze its properties and performance when applied to linear systems. Analytically, the method is shown to be convergent in $n+1$ iterations (n being the number of unknowns), irrespective of the nature of the system matrix. The performance of this method is greatly superior to other quasi-Newton methods and comparable with GMRes when tested on a number of standardized test-cases.
Keywords
This publication has 23 references indexed in Scilit:
- A new implementation of EN methodApplied Mathematics and Computation, 1999
- A parallel, implicit, cell‐centered method for two‐phase flow with a preconditioned Newton–Krylov solverComputational Geosciences, 1997
- Fast secant methods for the iterative solution of large nonsymmetric linear systemsIMPACT of Computing in Science and Engineering, 1990
- Accelerating with rank-one updatesLinear Algebra and its Applications, 1989
- Least Change Secant Updates for Quasi-Newton MethodsSIAM Review, 1979
- Some Convergence Properties of Broyden’s MethodSIAM Journal on Numerical Analysis, 1979
- Quasi-Newton Methods, Motivation and TheorySIAM Review, 1977
- A characterization of superlinear convergence and its application to quasi-Newton methodsMathematics of Computation, 1974
- Quasi-Newton methods and their application to function minimisationMathematics of Computation, 1967
- A class of methods for solving nonlinear simultaneous equationsMathematics of Computation, 1965