第七章方程求根 求解非线性方程 f(x)=0 f是非线性函数, 例:代数方程 f()=anx +an-x +…+a1+m。=0,n>1 例超越方程 f(x)=e+sinx=o
第七章 方程求根 1 1 1 0 ( ) 0 ( ) 0, 1 : ( ) sin 0 n n n n x f x f f x n f x x a x a x a x a e − − = = + + + + = = + = 求解非线性方程 是非线性函数， 例：代数方程 。 例 超越方程
§1.非线性方程实根的对分法(二分法) 设f(x)在[a,b]上连续且[a,b有且仅有一个根又 f(a)·f(b)0 a+b D,若f 2/0输出根x=a+b 2否则若+6 a+b al 2=b反之bq+b a. 5)p区国重道D外意共与王p 3,若 ait b ≈O,则得到根x≈+b
( ) [ , ] [ , ] ( ) ( ) 0 ( ) 0, ( ) 0 f x a b a b f a f b f a f b 设 在 上连续且 有且仅有一个根又 。则可用对分法： 不妨设 , . 2 2 0 2 , 2 0 2 1 , 1 1 1 a1 a a b b b b a b a a b f a b x a b f = + = = + = + + = = + 令 ， 反之 ）若 输出根 否则：若 ， 2 ),对[ a1 ,b1 ]区间重复1）的计算，并产生 [a2 ,b2 ] , . 2 0 2 3), a b x a b f i i i + i + 若 ，则得到根 §1. 非线性方程实根的对分法(二分法)
二分法的收敛性 f( 二分法产生一个有根区间: ba1b]… la b b b an,bn区间长度 b, 2 (b, (b-a 当n足够大时,取近似值xn=22+bp, 误差:x-x b-a <E 计算简便,容易估计误差,但收敛较慢
二分法的收敛性 1 1 [ , ] [ , ] [ , ] n n a b a b a b 二分法产生一个有根区间： 1 1 [ , ] 1 1 ( ) ( ) 2 2 n n n n n n n b a a b b a b a − − − = − = = − 区间长度： 当 足够大时，取近似值 ， 2 a b x n n n n + = 1 2 n n b a x x + − 误差： − 计算简便，容易估计误差，但收敛较慢。 a x * x0 b f x( ) a1 b1
§2.迭代法 改写方程:f(x)=0分x=(x)且q连续。 建立迭代格式: n+1 0(x),得到序列{x 则若{xn}收敛必收敛到f(x)=0的根: limxmt=lim(x )=l limx n→> 若{xn}收敛,即 limx=x,则 n x=q(x)→f(x)=0
§2. 迭代法 改写方程： f (x) = 0 x =(x)且 连续。 x x { x } n n n ( ) 建立迭代格式： +1 = ，得到序列 1 { } ( 0 ( ) lim lim lim n n n n n n n x f x x x x + → → → = = = 则 若 收敛必收敛到 ） 的根： * * * * { } ( ) ( ) 0 n n lim n x x x f x x x → = = = 若 收敛，即 ，则：
迭代过程的几何表示 x=q(x)分 ∫y=g(x) 交点即为真根 X=y y=x y=0( D
迭代过程的几何表示 y x = ( ) y x = O x* x2 x1 x0 x y P0 Q1 P1 P2 * P Q2 ( ) ( ) y x x x x y = = = 交点即为真根
例:求方程f(x)=x32-x-1=0在x0=1.5附近的根x 解:(1)将方程改写为x=x+1 由此建立迭代公式 k+1 1(k=0,1,2…) k 0 7 X11.51.357211.33086…1.324721.32472 迭代收敛 (2)若将方程改写为x=x3-1 建立迭代公式x1=x2-1 k 0 X,1.52.37512.39 迭代不收敛
3 * 0 3 3 1 k ( ) 1 0 1.5 . 1 1 1 ( 0,1,2 ) k 0 1 2 7 8 x 1.5 1.35721 1.33086 1.324 k k f x x x x x x x x x k + = − − = = = + = + = 例：求方程 在 附近的根 解：（ ） 将方程改写为 由此建立迭代公式 3 3 1 k 72 1.32472 2 1 1. k 0 1 2 x 1.5 2.375 12.39 k k x x x x + = − = − 迭代收敛。 （ ） 若将方程改写为 建立迭代公式 迭代不收敛
收敛充分性定理(一、1) 定理.设函数(x)在区间a,b上满足条件 (1)对任意x∈[a,b,都有a≤q(x)≤b (2)存在常数0<L<1,使得对一切x,y∈[a,b,都有 (x)-9(y)≤L|x-y 则方程x=q(x)在[a,b有唯一的根x,且对任何 初值x∈[a,b]迭代序列 n+1 qp(xn)(n=0,1, 均收敛于x,并有 D 1-L
* 1 * . ( ) [ , ] 1 [ , ] ( ) ; (2) 0 1, , [ , ], ( ) ( ) ( ) [ , ] , [ , ], ( ) ( 0,1, ) n n x a b x a b a x b L x y a b x y L x y x x a b x a b x x n x + − − = = = 0 定理 设函数 在区间 上满足条件 （ ）对任意 ，都有 存在常数 使得对一切 都有 则方程 在 内有唯一的根 且对任何 初值x 迭代序列 均收敛于 ，并有 * 1 0 x 1 n n L x x x L − − − 收敛充分性定理(一、1)
收敛充分性定理(-、2) 证:由条件(2)知(x)在[a,b上连续。 令y(x)=x-q(x),则v(x)在[a,b上连续,且 y(a)=a-q(a)≤0,v(b)=b-q(b)≥0 故存在∈[a,b,使得v()=0,即2=(2) 所以方程x=q(x)在[,b]有根 假设方程x=q(x)在a,b内有两个根x1≠x2, 由条件(2),有 x一=0(x)-9()≤L-x<-x 导出矛盾,唯一性得证
2 ( ) [ , ] ( ) ( ), ( ) [ , ] ( ) ( ) 0, ( ) ( ) 0 [ , ] 0, ( ) [ , ] x a b x x x x a b a a a b b b a b x x a b = − = − = − = = = 证：由条件（ ）知 在 上连续。 令 则 在 上连续，且 故存在 ，使得 （ ） 即 （ ）, 所以方程 在 内有根。 * * 1 2 * * * * * * * * 1 2 1 2 1 2 1 2 ( ) [ , ] , 2 ( ) ( ) x x a b x x x x x x L x x x x = − = − − − 假设方程 在 内有两个根 由条件（ ），有 导出矛盾，唯一性得证。 收敛充分性定理(一、2)
收敛充分性定理(一、3) 对任意x∈[a,b]迭代公式有 xX q(xn-1)-9(x)≤L x 依此类推,得xnxs|x-x 因0 即对任意初值xo∈[a,b,迭代序列{xn}均收 敛到方程的根x 类似地,对任意正整数k,有 lxk+ -xk=o(xk)-(xk-sLIxk k <L
0 * * * 1 1 * * 0 * 0 * 1 1 1 1 [ , ], ( ) ( ) 0< 1, lim x [ , ], ( ) ( ) n n n n n n n n k k k k k k k x a b x x x x L x x x x L x x L x x a b x x k x x x x L x x L x − − → + − − − = − − − − = − = − − − 对任意 由迭代公式有 依此类推，得 因 所以 即对任意初值 迭代序列 均收 敛到方程的根 。 类似地，对任意正整数 ,有 0 x 收敛充分性定理(一、3)
收敛充分性定理(一、4) 于是,对任意正整数n,p,有 n+p n+p n+p-1 n+p-1 n+p In+1-X L"|x1-x+L"n1x1-x0+…+L"x:-x L(+L+…+1)x1-x - LLLx-xol 令p→∞,得 x2-xd≤ 1-L
1 1 2 1 1 2 1 0 1 0 1 0 1 2 1 0 1 0 * 1 0 , , ( 1) 1 1 , 1 n p n n p n p n p n p n n n p n p n n p p p n n n n p L p L x L x x x x x x x x L L L x x x x x x L L L x x L L x x x x x + + + − + − + − + + − + − − − − − + − + + − − + − + + − = + + + − − = − − → − − − 于是，对任意正整数 有 令 得 收敛充分性定理(一、4)