非线性方程求根.pptx

16:14:47Numerical AnalysisNumerical Analysis1本章内容本章内容n 非线性方程求解非线性方程求解n 二分法二分法n 不动点迭代法及其加速不动点迭代法及其加速n 牛顿法、弦截法、抛物线法牛顿法、弦截法、抛物线法n 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点n 非线性方程组的数值求解非线性方程组的数值求解16:14:47Numerical AnalysisNumerical Analysis2本讲内容本讲内容l 迭代格式迭代格式l 加速算法加速算法l 收敛性收敛性n 非线性方程求解介绍非线性方程求解介绍n 二分法及其收敛性二分法及其收敛性n 不动点迭代及其加速不动点迭代及其加速16:14:47Numerical AnalysisNumerical Analysis3非线性方程数值解法非线性方程数值解法考虑方程考虑方程l 若若 f(x)是一次多项式，则称为是一次多项式，则称为线性方程线性方程；否则称为否则称为非线性方程非线性方程f(x)=0l 若若 f(x)=a0+a1x+.+anxn，则称为，则称为代数方程代数方程n=1,2,3,4 时有相应的求根公式，时有相应的求根公式，n 5 时不存在求根公式时不存在求根公式l 非线性方程可能有非线性方程可能有(无穷无穷)多个解，求解时必须强调多个解，求解时必须强调求解区间求解区间l 非线性方程一般没有直接解法，通常都使用非线性方程一般没有直接解法，通常都使用迭代算法迭代算法求解求解16:14:48Numerical AnalysisNumerical Analysis4非线性方程数值解法非线性方程数值解法q 几个基本概念几个基本概念l 实根与复根实根与复根l 根的重数根的重数 f(x)=(xx*)m g(x)且且 g(x*)0,则则 x*为为 f(x)=0 的的 m 重根重根l 有根区间：有根区间：a,b 上存在上存在 f(x)=0 的一个实根的一个实根q 研究内容：研究内容：在在有根有根的前提下求出方程的的前提下求出方程的近似根近似根16:14:48Numerical AnalysisNumerical Analysis5二分法（对分法）二分法（对分法）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 计算计算 f(x)，其中，其中若若|f(x)|或或 b-a，停止计算，输出近似，停止计算，输出近似解解 x若若 f(a)f(x)0，则令，则令 b=x;否则令否则令 a=xl 优点：优点：简单易用，总是收敛简单易用，总是收敛l 缺点：缺点：收敛速度慢，不能求复根和偶数重根收敛速度慢，不能求复根和偶数重根l 总结：总结：一般用来计算解的一个粗糙估计一般用来计算解的一个粗糙估计16:14:48Numerical AnalysisNumerical Analysis7误差分析误差分析记记 a1=a,b1=b,第第 k 步的有根区间为步的有根区间为 ak,bk结论：结论：二分法总是收敛的二分法总是收敛的16:14:48Numerical AnalysisNumerical Analysis8不动点迭代不动点迭代q 基本思想基本思想l 构造构造 f(x)=0 的一个等价方程：的一个等价方程：(x)的不动点的不动点f(x)=0 x=(x)等价变换等价变换f(x)的零点的零点16:14:48Numerical AnalysisNumerical Analysis9不动点迭代不动点迭代q 具体过程具体过程l 任取一个迭代初始值任取一个迭代初始值 x0，计算，计算得到一个迭代序列：得到一个迭代序列：x0，x1，x2，.，xn，.k=0,1,2,.几何含义：几何含义：求曲线求曲线 y=(x)与直线与直线 y=x 的交点的交点16:14:48Numerical AnalysisNumerical Analysis10 xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 16:14:49Numerical AnalysisNumerical Analysis11连续性分析连续性分析设设 (x)连续，若连续，若 收敛，即收敛，即 ，则，则即即q 收敛性分析收敛性分析性质：性质：若若 ，则不动点迭代，则不动点迭代收敛收敛，且，且 x*是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。16:14:50Numerical AnalysisNumerical Analysis12解的存在唯一性解的存在唯一性定理定理：设设 (x)Ca,b 且满足且满足证明：证明：P216(1)对任意的对任意的 x a,b 有有 (x)a,b(2)存在常数存在常数 0L1，使得任意的，使得任意的 x,y a,b 有有则则(x)在在 a,b 上存在上存在唯一的不动点唯一的不动点 x*解的存在唯一性解的存在唯一性16:14:50Numerical AnalysisNumerical Analysis13收敛性分析收敛性分析定理定理：设设 (x)Ca,b 且满足且满足证明：证明：P217(1)对任意的对任意的 x a,b 有有 (x)a,b(2)存在常数存在常数 0L1，使得任意的，使得任意的 x,y a,b 有有则对任意初始值则对任意初始值 x0 a,b，不动点迭代，不动点迭代 xk+1=(xk)收敛，且收敛，且不动点迭代的收敛性不动点迭代的收敛性16:14:50Numerical AnalysisNumerical Analysis14收敛性分析收敛性分析不动点迭代的收敛性不动点迭代的收敛性若若 (x)C1a,b 且对任意且对任意 x a,b 有有|(x)|L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛16:14:50Numerical AnalysisNumerical Analysis15举例举例例：例：求求 f(x)=x3 x 1=0 在区间在区间 1,2 中的根中的根(1)(2)16:14:50Numerical AnalysisNumerical Analysis16局部收敛局部收敛定义定义：设设 x*是是 (x)的不动点，若存的不动点，若存在在 x*的某个的某个 -邻域邻域 U(x*)=x*-,x*+，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1=(xk)产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x*是是 (x)的不动点，若的不动点，若 (x)在在 x*的某个邻域的某个邻域内连续，且内连续，且|(x*)|0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。(1)当当 p=1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*)0，则，则不动点迭代不动点迭代 xk+1=(xk)线性收敛线性收敛16:14:50Numerical AnalysisNumerical Analysis18收敛速度收敛速度定理：定理：设设 x*是是 (x)的不动点的不动点，若若 (p)(x)在在 x*的某邻的某邻域内连续，且域内连续，且则迭代则迭代 xk+1=(xk)是是 p 阶收敛的。阶收敛的。证明：证明：P21916:14:50Numerical AnalysisNumerical Analysis19Aitken 加速加速Aitken 加速加速若若 (x)变化不大变化不大，则可得：，则可得：16:14:51Numerical AnalysisNumerical Analysis20Aitken 加速加速收敛性：收敛性：超线性收敛超线性收敛 16:14:51Numerical AnalysisNumerical Analysis21Steffenson 加速加速Steffenson 加速加速将将 Aitken 加速技巧与不动点迭代相结合加速技巧与不动点迭代相结合 k=0,1,2,.迭代函数：迭代函数：16:14:51Numerical AnalysisNumerical Analysis22Steffenson 加速加速定理：定理：若若 x*是是 (x)的不动点的不动点，则则 x*是是 (x)的不的不动点。反之，若动点。反之，若 x*是是 (x)的不动点，且的不动点，且 ”(x)存存在，在，(x*)1，则，则 x*是是 (x)的不动点，且的不动点，且 Steffenson 加速迭代是二阶收敛的。加速迭代是二阶收敛的。l 若原迭代是若原迭代是 p 阶收敛的，则阶收敛的，则 Steffenson 加速后加速后 p+1 阶收敛阶收敛l 原来不收敛的迭代，原来不收敛的迭代，Steffenson 加速可能收敛加速可能收敛16:14:51Numerical AnalysisNumerical Analysis23举例举例例：例：用用 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);end16:14:51Numerical AnalysisNumerical Analysis24例：例：用用 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,endend16:14:51Numerical AnalysisNumerical Analysis25本讲内容本讲内容n Newton 法及其收敛性法及其收敛性n 牛顿下山法牛顿下山法n 弦截法与抛物线法弦截法与抛物线法16:14:51Numerical AnalysisNumerical Analysis26Newton 法法q 基本思想基本思想将非线性方程将非线性方程线性化线性化l 设设 xk 是是 f(x)=0 的近似根，将的近似根，将 f(x)在在 xk 处处 Taylor 展开展开令：令：条件：条件：f(x)016:14:52Numerical AnalysisNumerical Analysis27Newton 法法xyx*xkxk+116:14:52Numerical AnalysisNumerical Analysis28Newton 法法算法算法：(Newton 法法)(1)任取迭代初始值任取迭代初始值 x0(2)对对 k=1,2,.,maxit，计算，计算判断收敛性，若收敛，则停止计算，输出近似解判断收敛性，若收敛，则停止计算，输出近似解16:14:52Numerical AnalysisNumerical Analysis29收敛性收敛性 k=0,1,2,.l 迭代函数迭代函数牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛16:14:52Numerical AnalysisNumerical Analysis30举例举例例：例：用用 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，即牛顿法收敛即牛顿法收敛16:14:52Numerical AnalysisNumerical Analysis32牛顿牛顿法法q 牛顿牛顿的的优点优点牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程(组组)的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。充分靠近精确解时。q 牛顿牛顿的缺点的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法先用其它算法获取一个近似解，然后使用牛顿法l 需要求导数！需要求导数！16:14:52Numerical AnalysisNumerical Analysis33简化的简化的Newton法法线性收敛线性收敛简化的简化的 Newton 法法l 基本思想：基本思想：用用 f(x0)替代所有的替代所有的 f(xk)16:14:52Numerical AnalysisNumerical Analysis34Newton下山法下山法l 下山因子的取法：下山因子的取法：从从 =1 开始，逐次减半，直到满足下降条件开始，逐次减半，直到满足下降条件l 基本思想：基本思想：要求每一步迭代满足下降条件要求每一步迭代满足下降条件l 具体做法：具体做法：加加下山因子下山因子 Newton下山法下山法保证全局收敛保证全局收敛16:14:53Numerical AnalysisNumerical Analysis35重根情形重根情形且且l 解法一解法一：直接使用：直接使用 Newton 法法线性收敛线性收敛l 解法二解法二：改进的：改进的 Newton 法法二阶收敛二阶收敛缺点：缺点：需要知道需要知道 m 的值的值重根情形重根情形16:14:53Numerical AnalysisNumerical Analysis36重根情形重根情形令令x*是是 (x)=0 的的单重根单重根l 解法三解法三：用：用 Newton 法解法解 (x)=0迭代格式：迭代格式：16:14:53Numerical AnalysisNumerical Analysis37举例举例例：例：求求 x4-4x2 4=0 的二重根的二重根(1)普通普通 Newton 法法(2)改进的改进的 Newton 法法(3)用用 Newton 法解法解 (x)=016:14:53Numerical AnalysisNumerical Analysis38%重根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);end16:14:53Numerical AnalysisNumerical Analysis39弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法l 目的目的：避免计算：避免计算 Newton 法中的导数，且具有较法中的导数，且具有较高的收敛性（超线性收敛）高的收敛性（超线性收敛）l 弦截法（割线法）：弦截法（割线法）：用差商代替微商用差商代替微商l 抛物线法：抛物线法：用二次多项式近似用二次多项式近似 f(x)16:14:53Numerical AnalysisNumerical Analysis40弦截法弦截法l 弦截法迭代格式：弦截法迭代格式：k=1,2,3,.l 注：弦截法需要提供注：弦截法需要提供两个迭代初始值两个迭代初始值16:14:53Numerical AnalysisNumerical Analysis41收敛性收敛性定理：定理：设设 x*是是 f(x)的零点的零点，f(x)在在 x*的某邻域的某邻域 U(x,)内有二阶连续导数，且内有二阶连续导数，且 f(x)0，若初值，若初值 x0，x1 U(x,)，则当则当 U(x,)充分小时，弦截法具充分小时，弦截法具有有 p 阶收敛性，其中阶收敛性，其中16:14:53Numerical AnalysisNumerical Analysis42弦截法几何含义弦截法几何含义xyx*xk-1xkxk+116:14:54Numerical AnalysisNumerical Analysis43抛物线法抛物线法(略略)l 基本思想：基本思想：用二次曲线与用二次曲线与 x 轴的交点作为轴的交点作为 x*的近似值的近似值 抛物线法抛物线法16:14:54Numerical AnalysisNumerical Analysis44抛物线法抛物线法yxk-2xk-1xkxk+116:14:54Numerical AnalysisNumerical Analysis45抛物线法抛物线法l 计算过程计算过程二次曲线方程二次曲线方程 (三点三点 Newton 插值多项式插值多项式)l 问题：问题：p2(x)与与 x 轴有轴有两个交点两个交点，取哪个点？，取哪个点？解决方法：解决方法：取靠近取靠近 xk 的那个点的那个点!16:14:54Numerical AnalysisNumerical Analysis46抛物线法抛物线法取靠近取靠近 xk 的那个点的那个点16:14:54Numerical AnalysisNumerical Analysis47收敛性收敛性在一定条件下可以证明：抛物线法的收敛阶为在一定条件下可以证明：抛物线法的收敛阶为