ch7非线性方程求根

数值分析ComputationalMethod,Chapter7非线性方程求根,第7章非线性方程求根71方程求根与二分法,1.引言设若有使则称是方程的根或的零点。若，当时,称为方程的单根，当时,称为方程的m重根或的m重零点。,定理若有m阶导数，则是的m重根的充分必要条件是，。,证明:依据泰勒中值定理知.,泰勒公式：,2.二分法,零点定理若又则。依据零点定理对区间逐次分半进行根的搜索，这就是二分法。,，,；,具体作法如下：,设,，,令,，,（1）若,，则,是根；,（2）若,，令,；,（3）若,，令,。,对,再二分且同样的讨论，得,和一半的区间,将此过程继续下去，得,则,。,定理设又则由二分法得到的收敛于根，且有根的近似值误差估计式：。,72迭代法及收敛性1.不动点迭代法的概念,将改写成等价形式。若有使,则将称为的不动点。求的根,也就是找的不动点。设选择（初始近似值）并构造（2.2）计算公式（2.2）称为迭代格式,称为迭代函数,得到的称为迭代序列,用公式（2.2）逐步代入求近似解的方法称为迭代法(或不动点迭代法)。,若,则称迭代收敛,否则,就称迭代发散。若,迭代都收敛，则称迭代全局收敛。,压缩映象原理设若(1)当时，有，(2)使有则使。,证明,压缩映象原理证明,证存在性。令,（1）,，则,（2）,，则,（3）,，据零点定理，,，使,。,；,；,证唯一性。若另有,是不动点，,这与,矛盾。证毕,2.全局收敛,全局收敛性定理设若时，有;，使有迭代公式则,迭代法收敛，且有以下估计式,（1）,（2）,（3）,证明,，,证（1）,又由于,是固定数，而,，所以，,，迭代收敛。,证（2）,所以，,注：全局收敛性定理中条件(2)换成,，定理结论仍成立。,证（3）因而,证毕,据拉格朗日定理，,3局部收敛和p阶收敛,定义若是的不动点，,使,由迭代公式产生的序列，有，则称迭代局部收敛。,定义若,局部收敛性定理是的不动点，在连续，迭代公式，则(1)当时，迭代局部收敛；(2)当时，迭代发散。,证明由于,存在，故,当,时，,存在，,连续。且由,极限的保号性，当,时,，,使,；当,时，有,。,满足(2);当,时，,满足（1）；据全局收敛定理,在,上收敛。,当,时，,所以，,，,，迭代不收敛。,证毕,定义设，若，则称迭代过程是p阶收敛。特别地，p=1称为线性收敛，p1称为超线性收敛，p=2称为平方收敛。,定理若,则迭代过程是p阶收敛。,证明,证毕,例设方程，根,将方程改写成下列等价形式：（1）；（2）；（3）。试建立相应的迭代格式，并分析它们的收敛性，然后选取一个格式作为计算公式。,解（1）,，,；,，,；,，,。,（2）,（3）,，,，,收敛；,，,，不收敛；,，,，收敛。,因为，,，取,作为计算公式。,解毕,74牛顿法（切线法）,其牛顿迭代函数由解出得。,例设用牛顿迭代法求方程,内的根，,在,取,，要求,。,解,，,，,因为,所以,解毕,1牛顿迭代法及其收敛性,例设,写出用牛顿法求的迭代计算公式，并分析收敛性。,解,令,，,取,所以，,单减有下界，,存在，于是，对本题计算公,式取极限，,有,，说明，本题计算公式在,上全局收敛。,解毕,牛顿迭代函数设是的单根，即,。,故，牛顿法在邻近至少是2阶收敛的。,。,2简化牛顿法,特别即牛顿法。,75弦截法与抛物线法3弦截法,取是1步迭代法，1阶收敛,4快速弦截法,取是2步迭代法，1618阶收敛,5抛物线法（密勒法）,若用三点,连接成抛物线取与轴上靠近的交点当作的近似值。该法称作抛物线法或密勒法.计算公式为,是3步迭代法，1840阶收敛.,证明,二次牛顿插值,其中,令,解出,号取与,符号相同，即,6牛顿下山法（全局收敛）,的解,，则,若视,为,在,处的高度，则,是山谷的最低点，,若,有,，则,是一个下山序列,若,，且,，,，,取,，,，例取,7重根情形,复习定理若有k阶导数，则是的k重根的充分必要条件是，。,牛顿迭代函数,，,，收敛。,，,所以，收敛是1阶收敛。,(1)已知重数k,修改牛顿迭代函数,，收敛是2阶收敛。,2.重数k未知,设,迭代函数,，则,是,的单零点.,收敛是2阶收敛。,73迭代收敛的加速方法1.埃特金加速法,设,是1阶收敛,，且有,相除得：,即：,解出：,埃特金加速法,2.斯蒂芬森迭代法,斯蒂芬森迭代,由于,，,新迭代函数,76非线性方程组的解法,非线性方程组,两种解法:不动点迭代法(简单迭代法)牛顿迭代法,1不动点迭代法（简单迭代法）,改写成等价形式,简单迭代法：压缩映象原理和收敛性定理也成立。,2.牛顿迭代法,雅可比矩阵,牛顿迭代法,例写出解以下非线性方程组的迭代格式,解,简单迭