用Newton型分裂方法求解非线性方程组
|
摘要
对于牛顿型迭代格式等经典的算法,近年来经过很多学者的研究已经取得了丰硕的理论成果,包括收敛性定理、Kantorovich型定理和误差估计。局部收敛性定理事先假定了方程组有解存在,并且初始近似与解充分接近,则迭代序列收敛到方程组的解。然而对计算理论更为重要的是存在性、收敛性定理。在不知道解的情况下能够验证收敛条件,并且往往同时可以断定解的存在性乃至唯一性,因此对于各种迭代法建立存在性收敛性定理,始终是迭代法理论研究的中心课题之一。对于求解非线性方程组的Newton型分裂方法和离散Newton型分裂方法,Jochen W.Schmidt,Wolfgang Hoyer和Christian Haufe只给出了局部收敛性定理,并没有给出Kantorovich型存在性、收敛性定理,因此研究用分裂迭代格式求解非线性方程组,并给出Kantorovich型存在性收敛性定理,是对非线性方程组理论体系的完善,因此具有重要的理论意义。
本文研究了用Newton型分裂方法求解非线性方程组,给出了Kantorovich型存在性、收敛性定理。全文共分四部分。第一章,在绪论部分主要阐述了国内外有关求解非线性方程组研究的发展概况,并介绍了本文的主要研究内容、课题背景和研究意义。第二章,给出了Newton型分裂方法的Kantorovich型定理。第三章,给出了离散Newton型分裂方法的Kantorovich型定理。第四章,给出了半离散Newton型分裂方法的Kantorovich型定理。完善了Newton型分裂方法的收敛性定理。
Rich theoretical results of Newton-type iterative scheme and other classical algorithms have been made by many scholars in recent years,including convergence theorem,Kantorovich-type theorem and error estimate.The local convergence theorem assumpts that the solution of nonlinear system of equations exists,moreover the initial approximation approaches the solution sufficiently. But the existence and convergence theorem is more important to the theory of computation.We can verify the convergence conditions when we don't know about the situation of the solution,and assert the existence and uniqueness of the solution.Therefore,establishing the existence and convergence theorems for all kinds of the iteration methods has always been one of the center of theoretical analysis in iteration method.Jochen W.Schmidt,Wolfgang Hoyer and Christian Haufe only gave the local convergence theorems of Newton-type decomposition methods and discrete Newton-type decomposition methods for solving nonlinear system of equations.Therefore,researching Newton-type decomposition methods for solving nonlinear system of equations and giving the Kantorovich-type existence and convergence theorem will improve and perfect the theoretical system of nonlinear system of equations.Therefore,it has very important theoretical significance.
In this paper,the Newton-type decomposition methods have been applied in solving the nonlinear system of equations,moreover,Kantorovich-type theorems are given.There are four parts in this paper.In the first chapter,the solving nonlinear system of equations development at home and abroad,the main contents,background and significance are introduced in the preface.In the second chapter,the Kantorovich-type theorem for Newton-type decomposition methods is given.In the third chapter,the Kantorovich-type theorem for discrete Newton-type decomposition methods is given.In the fourth chapter,the Kantorovich-type theorem for semi-discrete Newton-type decomposition methods is given.The theory of convergence theorem of Newton-type decomposition methods has been perfected.
本文研究了用Newton型分裂方法求解非线性方程组,给出了Kantorovich型存在性、收敛性定理。全文共分四部分。第一章,在绪论部分主要阐述了国内外有关求解非线性方程组研究的发展概况,并介绍了本文的主要研究内容、课题背景和研究意义。第二章,给出了Newton型分裂方法的Kantorovich型定理。第三章,给出了离散Newton型分裂方法的Kantorovich型定理。第四章,给出了半离散Newton型分裂方法的Kantorovich型定理。完善了Newton型分裂方法的收敛性定理。
Rich theoretical results of Newton-type iterative scheme and other classical algorithms have been made by many scholars in recent years,including convergence theorem,Kantorovich-type theorem and error estimate.The local convergence theorem assumpts that the solution of nonlinear system of equations exists,moreover the initial approximation approaches the solution sufficiently. But the existence and convergence theorem is more important to the theory of computation.We can verify the convergence conditions when we don't know about the situation of the solution,and assert the existence and uniqueness of the solution.Therefore,establishing the existence and convergence theorems for all kinds of the iteration methods has always been one of the center of theoretical analysis in iteration method.Jochen W.Schmidt,Wolfgang Hoyer and Christian Haufe only gave the local convergence theorems of Newton-type decomposition methods and discrete Newton-type decomposition methods for solving nonlinear system of equations.Therefore,researching Newton-type decomposition methods for solving nonlinear system of equations and giving the Kantorovich-type existence and convergence theorem will improve and perfect the theoretical system of nonlinear system of equations.Therefore,it has very important theoretical significance.
In this paper,the Newton-type decomposition methods have been applied in solving the nonlinear system of equations,moreover,Kantorovich-type theorems are given.There are four parts in this paper.In the first chapter,the solving nonlinear system of equations development at home and abroad,the main contents,background and significance are introduced in the preface.In the second chapter,the Kantorovich-type theorem for Newton-type decomposition methods is given.In the third chapter,the Kantorovich-type theorem for discrete Newton-type decomposition methods is given.In the fourth chapter,the Kantorovich-type theorem for semi-discrete Newton-type decomposition methods is given.The theory of convergence theorem of Newton-type decomposition methods has been perfected.
引文
[1]黄象鼎,曾钟钢,马亚南.非线性数值分析的理论与方法[M].武汉:武汉大学出版社,2004:57-105.
[2]孙学思,宁石英.用牛顿型分解法解非线性方程组[J].电机与控制学报,1988,11(3):296-301.
[3]王贺元.一类分歧问题的扩充系统[J].河北师范大学学报:自然科学版,2000,24(4):436-438.
[4]DEUFLHARD P.Newton Methods for Nonlinear Problems Affine Invariance and Adaptive Algorithms[M].北京:科学出版社,2006:46-98.
[5]BUS J C P.Convergence of Newton-like Methods for Solving Systems of Nonlinear Equations[J].Numerische Mathematik,1976,27(3):271-281.
[6]ALEM M M,SAYED S,SOBKY B.Local Convergence of the Interior-Point Newton Method for General Nonlinear Programming[J].Journal of Optimization Theory and Applications,2004,120(3):487-502.
[7]KANTOROVICH L.On Newton's Method[J].Trudy Mat Inst Steklov,1949,28(1):104-144.
[8]OSTROWSHI A M.Solutions of Equations in Euclidean and Banach Spaces [M].New York:Academic Press,1973:65-96.
[9]OSTROWSHI A M.Simultaneous Systems of Equations[J].Not.Bur.Stand.Appl.Math,1960,29(29):29-34.
[10]YAMAMOTO T.A Method for Findings Sharp Error Bounds for Newton's Method Under the Kantorovich Assumptions[J].Numer.Math.,1986,6(49):203-220.
[11]YAMAMOTO T.On the Method of Tangent Hyperbolas in Banach Spaces[J].J.Comput.Appl.Math.,1988,7(21):75-86.
[12]CHEN X J,YAMAMOTO Tetsuro.Newton-like Methods for Solving Underdetermined Nonlinear Equations with Nondifferentiable Terms[J].Journal of Computational and Applied Mathematics,1994,2(55):311-324.
[13]FLORIAN A P.The Kantorovich Theorem and Interior Point Methods[J].Mathematical Programming,2005,102(1):47-70.
[14]WANG X H,LI C.Convergence of Newton's Method and Uniqueness of The Solution of Equations in Banach Spaces Ⅱ[J].Acta,Mathematica Sinica, 2003,19(2):405-412.
[15]王兴华,郭学萍.Newton法及其各种变形收敛性的统一判定法则[J].高等学校计算数学学报,1999,29(4):363-368.
[16]王兴华,韩丹夫,孙方裕.若干变形Newton迭代的点估计[J].计算数学,1990,12(2):145-156.
[17]THORLUND-PETERSEN Lars.Global Convergence of Newton's Method on An Interval[J].Mathematical Methods of Operations Research,2004,59(1):91-110.
[18]YAKOVLEV M N.A Convergence Theorem for The Newton Method[J].Journal of Mathematical Sciences,2000,101(4):3372-3375.
[19]LAMPARIELLO F,SCIANDRONE M.Global Convergence Technique for The Newton Method with Periodic Hessian Evaluation[J].Journal of Optimization Theory and Applications,2001,111(2):341-358.
[20]张萍,张弢.非线性方程组的Newton法及Newton型迭代法收敛性分析[J].沈阳大学学报,2002,14(4):101-103.
[21]王树忠,潘状元,张国志.关于简化Newton法的一个注记[J].1997,2(3):86-89。
[22]HUANG Z D.A Note on The Kantorovich Theorem for Newton Iteration[J].Comp.and Appl.Math.,1993,(47):211-217.
[23]黄正达.不精确牛顿方法的收敛性[J].浙江大学学报:理学版,2003,30(4):393-396.
[24]余沛.广义简化牛顿迭代收敛研究[J].重庆交通学院学报,2006,25(2):158-159.
[25]IOANNIS K.ARGYROS.A Convergence Analysis and Applications for Two Point Newton-like Methods in Banach Space under Relaxed Conditions[J].Aequationes Mathematicae,2006,71(1-2):124-148.
[26]HUANG Z H,SUN D F,ZHAO G Y.A Smoothing Newton-Type Algorithm of Stronger Convergence for The Quadratically Constrained Convex Quadratic Programming[J].Computational Optimization And Applications,2006,35(2):199-237.
[27]郑权,黄松奇.解非线性方程的Newton类方法及其变形[J].清华大学学报:自然科学版,2004,44(3):372-375.
[28]郑权,刘忠礼.Newton-like方法的收敛性及其应用[J].高等学校计算数 学学报,2005,27(S1):232-237.
[29]徐秀斌.具有常秩导数非线性方程组的牛顿迭代的Kantorovich型收敛性[J].浙江师范大学学报:自然科学版,2006,29(1):11-16.
[30]蒋青松,蒋茂旺.牛顿法的改进及其在Banach空间中的收敛性[J].数学理论与应用,2006,26(4):100-103.
[31]朱静芬,韩丹夫.“牛顿类”迭代的收敛性和误差估计[J].浙江大学学报:理学版,2005,32(6):623-626.
[32]邹健,宋述刚,陈忠.一个用割线法求解非线性方程组的异步并行算法[J].太原师范学院学报:自然科学版,2006,5(2):9-10.
[33]郭学萍,丰静.一类变形Newton法的收敛性[J].浙江大学学报:理学版,2006,33(4):389-392.
[34]游兆永,张讲社.Newton类方法的Kantorovich型收敛定理[J].西安交通大学学报,1993,27(5):125-126.
[35]吴淦洲.基于新拟牛顿方程的拟牛顿法的超线性收敛性分析[J].太原师范学院学报:自然科学版,2007,6(1):21-23.
[36]吴淦洲.求解非线性方程组的非精确牛顿法[J].茂名学院学报,2007,17(6):69-71.
[37]王娟.Hilbert空间中算子方程的不精确拟牛顿法的局部收敛性分析[D].大连:大连理工大学,2006:12-16.
[38]刘忠礼.不精确Newton-like方法及应用[D].北京:北方工业大学,2007:15-23.
[39]王伟.不精确拟牛顿法的收敛性[D].大连:大连理工大学,2006:6-12.
[40]田志远.一维离散牛顿法的收敛性(为庆贺游兆永教授60寿辰而作)[J].工程数学学报,1991,8(2):203-207.
[41]韩波,刘家琦.牛顿-正则化方法及应用[J].计算物理,1993,10(3):379-384.
[42]陈志,高旅端,邓乃扬.解非线性方程组的一类离散的Newton算法[J].1998,20(1):57-68.
[43]HOYER W,SCHMIDT J W.Newton-type Decomposition Methods for Equations Arising in Network Analysis[J].Z.Angew.Math.Mech.,1984,64(2):397-405.
[44]JOCHEN W,HOYER W,HAUFE Christian.Consistent Approximations in Newton-Type Decomposition Methods[J].Numer.Math.,1985,47(3):413- 425.
[45]冯国忱.非线性方程组迭代解法[M].上海:上海科学技术出版社,1989:49-142.
[2]孙学思,宁石英.用牛顿型分解法解非线性方程组[J].电机与控制学报,1988,11(3):296-301.
[3]王贺元.一类分歧问题的扩充系统[J].河北师范大学学报:自然科学版,2000,24(4):436-438.
[4]DEUFLHARD P.Newton Methods for Nonlinear Problems Affine Invariance and Adaptive Algorithms[M].北京:科学出版社,2006:46-98.
[5]BUS J C P.Convergence of Newton-like Methods for Solving Systems of Nonlinear Equations[J].Numerische Mathematik,1976,27(3):271-281.
[6]ALEM M M,SAYED S,SOBKY B.Local Convergence of the Interior-Point Newton Method for General Nonlinear Programming[J].Journal of Optimization Theory and Applications,2004,120(3):487-502.
[7]KANTOROVICH L.On Newton's Method[J].Trudy Mat Inst Steklov,1949,28(1):104-144.
[8]OSTROWSHI A M.Solutions of Equations in Euclidean and Banach Spaces [M].New York:Academic Press,1973:65-96.
[9]OSTROWSHI A M.Simultaneous Systems of Equations[J].Not.Bur.Stand.Appl.Math,1960,29(29):29-34.
[10]YAMAMOTO T.A Method for Findings Sharp Error Bounds for Newton's Method Under the Kantorovich Assumptions[J].Numer.Math.,1986,6(49):203-220.
[11]YAMAMOTO T.On the Method of Tangent Hyperbolas in Banach Spaces[J].J.Comput.Appl.Math.,1988,7(21):75-86.
[12]CHEN X J,YAMAMOTO Tetsuro.Newton-like Methods for Solving Underdetermined Nonlinear Equations with Nondifferentiable Terms[J].Journal of Computational and Applied Mathematics,1994,2(55):311-324.
[13]FLORIAN A P.The Kantorovich Theorem and Interior Point Methods[J].Mathematical Programming,2005,102(1):47-70.
[14]WANG X H,LI C.Convergence of Newton's Method and Uniqueness of The Solution of Equations in Banach Spaces Ⅱ[J].Acta,Mathematica Sinica, 2003,19(2):405-412.
[15]王兴华,郭学萍.Newton法及其各种变形收敛性的统一判定法则[J].高等学校计算数学学报,1999,29(4):363-368.
[16]王兴华,韩丹夫,孙方裕.若干变形Newton迭代的点估计[J].计算数学,1990,12(2):145-156.
[17]THORLUND-PETERSEN Lars.Global Convergence of Newton's Method on An Interval[J].Mathematical Methods of Operations Research,2004,59(1):91-110.
[18]YAKOVLEV M N.A Convergence Theorem for The Newton Method[J].Journal of Mathematical Sciences,2000,101(4):3372-3375.
[19]LAMPARIELLO F,SCIANDRONE M.Global Convergence Technique for The Newton Method with Periodic Hessian Evaluation[J].Journal of Optimization Theory and Applications,2001,111(2):341-358.
[20]张萍,张弢.非线性方程组的Newton法及Newton型迭代法收敛性分析[J].沈阳大学学报,2002,14(4):101-103.
[21]王树忠,潘状元,张国志.关于简化Newton法的一个注记[J].1997,2(3):86-89。
[22]HUANG Z D.A Note on The Kantorovich Theorem for Newton Iteration[J].Comp.and Appl.Math.,1993,(47):211-217.
[23]黄正达.不精确牛顿方法的收敛性[J].浙江大学学报:理学版,2003,30(4):393-396.
[24]余沛.广义简化牛顿迭代收敛研究[J].重庆交通学院学报,2006,25(2):158-159.
[25]IOANNIS K.ARGYROS.A Convergence Analysis and Applications for Two Point Newton-like Methods in Banach Space under Relaxed Conditions[J].Aequationes Mathematicae,2006,71(1-2):124-148.
[26]HUANG Z H,SUN D F,ZHAO G Y.A Smoothing Newton-Type Algorithm of Stronger Convergence for The Quadratically Constrained Convex Quadratic Programming[J].Computational Optimization And Applications,2006,35(2):199-237.
[27]郑权,黄松奇.解非线性方程的Newton类方法及其变形[J].清华大学学报:自然科学版,2004,44(3):372-375.
[28]郑权,刘忠礼.Newton-like方法的收敛性及其应用[J].高等学校计算数 学学报,2005,27(S1):232-237.
[29]徐秀斌.具有常秩导数非线性方程组的牛顿迭代的Kantorovich型收敛性[J].浙江师范大学学报:自然科学版,2006,29(1):11-16.
[30]蒋青松,蒋茂旺.牛顿法的改进及其在Banach空间中的收敛性[J].数学理论与应用,2006,26(4):100-103.
[31]朱静芬,韩丹夫.“牛顿类”迭代的收敛性和误差估计[J].浙江大学学报:理学版,2005,32(6):623-626.
[32]邹健,宋述刚,陈忠.一个用割线法求解非线性方程组的异步并行算法[J].太原师范学院学报:自然科学版,2006,5(2):9-10.
[33]郭学萍,丰静.一类变形Newton法的收敛性[J].浙江大学学报:理学版,2006,33(4):389-392.
[34]游兆永,张讲社.Newton类方法的Kantorovich型收敛定理[J].西安交通大学学报,1993,27(5):125-126.
[35]吴淦洲.基于新拟牛顿方程的拟牛顿法的超线性收敛性分析[J].太原师范学院学报:自然科学版,2007,6(1):21-23.
[36]吴淦洲.求解非线性方程组的非精确牛顿法[J].茂名学院学报,2007,17(6):69-71.
[37]王娟.Hilbert空间中算子方程的不精确拟牛顿法的局部收敛性分析[D].大连:大连理工大学,2006:12-16.
[38]刘忠礼.不精确Newton-like方法及应用[D].北京:北方工业大学,2007:15-23.
[39]王伟.不精确拟牛顿法的收敛性[D].大连:大连理工大学,2006:6-12.
[40]田志远.一维离散牛顿法的收敛性(为庆贺游兆永教授60寿辰而作)[J].工程数学学报,1991,8(2):203-207.
[41]韩波,刘家琦.牛顿-正则化方法及应用[J].计算物理,1993,10(3):379-384.
[42]陈志,高旅端,邓乃扬.解非线性方程组的一类离散的Newton算法[J].1998,20(1):57-68.
[43]HOYER W,SCHMIDT J W.Newton-type Decomposition Methods for Equations Arising in Network Analysis[J].Z.Angew.Math.Mech.,1984,64(2):397-405.
[44]JOCHEN W,HOYER W,HAUFE Christian.Consistent Approximations in Newton-Type Decomposition Methods[J].Numer.Math.,1985,47(3):413- 425.
[45]冯国忱.非线性方程组迭代解法[M].上海:上海科学技术出版社,1989:49-142.