1、第2章 一元线性方程的解发 计算方法第2章 一元非线性方程的解法1 二分法二分法2 迭代法迭代法3 切线法切线法(牛顿法牛顿法)4 弦截法弦截法5 加速迭代法加速迭代法第2章 一元线性方程的解发 计算方法 y a+1 a -50 O 50 x 50,502)(xeeayaxax第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,即即 12)(5050aeeaaxa y a
2、+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）在行星轨道（planetary orbits）的计算中,对任意的a和b，我们需要求x-asinx=b
3、的根（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)cos03xxe非线性方程可分为两种：非线性方程可分为两种：u 超越函数超越函数，即不能表示为上述形式的函数。，即不能表示为上述形式的函数。第2章 一元线性方程的解发
4、计算方法l 远在公元前远在公元前1700年的古巴比伦人就已有关于一、二次方程的年的古巴比伦人就已有关于一、二次方程的解法。解法。l 1535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)发现了三次方程发现了三次方程的解法，卡当的解法，卡当(HCardano)从他那里得到了这种解法，于从他那里得到了这种解法，于1545年在其名著年在其名著大法大法中公布了三次方程的公式解，称为中公布了三次方程的公式解，称为卡当算法。卡当算法。l 后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。又提出了四次方程的解法。第2章 一元线性方程的解发 计算方法l
5、1799年，高斯证明了代数方程必有一个实根或复根的定理，年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理称此为代数基本定理，并由此可以立刻推理n次代数方程必次代数方程必有有n个实根或复根。个实根或复根。l 但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其中的奥妙开始意识到有潜藏其中的奥妙,用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。l 在继续探索在继续探索5次以上方程解的艰难历程中，第一个重大突破次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔的是挪威数学家阿贝尔(NAbel1802-1829)182
6、4年阿贝尔发年阿贝尔发表了表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的论文，但并未受的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。到重视，连数学大师高斯也未理解这项成果的重要意义。第2章 一元线性方程的解发 计算方法l 十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)整理并发表了整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。要成果的宝贵。l 38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在专著在专著论置换与代数方程
7、论置换与代数方程中阐发了伽罗华的思想，一门现代中阐发了伽罗华的思想，一门现代数学的分支数学的分支群论诞生了。群论诞生了。l 在前几个世纪中，曾开发出一些求解代数方程的有效算法，在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。在一般的求根方式。第2章 一元线性方程的解发 计算方法方程根的数值计算步骤方程根的数值计算步骤u判断根的存在判断根的存在u确定根的分布范围确定根的分布范围u根的精确化根的精确化第2章 一元线性方程的解发 计算方法 根的存在定理根的存在定理(零点定理零点定
8、理)：f(x)为为 a,b 上的连续函数，若上的连续函数，若 f(a)f(b)0 0，则，则 a,b 中至少有一个实根。如果中至少有一个实根。如果f(x)在在 a,b 上还是单上还是单调递增或递减的，则调递增或递减的，则f(x)=0 0仅有一个实根。仅有一个实根。第2章 一元线性方程的解发 计算方法根的分布范围根的分布范围:在用近似方法时，需要知道方程的根所在区间。在用近似方法时，需要知道方程的根所在区间。若区间若区间 a,b 含有方程含有方程f(x)=0 0的根，则称的根，则称 a,b 为为f(x)=0的的有根区间有根区间；若区间若区间 a,b 仅含方程仅含方程f(x)=0 0的一个根，的一
9、个根，则称则称 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的图像只有一个交点位于的图像只有一个交点位于0.50.5，11内内。画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点轴交点的大致位置。也可将的大致位置。也可将f(x)=0)=0等价变形为等价变形为g1 1(x)=)=g2 2(x)的形
10、式，的形式，y=g1 1(x)与与y=g2 2(x)两曲线交点的横坐标所两曲线交点的横坐标所在的子区间即为含根区间。在的子区间即为含根区间。(1)描图法描图法第2章 一元线性方程的解发 计算方法(2)逐步搜索法逐步搜索法运用零点定理可以得到如下逐步搜索法：运用零点定理可以得到如下逐步搜索法：先确定方程先确定方程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)的值的值,依据
11、函数值异号及实根的个数确依据函数值异号及实根的个数确定隔根区间定隔根区间,通过调整步长，总可找到所有隔根通过调整步长，总可找到所有隔根区间。区间。第2章 一元线性方程的解发 计算方法例例1 1 方程方程f(xf(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 xf(xf(x)0 0.5 1.0 1.5
12、20 0.5 1.0 1.5 2 +可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根内必有一根第2章 一元线性方程的解发 计算方法1二分法二分法 设函数设函数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章 一元线性方程的解发 计算方法
13、如此逐次往复下去,便得到一系列有根区间 (a,b),(a1,b1),(a2,b2),(ak,bk),其中111()21()2kkkkkkkbabababa这里a0=a,b0=b显然有 当k时,区间(ak,bk)最终必收敛于一点,该点就是所求方程的根x。第2章 一元线性方程的解发 计算方法abx0 x1ab什么时候停止？x*kxx第2章 一元线性方程的解发 计算方法误差误差 分析：分析：第第1步产生的步产生的02a bx有误差有误差02b a|x x|第第 k 步产生的步产生的 xk 有误差有误差122kkkkbaba|xx|对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需
14、的步数 k：1lnln12ln 2kbabak第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)的中点01(1 1.5)1.252x 第2章 一元线性方程的解发 计算方法 由
15、于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=0在x=1.5附近的一个根(用六位有效数字计算)。
16、第2章 一元线性方程的解发 计算方法首先将原方程改写成等价形式31xx用初始近似根 x0=1.5 代入上式的右端可得3011.35721xx32110,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章 一元线性方程的解发 计算方法几何意义几何意义:()yxyg x和的交点 x=g(x)第2章 一元线性方程的解发 计算方
17、法xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第2章 一元线性方程的解发 计算方法同样的方程同样的方程不同的迭代格式不同的迭代格式有不同的结果有不同的结果什么形式的迭代什么形式的迭代法能够收敛呢法能够收敛呢?如何构造迭代函如何构造迭代函数呢数呢?第2章 一元线性方程的解发 计算方法 若从任何可取的初值出发都能保证收敛，则称它若从任何可取的初值出发都能保证收敛，则称它为为大范围收敛大范围收敛。如若为了保证收敛性必须选取初值充。如若为了保证收敛性必须选取初值充分接近
18、于所要求的根，则称它为分接近于所要求的根，则称它为局部收敛局部收敛。通常局部收敛方法比大范围收敛方法收敛得快。通常局部收敛方法比大范围收敛方法收敛得快。因此，一个合理的算法是先用一种大范围收敛方法求因此，一个合理的算法是先用一种大范围收敛方法求得接近于根的近似值（如对分法），再以其作为新的得接近于根的近似值（如对分法），再以其作为新的初值使用局部收敛法（如迭代法）。初值使用局部收敛法（如迭代法）。这里讨论迭代法的收敛性时，均指的是局部收敛这里讨论迭代法的收敛性时，均指的是局部收敛性。性。第2章 一元线性方程的解发 计算方法1212()()g xg xq xx1.则方程在则方程在(a,b)内有唯
19、一的根；内有唯一的根；11011kkkkqqxxxxxxqq 定理定理/收敛定理收敛定理/压缩映像原理压缩映像原理l 设方程设方程x=g(x)在在(a,b)内有根内有根x*l g(x)满足李普希茨满足李普希茨(Lipschitz)条件条件:即对即对(a,b)内任意的内任意的x1 和和x2都有：都有：q为某个确定的正数，为某个确定的正数，q1 条件条件结果结果3.还有误差估计式还有误差估计式2.且迭代公式且迭代公式 xk+1=g(xk)对对任意任意初始近似值初始近似值x0均收敛于均收敛于方程的根方程的根x；第2章 一元线性方程的解发 计算方法 由已知条件知，由已知条件知，x*为方程为方程x=g(
20、x)的根，即的根，即x*=g(x*)()()xg xyg y设设 也是方程的根，即也是方程的根，即xy于是，由李普希茨条件得于是，由李普希茨条件得()()xyg xg yq xy因为因为q1，所以上式矛盾，故必有，所以上式矛盾，故必有xy 证 1.有唯一根第2章 一元线性方程的解发 计算方法 考虑迭代公式 x k+1=g(xk),k=0,1,2,由李普希茨条件10()()kkkxxg xg xq xx 证 2.迭代公式收敛因为q1，当k时，qk0，即有 10kxxlimkkxx所以 第2章 一元线性方程的解发 计算方法 证 3.误差|xk-x*|=|xk-xk-1|=|g(xk-1)-g(xk
21、-2)|xk-x*|q/(1-q)|xk-xk-1|xk-x*|qk/(1-q)|x1-x0|可用可用 来来控制收敛精度控制收敛精度|1kkxx 1212()()g xg xq xx李普希茨李普希茨(Lipschitz)条件条件|g(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必须说明两点必
22、须说明两点:对于收敛的迭代过程，误差估计式说明迭代值的偏差xk-xk-1相当小，就能保证迭代误差x-xk足够小。因此在具体计算时常常用条件 xk-xk-1 来控制迭代过程结束。第2章 一元线性方程的解发 计算方法 例例 求方程 x=e-x 在x=0.5附近的一个根。按五位小数计算,计算结果 的精度要求为=10-3。()0.61xe 解 过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 xx10 xx01()g xx开始开始结束结束0,x输入输入1x输出输
23、出FT第2章 一元线性方程的解发 计算方法g(x)=e-x第2章 一元线性方程的解发 计算方法 因此用迭代公式 由表可见1kxkxe10 xxxxe为方程 的根 第2章 一元线性方程的解发 计算方法 最一般的形式可以写成 x=x+(x)f(x)这里(x)为任意一个正(或负)的函数。于是 g(x)=x+(x)f(x)这样只要合理选取(x),使得迭代公式满足收敛条件()1g xq如何构造迭代函数如何构造迭代函数g(x)呢呢?第2章 一元线性方程的解发 计算方法切线迭代公式：切线迭代公式：11(),1,2,()()kkxxa xkf xf x 弦截迭代公式：弦截迭代公式：1()()a xfx 第2章
24、 一元线性方程的解发 计算方法 设x*是方程f(x)=0的根，又x0 为x*附近的一个值，将f(x)在x0附近做泰勒展式之间和在其中020000)()(21)()()()(xxfxxxfxxxfxf*xx)()(21)()()()(020*00*0*fxxxfxxxfxf 3 切线法切线法(牛顿法牛顿法)令 ，则第2章 一元线性方程的解发 计算方法去掉 的二次项，有：0*xx 0)()()(000*0 xfxxfxxf*000()()f xxxfx1x即以x1代替x0重复以上的过程，继续下去得：第2章 一元线性方程的解发 计算方法,.1,0)()(1nxfxfxxnnnn以此产生的序列以此产生
25、的序列xn得到得到f(x)=0的近似解，称为的近似解，称为Newton法，又叫切线法。法，又叫切线法。第2章 一元线性方程的解发 计算方法牛顿法的几何意义牛顿法的几何意义xyx*x00100()()fxxxfxx 1x 2000()()()yf xfxxx1211()()fxxxfx牛顿法也称为切线法牛顿法也称为切线法,.1,0)()(1nxfxfxxnnnn()f x第2章 一元线性方程的解发 计算方法Newton迭代的方程为：迭代的方程为：)()()(0)(xfxfxxxxf所以所以2)()()()()()(xfxfxfxfxfxx若若f(x)在在x*处为单根，则处为单根，则(*)0,(*
26、)0,(*)0f xfxx所以，迭代格式收敛。所以，迭代格式收敛。Newton迭代法的收敛性迭代法的收敛性第2章 一元线性方程的解发 计算方法Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0第2章 一元线性方程的解发 计算方法(1)(1)选定初值选定初值x0、(3)(3)按迭代公式得新的近似值按迭代公式得新的近似值xk+1 (4)(4)判定误差判定误差，决定是否决定是否终止迭代。终止迭代。(2)(2)计算计算f (x)Newton迭代法的步骤迭代法的步骤第2章 一元线性方程的解发 计算方法Newton迭代法的步骤迭代法的步骤10 xx10 xx0
27、10()()f xxxfx结束结束1,2,kNI输出输出F0,xN输入输入0()0fx1I 0I 1I 11,(),xf xk输出输出00(),()f xf x求求kNFTT允许精度允许精度最大迭代最大迭代次数次数第2章 一元线性方程的解发 计算方法 例例 用用NewtonNewton迭代法求方程迭代法求方程xexex x-1=0-1=0在在0.50.5附近的根附近的根,精度要求精度要求=10=10-5-5.解：解：NewtonNewton迭代格式为迭代格式为,2,1,0,111kxexxexeexxxkxkkxkxxkkkkkkkkxk(xk)|xk-xk-1|012340.50.57102
28、0440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000第2章 一元线性方程的解发 计算方法1 1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。简单迭代法优越的地方。2 2、缺点：选定的初值要接近方程的解，否则有可能得不
29、到、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。除计算函数值外还要计算微商值。第2章 一元线性方程的解发 计算方法将将Newton迭代中的导数，用差商代替，有格式迭代中的导数，用差商代替，有格式111()()()kkkkkkkf xxxf xf xxx是是2步格式。收敛速度比步格式。收敛速度比Newton迭代慢迭代慢x0 x1切线切线 割线割线 4 弦截法弦截法 x2x2第2章 一元线性方程的解发 计算方法 点xk+1是满足该弦的方程的点，即有11()()(
30、)()kkkkkkf xf xyf xxxxx111()()0()()kkkkkkkf xf xf xxxxx从而可求得弦截迭代公式 111()()()()kkkkkkkf xxxxxf xf x(223)第2章 一元线性方程的解发 计算方法 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作为初始近似根,令 f(x)=x-e-x=0 利用上面公式得到弦截迭代公式为1111()()()kkkxkkkkkxxkkxexxxxxxxe计算结果见下页表。可以看出弦截法的收敛速度也是比较快的。第2章 一元线性方程的解发 计算方法第2章 一元线性方程的解发 计算方法5 加速迭代法加
31、速迭代法 已知方程的近似根xk，按迭代公式可求得xk+1。现考虑把xk+1作为过渡值,记为1()kkxg x11kkkxmxnx第2章 一元线性方程的解发 计算方法 仍然设仍然设x*为方程的根，即为方程的根，即 由迭代公式有：由迭代公式有：()xg x11()()()()kkkkxxg xg xxxgxxa也即也即 1()kkxxa xx第2章 一元线性方程的解发 计算方法11111,11kkaxxxaaamnaa整理得到 于是,只要取 这样可得到加速迭代公式 111()111kkkkkxg xaxxxaa第2章 一元线性方程的解发 计算方法 例例5 用加速迭代公式求方程 x=e-x 在x=0
32、.5附近的一个根。11110.61.61.6kxkkkkxexxx 解 因为在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)迭代方法。它也是一种加速迭代法。11111()()()()kkkkkxg xxxg xg xa xx1()kkxxa xx埃特金迭代法第2章 一元线性方程的
33、解发 计算方法 将上两式联立消去a得到可解出 111kkkkxxxxxxxx11112111112()2kkkkkkkkkkkkx xxxxxxxxxxxx第2章 一元线性方程的解发 计算方法 这样得到埃特金迭代公式1112111111()()()2kkkkkkkkkkkxg xxg xxxxxxxx第2章 一元线性方程的解发 计算方法 例例6 用埃特金迭代法求 x3-x-1=0 在(1,1.5)内的根。解解 前面已经提到,迭代公式 xk+1=x3k-1,k=0,1,2,是发散的。现用埃特金算法来求根,其迭代公式为第2章 一元线性方程的解发 计算方法仍取x0=1.5,计算结果见下表。31311
34、211111111()2kkkkkkkkkkkxxxxxxxxxxx第2章 一元线性方程的解发 计算方法第2章 一元线性方程的解发 计算方法定义定义2.2.1 设序列 收敛到 ，若有实数 和非零常数C，使得 其中 ，则称该序列是p 阶收敛的，C 称为渐进误差常数。0nx*x1pCeepnnn1lim*xxenn迭代法收敛的阶迭代法收敛的阶第2章 一元线性方程的解发 计算方法当p=1时，称为线性收敛；当p1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。第2章 一元线性方程的解发 计算方法一般迭代法是线性收敛一般迭代法是线性收敛线性收敛到 。0)()()(limlim*1nxxxxxee
35、nnnnn因为0nx所以*x第2章 一元线性方程的解发 计算方法迭代法的收敛速度迭代法的收敛速度)(0)(0)(.)()()(,)(*010*)(*)1(*xpxxxxxxxxxxxxnkkppD 阶收敛速度收敛到，以列产生的序，由，则而邻域内连续，且有的不动点是设定理定理)(p在x*的第2章 一元线性方程的解发 计算方法 证：证：()0()()(*)(*)!pPkkxxxxPxx其中 在 和 之间!)()(lim*)(*1pxxxxxppnnn将 (x)在x*附近做泰勒展式：因为有：1()1()(*)*()*(*)!kkpPkkxxxxxxxxP，由上式有：第2章 一元线性方程的解发 计算方
36、法定理：由埃特金迭代公式定理：由埃特金迭代公式 产生的序列产生的序列 至少平方收敛到至少平方收敛到 。0nx*x n=0，1，2，nn+1n+1nn+1nnn+1n+1nn+1xxxxxxxxxxx2)()()(21()x第2章 一元线性方程的解发 计算方法*1*()limlim()1lim()11nnnnnnnxxxxnnnxxxxxxxxxxxx的不动点，是证明：)(*xxx。即)(*xx第2章 一元线性方程的解发 计算方法还有：*()2()limnnnnxxnxxxxx*lim()()2()1)nnnnxxxxx*()()2()1xxx2*1)(x*11*2limnnnnxxnxxxxx
37、第2章 一元线性方程的解发 计算方法*()()()limnnxxnxxxxx于是有*2*()()2()limnnnnnnxxnxxxxxxxxx*2*()1lim()2()nnnnxxnnnnxxxxxxxxx 0 1)(1)(12*2*xx由埃特金迭代公式至少是由埃特金迭代公式至少是2阶（平方）收敛的。阶（平方）收敛的。第2章 一元线性方程的解发 计算方法 由线性收敛知由线性收敛知 当当n充分大时有充分大时有 即即0limlim112nCeeeennnnnnnnneeee112*1*1*2xxxxxxxxnnnn加速迭代法的另种推导加速迭代法的另种推导第2章 一元线性方程的解发 计算方法展开
38、有：展开有：nnnnnnxxxxxxx1221*2)(2*121*2)(2)(xxxxxxxxnnnn2*1212*2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxx第2章 一元线性方程的解发 计算方法已知 ，则 ，改成nx)(1nnxx)(2nnxx n=0，1，2，nn+1n+2nn+1nnn+1n+2nn+1xxxxxxxxxxx2)()()(21第2章 一元线性方程的解发 计算方法也可以改写成其中迭代函数,.)1,0()(1nxxnnxxxxxxx)(2)()()(2第2章 一元线性方程的解发 计算方法习题习题习题二习题二:2,3,4,5
