View source for Steepest descent, method of

{{MSC|65}}
{{TEX|done}}


The method of steepest decent is 
a special instance of the method of descent (cf.
[[Descent, method of|Descent, method of]]), when the direction $g^k$ of descent is chosen as the direction opposite to $\mathrm{grad} f(x^k)$. The formulas of the method of steepest descent are

$$x^{k+1} = x^k - \def\a{\alpha} \a_k f'(x^k),\quad k = 0,1,\dots ,$$
where the parameters $\{\a_k\}$ are determined by the condition that the function $f$ has maximum decrease at each step. If $f$ is twice continuously-differentiable and its matrix of second derivatives $f''$ satisfies the inequality

$$m\|y\|^2 \le (f''(x)y,y)\le M \|y\|^2$$
for any $x,y$, with constants $M\ge m > 0$, then (see
{{Cite|KaAk}},
{{Cite|PsDa}}) the sequence $\{x^k\}$ converges to a solution $x^*$ of the problem of minimizing $f$, the convergence rate being that of a geometric progression with quotient $q<1$.

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

$$F(X)=\frac{1}{2} (Ax,x) -(x,f).\tag{$*$}$$
Applied to (*), the method of steepest descent takes the form

$$x^{k+1} = x^k - \a_k(Ax^k -f), \quad k = 0,1,\dots ,$$
where the value of $\a_k$ is determined by minimization of the functional (*), according to the formula

$$\a_k = \frac{(\xi^k,\xi^k)}{(A\xi^k,\xi^k)},\quad \xi^k = Ax^k - f.$$
If the spectrum of $A$ lies in an interval $[m,M]$, $M\ge m > 0$, on the real axis, then the sequence $\{x^k\}$ converges to the solution $x^*$ at the rate of a geometric progression with quotient $q=(M-m)/(M+m)$.

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

$$A^* Au = A^*f,$$
and then one can apply the method of steepest descent (see also
[[Minimal discrepancy method|Minimal discrepancy method]]).

====References====
{|
|-
|valign="top"|{{Ref|Ba}}||valign="top"|  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations", MIR  (1977)  (Translated from Russian)  {{MR|0362811}}  {{ZBL|0524.65001}} 
|-
|valign="top"|{{Ref|FaFa}}||valign="top"|  D.K. Faddeev,   V.N. Faddeeva,   "Computational methods of linear algebra", Freeman  (1963)  (Translated from Russian)  {{MR|0161454}} {{MR|0158519}}  {{ZBL|0451.65015}} 
|-
|valign="top"|{{Ref|GoLo}}||valign="top"|  G.H. Golub,   C.F. van Loan,   "Matrix computations", Johns Hopkins Univ. Press  (1989)  {{MR|1002570}}  {{ZBL|0733.65016}} 
|-
|valign="top"|{{Ref|Ka}}||valign="top"|  L.V. Kantorovich,   "On the method of steepest descent"  ''Dokl. Akad. Nauk SSSR'', '''56''' :  3  (1947)  pp. 233–236  (In Russian)   
|-
|valign="top"|{{Ref|KaAk}}||valign="top"|  L.V. Kantorovich,   G.P. Akilov,   "Functional analysis", Pergamon  (1982)  (Translated from Russian)  {{MR|0664597}}  {{ZBL|0484.46003}} 
|-
|valign="top"|{{Ref|PsDa}}||valign="top"|  B.N. Pshenichnyi,   Yu.M. Danilin,   "Numerical methods in extremal problems", MIR  (1978)  (Translated from Russian)  {{MR|0502886}}  
|-
|}