西安石油大学现代数值计算方法第2章.ppt

第二章线性代数方程组的解法,2.1解线性方程组的直接法,2.2解线性方程组的迭代法,2.0概述,2.2迭代法的收敛性,一、研究数值解法的必要性,求,的解的值，根据克莱姆Gramer法则可表示为两个行列式之比,2.0概述,,如,若用每秒完成万亿次（1012）浮点乘法运算的计算机（几年前国内运算速度最快），按每天工作24小时,完成这些计算约需30年。若使用一般的个人电脑，每秒不外完成十亿次（109）浮点乘法运算，则完成这些计算约需3万年。天河千万亿次,计算一个阶行列式需要做个乘法，求解上述方程共做次乘除法。,二、线性代数方程组的常用解法,1、直接法只包含有限次四则运算。若在计算过程中都不发生舍入误差的假定下，计算结果就是原方程组的精确解。,2、迭代法把方程组的解向量看作是某种极限过程的极限，而且实现这一极限过程每一步的结果是把前一步所得的结果施行相同的演算步骤得到的。,Remark由于运算过程中舍入误差的存在，实际上直接方法得到的解也是方程组的近始解。,2.1解线性方程组的直接法,设有线性方程组,为非奇异矩阵。,或写为矩阵形式，其中,复习矩阵相乘,一、Gauss消去法,具体过程,其中,将改为,Step1,若令,用乘第一个方程加到第个方程，并保留第一式，则得,其中,记为,记为,其中,设为,第k-1步消元完成后，有,按上述做法，做完n-1步消元，原方程可化为同解的上三角方程组,其中,i,jk1,,n,（ik1,,n）,上面的方程记为,记为,最后，若，逐步回代可得到原方程组的解,（in-1,n-2,2，1）,上面的求解过程称为Gauss顺序消去法。它通过一系列消元过程与最后的一步回代过程来得到方程组的解。,Remark1在Gauss顺序消去法的消去过程中，可以将右端列向量视为方程组A的第n＋1列，直接对矩阵A（指现在的n行，n＋1列的增广矩阵）进行行初等变换，将其变换为上三角形矩阵，从而回代求解得到方程组的解。,Remark2可以统计出，如果A为n阶方阵，则Gauss顺序消去法消去过程所需的乘除运算次数为,回代过程所需的乘除运算次数为,故总的乘除运算次数为,取n＝20，则N＝3060，与Gramer法则相比，是天壤之别。,Remark3在消去过程中，也可以采用Gauss-Jordan消去法，将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法不需回代过程，但总的计算量为n3/2n2-n/2，比Gauss顺序消去法有所增加。,Remark4在消去过程中，消去过程能够进行的前提条件是。当detA时方程组存在唯一解，但未必能满足的条件。要使Gauss顺序消去法能够求得方程组的解，应满足如下的定理,定理用高斯顺序消去法能够求解方程组的解的充要条件为A的各阶顺序主子式均不为零。,算法见教材第27页,（1）消元过程.对k1,2，n-1进行如下运算对ik1.k2,,n;对jk1,,n1,2回代过程.按下述公式,③由于舍入误差的原因，Gauss顺序消去法不是一个实用的方法，实用中应该采用选主元的Gauss消去法。,在计算过程中舍入误差增大迅速，造成计算解与真解相差甚远，这一方法就是不稳定的方法，反之，在计算过程中的舍入误差增大能得到控制，该方法就是稳定的。小主元是不稳定的根源，这就需要采用“选主元素”技术，即选取绝对值最大的元素作为主元。,二、主元素消去法,B,1列主元消去法,一种常用的方法是列主元消去法。设增广矩阵为,再考虑右下角矩阵，选取绝对值最大的元素作为主元素,经过行的对换把主元素移到，,再按消元公式计算（i,j3,n）。,直至将方程组化成上三角方程组，再进行回代就可求得解。,算法见教材第27页,（1）消元过程.对k1,2，n-1进行如下运算①选主元找行号ik∈{k,,n}使若为零，终止.②交换[Ak,bk]中的第k,ik两行;③对ik1.k2,,n;令对jk1,,n1,2回代过程.按下述公式,2全主元消去法,B,Remark,Reamrk1全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。,Reamrk2全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了列交换，从而未知量的次序发生了变化，对编程带来了困难。而列主元消去法的计算结果已比较可靠，故实用中常用列主元消去法。,Reamrk3选主元的消去法与Gauss顺序消去法的乘除法的计算量是一样的，均为n3/3n2-n/3。,三、选主元素消去法的应用,1.求解方程组系,设系数矩阵A可逆，求解方程组系AX＝bii1,2,,m。,将方程组系的系数矩阵与右端向量写成增广矩阵,[A|b1,b2,,bm],按列选主元素后再用Gauss-Jordan消去法将左边的矩阵A化为单位矩阵，则得到,右端的列向量就是方程组系的解向量。,2.求逆矩阵,在1中令m＝n，且右端列向量组成单位阵，则当A化为单位阵时，右端矩阵即为A的逆矩阵。这是实用中求逆矩阵的可靠方法。,3.求行列式,若要求矩阵A的行列式，可用主元素消去法将其化为上三角阵，对角元素设为b11，b22，，bnn，于是A的行列式为,detA-1mb11b22bnn,其中m为行列交换的次数。这是实用中求行列式的可靠方法。,四、矩阵三角分解法,1.Gauss顺序消去法的矩阵形式,设方程组A中A的各阶顺序主子式均不为零，令,则n-1步消元过程为,将上述n-1步消元过程合并，得，,即,（1）,令L,则L,其中，L为单位下三角矩阵，它的对角元素皆为1。三角分解与高斯消去法的关系,AXb即为LUXb令YUX，方程变为LYb.可先解LYb，求出Y，再解UXY即可,2.矩阵的三角分解及条件,定义1.设A为n阶矩阵（n2）,称ALU为矩阵的三角分解，其中L是下三角矩阵，U是上三角矩阵。,Remark三角分解不唯一，可以有不同的形式。为确保唯一性，引入以下定义。,定义2.如果L是单位下三角矩阵，U是上三角矩阵，则称三角分解ALU为Doolittle分解；如果L是下三角矩阵，U是单位上三角矩阵，则称ALU为Crout分解。前面高斯顺序消去法对应了ALU的Doolittle分解。（P32定义1）,定理1设A为n阶可逆矩阵，则A有唯一DoolittleorCrout分解的充要条件为A的前n-1阶顺序主子式不为零。,Remark实际中对A进行三角分解，不是利用初等变换矩阵，而是直接使用矩阵乘法得到。（若不加说明，后面我们讲到的三角分解一律指Doolittle型分解。）,的求解过程为,可推导求解单位下三角形方程组的递归公式为,求解上三角形方程组的递归公式为,3.直接三角分解法,设ALU即,Step1,比较第一行元素,Step2,比较第二行元素,算出,比较第二列的元素,得出,一般地，设U的前k-1行以及L的前k-1列已求出，则,比较第k行元素,Stepk,可以算出,算出,这组公式可用下图记忆（紧凑格式）,P33,的求解过程为,可推导求解单位下三角形方程组的递归公式为,求解上三角形方程组的递归公式为,P34,对比计算和公式，,发现计算的规律与计算的规律类似,因此计算的求方程组的过程可用三角分解的紧凑格式取代。事实上,这只要把做为A的第n＋1列进行直接三角分解即可。,Reamrk上述直接三角分解法所对应的是Gauss顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。,例求解,,三角分解法的运算量与高斯消去法大体相当，但对于系数矩阵A不变而常数列b变化的的一类方程组来说，节省运算量因为ALU不用再分解，对于不同的b直接解LYb和UXY即可,列主元三角分解法主要思想,4.平方根法（Cholesky分解）,设A为n阶对称正定矩阵，L是非奇异下三角矩阵，称为矩阵A的乔列斯基Cholesky分解。,n阶对称正定矩阵A，一定存在如下的分解式，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一;，其中L为下三角阵，当限定L的对角元为正时，（Cholesky分解）的分解式唯一。,定义,定理,平方根法的计算公式（为简单起见设，L为下三角矩阵）,令,我们可以通过矩阵乘法比较来求L的下三角部分元素。具体计算公式如下,P28,Remark1由于在上式分解过程中有n次开方运算，故Choledsky分解法也称为平方根法。,Remark3可以证明，若用Gauss顺序消去法求解对称正定的方程组Ax＝b，则有,用Gauss顺序消去法求解对称正定方程组也不用选主元。,Remark4从运算量的角度看，平方根法是有利的。可以统计出，用平方根法求解Ax＝b所需乘除法的运算次数为,令有n次开方运算。n次开方运算一般使用迭代法，所需乘除法的运算次数大约为n的常数倍。故平方根法总的乘除法运算次数大约为,Remark5为避免开方运算，也可对A做分解。其中L为单位下三角阵,D为对角阵,平方根法举例,求解,解,,先解,4.改进的平方根法,n阶对称矩阵A，一定存在如下的分解式ALDLT，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一,改进的平方根法的计算公式,与P41不同,对k2,3,,n,分别计算,,改进的平方根法举例,求解,解,先解,五、解三对角方程组的追赶法,1.矩阵对角占优的概念,设,类似地，也有按列对角占优和按列严格对角占优的概念。,若对于，均有,则对称矩阵A按行严格对角占优。,2.追赶法解三对角方程组,设,并满足严格对角占优条件,当A严格对角占优时，可以证明各阶顺序主子式非零。第3节一般情况会证明n阶，可推广到任任意阶,即,等价于,令即,由得,由得,Remark只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为5n－4。上述方法称为解三对角方程组的追赶法，又称为Thomas方法。,追赶法举例,求解,解,,2.2解线性方程组的迭代法,为非奇异矩阵。,线性方程组的矩阵形式AXb,若能等价的写成XMXd,其中,,例如，AXB两边都加X得,XAXXb即XX-AXbIXAXb合并右边前两项得XI-AXb这里,,,与原方程等价,则当X0X1时,X1就是原方程的解.若X0≠X1，但当二者差别非常小时，例如当可认为X0≈X1可将X1作为近似解.否则,若X0满足X0MX0d,则X0就是原方程XMXd的解.若记,则当X2X1时,X2就是原方程的解.若X2≠X1，但当二者差别非常小时，例如当可认为X2≈X1可将X2作为近似.否则,则X*正是方程组XMXd的精确解称Xk1MXkd为迭代公式，称M为迭代矩阵.对应的方法为一种迭代法.,一.雅可比（Jacobi）迭代法,1迭代格式,设有n阶方程组,其中系数矩阵非奇异，且，i1,2，，n,将上式变形为,建立迭代格式,上面的迭代式称为雅可比（Jacobi）迭代格式。,用矩阵形式来表示方程组的迭代格式,设detA，且,则,记ADLU,雅可比迭代式成为,令,则得,举例用矩阵形式和分量形式,称B为雅可比迭代矩阵,雅可比,高斯-塞德尔迭代格式,二、高斯-塞德尔（Gauss-Seidel）迭代法,G-S迭代式成为,则,令,则得,记ADLU,举例用矩阵形式和分量形式,称G为高斯-赛德尔迭代矩阵,三、逐次超松弛迭代法（SOR法-SuccessiveOverRelaxation）,1.迭代公式,将G-S迭代格式,改写为,并记,一般地，残量余量。,这就是逐次超松驰迭代法（SOR方法，称为松驰因子。,SOR方法的计算公式也常写为,Remark可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。,将残量乘以一个修正量加到上，作为新的结果,P56例1,2.3迭代法的收敛性,一、向量的范数和矩阵的范数定义1（向量范数）对任意n维向量X∈Rn,若按一定规则对应一实数||X||，并满足以下条件①正定条件.即对任意X∈Rn,||X||≥0，只有当X0时，||X||0②齐次性.对任意实数k，||kX|||k|||X||（可扩展到复数）③三角不等式.对任意X，Y∈Rn,||XY||≤||X||||Y||则称||||为向量范数.例如设,分别称为X的1范数，2范数，∞范数，,定义2（矩阵范数）若对任意nn矩阵A，按一定规则对应一实数||A||，并满足以下条件①对任意nn矩阵A，||A||≥0，只有当A0时，||A||0②对任意实数k，||kA|||k|||A||③对任意nn矩阵A，B,||AB||≤||A||||B||④对任意nn矩阵A，B,||AB||≤||A||||B||则称||||为矩阵范数.,分别称为A的1范数（列范数），2范数（谱范数），∞范数（行范数），Frobenius范数P60例2（纠错）,设A是nn实矩阵，则ATA的任一特征值非负。记BATA，设λ是B的特征值，X是B的关于λ的特征向量，则,上式左、右分别左乘XT,所以λ≥0,定义3P59若有向量范数||||u和矩阵范数||||v,使得对任意nn矩阵A和n维向量X都有||AX||u≤||A||v||X||u则称向量范数||||u与矩阵范数||||v是相容的.注意特别当uv1,2,∞，向量范数||||u与矩阵范数||||v是相容的.,二、迭代法的收敛性,当k时，,与下式等价,或,与下式等价,当k时，,或,定义4向量序列的极限,迭代矩阵的谱半径,1收敛的充要条件,定理1（P62）迭代法，，对任意初始向量都收敛的充要条件是,注意雅可比和G-S迭代法对应的M为B,G,定义5（P61）设nn矩阵A的所有特征值为λ1，λ2，，λn，称下式为矩阵A的谱半径,雅可比、高斯-塞德尔迭代法举例,P76第9,10题,①是判定收敛的根本法则充分必要。,时，有可能存在某个初始向量使简单迭代法收敛。（该向量不好找）,Remark,2收敛的充分条件,证明,设λ是M的任一特征值，X是M的关于λ的特征向量，则有λXMX，根据范数相容性，有,由于X≠0得,根据λ的任意性知,根据定理1得证,定理3（P63）若nn矩阵A[aij]nn是严格对角占优矩阵，则A为非奇异矩阵.证用反正法.若|A|0，则齐次线性方程组AX0有非零解，设有一非零解为X,,说明|A|≠0，A是非奇异的,定理4（P64）若线性方程组AXb的系数矩阵是严格对角占优矩阵，则①解此线性方程组的雅可比迭代法收敛.②解此线性方程组的高斯-塞德尔迭代法收敛.,证（1）设A[aij]nn，则有,所以雅可比迭代法收敛.,由严格对角占优矩阵的定义有（按行）,i1,2,，n,证（2）用反正法.设G-LD-1U是高斯-塞德尔迭代矩阵,设λ是G的任一特征值，则有,假设|λ|≥1，,即λLDU严格对角占优，根据定理3得,矛盾,因此高斯-塞德尔迭代法对任意初始向量收敛。,证毕,注意由此还可得到求高斯-塞德尔迭代矩阵G的特征值的一个简便方法，λ是G的特征值的充要条件是,类似地推导求雅可比迭代矩阵特征值的简便方法,举例分别判别雅可比和G-S迭代法的收敛性,解令,所以，对有些初始解用雅可比迭代法发散。,判别G-S迭代法的收敛性,解令,所以，用高斯-塞德尔迭代法收敛。,见P76习题6,7,9,定理5（P65）若线性方程组AXb的系数矩阵A为正定矩阵，则解此线性方程组的高斯-塞德尔迭代法收敛（证明从略）见下例,解系数矩阵A是实对称矩阵,系数矩阵是正定矩阵。所以，用高斯-塞德尔迭代法收敛。,判别解下面方程组的高斯-塞德尔迭代法的收敛性,2.SOR方法的收敛性,（1）SOR方法收敛的必要条件是0ω2（定理6）,当＝1时，SOR方法就是Seidel迭代格式。当01时，称为超松弛方法。适当选取松弛因子的值，可以得到比G-S方法更快的收敛格式。,关于方法的收敛性有以下结论,（2）若系数矩阵A对称正定，且0ω2，则SOR方法收敛（定理7.P66）。,（3）若系数矩阵A严格对角占优，且0ω1，则SOR方法收敛（教材中未介绍此结论）。,Remark能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为opt。对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优等性质的矩阵A的线性方程组，可以建立最佳松弛因子其中J为解Ax＝b的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定opt并不容易，实际计算时一般都是根据试算的情况确定opt的一个近似值。,3.如果,则用此判断法比用方便。,Remark使用迭代法求解线代数方程组需注意的问题,1.迭代法的收敛性与初始向量的选取无关。但初始,向量的选取对迭代的工作量有重大影响。,4.对某些方程组，有时可适当作些变形，以使得迭代法收敛（交换方程或变元的次序）。,