数学线性代数方程组.pptx

《数学线性代数方程组.pptx》由会员分享，可在线阅读，更多相关《数学线性代数方程组.pptx（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 n阶线性代数方程组的一般形式解线性代数方程组的数值解法有：直接法，迭代法。第1页/共87页在没有舍入误差的情况下，经过有限次运算可以得到方程组的精确解的方法。线性代数方程组的直接解法/*Direct Method for Solving Linear Algebraic Systems*/求解Cramer法则:所需乘除法的运算量大约为(n+1)!+nn=20时，每秒1亿次运算速度的计算机要算30多万年！直接法第2页/共87页3.1 Gauss消去与矩阵LU分解一 Gauss消去1 直接法的关键思想如果方程组是“上三角方程组”或“下三角方程组”就可以很容易地求出方程组的解。因此，直接法的关键

2、思想就是如何把一般方程组约化为上/下三角方程。属于解方程的直接法第3页/共87页2 上三角方程组与回代过程第4页/共87页3 下三角方程组与前推过程第5页/共87页4 Gauss消去过程第6页/共87页则Gauss消去过程如下：该Gauss消去法为顺序高斯消去法第7页/共87页forforforGauss法的消元过程回代过程第8页/共87页顺序高斯消去法必须保证第k 步的akk0，因为它在消去过程和回代过程中起关键作用，所以称它为主元素。第9页/共87页例：用基本Gauss消元法求解下列方程组解：增广矩阵第10页/共87页第11页/共87页基本Gauss消元法的工作量消元过程：回代过程：加减法

3、的次数乘除法的次数第12页/共87页基本Gauss消元法的实现条件全不为零的充要条件是的顺序主子式都不等于零，即第13页/共87页小主元 可能导致计算失败例：在8位制计算机上解方程组要求用Gauss消去法计算。8个解：第14页/共87页主元素要作除数，其绝对值相对于被除数过小会影响到计算的精度，所以，我们可以采用5、列主元Gauss消去法解方程组除了“列主元消去法”，还有“全主元消去法”，但后者计算量过大，一般不用。思想每次消元之前，在剩余元素中选择绝对值最大的非零元素作为主元，然后经过换行换到主元位置第15页/共87页列主元消去法/*Column Pivoting Strategies*/S

4、tep k：第k步首先选择主元寻求 满足然后交换矩阵 的第 行和 行，再进行消元过程 第16页/共87页 算法:Gauss列主元消去算法求方程组Ax=b 的解.输入:增广矩阵An(n+1)=（A|b）.输出:近似解 xk=ak,n+1(k=1,2,n)或失败信息.消元过程 for k=1,2,n-1 do Step 1-Step 4 Step 1 寻找行号 ik,使得Step 2 如果 ，则交换第k行和ik行；否则转Step 7 第17页/共87页 算法:Gauss列主元消去算法（续）Step 3 for i=k+1,n 计算 Step 4 for j=k+1,n+1 计算回代过程Step 5

5、Step 6 for i=n-1,1 计算 Step 7 Output(系数矩阵奇异);/*不成功*/STOP.第18页/共87页例：用Gauss列主元消去法求解下列方程组解：首先写出增广矩阵第19页/共87页Step 1第20页/共87页消 元Step 2第21页/共87页消 元全主元消去法/*Complete Pivoting Strategies*/Step k：第k步选择主元寻求 和 满足然后交换矩阵 的第 行和 行，第 列和 列记录交换信息第22页/共87页二 LU分解1 矩阵的三角分解对方程组Ax=b的顺序Gauss消去过程的结果，就是把矩阵A分解成两个三角距阵L和U的乘积：A=L

6、U。利用这个特点可以进行线性方程组的直接三角分解法。第23页/共87页解方程组的直接三角分解法有3种形式：（1）A=LU（2）A=LU（3）A=LDU单位下三角阵上三角阵下三角阵单位上三角阵单位下三角阵对角阵单位上三角阵A的Doolittle分解A的Crout分解A的LDU分解第24页/共87页2 解方程组的直接三角分解法Ax=bLUx=b第25页/共87页Doolittle分解法本质它是基本Gauss消元法的一种等价变形 Gauss消元法的矩阵形式/*Matrix Form*/为上三角矩阵其中第26页/共87页 为单位下三角矩阵分解为单位下三角和上三角矩阵的乘积第27页/共87页设矩阵 分解

7、的计算公式根据矩阵的乘法，由 对应元素相等，得到第28页/共87页分解计算过程:Step1Step2Step3Step4Step5Step6Step2n-1Step2(n-1)先计算 的行再计算 的列依次交替进行第29页/共87页方程组求解的计算公式先求解方程组再求解方程组工作量第30页/共87页例8：用Doolittle分解法求解下列方程组解：系数矩阵第31页/共87页第32页/共87页3.2 乔列斯基（Cholesky）分解法(平方根法)当 为实对称正定矩阵时，三角分解法的变形。实对称正定矩阵的几个重要性质 A1 亦对称正定，且 aii 0 A 的顺序主子阵 Ak 亦对称正定 A 的特征值

8、 i 0 A 的全部顺序主子式 det(Ak)0（充要条件）第33页/共87页（Cholesky分解）如果 是正定矩阵，则存在唯一的对角元素为正数的下三角矩阵 ，使得 。证明：设则 的所有顺序主子式为正矩阵 存在Doolittle分解易证其中 为 的主对角元素，且有第34页/共87页单位上三角记由矩阵 的 分解的唯一性知：其中第35页/共87页思想Cholesky分解的计算公式设由 对应元素相等得第36页/共87页Cholesky分解公式第37页/共87页因对称性无需存储Step1Step2Step3Stepn的计算过程:逐 列 计 算元素仍然存放在矩阵 的相应位置上第38页/共87页例10：

