Revenue equivalence

2013-11-26T04:23:11Z

67.194.68.11: /* First Price Auction */

{{About|iterative methods for solving systems of equations|other uses|Relaxation (disambiguation)}}
In [[numerical mathematics]], '''relaxation methods''' are [[iterative method]]s for solving [[simultaneous equations|systems of equations]], including nonlinear systems.<ref name="OrtegaRheinboldt">{{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}}</ref>

Relaxation methods were developed for solving large [[sparse matrix|sparse]] [[linear system]]s, which arose as [[finite difference|finite-difference]] [[discretization]]s of [[differential equation]]s.<ref name="Varga "/><ref name="Young "/> They are also used for the solution of linear equations for [[linear least-squares]]{{Disambiguation needed|date=October 2012}} problems<ref name="BP"/> and also for systems of linear inequalities, such as those arising in [[linear programming]].<ref name="Murty">{{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}}</ref><ref>{{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}}</ref><ref name="Minoux">{{Cite book|last=Minoux|first=M.|authorlink=Michel Minoux|title=Mathematical programming: Theory and algorithms|note=With a foreword by Egon Balas|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}})|}}</ref> They have also been developed for solving nonlinear systems of equations.<ref name="OrtegaRheinboldt"/>

Relaxation methods are important especially in the solution of linear systems used to model [[elliptic partial differential equation]]s, such as [[Laplace's equation]] and its generalization, [[Poisson's equation]]. These equations describe [[boundary-value problem]]s, 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.<ref name="BP">Abraham Berman, Robert J. Plemmons, ''Nonnegative Matrices in the Mathematical Sciences'', 1994, SIAM. ISBN 0-89871-321-8.</ref><ref name="Young">[[David M. Young, Jr.]] ''Iterative Solution of Large Linear Systems'', Academic Press, 1971. (reprinted by Dover, 2003)</ref><ref name="Varga">[[Richard S. Varga]] 2002 ''Matrix Iterative Analysis'', Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.</ref>

These ''iterative methods'' of relaxation should not be confused with "''[[relaxation (approximation)|relaxation]]s''" in [[mathematical optimization]], which [[approximation theory|approximate]] a difficult problem by a simpler problem, whose "relaxed" solution provides information about the solution of the original problem.<ref name="Minoux"/>

==Synonyms==
Iterative relaxation of solutions is commonly dubbed ''smoothing'' because relaxation of certain equations (such as [[Laplace's equation]]) resembles repeated application of a local [[smoothing]] filter to the solution vector.<br>
Another name is [[Iterative_method#Stationary_iterative_methods|stationary linear iterative method]].

==Model problem of potential theory==
When φ is a smooth real-valued function on the real numbers, its second derivative can be approximated by:
:<math>\frac{d^2\varphi(x)}{{dx}^2} = \frac{\varphi(x{-}h)-2\varphi(x)+\varphi(x{+}h)}{h^2}\,+\,\mathcal{O}(h^2)\,.</math>
Using this in both dimensions for a function φ of two arguments at the point (''x'', ''y''), and solving for φ(''x'', ''y''), results in:
:<math>\varphi(x, y) = \tfrac{1}{4}\left(\varphi(x{+}h,y)+\varphi(x,y{+}h)+\varphi(x{-}h,y)+\varphi(x,y{-}h)
\,-\,h^2{\nabla}^2\varphi(x,y)\right)\,+\,\mathcal{O}(h^4)\,.</math>
To approximate the solution of the Poisson equation:
:<math>{\nabla}^2 \varphi = f\,</math>
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:
:<math>\varphi^*(x, y) = \tfrac{1}{4}\left(\varphi(x{+}h,y)+\varphi(x,y{+}h)+\varphi(x{-}h,y)+\varphi(x,y{-}h)
\,-\,h^2f(x,y)\right)\,,</math>
until convergence.<ref name="Young"/><ref name=" Varga"/>

The method, sketched here for two dimensions,<ref name="Young"/><ref name=" Varga"/> 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 [[preconditioner]]s for new methods. Indeed, the choice of preconditioner is often more important than the choice of iterative method, according to [[Yousef Saad]].<ref name="Saad">[[Yousef Saad]], ''[http://www-users.cs.umn.edu/%7Esaad/books.html Iterative Methods for Sparse Linear Systems]'', 1st edition, PWS, 1996.</ref>

[[Multigrid methods]] may be used to accelerate the methods. One can first compute an approximation on a coarser grid – usually the double spacing 2''h'' – and use that solution with [[interpolation|interpolated]] values for the other grid points as the initial assignment. This can then also be done recursively for the coarser computation.<ref name="Saad"/><ref>William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000), ''[http://www.llnl.gov/casc/people/henson/mgtut/welcome.html A Multigrid Tutorial]'' (2nd ed.), Philadelphia: [[Society for Industrial and Applied Mathematics]], ISBN 0-89871-462-1.</ref>

==See also==
* 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==
<references/>

==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]], ''[http://www-users.cs.umn.edu/%7Esaad/books.html 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}}

[[Category:Iterative methods]]
[[Category:Numerical linear algebra]]
[[Category:Relaxation (iterative methods)]]

formulasearchengine - User contributions [en]

Revenue equivalence