《7非线性方程求根教学材料》由会员分享，可在线阅读，更多相关《7非线性方程求根教学材料（48页珍藏版）》请在金锄头文库上搜索。
1、第七章 非线性方程(组)的数值解法,数值分析,2020/8/7,Numerical Analysis,2,本章内容,非线性方程求解,二分法,不动点迭代法及其加速,牛顿法、弦截法、抛物线法,求根问题的敏感性与多项式的零点 非线性方程组的数值求解,2020/8/7,Numerical Analysis,3,本讲内容,迭代格式 加速算法 收敛性,非线性方程求解介绍 二分法及其收敛性 不动点迭代及其加速,2020/8/7,Numerical Analysis,5,非线性方程数值解法,几个基本概念,实根与复根 根的重数 f(x)=(xx*)m g(x) 且 g(x*) 0, 则 x*为 f(x)=0 的
2、 m 重根 有根区间：a, b 上存在 f (x) = 0 的一个实根,研究内容：在有根的前提下求出方程的近似根,2020/8/7,Numerical Analysis,6,二分法（对分法）,基本思想,将有根区间进行对分，找出根所在的小区间，然后再对该小区间对分，依次类推，直到有根区间的长度满足给定的精度为止,2020/8/7,Numerical Analysis,7,二分法,算法 ：(二分法 ),(1) 计算 f(a)，f(b)，若 f(a) f(b) 0 ，则停止计算,(2) 对 k = 1, 2, . , maxit,计算 f(x)，其中,若 |f(x)| 或 b-a，停止计算，输出近似
3、解 x,若 f(a) f(x) 0，则令 b = x; 否则令 a = x,优点：简单易用，总是收敛 缺点：收敛速度慢，不能求复根和偶数重根 总结：一般用来计算解的一个粗糙估计,2020/8/7,Numerical Analysis,8,误差分析,记 a1 = a, b1 = b, 第 k 步的有根区间为 ak, bk,结论：二分法总是收敛的,2020/8/7,Numerical Analysis,9,不动点迭代,基本思想,构造 f (x) = 0 的一个等价方程：,2020/8/7,Numerical Analysis,10,不动点迭代,具体过程,任取一个迭代初始值 x0 ，计算,得到一个迭
4、代序列： x0，x1，x2，. . . ，xn，. . .,k = 0, 1, 2, . .,几何含义：求曲线 y = (x) 与直线 y = x 的交点,2020/8/7,Numerical Analysis,11,x2,2020/8/7,Numerical Analysis,12,连续性分析,设 (x) 连续，若 收敛，即 ，则,收敛性分析,性质：若 ，则不动点迭代收敛，且 x* 是 f(x)=0 的解；否则迭代法发散。,2020/8/7,Numerical Analysis,13,解的存在唯一性,定理：设 (x) Ca,b 且满足,证明：P216,对任意的 xa,b 有 (x)a,b 存
5、在常数 0L1，使得任意的 x, ya,b 有,则(x) 在 a,b 上存在唯一的不动点 x*,解的存在唯一性,2020/8/7,Numerical Analysis,14,收敛性分析,定理：设 (x) Ca,b 且满足,证明：P217,对任意的 xa,b 有 (x)a,b 存在常数 0L1，使得任意的 x, ya,b 有,则对任意初始值 x0a,b，不动点迭代 xk+1=(xk) 收敛，且,不动点迭代的收敛性,2020/8/7,Numerical Analysis,15,收敛性分析,不动点迭代的收敛性,若 (x)C1a,b 且对任意 xa,b 有 |(x)|L1 则上述定理中的结论成立。,收
6、敛性结论表明：收敛性与初始值的选取无关,2020/8/7,Numerical Analysis,16,举例,例：求 f(x) = x3 x 1=0 在区间 1, 2 中的根,2020/8/7,Numerical Analysis,17,局部收敛,定义：设 x* 是 (x) 的不动点，若存在 x* 的某个 -邻域 U(x*) =x*- , x* + ，对任意 x0U(x*)，不动点迭代 xk+1 = (xk) 产生的点列都收敛到 x*，则称该迭代局部收敛。,局部收敛,2020/8/7,Numerical Analysis,18,收敛速度,定义：设迭代 xk+1 = (xk) 收敛到 (x) 的不
7、动点 x*， 记 ek = xk x*，若,其中常数 C0，则称该迭代为 p 阶收敛。,当 p =1 时称为线性收敛，此时 C 1 时称为超线性收敛,二分法是线性收敛的 若 (x*) 0，则不动点迭代 xk+1 = (xk) 线性收敛,2020/8/7,Numerical Analysis,19,收敛速度,定理：设 x* 是 (x) 的不动点，若 (p)(x) 在 x* 的某邻域内连续，且,则迭代 xk+1 = (xk) 是 p 阶收敛的。,证明：P219,2020/8/7,Numerical Analysis,20,Aitken 加速,Aitken 加速,若 (x) 变化不大，则可得：,20
8、20/8/7,Numerical Analysis,21,Aitken 加速,2020/8/7,Numerical Analysis,22,Steffenson 加速,Steffenson 加速,将 Aitken 加速技巧与不动点迭代相结合,k = 0, 1, 2, . . .,迭代函数：,2020/8/7,Numerical Analysis,23,Steffenson 加速,定理：若 x* 是 (x) 的不动点，则 x* 是 (x) 的不动点。反之，若 x* 是 (x) 的不动点，且 ”(x) 存在，(x*) 1，则 x* 是 (x) 的不动点，且 Steffenson 加速迭代是二阶收敛
9、的。,若原迭代是 p 阶收敛的，则 Steffenson 加速后 p+1 阶收敛 原来不收敛的迭代，Steffenson 加速可能收敛,2020/8/7,Numerical Analysis,24,举例,例：用 Steffenson 加速法求 f(x) = x3 x 1=0 在区间 1, 2 中的根（取 (x) = x3 1）,clear; clc f = inline(x3-x-1,x); g = inline(x3-1,x); fprintf(True solution: x = %.4fn,fzero(f,1,2) n = 5; % 设置迭代步数 x = 1.5; % 迭代初始值 % 不
10、动点迭代 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,2020/8/7,Numerical Analysis,25,例：用 Steffenson 加速法求 f(x) = 3x2 ex
11、=0 在区间 3, 4 中的根（取 (x) = 2ln(x) + ln3）,clear; clc f = 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
12、)tol, break, end end % 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, end end,2020/8/7,Numerical Analysis,26,本讲内容,Newton 法及其收敛性 牛顿下山法 弦截法与抛物线法,2020/8/7,Numerical Analysis,
13、27,Newton 法,基本思想,将非线性方程线性化,设 xk 是 f (x)=0 的近似根，将 f(x) 在 xk 处 Taylor 展开,条件： f(x) 0,2020/8/7,Numerical Analysis,28,Newton 法,x,y,x*,xk,xk+1,2020/8/7,Numerical Analysis,29,Newton 法,算法 ：( Newton 法 ),(1) 任取迭代初始值 x0,(2) 对 k = 1, 2, . , maxit，计算,判断收敛性，若收敛，则停止计算，输出近似解,2020/8/7,Numerical Analysis,30,收敛性,k = 0
14、, 1, 2, . . .,迭代函数,2020/8/7,Numerical Analysis,31,举例,例：用 Newton 法求 f(x) = xex 1=0 的解,% Newton 迭代 clear; clc f = 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)tol, break, end x0 =
15、x; end,2020/8/7,Numerical Analysis,32,举例,例(P224)：用 Newton 法求 f(x) = x2 C=0 的正根,对任意 x00， 总有 |q|1， 即牛顿法收敛,2020/8/7,Numerical Analysis,33,牛顿法,牛顿的优点,牛顿法是目前求解非线性方程 (组) 的主要方法,至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。,先用其它算法获取一个近似解，然后使用牛顿法,需要求导数！,2020/8/7,Numerical Analysis,34,简化的Newton法,线性收敛,简化的 Newton 法,基本思想：用 f(
16、x0) 替代所有的 f(xk),2020/8/7,Numerical Analysis,35,Newton下山法,下山因子的取法： 从 =1 开始，逐次减半，直到满足下降条件,基本思想：要求每一步迭代满足下降条件,具体做法：加下山因子 ,Newton下山法,保证全局收敛,2020/8/7,Numerical Analysis,36,重根情形,且,重根情形,2020/8/7,Numerical Analysis,37,重根情形,令,x* 是 (x)=0 的单重根,2020/8/7,Numerical Analysis,38,举例,例：求 x4 - 4x2 4=0 的二重根,2020/8/7,Numerical Analysis,39,% 重根 clear; clc f = inline(x4 -4*x2 + 4,x); g1 = inline(x-(x2-2)/(4*
