第三章非线性方程求根
1 第三章 非线性方程求根
非线性方程求根 ■非线性科学是当今科学发展的一个重要研究方向 非线性方程的求根非常复杂 ■例如： a=1 无解 π sin(x)=y 1 2 [y=x2+a 一个解 无穷组解 a=4 = x=y2+a a=0 两个解 2 a=-1四个解 2
¡ 非线性科学是当今科学发展的一个重要研究方向 ¡ 非线性方程的求根非常复杂 ¡ 例如： 2 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 3
¡ 非线性方程的根通常不止一个，很难找到所有的解 ¡ 非线性方程求根，通常需要给定初始值或求解范围， 用迭代法求解 ¡ （介值定理）设 是区间 上的一个连续函数， 那么 取到 与 之间的任何一个值，即如果 是 与 之间的一个数，那么存在一个数 使得 （推论） 3 f (x) [a,b] f (x) f (a) f (b) f (a) f (b) f (c) y c [a,b] f (a) f (b) 0 x,s.t., f (x) 0 y
对分法 ■ 基于微积分中的介值定理，对区间[a,b]不断进行细分 ，缩小搜索区问 ■停上标准：x1-x<,或f(x<E2 f6) y=f(x) f(p) P3 a=a1 P2 b=b1 f(p2) f(a) Pi b1 P2 b2 a3 pa ba 4
¡ 基于微积分中的介值定理，对区间 不断进行细分 ，缩小搜索区间 ¡ 停止标准： 或 4 [a,b] 1 1 x x ε k k 2 f (x) ε
对分法 ■ 对分算法 Algorithm 6 Bisection Algorithm Input: f(z),a,b,M,6, 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+e 10: o←-f(c): 11: if el<6 or wl<then 12: return true; 13: end if 14: if sign(u)!sign(v)then b←c: 16: U←w 17: else 18: a←c: 19: u←w: 20: end if 21:end for 22:return false; Output: a,b,u,v 5
¡ 对分算法 5
迭代法 ■ 基本思想：将方程f(x)=0转换成等价形式X=p(x),给 定初值x。,构造迭代序列： xk+1=p(xk),k=1,2,… 若迭代收敛，即 limx=lim()=x, 则有f(x)=0 ■基本问题： ●如何构造迭代格式？ ●是否收敛？收敛速度？ ●收敛的条件？（例如是否与初值相关？） 6
¡ 基本思想：将方程 转换成等价形式 ，给 定初值 ，构造迭代序列： 若迭代收敛，即 则有 ¡ 基本问题： l 如何构造迭代格式？ l 是否收敛？收敛速度？ l 收敛的条件？（例如是否与初值相关？） 6 f (x) 0 x (x) 0 x 1 ( ), 1,2, k k x x k * 1 lim lim ( ) , k k k k x x x * f (x ) 0
迭代法 1958 定理：设p(x)在区间[a,b]上的连续，如果p(x)满足 (1)当x∈[a,b)时，有a≤p(x)≤b; (2)(x)在[a,b1上可导，并且存在正数L<1,使对任 意的x∈[a,],都有1p(x)KL, 则存在雅一的点xe[a,],使得x=p(x)成立，而且送代 格式x1=o(x)对于任意的初值，∈[a,b]均收敛于p(x)的不动 点x,并有误差估计公式 1以-xs2xx ·构造迭代格式的要素： ·等价形式x=p(x)满足|p(x)K1; ·初始值取自x的充分小领域；
¡ 定理：设 在区间 上的连续，如果 满足 （1）当 时，有 ； （2） 在 上可导，并且存在正数 ，使对任 意的 ，都有 ， 则存在唯一的点 ，使得 成立，而且迭代 格式 对于任意的初值 均收敛于 的不动 点 ，并有误差估计公式 ¡ 构造迭代格式的要素： l 等价形式 满足 ； l 初始值取自 的充分小领域； 7 (x) [a,b] (x) x [a,b] a (x) b (x) [a,b] L 1 x [a,b] ' | (x) | L * x [a,b] * * x (x ) 1 ( ) k k x x 0 x [a,b] (x) * x * 1 0 | | | |. 1 k k L x x x x L x (x) ' | (x) | 1 * x
收敛阶 ■定义：设送代格式xk1=p(x)收敛到p(x)的不动点x, 记e:=x-,若m=C>0,则称该送代格式为p k-→o|ekIP 阶收敛的，其中C称为渐进误差常数 8
¡ 定义：设迭代 格式 收敛到 的不动点 ， 记 ，若 ，则称该迭代格式为 阶收敛的，其中 称为渐进误差常数 8 1 ( ) k k x x (x) * x 0 | | | | lim 1 C e e p k k k * k k e x x p C
Newton送代法 ■ 将函数f(x)在x,处做Taylor展开： f(x)-x)+f)+( 2 f(xo)+f'(xo)(x-x)≈0 x4 Slopef'(pi)/y=f(x) ■ Newton送代格式： (p1f(p)) 。-2 Po Slopef'(po) Po.f(po》 9
¡ 将函数 在 处做Taylor展开： ¡ Newton迭代格式： 9 f (x) 0 x 0 2 0 0 0 0 ''( ) ( ) ( ) '( )( ) ( ) 2! f x f x f x f x x x x x 0 0 0 f (x ) f '(x )(x x ) 0 0 1 0 0 ( ) '( ) f x x x f x 1 ( ) , 1,2, '( ) k k k k f x x x k f x
Newton迭代法 I(收敛性)设f国)EC[a,1,x为fx)的单根，则存在δ>0，C>0 使得对任意的初值x,∈(x-6,x+),Newton迭代法 是2阶收敛的，即有|x1-xKC1x,-xP(n≥0) ■（重根情形)若x)∈Cm[a,b1,x为f)的m重根，则存在 δ>0，C>0,使得对任意的初值x。∈(x-6,x'+δ)，Newton 送代法1阶收敛的，即有|x1-xKC1x,-x1(n≥0) ■修正： mf(xx) X1=Xf代x) →1x1-xKC1x,-xP(n≥0) 4(x)=) f(x) f(x)f(x) f(x)=(x-x)"p(x) =-f(") 10
¡ （收敛性）设 ， 为 的单根，则存在 ，使得对任意的初值 ，Newton迭代法 是2阶收敛的，即有 ¡ （重根情形）若 ，为 的 重根，则存在 ，使得对任意的初值 ，Newton 迭代法1阶收敛的，即有 ¡ 修正： 10 2 f (x)C [a,b] * x f (x) 0, C 0 * * 0 x (x , x ) * * 2 1 | | | | ( 0). n n x x C x x n 1 ( ) [ , ] m f x C a b * x f (x) m * * 1 | | | | ( 0). n n x x C x x n 0, C 0 * * 0 x (x , x ) 1 ( ) '( ) k k k k mf x x x f x * * 2 1 | | | | ( 0). n n x x C x x n '( ) ( ) ( ) f x x f x * ( ) ( ) ( ) m f x x x p x 1 2 ( ) '( ) '( ) ( ) ''( ) k k k k k k k f x f x x x f x f x f x