Namespaces
Variants
Actions

Relaxation method

From Encyclopedia of Mathematics
Revision as of 16:32, 26 October 2014 by Richard Pinch (talk | contribs) (Category:Numerical analysis and scientific computing)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

weakening method

A method for the iterative solution of a system of linear algebraic equations $Ax=b$, the elementary step of which consists of varying only one component of the vector of unknowns, the number of variable components being chosen in a specific cyclic order. The relaxation method is most often used for solving systems with a positive-definite matrix $A$.

If one component of the vector of unknowns $x^k$ is varied such that for the new approximation $x^{k+1}$ the quadratic form $(A(x^{k+1}-x),x^{k+1}-x)$ is minimized, then the relaxation method is called a complete relaxation method. If, however, after one elementary step the value of the quadratic form is only reduced and not minimized, the relaxation method is called an incomplete relaxation method.

The best investigated method is that of successive upper relaxation, where the matrix $A$ possesses the so-called property $(A)$ and is ordered accordingly. A matrix $A$ is called a matrix possessing property $(A)$ if there is a permutation matrix $P$ such that the matrix $PAP^T$ has the form

$$\begin{Vmatrix}D_1&H\\K&D_2\end{Vmatrix},$$

where $D_1$ and $D_2$ are square diagonal matrices.

The iteration scheme of the relaxation method is as follows:

$$(D+\omega L)x^{k+1}=((1-\omega)D-\omega U)x^k+\omega b\quad k=0,1,\dots,$$

where $\omega$ is the relaxation parameter, $D$ is the diagonal, $L$ is the lower-triangular and $U$ is the upper-triangular matrix in the decomposition $A=D+L+U$. If $\omega>1$, then the method is called an upper relaxation method (over-relaxation), and if $\omega\leq1$, a lower relaxation method. The parameter $\omega$ is chosen from the condition of minimization of the spectral radius of the matrix $S$ of transfer from iteration to iteration:

$$S=(D+\omega L)^{-1}((1-\omega)D-\omega U).$$

If $A$ is a symmetric matrix with positive diagonal elements and $\lambda_i$ are the roots of the determinant equation $\det(L+\lambda D+U)=0$, then the optimum value of the parameter $\omega$ is given by the formula

$$\omega=\omega_0=\frac{2}{1+\sqrt{1-\lambda_0^2}},$$

where $\lambda_0^2=\max\lambda_i^2$. For $\omega=\omega_0$ the spectral radius of $S$ is equal to

$$\omega_0-1=\frac{1-\sqrt{1-\lambda_0^2}}{1+\sqrt{1-\lambda_0^2}}<1.$$

Cases are examined where some $\lambda_i$ are complex. Block relation methods have been developed.

References

[1] D.M. Young, "Iterative methods for solving partial differential equations of elliptic type" Trans. Amer. Math. Soc. , 76 : 1 (1954) pp. 92–111
[2] D.M. Young, "Iterative solution of large linear systems" , Acad. Press (1971)
[3] W. Wasow, J. Forsyth, "Finite-difference methods for partial differential equations" , Wiley (1960)
[4] D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)
[5] L.A. Hageman, D.M. Young, "Applied iterative methods" , Acad. Press (1981)
How to Cite This Entry:
Relaxation method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Relaxation_method&oldid=33055
This article was adapted from an original article by E.S. Nikolaev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article