第四章非线性方程求根 2
2 第四章 非线性方程求根
非线性方程求根 非线性科学是当今科学发展的一个重要研究方向 非线性方程的求根非常复杂 ■例如： a= 无解 2 sin(x)=y 1 2 y=x2+a Q= -4 一个解 无穷组解 1 x=y2+a a=0 两个解 y= 2 a=-1四个解 3
非线性方程求根 非线性科学是当今科学发展的一个重要研究方向 非线性方程的求根非常复杂 例如： 3 = = 2 1 ) 2 sin( y x y π 无穷组解 = − = = = ⇒ = + = + 1 0 4 1 1 2 2 a a a a x y a y x a 无解 一个解 两个解 四个解
非线性方程求根 ■非线性方程的根通常不止一个，很唯找到所有的解 ·非线性方程求根，通常需要给定初始值或求解范围， 用送代法求解 ■（介值定理）设f(x)是区间[a,b]上的一个连续函数， 那么f(x)取到f(a与f(b)之间的任何一个值，即如果y 是f(a)与f(b)之间的一个数，那么存在一个数c∈[a,b] 使得f(c)=y (推论)f(a)f(b)<0→3x,s.t,f(x)=0 4
非线性方程求根 非线性方程的根通常不止一个，很难找到所有的解 非线性方程求根，通常需要给定初始值或求解范围， 用迭代法求解 （介值定理）设 是区间 上的一个连续函数， 那么 取到 与 之间的任何一个值，即如果 是 与 之间的一个数，那么存在一个数 使得 （推论） 4 f x( ) [,] a b f x( ) f a( ) f b( ) f a( ) f b( ) fc y ( ) = c ab ∈[,] f (a)⋅ f (b) < 0 ⇒ ∃x,s.t., f (x) = 0 y
对分法 ■基于微积分中的介值定理，对区间[a,b]不断进行细分 ，缩小搜索区间 ■停止标准：x+-x<,或f<2 YA f6) y=f(x) f(pi) P3 十 a=a P2 b=b1 f（p2) f(a) 0 四 a2 P2 b2 a3 p3 b3 5
对分法 基于微积分中的介值定理，对区间 不断进行细分 ，缩小搜索区间 停止标准： 或 5 [,] a b 1 1 x x ε k+ − k < 2 f x( ) ε <
对分法 ■ 对分算法 Algorithm 6 Bisection Algorithm Input: f(x),a,b,M,6.e 1:u←-f(a: 2:v←f(b) 3:e←b-a 4:if sign(u)==sign(v)then 5:return false; 6:end if 7:for k=1 to M do 8:e-e/2: 9:c←-a+eg 10:w←f(c: 11: if e<6 or w<then 12: return true; 13: end if 14: if sign(u)!sign(v)then 15: b←- 16: U←-U; 17: else 18: a←-c 19: u← 20:end if 21:end for 22:return false; Output: a,b,u,v 6
对分法 对分算法 6
迭代法 基本思想：将方程fx)=0转换成等价形式x=p(x),给 定初值，构造送代序列： Xk+1=p(xk)2k=1,2,. 若送代收敛，即 lim=lim()=x, 00 则有f(x)=0 ■基本问题： ●如何构造送代格式？ ●是否收敛？收敛速度？ ·收敛的条件？（例如是否与初值相关？）
迭代法 基本思想：将方程 转换成等价形式 ，给 定初值 ，构造迭代序列： 若迭代收敛，即 则有 基本问题： 如何构造迭代格式？ 是否收敛？收敛速度？ 收敛的条件？（例如是否与初值相关？） 7 f x() 0 = x x = ϕ( ) 0 x 1 ( ), 1,2, k k x xk + = = ϕ * 1 lim lim ( ) , k k k k x xx + ϕ →∞ →∞ = = * f x()0 =
迭代法 ■定理：设p(x)在区问[a,b]上的连续，如果p(x)满足 (1)当x∈[a,b]时，有a≤p(x)≤b; (2)p(x)在[a,b]上可导，并且存在正数L<1,使对任 意的x∈[a,b],都有Ip(x)KL, 则存在难一的点x∈[a,使得x=(x)成立，而且送代 格式x1=p(x)对于任意的初值x∈[a,b]均收敛于p(x)的不动 点x,并有误差估计公式 1x-xsx-x ■构造送代格式的要素： ●等价形式x=p(x)满足|p(x)K1; ●初始值取自x的充分小领域； 8
迭代法 定理：设 在区间 上的连续，如果 满足 （1）当 时，有 ； （2） 在 上可导，并且存在正数 ，使对任 意的 ，都有 ， 则存在唯一的点 ，使得 成立，而且迭代 格式 对于任意的初值 均收敛于 的不动 点 ，并有误差估计公式 构造迭代格式的要素： 等价形式 满足 ； 初始值取自 的充分小领域； 8 ϕ( ) x [,] a b ϕ( ) x x ab ∈[,] a xb ≤ ≤ ϕ( ) ϕ( ) x [,] a b L < 1 x ab ∈[,] ' | ( )| ϕ x L ≤ * x ab ∈[,] * * x x = ϕ( ) 1 ( ) k k x x + = ϕ 0 x ab ∈[,] ϕ( ) x * x * 1 0 | | | |. 1 k k L xx xx L −≤ − − x x = ϕ( ) ' | ( )| 1 ϕ x < * x
迭代法 》 ■定义：设送代格式xk+1=p(x)收敛到p(x)的不动点x, 记e,=x-x,若m=C>0,则称该迭代格式为p kexp 阶收敛的，其中C称为渐进误差常数 9
迭代法 定义：设迭代 格式 收敛到 的不动点 ， 记 ，若 ，则称该迭代格式为 阶收敛的，其中 称为渐进误差常数 9 1 ( ) k k x x + = ϕ ϕ( ) x * x 0 | | | | lim 1 = > + →∞ C e e p k k k * k k exx = − p C
Newton迭代法 ■ 将函数f(x)在x处做Taylor展开： fx)=/()+fXx-x)+I(x- 21 f(x)+f'(x)x-x)≈0 f(xo) Slopef"(p1)/y=f(x) x1=x0 f'(x) ■Newton迭代格式： (pL.f(p)) -12 Slopef'(po) (po.f(po) 10
Newton迭代法 将函数 在 处做Taylor展开： Newton迭代格式： 10 f x( ) 0 x 0 2 0 00 0 ''( ) ( ) ( ) '( )( ) ( ) 2! f x fx fx f x x x x x = + −+ − + 0 00 fx f x x x ( ) '( )( ) 0 + −≈ 0 1 0 0 ( ) '( ) f x x x f x = − 1 ( ) , 1,2, '( ) k k k k f x xx k f x + =− =
Newton迭代法 I（收敛性)设fx)eC[a,b],x为f(x)的单根，则存在8>0，C>0 ,使得对任意的初值x∈(x-6,x+δ)，Newton送代法 是2阶收敛的，即有|x+1-xKC|xn-xP(n≥0) (重根情形)若f(x)∈C[a,],x为f(x)的m重根，则存在 6>0,C>0,使得对任意的初值x∈(x-6,x+),Newton 送代法1阶收敛的，即有|xn1-xCxn-x|(n≥0) ■修正： mf(xx) Xk1=Xf(x) |xn41-xKC1x,-xP(n≥0)， 4(x)=x) f(x) f(x)f(x) f(x)=(x-x)"p(x) =:f(x-ff"(x,)
Newton迭代法 （收敛性）设 ， 为 的单根，则存在 ，使得对任意的初值 ，Newton迭代法 是2阶收敛的，即有 （重根情形）若 ，为 的 重根，则存在 ，使得对任意的初值 ，Newton 迭代法1阶收敛的，即有 修正： 11 2 f x C ab () [,] ∈ * x f x( ) δ > > 0, 0 C * * 0 xx x ∈− + (,) δ δ * * 2 1 | | | | ( 0). n n x x Cx x n + −≤ − ≥ 1 () [,] m f x C ab + ∈ * x f x( ) m * * 1 | | | | ( 0). n n x x Cx x n + −≤ − ≥ δ > > 0, 0 C * * 0 xx x ∈− + (,) δ δ 1 ( ) '( ) k k k k mf x x x f x + = − * * 2 1 | | | | ( 0). n n x x Cx x n + −≤ − ≥ ' ( ) ( ) ( ) f x x f x µ = * () ( ) () m f x x x px = − [ ] 1 2 ( ) '( ) '( ) ( ) ''( ) k k k k k kk fx f x x x f x fx f x + = − −