Adjoint Tangent Rank-1 updates.pdf

nstitute of cientific omputing IS C Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook Local convergence results of quasi-Newton methods using the Adjoint Tangent Rank-1 update Sebastian Schlenkrich1 Andreas Griewank2 Andrea Walther1 1Institute für Wissenschaftliches Rechnen, Technische Universit?t Dresden 2Institut für Mathematik, Humold Universit?t Berlin Südostdeutsches Kolloquium 2006, Martin-Luther-Universit?t Halle-Wittenberg Supported by DFG grant WA 1607/2-1 and DFG Research Center MATHEON nstitute of cientific omputing IS C Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook Outline Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook nstitute of cientific omputing IS C Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook Outline Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook nstitute of cientific omputing IS C Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook Nonlinear equation system Problem ? F : Rn ? Rn differentiable ? x? ∈ Rn with F (x?) = 0 ? F ′(x?) nonsingular, F ′ L-continuous in x? with constant L Quasi-Newton method for i = 0,1,2, . . . ? compute iterate xi+1 = xi ? A?1i F (xi) ? update Ai 7→ Ai+1 end nstitute of cientific omputing IS C Quasi-Newton methods for nonlinear equations Adjoint Tangent Rank-1 updates Numerical results Conclusions and outlook Motivation Choices for Ai ? Ai = F ′(xi) (Newton’s method) + local quadratic convergence – Jacobian evaluation in each iteration – linear algebra effort O(n3) per iteration ? Ai = A (constant iteration matrix) – at most local linear convergence (except if A = F ′(x?)) + no repeated Jacobian evaluation +