《西安石油大学现代数值计算方法》由会员分享，可在线阅读，更多相关《西安石油大学现代数值计算方法（102页珍藏版）》请在金锄头文库上搜索。
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：若 令 ,用 乘 第一个方程加到第 个方程 ，并保留第一 式，则得其中记为若 令 ，乘第二个方程加到第i个方程 ，则得用Step2:记为其中设为第k-1步消
3、元完成后，有Stepk：若 ,令 , （i=k+1,k+2,)用- 来乘以第k-1步所得方程中的第k个方程，加到 第i 个方程，并保留第k个方程，则得 ：（i=k+1,k+2,n）按上述做法，做完n-1步消元，原方程可化为同解的上 三角方程组：其中(i,j=k+1,n)（i=k+1,n）上面的方程记为记为最后，若 ，逐步回代可得到原方程组的解：（i=n-1,n-2,2，1）上面的求解过程称为Gauss顺序消去法。它通过一 系列消元过程与最后的一步回代过程来得到方程组的 解。Remark1：在Gauss顺序消去法的消去过程中，可以将 右端列向量视为方程组A的第n1列，直接对矩阵A（ 指现在的n行
4、，n1列的增广矩阵）进行行初等变换 ，将其变换为上三角形矩阵，从而回代求解得到方程 组的解。Remark2：可以统计出，如果A为n阶方阵，则Gauss顺 序消去法消去过程所需的乘除运算次数为回代过程所需的乘除运算次数为故总的乘除运算次数为取n20，则N3060，与Gramer法则相比，是天壤 之别。 Remark3：在消去过程中，也可以采用Gauss-Jordan消 去法，将方程组化为对角形方程组，进而化为单位阵 ，则右端列向量就化为方程组的解向量。该方法不需 回代过程，但总的计算量为n3/2+n2-n/2，比Gauss顺序 消去法有所增加。Remark4：在消去过程中，消去过程能够进行的前
5、提条件是 。当detA= 时方程组存在唯 一解，但未必能满足 的条件。要使Gauss顺 序消去法能够求得方程组的解，应满足如下的定 理： 定理：用高斯顺序消去法能够求解方程组 的解的充要条件为A的各阶顺序主子式均不为零 。算法见教材第27页：（1）消元过程.对k=1,2，n-1进行如下运算：对i=k+1.k+2,n;对j=k+1,n+1,(2) 回代过程.按下述公式此时高斯顺序消去法能进 行下去，但不能求出唯一解。当 detA=0,说明：当 高斯顺序消去法能进行下去，但当 或相对于（k=1,2,，n)均不为零时（i=k+1,k+2，n）比较小时，计算时产生的 舍入误差将导致计算结果误差增大。由
6、于舍入误差的原因，Gauss顺序消去法不是 一个实用的方法，实用中应该采用选主元的 Gauss消去法。在计算过程中舍入误差增大迅速，造成 计算解与真解相差甚远，这一方法就是不稳 定的方法，反之，在计算过程中的舍入误差 增大能得到控制，该方法就是稳定的。小主 元是不稳定的根源，这就需要采用“选主元 素”技术，即选取绝对值最大的元素作为主 元。二、主元素消去法B= 1)列主元消去法一种常用的方法是列主元消去法。设增广矩阵为在第一列中选取绝对值最大的元素,如若 = 调换第一行与第i行，这时的 就是原来的 ,再进行消去法的第一步，即再考虑 右下角矩阵，选取绝对值最大的元素作为 主元素,经过行的对换把主
7、元素移到 ， 再按消元公式计算 （i,j=3,n）。直至将方程组化成上三角方程组，再进行回代就可 求得解。然后每一步类似的都在右下角方阵中的第一列中选 主元，再经行对调, 将主元素换到右下脚方阵中左 上角的位置。再按下一步计算（i,j=kn)算法见教材第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= 列在A中选取绝对值最大的元素作为主元素，如 ,然后交换B 的第一行与第 行，第一列，这时的 就是元
8、素的 元法的第一步，即与第 ，然后进行消都 换把主元素移到 再按消元公式计算 （i,j=3,n）,然后每一步 对再考虑 右下角矩阵，选取绝对值最大的元素作为 主元素,经过行的对换和列的对 在右下角方阵中进行完全选主元，经过行的位置, 类似的 调列对调将主元换到右下角方阵中左上角的位置， 再按下一步计算 （i,j=kn）直至将方程组化成上 三角方程组，再进行回代就可得解。RemarkReamrk1：全主元消去法每一步所选取的主元的绝 对值不低于列主元消去法的同一步所选主元的绝 对值，因而计算结果更加可靠。Reamrk2：全主元消去法每一步选主元要花费更多的 机时，并且对增广矩阵做了列交换，从而未
9、知量的 次序发生了变化，对编程带来了困难。而列主元消 去法的计算结果已比较可靠，故实用中常用列主元 消去法。Reamrk3：选主元的消去法与Gauss顺序消去法的 乘除法的计算量是一样的，均为n3/3+n2-n/3。三、选主元素消去法的应用 1.求解方程组系设系数矩阵A可逆，求解方程组系AXbi(i=1,2,m)。将方程组系的系数矩阵与右端向量写成增广矩阵 A|b1,b2,bm 按列选主元素后再用Gauss-Jordan消去法将左边的 矩阵A化为单位矩阵，则得到右端的列向量就是方程组系的解向量。2.求逆矩阵在1中令mn，且右端列向量组成单位阵，则当 A化为单位阵时，右端矩阵即为A的逆矩阵。这
10、是实用中求逆矩阵的可靠方法。3.求行列式若要求矩阵A的行列式，可用主元素消去法将其化 为上三角阵，对角元素设为b11，b22，bnn，于 是A的行列式为：det(A)=(-1)m b11b22bnn其中m为行列交换的次数。这是实用中求行 列式的可靠方法。四、矩阵三角分解法1.Gauss顺序消去法的矩阵形式设方程组A = 中A的各阶顺序主子式均不为零，令则n-1步消元过程为将上述n-1步消元过程合并，得，即 （1） 由 得：容易验证： 每个 可逆，且 k=1,2,，n-1 令L= 则 L= 又令 U= ,且 U= 则A=LU， 其中，L为单位下三角矩阵，它的对角元素皆为1。 (三角分解与高斯消去
11、法的关系)Gauss消去法的实质就是用一连串的初等变换 把系数方阵A化成上三角方阵U，同时把右端向 量化 为 , 若矩阵A=LU，则LU叫做矩阵A的LU 分解 .AX=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是单位上三角
12、矩阵，则称A=LU为Crout分 解。前面高斯顺序消去法对应了A=LU的Doolittle 分解。（P32定义1）定理1：设A为n阶可逆矩阵，则A有唯一 Doolittle(or Crout)分解的充要条件为：A的前n- 1阶顺序主子式不为零。Remark：实际中对A进行三角分解，不是利用初等变 换矩阵，而是直接使用矩阵乘法得到。（若不加说明 ，后面我们讲到的三角分解一律指Doolittle型分解 。）的求解过程为:可推导求解单位下三角形方程组 的递归公式为 :求解上三角形方程组 的递归公式为：3.直接三角分解法 设A=LU 即Step1： 比较第一行元素：比较第一列元素：解出Step2： 比
13、较第二行元素： 算出： 比较第二列的元素： 得出：一般地，设U的前k-1行以及L的前k-1列已求出，则比较第k行元素Stepk： 可以算出： 比较第k列元素(ik 即行指标列指标，为算 , ik) 算出 : 这组公式可用下图记忆（紧凑格式）:P33的求解过程为:可推导求解单位下三角形方程组 的递归公式为 :求解上三角形方程组 的递归公式为: (P34):对比计算 和 公式， 发现计算 的规律与计算 的规律类似,因此计 算 的求方程组的过程可用三角分解的紧凑格 式取代。事实上,这只要把 做为A的第n1列 进行直接三角分解即可。Reamrk：上述直接三角分解法所对应的是Gauss顺序 消去法，二者
14、的乘除运算次数是相当的。实际中对 阶数较高的线性方程组，应采用选主元的三角分解 法求解，以保证计算结果的可靠性。例求解F三角分解法的运算量与高斯消去法大体 相当，但对于系数矩阵A不变而常数列b 变化的的一类方程组来说，节省运算量F因为A=LU不用再分解，对于不同的bF直接解LY=b和UX=Y即可列主元三角分解法主要思想4.平方根法（Cholesky分解） 设A为n阶 对称正定矩阵，L是非奇异下 三角矩阵，称 为矩阵A的乔列斯基(Cholesky) 分解。n阶 对称正定矩阵A，一定存在如下的分 解式 ，其中L为单位下三角阵，D是对角 元全为正的对角阵，且这种分解式唯一; ， 其中L为下三角阵，当
15、限定L的对角元为正时， （Cholesky分解）的分解式唯一。定义： 定理： 平方根法的计算公式 （为简单起见设 ，L为下三角矩阵） 令我们可以通过矩阵乘法比较来求L的下三角部分 元素。具体计算公式如下:P28Remark1:由于在上式分解过程中有n次开方运算， 故Choledsky分解法也称为平方根法。 Remark3:可以证明，若用Gauss顺序消去法求解对称正 定的方程组Axb，则有Remark2: 因为 ，这说明放大受到控制，故用平方根法解对称正定的方程组 时，不必考虑选主元的问题，算法本身数值稳定。的平方不会超过A的最大对角元，因而舍入误差的其中是第k步Gauss顺序消去过程所得元素。这说明 用Gauss顺序消去法求解对称正定方程组也不用选主元 。Remark4:从运算量的角度看，平方根法是有利的。 可以统计出，用平方根法求解A
