研究生翻译学习.pptx

《研究生翻译学习.pptx》由会员分享，可在线阅读，更多相关《研究生翻译学习.pptx（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、研究数值解法的必要性一、研究数值解法的必要性求：求：的解的解 的值，根据克莱姆的值，根据克莱姆(Gramer)(Gramer)法则可法则可表示为两个行列式之比：表示为两个行列式之比：2.0 2.0 概述概述第1页/共97页第2页/共97页如：如：,若用每秒完成万亿次（若用每秒完成万亿次（10101212）浮点乘法运算的计算机（几年）浮点乘法运算的计算机（几年前国内运算速度最快），按每天工作前国内运算速度最快），按每天工作24小时小时,完成这些计算约需完成这些计算约需3030年。若使用一般的年。若使用一般的个人电脑，每秒不外完成十亿次（个人电脑，每秒不外完成十亿次（10109 9）浮点乘法运

2、算，则完成这些计算约需）浮点乘法运算，则完成这些计算约需3 3万年。万年。(天河千万亿次天河千万亿次)计算一个计算一个 阶行列式需要做阶行列式需要做 个乘法，求解上述方程共做个乘法，求解上述方程共做 次乘除法。次乘除法。第3页/共97页二、线性代数方程组的常用解法二、线性代数方程组的常用解法1 1、直接法、直接法：只包含有限次四则运算。若在计算过程中只包含有限次四则运算。若在计算过程中都不发生舍入误差的假定下，计算结果就是原都不发生舍入误差的假定下，计算结果就是原方程组的精确解。方程组的精确解。2 2、迭代法：、迭代法：把方程组的解向量看作是某种极限过程的把方程组的解向量看作是某种极限过程的极

3、限，而且实现这一极限过程每一步的结果是极限，而且实现这一极限过程每一步的结果是把前一步所得的结果施行相同的演算步骤得到把前一步所得的结果施行相同的演算步骤得到的。的。Remark：由于运算过程中舍入误差的存在，实际上直接方法得到的解也由于运算过程中舍入误差的存在，实际上直接方法得到的解也是方程组的近始解。是方程组的近始解。第4页/共97页2.12.1解线性方程组的直接法解线性方程组的直接法设有线性方程组设有线性方程组为非奇异矩阵为非奇异矩阵。或写为矩阵形式或写为矩阵形式 ，其中，其中第5页/共97页一、一、GaussGauss消去法消去法具体过程：具体过程：其中将 改为第6页/共97页Step

4、1Step1：若若 令令 ,用用 乘乘 第一个方程加到第第一个方程加到第 个方程个方程 ，并保留第，并保留第一一式，则得式，则得其中其中记为记为第7页/共97页 若若 令令 ，乘第二个方程加到第乘第二个方程加到第i个方程个方程 ，则得，则得用Step2:Step2:记为记为其中其中第8页/共97页设为设为第第k k-1-1步消元完成后，有步消元完成后，有第9页/共97页Stepk：若 ,令 ,（i=k+1,k+2,)用用-来来乘乘以以第第k-1步步所所得得方方程程中中的的第第k k个个方方程程，加加到到第第i i 个个方方程程，并保留第并保留第k k个方程，则得：个方程，则得：（i=k+1,k

5、+2,n）第10页/共97页按上述做法，做完按上述做法，做完n-1n-1步消元，原方程可化为同解的上三角方程组：步消元，原方程可化为同解的上三角方程组：其中其中(i,j=k+1,(i,j=k+1,n),n)（i=k+1,i=k+1,n,n）上面的方程记为上面的方程记为记为记为第11页/共97页最后，若最后，若 ，逐步回代可得到原方程组的解：，逐步回代可得到原方程组的解：（i=n-1,n-2,2，1）上面的求解过程称为上面的求解过程称为GaussGauss顺序消去法。它通过一系列消元过程与最后的一步回顺序消去法。它通过一系列消元过程与最后的一步回代过程来得到方程组的解。代过程来得到方程组的解。R

6、emark1Remark1：在：在GaussGauss顺序消去法的消去过程中，可以将右端列向量视为方程组顺序消去法的消去过程中，可以将右端列向量视为方程组A A的第的第n n1 1列，直接对矩阵列，直接对矩阵A A（指现在的（指现在的n n行，行，n n1 1列的增广矩阵）进行行初等变换，将其列的增广矩阵）进行行初等变换，将其变换为上三角形矩阵，从而回代求解得到方程组的解。变换为上三角形矩阵，从而回代求解得到方程组的解。第12页/共97页Remark2Remark2：可以统计出，如果可以统计出，如果A A为为n n阶方阵，则阶方阵，则GaussGauss顺序消去法消去过程所需的乘除顺序消去法消

7、去过程所需的乘除运算次数为运算次数为回代过程所需的乘除运算次数为回代过程所需的乘除运算次数为故总的乘除运算次数为故总的乘除运算次数为 取取n n2020，则，则N N30603060，与，与GramerGramer法则相比，是天壤之别。法则相比，是天壤之别。Remark3Remark3：在消去过程中，也可以采用在消去过程中，也可以采用Gauss-JordanGauss-Jordan消去法，将方程组化为对角形方消去法，将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法不需回代过程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法不需回代过程，但总的计算量

8、为程，但总的计算量为n n3 3/2+n/2+n2 2-n/2-n/2，比，比GaussGauss顺序消去法有所增加。顺序消去法有所增加。第13页/共97页Remark4Remark4：在消去过程中，消去过程能够进行的前提条件是在消去过程中，消去过程能够进行的前提条件是 。当。当detA=detA=时方程组存在唯一解，但未必能满足时方程组存在唯一解，但未必能满足 的条件。要使的条件。要使GaussGauss顺序消去法能顺序消去法能够求得方程组的解，应满足如下的定理：够求得方程组的解，应满足如下的定理：定理定理：用高斯顺序消去法能够求解方程组：用高斯顺序消去法能够求解方程组 的解的充要条件为的解

9、的充要条件为A A的的各阶顺序主子式均不为零。各阶顺序主子式均不为零。第14页/共97页算法见教材第算法见教材第2727页：页：（1）消元过程.对k=1,2，n-1进行如下运算：对i=k+1.k+2,n;对j=k+1,n+1,(2)回代过程.按下述公式第15页/共97页 此时高斯顺序消去法能进行下去，但不能求出唯一解。此时高斯顺序消去法能进行下去，但不能求出唯一解。当 detA=0,说明：说明：当当 高斯顺序消去法能进行下去，但当高斯顺序消去法能进行下去，但当 或相对于或相对于（k=1,2,，n)均不为零时均不为零时 （i=k+1,k+2，n）比较小时，计算时产生的舍入误差将导致计算结果）比较

10、小时，计算时产生的舍入误差将导致计算结果误差增大。误差增大。由于舍入误差的原因，由于舍入误差的原因，Gauss顺序消去法不是一个实用的方法，实用中顺序消去法不是一个实用的方法，实用中应该采用选主元的应该采用选主元的Gauss消去法。消去法。第16页/共97页 在在计计算算过过程程中中舍舍入入误误差差增增大大迅迅速速，造造成成计计算算解解与与真真解解相相差差甚甚远远，这这一一方方法法就就是是不不稳稳定定的的方方法法，反反之之，在在计计算算过过程程中中的的舍舍入入误误差差增增大大能能得得到到控控制制，该该方方法法就就是是稳稳定定的的。小小主主元元是是不不稳稳定定的的根根源源，这这就就需需要要采采用

11、用“选选主主元元素素”技技术术，即即选选取取绝绝对对值值最最大大的的元元素素作作为为主主元。元。二、主元素消去法二、主元素消去法第17页/共97页B=1)1)列主元消去法列主元消去法一种常用的方法是列主元消去法。设增广矩阵为一种常用的方法是列主元消去法。设增广矩阵为在第一列中选取绝对值最大的元素在第一列中选取绝对值最大的元素,如若如若 =调换第一行与第调换第一行与第i i行，行，这时的这时的 就是原来的就是原来的 ,再进再进行消去法的第一步，即行消去法的第一步，即第18页/共97页再考虑再考虑 右下角矩阵，选取绝对值最大的元素作为主元素右下角矩阵，选取绝对值最大的元素作为主元素,经过行的对换把

12、主元经过行的对换把主元素移到素移到 ，再按消元公式计算再按消元公式计算 （i,j=3,i,j=3,n n）。）。直至将方程组化成上三角方程组，再进行回代就可求得解。直至将方程组化成上三角方程组，再进行回代就可求得解。然然后后每每一一步步类类似似的的都都在在右右下下角角方方阵阵中中的的第第一一列列中中选选主主元元，再再经经行行对对调调,将将主主元元素素换到右下脚方阵中左上角的位置。再按下一步计算换到右下脚方阵中左上角的位置。再按下一步计算（i,j=kn)第19页/共97页算法见教材第算法见教材第2727页：页：（1）消元过程.对k=1,2，n-1进行如下运算：选主元：找行号ikk,n 使 若为零

13、，终止.交换A(k),b(k)中的第k,ik两行;对i=k+1.k+2,n;令 对j=k+1,n+1,(2)回代过程.按下述公式第20页/共97页2)2)全主元消去法全主元消去法B=列列在在A A中选取绝对值最大的元素作为主元素，如中选取绝对值最大的元素作为主元素，如 ,然后交换然后交换B B 的第一行与第的第一行与第 行，第一行，第一列，这时的列，这时的 就是元素的就是元素的元法的第一步，即元法的第一步，即与第与第 ，然后进行消然后进行消第21页/共97页都换把主元素移到再按消元公式计算（i,j=3,n）,然后每一步对再考虑 右下角矩阵，选取绝对值最大的元素作为主元素,经过行的对换和列的对在

14、右下角方阵中进行完全选主元，经过行的位置,类似的调列对调将主元换到右下角方阵中左上角的位置，再按下一步计算 （i,j=kn）直至将方程组化成上三角方程组，再进行回代就可得解。第22页/共97页RemarkReamrk1Reamrk1：全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的：全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。同一步所选主元的绝对值，因而计算结果更加可靠。Reamrk2Reamrk2：全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了：全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了列交

15、换，从而未知量的次序发生了变化，对编程带来了困难。而列主元消去法的列交换，从而未知量的次序发生了变化，对编程带来了困难。而列主元消去法的计算结果已比较可靠，故实用中常用列主元消去法。计算结果已比较可靠，故实用中常用列主元消去法。Reamrk3Reamrk3：选主元的消去法与：选主元的消去法与GaussGauss顺序消去法的乘除法的计算量是一样的，顺序消去法的乘除法的计算量是一样的，均为均为n n3 3/3+n/3+n2 2-n/3-n/3。第23页/共97页三、选主元素消去法的应用三、选主元素消去法的应用1.1.求解方程组系求解方程组系设系数矩阵设系数矩阵A A可逆，求解方程组系可逆，求解方程

16、组系AXAXb bi i(i=1,2,(i=1,2,m m)。将方程组系的系数矩阵与右端向量写成增广矩阵将方程组系的系数矩阵与右端向量写成增广矩阵 A|bA|b1 1,b,b2 2,b,bm m 按列选主元素后再用按列选主元素后再用Gauss-JordanGauss-Jordan消去法将左边的矩阵消去法将左边的矩阵A A化为单位矩阵，则得到化为单位矩阵，则得到右端的列向量就是方程组系的解向量。右端的列向量就是方程组系的解向量。第24页/共97页2.2.求逆矩阵求逆矩阵在在1 1中令中令m mn n，且右端列向量组成单位阵，则当，且右端列向量组成单位阵，则当A A化为单位阵时，右端矩阵化为单位阵

17、时，右端矩阵即为即为A A的逆矩阵。这是实用中求逆矩阵的可靠方法。的逆矩阵。这是实用中求逆矩阵的可靠方法。3.3.求行列式求行列式若要求矩阵若要求矩阵A A的行列式，可用主元素消去法将其化为上三角阵，对角元素设为的行列式，可用主元素消去法将其化为上三角阵，对角元素设为b b1111，b b2222，b bnnnn，于是，于是A A的行列式为：的行列式为：det(det(A A)=(-1)=(-1)m m b b1111b b2222b bnnnn 其中其中m m为行列交换的次数。这是实用中求行列式的可靠方法。为行列交换的次数。这是实用中求行列式的可靠方法。第25页/共97页四、四、矩阵三角分解

18、法矩阵三角分解法1 1.Gauss.Gauss顺序消去法的矩阵形式顺序消去法的矩阵形式设方程组设方程组A=A=中中A A的各阶顺序主子式均不为零，令的各阶顺序主子式均不为零，令第26页/共97页第27页/共97页则则n-1n-1步消元过程为步消元过程为将上述将上述n-1n-1步消元过程合并，得，步消元过程合并，得，第28页/共97页即（1）由得：容易验证：每个 可逆，且k=1,2,，n-1第29页/共97页令L=则L=又令U=,且U=则A=LU，其中，其中，L为单位下三角矩阵，它的对角元素皆为为单位下三角矩阵，它的对角元素皆为1 1。(三角分解与高斯消去法的关系三角分解与高斯消去法的关系)第3

19、0页/共97页即U为阵，由（1）式，上三角矩 Gauss消消去去法法的的实实质质就就是是用用一一连连串串的的初初等等变变换换把把系系数数方方阵阵A化化成成上上三三角角方方阵阵U，同时把右端向量化，同时把右端向量化 为为 ,若矩阵若矩阵A=LU，则，则LU叫做矩阵叫做矩阵A的的LU分解分解.AX=b即为LUX=b令Y=UX，方程变为LY=b.可先解LY=b，求出Y，再解UX=Y即可第31页/共97页2 2.矩阵的三角分解及条件矩阵的三角分解及条件定定义义1.1.设设A A为为n n阶阶矩矩阵阵（n n 2 2）,称称A=LUA=LU为为矩矩阵阵的的三三角角分分解解，其其中中L L是是下下三三角角

20、矩矩阵阵，U U是上三角矩阵。是上三角矩阵。Remark Remark：三角分解不唯一，可以有不同的形式三角分解不唯一，可以有不同的形式 。为确保唯一性，引入以下定义。为确保唯一性，引入以下定义。定义2.如如果果L L是是单单位位下下三三角角矩矩阵阵，U U是是上上三三角角矩矩阵阵，则则称称三三角角分分解解A=LUA=LU为为DoolittleDoolittle分分解解；如如果果L L是是下下三三角角矩矩阵阵，U U是是单单位位上上三三角角矩矩阵阵，则则称称A=LUA=LU为为CroutCrout分解分解。前面高斯顺序消去法对应了。前面高斯顺序消去法对应了A=LUA=LU的的Doolittle

21、Doolittle分解。（分解。（P32P32定义定义1 1）定定理理1 1：设设A A为为n n阶阶可可逆逆矩矩阵阵，则则A A有有唯唯一一DoolittleDoolittle(or(or CroutCrout)分分解解的的充充要要条条件件为：为：A A的前的前n-1n-1阶顺序主子式不为零。阶顺序主子式不为零。第32页/共97页RemarkRemark：实际中对实际中对A A进行三角分解，不是利用初等变换矩阵，而是直接使用矩阵乘进行三角分解，不是利用初等变换矩阵，而是直接使用矩阵乘法得到。（若不加说明，后面我们讲到的三角分解一律指法得到。（若不加说明，后面我们讲到的三角分解一律指Dooli

22、ttleDoolittle型分解。）型分解。）的求解过程为:可推导求解单位下三角形方程组可推导求解单位下三角形方程组 的递归公式为的递归公式为:求求解解上三角形方程组上三角形方程组 的递归公式为：的递归公式为：第33页/共97页3.直接三角分解法设A=LU即Step1Step1：比较第一行元素：比较第一行元素：比较第一列元素：比较第一列元素：解出解出第34页/共97页Step2Step2：比较第二行元素比较第二行元素：算出：算出：比较第二列的元素：比较第二列的元素：得出得出：一般地，设一般地，设U U的前的前k k-1-1行以及行以及L L的前的前k-1k-1列已求出，则列已求出，则比较第比较

23、第k k行元素行元素StepkStepk：第35页/共97页可以算出可以算出：比较第比较第k k列元素列元素(ik(ik 即行指标即行指标 列指标，为算列指标，为算 ,ik)算出算出:这组公式可用下图记忆（紧凑格式）这组公式可用下图记忆（紧凑格式）:P33第36页/共97页的求解过程为:可推导求解单位下三角形方程组可推导求解单位下三角形方程组 的递归公式为的递归公式为 :求解上三角形方程组求解上三角形方程组 的递归公式为的递归公式为:(P34):第37页/共97页对比计算对比计算 和和 公式，公式，发现计算发现计算 的规律与计算的规律与计算 的规律类似的规律类似,因此计算因此计算 的求方程组的

24、过程可的求方程组的过程可用三角分解的紧凑格式取代。事实上用三角分解的紧凑格式取代。事实上,这只要把这只要把 做为做为A A的第的第n n1 1列进行直列进行直接三角分解即可。接三角分解即可。ReamrkReamrk：上述直接三角分解法所对应的是上述直接三角分解法所对应的是GaussGauss顺序消去法，二者的乘除运算次顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。以保证计算结果的可靠性。第38页/共97页例求解第39页/共97页三角分解法的运算量

25、与高斯消去法大体相当，但对于系数矩阵A不变而常数列b变化的的一类方程组来说，节省运算量因为A=LU不用再分解，对于不同的b直接解LY=b和UX=Y即可第40页/共97页列主元三角分解法主要思想第41页/共97页4.4.平方根法（平方根法（CholeskyCholesky分解）分解）设设A为为n阶阶 对称正定矩阵，对称正定矩阵，L是非奇异下三角矩阵，称是非奇异下三角矩阵，称 为矩阵为矩阵A的的Cholesky分解。分解。n阶 对称正定矩阵A，一定存在如下的分解式 ，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一;，其中L为下三角阵，当限定L的对角元为正时，（Cholesky分解

26、）的分解式唯一。定义：定义：定理：第42页/共97页平方根法平方根法的计算的计算公式公式（为简单起见设（为简单起见设 ，L L为下三角矩阵）为下三角矩阵）令令 我们可以通过矩阵乘法比较来求我们可以通过矩阵乘法比较来求L L的下三角部分元素。具体计算公式如下的下三角部分元素。具体计算公式如下:第43页/共97页P28第44页/共97页Remark1:Remark1:由于在上式分解过程中有由于在上式分解过程中有n n次开方运算，故次开方运算，故C Choledskyholedsky分解法分解法也称为也称为平平方根法方根法。Remark3:可以证明，若用可以证明，若用Gauss顺序消去法求解对称正顺

27、序消去法求解对称正定的方程组定的方程组Axb，则有，则有Remark2:因为 ，这说明放大受到控制，故用平方根法解对称正定的方程组放大受到控制，故用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。时，不必考虑选主元的问题，算法本身数值稳定。的平方不会超过A的最大对角元，因而舍入误差的其中是第是第k步步Gauss顺序消去过程所得元素。这说明顺序消去过程所得元素。这说明用用Gauss顺序消去法求解对称正定方程组也不用选主元。顺序消去法求解对称正定方程组也不用选主元。第45页/共97页Remark4:Remark4:从运算量的角度看，平方根法是有利的。可以统计出，用平方根法求从

28、运算量的角度看，平方根法是有利的。可以统计出，用平方根法求解解AxAxb b所需乘除法的运算次数为：所需乘除法的运算次数为：令有令有n n次开方运算。次开方运算。n n次开方运算一般使用迭代法，所需乘除法的运算次数大约为次开方运算一般使用迭代法，所需乘除法的运算次数大约为n n的常数倍。故平方根法总的乘除法运算次数大约为的常数倍。故平方根法总的乘除法运算次数大约为Remark5Remark5：为避免开方运算，也可对为避免开方运算，也可对A A做做 分解。分解。(其中其中L L为单位下三角为单位下三角阵阵,D,D为对角阵为对角阵)第46页/共97页平方根法举例平方根法举例求解求解解解第47页/共

29、97页先解第48页/共97页4.4.改进的平方根法改进的平方根法 n阶对称矩阵A，一定存在如下的分解式A=LDLT，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一第49页/共97页改进的平方根法改进的平方根法的计算的计算公式公式与P41不同对k=2,3,n,分别计算第50页/共97页改进的平方根法举例改进的平方根法举例求解求解解解第51页/共97页先解第52页/共97页五、解三对角方程组的追赶法五、解三对角方程组的追赶法1.1.矩阵对角占优的概念矩阵对角占优的概念设设类似地，也有类似地，也有按列对角占优按列对角占优和和按列严格对角占优按列严格对角占优的概念。的概念。若对于若对

30、于 ，均有，均有 ,则对称矩阵则对称矩阵A按行严格按行严格对角对角占优占优。若对于若对于 ，不等式，不等式 均成立，且至少均成立，且至少对某个有，则称矩阵A按行对角占优。第53页/共97页2.2.追赶法解三对角方程组追赶法解三对角方程组设设并满足严格对角占优条件并满足严格对角占优条件当当A A严格对角占优时，可以证明各阶顺序主子式非零。严格对角占优时，可以证明各阶顺序主子式非零。第54页/共97页 当当A A为上述三对角阵时，为上述三对角阵时，A A有更特殊的三角分解形式有更特殊的三角分解形式A=L UA=L U 即：即：事实上，比较第事实上，比较第i行的第行的第i1列，立刻可得列，立刻可得U

31、的次上三角线元素为的次上三角线元素为 ，由矩阵相乘，由矩阵相乘可得可得 ，一般地比较第，一般地比较第i行第行第i1列列 ,比较第i行第i列第55页/共97页即即等价于令即由 得第56页/共97页由由 得得Remark：只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为程是稳定的（不必选主元素），其乘除法运算次数为5n5n4 4。上述方法称为解三对。上述方法称为解三对角方程组的角方程组的追赶法追赶法，又称为，又称为ThomasThomas方法。方法。第57页/共97页追赶法举例

32、追赶法举例求解求解解解第58页/共97页第59页/共97页2.2 解线性方程组的迭代法为非奇异矩阵为非奇异矩阵。线性方程组的矩阵形式线性方程组的矩阵形式AX=b,AX=b,若能等价的写成若能等价的写成X=MX+d,X=MX+d,其中其中 第60页/共97页例如，例如，AX=BAX=B两边都加两边都加X X得得X+AX=X+b即X=X-AX+b=IX-AX+b合并右边前两项得X=(I-A)X+b这里与原方程等价第61页/共97页则当则当X(0)=X(1)时时,X(1)就是原方程的解就是原方程的解.若若X(0)X(1)，但当二者差别非常小时，但当二者差别非常小时，例如当例如当可认为可认为X(0)X

33、(1)可将可将X(1)作为近似解作为近似解.否则否则若若X(0)满足满足X(0)=MX(0)+d,则则X(0)就就是原方程是原方程X=MX+d的解的解.若若记记第62页/共97页则当则当X(2)=X(1)时,X(2)就是原方程的解.若X(2)X(1)，但当二者差别非常小时，例如当可认为X(2)X(1)可将X(2)作为近似.否则第63页/共97页则则X X*正是方程组正是方程组X=MX+dX=MX+d的精确解的精确解称称X X(k+1)(k+1)=MX=MX(k)(k)+d+d为迭代公式，为迭代公式，称称M M为迭代矩为迭代矩阵阵.对应的方法为一种迭代法对应的方法为一种迭代法.第64页/共97页

34、一一.雅可比（雅可比（JacobiJacobi）迭代法迭代法(1)(1)迭代格式迭代格式设有设有n n 阶方程组阶方程组其中系数矩阵非奇异，且 ，i=1,2，n将上式变形为将上式变形为第65页/共97页建立迭代格式建立迭代格式上面的迭代式称为上面的迭代式称为雅可比（雅可比（JacobiJacobi）迭代格式）迭代格式。第66页/共97页用矩阵形式来表示方程组的迭代格式用矩阵形式来表示方程组的迭代格式 设设det(A)，且，且则则记记A=D+L+UA=D+L+U 第67页/共97页雅可比迭代式成为：雅可比迭代式成为：令令则得则得举例举例用矩阵形式和分量形式！用矩阵形式和分量形式！称称B B为雅可

35、比迭代矩阵为雅可比迭代矩阵第68页/共97页雅可比雅可比高斯高斯-塞德尔塞德尔迭代格式迭代格式二、高斯-塞德尔（Gauss-Seidel）迭代法第69页/共97页第70页/共97页G-SG-S迭代式成为：迭代式成为：则则令令则得则得记记A=D+L+UA=D+L+U 举例用矩阵形式和分量形式！称称G G为高斯为高斯-赛德尔迭代矩阵赛德尔迭代矩阵第71页/共97页 三、逐次超松弛迭代法三、逐次超松弛迭代法（SORSOR法法-Successive Over Relaxation-Successive Over Relaxation）1.1.迭代公式迭代公式将将G G-S-S迭代格式迭代格式改写为：改

36、写为：并记并记一般地，一般地，残量残量(余量余量)。第72页/共97页这就是这就是逐次超松驰迭代法（逐次超松驰迭代法（SORSOR方法方法)，称为称为松驰松驰因子。因子。SOR方法的计算公式也常写为：方法的计算公式也常写为：Remark：可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。将残量乘以一个修正量加到将残量乘以一个修正量加到 上，作为新的结果上，作为新的结果P56例1第73页/共97页2.3迭代法的收敛性一、向量的一、向量的范数和矩阵的范数和矩阵的范数 定义定义1 1（向量范数）对任意（向量范数）对任意n n维向量维向量XXRn,若按一定规则对应一实数若按一定规则对应一

37、实数|X|，并满足，并满足以下条件：以下条件：正定条件正定条件.即对任意即对任意X Rn,|X|0，只有当X=0时，|X|=0齐次性齐次性.对任意实数对任意实数k k，|kX|=|k|X|（可扩展到复数）三角不等式三角不等式.对任意X，Y Rn,|X+Y|X|+|Y|则称|为向量范数.例如设第74页/共97页分别称为X的1范数，2范数，范数，第75页/共97页 定义2（矩阵范数）若对任意nn矩阵A，按一定规则对应一实数|A|，并满足以下条件：对任意nn矩阵A，|A|0，只有当A=0时，|A|=0对任意实数k，|kA|=|k|A|对任意nn矩阵A，B,|A+B|A|+|B|对任意nn矩阵A，B,

38、|AB|A|B|则称|为矩阵范数.第76页/共97页分别称为X的1范数（列范数），2范（谱范数）数，范数（行范数），Frobenius范数P60例2（纠错）第77页/共97页定义3(P59)若有向量范数|u和矩阵范数|v,使得对任意nn矩阵A和n维向量X都有|AX|u|A|v|X|u 则称向量范数|u与矩阵范数|v是相容的.注意特别当u=v=1,2,，向量范数|u与矩阵范数|v是相容的.第78页/共97页二、迭代法的收敛性二、迭代法的收敛性当 k 时，与下式等价 或 与下式等价当 k 时，或定义4向量序列的极限第79页/共97页迭代矩阵的谱半径迭代矩阵的谱半径(1)(1)收敛的充要条件收敛的充

39、要条件定理定理1 1（P62P62）迭代法迭代法 ，对，对 任意初始向量任意初始向量 都收敛的充要条件是：都收敛的充要条件是：注意雅可比好和G-S迭代法对应的M为B,G定义5（P61）设nn矩阵A的所有特征值为1，2，n，称下式为矩阵A的谱范数第80页/共97页雅可比、高斯-塞德尔迭代法举例：P76：第9,10题 是判定收敛的根本法则(充分必要！)。时，有可能存在某个初始向量 使简 单迭代法收敛。（该向量不好找）RemarkRemark：第81页/共97页(2)(2)收敛的充分条件收敛的充分条件证明：证明：则简单迭代格式关于任意初始向量则简单迭代格式关于任意初始向量 和和 收敛。且收敛。且若若

40、 定理定理2（P62）设迭代公式设迭代公式设是M的任一特征值，X是A的关于的特征向量，则有X=MX，根据范数相容性，有第82页/共97页由于X0得根据的任意性知根据定理1得证第83页/共97页第84页/共97页定理3（P63）若nn矩阵A=aij nn是严格对角占优矩阵，则A为非奇异矩阵.证：用反正法.若|A|=0，则齐次线性方程组AX=0有非零解，设有一非零解为X 第85页/共97页说明|A|0，A是非奇异的第86页/共97页定理4（P64）若线性方程组AX=b的系数矩阵是严格对角占优矩阵，则解此线性方程组的雅可比迭代法收敛.解此线性方程组的高斯-塞德尔迭代法收敛.（按行）,（i=1,2,n

41、）证（1）设A=aijnn，则有第87页/共97页所以雅可比迭代法收敛.由严格对角占优矩阵的定义有（按行）由严格对角占优矩阵的定义有（按行）i=1,2,，n第88页/共97页证证（2 2）：用用反反正正法法.设设G=-(L+D)G=-(L+D)-1-1 U U是是高高斯斯-塞塞德德尔尔迭迭代代矩矩阵阵,设设是是G G的的任一特征值，假设任一特征值，假设11，则有，则有第89页/共97页第90页/共97页即(L+D)+U严格对角占优，根据定理3得矛盾第91页/共97页因此高斯-塞德尔迭代法对任意初始向量收敛。证毕注意：由此还可得到求高斯-塞德尔迭代矩阵G的特征值的一个简便方法P76作业题7,9,

42、10第92页/共97页定理5（P65）若线性方程组AX=b的系数矩阵A为正定矩阵，则解此线性方程组的高斯-塞德尔迭代法收敛（证明从略）第93页/共97页2.SOR2.SOR方法的收敛性方法的收敛性（1 1）SORSOR方法收敛的必要条件是方法收敛的必要条件是0 0 2 2（定理（定理6 6）当当 1 1时，时，SORSOR方法就是方法就是SeidelSeidel迭代格式。当迭代格式。当00 111时，称为超松弛方法。适当选取松弛因子时，称为超松弛方法。适当选取松弛因子 的值，可以得到比的值，可以得到比G-SG-S方法更快的收方法更快的收敛格式。敛格式。关于方法的收敛性有以下结论关于方法的收敛性

43、有以下结论：（2 2）若系数矩阵）若系数矩阵A A 对称正定，且对称正定，且0 0 22，则，则SORSOR方法收敛（定理方法收敛（定理7.P667.P66）。）。（3 3）若系数矩阵）若系数矩阵A A 严格对角占优，且严格对角占优，且00 1 1，则，则SORSOR方法收敛（方法收敛（教材中为介绍教材中为介绍此结论此结论）。）。第94页/共97页RemarkRemark：能使：能使SORSOR方法收敛最快的松弛因子叫做最佳松弛因子，记为方法收敛最快的松弛因子叫做最佳松弛因子，记为 optopt。对某些特殊类型的矩阵，可以建立对某些特殊类型的矩阵，可以建立SORSOR方法最佳松弛因子理论。例如

44、，对于具方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优等性质的矩阵有对称正定，或严格对角占优等性质的矩阵A A的线性方程组，可以建立最佳松弛因的线性方程组，可以建立最佳松弛因子子 其中其中(J J)为解为解AxAxb b的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定 optopt并不容易，实际计算时一般都是根据试算的情况确定并不容易，实际计算时一般都是根据试算的情况确定 optopt的一个近似值。的一个近似值。第95页/共97页3.3.如果如果 ,则用此判断法比用则用此判断法比用 方便。方便。RemarkRemark：使用迭代法求解线代数：使用迭代法求解线代数方程组需注意的问题方程组需注意的问题1.1.迭代法的收敛性与初始向量的选取无关。但初始迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。向量的选取对迭代的工作量有重大影响。2.2.在使用实用误差估计式在使用实用误差估计式 停止迭代时，停止迭代时，要选的恰当。要选的恰当。4.4.对某些方程组，有时可适当作些变形，以使得迭代法收敛（交换方程或变元对某些方程组，有时可适当作些变形，以使得迭代法收敛（交换方程或变元的次序）。的次序）。第96页/共97页感谢您的观看！第97页/共97页