- A sufficiently exact inexact Newton step based on reusing matrix information Anders Forsgren (andersf kth.se) Abstract: Newton's method is a classical method for solving a nonlinear equation \$F(z)=0\$. We derive inexact Newton steps that lead to an inexact Newton method, applicable near a solution. The method is based on solving for a particular \$F'(z_{k'})\$ during \$p\$ consecutive iterations \$k=k',k'+1,\dots,k'+p-1\$. One such \$p\$-cycle requires \$2^p-1\$ solves with the matrix \$F'(z_{k'})\$. If matrix factorization is used, it is typically more computationally expensive to factorize than to solve, and we envisage that the proposed inexact method would be useful as the iterates converge. The inexact method is shown to be \$p\$-step convergent with \$Q\$-factor \$2^p\$ under standard assumptions where Newton's method has quadratic rate of convergence. The method is thus sufficiently exact in the sense that it mimics the convergence rate of Newton's method. It may interpreted as a way of performing iterative refinement by solving the subproblem \$F(z_k) + F'(z_k)d=0\$ sufficiently exactly by a simplified Newton method. The method is contrasted to a simplified Newton method, where it is known that a cycle of \$2^p-1\$ iterations gives the same type of convergence. We present some numerical results and also discuss how this method might be used in the context of interior methods for linear programming. Keywords: Nonlinear equations, Newton's method, inexact Newton method, simplified Newton method Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Technical Report TRITA-MAT-2009-OS7, Department of Mathematics, Royal Institute of Technology, November 2009. Download: [PDF]Entry Submitted: 11/27/2009Entry Accepted: 11/27/2009Entry Last Modified: 11/27/2009Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society. 