第7章非线性方程与方程组的数值解法.ppt

数值分析数值分析李小林李小林 重庆师范大学数学学院重庆师范大学数学学院Numerical Analysis数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法2第七章第七章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/*Numerical Solutions of Nonlinear Equations and Nonlinear Algebraic Systems*/我们知道在实际应用中有许多非线性方程的例子我们知道在实际应用中有许多非线性方程的例子例如例如:（1）在光的衍射理论（）在光的衍射理论（the theory of diffraction of light)中中,我我们需要求们需要求 x-tanx=0 的根的根（2）在行星轨道（）在行星轨道（planetary orbits）的计算中的计算中,对任意的对任意的a和和b，我们需要求我们需要求 x-asinx=b 的根的根（3）在数学中，需要求在数学中，需要求n次多项式次多项式的根的根数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法3历史背景历史背景 代数方程的求根问题是一个古老的数学问题。理论上，代数方程的求根问题是一个古老的数学问题。理论上，次代数方程在复数域内一定有次代数方程在复数域内一定有 个根个根(考虑重数考虑重数)。早在。早在1616世纪世纪就找到了三次、四次方程的求根公式，但直到就找到了三次、四次方程的求根公式，但直到1919世纪才证明大世纪才证明大于等于于等于5 5次的一般代数方程式不能用代数公式求解，而对于超次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。数值方法求得满足一定精度要求的根的近似解。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法4求方程求方程 几何意义几何意义基本定理基本定理 如果函数如果函数 在在 上连续，且上连续，且则至少有一个数则至少有一个数 使得使得 ，若同时，若同时 的一阶的一阶导数导数 在在 内存在且保持定号，即内存在且保持定号，即 (或或 )则这样的则这样的 在在 内唯一。内唯一。abx*数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法51 1 二分法二分法 /*Bisection Method*/原理：原理：若若 f Ca,b，且且 f(a)f(b)0，则则 f 在在(a,b)上至少有一实根。上至少有一实根。基本思想：基本思想：逐步将区间分半，通过判别区间端点函数值的符号，逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根出满足给定精度的根 的近似值。的近似值。以以此此类类推推数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法6终止法则？终止法则？abx1x2abWhen to stop?或或不能保证不能保证 x 的精的精度度x*2xx*数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法7 二分法算法二分法算法给定区间给定区间a,b，求，求f(x)=0 在该区间上的根在该区间上的根x.输入输入:a和和b;容许误差容许误差 TOL;最大对分次数最大对分次数 Nmax.输出输出:近似根近似根 x.Step 1 Set k=1;Step 2 Compute x=(a+b)/2;Step 3 While(k Nmax)do steps 4-6 Step 4 If f(x)=0 or|b-a|TOL,STOP;Output the solution x.Step 5 If x*f(a)0,Set b=x;Else Set a=x;Step 6 Set k=k+1;Compute x=(a+b)/2;Go To Step 3;Step 7 Output the solution of equation:x;STOP.数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法83、由二分法的过程可知：由二分法的过程可知：4、对分次数的计算公式：对分次数的计算公式：1、2、令令误差误差 分析分析数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法9解解：例例1 1：用二分法求方程用二分法求方程 在区间在区间 上的上的根，精确到小数点后第根，精确到小数点后第2 2位，问至少需对分多少次？位，问至少需对分多少次？数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法10k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 +数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法11简单简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可).无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 注：注：注：注：用二分法求根，最好先给出用二分法求根，最好先给出 f(x)草图以确定根的大草图以确定根的大概位置，或用搜索程序，将概位置，或用搜索程序，将a,b分为若干小区间，对每分为若干小区间，对每一个满足一个满足 f(ak)f(bk)0 的区间调用二分法程序，可找的区间调用二分法程序，可找出区间出区间a,b内的多个根，且不必要求内的多个根，且不必要求 f(a)f(b)0。优点优点缺点缺点数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法122 不动点迭代法及其收敛性不动点迭代法及其收敛性f(x)=0 x=(x)（迭代函数）迭代函数）等价变换等价变换思思路路从一个初值从一个初值 x0 出发，计算出发，计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使使得得 ，且，且 连续，则由连续，则由 可可知知 x*=(x*)，即，即x*是是 的的不动点，也就是不动点，也就是f 的的根。根。看起来很简单，令人看起来很简单，令人有点不相信，那么问有点不相信，那么问题是什么呢？题是什么呢？如何判定这种方法如何判定这种方法是收敛的呢？是收敛的呢？f(x)的根的根(x)的不动点的不动点一、不动点迭代一、不动点迭代 /*Fixed-Point Iteration*/数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法13xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意义几何意义数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法14例例2：已知方程已知方程 在在 上有一个根（正根）上有一个根（正根）下面选取下面选取5 5种迭代格式：种迭代格式：1 1、即即2 2、即即3 3、即即4 4、即即5 5、即即数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法15取取计算结果如下：计算结果如下：法法1 1法法4 4法法3 3法法2 2法法5 5 数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法16Lipschitz条件成条件成立的充分条件立的充分条件考虑方程考虑方程 x=(x),若若(I)当当 x a,b 时，时，(x)a,b；(II)0 L 1 使得使得 对对 x a,b 成成立。立。则任取则任取 x0 a,b，由由 xk+1=(xk)得到的序列得到的序列 收收敛于敛于(x)在在a,b上的上的唯一不动点。并且有误差估计式：唯一不动点。并且有误差估计式：(k=1,2,)且且存在极限存在极限连续时连续时数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法17证明：证明：(x)在在a,b上存在不动点？上存在不动点？令令有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法18L 越越 收敛越快收敛越快可用可用 来来控制收敛精度控制收敛精度 小小注：注：注：注：条件条件(II)可改为可改为 在在a,b 满足满足Lipschitz条件条件,定理结论仍然成立。定理结论仍然成立。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法19 算法算法:不动点迭代不动点迭代给定初始近似值给定初始近似值 x0，求，求x=(x)的解的解.输入输入:初始近似值初始近似值 x0;容许误差容许误差 TOL;最大迭代次数最大迭代次数 Nmax.输出输出:近似解近似解 x 或或失败信息失败信息.Step 1 Set i=1;Step 2 While(i Nmax)do steps 3-6Step 3 Set x=(x0);/*计算计算 xi*/Step 4 If|x x0|1)(1)阶收敛的方法，阶收敛的方法，改用改用Stefensen迭代方法优点不多。迭代方法优点不多。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法39数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法40数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法41数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法42数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法43数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法44数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法454 牛顿法牛顿法 /*Newton-Raphson Method*/一、牛顿迭代公式的推导一、牛顿迭代公式的推导1、待定参数法待定参数法不动点迭代的不动点迭代的关键关键是构造满足是构造满足收敛条件收敛条件的的迭代函数迭代函数 一种一种自然的选择自然的选择是令是令为了加速不动点迭代的收敛过程，应尽可能使迭代函数为了加速不动点迭代的收敛过程，应尽可能使迭代函数 在在 处有处有更多阶导数等于零更多阶导数等于零。令令现设现设数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法46取取满足满足因此，选取迭代函数因此，选取迭代函数Newton Raphson迭代格式迭代格式称之为称之为牛顿牛顿拉夫森拉夫森方法，简称方法，简称牛顿法牛顿法原理：原理：将非线性方程将非线性方程线性化线性化取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x 之间之间2、Taylor展开法展开法/*Taylors expansion Method*/数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法47将将(x*x0)2 看成看成高阶小量高阶小量，则有：，则有：xyx*x0只要只要 f C1，每一步迭代都有每一步迭代都有 而且而且 ，则，则 x*就是就是 f 的根。的根。与与x轴交点的横坐标轴交点的横坐标数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法48无开方运算，又无除法运算。无开方运算，又无除法运算。例例1 1：写出求写出求 的的Newton迭代格式；迭代格式；写出求写出求 的的Newton迭代格式迭代格式,要求公式中既要求公式中既解：解：等价于求方程等价于求方程 的正的正根根解法一：解法一：等价于求方程等价于求方程 的正的正根根 数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法49解法二：解法二：等价于求方程等价于求方程 的正的正根根 （局部收敛性局部收敛性）设设 x*为方程为方程 f(x)=0的根，在包含的根，在包含x*的某个开区间内的某个开区间内 连续，连续，且且 ，则，则存在存在 x*的的邻域邻域 ，使得任取初值，使得任取初值 ，由，由Newtons Method产生的序列产生的序列 以不低于以不低于二阶二阶的收敛速度收敛于的收敛速度收敛于x*，且，且Th数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法50证明：证明：Newtons Method 事实上是一种事实上是一种特殊的不动点迭代特殊的不动点迭代 其中其中 ，则，则至少平方收敛至少平方收敛由由 Taylor 展开：展开：在在单单根根/*simple root*/附近收敛快附近收敛快 只要只要 ，则，则令令 可得结论。可得结论。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法51有根有根根根唯一唯一产生的序列产生的序列单调有单调有界界保证收敛保证收敛证明：证明：因为因为f C2a,b，由（由（1）和（）和（2）知）知f(x)在在a,b内有内有唯一唯一根根下面由条件（下面由条件（1）、（）、（2）分）分4种情况讨论：种情况讨论：仅证明仅证明第一种第一种情况，其它情况类似讨论情况，其它情况类似讨论 （收敛的充分条件收敛的充分条件）设设f(x)=0 且且f C2a,b，若若(1)f(a)f(b)0；(2)在整个在整个a,b上上 不变号且不变号且 ；(3)选取选取 x0 a,b 使得使得 ；则则Newtons Method产生的序列产生的序列 xk 收敛于方程的根收敛于方程的根 ,Th且且数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法52由由中值定理，中值定理，使得使得因此因此即即 在在 上单调递增上单调递增由由另一方面，由另一方面，由Taylor展开得展开得 介于介于 、之之间间数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法53重复以上过程，可得（重复以上过程，可得（归纳法归纳法）（自己证）（自己证）因此，数列因此，数列 单调下降且有下界单调下降且有下界令令由由Taylor展开得展开得数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法54注：注：注：注：Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0 （收敛的另一充分条件收敛的另一充分条件）设设 在在a,b上连续，上连续，(1)f(a)f(b)0；(2)在整个在整个a,b上上 且且 ；(3)，则对则对 ，Newtons Method产生的序列产生的序列 xk 收敛于收敛于方方程程 在在a,b内内的唯一实根的唯一实根 。Th且且数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法55Th中条件中条件（3）的的几何意义几何意义保证数列保证数列 单调递增且有上界单调递增且有上界数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法56改进与推广改进与推广/*improvement and generalization*/重根重根 /*multiple root*/加速收敛法：加速收敛法：Q1:若若 ，Newtons Method 是否仍收敛？是否仍收敛？设设 x*是是 f 的的 m 重根，则：重根，则：且且 。因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，但重数有局部收敛性，但重数 m 越高越高，收敛，收敛越慢越慢。Q2:如何如何加速加速重根情况时的收敛速度？重根情况时的收敛速度？A2:将求将求 f 的的重根转化重根转化为求另一函数的为求另一函数的单根单根。令，则令，则 f 的重根的重根 =的单根。的单根。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法57 求复根求复根 /*Finding Complex Roots*/Newton 公式中的自变量可以是公式中的自变量可以是复数复数记记 z=x+i y,z0 为初值，同样有为初值，同样有设设代入公式，令代入公式，令实、虚部对应相等实、虚部对应相等，可得，可得数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法58 5 弦割法与抛物线法弦割法与抛物线法 /*Secant Method and Parabola Method*/x0 x1割线割线/*secant line*/切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。Newtons Method 每一步要计算每一步要计算 f 和和 ，为了避免计算导数，为了避免计算导数值，现用值，现用 f 的值近似的值近似 ，从而得到，从而得到弦割法弦割法（割线法割线法）。）。x2一、弦割法一、弦割法数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法59 局部收敛性局部收敛性 设设 表示区间表示区间 ，x*为方程为方程 f(x)=0的根，的根，函数函数f(x)在在 中有中有足够阶连续导数足够阶连续导数，且且 满足满足 Th则对则对 ，由，由弦割法弦割法产生的序列产生的序列 都收敛于都收敛于x*，且，且(i)(ii)(iii)其中其中收敛速度介于收敛速度介于Newton and Bisection 之间之间 数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法60Corollary(推论推论)设设 x*为方程为方程 f(x)=0的的一个根，一个根，且且 在在 x*的的附近连续，则附近连续，则 使得使得 则由则由弦割法弦割法产生的序列产生的序列 都收敛于都收敛于x*。例例1 证明方程证明方程 在区间在区间 内有内有唯一唯一根根 ，且，且使得对任意的初始值使得对任意的初始值 ，由，由弦割法弦割法产生的序产生的序列列 都收敛于都收敛于 。证明：证明：令令方程方程存在存在根根方程存在方程存在唯一唯一根根且且在在 附近连续附近连续由由推论推论知，由知，由弦割法弦割法产生的序列产生的序列 都收敛于都收敛于 。数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法61xk-2Muller方法的思想来源于方法的思想来源于弦割法弦割法:利用利用3个已知点构造一条抛物个已知点构造一条抛物线线,取其与取其与x轴的交点构造下一次迭代值轴的交点构造下一次迭代值.x*二、抛物线法二、抛物线法(Muller)几何图示几何图示xkxk-1xk+1数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法62 Muller方法的具体实现方法的具体实现:设已知三个点设已知三个点则过上述三个点的则过上述三个点的抛物线方程抛物线方程为为:取该抛物线与取该抛物线与x轴的交点作为下一次迭代值轴的交点作为下一次迭代值,即即然后取新的相邻的三次迭代值重复上述过程然后取新的相邻的三次迭代值重复上述过程,即为即为Muller方法方法.数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法63 （局部收敛性局部收敛性）设设 ，在在x*的某邻域内连续，则的某邻域内连续，则存存在在 x*的一个邻域的一个邻域 ，当，当 时时,由由抛物线法抛物线法产生的序列产生的序列 收敛于收敛于x*，且，且Th其中其中 ,是方程是方程 的根的根.Muller法法的优点：初值的选取范围比的优点：初值的选取范围比Newton法和法和弦割法弦割法宽宽,而且可以一次求得方程的而且可以一次求得方程的一对复根一对复根.数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法64 6.5 非线性方程组的迭代解法非线性方程组的迭代解法/*The Iterative Method for Systems of Nonlinear Equations*/n个方程的个方程的n元非线性方程组的一般形式：元非线性方程组的一般形式：其中其中 是定义在区域是定义在区域 上的上的n元实值函数，且元实值函数，且 中至少有一个是中至少有一个是非线性函数非线性函数。如如数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法65一、一、Newton迭代法及其改进算法迭代法及其改进算法利用多元函数的利用多元函数的Taylor展开公式得展开公式得 Newton迭代法的迭代格式迭代法的迭代格式数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法66写成矩阵形式写成矩阵形式数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法67其中其中称之为函数称之为函数 的的Jacobi矩阵矩阵数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法68称上述公式为称上述公式为Newton迭代格式。迭代格式。Newton迭代方法在实际迭代时，转化为求迭代方法在实际迭代时，转化为求方程组的解方程组的解数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法69解：解：例：例：用用Newton迭代法求解下列方程组迭代法求解下列方程组取取解方程组解方程组数值分析数值分析第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法70即即计算结果如下计算结果如下 要求要求 精度精度迭代迭代次数次数 0.001 2(1.0000 1.0000)0.0001 3(1.0000 1.0000)方程组的方程组的近似解近似解