第七章方程求根 求解非线性方程 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)