《第二章 非线性方程的数值解法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章 非线性方程的数值解法PPT讲稿.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 非线性方程的数值解法第1页，共19页，编辑于2022年，星期二取取满足满足因此，选取迭代函数因此，选取迭代函数Newton Raphson迭代格式迭代格式称之为称之为牛顿牛顿拉夫森拉夫森方法，简称方法，简称牛顿法牛顿法原理：原理：将非线性方程将非线性方程线性化线性化取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x 之间之间2、Taylor展开法展开法/*Taylors expansion Method*/第2页，共19页，编辑于2022年，星期二将将(x*x0)2 看成看成高阶小量高阶小量，则有：，则有：xyx*x0只要只要 f C1
2、，每一步迭代都有，每一步迭代都有 而且而且 ，则，则 x*就是就是 f 的根。的根。与与x轴交点的横坐标轴交点的横坐标第3页，共19页，编辑于2022年，星期二无开方运算，又无除法运算。无开方运算，又无除法运算。例例1 1：写出求写出求 的的Newton迭代格式；迭代格式；写出求写出求 的的Newton迭代格式迭代格式,要求公式中既要求公式中既解：解：等价于求方程等价于求方程 的正根的正根等价于求方程等价于求方程 的正根的正根第4页，共19页，编辑于2022年，星期二Th2.7 （局部收敛性局部收敛性）设设 x*为方程为方程 f(x)=0的根，在包含的根，在包含x*的某个开区间内的某个开区间内
3、 连续，连续，且且 ，则存在，则存在 x*的邻域的邻域 ，使得任取，使得任取初值初值 ，由，由Newtons Method产生的序列产生的序列 以不低于以不低于二阶二阶的收敛速度收敛于的收敛速度收敛于x*，且，且第5页，共19页，编辑于2022年，星期二证明：证明：Newtons Method 事实上是一种事实上是一种特殊的不动点迭代特殊的不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开：在单根/*simple root*/附近收敛快只要只要 ，则令，则令 可得结论。可得结论。第6页，共19页，编辑于2022年，星期二有根根唯一产生的序列单调有界保证收敛Th2.8 （收敛的
4、充分条件收敛的充分条件）设设f(x)=0 且且f C2a,b，若，若(1)f(a)f(b)0；(2)在整个在整个a,b上上 不变号且不变号且 ；(3)选取选取 x0 a,b 使得使得 ；则则Newtons Method产生的序列产生的序列 xk 收敛于方程的根收敛于方程的根 ,且且第7页，共19页，编辑于2022年，星期二注：注：Newtons Method 收敛性依赖于x0 的选取。x*x0 x0 x0Th2.9 （收敛的另一充分条件收敛的另一充分条件）设设 在在a,b上连续，上连续，(1)f(a)f(b)0；(2)在整个在整个a,b上上 且且 ；(3)，则对则对 ，Newtons Meth
5、od产生的序列产生的序列 xk 收敛于方收敛于方程程 在在a,b内内的唯一实根的唯一实根 。且且第8页，共19页，编辑于2022年，星期二Th2.9中条件中条件（3）的的几何意义几何意义保证数列保证数列 单调递增且有上界单调递增且有上界第9页，共19页，编辑于2022年，星期二改进与推广（改进与推广（补充补充）/*improvement and generalization*/重根重根 /*multiple root*/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为 Newtons
6、Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 n 越高越高，收敛，收敛越慢越慢。Q2:如何如何加速加速重根情况时的收敛速度？重根情况时的收敛速度？A2:将求将求 f 的的重根转化重根转化为求另一函数的为求另一函数的单根单根。令，则令，则 f 的重根的重根 =的单根。的单根。第10页，共19页，编辑于2022年，星期二 5 弦割法与抛物线法弦割法与抛物线法 /*Secant Method and Parabola Method*/x0 x1割线/*secant line*/切线斜率切线斜率 割线斜率割线
7、斜率需要需要2个初值个初值 x0 和和 x1。Newtons Method 每一步要计算每一步要计算 f 和和 ，为了避免计算导数，为了避免计算导数值，现用值，现用 f 的值近似的值近似 ，从而得到，从而得到弦割法弦割法（割线法割线法）。）。x2一、弦割法一、弦割法第11页，共19页，编辑于2022年，星期二Th2.10 局部收敛性局部收敛性 设设 表示区间表示区间 ，x*为方程为方程 f(x)=0的根，的根，函数函数f(x)在在 中有中有足够阶连续导数足够阶连续导数，且且 满足满足 则对则对 ，由割线法产生的序列，由割线法产生的序列 都收敛于都收敛于x*，且，且(i)(ii)(iii)其中其
8、中收敛速度介于Newton and Bisection 之间 第12页，共19页，编辑于2022年，星期二xk-2Muller方法的思想来源于方法的思想来源于弦割法弦割法:利用利用3个已知点构造一条抛物个已知点构造一条抛物线线,取其与取其与x轴的交点构造下一次迭代值轴的交点构造下一次迭代值.x*二、抛物线法二、抛物线法(Muller)几何图示几何图示xkxk-1xk+1第13页，共19页，编辑于2022年，星期二 Muller方法的具体实现方法的具体实现:设已知三个点设已知三个点则过上述三个点的则过上述三个点的抛物线方程抛物线方程为为:取该抛物线与取该抛物线与x轴的交点作为下一次迭代值轴的交点
9、作为下一次迭代值,即即然后取然后取新的相邻的三次迭代值新的相邻的三次迭代值重复上述过程重复上述过程,即为即为Muller方法方法.第14页，共19页，编辑于2022年，星期二 Muller方法中抛物线根的计算方法方法中抛物线根的计算方法:首先要将抛物线化为首先要将抛物线化为规范形式规范形式:引入新的变量引入新的变量第15页，共19页，编辑于2022年，星期二将上述变量代入前面的抛物线方程将上述变量代入前面的抛物线方程,得得其中其中的两个零点为的两个零点为:第16页，共19页，编辑于2022年，星期二取取 的两个零点中靠近的两个零点中靠近 的那个零点的那个零点,则有则有 Muller方法的迭代公
10、式为方法的迭代公式为:具体计算步骤见教材具体计算步骤见教材P39.第17页，共19页，编辑于2022年，星期二 算法:Muller方法给定初始近似值 x0，x1，x2,求f(x)=0 的根.输入:初值 x0，x1，x2;容许误差 TOL.输出:近似解 x.Step 1 Set i=1;Step 4 If|t4(x2-x1)|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
11、-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);第18页，共19页，编辑于2022年，星期二Th2.5.2 （局部收敛性局部收敛性）设设 ，在在x*的某邻域内连续，则存的某邻域内连续，则存在在 x*的一个邻域的一个邻域 ，当，当 时时,由由抛物线法抛物线法产生的序列产生的序列 收敛于收敛于x*，且，且其中其中 ,是方程是方程 的根的根.Muller法的优点：初值的选取范围比Newton法和弦割法宽,而且可以一次求得方程的一对复根.第19页，共19页，编辑于2022年，星期二