数值分析第五章线性方程组直接解法.ppt

《数值分析第五章线性方程组直接解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章解线性方程组的直接方法数值分析——Gauss消去法1线性方程组直接解法自然科学和工程计算中,很多问题最终都需要求解一个线性代数方程组(1)直接法:适合低阶方程组或某些特殊大型稀疏方程组目前使用的数值解法:(2)迭代法:解大型稀疏方程组的主流算法在本章中，我们总是假定A是n阶方阵2Gauss消去法例：直接法解线性方程组解：3Gauss消去法高斯消去法的主要思路：将系数矩阵A化为上三角矩阵，然后回代求解。考虑n阶线性方程组：矩阵形式=4Gauss消去法第一步：消去第一列依次将增广矩阵的第i行+mi1第1行，得设，计算其

2、中第二步：消去第二列依次将上述矩阵的第i行+mi2第2行，得其中设，计算记，即。5Gauss消去法高斯消去法第k步：消去第k列依此类推，直到第n-1步，原方程化为设，计算回代求解：计算(i=k+1,…,n)(i=n-1,…,1)6几点注记主元：Gauss消去法能进行到底的条件：主元全不为0Gauss消去法的运算量计算机中做乘除运算的时间远远超过做加减运算时间，故我们只估计乘除运算的次数定理：（i=1,2,...,n）的充要条件是A的顺序主子式不为零，即7运算量第k步：消去第k列计算计算(i=k+1,…,n)回代求解：(i

3、=k+1,…,n)n–k次(n–k)2次n–k次n(n+1)/2次乘除运算量为：8LU分解Gauss消去过程其实就是一个矩阵的三角分解过程则A(k)与A(k+1)之间的关系式可以表示为：其中：(i=k+1,…,n)将Gauss消去过程中第k-1步消元后的系数矩阵记为：(k=1,…,n-1)9LU分解LU分解记：，则其中：L---单位下三角矩阵，U---上三角矩阵LU分解于是有：容易验证：(k=1,…,n-1)(杜利脱尔Doolittle分解)10LU分解存在唯一性LU分解存在高斯消去法不被中断定理：若A的所有顺序主子式不为

4、零，则A存在唯一的LU分解所有顺序主子式不为零11列主元Gauss消去法Gauss消去法有效的条件是：主元全不为零例：解线性方程组①先选取列主元：②ifikkthen交换第k行和第ik行③消元列主元Gauss消去法在第k步消元时，在第k列的剩余部分选取主元12列主元Gauss消去法算法(列主元Gauss消去法)fork=1ton-1ifthenstopifikkthenswapk-thandik-throw(includingb)fori=k+1tonendend13PLU分解列主元Gauss消去法对应的矩阵分解为PL

5、U分解定理：若A非奇异，则存在排列矩阵P，使得PA=LU其中L为单位下三角矩阵，U为上三角矩阵列主元Gauss消去法比普通Gauss消去法要多一些比较运算，但比普通高斯消去法稳定列主元Gauss消去法是目前直接法的首选算法14全主元Gauss消去法全主元高斯消去法：第k步消元时，在剩余的n-k阶子矩阵中选取主元①先选取全主元：ifikkthen交换第k行和第ik行ifjkkthen交换第k列和第jk列③消元列交换改变了xi的顺序，须记录交换次序，解完后再换回来全主元高斯消去法具有更好的稳定性，但很费时，在实际计算中很少

6、使用15解：例：采用十进制八位浮点数，分别用Gauss消去法和列主元Gauss消去法求解:精确解为8个8个Gauss消去法：9个Gauss消去法－例子16列主元Gauss消去法：Gauss消去法－例子第五章解线性方程组的直接方法数值分析——矩阵三角分解法181、LU分解将Gauss消去过程中第k-1步消元后的系数矩阵记为：(k=1,…,n-1)LU分解19则A(k)与A(k+1)之间的关系式可以表示为：其中：(i=k+1,…,n)LU分解20LU分解于是有：容易验证(k=1,…,n-1)21记：，则这里:L---单位下三角

7、矩阵，LU分解(杜利脱尔Doolittle分解)U---上三角矩阵LU分解存在普通高斯消去法不被中断?LU分解22若A的所有顺序主子式不为零，则A存在唯一的LU分解.证：存在性由Gauss消去法可得；唯一性可用反证法证明.(LU分解的唯一性)定理1类似的，还可以得到定理2若A的所有顺序主子式不为零，则A存在唯一的克洛脱(Crout)分解:其中：L是下三角矩阵，U是单位上三角矩阵LU分解23计算LU分解利用矩阵乘法直接计算LU分解LU=A比较等式两边的第一行得：u1j=a1j比较等式两边的第一列得：比较等式两边的第二行

8、得：比较等式两边的第二列得：(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U的第一行L的第一列U的第二行L的第二列24计算LU分解第k步：此时U的前k-1行和L的前k-1列已经求出比较等式两边的第k行得：比较等式两边的第k列得：直到第n步，便可求出矩阵L和U的所有元素。(j=k