《计算方法》第二章 迭代法

第二节迭代法 迭代原理 迭代方法是依靠收敛的迭代序列来求 方程根的近似值。 ●简单迭代法的基本思想 将方程f(x)=0化为等价方程x=0(x) 然后在隔根区间内取一点x,按下式计算 (k=0,1,2,…) 计算结果生成数列 2啊1 如果这个数列有极限Mmk,显然 k→x 就是方程x=q(x)的根。于是可以从此数列 中求得满足精度要求的近似根。 ●相关定义 迭代法:上述求方程的根的方法 迭代格式: k+1=9(x k (k=0,1,2…)

第二节 迭代法 一、 迭代原理 迭代方法是依靠收敛的迭代序列来求 方程根的近似值。 ⚫ 简单迭代法的基本思想 将方程 f x( ) 0= 化为等价方程 x x =( ) ， 然后在隔根区间内取一点 0 x ，按下式计算 1 ( ) k k x x  + = （ k =0,1,2, ） 计算结果生成数列 0 1 , , , ,k x x x 如果这个数列有极限 * lim x x k k = → ，显然 x * 就是方程 x x =( ) 的根。于是可以从此数列 中求得满足精度要求的近似根。 ⚫ 相关定义 迭代法： 上述求方程的根的方法. 迭代格式： ( ) ( 0,1,2, ) 1 x x k k k = =  +

迭代函数:(x) 迭代初始值:x 迭代序列: kk=0 若序列{x kk=0 收敛,则称迭代格式收 敛;否则,称迭代格式x, k+1k)是发散 的。 ●简单迭代法的步骤 1.将f(x)=0分x=m(x),其中m(x)不唯一, 但总能找到。 2.设f(x)∈C[a,b],且f(a)f(b)<0,即[a,b 是隔根区间, 在[b内取一点x,按下式计算 k+1=0(xk)(k=012…) (*1 可得一个序列x 若序列 k/k=0 是收 kk=0 敛的,即:

迭代函数： ( )x . 迭代初始值： 0 x . 迭代序列： 0 x k k            = . 若序列 0 x k k            = 收敛，则称迭代格式收 敛；否则，称迭代格式 ( ) 1 x x k k = + 是发散 的。 ⚫ 简单迭代法的步骤 1.将 f x( ) 0=  x x =( ) ，其中 ( )x 不唯一， 但总能找到。 2.设 f x C a b ( ) [ , ]  ，且 f a f b ( ) ( ) 0   ，即 [ , ] a b 是隔根区间， 在 [ , ] a b 内取一点 0 x ，按下式计算： ( ) ( 0,1,2, ) 1 x x k k k = =  + (*1) 可得一个序列 0 x k k            = ，若序列 0 x k k            = 是收 敛的，即：

lm X k 对(*1)式两边取极限得 k-。k+1k20k k->ook+1-,lim k/-p(r) Im 即:x*为方程x=0(x)的根,也就是 f(x)=0的根。 例1.用迭代法求方程x4+2x2-x-3=0在 [1.2]内的实根。取xn=1 (精确解为x*=1.124123029)。 解:对方程进行如下三种变形: ①、x=q(x)=x4+2x2-3, 建立迭代格式: x1=q2(x)=x(+2x2-3,(n=0,,) 可得:x=96x=8495307×107,显然这 是一个发散的迭代格式

* lim x x k k = → 对（*1）式两边取极限得： ( ) lim lim 1 x x k k k k =  → → +  * * ( ) ( ) lim lim 1 x x x x k k k k = = =   → → + 即： x * 为方程 x x =( ) 的根，也就是 f x( ) 0= 的根。 例 1．用迭代法求方程 x x x 4 2 + − − = 2 3 0 在 [1,1.2] 内的实根。取 0 x =1 。 （精确解为 x * =1.124123029 ）。 解：对方程进行如下三种变形： ①、 4 2 1 x x x x = = + −  ( ) 2 3 ， 建立迭代格式： 4 2 1 1( ) 2 3, ( 0,1, ) n n n n x x x x n  + = = + − = 可得： 3 4 x x = =  96, 8.495307 107 ，显然这 是一个发散的迭代格式

②、x=9(x)=(3+x-2x)y 建立迭代格式: x1=q2(x)=(3+xn-2x2),(n=0,1,…) 可得:x=x,=1.124123,迭代格式 是收敛的。 ⑧、x=(x)=√x+4-1 建立迭代格式 n+1 g(x)=x+4-1,(m=0…) 可得:x=x=1.124123,迭代格式是收 敛的。 从上例可看出,对f(x)=0的迭代函数不 唯一,建立的迭代格式有的发散有的收敛, 有的收敛的快,有的收敛的慢 这正是下面所要讨论的两个问题:收敛 性问题和收敛速度问题。 收敛条件与误差估计 ●收敛条件

②、 1 2 4 2 x x x x = = + −  ( ) (3 2 ) ， 建立迭代格式： 1 2 4 1 2( ) (3 2 ) , ( 0,1, ) n n n n x x x x n  + = = + − = 可得： 26 27 x x = =1.124123 ，迭代格式 是收敛的。 ③、 3 x x x = = + −  ( ) 4 1 ， 建立迭代格式： 1 3( ) 4 1, ( 0,1, ) n n n x x x n  + = = + − = 可得： 6 7 x x = =1.124123 ，迭代格式是收 敛的。 从上例可看出，对 f x( ) 0= 的迭代函数不 唯一，建立的迭代格式有的发散有的收敛， 有的收敛的快，有的收敛的慢。 这正是下面所要讨论的两个问题：收敛 性问题和收敛速度问题。 二、收敛条件与误差估计 ⚫ 收敛条件

定理1设o(x)在有限区间[ab上存在,且 满足如下条件: (1)当x∈a,b时,(x)∈b], 即a≤q(x)≤b (*2) (2)存在正常数L<1,使得对∨x∈[a,b, (x)k≤L<1 (*3) 则:①在[ab上的解x存在且唯一; ②对任选的初始近似x∈[ab,由迭代 过程x+1=0(x(=012)产生的序列 {x2收敛到x 证明:①存在唯一性 由(*3)知,0(x)在[a,b]上连续, 令g(x)=x-m(x),则g(x)在[a,b]上连续。 由(*2)知:g(a)=a-m(a)≤0, g(b)=b-(b) 则方程g(x)=0在[ab上至少有一个根x*

定理 1 设 '( )x 在有限区间 [ , ] a b 上存在，且 满足如下条件： （1）当 x a b x a b   [ , ] ( ) [ , ] 时， ， 即 a x b   ( ) . (*2) （2）存在正常数 L1 ，使得对  x a b [ , ] ， | '( )| 1  x L  (*3) 则：①在 [ , ] a b 上的解 x * 存在且唯一； ②对任选的初始近似 0 x a b [ , ] ，由迭代 过 程 ( ),( 0,1,2, ) 1 x x k k k = =  + 产生的序列 { } x k 收敛到 x * 。 证明：①存在唯一性 由（*3）知， ( ) [ , ] x a b 在 上连续， 令 g x x x ( ) ( ), = − 则 g x a b ( ) [ , ] 在 上连续。 由（*2）知： g a a a ( ) ( ) 0, = −   g b b b ( ) ( ) 0, = −   则方程 g x( ) = 0 在 [ , ] a b 上至少有一个根 x *

设g(x)=x-0(x)在[a,b上有两个根 a≠a,即:a1=0(a),a2=0(a2),则有 a-a Hp(a)-ploHoSla-aslas-a 其中L<1, 只有当a=a时,不等式才成立。 故:&≡C,=x ②收敛性 任取x∈[ab,由微分中值定理,有 Ix xEo(-(x kllxxlo((x) ≤L2|x2-xk…≤|x-x 0<L<1, n!xn-x2)=0,即12x 推论若条件(*3)改为存在正常数L<1, 对x,x,∈[a6,不等式 (x)-9(x)Lx2-x

设 g x x x ( ) ( ), = − 在 [ , ] a b 上有两个根   1 2  ，即： 1 1    = ( ), 2 2    = ( ), 则有 ' 2 1 2 1 2 1 2 1 | | | ( ) ( )| | ( )|| | | |             − = − = −  − L 其中 L1 ， 只有当   1 2 = 时，不等式才成立。 故： 1 2   =x * 。 ②收敛性 任取 0 x a b [ , ] ，由微分中值定理，有 1 1 2 | | | ( ) ( )| | | | ( ) ( )| * * * * n n n n x x x x L x x L x x     − − − − = −  − = − 2 0 2 * * | | | |, n L x x L x x n −  −   − 0 1  L ，  lim ( ) 0 x x * n n − = → ，即 lim x x * n n = → 。 推论 若条件（*3）改为存在正常数 L1 ， 对 1 2   x x a b , [ , ] ，不等式 2 1 2 1 | ( ) ( )| | |   x x L x x −  −

恒成立,则定理1中的结论成立。 我们称满足定理1条件的q为从 ab→a,b]的压缩映射,称定理中的常数L 为 Lipschitz常数 定理2设x*是x=0(x)的一个根,(x)在x 的某个邻域U={xxxk}内(x)存在, 且存在正常数L<1,使 p(x)L<1,Vx∈U (米4) 则任取x∈U,迭代格式x1=0(x)均收敛于 x,并且有下列估计式成立。 k1-Lk k-1 (*5) k x-x 反之,若(x)1,则迭代格式x1=0(x)发

恒成立,则定理 1 中的结论成立。 我们称满足定理 1 条件的  为 从 a b a b , ,             → 的压缩映射，称定理中的常数 L 为 Lipschitz 常数。 定理 2 设 x * 是 x x =( ) 的一个根， ( )x 在 x * 的某个邻域 U x x x = −  { | | } *  内 '( )x 存在， 且存在正常数 L1 ，使 | ( )| 1  x L  ，  x U （*4） 则任取 0 x U ，迭代格式 1 ( ) k k x x  + = 均收敛于 x * ，并且有下列估计式成立。 * 1 1 * 1 1 0 L x x x x k k k L Lk x x x x k L −  − − − −  − − （*5） 反之，若 | ( )| 1  x  ，则迭代格式 ( ) 1 x x k k = + 发

散。 证明:首先证明条件式(*4)成立时迭代格 式的收敛性。 显然,在x的邻域U内定理1的条件 (2)成立,在根据微分中值定理和条件式 (*4),任取x∈U,有 x-0(x)=0(x)-0(x)=0(2)x-x) ≤Lx-x<x-xk<6 故q(x)∈U,即定理1的条件(1)也成立。 由定理1,当x0eU时,迭代格式x+1=0(x) 收敛于x 下面证明证明条件式(*4)成立时误差 估计式(*5)成立。 当x∈U时,因为 x-x,≤Lx ≤L(x-x2+ kkk

散。 证明：首先证明条件式（*4）成立时迭代格 式的收敛性。 显然，在 x * 的邻域 U 内定理 1 的条件 （2）成立，在根据微分中值定理和条件式 （*4），任取 x U ，有 * * * ( ) ( ) ( ) '( )( ) * * x x x x x x L x x x x       − = − = −  −  −  故 ( )x U ，即定理 1 的条件（1）也成立。 由定理 1，当 0 x U 时，迭代格式 ( ) 1 x x k k = + 收敛于 x * 。 下面证明证明条件式（*4）成立时误差 估计式（*5）成立。 当 0 x U 时，因为 * * * ( ) 1 1 x x L x x L x x x x k k k k k −  −  − + − − −

故 x-x k-1-Llkk 类似的, kk-1 P(x, 1-p k-2 0(2(x ≤L k-1 k-1“k-2 上两式联立即得误差估计式(*5) k 下证|(x)1时,迭代格式x1=以(x)发散。 k+1 由于 x=x (x)-( k(5)(x-x x-X k+1 所以迭代过程发散。 全局收敛性:对于任意给定x,迭代格式均 收敛,则称此格式具有全局收敛性。 局部收敛性:若存在根x*的邻域 U(x,)=x-,x+4使对vx∈U(x,:),迭

故 * 1 1 L x x x x k k k L −  − − − 。 类似的， ( ) ( ) '( )( ) 1 1 2 1 2 1 1 2 1 0 x x x x x x k k k k k k L x x L x x k k k − = − = −     − − − − −  −   − − − − 上两式联立即得误差估计式（*5）。 * 1 1 0 Lk x x x x k L −  − − 下证 | ( )| 1  x  时，迭代格式 ( ) 1 x x k = + 发散。 由于 * * * * ( ) ( ) '( )( ) 1 x x x x x x x x k k k k − = − = −  −     + 所以迭代过程发散。 全局收敛性：对于任意给定 0 x ，迭代格式均 收敛，则称此格式具有全局收敛性。 局部收敛性：若存在根 x * 的邻域 U x x x ( , ) [ , ] * * *    = − + 使对 ( , ) * 0   x U x  ，迭

代法均收敛,则称此迭代法局部收敛. 如定理2所提到的迭代法收敛性属于局部 收敛,因为只有当x。选得充分接近x时, 迭代序列才保证收敛。 收敛速度:由(*5)x-x1≤ k k1-L1“0 可见, L值愈小,迭代法收敛得愈快。 若L<1,则收敛快;L接近于1,则收敛很 慢 例2.求9x2-sinx-1=0在[0,1内的一个实 根. 解:9x2-sinx-1=0→x=(x)=Smx+, 0≤(x)≤1,此时定理1中的条件 (*2)成立

代法均收敛，则称此迭代法局部收敛. 如定理 2 所提到的迭代法收敛性属于局部 收敛，因为只有当 0 x 选得充分接近 x * 时， 迭代序列才保证收敛。 收敛速度：由（*5） * 1 1 0 Lk x x x x k L −  − − 可见， L 值愈小，迭代法收敛得愈快。 若 L1 ，则收敛快； L 接近于 1，则收敛很 慢。 例 2.求 9 sin 1 0 x x 2− − = 在[0，1]内的一个实 根. 解： 9 sin 1 0 x x 2− − =  sin 1 ( ) , 3 x x x  + = = 0 ( ) 1    x ，此时定理 1 中的条件 （*2）成立