On the linear convergence of Newton–Krylov methods

Abstract

Solution of large-scale nonlinear optimization problems and systems of nonlinear equations continues to be a difficult problem. One of the main classes of algorithms for solving these problems is the class of Newton–Krylov methods. In this article the number of iterations of a Krylov subspace method needed to guarantee at least a linear convergence of the respective Newton–Krylov method is studied. The problem is especially complicated if the matrix of the linear system to be solved is nonsymmetric. In the article, explicit estimates for the number of iterations for the Krylov subspace methods are obtained.

Keywords:

• Newton–Krylov methods
• linear convergence
• large-scale optimization

AMS Subject Classification :

• 90C53
• 65K05
• 65F10

Acknowledgements

The authors would like to thank the anonymous reviewer for valuable comments and suggestions. The authors would especially like to thank Oleg Burdakov for a fruitful discussion of the problem.