请输入您要查询的百科知识：

　

词条 Relaxation (iterative method)
释义

  1. Convergence and acceleration

  2. See also

  3. Notes

  4. References

  5. Further reading

{{About|iterative methods for solving systems of equations|other uses|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. 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.[2][3][4] 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.[5][6][7]

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.[4]

==Model problem of potential theory==

When φ is a smooth real-valued function on the real numbers, its second derivative can be approximated by:

Using this in both dimensions for a function φ of two arguments at the point (x, y), and solving for φ(x, y), results in:

To approximate the solution of the Poisson equation:

numerically on a two-dimensional grid with grid spacing h, the relaxation method assigns the given values of function φ to the grid points near the boundary and arbitrary values to the interior grid points, and then repeatedly performs the assignment

φ := φ* on the interior points, where φ* is defined by:

until convergence.[6]

The method, sketched here for two dimensions,[6] is readily generalized to other numbers of dimensions.

Convergence and acceleration

While the method converges under general conditions, it typically makes slower progress than competing methods. Nonetheless, the study of relaxation methods remains a core part of linear algebra, because the transformations of relaxation theory provide excellent preconditioners for new methods. Indeed, the choice of preconditioner is often more important than the choice of iterative method.[8]

Multigrid methods may be used to accelerate the methods. One can first compute an approximation on a coarser grid – usually the double spacing 2h – and use that solution with interpolated values for the other grid points as the initial assignment. This can then also be done recursively for the coarser computation.[8][9]

See also

  • In linear systems, the two main classes of relaxation methods are stationary iterative methods, and the more general Krylov subspace methods.
  • The Jacobi method is a simple relaxation method.
  • The Gauss–Seidel method is an improvement upon the Jacobi method.
  • Successive over-relaxation can be applied to either of the Jacobi and Gauss–Seidel methods to speed convergence.
  • Multigrid methods

Notes

1. ^1 {{Cite book|last1=Ortega|first1=J. M.|last2=Rheinboldt|first2=W. C.|title=Iterative solution of nonlinear equations in several variables|edition=Reprint of the 1970 Academic Press|series=Classics in Applied Mathematics|volume=30|publisher=Society for Industrial and Applied Mathematics (SIAM)|location=Philadelphia, PA|year=2000|pages=xxvi+572|isbn=0-89871-461-3|mr=1744713|ref=harv}}
2. ^{{Cite book|last=Murty|first=Katta G.|authorlink=Katta G. Murty|chapter=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)| title=Linear programming|publisher=John Wiley & Sons Inc.|location=New York|year=1983|pages=453–464|isbn=0-471-09725-X|mr=720547|ref=harv}}
3. ^{{Cite journal|last=Goffin|first=J.-L.|title=The relaxation method for solving systems of linear inequalities|journal=Math. Oper. Res.|volume=5|year=1980|number=3|pages=388–414|jstor=3689446|doi=10.1287/moor.5.3.388|mr=594854|ref=harv}}
4. ^1 {{Cite book|last=Minoux|first=M.|authorlink=Michel Minoux|title=Mathematical programming: Theory and algorithms|others=Egon Balas (foreword)|edition=Translated by Steven Vajda from the (1983 Paris: Dunod) French|publisher=A Wiley-Interscience Publication. John Wiley & Sons, Ltd.|location=Chichester|year=1986|pages=xxviii+489|isbn=0-471-90170-9|mr=868279|ref=harv|id=(2008 Second ed., in French: Programmation mathématique: Théorie et algorithmes. Editions Tec & Doc, Paris, 2008. xxx+711 pp. {{isbn|978-2-7430-1000-3}}. {{MR|2571910}})}}
5. ^1 Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. {{isbn|0-89871-321-8}}.
6. ^1 2 David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003)
7. ^Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
8. ^1 Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996.
9. ^William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000), A Multigrid Tutorial {{webarchive|url=https://web.archive.org/web/20061006153457/http://www.llnl.gov/casc/people/henson/mgtut/welcome.html |date=2006-10-06 }} (2nd ed.), Philadelphia: Society for Industrial and Applied Mathematics, {{isbn|0-89871-462-1}}.

References

  • Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. {{isbn|0-89871-321-8}}.
  • {{Cite book|last1=Ortega|first1=J. M.|last2=Rheinboldt|first2=W. C.|title=Iterative solution of nonlinear equations in several variables|edition=Reprint of the 1970 Academic Press|series=Classics in Applied Mathematics|volume=30|publisher=Society for Industrial and Applied Mathematics (SIAM)|location=Philadelphia, PA|year=2000|pages=xxvi+572|isbn=0-89871-461-3|mr=1744713|ref=harv}}
  • {{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 18.3. Relaxation Methods | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=964}}
  • Yousef Saad, Iterative Methods for Sparse Linear Systems, 1st edition, PWS, 1996.
  • Richard S. Varga 2002 Matrix Iterative Analysis, Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
  • David M. Young, Jr. Iterative Solution of Large Linear Systems, Academic Press, 1971. (reprinted by Dover, 2003)

Further reading

  • Southwell, R.V. (1940) Relaxation Methods in Engineering Science. Oxford University Press, Oxford.
  • Southwell, R.V. (1946) Relaxation Methods in Theoretical Physics. Oxford University Press, Oxford.
  • {{cite book | author= John. D. Jackson | title=Classical Electrodynamics | location=New Jersey | publisher=Wiley | year=1999| isbn=0-471-30932-X}}
  • {{cite book | author= M.N.O. Sadiku | title=Numerical Techniques in Electromagnetics | location=Boca Raton | publisher=CRC Pres | year=1992}}
  • {{cite book | author= P.-B. Zhou | title=Numerical Analysis of Electromagnetic Fields | location=New York | publisher=Springer | year=1993}}

3 : Iterative methods|Numerical linear algebra|Relaxation (iterative methods)
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/23 9:32:11