Namespaces
Variants
Actions

Steepest descent, method of

From Encyclopedia of Mathematics
Revision as of 17:04, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A special instance of the method of descent (cf. Descent, method of), when the direction of descent is chosen as the direction opposite to . The formulas of the method of steepest descent are

where the parameters are determined by the condition that the function has maximum decrease at each step. If is twice continuously-differentiable and its matrix of second derivatives satisfies the inequality

for any , with constants , then (see [2], [4]) the sequence converges to a solution of the problem of minimizing , the convergence rate being that of a geometric progression with quotient .

The method of steepest descent has been widely applied to the solution of systems of linear algebraic equations with a Hermitian or positive-definite matrix . In the real symmetric case, the problem of solving this system is equivalent to finding a vector in an -dimensional vector space minimizing the functional

(*)

Applied to (*), the method of steepest descent takes the form

where the value of is determined by minimization of the functional (*), according to the formula

If the spectrum of lies in an interval , , on the real axis, then the sequence converges to the solution at the rate of a geometric progression with quotient .

The method of steepest descent can be applied to solve an operator equation with a self-adjoint positive-definite bounded operator . If does not satisfy these conditions, the problem can be symmetrized, reduced to the problem

and then one can apply the method of steepest descent (see also Minimal discrepancy method).

References

[1] L.V. Kantorovich, "On the method of steepest descent" Dokl. Akad. Nauk SSSR , 56 : 3 (1947) pp. 233–236 (In Russian)
[2] L.V. Kantorovich, G.P. Akilov, "Functional analysis" , Pergamon (1982) (Translated from Russian)
[3] D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)
[4] B.N. Pshenichnyi, Yu.M. Danilin, "Numerical methods in extremal problems" , MIR (1978) (Translated from Russian)
[5] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)


Comments

References

[a1] G.H. Golub, C.F. van Loan, "Matrix computations" , Johns Hopkins Univ. Press (1989)
How to Cite This Entry:
Steepest descent, method of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Steepest_descent,_method_of&oldid=13529
This article was adapted from an original article by Yu.A. Kuznetsov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article