Newton methods for Nonlinear Systems
              and Function Optimization.
              Theory and Implementation
     Luca Bergamaschi
     Department of Civil Environmental and Architectural Engineering
     University of Padova
     e-mail:luca.bergamaschi@unipd.it
     webpage: www.dmsa.unipd.it/˜berga
        Summary
                  Nonlinear systems of equations. A few examples
                  Newton’s method for f(x)=0.
                  Newton’s method for systems.
                  Local convergence. Exit tests.
                  Global convergence. Backtracking. Line search algorithms
                  Solving the Newton systems by iterative methods: the Inexact Newton method.
                  Avoiding exact computation of the Jacobian: Quasi Newton methods: theory and
                  sparse implementation.
                                                                                                 2 of 53
           Systems of nonlinear equations: Examples
                         Intersection of curves in Rn.
                         Find the intersections between the circumference and the hyperbola:
                                                                      x2+y2=4
                                                                          xy =1
                         Discretization of nonlinear PDEs. Examples
                             1  Navier Stokes equations in fluid-dynamics
                             2  Two-phase flow in porous media
                         Minimization of nonlinear functions (applications in data science, machine
                         learning)
                                                          minG(x)        =⇒ Solve G′(x)=0
                                                                                                                                         3 of 53
        The Navier-Stokes problem
              The motion of incompressible newtonian fluids is governed by the Navier-Stokes
              equations, a system of PDEs that arises from the conservation of mass and
              momentum.
              In the general non-stationary case they take the form
                           ∂u
                           ∂t −ν∆u+(u·∇)u+∇p=f, x∈Ω,t>0                    +BCs
                           
                             divu=0,                        x∈Ω,t>0
              where Ω⊂R3 is the domain on which the motion evolves; u=u(x,t) is the velocity
              field; p =p(x,t) is the density-scaled pressure field; f is a forcing term per unit mass,
              ν is the kinematic viscosity.
              The first of the two equations imposes the conservation of momentum;
                  the term ν∆u takes into account the diffusive processes,
                  (u·∇)u models the convective processes.
              The equation divu=0 imposes the incompressibility of the fluid, i.e. the density is a
              constant, both in space and time.
              The Navier-Stokes equations are nonlinear, due to the term (u·∇)u.
                                                                                                 4 of 53