非线性方程求根

第七章 非线性方程(组)的数值解法数值分析本章内容本章内容n 非线性方程求解非线性方程求解n 二分法二分法n 不动点迭代法及其加速不动点迭代法及其加速n 牛顿法、弦截法、抛物线法牛顿法、弦截法、抛物线法n 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点n 非线性方程组的数值求解非线性方程组的数值求解本讲内容本讲内容l 迭代格式迭代格式l 加速算法加速算法l 收敛性收敛性n 非线性方程求解介绍非线性方程求解介绍n 二分法及其收敛性二分法及其收敛性n 不动点迭代及其加速不动点迭代及其加速非线性方程数值解法非线性方程数值解法考虑方程考虑方程l 若若 f(x) 是一次多项式，则称为是一次多项式，则称为线性方程线性方程； 否则称为否则称为非线性方程非线性方程f (x) = 0l 若若 f(x) = a0 + a1x + . . . + anxn ，则称为，则称为代数方程代数方程, ( ) , xRf xC a b n=1, 2, 3, 4 时有相应的求根公式，时有相应的求根公式，n 5 时不存在求根公式时不存在求根公式l 非线性方程可能有非线性方程可能有(无穷无穷)多个解，求解时必须强调多个解，求解时必须强调求解区间求解区间l 非线性方程一般没有直接解法，通常都使用非线性方程一般没有直接解法，通常都使用迭代算法迭代算法求解求解非线性方程数值解法非线性方程数值解法q 几个基本概念几个基本概念l 实根与复根实根与复根l 根的重数根的重数 f(x)=(xx*)m g(x) 且且 g(x*) 0, 则则 x*为为 f(x)=0 的的 m 重根重根l 有根区间：有根区间：a, b 上存在上存在 f (x) = 0 的一个实根的一个实根q 研究内容：研究内容：在在有根有根的前提下求出方程的的前提下求出方程的近似根近似根二分法（对分法）二分法（对分法）q 基本思想基本思想将有根区间进行对分，找出根所在的小区间，然后再对该将有根区间进行对分，找出根所在的小区间，然后再对该小区间对分，依次类推，直到有根区间的长度满足给定的小区间对分，依次类推，直到有根区间的长度满足给定的精度为止精度为止q 数学原理：数学原理：介值定理介值定理设设 f(x) 在在 a, b 上连续，且上连续，且 f(a) f(b)0，则由介值定理可得，则由介值定理可得，在在 (a, b) 内至少存在一点内至少存在一点 使得使得 f( )=0q 适用范围适用范围求有根区间内的求有根区间内的 单重实根单重实根 或或 奇重实根，即奇重实根，即 f(a) f(b)0 ，则停止计算，则停止计算(2) 对对 k = 1, 2, . , maxit 2abx 计算计算 f(x)，其中，其中若若 |f(x)| 或或 b-a ，停止计算，输出近似解，停止计算，输出近似解 x若若 f(a) f(x) 0，则令，则令 b = x; 否则令否则令 a = xl 优点：优点：简单易用，总是收敛简单易用，总是收敛l 缺点：缺点：收敛速度慢，不能求复根和偶数重根收敛速度慢，不能求复根和偶数重根l 总结：总结：一般用来计算解的一个粗糙估计一般用来计算解的一个粗糙估计误差分析误差分析记记 a1 = a, b1 = b, 第第 k 步的有根区间为步的有根区间为 ak, bk11224kkkkkkkbababaxxx 112kba 20 ()kkakbxx 结论：结论：二分法总是收敛的二分法总是收敛的不动点迭代不动点迭代q 基本思想基本思想l 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx (x) 的不动点的不动点f (x) = 0 x = (x)等价变换等价变换f (x) 的零点的零点不动点迭代不动点迭代q 具体过程具体过程l 任取一个迭代初始值任取一个迭代初始值 x0 ，计算，计算得到一个迭代序列：得到一个迭代序列： x0，x1，x2，. . . ，xn，. . . 1()kkxx k = 0, 1, 2, . . 几何含义：几何含义：求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 连续性分析连续性分析设设 (x) 连续，若连续，若 收敛，即收敛，即 ，则，则 1limlim()limkkkkkkxxx lim*kkxx 0kkx *( *)xx ( *)0f x 即即q 收敛性分析收敛性分析性质：性质：若若 ，则不动点迭代，则不动点迭代收敛收敛，且，且 x* 是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。lim*kkxx 解的存在唯一性解的存在唯一性定理定理：设设 (x) Ca,b 且满足且满足证明：证明：P216对任意的对任意的 x a,b 有有 (x) a,b存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 则则 (x) 在在 a,b 上存在上存在唯一的不动点唯一的不动点 x*解的存在唯一性解的存在唯一性收敛性分析收敛性分析定理定理：设设 (x) Ca,b 且满足且满足证明：证明：P217对任意的对任意的 x a,b 有有 (x) a,b存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 则对任意初始值则对任意初始值 x0 a,b，不动点迭代，不动点迭代 xk+1= (xk) 收敛，且收敛，且不动点迭代的收敛性不动点迭代的收敛性11011kkkkLLxxxxxxLL 收敛性分析收敛性分析不动点迭代的收敛性不动点迭代的收敛性若若 (x) C1a,b 且对任意且对任意 x a,b 有有 | (x)| L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛举例举例例：例：求求 f(x) = x3 x 1=0 在区间在区间 1, 2 中的根中的根 3( )1xx 231( )(1)3xx 31( )0.2513x (1)1( )2x (1,2)x 3( )1xx 2( )3xx ( )1x (2)0( )7x (1,2)x 局部收敛局部收敛定义定义：设设 x* 是是 (x) 的不动点，若存的不动点，若存在在 x* 的某个的某个 -邻域邻域 U(x*) =x*- , x* + ，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1 = (xk) 产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x* 是是 (x) 的不动点，若的不动点，若 (x) 在在 x* 的某个邻域内的某个邻域内连续，且连续，且 | (x*)| 0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。当当 p =1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*) 0，则，则不动点迭代不动点迭代 xk+1 = (xk) 线性收敛线性收敛收敛速度收敛速度定理：定理：设设 x* 是是 (x) 的不动点的不动点，若若 (p)(x) 在在 x* 的某邻的某邻域内连续，且域内连续，且(1)()( *)( *)( *)0,( *)0ppxxxx 则迭代则迭代 xk+1 = (xk) 是是 p 阶收敛的。阶收敛的。证明：证明：P219Aitken 加速加速Aitken 加速加速10()xx 1010*()( *)()(*)xxxxxx 21()xx 2121*()( *)()(*)xxxxxx 若若 (x) 变化不大变化不大，则可得：，则可得：12()() 0121*xxxxxxxx 2100210()*2xxxxxxx 1yAitken 加速加速01234 . . .xxxxx123 . . .yyy21121()2kkkkkkkxxyxxxx 收敛性：收敛性：1*lim0*kkkyxxx 超线性收敛超线性收敛 Steffenson 加速加速21()(), (), 2kkkkkkkkkkkyxyxzyxxzyx Steffenson 加速加速将将 Aitken 加速技巧与不动点迭代相结合加速技巧与不动点迭代相结合 k = 0, 1, 2, . . . 迭代函数：迭代函数： 21( ( )(), ( )( )2 ( )kkxxxxxxxxx Steffenson 加速加速定理：定理：若若 x* 是是 (x) 的不动点的不动点，则则 x* 是是 (x) 的不的不动点。反之，若动点。反之，若 x* 是是 (x) 的不动点，且的不动点，且 ”(x) 存存在，在， (x*) 1，则，则 x* 是是 (x) 的不动点，且的不动点，且 Steffenson 加速迭代是二阶收敛的。加速迭代是二阶收敛的。l 若原迭代是若原迭代是 p 阶收敛的，则阶收敛的，则 Steffenson 加速后加速后 p+1 阶收敛阶收敛l 原来不收敛的迭代，原来不收敛的迭代，Steffenson 加速可能收敛加速可能收敛举例举例例：例：用用 Steffenson 加速法求加速法求 f(x) = x3 x 1=0 在区间在区间 1, 2 中的根（取中的根（取 (x) = x3 1）clear; clcf = inline(x3-x-1,x); g = inline(x3-1,x); fprintf(True solution: x = %.4fn,fzero(f,1,2)n = 5; % 设置迭代步数x = 1.5; % 迭代初始值% 不动点迭代fprintf(普通不动点迭代n)for k = 1 : n x = g(x); fprintf(k=%d, x=%.4fn,k,x);end % Steffenson 加速x = 1.5; % 迭代初始值fprintf(Steffenson 加速迭代n)for k = 1 : n x1 = g(x); x2 = g(x1); x = x - (x1-x)2/(x2-2*x1+x); fprintf(k=%d, x=%.4fn,k,x);end例：例：用用 Steffenson 加速法求加速法求 f(x) = 3x2 ex=0 在区间在区间 3, 4 中的根（取中的根（取 (x) = 2ln(x) + ln3）clear; clcf = inline(3*x2-exp(x),x);g = inline(2*log(x)+log(3),x);xt = fzero(f,3,4);fprintf(True solution: x = %.7fn, xt)n = 50; % 设置迭代步数tol = 1e-6; % 不动点迭代x = 3.5; % 迭代初始值fprintf(普通不动点迭代n)for k = 1 : n x = g(x); fprintf(k=%2d, x=%.7fn,k,x); if abs(x-xt)tol, break, endend % Steffenson 加速x = 3.5; % 迭代初始值fprintf(Steffenson 加速迭代n)for k = 1 : n x1 = g(x); x2 = g(x1); x = x - (x1-x)2/(x2-2*x1+x); fprintf(k=%2d, x=%.7fn,k,x); if abs(x-xt)tol, break, endend本讲内容本讲内容n Newton 法及其收敛性法及其收敛性n 牛顿下山法牛顿下山法n 弦截法与抛物线法弦截法与抛物线法Newton 法法q 基本思想基本思想将非线性方程将非线性方程线性化线性化2( )( )()()()()2!kkkkff xf xfxxxxx l 设设 xk 是是 f (x)=0 的近似根，将的近似根，将 f(x) 在在 xk 处处 Taylor 展开展开令：令：( )0P x 1()()kkkkf xxxfx ( )P x()()()kkkf xfxxx 条件：条件： f(x) 0Newton 法法xyx*xkxk+1Newton 法法算法算法 ：( Newton 法法 )(1) 任取迭代初始值任取迭代初始值 x0(2) 对对 k = 1, 2, . , maxit，计算，计算判断收敛性，若收敛，则停止计算，输出近似解判断收敛性，若收敛，则停止计算，输出近似解1()()kkkkf xxxfx 收敛性收敛性1()()kkkkf xxxfx k = 0, 1, 2, . . . l 迭代函数迭代函数( )( )( )f xxxfx ( *)( *)0,( *)2( *)fxxxfx 牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛12*( *)( *)lim(*)2!2( *)kkkxxxfxxxfx 举例举例例：例：用用 Newton 法求法求 f(x) = xex 1=0 的解的解% Newton 迭代clear; clcf = inline(x*exp(x)-1,x);df = inline(exp(x)*(1+x),x);n = 10;tol = 1e-6;x0 = 0.5; % 迭代初始值for k = 1 : n x = x0 - f(x0)/df(x0); fprintf(k=%2d, x=%.7fn,k,x); if abs(x-x0)0，总有总有 |q|1，即牛顿法收敛即牛顿法收敛牛顿牛顿法法q 牛顿牛顿的的优点优点牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程 (组组) 的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。充分靠近精确解时。q 牛顿牛顿的缺点的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法先用其它算法获取一个近似解，然后使用牛顿法l 需要求导数！需要求导数！简化的简化的Newton法法10()()kkkfxf xxx 线性收敛线性收敛简化的简化的 Newton 法法l 基本思想：基本思想：用用 f(x0) 替代所有的替代所有的 f(xk)Newton下山法下山法1()()kkkkf xxxfx l 下山因子的取法：下山因子的取法： 从从 =1 开始，逐次减半，直到满足下降条件开始，逐次减半，直到满足下降条件l 基本思想：基本思想：要求每一步迭代满足下降条件要求每一步迭代满足下降条件 1kkfxfx l 具体做法：具体做法：加加下山因子下山因子 Newton下山法下山法保证全局收敛保证全局收敛重根情形重根情形( )(*)( )mf xxxg x ( *)0g x 且且l 解法一解法一：直接使用：直接使用 Newton 法法( )( )( )f xxxfx 1( *)1xm 线性收敛线性收敛l 解法二解法二：改进的：改进的 Newton 法法( )( )( )f xxxmfx ( *)0 x 二阶收敛二阶收敛缺点：缺点：需要知道需要知道 m 的值的值重根情形重根情形重根情形重根情形( )( )( )f xxfx 令令x* 是是 (x)=0 的的单重根单重根l 解法三解法三：用：用 Newton 法解法解 (x) = 02( )( ) ( )( )( ) ( )( ) ( )xf x fxxxxxfxf x fx 12() () ()() ()kkkkkkkf xfxxxfxf xfx 迭代格式：迭代格式：举例举例例：例：求求 x4 - 4x2 4=0 的二重根的二重根 *2x 212( )4xxxx (1) 普通普通 Newton 法法(2) 改进的改进的 Newton 法法(3) 用用 Newton 法解法解 (x) = 0222( )2xxxx 232(2)( )2x xxxx % 重根clear; clcf = inline(x4 -4*x2 + 4,x);g1 = inline(x-(x2-2)/(4*x),x);g2 = inline(x-(x2-2)/(2*x),x);g3 = inline(x-x*(x2-2)/(x2+2),x);fprintf(True solution: x=%.7fn,sqrt(2);n = 10;x0 = 1.5; % 迭代初始值x1 = x0; x2 = x0; x3 = x0;for k = 1 : n x1 = g1(x1); x2 = g2(x2); x3 = g3(x3); fprintf(k=%2d, x1=%.7f, x2=%.7f, x3=%.7fn,k,x1,x2,x3);end弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法l 目的目的：避免计算：避免计算 Newton 法中的导数，且具有较法中的导数，且具有较高的收敛性（超线性收敛）高的收敛性（超线性收敛）l 弦截法（割线法）：弦截法（割线法）：用差商代替微商用差商代替微商l 抛物线法：抛物线法：用二次多项式近似用二次多项式近似 f(x)弦截法弦截法l 弦截法迭代格式：弦截法迭代格式：111()()(),kkkkkkkf xf xfxf xxxx 111()()()kkkkkkkxxxxf xf xf x k = 1, 2, 3, . . .l 注：弦截法需要提供注：弦截法需要提供两个迭代初始值两个迭代初始值收敛性收敛性定理：定理：设设 x* 是是 f(x) 的零点的零点， f(x) 在在 x* 的某邻域的某邻域 U(x, ) 内有二阶连续导数，且内有二阶连续导数，且 f(x) 0，若初值，若初值 x0，x1 U(x, )，则当则当 U(x, ) 充分小时，弦截法具有充分小时，弦截法具有 p 阶收敛性，其中阶收敛性，其中152p 2(10)pp 弦截法几何含义弦截法几何含义xyx*xk-1xkxk+1抛物线法抛物线法(略略)l 基本思想：基本思想： 用二次曲线与用二次曲线与 x 轴的交点作为轴的交点作为 x* 的近似值的近似值 抛物线法抛物线法抛物线法抛物线法yxk-2xk-1xkxk+1抛物线法抛物线法l 计算过程计算过程二次曲线方程二次曲线方程 (三点三点 Newton 插值多项式插值多项式)21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxx l 问题：问题：p2(x) 与与 x 轴有轴有两个交点两个交点，取哪个点？，取哪个点？解决方法：解决方法：取靠近取靠近 xk 的那个点的那个点!抛物线法抛物线法21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxx 12122 ()4 () ,kkkkkkkf xxxf xf xxx 1121,()kkkkkkkf xxf xxxxx 取靠近取靠近 xk 的那个点的那个点收敛性收敛性在一定条件下可以证明：抛物线法的收敛阶为在一定条件下可以证明：抛物线法的收敛阶为 1.840p 32(10)ppp