9、用Cholesky分解法求解下列方程组解：系数矩阵为Step1Step2Step3第39页/共87页求解方程组求解方程组第40页/共87页 Cholesky分解法求解方程组中需说明的几个问题工作量：约为 分解的一半；不必选主元：的正定性和稳定性稳定性：是数值稳定的；缺陷：存在开平方运算。改进方法：分解改进的平方根法第41页/共87页改进的平方根法(/*Modified Square Rooting Method*/)当 时第42页/共87页令Step1Step2Step3时Stepn第43页/共87页例6：用改进的平方根法求解下列方程组解：系数矩阵为Step1Step2Step3第44页/共8

10、7页求解方程组求解方程组第45页/共87页 分解公式(算法3.3.2)：求解方程组等价方程组forforfor第46页/共87页先求解方程组再求解方程组方程组求解的实际计算公式：第47页/共87页3.3 向量范数与矩阵范数一 向量范数1 定义设向量xRn，若与x对应的 一个实值函数（并记为）|x|满足：|x|0，其中|x|=0当且仅当x=0,称为正定性；|kx|=|k|x|,kR,称为齐次性；|x+y|x|+|y|,且x,yRn,称为三角不等式。第48页/共87页例：设x=(2,-4,3)T,求|x|1,|x|2和|x|第49页/共87页第50页/共87页称为矩阵ATA的谱半径第51页/共87

11、页第52页/共87页 3.4线性代数方程组的迭代解法/*Iterative Method for Solving Linear Algebraic Systems*/求解迭代法从一个初始向量出发,按照一定的递推格式,产生逼近方程组的近似解序列。迭代法是一种逐次逼近的方法,与直接法比较,具有:程序简单,存储量小的优点。特别适用于求解系数矩阵为大型稀疏矩阵/*sparse matrices*/的方程组。思路与解f(x)=0 的不动点迭代相似，将方程组等价改写成 形式，从而建立迭代格式，从 出发，生成迭代序列第53页/共87页二、Jacobi迭代法第54页/共87页2 J法的迭代矩阵B称为迭代矩阵，

12、f称为常数项 第55页/共87页二 Gauss-Seidel迭代第56页/共87页2、GS法迭代矩阵一般情况下，迭代公式用来计算x的值和求迭代矩阵，迭代矩阵用来分析迭代是否收敛。第57页/共87页第58页/共87页J法适用于并行计算，GS法适用于串行计算，并且所需要的存储空间较小。第59页/共87页3.5 迭代法的分析第60页/共87页第61页/共87页第62页/共87页第63页/共87页由该定理可知,只要迭代矩阵的谱半径小于1,则J法和GS法收敛.第64页/共87页第65页/共87页第66页/共87页定理3.2：如果A 是严格对角占优矩阵，则它一定非奇异。第67页/共87页第68页/共87页

13、定理3.3：如果方程组的系数矩阵A 是严格对角占优的，则对任意初始近似值，Jacobi迭代法和G-S迭代法均收敛。证明：第69页/共87页第70页/共87页第71页/共87页3.6 超松弛(SOR)迭代法/*Overrelaxation Iteration*/一、超松弛(SOR)迭代法思想类似于G-S迭代法的改进方法，利用第k次迭代值和第k+1次的G-S迭代值作加权平均G-S迭代法的计算公式：作加权平均第72页/共87页超松弛(SOR)迭代法的分量形式：其中 称为松弛因子；时即为G-S迭代SOR迭代法的迭代矩阵：记第73页/共87页超松弛(SOR)迭代法的迭代公式迭代矩阵其中例4：写出SOR迭

14、代法求解下列方程组的迭代格式第74页/共87页解：SOR迭代法的迭代公式取初始向量选取不同的 值进行计算，结果见下表第75页/共87页 要求要求 精度精度迭代迭代次数次数 0.001 12(3.0012790 3.9989342 -5.0002665)0.0001 16(3.0001952 3.9998374 -5.0000407)0.00001 21(3.0000186 3.9999845 -5.0000039)0.001 12(3.0020191 3.9982705 -5.0004444)0.0001 18(3.0001673 3.9998567 -5.0000368)0.00001 23

15、(3.0000210 3.9999820 -5.0000046)0.001 8(2.9997451 4.0000653 -4.9998924）0.0001 10(2.9999853 4.0000031 -4.9999935）0.00001 12(2.9999993 4.0000001 -4.9999996）0.001 13(3.0006104 4.0001741 -5.0007434)0.001 151(2.9995106 4.0017780 -5.0027919）方 程 组 的 近 似 解的值第76页/共87页求解方程组 的SOR法收敛的必要条件是：二、SOR迭代法的收敛性：设 为对称正定矩

16、阵，且则求解方程组 的SOR法收敛。第77页/共87页3.7 线性方程组的条件对方程组的右端b作一个”微小”变化考虑系数矩阵及右端项的微小变化对方程解的影响。第78页/共87页如果对系数矩阵作”微小”改变第79页/共87页如何评价方程组的“好坏”？第80页/共87页分别考虑右端项及系数矩阵变化对解的影响|A-1|A|起“放大系数”的作用第81页/共87页第82页/共87页定义3.1 设A为非奇异矩阵，称 cond(A)=|A-1|A|为矩阵A的条件数。如果矩阵A的条件数 cond(A)相对大，则称A为病态矩阵，对应的方程组Ax=b为病态方程。否则，称A是良态矩阵。第83页/共87页定理3.6 对任意的非奇异矩阵 A，cond(A)是由任意的矩阵范数定义的条件数，则第84页/共87页第85页/共87页第86页/共87页感谢您的观看。第87页/共87页