(非线性方程的求根 A 非线性方程的求根 主讲:王开荣 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 非线性方程的求根 主讲：王开荣 11 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 第五章非线性方程的求根 §1二分法 基本思想:利用零点定理确定根的存在区间,逐步将含 根的区间对分.通过判别函数值的符号,将根的存在区 间缩小到充分小,从而求出满足精度要求的根的近似值 计算步骤为,计算函数值f(a+b)/2) 1.若(a+b)2)E,则 当f(a+b)/2)fa)0,a1((a+b)/2,b1b 继续此过程就得到一个包含根的区间套,满足 2 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 22 第五章 非线性方程的求根 §1 二分法 基本思想: 利用零点定理确定根的存在区间, 逐步将含 根的区间对分. 通过判别函数值的符号, 将根的存在区 间缩小到充分小, 从而求出满足精度要求的根的近似值. 计算步骤为, 计算函数值f((a+b)/2), 1. 若|f((a+b)/2)|e,则 当f((a+b)/2)·f(a)0, a1¬(a+b)/2, b1¬b. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 ( la, b=a1,b=a2, b2=.lan, bnl= (2)(ak(bk)<0,a∈(ak,b1),k=1,2,…,n, (3)bkak=(b-a)/2k,k=1,2,…,n, 当n充分大时就有:≈(an+bn)/2 误差估计式为 at6 b 2 注1优点:方法和计算都简单,且对函数(x)的性质要求 不高,只须连续即可.其缺点是不能求偶数的重根在实 用中常用二分法来判别根的存在区间,或求出根的初始 近似值,以便使用其它的快速选代法求根 3 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 33 当 n 充分大时就有: a»(an +bn )/2 1 2 2 n n n a b b a a + + - 误差估计式为 - £ (1)[a, b]É[a1 , b1 ]É[a2 , b2 ]É···É[an , bn ]É (2)f(ak )f(bk )<0, aÎ(ak , bk ), k=1, 2, ··· , n, ··· (3) bk -ak=(b-a)/2k , k=1, 2, ··· , n, ··· 注1 优点:方法和计算都简单, 且对函数f(x)的性质要求 不高, 只须连续即可. 其缺点是不能求偶数的重根. 在实 用中常用二分法来判别根的存在区间, 或求出根的初始 近似值, 以便使用其它的快速迭代法求根. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 注2应用中常常是取适当的步长h,对区间{a,b从左到 右逐步扫描,检查小区间的两端函数值符号,从而判断 根的存在区间,再用收敛速度快的选代法,选代计算求 根.步长h选择应适当,过大可能漏掉根,过小将会增加 计算的工作量 §2迭代法 设方程x)=0可以转化为等价的形式=g(x),从某个 初值x0出发令 xk+1=g(x1),k=0,1,2 (5.1) 得到序列{xA}.当g(x)连续,且序列{x收敛时,有 lim xkI= lim g(xk)=gdim x) →0 k→∞ k→∞ 即PQ=g(a),也即序列{xk的极限是方程f(x)=0的根 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 44 注2 应用中常常是取适当的步长h, 对区间[a, b]从左到 右逐步扫描, 检查小区间的两端函数值符号, 从而判断 根的存在区间, 再用收敛速度快的迭代法, 迭代计算求 根. 步长h选择应适当, 过大可能漏掉根, 过小将会增加 计算的工作量. §2 迭代法 设方程f(x)=0可以转化为等价的形式x=g(x). 从某个 初值x0出发令 得到序列{xk }. 当g(x)连续, 且序列{xk }收敛时, 有 1 lim lim ( ) (lim ) k k k k k k x g x g x + ®¥ ®¥ ®¥ = = 即a=g(a), 也即序列{xk }的极限a是方程f(x)=0的根. xk+1 =g(xk ), k=0, 1, 2, ··· (5.1) PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 称(51)为选代公式,函数g(x)为选代函数,构造选代公 式的方法称为选代法 迭代公式构造的不同,可能会出现发散或无意义的 情形,即使是收敛的,收敛的速度也有快慢之分 单点迭代法计算第k+1个近似值xk时仅用到第k个点 处的信息,如(51) 多点选代法:计算xk+1时需要用到前面p个点处的信 息一般形式为:xk+1=8(xkxk1,…,x+) 多点选代法需要p个起始的初始值:xnx1,…,x 、迭代法的收敛性 选代法一般只具有局部的收敛性,即当初始值x0充分 接近于根a时,选代法产生的序列{x}才收敛于根 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 55 称(5.1)为迭代公式, 函数g(x)为迭代函数. 构造迭代公 式的方法称为迭代法. 迭代公式构造的不同, 可能会出现发散或无意义的 情形, 即使是收敛的, 收敛的速度也有快慢之分. 单点迭代法 计算第k+1个近似值xk+1时仅用到第k个点 处的信息,如(5.1) 多点迭代法：计算xk+1时需要用到前面p个点处的信 息一般形式为: xk+1 =g(xk , xk-1, ··· , xk-p+1) 多点迭代法需要p个起始的初始值: x0 , x1 , ··· , xp-1. 一 、迭代法的收敛性 迭代法一般只具有局部的收敛性, 即当初始值x0充分 接近于根a时, 迭代法产生的序列{xk }才收敛于根a. PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 定义5,1若存在常数L>0,使x1,x2∈[a,b有: g(x1)-g(x2)≤Lx1-x2 则称g(x)在{a,b上满足 Lipschitz条件,L称为 Lipschitz 常数 注1若g(x)连续→g(x)满足 Lipschitz条件→g(x)连续 注2:由 Lagrange定理lg(x1)-g(x2)=g(2)川1-x2 所以常取L=maxg(x),x∈[a,b 定理52对选代方程x=g(x),若选代函数g(x)满足 ①当x∈|a,b时,有g(x)∈a,b; ②g(x)在{a,b上满足 Lipschi条件且 Lipschitz常数 L<1,则有: PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 66 则称g(x)在[a, b]上满足Lipschitz条件, L称为Lipschitz 常数. 定义5.1 若存在常数 L>0, 使"x1 , x2Î[a, b]有: ①当xÎ[a, b]时, 有g(x)Î[a, b]; 注1 若g¢(x)连续Þg(x)满足Lipschitz条件Þg(x)连续. 定理5.2 对迭代方程x=g(x), 若迭代函数g(x)满足 ②g(x)在 [a,b]上满足Lipschitz条件且Lipschitz常数 L<1, 则有: |g(x1 )-g(x2 )|£ L|x1 -x2 | 注2:由Lagrange定理 |g(x1 )-g(x2 )|=|g¢(x)|×|x1 -x2 | 所以常取 L=max|g¢(x)|, xÎ[a, b] PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 ①x=g(x)在(a,b)内存在唯一的根a ②对vx∈{a,b,选代公式xx=g(x)均收敛,且 lim x, =a L X-x 1-L x-xo L ⑤ g(a 由③常用xk+1-xk,作为选代终止的判别条件,由 ④选代收敛速度与L的值有关,当L<<1时收敛较快,当 L接近于1时收敛较慢.并可由④的右端来近似估计迭 代次数 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 77 ⑤ ③ ④ 1 1 k k k L x x x L a - £ - - - 1 0 1 k k L x x x L a - £ - - 1 lim ( ) k k k x g x a a a + ®¥ - = ¢ - 由③常用|xk+1-xk |<e, 作为迭代终止的判别条件, 由 ④迭代收敛速度与L的值有关, 当L<<1时收敛较快, 当 L接近于1时收敛较慢. 并可由④的右端来近似估计迭 代次数. ②对"x0Î[a, b], 迭代公式xk+1 =g(xk )均收敛, 且 ① x=g(x)在(a, b)内存在唯一的根a. lim k k x a ®¥ = PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 收敛速度 定义52记选代公式的第k次选代误差为E=0-x2并 假设选代公式是收敛的,若存在实数p1使得 k+1 Im =C≠0 k 则称选代公式是p阶收敛的,C称为渐近误差常数 当p=1时,称选代公式为线性收敛;当p=2时,称选代 公式为二阶收敛;当1p<2或p=1,C=0时,称选代公式 为超线性收敛 定理53对选代公式x+=g(xb),若gp(x)在根的邻域内 连续并且 g()=g"(a)=…=g(p)(a)=0,g)()≠0 则该选代公式在根α的邻域内是p阶收敛的 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 88 二、收敛速度 定义5.2 记迭代公式的第 k 次迭代误差为ek =a-xk ,并 假设迭代公式是收敛的, 若存在实数p³1使得 1 lim 0 k p k k C e e + ®¥ = ¹ 则称迭代公式是 p 阶收敛的, C 称为渐近误差常数. 当 p=1时, 称迭代公式为线性收敛; 当p=2时, 称迭代 公式为二阶收敛; 当 1<p<2或p=1, C=0 时, 称迭代公式 为超线性收敛. 定理5.3 对迭代公式xk+1 =g(xk ), 若g (p) (x)在根a的邻域内 连续并且 则该迭代公式在根a的邻域内是p阶收敛的. g¢(a)=g²(a)=···= g (p-1)(a)=0, g (p) (a)¹0 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 §3常用的选代方法 、 Newton方法 f(k) 迭代公式 k+1=X 8 Im h+ f"() 有 k→ 8 2f() 当f()≠0时 Newton法是二阶收敛的. Newton法的 几何意义是,用点(x,八x1处的切线与x轴交点处的横 坐标作为x1 简化 Newton方法 在应用 Newton选代公式时,f(x)很难计算的,甚至在 某些近似值x处,f'(x)的值很小,使选代过程无法进 行下去.可采用简化 Newton法 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 99 §3 常用的迭代方法 一 、Newton方法 迭代公式 1 ( ) ( ) k k k k f x x x f x + = - ¢ 有 1 2 ( ) lim 2 ( ) k k k f f e a e a + ®¥ ¢¢ = - ¢ 当f ¢(a)¹0时 Newton法是二阶收敛的. Newton法的 几何意义是, 用点(xk , f(xk ))处的切线与 x 轴交点处的横 坐标作为xk+1. 二、简化Newton方法 在应用Newton迭代公式时, f ¢(x)很难计算的, 甚至在 某些近似值xk处, |f ¢(xk )|的值很小, 使迭代过程无法进 行下去. 可采用简化Newton法 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com
(非线性方程的求根 f(x2) Xu+=xk 其中C为一常数,常取C=f(x0)有选代公式 k+1=x f(o) 其几何意义为用过点(x1,(x)且平行于(x0,f(x)处 切线的直线与x轴交点的横坐标作为xk1 简化 Newton只具有超线性收敛性 、 Newton下山法 在 Newton法中,若函数f(x)表达式比较复杂,初值x选 取比较困难时,为扩大初值的选取范围,可采用选代公式 f(xr) k+1=x X k=0.1.2… 其中参数入选取为0<1且满足下山条件 PDF檔案使用"pdfFactoryPro"試用版本建立www.pdffactory.com
非线性方程的求根 1010 1 ( ) k k k f x x x C + = - 其中C为一常数, 常取C= f ¢(x0 )有迭代公式 1 0 ( ) ( ) k k k f x x x f x + = - ¢ 其几何意义为用过点(xk , f(xk ))且平行于(x0 , f(x0 )) 处 切线的直线与x轴交点的横坐标作为xk+1. 简化Newton只具有超线性收敛性. 三、Newton下山法 在Newton法中, 若函数f(x)表达式比较复杂, 初值x0选 取比较困难时, 为扩大初值的选取范围, 可采用迭代公式 1 ( ) , 0,1,2, ( ) k k k k k f x x x k f x + = - = l ¢ L 其中参数lk选取为0<lk£1且满足下山条件 PDF 檔案使用 "pdfFactory Pro" 試用版本建立 www.pdffactory.com