计算方法 第2章 一元线性方程的解法

1、第2章 一元线性方程的解发 计算方法 第2章 一元非线性方程的解法 1 二分法二分法 2 迭代法迭代法 3 切线法切线法(牛顿法牛顿法) 4 弦截法弦截法 5 加速迭代法加速迭代法 第2章 一元线性方程的解发 计算方法 y a+1 a -50 O 50 x 50,50 2 )( x eea y a x a x 第2章 一元线性方程的解发 计算方法 记笔记记笔记 由题设知曲线的最底点由题设知曲线的最底点(0,y(0)(0,y(0)与最高点与最高点 (50,y(50)(50,y(50)之间的高度差为之间的高度差为1m,1m,所以应有所以应有 y(50)=y(0)+1,y(50)=y(0)+1,即即

2、 1 2 )( 5050 a eea a x a y a+1 a -50 O 50 x 要计算电缆的长度要计算电缆的长度, ,必须必须 先求出上述方程中先求出上述方程中 的的a ,a ,由于它是关于由于它是关于a a的非线性方程的非线性方程, ,没有现成的公没有现成的公 式可用式可用,因此只能寻求其他解法因此只能寻求其他解法. . 第2章 一元线性方程的解发 计算方法 在实际应用中有许多非线性方程的例子，例如 求求f(xf(x)=0)=0的根的根 （1）在光的衍射理论（the theory of diffraction of light)中,我们 需要求x-tanx=0的根 （2）在行星轨道（

3、 planetary orbits）的计算中,对任意的a和b， 我们需要求x-asinx=b的根 （3）在数学中，需要求n次多项式xn + a1 xn-1+.+an-1 x + an 0 的根 第2章 一元线性方程的解发 计算方法 满足方程的满足方程的x值通常叫做值通常叫做方程的根或解方程的根或解， 也叫函数也叫函数f( (x)=0)=0的零点。的零点。 非线性方程的一般形式：非线性方程的一般形式：f(x)=0 这里这里f( (x) )是单变量是单变量x 的函数。的函数。 u 代数多项式：代数多项式： f( (x)=)=a0+a1x+anxn (an0) cos0 3 x x e 非线性方程可

4、分为两种：非线性方程可分为两种： u 超越函数超越函数，即不能表示为上述形式的函数。，即不能表示为上述形式的函数。 第2章 一元线性方程的解发 计算方法 l 远在公元前远在公元前1700年的古巴比伦人就已有关于一、二次方程的年的古巴比伦人就已有关于一、二次方程的 解法。解法。 l 1535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)发现了三次方程发现了三次方程 的解法，卡当的解法，卡当(HCardano)从他那里得到了这种解法，于从他那里得到了这种解法，于 1545年在其名著年在其名著大法大法中公布了三次方程的公式解，称为中公布了三次方程的公式解，称为 卡当算法。卡当

5、算法。 l 后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。又提出了四次方程的解法。 第2章 一元线性方程的解发 计算方法 l 1799年，高斯证明了代数方程必有一个实根或复根的定理，年，高斯证明了代数方程必有一个实根或复根的定理， 称此为代数基本定理，并由此可以立刻推理称此为代数基本定理，并由此可以立刻推理n次代数方程必次代数方程必 有有n个实根或复根。个实根或复根。 l 但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其中的奥妙开始意识到有潜藏其中的奥妙, 用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。 l 在继续探

6、索在继续探索5次以上方程解的艰难历程中，第一个重大突破次以上方程解的艰难历程中，第一个重大突破 的是挪威数学家阿贝尔的是挪威数学家阿贝尔(NAbel1802-1829) 1824年阿贝尔发年阿贝尔发 表了表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的论文，但并未受的论文，但并未受 到重视，连数学大师高斯也未理解这项成果的重要意义。到重视，连数学大师高斯也未理解这项成果的重要意义。 第2章 一元线性方程的解发 计算方法 l 十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)整理并发表了整理并发表了 伽罗华的遗作，人们才意识到这项近代数学发展史上的重伽罗华

7、的遗作，人们才意识到这项近代数学发展史上的重 要成果的宝贵。要成果的宝贵。 l 38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在专著在专著 论置换与代数方程论置换与代数方程中阐发了伽罗华的思想，一门现代中阐发了伽罗华的思想，一门现代 数学的分支数学的分支群论诞生了。群论诞生了。 l 在前几个世纪中，曾开发出一些求解代数方程的有效算法，在前几个世纪中，曾开发出一些求解代数方程的有效算法， 它们构成了数值分析中的古典算法。至于超越方程则不存它们构成了数值分析中的古典算法。至于超越方程则不存 在一般的求根方式。在一般的求根方式。 第2章 一元线性方程的解发 计算方

8、法 方程根的数值计算步骤方程根的数值计算步骤 u判断根的存在判断根的存在 u确定根的分布范围确定根的分布范围 u根的精确化根的精确化 第2章 一元线性方程的解发 计算方法 根的存在定理根的存在定理( (零点定理零点定理) )： f(x)为为 a,b 上的连续函数，若上的连续函数，若 f(a)f(b)0 0，则，则 a,b 中至少有一个实根。如果中至少有一个实根。如果f(x)在在 a,b 上还是单上还是单 调递增或递减的，则调递增或递减的，则f(x)=0 0仅有一个实根。仅有一个实根。 第2章 一元线性方程的解发 计算方法 根的分布范围根的分布范围: : 在用近似方法时，需要知道方程的根所在区间

9、。在用近似方法时，需要知道方程的根所在区间。 若区间若区间 a,b 含有方程含有方程f(x)=0 0的根，则称的根，则称 a,b 为为f(x)=0 的的有根区间有根区间；若区间若区间 a,b 仅含方程仅含方程f(x)= 0 0的一个根，的一个根， 则称则称 a,b 为为f(x)= 0的一个的一个隔根区间。隔根区间。求隔根区间有求隔根区间有 两种方法：两种方法： 第2章 一元线性方程的解发 计算方法 例如，求方程例如，求方程3 3x-1-1-cosx=0 0的隔根区间。的隔根区间。 将方程等价变形为将方程等价变形为3 3x-1=-1=cosx ，易见，易见y=3 3x-1-1与与 y=cosx的

10、图像只有一个交点位于的图像只有一个交点位于0.50.5，11内内。 画出画出y= =f( (x) )的略图，从而看出曲线与的略图，从而看出曲线与x轴交点轴交点 的大致位置。也可将的大致位置。也可将f( (x)=0)=0等价变形为等价变形为g1 1( (x)=)=g2 2( (x) ) 的形式，的形式，y= =g1 1( (x) )与与y= =g2 2( (x) )两曲线交点的横坐标所两曲线交点的横坐标所 在的子区间即为含根区间。在的子区间即为含根区间。 (1)描图法描图法 第2章 一元线性方程的解发 计算方法 (2)逐步搜索法逐步搜索法 运用零点定理可以得到如下逐步搜索法：运用零点定理可以得到

11、如下逐步搜索法： 先确定方程先确定方程f( (x)=0)=0的所有实根所在的区间的所有实根所在的区间 为为 a, ,b,从从x0 0= =a 出发出发, ,以步长以步长 h=( (b-a) )/n 其中其中n是正整数，在是正整数，在 a, ,b 内取定节点：内取定节点： xi=x0 0ih ( (i=0,1,2=0,1,2，n) ) 计算计算f( (xi) )的值的值, ,依据函数值异号及实根的个数确依据函数值异号及实根的个数确 定隔根区间定隔根区间, ,通过调整步长，总可找到所有隔根通过调整步长，总可找到所有隔根 区间。区间。 第2章 一元线性方程的解发 计算方法 例例1 1 方程方程f(x

12、f(x)=x)=x3 3-x-1=0 -x-1=0 确定其有根区间确定其有根区间 解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0 x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下 x x f(xf(x) ) 0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + + 可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根内必有一根 第2章 一元线性方程的解发 计算方法 1二分法二分法 设函数设函

13、数f(x)在区间在区间a,b上单调连续上单调连续,且且 f(a)f(b)0 则方程在区间则方程在区间(a,b)内有且仅有一个实根内有且仅有一个实根x。 下面在有根区间下面在有根区间(a,b)内介绍二分法的基本思想。内介绍二分法的基本思想。 第2章 一元线性方程的解发 计算方法 x0= (a+b) 2 若若: f(a)f(x0)0 则，令则，令 a1=a，b1=x0 否则，令否则，令 a1=x0，b1=b 第2章 一元线性方程的解发 计算方法 如此逐次往复下去,便得到一系列有根区间 (a,b),(a1,b1),(a2,b2),(ak,bk), 其中 11 1 () 2 1 () 2 kkkk k

14、k k baba baba 这里a0=a, b0=b显然有 当k时,区间(ak,bk)最终必收敛于一点,该点就 是所求方程的根x。 第2章 一元线性方程的解发 计算方法 a b x0 x1 a b 什么时候停止？ x* k xx 第2章 一元线性方程的解发 计算方法 误差误差 分析：分析： 第第1步产生的步产生的 0 2 a b x 有误差有误差 0 2 b a |x x | 第第 k 步产生的步产生的 xk 有误差有误差 1 22 kk k k baba | xx| 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ： 1 lnln 1 2ln 2 k ba

15、ba k 第2章 一元线性方程的解发 计算方法 计算步骤 ： 输入有根区间的端点a、b及预先给定的精度; (a+b)/2 x; 若f(a)f(x)0，则x b，转向;否则x a，转向。 若b-a,则输出方程满足精度的根x，结束；否则转向。 二分法具有简单和易操作的优点。 第2章 一元线性方程的解发 计算方法 第2章 一元线性方程的解发 计算方法 例1 求方程 f(x)=x3-x-1=0 在区间(1,1.5)内的根。要求用四位小数计算,精确到 10-2。 解： 这里 a=1，b=1.5 取区间(1，1.5)的中点 0 1 (1 1.5)1.25 2 x 第2章 一元线性方程的解发 计算方法 由于

16、f（1）0，f（1.5）0 f(1.25)0,则令 a1=1.25, b1=1.5 得到新的有根区间(1.25,1.5) 第2章 一元线性方程的解发 计算方法 2 迭代法迭代法 迭代法的基本思想是: 首先将方程f(x)改写成某种等价形式，由等价形式构造 相应的迭代公式，然后选取方程的某个初始近似根x0， 代入迭代公式反复校正根的近似值，直到满足精度要 求为止。迭代法是一种数值计算中重要的逐次逼近方 法。 f (x) = x- g (x) =0 x = g (x) 等价变换等价变换 f (x) 的根的根g (x) 的不动点的不动点 第2章 一元线性方程的解发 计算方法 例：求方程 x3-x-1=

17、0 在x=1.5附近的一个根(用六位有效数字计算)。 第2章 一元线性方程的解发 计算方法 首先将原方程改写成等价形式 3 1xx 用初始近似根 x0=1.5 代入上式的右端可得 3 0 11.35721xx 3 21 10,1,2,xxk 第2章 一元线性方程的解发 计算方法 第2章 一元线性方程的解发 计算方法 虽然迭代法的基本思想很简单，但效果并不总是令人 满意的。对于上例，若按方程写成另一种等价形式 x=x3-1 建立迭代公式 xk+1=x3k-1, k=0,1,2, 仍取初始值x0=1.5, 则迭代结果为 x1=2.375 x2=12.3976 第2章 一元线性方程的解发 计算方法

18、几何意义几何意义: ( )yxyg x和的交点 x = g (x) 第2章 一元线性方程的解发 计算方法 x y y = x x y y = x x y y = x x y y = x x*x* x*x* y=g(x) y=g(x) y=g(x) y=(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 第2章 一元线性方程的解发 计算方法 同样的方程同样的方程 不同的迭代格式不同的迭代格式 有不同的结果有不同的结果 什么形式的迭代什么形式的迭代 法能够收敛呢法能够收敛呢? ? 如何构造迭代函如何构造迭代函 数呢数呢? ? 第2章 一元线性方程

19、的解发 计算方法 若从任何可取的初值出发都能保证收敛，则称它若从任何可取的初值出发都能保证收敛，则称它 为为大范围收敛大范围收敛。如若为了保证收敛性必须选取初值充。如若为了保证收敛性必须选取初值充 分接近于所要求的根，则称它为分接近于所要求的根，则称它为局部收敛局部收敛。 通常局部收敛方法比大范围收敛方法收敛得快。通常局部收敛方法比大范围收敛方法收敛得快。 因此，一个合理的算法是先用一种大范围收敛方法求因此，一个合理的算法是先用一种大范围收敛方法求 得接近于根的近似值（如对分法），再以其作为新的得接近于根的近似值（如对分法），再以其作为新的 初值使用局部收敛法（如迭代法）。初值使用局部收敛法（

20、如迭代法）。 这里讨论迭代法的收敛性时，均指的是局部收敛这里讨论迭代法的收敛性时，均指的是局部收敛 性。性。 第2章 一元线性方程的解发 计算方法 1212 ()()g xg xq xx 1. 则方程在则方程在(a,b)内有唯一的根；内有唯一的根； 110 11 k kkk qq xxxxxx qq 定理定理/收敛定理收敛定理/压缩映像原理压缩映像原理 l 设方程设方程x=g(x)在在(a,b)内有根内有根x* l g(x)满足李普希茨满足李普希茨(Lipschitz)条件条件:即对即对(a,b)内任意的内任意的x1 和和x2都有：都有： q为某个确定的正数，为某个确定的正数，q1 条件条件

21、结果结果 3. 还有误差估计式还有误差估计式 2. 且迭代公式且迭代公式 xk+1=g(xk) 对对任意任意初始近似值初始近似值x0均收敛于均收敛于 方程的根方程的根x； 第2章 一元线性方程的解发 计算方法 由已知条件知，由已知条件知，x*为方程为方程x=g(x)的根，即的根，即x*=g(x*) () () xg x yg y 设设 也是方程的根，即也是方程的根，即xy 于是，由李普希茨条件得于是，由李普希茨条件得 ()()xyg xg yq xy 因为因为q1，所以上式矛盾，故必有，所以上式矛盾，故必有 xy 证 1. 有唯一根 第2章 一元线性方程的解发 计算方法 考虑迭代公式 x k+

22、1=g(xk) , k=0,1,2, 由李普希茨条件 1 0 ()() kk k xxg xg x q xx 证 2. 迭代公式收敛 因为q1，当k时，qk0，即有 1 0 k xx lim k k xx 所以 第2章 一元线性方程的解发 计算方法 证 3. 误差 |xk-x*|= |xk-xk-1| = |g(xk-1)-g(xk-2)| |xk-x*| q/(1- q)|xk-xk-1| |xk-x*| qk/(1- q) |x1-x0| 可用可用 来来 控制收敛精度控制收敛精度 | 1kk xx 1212 ()()g xg xq xx 李普希茨李普希茨(Lipschitz)条件条件 |g

23、(xk-1)-g(x*)| q |xk-1-x*| q (|xk-xk-1|+|xk-x*|) q |x k-1-xk-2| qk-1|x1-x0| 第2章 一元线性方程的解发 计算方法 要验证要验证g(x)是否满足李氏条件一般比较困难，若是否满足李氏条件一般比较困难，若g(x)可可 微，可用条件微，可用条件 来判断迭代公式是否收敛。来判断迭代公式是否收敛。 ( )1g xq 必须说明两点必须说明两点: 对于收敛的迭代过程，误差估计式说明迭代值的偏 差xk-xk-1相当小，就能保证迭代误差x-xk足够 小。因此在具体计算时常常用条件 xk-xk-1 来控制迭代过程结束。 第2章 一元线性方程的

24、解发 计算方法 例例 求方程 x=e-x 在x=0.5附近的一个根。按五位小数计算,计算结果 的精度要求为=10-3。 ()0.61 x e 解 过x=0.5以步长h=0.1计算 f(x)=x-e-x 由于 f(0.5)0，f(0.6)0 故所求的根在区间(0.5,0.6)内,且在x=0.5附近 第2章 一元线性方程的解发 计算方法 10 xx 10 xx 01 ()g xx 开始开始 结束结束 0, x输入输入 1 x输出输出 F T 第2章 一元线性方程的解发 计算方法 g(x)=e-x 第2章 一元线性方程的解发 计算方法 因此用迭代公式 由表可见 1 k x k xe 10 x xx

25、xe 为方程 的根 第2章 一元线性方程的解发 计算方法 最一般的形式可以写成 x=x+(x)f(x) 这里(x)为任意一个正(或负)的函数。于是 g(x)=x+(x)f(x) 这样只要合理选取(x),使得迭代公式满足收敛条件 ( )1g xq 如何构造迭代函数如何构造迭代函数g(x)呢呢? ? 第2章 一元线性方程的解发 计算方法 切线迭代公式：切线迭代公式： 1 1 ( ),1,2, ( )() k k xx a xk f xf x 弦截迭代公式：弦截迭代公式： 1 ( ) ( ) a x fx 第2章 一元线性方程的解发 计算方法 设x * 是方程f (x ) = 0的根，又x0 为x

26、* 附近的一个 值 ，将f (x ) 在x0附近做泰勒展式 之间和在其中 0 2 0000 )()( 2 1 )()()()( xx fxxxfxxxfxf * xx )()( 2 1 )()()()(0 2 0 * 00 * 0 * fxxxfxxxfxf 3 切线法切线法(牛顿法牛顿法) 令 ，则 第2章 一元线性方程的解发 计算方法 去掉 的二次项，有： 0 * xx 0)()()( 000 * 0 xfxxfxxf * 0 0 0 () () f x xx fx 1 x 即 以x1代替x0重复以上的过程，继续下去得： 第2章 一元线性方程的解发 计算方法 ,.1 , 0 )( )( 1

27、 n xf xf xx n n nn 以此产生的序列以此产生的序列xn得到得到f(x)=0的近似解，称为的近似解，称为 Newton法，又叫切线法。法，又叫切线法。 第2章 一元线性方程的解发 计算方法 牛顿法的几何意义牛顿法的几何意义 x y x* x0 0 10 0 () () fx xx fx x 1 x 2 000 ()()()yf xfxxx 1 21 1 () () fx xx fx 牛顿法也称为切线法牛顿法也称为切线法 ,.1 , 0 )( )( 1 n xf xf xx n n nn ( )f x 第2章 一元线性方程的解发 计算方法 Newton迭代的方程为：迭代的方程为：

28、)( )( )(0)( xf xf xxxxf 所以所以 2)( )( )( ) )( )( ()( xf xfxf xf xf xx 若若f(x)在在x*处为单根，则处为单根，则( *)0,( *)0,( *)0f xfxx 所以，迭代格式收敛。所以，迭代格式收敛。 Newton迭代法的收敛性迭代法的收敛性 第2章 一元线性方程的解发 计算方法 Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。 x* x0 x0 x0 第2章 一元线性方程的解发 计算方法 (1) (1) 选定初值选定初值x0 、 (3) (3) 按迭代公式得新的近似值按迭代公式得新的近似值xk+1

29、 (4) (4) 判定误差判定误差，决定是否决定是否终止迭代。终止迭代。 (2) (2) 计算计算f (x) Newton迭代法的步骤迭代法的步骤 第2章 一元线性方程的解发 计算方法 Newton迭代法的步骤迭代法的步骤 10 xx 10 xx 0 10 () () f x xx fx 结束结束 1,2,kN I 输出输出 F 0, , xN 输入输入 0 ()0fx 1I 0I 1I 11 ,( ),xf xk 输出输出 00 ( ),( )f xf x求求 kN F T T 允许精度允许精度 最大迭代最大迭代 次数次数 第2章 一元线性方程的解发 计算方法 例例 用用NewtonNewt

30、on迭代法求方程迭代法求方程xexex x-1=0-1=0在在0.50.5附近的根附近的根, , 精度要求精度要求 =10=10-5 -5. . 解：解：NewtonNewton迭代格式为迭代格式为 , 2 , 1 , 0, 1 1 1 k x ex x exe ex xx k x k k x k x x k kk k kk k kxk(xk)|xk-xk-1| 0 1 2 3 4 0.5 0.57102044 0.56715557 0.56714329 0.56714329 -0.17563936 0.01074751 0.00003393 0.0000000003 0.0000000003

31、 0.07102044 0.00386487 0.00001228 0.00000000 第2章 一元线性方程的解发 计算方法 1 1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过 程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比 简单迭代法优越的地方。简单迭代法优越的地方。 2 2、缺点：选定的初值要接近方程的解，否则有可能得不到、缺点：选定的初值要接近方程的解，否则有可能得不到 收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代

32、 除计算函数值外还要计算微商值。除计算函数值外还要计算微商值。 第2章 一元线性方程的解发 计算方法 将将Newton迭代中的导数，用差商代替，有格式迭代中的导数，用差商代替，有格式 1 1 1 () ()() k kk kk kk f x xx f xf x xx 是是2步格式。收敛速度比步格式。收敛速度比Newton迭代慢迭代慢 x0 x1 切线切线 割线割线 4 弦截法弦截法 x2x2 第2章 一元线性方程的解发 计算方法 点xk+1是满足该弦的方程的点，即有 1 1 ()() ()() kk kk kk f xf x yf xxx xx 1 1 1 ()() 0()() kk kkk

33、kk f xf x f xxx xx 从而可求得弦截迭代公式 11 1 () () ()() k kkkk kk f x xxxx f xf x (223) 第2章 一元线性方程的解发 计算方法 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作为初始近似根,令 f(x)=x-e-x=0 利用上面公式得到弦截迭代公式为 1 11 1 () ()() k kk x k kkkk xx kk xe xxxx xxxe 计算结果见下页表。 可以看出弦截法的收敛速度也是比较快的。 第2章 一元线性方程的解发 计算方法 第2章 一元线性方程的解发 计算方法 5 加速迭代法加速迭代法

34、 已知方程的近似根xk，按迭代公式可求得xk+1。现 考虑把xk+1作为过渡值,记为 1 () kk xg x 11kkk xmxnx 第2章 一元线性方程的解发 计算方法 仍然设仍然设x*为方程的根，即为方程的根，即 由迭代公式有：由迭代公式有： ()xg x 1 1 ()() ( )() kk kk xxg xg x xxgxx a 也即也即 1 () kk xxa xx 第2章 一元线性方程的解发 计算方法 1 1 11 1 , 11 kk a xxx aa a mn aa 整理得到 于是,只要取 这样可得到加速迭代公式 1 11 () 1 11 kk kkk xg x a xxx aa

35、 第2章 一元线性方程的解发 计算方法 例例5 用加速迭代公式求方程 x=e-x 在x=0.5附近的一个根。 1 11 10.6 1.61.6 k x k kkk xe xxx 解 因为在x=0.5附近 g(x)=-e-x g(0.5)=-e-0.5-0.6 故加速迭代公式的具体形式为： 第2章 一元线性方程的解发 计算方法 第2章 一元线性方程的解发 计算方法 与例2（P35）比较： 例2：迭代十次 满足精度=10-3 例5：迭代三次 满足精度=10-5 第2章 一元线性方程的解发 计算方法 上述迭代法需要计算导数ag(x)， 下面介绍埃特金(Aitken)迭代方法。它也是一种加速迭代法。

36、11 11 1 () ()() () kk kk k xg x xxg xg x a xx 1 () kk xxa xx 埃特金迭代法 第2章 一元线性方程的解发 计算方法 将上两式联立消去a得到 可解出 1 11 kk kk xxxx xxxx 11 11 2 11 1 11 2 () 2 kkk kkk kk k kkk x xx x xxx xx x xxx 第2章 一元线性方程的解发 计算方法 这样得到埃特金迭代公式 1 11 2 11 11 11 () () () 2 kk kk kk kk kkk xg x xg x xx xx xxx 第2章 一元线性方程的解发 计算方法 例例6

37、 用埃特金迭代法求 x3-x-1=0 在(1,1.5)内的根。 解解 前面已经提到,迭代公式 xk+1=x3k-1, k=0,1,2, 是发散的。 现用埃特金算法来求根,其迭代公式为 第2章 一元线性方程的解发 计算方法 仍取x0=1.5,计算结果见下表。 3 1 3 11 2 11 11 11 1 1 () 2 kk kk kk kk kkk xx xx xx xx xxx 第2章 一元线性方程的解发 计算方法 第2章 一元线性方程的解发 计算方法 定义定义2.2.1 设序列 收敛到 ，若有实数 和非零常数C，使得 其中 ， ，则称该序列是p 阶收 敛的，C 称为渐进误差常数。 0n x *

38、 x 1p C e e p n n n 1 lim * xxe nn 迭代法收敛的阶迭代法收敛的阶 第2章 一元线性方程的解发 计算方法 当p=1时，称为线性收敛； 当p1时，称为超线性收敛； 当p=2时，称为平方收敛或二次收敛。 第2章 一元线性方程的解发 计算方法 一般迭代法是线性收敛一般迭代法是线性收敛 线性收敛到 。 0)( )()( limlim * * * 1 n x xx xx e e n n n n n 因为 0 n x所以 * x 第2章 一元线性方程的解发 计算方法 迭代法的收敛速度迭代法的收敛速度 )(0)( 0)(.)()( )(,)( * 0 10 *)( *) 1(* * xpx xxxx xxx xxxx n kk p p D 阶收敛速度收敛到，以列 产生的序，由，则而 邻域内连续，且有 的不动点是设 定理定理 )(p 在x*的 第2章 一元线性方程的解发 计算方法 证：证： ( ) 0 ( ) ()( *)(*) ! p P kk xxxx P xx 其中 在 和 之间 ! )( )( lim *)( * * 1 p x xx xx p p n n n 将 (x ) 在x*附近做泰勒展式： 因为有： 1 ( )