计算方法课件7

1、2.2.4 迭代过程的加速迭代过程的加速一、加权法一、加权法11 ()1kkkxxcxc二、埃特金加速法和斯蒂芬森迭代法二、埃特金加速法和斯蒂芬森迭代法1、埃特金加速法、埃特金加速法22121212kkkkkkkxxxxxxx2、斯蒂芬森算法、斯蒂芬森算法1()kkkyxx2()kkkzyx221()22kkkkkkkkkkkkkx zyyxxxzyxzyx 说明：说明：a.a.埃特金算法适用于任意线性序列，斯蒂芬森埃特金算法适用于任意线性序列，斯蒂芬森算法只针对不动点迭代。算法只针对不动点迭代。b.b.只要迭代函数只要迭代函数( (x) )满足满足(x*)1。不管原迭。不管原迭 代法是否收敛

2、，由它构造的代法是否收敛，由它构造的斯蒂芬森迭代法至斯蒂芬森迭代法至 少是平方收敛的。它是对不动点迭代法的收敛少是平方收敛的。它是对不动点迭代法的收敛 性和收敛速度的一种改善方法。性和收敛速度的一种改善方法。c.c.当原来的迭代法已有二阶或更高收敛阶时，当原来的迭代法已有二阶或更高收敛阶时， 没必要使用没必要使用斯蒂芬森算法，这时加速效果已斯蒂芬森算法，这时加速效果已 不显著。不显著。2.3.1 牛顿迭代公式牛顿迭代公式一、迭代公式一、迭代公式( )0,()0kf xfx非线性方程若1()()kkkkf xxxfx0,1,2,k *x1 kxkx )(,kkkxfxpy xfy x0定理定理1

3、: *()0,()0()2f xfxfxxx设且在 邻域连续，则牛顿迭代法在根 局部收敛，且至少是 阶收敛，并有*12*()lim2()kkkefxefx2.3.3 改进牛顿迭代公式改进牛顿迭代公式一、简化牛顿法一、简化牛顿法1( )kkkf xxxc其中其中c为常数为常数二、牛顿下山法二、牛顿下山法1()()kkkkf xxxfx01下山因子（）1()()kkf xf x下山成功条件：下山成功条件：三、重根时的修正算法三、重根时的修正算法*( )02),xf xmm1、 当重根数已知时，设 是的 重根(即满足*(1)*()*()()()0,()0mmfxfxfxfx则迭代过程则迭代过程1()

4、()kkkkfxxxfx是线性收敛，不是平方收敛。是线性收敛，不是平方收敛。修正算法修正算法( )( )( )f xxxmfx迭代函数*()0 x此时1()()kkkkf xxxmfx迭代格式是平方收敛的。是平方收敛的。这种修正方法需要预知重根数这种修正方法需要预知重根数m的值。的值。例例1: 32( )() ,( )0f xxaf x设函数写出解的牛顿迭代格式，并证明此格式的收敛阶。解解: 3232( )() ,( )6()f xxafxxa x将代入牛顿迭代法，有代入牛顿迭代法，有 321322()56()66kkkkkkkxaaxxxxa xx25( ),66axxx迭代函数所以牛顿迭代

5、法为线性收敛。所以牛顿迭代法为线性收敛。*33,()0.510 xaa又已知35( )63axxm=2。若选取迭代格式。若选取迭代格式 321322()226()33kkkkkkkxaaxxxxa xx22( ),33axxx迭代函数所以牛顿迭代法为平方收敛。所以牛顿迭代法为平方收敛。*333,()0,()0 xaaa又已知322( )33axx例例2 2：422( )440 xf xxx已知是方程的二重根，用牛顿迭代法重根修正公式求解。解：解：牛顿迭代法牛顿迭代法422223244(2)2484 (2)4xxxxxxxxxxx xx重根数重根数m=2=2时，修正公式时，修正公式2224xxx

6、x取取x0=1.5=1.5k牛顿值xkxk (m已知时)01.51.511.4583333331.41666666721.4366071431.41421686531.4254976191.4142135622 2、当重根数未知时，令、当重根数未知时，令( )( )( )f xxfx牛顿迭代法修正为牛顿迭代法修正为( )( )xxxx则该方法是二阶收敛的。则该方法是二阶收敛的。迭代格式迭代格式2( )( )( )( )( )fx f xxxfxf x fx2( )( )( )( )( )( )( )( )xfx f xxxxxfxf x fx此时取取x0=1.5=1.5k牛顿值xkxk (m已

7、知时)xk (m未知时)01.51.51.511.4583333331.4166666671.41176470621.4366071431.4142168651.41421143831.4254976191.4142135621.414213562例：例：422( )440 xf xxx已知是方程的二重根，用牛顿迭代法和重根修正公式求解。解：解：牛顿迭代法牛顿迭代法12() ()()()()kkkkkkkfxf xxxfxf xfx作业：作业：数值计算方法数值计算方法P55：2.1-2.14题题 科学与工程计算科学与工程计算P67：1-17题题 第三章第三章 解线性代数方程解线性代数方程 组的

8、直接法组的直接法3.1 3.1 高斯消去法高斯消去法 3.1.1 3.1.1 基本思想基本思想 3.1.2 3.1.2 计算步骤计算步骤 3.1.3 3.1.3 使用条件使用条件 3.1.4 3.1.4 计算量计算量3.2 3.2 列主元高斯消去法列主元高斯消去法 3.2.1 3.2.1 数值不稳定数值不稳定 3.2.2 3.2.2 选主技术选主技术 3.2.3 3.2.3 计算矩阵行列式计算矩阵行列式 3.2.4 3.2.4 高斯高斯约当消去法约当消去法3.3 3.3 矩阵三角分解法矩阵三角分解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 3.3.2 3.3.2 解线性方程组

9、的三角分解法解线性方程组的三角分解法 3.3.3 3.3.3 平方根法平方根法 3.3.4 3.3.4 追赶法追赶法3.4 3.4 向量和矩阵的范数向量和矩阵的范数 3.4.1 3.4.1 向量的范数向量的范数 3.4.2 3.4.2 矩阵的范数矩阵的范数第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法n阶线性代数方程组的一般形式阶线性代数方程组的一般形式11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb写成矩阵写成矩阵向量形式向量形式Axb1111nnnnaaAaa12nxxxx12nbbbb其中其中A称为系数矩阵，称为系数矩

10、阵，x称为解向量，称为解向量，b称为右端常向量。称为右端常向量。问题提出：问题提出：一、一、数学准备数学准备(一一) 克莱姆克莱姆(Gramer)法则法则 含有含有n个未知量个未知量n个方程的线性方程组，当个方程的线性方程组，当其系数矩阵的行列式其系数矩阵的行列式D0时，线性方程组有且时，线性方程组有且仅有唯一解仅有唯一解1, 2,iiDxinD 其中，其中，D表示表示det(A)，Di表示表示D中第中第i列换成列换成b后所得行列式。后所得行列式。克莱姆法则解线性方程组的计算量（乘法次数）克莱姆法则解线性方程组的计算量（乘法次数）(1)! (1)nSnnn212010n 例如，乘法次数为两类数

11、值解法：两类数值解法：直接解法直接解法：假定计算过程没有舍入误差的情况下，假定计算过程没有舍入误差的情况下， 经过有限步算术运算后能求得线性方程经过有限步算术运算后能求得线性方程 组精确解的方法组精确解的方法。迭代解法迭代解法: :构造适当的向量序列，用某种极限过程去构造适当的向量序列，用某种极限过程去 逐步逼近精确解。逐步逼近精确解。但实际计算中由于舍入误差的影响，这类方法也只能求得近似解但实际计算中由于舍入误差的影响，这类方法也只能求得近似解例如：高斯消去法、三角分解法等。例如：高斯消去法、三角分解法等。例如：雅可比迭代法、高斯例如：雅可比迭代法、高斯- -赛德尔迭代法等。赛德尔迭代法等。

12、(二二) 下三角方程组（矩阵）下三角方程组（矩阵）177x12232xx12345610 xxx 1717x 下三角阵下三角阵1237723245614xxx 123101xxx211(22)03xx3121(1045)6xxx111121222212nnnnnnaxbaaxbaaaxb 111 1bxa111()1, 2 ,iiiikkkiixbaxina或得到或得到221 212 21()xbaxa211()innn kkkn nxbaxa结论：结论： 已知下三角方程组已知下三角方程组Axb1212, ,TnTnnbb bbRxx xx其中已知，未知n nijAaR是已知的非奇异下三角阵，

13、即11212212nnnnaaaAaaa aii0, i=1,2,n由方程组第一个方程由方程组第一个方程111 1111ba xbxa由第二个方程由第二个方程21 122222221 1221()a xa xbxba xa顺序求出顺序求出x2、x3、xi-1 时，由第时，由第i个方程个方程1 122,11iii iiiiiia xa xaxa xb1 122,111()iiiii iiiixba xa xaxa求出111()iiikkkiiba xa2,3,in称之为顺代。称之为顺代。21(1)(21)22nin ninn该法的计算量该法的计算量(三三) 上三角方程组（矩阵）上三角方程组（矩阵

14、）377x23233xx12345610 xxx 377x231(33)2xx132110654xxx上三角阵上三角阵1234561023377xxx 123101xxx111211122222nnnnnnaaaxbaaxbaxb 11(),1, 2,1niiikkkiiixbaxin na 或得到或得到nnn nbxa22232 21()nkkkxbaxa11121 11()nkkkxbaxa结论：结论： 已知上三角方程组已知上三角方程组Axb1212, ,TnTnnbb bbRxx xx其中已知，未知n nijAaR是已知的非奇异上三角阵，即aii0, i=1,2,n从最后一个方程依次求出

15、从最后一个方程依次求出aij=0, ij11()1, 2,1nnnnniiikkkiiibxaxbaxina 这个过程称为回代。这个过程称为回代。11(),1, 2,1niiikkkiiixbaxin na 或表示成或表示成3.1 3.1 高斯消去法高斯消去法 3.1.1 3.1.1 基本思想基本思想 3.1.2 3.1.2 计算步骤计算步骤 3.1.3 3.1.3 使用条件使用条件 3.1.4 3.1.4 计算量计算量3.2 3.2 列主元高斯消去法列主元高斯消去法 3.2.1 3.2.1 数值不稳定数值不稳定 3.2.2 3.2.2 选主技术选主技术 3.2.3 3.2.3 计算矩阵行列式

16、计算矩阵行列式 3.2.4 3.2.4 高斯高斯约当消去法约当消去法3.3 3.3 矩阵三角分解法矩阵三角分解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 3.3.2 3.3.2 解线性方程组的三角分解法解线性方程组的三角分解法 3.3.3 3.3.3 平方根法平方根法 3.3.4 3.3.4 追赶法追赶法3.4 3.4 向量和矩阵的范数向量和矩阵的范数 3.4.1 3.4.1 向量的范数向量的范数 3.4.2 3.4.2 矩阵的范数矩阵的范数第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法3.1 高斯消去法高斯消去法3.1.1 基本思想基本思想 利用初等变换用逐

17、次消去未知数的方法把原方程组化为上三角形方程组进行求解 。1、消元：用初等行变换将原方程组的系数矩阵 化为上三角形矩阵(简称上三角阵)。2、回代：对上三角形方程组的最后一个方程 求解，将求得的解逐步往上一个方 程代入求解。 求解分成两步：例例1：三阶方程组：三阶方程组12312312231425427xxxxxxxx2 1 3 14 2 5 41 2 0 753222 1 310 41 206.52 1310 4120 00.875 5.25123233231420 .8 7 55 .2 5xxxxxx36x 21x 19x 回代回代2121112ama31311112ama32322258a

18、ma3.1 3.1 高斯消去法高斯消去法 3.1.1 3.1.1 基本思想基本思想 3.1.2 3.1.2 计算步骤计算步骤 3.1.3 3.1.3 使用条件使用条件 3.1.4 3.1.4 计算量计算量3.2 3.2 列主元高斯消去法列主元高斯消去法 3.2.1 3.2.1 数值不稳定数值不稳定 3.2.2 3.2.2 选主技术选主技术 3.2.3 3.2.3 计算矩阵行列式计算矩阵行列式 3.2.4 3.2.4 高斯高斯约当消去法约当消去法3.3 3.3 矩阵三角分解法矩阵三角分解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 3.3.2 3.3.2 解线性方程组的三角分解法

19、解线性方程组的三角分解法 3.3.3 3.3.3 平方根法平方根法 3.3.4 3.3.4 追赶法追赶法3.4 3.4 向量和矩阵的范数向量和矩阵的范数 3.4.1 3.4.1 向量的范数向量的范数 3.4.2 3.4.2 矩阵的范数矩阵的范数第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法3.1.2 计算步骤计算步骤下面讨论一般的下面讨论一般的n阶线性方程组的高斯消去法。阶线性方程组的高斯消去法。11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb写成矩阵写成矩阵向量形式向量形式Axb其中其中()ijnAa12(,)Tnxxxx

20、12(,)Tnbb bb记为记为(1)(1)Axb元素记为元素记为(1)(1),1,2,ijiabi jn和一、消元过程一、消元过程1、第一次消元：、第一次消元：11(1)0a设111(1)1(1)2,3,iiamina先对行计算乘数消元得到消元得到(2)(2)Axb(1)(1)(1)(1)1111211( 2 )( 2 )( 2 )22222( 2 )( 2 )( 2 )200nnnnnnnxaaabxaabxaab(2)ija其中其中(1)(1)11ijijam a(2)(1)(1)1 1iiibbm b,2,3,i jn2、第、第k次消元次消元 (2kn-1) ：设第设第k-1次消元已完

21、成，有次消元已完成，有( )( )kkAxb(1)(1)(1)11121(2)(2)222( )( )( )( )( )00nnkkkkkknkknknnaaaaaAaaaa (1)1(2)2( )( )( )kkkknbbbbb用用-mik乘第乘第k个方程，加到第个方程，加到第i个方程，消去第个方程，消去第i个个方程到第方程到第n个方程的未知数个方程的未知数xk，得到，得到(1)(1)kkAxb(1)kija其中其中( )( )kkijikkjam a(1)( )( )kkkiiikkbbm b,1,i jkn( )( )( )1,ikkkkkkkikkaamikna设0,计算乘数3、第、第

22、n-1次消元后，有次消元后，有( )( )nnAxb(1)(1)(1)(1)1111211(2)(2)(2)22222( )( )000nnnnnnnnxaaabxaabxab消元过程自上而下进行，每次都是顺序选取主消元过程自上而下进行，每次都是顺序选取主对角线上元素对角线上元素akk(k)作为主元素，消去以下各行作为主元素，消去以下各行相应的变元，叫顺序消去法。相应的变元，叫顺序消去法。二、回代过程二、回代过程对上式自下而上逐步回代，得对上式自下而上逐步回代，得()()nnnnnnbxa( )( )( )1() /niiiiiijjiijixbaxa 1,2,1in其中：其中：()(1,2,

23、)kkkakn各次消元的主元素ikm各次消元的乘数1,2,1kn1,1,iknn主元素所在的行称为主行。主元素所在的行称为主行。三、高斯消去法计算步骤总结三、高斯消去法计算步骤总结用用k表示消元过程的次序时，表示消元过程的次序时，1、消元过程、消元过程( )1,2,1kkkakn设0,对计算(1)( )( )kkkijijikkjaam a(1)( )( )kkkiiikkbbm b,1,i jkn( )( )/ikkkkkikmaa2、回代过程、回代过程()()/nnnnnnxba( )( )( )1() /niiiiiijjiijixbaxa 1,2,1in四、计算机计算高斯消去法框图及特

24、点四、计算机计算高斯消去法框图及特点开始开始读入读入aij, bi,i,j=1,2,n1 kaik/akk = aiki=k+1,k+2,nk= =n-1? ?输出输出b1,b2,bn结束结束k+1=kyN1/1()1,2,2,1nnnnniijjij iiibabba bbainn 选主元选主元aij-aikakj = aiji,j=k+1,k+2,nbi-aikbk = bii=k+1,k+2,n计算机计算高斯消去法特点计算机计算高斯消去法特点1、按消元规则进行运算后，对角线以下元素、按消元规则进行运算后，对角线以下元素 为为0，故运算中对角线以下元素不作计算，故运算中对角线以下元素不作计

25、算， 以减小计算量。以减小计算量。2、对角线以下元素对回代求解无影响，故将、对角线以下元素对回代求解无影响，故将 乘数放在该处，即乘数放在该处，即1,2,ikikkkaaikkna以节省存储单元。以节省存储单元。3、对角线以上元素和常数项采用、对角线以上元素和常数项采用“原地原地”工工作作 方式，即经变换后的元素仍放在原来的位方式，即经变换后的元素仍放在原来的位 置上以节省存储单元。置上以节省存储单元。aij-aikakj = aij i,j=k+1,k+2,nbi-aikbk = bi i=k+1,k+2,n4、回代后的值仍放在常数项存储单元以节省存储单元。、回代后的值仍放在常数项存储单元以

26、节省存储单元。1/1,2,2,11()nnnnniijjij iiibabinnba bba 这时这时b1,b2,bn中存放的就是输出值中存放的就是输出值x1, ,x2, , ,xn 。例例1：用计算机求解方程组：用计算机求解方程组111122133121122223323113223333a xaxaxbaxaxaxbaxaxaxb解：解：用增广矩阵各元素的位置代表计算机的存储单用增广矩阵各元素的位置代表计算机的存储单元，增广矩阵元素数值的变化代表存储单元所元，增广矩阵元素数值的变化代表存储单元所存放数据的变化。存放数据的变化。放入初始数据放入初始数据11121312122232313233

27、3aaabaaabaaab第一次消元第一次消元11121312223232333(1)(1)(1)(1)(2)(2)(2)21(2)(2)(2)31aaabmaabmaab第二次消元第二次消元111213122232333(1)(1)(1)(1)(2)(2)(2)21(3)(3)3132aaabmaabmmab第一次回代第一次回代11121312223233(1)(1)(1)(1)(2)(2)(2)21(3)31323aaabmaabmmax第二次回代第二次回代1112131222333(1)(1)(1)(1)(2)(2)212(3)31323aaabmaaxmmax第三次回代第三次回代111

28、213222333(1)(1)(1)1(2)(2)212(3)31323aaaxmaaxmmax例例2：用高斯消去法解：用高斯消去法解12312312324326225xxxxxxxxx解：消元过程解：消元过程211431261225211400.50.5001.51.53211400.50.500033回代过程回代过程3313x2311(0) /()122xx1324/ 21xxx3.1 3.1 高斯消去法高斯消去法 3.1.1 3.1.1 基本思想基本思想 3.1.2 3.1.2 计算步骤计算步骤 3.1.3 3.1.3 使用条件使用条件 3.1.4 3.1.4 计算量计算量3.2 3.2

29、 列主元高斯消去法列主元高斯消去法 3.2.1 3.2.1 数值不稳定数值不稳定 3.2.2 3.2.2 选主技术选主技术 3.2.3 3.2.3 计算矩阵行列式计算矩阵行列式 3.2.4 3.2.4 高斯高斯约当消去法约当消去法3.3 3.3 矩阵三角分解法矩阵三角分解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 3.3.2 3.3.2 解线性方程组的三角分解法解线性方程组的三角分解法 3.3.3 3.3.3 平方根法平方根法 3.3.4 3.3.4 追赶法追赶法3.4 3.4 向量和矩阵的范数向量和矩阵的范数 3.4.1 3.4.1 向量的范数向量的范数 3.4.2 3.4

30、.2 矩阵的范数矩阵的范数第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法3.1.3 使用条件使用条件一、数学准备一、数学准备1、定义：设、定义：设A=(aij)n.令令1111iiiiiaaDaa1,2,inD 1,D2,Dn是是1至至n阶行列式，称为阶行列式，称为A的的顺序主子式顺序主子式2、行列式性质：、行列式性质：把一行的倍数加到另一行，行列式值不变，把一行的倍数加到另一行，行列式值不变，即即A的一行乘上数的一行乘上数加到另一行得到加到另一行得到AdetdetAA证明：证明：把把A的第的第k行乘上数行乘上数加到第加到第i行得到行得到11121111211112111221

31、212121212121212nnnikikinkniiinkkknkkknkkknkkknnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanndetdetAA二、高斯消去法使用条件之一二、高斯消去法使用条件之一定理：方程组系数矩阵的顺序主子式全不为零，定理：方程组系数矩阵的顺序主子式全不为零， 则高斯消去法能实现方程组的求解。则高斯消去法能实现方程组的求解。证明：证明：从高斯消去法的计算过程可以看出，消从高斯消去法的计算过程可以看出，消元步骤能顺序进行的条件是元步骤能顺序进行的条件是(1)(2)(1)11221,1,nnnaaa全不为零。全不

32、为零。回代步骤则要求回代步骤则要求()0nnna方法一：方法一：设方程组系数矩阵设方程组系数矩阵A=(aij)n ,其顺序主子式其顺序主子式11110iiiiiaaDaa1,2,in三角方程组的顺序主子式三角方程组的顺序主子式111212211(1)(1)(1)(2)(2)22(1)(2)( )22( )00iiiiiiiiaaaaaDaaaa1,2,in故高斯消去法能实现方程组的求解故高斯消去法能实现方程组的求解方法二：方法二：(1)(2)( )11220nnna aa用数学归纳法证明111110iDa当时，(1)110a101,2,1iikDik当时，( )01,2,1iiiaik有因此高

33、斯消去法至少可进行前因此高斯消去法至少可进行前k-1步。将原方程化为步。将原方程化为( )( )kkAxb其中其中(1 )(1 )(1 )(1 )1 11 211( 2 )( 2 )( 2 )2 222()()()()()knknkkkk kk nkkn kn naaaaaaaAaaaa 由于消元时用的是一个数乘某一行再加到另一行由于消元时用的是一个数乘某一行再加到另一行去的初等变换，此变换不改变行列式的值，所以去的初等变换，此变换不改变行列式的值，所以(1)(2 )()1122kkkkDaaa( )0,1, 2,1iiiaik因()0,0kkkkDa所 以并 且 仅 当所以能实现高斯消去法求

34、解。所以能实现高斯消去法求解。三、高斯消去法使用条件之二三、高斯消去法使用条件之二1、定义：设矩阵、定义：设矩阵A=(aij)n每一行对角元素的绝对每一行对角元素的绝对 值都大于同行其它元素绝对值之和，值都大于同行其它元素绝对值之和，11, 2,niiijjjiaain则称则称A为严格行对角占优矩阵，简称严格对角占优。为严格行对角占优矩阵，简称严格对角占优。例：设矩阵例：设矩阵A=(aij)n为严格对角占优，经过一步为严格对角占优，经过一步 高斯消去得到高斯消去得到(2)1112TaaAA其中其中(2)(2)2222(2)(2)2nnnnaaAaa则则A2也严格对角占优，即也严格对角占优，即(

35、2)(2)2iinijjj iaa证明：由于证明：由于A为严格对角占优矩阵，故为严格对角占优矩阵，故1nijiijj iaa1,2,in经过一步高斯消去得经过一步高斯消去得11(2)11ijijija aaaa,2,3,i jn1(2)122211nnniijijjjjjj ij ij iaaaaa11112211()nniijijijjj iaaaaaa再利用再利用A严格对角占优，由上式可得严格对角占优，由上式可得1(2)1111211()niijiiiijjiaaaaaaa1111iiiiaaaa(2)1111iiiiiia aaaa2,3,in(2)(2)2iinijjj iaa当当A为严格对角占优时，为严格对