资源预览内容
第1页 / 共48页
第2页 / 共48页
第3页 / 共48页
第4页 / 共48页
第5页 / 共48页
第6页 / 共48页
第7页 / 共48页
第8页 / 共48页
第9页 / 共48页
第10页 / 共48页
亲,该文档总共48页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第七章 非线性方程(组)的数值解法,数值分析,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 的 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,停止计算,输出近似解 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 ,计算,得到一个迭代序列: 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 存在常数 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 则上述定理中的结论成立。,收敛性结论表明:收敛性与初始值的选取无关,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) 的不动点 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) 变化不大,则可得:,2020/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 加速迭代是二阶收敛的。,若原迭代是 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; % 迭代初始值 % 不动点迭代 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=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)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,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, 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 = 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(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*
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号