《非线性方程的数值解法》由会员分享，可在线阅读，更多相关《非线性方程的数值解法（19页珍藏版）》请在金锄头文库上搜索。
1、4 牛顿法牛顿法一、牛顿迭代公式的推导一、牛顿迭代公式的推导(Taylor展开法展开法)思想：思想：非线性方程线性化非线性方程线性化（以直代曲）（以直代曲）取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:， 在在 x0 和和 x 之间之间将将 (x* x0)2 看成看成高阶小量高阶小量，则有：，则有：令令注：牛顿法是一种特殊的迭代法。注：牛顿法是一种特殊的迭代法。Newton Raphson迭代格式迭代格式称之为称之为牛顿牛顿拉夫森拉夫森方法，简称方法，简称牛顿法牛顿法.xyx*x0与与x轴交点的横坐标轴交点的横坐标无开方运算，又无除法运算。无开方运算，又无除法
2、运算。例例1 1：写出求写出求 的的Newton迭代格式；迭代格式； 写出求写出求 的的Newton迭代格式迭代格式, ,要求公式中既要求公式中既解：解：等价于求方程等价于求方程 的正的正根根解法一：解法一：等价于求方程等价于求方程 的正的正根根解法二：解法二：等价于求方程等价于求方程 的正的正根根 Th2.7 （局部收敛性局部收敛性） 设设 x* 为方程为方程 f (x) =0的根，在包含的根，在包含x*的某个开区间内的某个开区间内 连续，连续， 且且 ，则存在，则存在 x* 的邻域的邻域 ，使得任取初值，使得任取初值 ，由，由Newtons Method产生的序列产生的序列 以以不低于二阶
3、不低于二阶的收敛速度收敛于的收敛速度收敛于x*，且，且证明：证明：Newtons Method 事实上是一种事实上是一种特殊的不动点迭代特殊的不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开： 只要只要 ，则令，则令 可得结论。可得结论。Th2.5有根有根根唯一根唯一产生的序列产生的序列单调有单调有界界保证收敛保证收敛证明省略。证明省略。Th2.8 （收敛的充分条件收敛的充分条件）设设f (x) =0 且且f C2a, b，若，若(1) f (a) f (b) 0；(2) 在整个在整个a, b上上 不变号且不变号且 ；(3) 选取选取 x0 a, b 使得使得 ；则则New
4、tons Method产生的序列产生的序列 xk 收敛于方程的根收敛于方程的根 .Th2.9 （收敛的另一充分条件收敛的另一充分条件）设设 在在a, b上连续，上连续， (1) f (a) f (b) 0；(2) 在整个在整个a, b上上 且且 ；(3) ，则对则对 ，Newtons Method产生的序列产生的序列 xk 收敛于方收敛于方程程 在在a, b内内的唯一实根的唯一实根 。且且证明省略。证明省略。注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0改进与推广（改进与推广（补充补充） 重根重根 加速收敛法：加速收敛法：Q1:
5、 若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x* 是是 f 的的 n 重根，则：重根，则： 且且 。因为因为 Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代, ,其其中中 ，则，则A1: 有局部收敛性，但重数有局部收敛性，但重数 n 越高越高，收敛，收敛越慢越慢。Q2: 如何如何加速加速重根情况时的收敛速度？重根情况时的收敛速度？A2: 将求将求 f 的的重根转化重根转化为求另一函数的为求另一函数的单根单根。令，则令，则 f 的重根的重根 = = 的单根。的单根。 求复根求复根 Newton 公式中的自变量可以是公式中的自变量可
6、以是复数复数记记 z = x + i y, z0 为初值，同样有为初值，同样有设设代入公式，令代入公式，令实、虚部对应相等实、虚部对应相等，可得，可得 5 弦割法与抛物线法弦割法与抛物线法 x0x1割线割线 切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。Newtons Method每一步要计算每一步要计算 ，为了避免计算导数值，为了避免计算导数值，现用现用 的近似，得到的近似，得到弦割法弦割法（割线法割线法）。）。x2一、弦割法一、弦割法Th2.10 局部收敛性局部收敛性 设设 表示区间表示区间 ， x*为方程为方程 f (x) =0的根，的根， 函数函数f (x
7、)在在 中有中有足够阶连续导数足够阶连续导数， 且且 满足满足 则对则对 ，由割线法产生的序列，由割线法产生的序列 都收敛于都收敛于x*，且，且(i) (ii) (iii) 其中其中收敛速度介于收敛速度介于Newton and Bisection 之间之间 Corollary(推论推论) 设设 x* 为方程为方程 f (x) =0的一个根，的一个根， ， 且且 在在 x* 的附近连续，则的附近连续，则 使得使得 由由Secant Method产生的序列产生的序列 都收敛于都收敛于x*。xk-2Muller方法的思想来源于方法的思想来源于弦割法弦割法: :利用利用3个已知点构造一条抛物个已知点构
8、造一条抛物线线, ,取其与取其与x轴的交点构造下一次迭代值轴的交点构造下一次迭代值. .x*二、抛物线法二、抛物线法(Muller)几何图示几何图示xkxk-1xk+1 Muller方法的具体实现方法的具体实现: :设已知三个点设已知三个点则过上述三个点的则过上述三个点的抛物线方程抛物线方程为为: :取该抛物线与取该抛物线与x轴的交点作为下一次迭代值轴的交点作为下一次迭代值, ,即即然后取新的相邻的三次迭代值重复上述过程然后取新的相邻的三次迭代值重复上述过程, ,即为即为Muller方法方法. Muller方法中抛物线根的计算方法方法中抛物线根的计算方法: :首先要将抛物线化为首先要将抛物线化
9、为规范形式规范形式: :引入新的变量引入新的变量其中其中的两个零点为的两个零点为: :可以写为：可以写为：取取 的两个零点中靠近的两个零点中靠近 的那个零点的那个零点, ,则有则有 Muller方法的迭代公式为方法的迭代公式为: :具体计算步骤见教材具体计算步骤见教材P39. 算法算法: : Muller方法方法给定初始近似值给定初始近似值 x0 ， x1 ， x2 ,求求f(x) =0 的根的根. .输入输入: : 初值初值 x0 ， x1， x2; ; 容许误差容许误差 TOL.输出输出: 近似解近似解 x.Step 1 Set i = 1; Step 4 If |t4(x2-x1) |
10、TOLStep 2 do steps 3-7 then Output (x); STOP; Step 3 Compute t3= (x2 x1)/ (x1 x0); Step 5 Set i +; d3= 1+t3; Step 6 Set x0 = x1 , x1=x2 , x2=x; a=f(x0)t32-f(x1)t3d3+f(x2)t3; Step 7 goto Step 2. b=f(x0)t32-f(x1)d32+f(x2)(t3+d3); c=f(x2)d3 ; t4=-2c/b+sign(b)sqrt(b2-4ac); x= x2+t4(x2-x1);Th2.5.2 （局部收敛性局部收敛性） 设设 ， 在在x*的某邻域内连续，则的某邻域内连续，则存存在在 x* 的一个邻域的一个邻域 ，当，当 时时,由由抛物线法抛物线法产生的序列产生的序列 收敛于收敛于x*，且，且其中其中 , ,是方程是方程 的根的根. . Muller法法的优点：初值的选取范围比的优点：初值的选取范围比Newton法和法和弦割法弦割法宽宽, ,但计算量比弦割法大。进一步研究可知但计算量比弦割法大。进一步研究可知MullerMuller法可求复根。法可求复根。
