《数值计算方法》第七章 方程求根

第七章方程求根 求解非线性方程 f(x)=0 f是非线性函数, 例:代数方程 f(x)=anx tax ++ax +a=o, n>lo 例超越方程 f( x=o+sinx=0 e

第七章 方程求根 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 atb =0输出根x=xb a+b D,若f ,否则:若 <0 2’b=b反之h,a+b atb 令a 5)P区国重道D即斗其王[P 3若+b|=0,则得到根x=+b 2 2

( ) [ , ] [ , ] ( ) ( ) 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(x) 二分法产生一个有根区间: ab]a1blb…lanb, a b b la,b,区间长度: b-a 2 (6m--a (b-a) 当n足够大时,取近似值斯<2+b 误差:1x-x b-a 2 n+1 <8 计算简便,容易估计误差,但收敛较慢

二分法的收敛性 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=q(x)且φ连续 建立迭代格式:xn1=(x),得到序列{xn 则若{}收敛必收敛到f(x=0的根: limxmI-lim(x )=l limx 若{x}收敛,即 limx=x,则: x=(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  →  = =  = 若 收敛，即 ，则：

迭代过程的几何表示 y=(x) x=(x)今 交点即为真根 X=y y=x y=(x)

迭代过程的几何表示 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)=x3-x-1=0在x=1.5附近的根x 解:(1)将方程改写为x=√x+1 由此建立迭代公式 k+1 k+1(=0,1,2…) k 0 7 1.51.357211.3086…1.324721.32472 迭代收敛。 2)若将方程改写为x=x3-1 建立迭代公式 k+1 k o k 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) 定理.设函数q(x)在区间a,b上满足条件 (1)对任意x∈[a,b,都有a≤p(x)≤b; (2)存在常数0<L<1,使得对一切x,y∈[a,b],都有 (x)-9(y)≤Lx-y 则方程x=q(x)在a,b内有唯一的根x,且对任何 初值x。∈[a,b]迭代序列 n+1 qp(xn)(n=0,1,) 均收敛于x,并有 X 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)知9(x)在[a,b上连续 令y(x)=x-q(x),则v(x)在[a,b上连续,且 y(a)=a-(a)≤0,v(b)=b-q(b)≥0 故存在∈[a,b,使得v(5)=0,即ξ=(5), 所以方程x=q(x)在[a,b]有根。 假设方程x=q(x)在a,b内有两个根x≠ 由条件(2),有 x-x1=0(x)-9(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]由迭代公式有 xnx=o(xn-D-()sL xX 依此类推,得 x"|≤n 因00 即对任意初值xo∈[a,b迭代序列{xn}均收 效到方程的根x 类似地,对任意正整数k,有 lxk+lxk=lo(xk)-(xk-sLIxk-xk-I <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     − − →  + − −  − = −  − −  −  =  − = −  −   − 对任意 由迭代公式有 依此类推，得 因 所以 即对任意初值 迭代序列 均收 敛到方程的根 。 类似地，对任意正整数 ,有 x0 收敛充分性定理(一、3)

收敛充分性定理(一、4) 于是,对任意正整数n,p,有 ntp Xns ntp n+p- n+D-1 n+p-2 n+1 Inl L"nx:-xc+”1x1-x+…+L"x =L"(L"+L P2+…+1)x1X0 0 P→∞,得 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)