解线性方程组的直接法.ppt

1、解线性方程组的直接法,在科学研究与工程技术中存在着大量的解线性方程组的问题。很多数值方法到最后也会涉及到线性方程组的求解问题：,如求样条插值的 M 和 m 关系式，解曲线拟合的法方程，求矩阵特征值的反幂法等问题。,对线性方程组：,或者：,我们有Cramer法则,当且仅当det(A)0时，有唯一的解：,但在实际工程运算中Cramer法则往往不能实用于计算方程组的解，如 n100，1033次/秒的计算机要算10120年，这是可想象，也是不现实的。,一般的，在工程领域解线性方程组的方法可以分为2类：,直接法：准确，可靠，理论上得到的解是精确的;,迭代法：速度快，但有误差.,本章讲解直接法,我们知道，

2、虽然方程组系数矩阵为一般比较“完整”的矩阵时， 解方程组非常困难，但如果方程的系数矩阵为下面有3种时， 我们可以直接求出其解：,n次运算,（n1）n/2次运算,一、消去法,对角矩阵,下三角矩阵,（n1）n/2次运算,问题是：我们如何将系数矩阵为一般形式的方程组，化为具有以上特殊系数矩阵的方程组？,下三角矩阵,我们知道，对方程组作如下的变换，解不变,交换两个方程的次序；,一个方程的两边同时乘以一个非0的数；,一个方程的两边同时乘以一个数，加到另一个方程。,因此，对相应的增广矩阵(A，b) 作初等行变换方程组解不变，即,交换矩阵的两行；,某一行乘以一个非0的数；,某一行乘以一个数，加到另一行；,消

3、元法就是对增广矩阵作上述的行变换，使之变为我们已知的 3种类型之一，而后求解的方法。,1.高斯(Gauss)消元法,行变换,1.消去过程将系数矩阵化为上三角矩阵：,运算量： (n-1)(1+n),步骤分为两个过程,第一步：第i行第1行(-ai1)/a11, i=2,3,n.,运算量： (n-2)(1+n -1) =(n-2)n,第二步：第i行第2行(-ai2(2)/a22(2), i=3,4,n.,第k步：,类似的做下去，我们有：,运算量： (nk) (1nk1)=(nk)(nk2).,n1步以后，我们可以得到变换后的矩阵为：,2.回带过程对系数矩阵为上三角矩阵方程组，逐步求解：,因此，总的运

4、算量为：,加上 解上述上三角阵的运算量(n+1)n/2，总共为：,例题,用Gauss消去法解方程组:,1消元：对增广矩阵进行初等行变换,2回带：解以上矩阵为增广矩阵的方程组：,所以，Gauss消元法的可行条件为：,就是要求 A 的所有顺序主子式均不为 0，即,因此，有些有解的问题，不能用Gauss消元求解(出现溢出现象),例：单精度解方程组,用Gauss 消元法计算：,8个,小主元可能导致计算失败。,在 Gauss 消元第 k 步之前，做如下的事情：,行的交换，不改变方程组的解，同时又有效地克服了Gauss消元的缺陷,例：,2、列主元消元法,例题,用列主元消去法解方程组,1消元：对增广矩阵进行

5、初等行变换,2回带：解以上矩阵为增广矩阵的方程组：,选主元,消元,选主元,消元,将在Gauss消元第k步，变为,将该行上三角的部分也变为0,最后变为一个对角阵。,它的运算次数比Gauss消元多。适用于计算多个系数相同的方程组，如,X，B均为矩阵,3、Jordan消元法,例题,用Jordan消去法解方程组,1消元：对增广矩阵进行初等行变换,2回带：解以上矩阵为增广矩阵的方程组：,Gauss消元法的第k步：,从矩阵理论来看，相当于左乘矩阵,二、三角分解法,分析Gauss消元法的过程：,因此，整个Gauss消元法相当于左乘了一个单位下三角阵,所以存在L，使 A=LU,其中L为单位下三角阵，U为上三角

6、阵。因此,我们可以通过2次反代过程求解方程组,最终使系数矩阵化为上三角矩阵即A=L-1U,求下三角L和单位上三角U，使得A= L U,比较第1行：,比较第1列：,1、Doolittle分解直接三角分解,比较第2行：,比较第2列：,比较第 k 行：,比较第 k列：,k-1次,k-11次,分解过程完毕，加上两次反代过程,总运算量为：,存储在矩阵的原来位置，且不影响计算,注意：,分解的理论由Gauss消元得出，因此分解能够进行的条件与Gauss消元一样,例：用Doolittle分解 直接三角分解A=LU解方程组：,LY=b, 得：y1=3.0 , y2=-0.5 , y3=-6.75 ,UX=Y,

7、得 x1=0.785714, x2=0.714286, x3=-1.928571,2、Crout 分解,L为下三角，U为单位上三角,两次反代过程,下面，我们对一下特殊的矩阵，提出一些特定的分解法,例：用 Crout分解 直接三角分解A=LU解方程组：,3. 三对角阵的追赶法,所以，有计算过程如下：,3. 对称阵的 LDLT 分解,应用有限元法解结构力学问题时，最后归结为求解线性代数方程组，系数矩阵往往对称正定。平方根法是一种对称正定矩阵的三角分解法，广泛用于求解系数矩阵为对称正定的线性代数方程组。,若A对称正定，且顺序主子式不为零，则有下三角阵L，使得,所以有：,称为平方根法， 因为带了开方运算，因此不常用,又,则有,比较等号两边后，有,例 用三角分解法，解线性方程组AX=b，其中,解 首先对系数矩阵进行平方根法分解，设,由LYb:,解之得,由DZY:,解之得,由LTXZ: