第三章线性方程组解法ppt课件.ppt

《第三章线性方程组解法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性方程组解法引言引言求解线性方程组的方法§1Gauss消元法Gauss消元法是最基本的一种方法，下例说明其基本思想:例1.解线性方程组：解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：例1（续）再消一次元得：二次消元后将方程化为上三角形式，然后进行回代容易解出：x3=3,x2=2,x1=1。1.1Gauss消去法Gauss消元法的消元过程第k步：设第k1步消元后得原方程组的同解方程组为：Gauss消元法的回代

2、过程回代过程：逐步回代求得原方程组的解Gauss消元法可以进行的充分条件Gauss消元法的算法描述消元过程回代过程Gauss消元法的计算量由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第k次消元需作nk次除法，作(nk)(nk+1)次乘法，故消元过程中乘除法运算量为：所以Gauss消去法的乘除法总运算量为：1.2主元消去法在该过程中，主元是按列选取的，故称为列主元法。列主元素法的具体步骤如下：列主元消去法全主元消去法全主元消去法：精度高，

3、但是要换列和记录次序，比较麻烦。计算过程保留三位小数。Gauss-Jordan求矩阵的逆Gauss消元法有许多变形，列主元素法是其中之一，在列主元法的基础上还可对算法进行如下的修改：在消元过程中选主元后，先将主元化为1，然后将主元所在列上、下方各元素均化为0，这样消元的结果使系数矩阵化为了单位阵，无需回代就得到了原方程之解，这种无回代过程的列主元素法称为Gauss-Jordan消元法。Gauss-Jordan消元法比顺序消去法计算量大一点，实践中使用不多，但用它求逆阵却十分方便。因为消元过程实质上

4、就是对系数矩阵实行初等行变换，当将Gauss-Jordan消去法用于矩阵[A,I]时，得问题：若要求计算过程保留三位小数，结果又该如何？解1.3解三对角方程组的追赶法在很多问题中，需要解如下形式的三对角方程组：三对角方程组的系数矩阵为三对角阵，对于这种特殊而又简单的方程组，用前面介绍的方法求解由于有大量的零元素既占内存又浪费计算时间，显然很不经济。充分注意到三对角方程组的特点，根据顺序消元的思想导出一个简便的算法——追赶法。首先进行顺序消元，且每步将主元系数化为1，将方程组化为：其中系数按下式计算

5、：回代求解得：用追赶法解下列三对角方程组：例6解：首先将方程组化为（先追）：然后回代（赶）求解：x5=0，x4=30/7，x3=6/7，x2=12/7，x1=0可以看出，追赶法本质上还是顺序消元法，但由于计算过程中只涉及系数矩阵的非零元，因此大大节约了计算机内存与计算量，按乘除法次数进行比较，Gauss消元法约为n3/3，而追赶法仅为5n-3次，可见追赶法是求解三对角方程组的非常好的方法。§2矩阵分解法几类特殊的线性方程组求解：1、若矩阵具有对角结构，即求解2、若矩阵具有下三角结构，即求解3、若

6、矩阵具有上三角结构，即求解如果用矩阵形式表示，Gauss消元法的消元过程是对方程组的增广矩阵（A、b）进行一系列的初等行变换，将系数矩阵A化成上三角矩阵的过程，也等价于用一串初等变换阵去左乘增广矩阵，因此，消元过程可以通过矩阵运算来实现。2.1Gauss消元法的矩阵形式事实上，Gauss消元法的第一次消元相当于用初等矩阵：第二次消元相当于用初等矩阵：第k次消元相当于用初等矩阵：经过n1步消元后得到：这说明：在的条件下，消元过程实际上是把系数矩阵A分解成单位下三角阵与上三角矩阵的乘积的过程。因为L

7、k(k=1,2,…,n1)均为非奇异阵，故它们的逆矩阵存在。容易求出：2.2Doolittle分解——LU分解由上述过程，可以将矩阵A分解成两个三角形矩阵的乘积，即：A=LU，其中L为单位下三角矩阵，U为上三角矩阵：上述分解称为杜利特尔（Doolittle）分解，也称为LU分解。定理.设A为n阶方阵，矩阵A存在唯一的Doolittle分解的充分条件为：A的顺序主子式Ai(i=1,2,…,n1)均不为零；若A为非奇异的，则其亦为必要条件。下面讨论如何对A进行LU分解：由于两个矩阵相等就是它们的对

8、应元素都相等，因此通过比较A与LU的对应元素，即可得到直接计算L、U的元素的公式：A=LU即：由矩阵乘法规则及比较式子两端的元素，得：对A进行LU分解（k行k列）得到计算ukj和lik的公式：假设已经求得U的前k-1行，L的前k-1列，下面讨论U的第k行，L的第k列：对A进行LU分解的具体步骤1.计算U的第1行，L的第1列，亦称为计算第1框；2.计算U的第k行，L的第k列（k=2,…,n），即第k框；三角分解的紧凑格式矩阵的三角分解可按以下格式及顺序进行。这种格式既便于记忆，又便于