研究生翻译第2讲.ppt

《研究生翻译第2讲.ppt》由会员分享，可在线阅读，更多相关《研究生翻译第2讲.ppt（97页珍藏版）》请在三一文库上搜索。

1、第二章 线性代数方程组的解法,2.1 解线性方程组的直接法,2.2 解线性方程组的迭代法,2.0 概述,2.2 迭代法的收敛性,一、研究数值解法的必要性,求：,的解 的值，根据克莱姆(Gramer)法则可 表示为两个行列式之比：,2.0 概述,如： ,若用每秒完成万亿次（1012）浮点乘法运算的计算机（几年前国内运算速度最快），按每天工作24小时,完成这些计算约需30年。若使用一般的个人电脑，每秒不外完成十亿次（109）浮点乘法运算，则完成这些计算约需3万年。(天河千万亿次),计算一个 阶行列式需要做 个乘法，求解上述方程共做 次乘除法。,二、线性代数方程组的常用解法,1、直接法： 只包含有限

2、次四则运算。若在计算过程中都不发生舍入误差的假定下，计算结果就是原方程组的精确解。,2、迭代法： 把方程组的解向量看作是某种极限过程的极限，而且实现这一极限过程每一步的结果是把前一步所得的结果施行相同的演算步骤得到的。,Remark：由于运算过程中舍入误差的存在，实际上直接方法得到的解也是方程组的近始解。,2.1解线性方程组的直接法,设有线性方程组,为非奇异矩阵。,或写为矩阵形式 ，其中,一、Gauss消去法,具体过程：,其中,将 改为,Step1：,若 令 ,用 乘 第一个方程加到第 个方程 ，并保留第一式，则得,其中,记为,记为,其中,设为,第k-1步消元完成后，有,按上述做法，做完n-1

3、步消元，原方程可化为同解的上三角方程组：,其中,(i,j=k+1,n),（i=k+1,n）,上面的方程记为,记为,最后，若 ，逐步回代可得到原方程组的解：,（i=n-1,n-2,2，1）,上面的求解过程称为Gauss顺序消去法。它通过一系列消元过程与最后的一步回代过程来得到方程组的解。,Remark1：在Gauss顺序消去法的消去过程中，可以将右端列向量视为方程组A的第n1列，直接对矩阵A（指现在的n行，n1列的增广矩阵）进行行初等变换，将其变换为上三角形矩阵，从而回代求解得到方程组的解。,Remark2：可以统计出，如果A为n阶方阵，则Gauss顺序消去法消去过程所需的乘除运算次数为,回代过

4、程所需的乘除运算次数为,故总的乘除运算次数为,取n20，则N3060，与Gramer法则相比，是天壤之别。,Remark3：在消去过程中，也可以采用Gauss-Jordan消去法，将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法不需回代过程，但总的计算量为n3/2+n2-n/2，比Gauss顺序消去法有所增加。,Remark4：在消去过程中，消去过程能够进行的前提条件是 。当detA= 时方程组存在唯一解，但未必能满足 的条件。要使Gauss顺序消去法能够求得方程组的解，应满足如下的定理：,定理：用高斯顺序消去法能够求解方程组 的解的充要条件为A的各阶顺序主子

5、式均不为零。,算法见教材第27页：,（1）消元过程.对k=1,2，n-1进行如下运算： 对i=k+1.k+2,n; 对j=k+1,n+1, (2) 回代过程.按下述公式,由于舍入误差的原因，Gauss顺序消去法不是一个实用的方法，实用中应该采用选主元的Gauss消去法。,在计算过程中舍入误差增大迅速，造成计算解与真解相差甚远，这一方法就是不稳定的方法，反之，在计算过程中的舍入误差增大能得到控制，该方法就是稳定的。小主元是不稳定的根源，这就需要采用“选主元素”技术，即选取绝对值最大的元素作为主元。,二、主元素消去法,B=,1)列主元消去法,一种常用的方法是列主元消去法。设增广矩阵为,再考虑 右下

