第4章非线性方程求根 非线性科学是当今科学发展的一个重要研究方向,而非线性方程的求根也成了 个不可缺的内容。但是,非线性方程的求根非常复杂 通常非线性方程的根的情况非常复杂: a=1无解 sin(x)=y y=x +a 一个解 2 无穷组解 4 x=y +a a=0两个解 y 2 a=-1四个解
第4章 非线性方程求根 非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一 个不可缺的内容。但是，非线性方程的求根非常复杂。 通常非线性方程的根的情况非常复杂： = = 2 1 ) 2 sin( y x y 无穷组解 = − = = = = + = + 1 0 4 1 1 2 2 a a a a x y a y x a 无解 一个解 两个解 四个解
所以,只在某个区域内可能解存在唯一,而且经常很简单的形式得不到精确解: e-Cos(a)=0 因此,通常我们用迭代法解非线性方程 看迭代法之前,先看看一种简单直观的方法 原理:f(a)·f(b)<0→3x,s1,f(x)=0
所以，只在某个区域内可能解存在唯一，而且经常很简单的形式得不到精确解： 因此，通常我们用迭代法解非线性方程 看迭代法之前，先看看一种简单直观的方法 原理： f (a) f (b) 0 x,s.t., f (x) = 0 e −cos( x) = 0 x
41对分法 什么时候停止? b 血2b x+1-xk<1或f(x)<62
4.1对分法 a b x1 x2 a b 什么时候停止？ 1 1 x x ε k+ − k 2 或 f (x) ε x*
算法 While(la-b>eps X=(a+b)/2 f(×) 若(f(x)<eps)x为解 若f(x)*f(b)0修正区间为[x,b] 若f(a)*(x)<0修正区间为ax End while 每次缩小一倍的区间,收敛速度为1/2,较慢,且只能求一个根,使用条件限制较大 不能保证x的精度
While(|a-b|>eps) x=(a+b)/2 f(x) 若(|f(x)|<eps) x为解 若f(x)*f(b)<0 修正区间为[x,b] 若f(a)*f(x)<0 修正区间为[a,x] End while 每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，使用条件限制较大 算法 2 x* x 不能保证 x 的精度
42迭代法 等价变换 f∫(x)=0 x=g(x) ∫(x)的根←◆g(x)的不动点 从一个初值x出发,计算x1=g(x),x2=g(x1), 思xk1=g(x),若{x%收敛,即存在x*使得 路mmx=x,且g连续,则由lmx1=问阳知x) gx*),即x*是g的不动点,也就是f的根
4.2 迭代法 f (x) = 0 x = g (x) 等价变换 f (x) 的根 g (x) 的不动点 思 路 从一个初值 x0 出发，计算 x1 = g(x0 ), x2 = g(x1 ), …, xk+1 = g(xk ), … 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。 k k=0 x lim x x * k k = → ( ) k k k k x g x → + → lim 1 = lim
迭代法的基本步骤如下 1、给出方程的局部等价形式f(x)=0<x=9(x) 2、取合适的初值,产生迭代序列x0,x1=9(x1) 3、求极限x*=mxn易知,该值为方程的根 n→)+0 ∧ 定收敛吗?
迭代法的基本步骤如下： 1、给出方程的局部等价形式 f (x) = 0 x =(x) 2、取合适的初值，产生迭代序列 , ( ) 0 i 1 i x x = x + 3、求极限 n n x x →+ * = lim 易知，该值为方程的根 一定收敛吗？
y=x y y=x y=glx) y=glr)
x y y = x x* y=g (x ) x 0 p 0 x 1 p 1 ✓ x y y = x x* y=g (x ) x 0 p 0 x 1p 1
定理 qp(x),x∈[a,b]若满足: 1、a≤(x)≤b,x∈[a,b 2、0(x)可导,且存在正数L<1,使得对任意的x,有(x)≤L 则有: 1、存在唯一的点x*,x*=p(x*) 2、Vx∈[a,b]迭代收敛,且有误差估计 x*xs 1-L
(x), x[a,b] 若满足： 1、 a (x) b, x[a,b] 2、 (x) 可导，且存在正数L<1，使得对任意的x，有 '(x) L 则有： 1、存在唯一的点 x*, x* =(x*) 2、 x a,b 0 迭代收敛，且有误差估计 1 0 1 * x x L L x x k k − − − 定理
证明 ①存在唯一性 做辅助函数v(x)=x-q(x),则有V(a)≤0,v(b)≥0 所以,存在点x*2S,t,/(x*)=0→x*=p(x*) 若x**=((x*),则有: x*一x*料=0(x*)-(x**)=回(5Xx*一x*≤Lx*-x*料 又,1<1→x*=x* ②yx0∈[a,b]则 xx+1-x*=p(xk)0(x*)=(5)(xk-x x1-x米≤lxkx料≤…≤Z|x-x料 所以,任意的初值都收敛
①存在唯一性 ② 做辅助函数 (x) = x −(x) ，则有 (a) 0, (b) 0 所以，存在点 x*,s.t., (x*) = 0 x* =(x*) 若 x** =(x**) ，则有： x*−x** = (x*)−(x**) = '()(x*−x**) L x*−x** 又， L 1 x*= x** [ , ] x0 a b 则 * ( ) ( *) '( )( *) 1 x x x x x x k+ − = k − = k − * * 0 * 1 1 x x L x x L x x k k − k − − + + 所以，任意的初值都收敛 证明：
③误差估计 x1-x|=10(x)-0(x-)≤Lxk-x1s…≤Zx1-x0 ktp x2≤|x k+p k+D-1 …+x ≤(+…+1)x-xl k + *一x/、<不 证毕 1-L
③误差估计 1 1 1 1 0 x x (x ) (x ) L x x L x x k k+ − k = k − k− k − k− − k p k k p k p k k x − x x − x + + x − x + + + −1 +1 ( ) 1 0 1 L L x x k p k + + − + + ( ) 1 0 1 0 1 1 1 x x L L x x L L L k p k − − − − − = 由p的任意性，令 1 0 1 * x x L L x x k k − − − p →+ 证毕