4线性方程组的直接解法

1、4 线性方程组的直接解法线性方程组的直接解法 （ Direct methods of Linear equations ） n 本章主要内容本章主要内容n 4.1 高斯消去法高斯消去法 n 4.2 三角分解法三角分解法 n 4.3 直接法的误差分析直接法的误差分析n 4.4 近似解的精度改善近似解的精度改善n 重点：重点：LU分解分解n 难点：追赶法、平方根法难点：追赶法、平方根法 直接法直接法（第（第4章）章）思想思想：对系数矩阵进行分解分解、变换变换，经有限次算术运算，求出精确解特点特点：准确、可靠、无方法误差无方法误差适用适用：中、小规模问题，尤其是稠密系数矩阵问题问题：舍入误差对病态方

2、程组的影响，算法可能不稳定 常见的线性方程组常见的线性方程组数值方法分类数值方法分类 平方根分解法乔立斯基三对角方程组的追赶法分解克劳拉分解杜利特里分解分解法消去法主元消去法消去法消去法直接法迭代法迭代法迭代法迭代法)()()(CholesyCroutDoolittleLUJordanGaussGaussGaussSORSeidelGaussJacobi4.1 消去法消去法 4.1.1 高斯消去法高斯消去法用高斯消去法求解线性方程组，分为消元过程消元过程和回代过程。回代过程。 消元过程消元过程将原始方程组 记作 。经过n-1步消元后，得到Axb(1)(1)A xb记作( )( )nnAxb(1

3、)(1)(1)(1)1111121(2)(2)(2)22222( )( )nnnnnnnnbxaaaxaabxab ( )( )/(1, )kkikikkkmaaikn (1)( )( )( ,1, )kkkijijikkjaam ai jkn (1)( )( )(1, )kkkiiikkbbm bikn 其中注意：必须确保0kka 回代过程回代过程对于上三角方程组，容易得到( )( )( )( )( )1/()/(1,2,2,1)nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 可行性与计算量可行性与计算量1、系数矩阵A的各阶顺序阶主子式均不为零。2、系数矩阵A对称正定。3、系

4、数矩阵A严格对角占优。消元和回代的乘除及加减法总次数总次数如下：65232)1()1)(332)1()1)()(2311231111nnnnnknknnnnnnknknknnknknk高斯消元法的消去过程和回代过程均要求 ，否则溢出停机。但在如下情况下，对原方程组不作任何处理，确保上述条件成立，使高斯消去法在计算机上顺利执行。 由于在此不予证明，仅列出一下三个条件条件： ), 2 , 1( 0)(nkakkk相比克莱姆法则的乘除法次数不在一个数量级上，减少了很多。nnnn) 1( !) 1(4.1.2 高斯列主元消去法高斯列主元消去法为拟制舍入误差的传播，在消元过程中希望主元 的绝对值最大，就

5、要在每步消元过程前选主元。通常有列主元列主元和全主元全主元两种方法。 kka列主元消去法列主元消去法是第k步消元时，选取( )( )maxkkpkikk i naa 作为主元素，进行消元。而全主元消去法全主元消去法是选取ijnjknikpqaamax作为第k步的主元素进行消元。列主元列主元往往需要行的交换，而全主元全主元不仅需要行的交换，而且可能需要列的交换。列的交换实质上是未知量的交换。列主元素消去法步骤及流程框图 （p63-65）选主元的思想思想是消除零主元和小主元，策略策略是对方称组进行行或列的交换。4.2 三角分解法三角分解法 矩阵的初等（行）变换与初等方阵矩阵的初等（行）变换与初等方

6、阵矩阵的初等变换：三种形式初等方阵：三种形式类型，p(I,j), p(i(k),p(i(k),j)，与初等变换一一对应初等变换与初等方阵的关系：初等方阵的逆阵、行列式、乘法此处主要使用第三种形式的初等方阵1111),(kjkiP1),(1111),(1jkiPkjkiP4.2.1 LU LU分解法分解法高斯消去法的消元过程是通过对增广矩阵的初等行变换来完成的。 101001,/, 1/, 3/, 3 , 2/10010001,10010001,10010001,1001001000002121111211111211)1(1, 1)1(1,1,)()()2(22)2(22)1(11)1(111

7、,1221211121)()()(2)(2)(22)(1)(1)(12)(11)2()2()2(2)2(2)2(2)2(22)2(1)2(1)2(12)2(11)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnnnnnnnkkkkikikiiiinnnnkknnknnnnnnnnnnnnnnnnnnnnnnnnnnnnlllLALyLUyULyULLLbALLLLaalnkiaalniaalniaallLlLlLllLyUbALLLLyUbabaabaaabaabaabaaabaaabaaabaaabALUULALybLU分解。这

8、里的乘积，这就是矩阵的与上三角阵分解为单位下三角阵即将又可写成阶单位下三角阵，且阵的乘积构成的它们都是若干个初等方则有令其中用矩阵乘法可表示为：例例4-2 P67用用LU分解法求解线性方程组的分解法求解线性方程组的步骤步骤（1）对）对A进行进行LU分解，即分解，即A=LU；公式见p69 （4-5）-（4-8）（2）求解）求解Ly=b；公式见p69 （4-9）（3）求解）求解Ux=y；公式见p70 （4-10） 例例4-3 p70用用LU分解法求解线性方程组的分解法求解线性方程组的数据结构数据结构 存储空间仅需一个存储空间仅需一个n阶的二维数组和一个阶的二维数组和一个n阶的一维数组（向量）阶的一

9、维数组（向量）公式nnnnnnnnnnnnnnnxxxyyybbbulluuluuuaaaaaaaaaA212121212222111211212222111211思考思考：如何利用矩阵的LU分解求解矩阵方程 Ax=B。4.2.1 LU LU分解法分解法 直接三角分解直接三角分解 可以不经过高斯消去过程，直接利用公式得到矩阵的可以不经过高斯消去过程，直接利用公式得到矩阵的LU分解。令分解。令LUuuuuuulllaaaaaaaaaAnnnnnnnnnnnn000101001222112112121212222111211矩阵L,U的计算公式见教材p69 （4-5）-（4-8）。如上的LU分解成

10、为杜利特尔（杜利特尔（Doolittle）分解）分解。还有另一种分解法称为克克劳特（劳特（Crout）分解）分解，它是将A分解为一个下三角阵L与一个单位上三角阵U的乘积的形式，可以自己推导L和U的计算公式。LU分解的唯一性定理分解的唯一性定理定理定理4-1 设设A为为n阶方阵，若阶方阵，若A的各阶顺序主子式不为零，则的各阶顺序主子式不为零，则A可分解可分解为单位下三角阵为单位下三角阵L与一个上三角阵与一个上三角阵U的乘积，且这种分解是唯一的。的乘积，且这种分解是唯一的。证明：反证法。见证明：反证法。见p67 列主元列主元LU分解的分解的矩阵描述矩阵描述的意义同上节。种形式的初等方阵，第的行时交

11、换次两行所对应素在第次交换选列主元其主元是第这里kkkiniininniininLikEbbELELELUAAELELELknn1,)()1(1 ,12,21,1)()1(1 ,12,21,1121121PbLUxPAxLUPALLLLLPALLLLAEEEEELEEEELEEELELLnnnniiiiiiinininninininninknnnnnnnnnnnn,)()(54p1211112111 ,2,2,12,1,2,32,1,1,21,1121, 11, 1221, 1122111从而有令），可得到如下形式（见拓展 列主元列主元LU分解计算分解计算步骤步骤和和公式公式 P73-744.

12、2.2 列主元列主元LULU分解法分解法4.2.3 三对角方程组的追赶法三对角方程组的追赶法 三对角矩阵三对角矩阵与三对角方程组与三对角方程组 三对角矩阵的克劳特分解的三对角矩阵的克劳特分解的唯一性唯一性 追赶法计算追赶法计算步骤步骤及及流程图流程图 追赶法计算时的追赶法计算时的存储结构存储结构nnnnndacdacdacdA11122211定理定理4-2 设设A为三对角矩阵，且对角占优，则对为三对角矩阵，且对角占优，则对A可以进行可以进行克劳特分解克劳特分解，且分解是唯一的。且分解是唯一的。1 , 2 , 1,3, 3 , 2)/()(,/21, 3 , 2)/(,/11111111111n

13、ixuyxyxniuadyabydbyniuadcudcuiiiinniiiiiiiiiiii步骤步骤步骤iiiiiiixyubcda4.2.4 对称正定矩阵的平方根法对称正定矩阵的平方根法定理定理4-3 设设A为对称正定矩阵，则存在一个下三角阵为对称正定矩阵，则存在一个下三角阵L使得使得 A=LLT 若限定若限定L的主对角线元素取正值，则这种分解是唯一的。的主对角线元素取正值，则这种分解是唯一的。nnnnnnnnjjjkjkikijijjkjkjjjjnkijjjjkjkikjkikijllllllllllLnjinjlllalnjlalnjjilllllla,11,123222131211

14、111112111,1;1,2,1/)(,2,1)(,1,21的计算次序为：用上式求由矩阵乘法，可得1 , 1,/)(,2, 1/)(111nnilxlyxnilylbyyxLbLyiinikkkiiiiiikkikiiT的计算公式如下：和求解4.3 直接法的误差分析直接法的误差分析4.3.1 病态方程组病态方程组 对于线性方程组对于线性方程组Ax=b，如果，如果A或者或者b有很小的扰动（误差），但其有很小的扰动（误差），但其解会有很大的扰动（误差），则称该方程组为解会有很大的扰动（误差），则称该方程组为病态方程组病态方程组。11,00001. 0000211,0001. 00220001.

15、19999. 011220001. 11110001. 220001. 1111212121xAxxbxxxxxx时当精确解时当原问题20000/ 12/0001. 0/0001. 02/ 1/1bbbxxx上例的第一种情况：10000/11/0001. 0/0001. 02/1/1AAAxxx上例的第二种情况：4.3.2 矩阵的条件数矩阵的条件数通常用条件数的大小来度量方程组病态的程度。通常用条件数的大小来度量方程组病态的程度。矩阵矩阵A的条件数定义为的条件数定义为 范数及可取2 , 1)(1AAACond时当时当0)(1)(0)()(1)(bAAAAACondACondxxAbbACondxxAAbbAAACondACondxx计算3阶希尔伯特矩阵的条件数（例4-6）4.4 近似解的精度改善近似解的精度改善 基本