6、角矩阵，选取绝对值最大的元素作为主元素,经过行的对换把主元素移到 ，,再按消元公式计算 （i,j=3,n）。,直至将方程组化成上三角方程组，再进行回代就可求得解。,算法见教材第27页：,（1）消元过程.对k=1,2，n-1进行如下运算： 选主元：找行号ikk,n 使 若为零，终止. 交换A(k),b(k)中的第k,ik两行; 对i=k+1.k+2,n;令 对j=k+1,n+1, (2) 回代过程.按下述公式,2)全主元消去法,B=,Remark,Reamrk1：全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。,Reamrk2：全主元消去法

7、每一步选主元要花费更多的机时，并且对增广矩阵做了列交换，从而未知量的次序发生了变化，对编程带来了困难。而列主元消去法的计算结果已比较可靠，故实用中常用列主元消去法。,Reamrk3：选主元的消去法与Gauss顺序消去法的乘除法的计算量是一样的，均为n3/3+n2-n/3。,三、选主元素消去法的应用,1.求解方程组系,设系数矩阵A可逆，求解方程组系AXbi(i=1,2,m)。,将方程组系的系数矩阵与右端向量写成增广矩阵,A|b1,b2,bm,按列选主元素后再用Gauss-Jordan消去法将左边的矩阵A化为单位矩阵，则得到,右端的列向量就是方程组系的解向量。,2.求逆矩阵,在1中令mn，且右端列

8、向量组成单位阵，则当A化为单位阵时，右端矩阵即为A的逆矩阵。这是实用中求逆矩阵的可靠方法。,3.求行列式,若要求矩阵A的行列式，可用主元素消去法将其化为上三角阵，对角元素设为b11，b22，bnn，于是A的行列式为：,det(A)=(-1)m b11b22bnn,其中m为行列交换的次数。这是实用中求行列式的可靠方法。,四、矩阵三角分解法,1.Gauss顺序消去法的矩阵形式,设方程组A = 中A的各阶顺序主子式均不为零，令,则n-1步消元过程为,将上述n-1步消元过程合并，得，,即,（1）,令L=,则 L=,其中，L为单位下三角矩阵，它的对角元素皆为1。 (三角分解与高斯消去法的关系),即,AX

9、=b即为LUX=b 令Y=UX，方程变为LY=b. 可先解LY=b，求出Y，再解UX=Y即可,2 .矩阵的三角分解及条件,定义1.设A为n阶矩阵（n 2）,称A=LU为矩阵的三角分解，其中L是下三角矩阵，U是上三角矩阵。,Remark：三角分解不唯一，可以有不同的形式 。为确保唯一性，引入以下定义。,定义2.如果L是单位下三角矩阵，U是上三角矩阵，则称三角分解A=LU为Doolittle分解；如果L是下三角矩阵，U是单位上三角矩阵，则称A=LU为Crout分解。前面高斯顺序消去法对应了A=LU的Doolittle分解。（P32定义1）,定理1：设A为n阶可逆矩阵，则A有唯一Doolittle(

10、or Crout)分解的充要条件为：A的前n-1阶顺序主子式不为零。,Remark：实际中对A进行三角分解，不是利用初等变换矩阵，而是直接使用矩阵乘法得到。（若不加说明，后面我们讲到的三角分解一律指Doolittle型分解。）,的求解过程为:,可推导求解单位下三角形方程组 的递归公式为 :,求解上三角形方程组 的递归公式为：,3.直接三角分解法,设A=LU 即,Step1：,比较第一行元素：,Step2：,比较第二行元素：,算出：,比较第二列的元素：,得出：,一般地，设U的前k-1行以及L的前k-1列已求出，则,比较第k行元素,Stepk：,可以算出：,算出:,这组公式可用下图记忆（紧凑格式）

11、:,P33,的求解过程为:,可推导求解单位下三角形方程组 的递归公式为 :,求解上三角形方程组 的递归公式为:,(P34):,对比计算 和 公式，,发现计算 的规律与计算 的规律类似,因此计算 的求方程组的过程可用三角分解的紧凑格式取代。事实上,这只要把 做为A的第n1列进行直接三角分解即可。,Reamrk：上述直接三角分解法所对应的是Gauss顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。,例求解,三角分解法的运算量与高斯消去法大体相当，但对于系数矩阵A不变而常数列b变化的的一类方程组来说，节省运算量 因为A=LU

