GLOBALLY CONVERGENT INEXACT NEWTON METHODS

被引:317
作者
EISENSTAT, SC
WALKER, HF
机构
[1] YALE UNIV,SCI COMPUTAT RES CTR,NEW HAVEN,CT 06520
[2] UTAH STATE UNIV,DEPT MATH & STAT,LOGAN,UT 84322
关键词
INEXACT NEWTON METHODS; NEWTON ITERATIVE METHODS; TRUNCATED NEWTON METHODS; NEWTONS METHOD; GLOBALLY CONVERGENT NEWTON-LIKE METHODS; GLOBAL CONVERGENCE ANALYSES FOR NEWTON-LIKE METHODS;
D O I
10.1137/0804022
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Inexact Newton methods for finding a zero of F : R(n) --> R(n) are variations of Newton's method in which each step only approximately satisfies the linear Newton equation but still reduces the norm of the local linear model of F. Here, inexact Newton methods are formulated that incorporate features designed to improve convergence from arbitrary starting points. For each method, a basic global convergence result is established to the effect that, under reasonable assumptions, if a sequence of iterates has a limit point at which F' is invertible, then that limit point is a solution and the sequence converges to it. When appropriate, it is shown that initial inexact Newton steps are taken near the solution, and so the convergence can ultimately be made as fast as desired, up to the rate of Newton's method, by forcing the initial linear residuals to be appropriately small. The primary goal is to introduce and analyze new inexact Newton methods, but consideration is also given to ''globalizations'' of (exact) Newton's method that can naturally be viewed as inexact Newton methods.
引用
收藏
页码:393 / 422
页数:30
相关论文
共 18 条
[2]   GLOBAL APPROXIMATE NEWTON METHODS [J].
BANK, RE ;
ROSE, DJ .
NUMERISCHE MATHEMATIK, 1981, 37 (02) :279-295
[3]   INEXACT NEWTON METHODS [J].
DEMBO, RS ;
EISENSTAT, SC ;
STEIHAUG, T .
SIAM JOURNAL ON NUMERICAL ANALYSIS, 1982, 19 (02) :400-408
[4]  
DENNIS JE, 1983, SERIES AUTOMATIC COM
[5]  
Deuflhard P., 1991, Impact of Computing in Science and Engineering, V3, P366, DOI 10.1016/0899-8248(91)90004-E
[6]  
ELHALLABI M, 1987, THESIS RICE U HOUSTO
[7]  
ELHALLABI M, 1989, TR8725 RIC U DEP MAT
[8]  
Elman H. C., 1982, THESIS YALE U NEW HA
[9]  
GOLDSTEIN AA, 1967, CONSTRUCTIVE REAL AN
[10]  
Kantorovich LV, 1982, FUNCTIONAL ANAL