Accelerating convergence of the globalized Newton method to critical solutions of nonlinear equations
- PDF / 1,110,294 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 152 Views
Accelerating convergence of the globalized Newton method to critical solutions of nonlinear equations A. Fischer1 · A. F. Izmailov2 · M. V. Solodov3 Received: 8 April 2020 / Accepted: 14 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the case of singular (and possibly even nonisolated) solutions of nonlinear equations, while superlinear convergence of the Newton method cannot be guaranteed, local linear convergence from large domains of starting points still holds under certain reasonable assumptions. We consider a linesearch globalization of the Newton method, combined with extrapolation and over-relaxation accelerating techniques, aiming at a speed up of convergence to critical solutions (a certain class of singular solutions). Numerical results indicate that an acceleration is observed indeed. Keywords Nonlinear equation · Newton method · Singular solution · Critical solution · 2-regularity · Linear convergence · Superlinear convergence · Extrapolation · Overrelaxation · Linesearch Mathematics Subject Classifications 65H10 · 65H20
1 Introduction In this paper, we are interested in the behavior of various forms of linesearch Newton methods for a system of nonlinear equations
* A. F. Izmailov [email protected] A. Fischer andreas.fischer@tu‑dresden.de M. V. Solodov [email protected] 1
Faculty of Mathematics, Technische Universität Dresden, 01062 Dresden, Germany
2
VMK Faculty, OR Department, Lomonosov Moscow State University, MSU, Uchebniy Korpus 2, Leninskiye Gory, Moscow, Russia 119991
3
IMPA – Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro RJ 22460‑320, Brazil
13
Vol.:(0123456789)
A. Fischer et al.
Φ(u) = 0,
(1.1)
where Φ ∶ ℝp → ℝp is a sufficiently smooth mapping. We are especially interested in the case when this system has singular (and possibly even nonisolated) solutions. Here, by singularity of a solution ū we mean that the Jacobian Φ� (̄u) is a singular matrix. For a given iterate uk ∈ ℝp , the basic Newton method generates the next iterate by the update uk+1 = uk + vk , where vk solves the linear system
Φ(uk ) + Φ� (uk )v = 0.
(1.2)
The classical theory says that when initialized close to a nonsingular solution, this method uniquely defines a sequence of iterates, converging to this solution superlinearly. Moreover, the standard linesearch technique employing the residual of (1.1), used to globalize convergence, accepts the unit stepsize asymptotically, thus ensuring fast local convergence of the overall algorithm. See, e.g., [17, Chapter 5.1.1]. In case of a singular solution ū , it is evident that one cannot guarantee convergence of the Newton method from all starting points in the entire neighborhood of ū , as the iteration equation (1.2) need not even be solvable for some uk arbitrarily close to such ū . Nevertheless, local convergence at a linear rate can still be established from some large domains of starting points, and under reasonable assumptions. The most relevan
Data Loading...
