《线性方程组的迭代解法 消去法》由会员分享，可在线阅读，更多相关《线性方程组的迭代解法 消去法（68页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 线性方程组的迭代解法线性方程组的迭代解法6.1 消去法消去法方程组系数矩阵的分类方程组系数矩阵的分类n低阶稠密矩阵（例如，阶数不超过低阶稠密矩阵（例如，阶数不超过150）（一般用直接法来求解）（一般用直接法来求解）n大型稀疏矩阵（即矩阵阶数高且零元素大型稀疏矩阵（即矩阵阶数高且零元素较多）较多）（一般用迭代法来求解）（一般用迭代法来求解）线性方程组的数值解法分类线性方程组的数值解法分类n直接法直接法 经过有限步算术运算，可求得方程组精经过有限步算术运算，可求得方程组精确解的方法。确解的方法。n迭代法迭代法 用某种极限过程去逐步逼近线性方程组用某种极限过程去逐步逼近线性方程组精确解
2、的方法。精确解的方法。消去法的基本思想消去法的基本思想通过将一个方程通过将一个方程乘或除乘或除以某个常数，以及将两个以某个常数，以及将两个方程方程相加减相加减这两种手续，逐步这两种手续，逐步减少减少方程中方程中变元变元的的数目，最终使每个方程仅含一个变元，从而得出数目，最终使每个方程仅含一个变元，从而得出所求的解所求的解.n约当（约当（Jordan)消去法消去法n高斯（高斯（Gauss)消去法消去法 约当消去法约当消去法特点特点它的每一步仅在一个方程中保留某个变元，它的每一步仅在一个方程中保留某个变元，而从其余的各个方程中消去该变元，这样经而从其余的各个方程中消去该变元，这样经过反复消元后，所
3、给方程组最终被加工成一过反复消元后，所给方程组最终被加工成一个方程仅含一个变元的形式，从而得出所求个方程仅含一个变元的形式，从而得出所求的解的解.AXAX=b b方程组的向量表示形式方程组的向量表示形式方程形态的演变（方程形态的演变（0）方程形态的演变（方程形态的演变（1）方程形态的演变（方程形态的演变（1）方程形态的演变（方程形态的演变（2）方程形态的演变（方程形态的演变（2）方程形态的演变（方程形态的演变（k-1）方程形态的演变（方程形态的演变（k）方程形态的演变（方程形态的演变（k）方程形态的演变（方程形态的演变（n）约当消去法第（约当消去法第（1）步）步初始状态初始状态第（第（1）步）
4、步约当消去法第（约当消去法第（1）步）步运算过程运算过程约当消去法第（约当消去法第（k）步）步第（第（k-1）步）步第（第（k）步）步约当消去法第（约当消去法第（k）步）步运算过程运算过程约当消去法的计算量与存储空间约当消去法的计算量与存储空间计算量计算量存储空间存储空间高斯消去法高斯消去法虽然高斯消去法是一个古老的求解线性方程组的虽然高斯消去法是一个古老的求解线性方程组的方法（早在公元前方法（早在公元前250年我国就掌握了解方程组的年我国就掌握了解方程组的消去法），但是由它改进、变形得到的选主元素消去法），但是由它改进、变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的消去法、三角
5、分解法仍然是目前计算机上常用的有效方法。有效方法。举例（一）解：q 例：直接法解线性方程组例：直接法解线性方程组高斯消去法的基本思想高斯消去法的基本思想考虑考虑 n 阶线性方程组：阶线性方程组：矩阵形式矩阵形式=方程形态的演变（方程形态的演变（0）方程形态的演变（方程形态的演变（1）方程形态的演变（方程形态的演变（1）方程形态的演变（方程形态的演变（2）方程形态的演变（方程形态的演变（2）方程形态的演变（方程形态的演变（k-1）方程形态的演变（方程形态的演变（k）方程形态的演变（方程形态的演变（k）方程形态的演变（方程形态的演变（n）高斯消去法的回代过程高斯消去法的回代过程高斯消去法的计算量分
6、析高斯消去法的计算量分析消元第消元第k步的计算量为步的计算量为(n-k+1)(n-k+1)回代第回代第k步的计算量为步的计算量为(k-1)高斯消去法总的乘除运算量为：高斯消去法总的乘除运算量为：高斯主元素消去法高斯主元素消去法由高斯消去法知道，在消元的过程中可能由高斯消去法知道，在消元的过程中可能出现出现 的情况，这是消去法将无法进的情况，这是消去法将无法进行即使主元素行即使主元素 但很小时，用其作除但很小时，用其作除数，会导致其他元素数量级的严重增长和数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可舍入误差的扩散，最后也使得计算解不可靠。靠。例例2错误算法错误算法例例
7、2改进算法改进算法全主元高斯消去法全主元高斯消去法第第 k 步消元时选步消元时选 A(k)中绝对值最大的元素为主元，即中绝对值最大的元素为主元，即 先选取先选取全主元全主元：if ik k then 交换交换第第 k 行行和和第第 ik 行行；if jk k then 交换交换第第 k 列列和和第第 jk 列列；消元消元列交换改变了列交换改变了 xi 的顺序，须记录的顺序，须记录交换次序交换次序，解完后再，解完后再换回来。换回来。全主元高斯消去法具有很好的稳定性，但选全主元比全主元高斯消去法具有很好的稳定性，但选全主元比较费时，故在实际计算中很少使用。较费时，故在实际计算中很少使用。定理定理定
8、理定理1定理定理2假设方程组（假设方程组（4）是对角占优的，则）是对角占优的，则（k=1，2，n）全不为）全不为 0.假设方程组（假设方程组（4）对称并且是对角占优的，）对称并且是对角占优的，则则 （k=1，2，n）全是主元素）全是主元素.定理1假设方程组（假设方程组（4）是对角占优的，则（）是对角占优的，则（k=1，2，n）全不为）全不为 0.证：证：定理1定理1定理1变换以后仍然是对角占优的，以此类推，则命题得证。变换以后仍然是对角占优的，以此类推，则命题得证。例题例题2用列主元消去法求解下列方程组用列主元消去法求解下列方程组写成向量表示形式写成向量表示形式增增广广矩矩阵阵消元（消元（1）
9、选选主主元元素素交交换换消消元元消元（消元（2）选选主主元元素素交交换换消消元元回代回代得得到到方方程程方方程程组组的的解解矩阵的三角分解矩阵的三角分解 高斯消元法的矩阵形式高斯消元法的矩阵形式:Step 1:记记 L1=L11=记记 于是于是矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解矩阵的三角分解Step n 1:Lk=其中其中矩阵的三角分解矩阵的三角分解记为记为L记记 U=矩阵的三角分解矩阵的三角分解定理定理1：（矩阵的三角分解）设：（矩阵的三角分解）设A为为n n实矩阵，如果实矩阵，如果解解AX=b用高斯消去法能够完成（限制不进行行的交用高斯消去法能够完成（限
10、制不进行行的交换，即换，即 ），则矩阵），则矩阵A可分解可分解为单位下三角矩阵为单位下三角矩阵L与上三角知阵与上三角知阵U的乘积。的乘积。A=LU且这种分解是唯一的。且这种分解是唯一的。矩阵的三角分解法矩阵的三角分解法将高斯消去法改写为紧凑型时，可以直接从矩阵A的元素得到计算L,U元素的递推公式，而不需要任何中间步骤，这就是所谓直接三角分解法。一旦实现了矩阵A的LU分解，那么求解Ax=b的问题就等价于求解两个三角形方程组分解方式分解方式A=LU的唯一性的唯一性为保证分解方式为保证分解方式A=LU的唯一性，要求将分解阵的唯一性，要求将分解阵L与与U中的一个单位化，即令其主对角元素全为中的一个单位
11、化，即令其主对角元素全为1这里区分两种情况：这里区分两种情况：n如果限定如果限定L为单位下三角阵，则称矩阵分解为为单位下三角阵，则称矩阵分解为Doolittle分解分解n如果限定如果限定U为单位上三角阵，这时矩阵分解成为单位上三角阵，这时矩阵分解成为为Crout分解分解矩阵的三角分解矩阵的三角分解于是有：于是有：容易验证：容易验证：(k=1,n-1)矩阵的三角分解矩阵的三角分解记：记：，则，则其中：其中：L-单位下三角矩阵单位下三角矩阵，U-上三角矩阵上三角矩阵LU 分解(杜利脱尔Doolittle分解)直接利用矩阵乘法来计算直接利用矩阵乘法来计算 LU分解分解比较等式两边的比较等式两边的第一
12、行第一行得：得：u1j=a1j比较等式两边的比较等式两边的第一列第一列得：得：比较等式两边的比较等式两边的第二行第二行得：得：比较等式两边的比较等式两边的第二列第二列得：得：(j=1,n)(i=2,n)(j=2,n)(i=3,n)U 的第一行的第一行 L 的第一列的第一列 U 的第二行的第二行 L 的第二列的第二列 直接利用矩阵乘法来计算直接利用矩阵乘法来计算 LU分解分解第第 k 步：步：此时此时 U 的前的前 k-1 行和行和 L 的前的前 k-1 列已经求出列已经求出比较等式两边的比较等式两边的第第 k 行行得：得：比较等式两边的比较等式两边的第第 k 列列得：得：直到第直到第 n 步，便可求出矩阵步，便可求出矩阵 L 和和 U 的所有元素。的所有元素。(j=k,n)(i=k+1,n)例题例题1解解例题例题2解解例题例题3解解例题例题4解解追追赶赶追赶法追赶法追赶法追赶法追赶法追赶法追赶法追赶法