12、不用再分解，对于不同的b 直接解LY=b和UX=Y即可,列主元三角分解法主要思想,4.平方根法（Cholesky分解）,设A为n阶 对称正定矩阵，L是非奇异下三角矩阵，称 为矩阵A的Cholesky分解。,n阶 对称正定矩阵A，一定存在如下的分解式 ，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一; ，其中L为下三角阵，当限定L的对角元为正时， （Cholesky分解）的分解式唯一。,定义：,定理：,平方根法的计算公式 （为简单起见设 ，L为下三角矩阵）,令,我们可以通过矩阵乘法比较来求L的下三角部分元素。具体计算公式如下:,P28,Remark1:由于在上式分解过程中有n次

13、开方运算，故Choledsky分解法也称为平方根法。,Remark3:可以证明，若用Gauss顺序消去法求解对称正 定的方程组Axb，则有,用Gauss顺序消去法求解对称正定方程组也不用选主元。,Remark4:从运算量的角度看，平方根法是有利的。可以统计出，用平方根法求解Axb所需乘除法的运算次数为：,令有n次开方运算。 n次开方运算一般使用迭代法，所需乘除法的运算次数大约为n的常数倍。故平方根法总的乘除法运算次数大约为,Remark5：为避免开方运算，也可对A做 分解。(其中L为单位下三角阵,D为对角阵),平方根法举例,求解,解,先解,4.改进的平方根法,n阶 对称矩阵A，一定存在如下的分

14、解式 A=LDLT，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一,改进的平方根法的计算公式,与P41不同,对k=2,3,n,分别计算,改进的平方根法举例,求解,解,先解,五、解三对角方程组的追赶法,1.矩阵对角占优的概念,设,类似地，也有按列对角占优和按列严格对角占优的概念。,若对于 ，均有 ,则对称矩阵A按行严格对角占优。,2.追赶法解三对角方程组,设,并满足严格对角占优条件,当A严格对角占优时，可以证明各阶顺序主子式非零。,即,等价于,令 即,由 得,由 得,Remark：只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法

15、运算次数为5n4。上述方法称为解三对角方程组的追赶法，又称为Thomas方法。,追赶法举例,求解,解,2.2 解线性方程组的迭代法,为非奇异矩阵。,线性方程组的矩阵形式AX=b,若能等价的写成 X=MX+d,其中,例如，AX=B两边都加X得,X+AX=X+b即X=X-AX+b=IX-AX+b 合并右边前两项得X=(I-A)X+b 这里,与原方程等价,则当X(0)=X(1)时, X(1)就是原方程的解. 若X(0)X(1) ，但当二者差别非常小时，例如当 可认为X(0)X(1)可将X(1)作为近似解.否则,若X(0)满足X(0)=MX(0)+d,则X(0)就是原方程X=MX+d的解.若记,则当X

16、(2)=X(1)时, X(2)就是原方程的解. 若X(2)X(1) ，但当二者差别非常小时，例如当 可认为X(2)X(1)可将X(2)作为近似.否则,则X*正是方程组X=MX+d的精确解 称X(k+1)=MX(k)+d为迭代公式， 称M为迭代矩阵.对应的方法为一种迭代法.,一.雅可比（Jacobi）迭代法,(1)迭代格式,设有n 阶方程组,其中系数矩阵非奇异，且 ，i=1,2，n,将上式变形为,建立迭代格式,上面的迭代式称为雅可比（Jacobi）迭代格式。,用矩阵形式来表示方程组的迭代格式,设det(A) ，且,则,记A=D+L+U,雅可比迭代式成为：,令,则得,举例用矩阵形式和分量形式！,称

17、B为雅可比迭代矩阵,雅可比,高斯-塞德尔 迭代格式,二、高斯-塞德尔（Gauss-Seidel）迭代法,G-S迭代式成为：,则,令,则得,记A=D+L+U,举例用矩阵形式和分量形式！,称G为高斯-赛德尔迭代矩阵,三、逐次超松弛迭代法 （SOR法-Successive Over Relaxation）,1.迭代公式,将G-S迭代格式,改写为：,并记,一般地，残量(余量) 。,这就是逐次超松驰迭代法（SOR方法)， 称为松驰 因子。,SOR方法的计算公式也常写为：,Remark：可见，SOR方法的得到的 可以看成是G-S方法的结果与 的加权平均。,将残量乘以一个修正量加到 上，作为新的结果,P56

