Relaxation (iterative method)

This article is about iterative methods for solving systems of equations. For other uses, see Relaxation (disambiguation).

In numerical mathematics, relaxation methods are iterative methods for solving systems of equations, including nonlinear systems.[1]

Relaxation methods were developed for solving large sparse linear systems, which arose as finite-difference discretizations of differential equations.[2][3] They are also used for the solution of linear equations for linear least-squares problems[4] and also for systems of linear inequalities, such as those arising in linear programming.[5][6][7] They have also been developed for solving nonlinear systems of equations.[1]

Relaxation methods are important especially in the solution of linear systems used to model elliptic partial differential equations, such as Laplace's equation and its generalization, Poisson's equation. These equations describe boundary-value problems, in which the solution-function's values are specified on boundary of a domain; the problem is to compute a solution also on its interior. Relaxation methods are used to solve the linear equations resulting from a discretization of the differential equation, for example by finite differences.[2][3][4]

Iterative relaxation of solutions is commonly dubbed smoothing because with certain equations, such as Laplace's equation, it resembles repeated application of a local smoothing filter to the solution vector. These are not to be confused with relaxation methods in mathematical optimization, which approximate a difficult problem by a simpler problem whose "relaxed" solution provides information about the solution of the original problem.[7]

  1. ^ a b Ortega, J. M.; Rheinboldt, W. C. (2000). Iterative solution of nonlinear equations in several variables. Classics in Applied Mathematics. Vol. 30 (Reprint of the 1970 Academic Press ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xxvi+572. ISBN 0-89871-461-3. MR 1744713.
  2. ^ a b Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
  3. ^ a b David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003)
  4. ^ a b Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
  5. ^ Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons Inc. pp. 453–464. ISBN 0-471-09725-X. MR 0720547.
  6. ^ Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Mathematics of Operations Research. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854.
  7. ^ a b Minoux, M. (1986). Mathematical programming: Theory and algorithms. Egon Balas (foreword) (Translated by Steven Vajda from the (1983 Paris: Dunod) French ed.). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique: Théorie et algorithmes. Editions Tec & Doc, Paris, 2008. xxx+711 pp. . ).