Steepest descent, method of

2020 Mathematics Subject Classification: Primary: 65-XX [MSN][ZBL]

The method of steepest decent is a special instance of the method of descent (cf. 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 [KaAk], [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).

References

[Ba]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations", MIR (1977) (Translated from Russian) MR0362811 Zbl 0524.65001
[FaFa]	D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra", Freeman (1963) (Translated from Russian) MR0161454 MR0158519 Zbl 0451.65015
[GoLo]	G.H. Golub, C.F. van Loan, "Matrix computations", Johns Hopkins Univ. Press (1989) MR1002570 Zbl 0733.65016
[Ka]	L.V. Kantorovich, "On the method of steepest descent" Dokl. Akad. Nauk SSSR, 56 : 3 (1947) pp. 233–236 (In Russian)
[KaAk]	L.V. Kantorovich, G.P. Akilov, "Functional analysis", Pergamon (1982) (Translated from Russian) MR0664597 Zbl 0484.46003
[PsDa]	B.N. Pshenichnyi, Yu.M. Danilin, "Numerical methods in extremal problems", MIR (1978) (Translated from Russian) MR0502886