newton Interface

public interface newton

Implements the simple Newton-Krylov method for finding roots (fixed points) of a nonlinear vector-valued function $F(\mathbf{X})$, i.e. solutions $\mathbf{X}^*$ such that $F(\mathbf{X}^*) - \mathbf{X}^* = \mathbf{0}$ starting from an initial guess via successive solution increments based on local linearization $\mathbf{J}_\mathbf{X}$ (the Jacobian) of the nonlinear function in the vicinity of the current solution.

Algorthmic Features

• At iteration $k$, the standard Newton step $\mathbf{\delta x}_k$ is computed as the solution of the linear system

$$\mathbf{J}_\mathbf{X_k} \mathbf{\delta x}_k = \mathbf{r}_k$$

where $\mathbf{r}_k = -F(\mathbf{X}_k)$ is the residual of the nonlinear function. The new guess for the fixed point is then given by:

$$\mathbf{X}_{k+1} = \mathbf{X}_k + \alpha \mathbf{\delta x}_k$$

where $\alpha \in \left( 0, 1 \right]$ parametrizes the step length. The standard Newton algorithm sets $\alpha = 1$.

• The Jacobian is never assembled and the linear system is solved using one of the available iterative solvers.
• When the residual norm does not decrease during iteration indicating that the linearization is not a very accurate model of the function's behaviour, which often happens during the initial iterations, a 1D step bisection method based on the golden ratio is implemented to dampen the step and improve convergence of the method.
• The implementation allows for dynamic tolerances (also known as inexact Newton), where the approximation for the residual and the linear system can be solved with relaxed tolerances to reduce overall time to solution.
• The method is suitable to both fixed points and periodic orbits via the choice of residual and corresponding Jacobian matrix. In the case of unforced periodic orbits, the period is itself an unknown that must be included in the iteration.

Advantages

• The iterative solution of the linear systems has a comparatively low storage footprint.
• If the Newton iteration converges, the convergence is formally asymptotically of second order. Using dynamic tolerances and line searches slightly reduce this convergence rate in exchange for a larger convergence region.

Limitations

• The method is not guaranteed to converge if the initial guess is too far from the fixed point. If the Newton iteration diverges even with step bisection, the best suggestion is to find a better initial guess. If this is not feasible, some alternatives to improve the convergence of the Newton iteration are possible (but not implemented to date), including various line search algorithms and trust region methods (doglog, double dogleg, hookstep, ...).

References

• Sánchez, J., Net, M., Garcıa-Archilla, B., & Simó, C. (2004). "Newton–Krylov continuation of periodic orbits for Navier–Stokes flows". Journal of Computational Physics, 201(1), 13-33.
• Viswanath, D. (2007). "Recurrent motions within plane Couette turbulence". Journal of Fluid Mechanics, 580, 339-358.
• Duguet, Y., Pringle, C. C. T., Kerswell, R. R. (2008). "Relative periodic orbits in transitional pipe flow". Physics of Fluids, 20(11), 114102.
• Frantz, R. A., Loiseau, J. C., & Robinet, J. C. (2023). "Krylov methods for large-scale dynamical systems: Application in fluid dynamics". Applied Mechanics Reviews, 75(3), 030802.

Module Procedures