Newton methods for nonlinear problems. Affine invariance and adaptive algorithms.

*(English)*Zbl 1056.65051
Springer Series in Computational Mathematics 35. Berlin: Springer (ISBN 3-540-21099-7/hbk). xii, 424 p. (2004).

Although the invariance of Newton’s method under affine transformations tends to be known, it has scarcely been taken into account in standard convergence theories and typical computational practice. For many years the author and various colleagues have shown that careful attention to this affine invariance allows for the development of highly effective algorithms. This book represents a long awaited comprehensive treatise of these important, and, by now, wide ranging results. It reflects the author’s conviction (shared by this reviewer) that mathematical theory and algorithm construction should mutually influence each other as closely as possible. Accordingly, the presentation is strongly balanced in its interplay between the theoretical analysis and the development of algorithms that are effective for realistic, and not just toy-type, problems.

The overall presentation has two basic threads. The first involves close consideration of four affine invariances for Newton’s method applied to a nonlinear mapping \(F\) between Banach spaces: (1) Affine covariance: The iterates are invariant under affine transformations of the image space. (2) Affine contravariance: Under affine transformations of the domain space the iterates transform in the same way. (3) Affine conjugacy: If \(F\) is a gradient mapping then under an affine transformation of the domain space the Jacobian transformation is conjugate. (4) Affine similarity: In the case of identical domain and image spaces an affine transformation induces a similarity transformation of the Jacobian.

The second thread is a computational paradigm central to the construction of adaptive Newton algorithms: Affine-invariant computational estimates of affine invariant Lipschitz constants are cheaply available in the course of the algorithms, while, without strict observation of the affine invariance of the Lipschitz conditions geometric distortions lead to totally unrealistic estimates.

After an introductory chapter covering the basic background and terminology, the book is divided into two parts. The first part concerns Newton methods in finite dimensions. Different affine invariant Lipschitz conditions lead to different local convergence domains in terms of different norms. In particular, the above named invariances (1), (2), and (3) give rise to algorithms that are controlled by error norms, residual norms, and energy norms, respectively. The details are worked out for different types of Newton algorithms and then globalization concepts are surveyed, such as steepest descent methods, trust region methods, Levenberg Marquardt methods, and Newton’s method with damping strategies. Affine invariance also plays an important role in local and global Gauss-Newton methods for nonlinear least squares. In addition, adaptive continuation processes for parameter dependent nonlinear equations are discussed and attention is also directed to augmented systems for determining selected critical points.

The second part of the book turns to infinite-dimensional problems. For stiff initial value problems for ordinary differential equations (ODEs) a simplified Newton method is analyzed as a replacement of the standard Picard iteration that, typically, is suitable only for nonstiff problems. For nonlinear two-point ODE boundary value problems an adaptive multilevel collocation method is applied and analyzed as an inexact Newton method in function space. Finally, the last chapter addresses asymptotic mesh independence and the use of inexact Newton multilevel finite element methods for solving elliptic partial differential equations (PDE) boundary value problems.

Throughout the text algorithms are presented as informal programs. Many of these have been implemented in detail and were used for various numerical examples. Web sites for these codes are provided.

In many parts the presentation covers unpublished material and also points to possible future research areas and relevant topics that have not been included. As such the book is certainly a research monograph. However, the form of the presentation also makes selected parts well accessible for use as text material in appropriate courses. All in all, this is an excellent contribution to the computational analysis of nonlinear equations that should be of interest to anyone interested in this area.

The overall presentation has two basic threads. The first involves close consideration of four affine invariances for Newton’s method applied to a nonlinear mapping \(F\) between Banach spaces: (1) Affine covariance: The iterates are invariant under affine transformations of the image space. (2) Affine contravariance: Under affine transformations of the domain space the iterates transform in the same way. (3) Affine conjugacy: If \(F\) is a gradient mapping then under an affine transformation of the domain space the Jacobian transformation is conjugate. (4) Affine similarity: In the case of identical domain and image spaces an affine transformation induces a similarity transformation of the Jacobian.

The second thread is a computational paradigm central to the construction of adaptive Newton algorithms: Affine-invariant computational estimates of affine invariant Lipschitz constants are cheaply available in the course of the algorithms, while, without strict observation of the affine invariance of the Lipschitz conditions geometric distortions lead to totally unrealistic estimates.

After an introductory chapter covering the basic background and terminology, the book is divided into two parts. The first part concerns Newton methods in finite dimensions. Different affine invariant Lipschitz conditions lead to different local convergence domains in terms of different norms. In particular, the above named invariances (1), (2), and (3) give rise to algorithms that are controlled by error norms, residual norms, and energy norms, respectively. The details are worked out for different types of Newton algorithms and then globalization concepts are surveyed, such as steepest descent methods, trust region methods, Levenberg Marquardt methods, and Newton’s method with damping strategies. Affine invariance also plays an important role in local and global Gauss-Newton methods for nonlinear least squares. In addition, adaptive continuation processes for parameter dependent nonlinear equations are discussed and attention is also directed to augmented systems for determining selected critical points.

The second part of the book turns to infinite-dimensional problems. For stiff initial value problems for ordinary differential equations (ODEs) a simplified Newton method is analyzed as a replacement of the standard Picard iteration that, typically, is suitable only for nonstiff problems. For nonlinear two-point ODE boundary value problems an adaptive multilevel collocation method is applied and analyzed as an inexact Newton method in function space. Finally, the last chapter addresses asymptotic mesh independence and the use of inexact Newton multilevel finite element methods for solving elliptic partial differential equations (PDE) boundary value problems.

Throughout the text algorithms are presented as informal programs. Many of these have been implemented in detail and were used for various numerical examples. Web sites for these codes are provided.

In many parts the presentation covers unpublished material and also points to possible future research areas and relevant topics that have not been included. As such the book is certainly a research monograph. However, the form of the presentation also makes selected parts well accessible for use as text material in appropriate courses. All in all, this is an excellent contribution to the computational analysis of nonlinear equations that should be of interest to anyone interested in this area.

Reviewer: W. C. Rheinboldt (Pittsburgh)

##### MSC:

65H10 | Numerical computation of solutions to systems of equations |

65-02 | Research exposition (monographs, survey articles) pertaining to numerical analysis |

65L05 | Numerical methods for initial value problems involving ordinary differential equations |

65L10 | Numerical solution of boundary value problems involving ordinary differential equations |

65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |

65J15 | Numerical solutions to equations with nonlinear operators |

47J25 | Iterative procedures involving nonlinear operators |

34A34 | Nonlinear ordinary differential equations and systems |

34B15 | Nonlinear boundary value problems for ordinary differential equations |

35J65 | Nonlinear boundary value problems for linear elliptic equations |