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

《chapter2解线性方程组的直接法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章解线性方程组的直接法深圳大学计算机系12.1引言n元方程组的一般表示：矩阵表示：Ax=b2线性方程组的应用递归方程求解—通解代入初始数据，解线性方程组实际应用中—经济（线性规划）、科学计算等对线性方程组的研究，中国比欧洲至少早1500年，记载在公元初《九章算术》方程章中。3解线性方程组的方法线性方程组的数值解法分为直接法和迭代法直接法：经过有限步计算就能得到方程组“准确解”的方法。如消元法及其派生方法。迭代法：是一种逐次逼近法，从一个假设解开始，通过一系列的迭代求解，最后产生满足精度要求的

2、近似解的方法。如Jacobi迭代法，Seidel迭代法。本章主要学习解线性方程组的直接法。42.2Guass消元法1、三角形方程组的解—回代法上三角方程组的一般形式：上三角方程组的解：5下三角形方程组的解—回代法下三角方程组的一般形式：下三角方程组的解：6例1：用回代法解线性方程组解：x3=2x2=(-4+42)/0.5=8x1=-13三角形方程组求解例7Guass消元法2、Gauss消元法基本思想：对方程组逐个消元，化为一个同解上三角方程组——消元过程；然后用回代法求解—回代过程。8Guass

3、消元法得到同解方程组的消元依据：9消元顺序：Guass消元法10Guass消元法11例2：用Gauss消元法解线性方程组。①2233②4771③-245-7①2233②031-5③068-4=②-①(4/2)=③-①(-2/2)①2233②031-5③0066=③-②(6/3)Guass消元法例12Guass消元法效率及不足程序实现：二维数组存储增广矩阵一维数组x复杂度分析：O(n3)O(n3/3)Guass消元法的不足:(1)aii=0时无法继续消元;(2)aii很小时，aji/aii很大，

4、产生舍入误差，解失真。Cramer法则132.3Gauss列主元消元法主元消元法原理：在第i步消元前，按照某种策略，选取ari(r=i,i+1,…,n)作为枢纽（该数称为主元)，并进行方程位置的调整，再进行消元。列主元消元法：在第i步消元前，选取中绝对值最大的作为主元。Guass消元中位于主对角线（i，i）位置上的元素称为主元。14Guass列主元消元法例例3：用Gauss消元和列主元法解线性方程组。解:[Guass]方程组的准确解为x=(9998/9999,10000/9999)T.小主元a1

5、1回代求解x2=1.0000,x1=0.0000.计算结果相当糟糕.原因:求行乘数时用了”小主元”0.0001作除数.15回代得：x=(1.0000,1.0000)T与准确解x=(9998/9999,10000/9999)T相差不大。Guass列主元消元法例解:[列主元]若上题在求解时将1,2行交换,即主元a1116Guass列主元消元法的程序实现程序实现：二维数组存储增广矩阵（Ab），一维数组x、一维数组p={1,2,…,n}—记录方程组中方程顺序。第i(i=1,2,…,n-1)步主元消元①选

6、取ri，满足a[p[r]][i]a[p[j]][i],其中j=i,i+1,…,n②若a[p[r]][i]<ε，方程无解，退出。③若ir，p[i]p[r]④以a[p[i]][i]为枢纽，消去a[p[j]][i],j=i+1,…,n复杂度分析：O(n3)17消元法的计算中断注意:若A非奇,总可通过带有行交换或不带有行交换的消元过程,将A化成非奇三角矩阵。因此,回代求解过程也可进行到底。但实际中,A是否非奇异难以判定。算法应考虑:1、消元过程某一步找不到非零元,于是计算中断。2、消元可进行到底

7、,但,回代求解过程无法进行.算法设计要考虑以上情况,给出计算中断的信息.18列主元算法在实际中应用较广。“全面选主元”算法：即在第k步消元前，求ap,q=maxai,j(i,j=k+1,…,n);交换i与p行，j与q列，把ap,q作为主元；交换xj与xp。误差分析与数值试验证明：“全面选主元”消去法是数值“稳定的”.关于主元消元法19行变换相当于左乘初等矩阵Gauss消元过程可以用矩阵乘法实现.分为两种情况:1.不带行交换的消元过程消元的每一步等价于左乘初等下三角矩阵，即：对k=1,有其中2.4

8、消元过程与系数矩阵的分解20第k次消元有即不带行交换的消元过程21因此,消元完成后,有故从而不带行交换的消元过程22即：不带行交换的消元过程23不带行交换的消元过程顺序主元且:24定义：称A=LU为矩阵A的LU分解或三角分解。当L为单位下三角矩阵时，称为Doolittle分解。当U为单位上三角矩阵时，称为Crout分解。问题：矩阵A存在LU分解（即Gauss消去法可以执行）的条件是什么？不带行交换的消元过程25解:由上述分析不难得到：不带行交换的消元过程26Gauss消去法可以执行定理2.1:[