中国矿业大学：《数值计算方法》课程教学课件（讲稿）第2章 非线性方程求解 Solutions of Nonlinear Equation

中国矿亚大警CHINAUNIVERSITY OFMININGAND TECHNOLOGYCH2非线性方程求解/* Solutions of NonlinearEquation *s1二分法S2迭代法$3牛顿法及其变形

CHINA UNIVERSITY OF MINING AND TECHNOLOGY CH2 非线性方程求解 /* Solutions of Nonlinear Equation */ §1 二分法 §2 迭代法 §3 牛顿法及其变形

中国矿亚大整CHINAUNIVERSITY OFMININGANDTECHNOLOGY非线性方程求根求f(x)=0的根1.根的隔离与隔根区间(自习)(1)作图法(2)逐步搜索法2． 二分法原理：若feC[a,bl，且f(a)·f(b)<0，则f在（a,b)上必有一根

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 非线性方程求根 求 f (x) = 0 的根 1. 根的隔离与隔根区间 （自习） 2. 二分法 原理：若 f ∈C[ a, b ]，且 f ( a) · f ( b) < 0，则 f 在 ( a, b) 上必 有一根。 (1)作图法 (2)逐步搜索法

中国矿亚大医CHINAUNIVERSITYOFMININGANDTECHNOLOGYWhen to stop?七华b21f(x)<82Xk+1-<8或不能保证x的精度8X

CHINA UNIVERSITY OF MINING AND TECHNOLOGY a b x1 x 2 a b When to stop? 1 1 x x ε k + − k < 2 或 f ( x ) < ε 不能保证 x 的精 度 x* ε 2 x* x

Bisection Method中国矿亚大CHINAUNIVERSITYOFMININGANDTECHNOLOGY分析误差a+b有误差-第1步产生的x=2b-a第k步产生的x有误差-x≤2k对于给定的精度，可估计二分法所需的步数k：= k>[m(b-a)-Ine]b-a82kIn2①简单；对f（x）要求不高（只要连续即可）①无法求复根，收敛慢注：用二分法求根，最好先给出f（x）草图以确定根的大概位置。或用搜索程序，将a.b分为若干小区间，对每个满足f（a）f（b）<0的区间调用二分法程序，可找出区间la,bl内的多个根，且不必要求f(a):f（b）<0

CHINA UNIVERSITY OF MINING AND TECHNOLOGY Bisection Method 误差 分析 第 1步产生的 2 1 a b x + = 有误差 2 1 b a |x x*| − − ≤ 第 k 步产生的 xk 有误差 k k b a |x x*| 2 − − ≤ 对于给定的精度 ε ,可估计二分法所需的步数 k ： [ ( ) ] ln 2 ln ln 2 b a ε ε k b a k − − − ①简单; 对 f (x ) 要求不高 (只要连续即可) . ①无法求复根，收敛慢 注：用二分法求根，最好先给出 f (x ) 草图以确定根的大 概位置。或用搜索程序，将 [ a, b ]分为若干小区间，对每一 个满足 f ( a k)·f ( b k) < 0 的区间调用二分法程序，可找出区 间 [ a, b ]内的多个根，且不必要求 f ( a)·f ( b) < 0

中国矿亚大整CHINA UNIVERSITY OF MININGAND TECHNOLOGYsS2迭代法/*Fixed-Point Iteration *对方程：等价变换f(x)= 0x=@(x)f(x)的根(x）的不动点一般设?(x）至少是连续的

CHINA UNIVERSITY OF MINING AND TECHNOLOGY §2 迭代法 /* Fixed-Point Iteration */ 对方程 : f ( x ) = 0 x = ϕ ( x ) f (x) 的根 等价变换 ϕ ( x )的不动点 一般设 至少是连续的。 ϕ( ) x