18、例1,2.3迭代法的收敛性,一、向量的范数和矩阵的范数 定义1 （向量范数）对任意n维向量XRn,若按一定规则对应一实数|X| ，并满足以下条件： 正定条件.即对任意XRn, |X|0，只有当X=0时， |X|=0 齐次性.对任意实数k， |kX|= |k| |X| （可扩展到复数） 三角不等式.对任意X，YRn, |X+Y| |X|+ |Y| 则称| 为向量范数. 例如设,分别称为X的1范数， 2范数， 范数，,定义2 （矩阵范数）若对任意nn矩阵A，按一定规则对应一实数|A| ，并满足以下条件： 对任意nn矩阵A， |A|0，只有当A=0时， |A|=0 对任意实数k， |kA|= |k|

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

20、1) 收敛的充要条件,定理1（P62）迭代法 ， ，对 任意初始向量 都收敛的充要条件是：,注意 雅可比好和G-S迭代法对应的M为B,G,定义 5（P61）设nn矩阵A的所有特征值为1， 2， n，称下式为矩阵A的谱范数,雅可比、高斯-塞德尔迭代法举例：,P76：第9,10题, 是判定收敛的根本法则(充分必要！)。,时，有可能存在某个初始向量 使简 单迭代法收敛。（该向量不好找）,Remark：,(2)收敛的充分条件,证明：,设是M的任一特征值，X是A的关于的特征向量，则有X=MX，根据范数相容性，有,由于X0得,根据的任意性知,根据定理1得证,定理3（P63） 若nn矩阵A=aij nn是严

21、格对角占优矩阵，则A为非奇异矩阵. 证：用反正法.若|A|=0，则齐次线性方程组AX=0有非零解，设有一非零解为X,说明|A|0，A是非奇异的,定理4（P64）若线性方程组AX=b的系数矩阵是严格对角占优矩阵，则解此线性方程组的雅可比迭代法收敛.解此线性方程组的高斯-塞德尔迭代法收敛.,证（1）设A=aijnn，则有,所以雅可比迭代法收敛.,由严格对角占优矩阵的定义有（按行）,i=1,2,，n,证（2）：用反正法.设G=-(L+D)-1 U是高斯-塞德尔迭代矩阵,设是G的任一特征值，假设 1，则有,即(L+D)+U严格对角占优，根据定理3得,矛盾,因此高斯-塞德尔迭代法对任意初始向量收敛。,证

22、毕,注意：由此还可得到求高斯-塞德尔迭代矩阵G的特征值的一个简便方法 P76作业题7,9,10,定理5（P65）若线性方程组AX=b的系数矩阵A为正定矩阵，则解此线性方程组的高斯-塞德尔迭代法收敛 （证明从略）,2.SOR方法的收敛性,（1） SOR方法收敛的必要条件是0 2（定理6）,当1时，SOR方法就是Seidel迭代格式。当01时，称为超松弛方法。适当选取松弛因子的值，可以得到比G-S方法更快的收敛格式。,关于方法的收敛性有以下结论：,（2）若系数矩阵A 对称正定，且0 2，则SOR方法收敛（定理7.P66）。,（3）若系数矩阵A 严格对角占优，且01，则SOR方法收敛（教材中为介绍此

23、结论）。,Remark：能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为opt。 对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优等性质的矩阵A的线性方程组，可以建立最佳松弛因子 其中(J)为解Axb的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定opt并不容易，实际计算时一般都是根据试算的情况确定opt的一个近似值。,3.如果 ,则用此判断法比用 方便。,Remark：使用迭代法求解线代数 方程组需注意的问题,1.迭代法的收敛性与初始向量的选取无关。但初始,向量的选取对迭代的工作量有重大影响。,4.对某些方程组，有时可适当作些变形，以使得迭代法收敛（交换方程或变元的次序）。,