中国矿亚大鉴CHINAUNIVERSITYOFMININGANDTECHNOLOGY一、基本思想与迭代格式设x是x=@(x）的精确解：x*=(x）任取x（一般±x），p(x）≠x，记xi =p(x)x, =p(x)Xk+1 = (xk)得到一序列x.如果（x的极限存在，必有limXk=xk→80

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 一、基本思想与迭代格式 * ** xx x x x 是 的精确解 = = ϕ ϕ ( ) : ( ). * 0 任取 一般 x x ( ), ≠ ( ) , * 0 ϕ x ≠ x 记 ( ) 1 0 x = ϕ x ( ) 2 1 x = ϕ x ( ) k 1 k x = ϕ x + { } . k 得到一序列 x * lim . k k x x →∞ 必有 = { } , k 如果 的极限存在 x 设

limx,=X中国矿亚大整CHINAUNIVERSITYOF MININGANDTECHNOLOGYk>00x*=limX= limp(xk-1)k→>0k-00=p(limxk-1) =Φ(x*)0p(x)基本迭代格式迭代函数Xk+1=0(x)limx=x迭代收敛limx不存在迭代发散k-80k80Ohyeah?Whotellsyou that the methodis convergent?-oblem?

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 基本迭代格式 迭代函数 迭代收敛 迭代发散 ( ) * = ϕ x k k x x → ∞ = lim * lim ( ) − 1 → ∞ = k k ϕ x (lim ) − 1 → ∞ = k k ϕ x ( ) k 1 k x = ϕ x + ϕ ( x ) * lim k k x x →∞ = lim k k x →∞ 不存在 * lim k k x x →∞ = So basically we are done! I can’t believe it’s so simple! What’s the problem? Oh yeah? Who tells you that the method is convergent?

中国矿亚大警CHINAUNIVERSITYOF MININGANDTECHNOLOGY几何意义：J=x求x=(x）的根求的交点（的横坐标）y=p(x)y(x)J=2y=xP(x1)y=(x)p(xo)XP(xo)P(x))1110收敛@ (x)1发散情形是否正确？收敛情

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 几何意义: ←⎯收敛情形 ⎯⎯⎯ ⎯ 发散情形 ⎯⎯⎯→ 求 的根 x x = ϕ( ) ( ) y x y ϕ x ⎧ = ⇔ ⎨ ⎩ = 求 的交点 (的横坐标 ) 是否正确 ? ϕ ′ ( x ) 1 发散

中国矿亚大整CHINAUNIVERSITY OFMININGANDTECHNOLOGY例1:用选代法求 x3 -x2-1=0 在[1.3,1.6]内的根解：建立下面三个迭代格式：112) =(+x) 3) ×=71) xk+ =1+一(x -1)/2书取选代初值xc=1.3(或1.6)，编程可得如下结论：格式1)、2)收敛，且2)收敛速度快，3)发散注：在使用迭代法计算的时候，必须注意考虑：(1)如何构造收敛的迭代格式(2)如何建立收敛快的迭代格式

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 例 1 ：用迭代法求 在 1 0 [1.3,1.6]内的根 3 2 x − x − = 解：建立下面三个迭代格式： 1 2 1 1) 1 k + = + k x x ( ) 1 3 2 2) 1 1 / k k x = + x + ( ) 1 1 2 1 1 3 ) / k k x x − + = 取迭代初值x 0=1.3( 或1.6) ，编程可得如下结论 ： 格式1) 、2)收敛，且2)收敛速度快，3)发散 注：在使用迭代法计算的时候，必须注意考虑： (1)如何构造收敛的迭代格式 (2)如何建立收敛快的迭代格式

中国矿基天整CH选代结果ININGAND选代2结果迭代3结果1.3000000x(1)1.30000001.3000000x(2)1.59171601.39075541.8257419x(3)1.39470161.43162721.10046911.51408791.4501476x(4)3.15488661.4362122x(5)1.45855870.6812206x(6)1.48480021.46238200.0000000x(7)1.45359051.46412070.3535041x(8)1.47327751.46491140.3905038x(9)1.46071351.46527110.4523004x(10)1.46867301.46543470.4742852x(11)1.46360681.46550910.48756581.4668219x(12)1.46554300.4936729x(13)1.46477771.46555840.4968626x(14)1.46607581.46556540.4984245x(15)0.49921391.46525081.4655686

CHINA UNIVERSITY OF MINING AND TECHNOLOGY 迭代 1结果 迭代 2结果 迭代 3结果 x( 1) 1.3000000 1.3000000 1.3000000 x( 2) 1.5917160 1.3907554 1.8257419 x( 3) 1.3947016 1.4316272 1.1004691 x( 4) 1.5140879 1.4501476 3.1548866 x( 5) 1.4362122 1.4585587 0.6812206 x( 6) 1.4848002 1.4623820 0.0000000 x( 7) 1.4535905 1.4641207 0.3535041 x( 8) 1.4732775 1.4649114 0.3905038 x( 9) 1.4607135 1.4652711 0.4523004 x(10) 1.4686730 1.4654347 0.4742852 x(11) 1.4636068 1.4655091 0.4875658 x(12) 1.4668219 1.4655430 0.4936729 x(13) 1.4647777 1.4655584 0.4968626 x(14) 1.4660758 1.4655654 0.4984245 x(15) 1.4652508 1.4655686 0.4992139