线性代数方程组的解法.pptx

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

1、1 求解线性方程组求解线性方程组 其中其中 且且。第1页/共65页2 利用利用 法则求解时存在的困难是：当方程法则求解时存在的困难是：当方程组的阶数组的阶数 很大时，计算量为很大时，计算量为常用计算方法常用计算方法:(1)直接解法：直接解法：它是一类精确方法，即若不考虑计算过程中的它是一类精确方法，即若不考虑计算过程中的舍入误差舍入误差，那么通，那么通过有限步运算可以获得方程解的过有限步运算可以获得方程解的精确结果精确结果.Gauss 逐步（顺序）消去法、逐步（顺序）消去法、Gauss主元素法、矩阵分解法等；主元素法、矩阵分解法等；第2页/共65页3 (2)迭代解法迭代解法：所谓迭代方法，就是

2、构造某种：所谓迭代方法，就是构造某种极限过程极限过程去逐步去逐步逼近逼近方程组方程组的解的解.经典迭代法有经典迭代法有：迭代法、迭代法、迭代法、迭代法、逐次超松弛（逐次超松弛（SOR）迭代法等；）迭代法等；第3页/共65页4 向量空间及相关概念和记号 1 向量的范数第4页/共65页5例例:设设求求根据定义根据定义:第5页/共65页6范数的等价性例如：第6页/共65页7设设为为中的一个给定中的一个给定向量序列向量序列若对若对则称向量序列则称向量序列 收敛收敛于向量于向量 命题命题:当当时时这是因为这是因为2 向量序列的收敛问题第7页/共65页8利用向量范数的等价性及向量范数的连续性利用向量范数的

3、等价性及向量范数的连续性,容易容易得到定理得到定理5.2的证明的证明 第8页/共65页9对于对于 上的任何上的任何向量范数向量范数,我们可以定义我们可以定义矩阵范数矩阵范数.1.1.矩阵的范数矩阵的范数矩阵的一些相关概念及记号第9页/共65页10定理定理5.3 矩阵的矩阵的从属范数从属范数具有下列具有下列基本性质基本性质：1），当且仅当，当且仅当 时，时，2)4)时时5)、定理5.3中的性质 1),2)和 3)是一般范数所满足的基本性质，性质 4)、5)被称为相容性条件，一般矩阵范数并不一定满足该条件.第10页/共65页11三种从属范数计算：三种从属范数计算：（1）矩阵的）矩阵的1-范数（范数

4、（列和范数列和范数）:（3）矩阵的）矩阵的2-范数范数:其中其中 :的最大特征值的最大特征值（2）矩阵的）矩阵的 -范数（范数（行和范数行和范数）:第11页/共65页12解：解：按定义按定义例例 已知矩阵已知矩阵 求求第12页/共65页13矩阵范数的矩阵范数的等价定理等价定理：对对 、，存在常数，存在常数 和和 ，使得：，使得：几种常用范数的等价关系：几种常用范数的等价关系：第13页/共65页142.谱半径：谱半径：此时此时若若 为为对称阵对称阵，（因为因为 ）第14页/共65页15关于矩阵的谱半径与矩阵的范数之间有如下关系.第15页/共65页16定义定义5.35.3 称称矩阵序列矩阵序列 是

5、是收敛收敛的，的，如果如果存在存在 ，使得，使得 此时称此时称 为矩阵序列为矩阵序列 的极限的极限 记为记为矩阵序列矩阵序列 的的充分必要条件充分必要条件为为 3.矩阵级数的收敛性第16页/共65页17第17页/共65页18 该定理将被应用于解方程组的扰动分析和Gauss消去法的舍入误差分析.第18页/共65页194 矩阵的条件数 第19页/共65页20第20页/共65页215 几种特殊矩阵 且至少有一且至少有一 个使不等式严格成立，则称矩阵个使不等式严格成立，则称矩阵 为为按行对角占优矩阵按行对角占优矩阵。若。若 严格不等严格不等 式均成立，则称式均成立，则称 为为按行严格对角占优矩阵按行严

6、格对角占优矩阵.类似地，可以给出矩阵类似地，可以给出矩阵 为为按列（严格）对角按列（严格）对角占优矩阵占优矩阵的定义的定义.第21页/共65页22证明 我们只证按行严格对角占优的情形，这时有从而 矛盾第22页/共65页23第23页/共65页245.2 Gauss消去法、矩阵分解第24页/共65页252.1 Gauss消去法下面通过简单例子导出一般算法。下面通过简单例子导出一般算法。设给定方程组设给定方程组(1)第25页/共65页26乘以第一个方程，这样方程组（乘以第一个方程，这样方程组（1 1）(2)化为化为其中：其中：显然方程组（显然方程组（2）和原方程组（）和原方程组（1）等价）等价 若若

7、，则以第，则以第个方程减去个方程减去 (1)第26页/共65页27 得到得到(3)其中其中依此方法继续下去，得到依此方法继续下去，得到以（以（2 2）的第）的第个方程个方程减去减去(2)第27页/共65页28（4）从（从（4）的最后一个方程组得到）的最后一个方程组得到其中其中第28页/共65页29再将再将代入（代入（4 4）倒数第二个方程，可得：）倒数第二个方程，可得：类似地，得到：类似地，得到：我们称将方程组（我们称将方程组（1）按以上步骤化为等价方程组）按以上步骤化为等价方程组（4）的过程为解线性方程组的）的过程为解线性方程组的消元过程消元过程 从（从（4）中得出解的过程称为高斯消去法的）

8、中得出解的过程称为高斯消去法的回代过程回代过程（4）第29页/共65页30一般情形一般情形对于一般的对于一般的阶线性代数方程组阶线性代数方程组 即即1.消元过程消元过程首先消去第一列除首先消去第一列除 之外的所有元素，之外的所有元素，第30页/共65页31设设总可由消元过程得到系数矩阵为上三角阵的线性代数总可由消元过程得到系数矩阵为上三角阵的线性代数方程组，其第方程组，其第步的结果为步的结果为第31页/共65页32其中其中这里取这里取 2.回代过程回代过程若通过消元过程原方程组已化为等价的三角形若通过消元过程原方程组已化为等价的三角形方程组方程组第32页/共65页33且且 ,则逐步回代可得原方

9、程组的解则逐步回代可得原方程组的解第33页/共65页34Gauss逐步消去法有如下的缺点逐步消去法有如下的缺点：任一主元任一主元 ，就无法做下去，就无法做下去任一任一 绝对值很小时绝对值很小时,也不行（舍入误差的影响大）也不行（舍入误差的影响大）2.2 Gauss主元素消去法下面我们讨论下面我们讨论列主元消去法列主元消去法.假设假设Gauss消去法的消元过程进行到消去法的消元过程进行到 第第 步，步，第34页/共65页设设第35页/共65页36并令并令 为达到最大值为达到最大值 的最小行标的最小行标 ，则交换则交换 和和 中的第中的第 行和第行和第 行，行，再进行消元过程的第再进行消元过程的第

10、 步步.这时每个乘子这时每个乘子 都满足都满足 可以防止有效数字大量丢失而产生误差可以防止有效数字大量丢失而产生误差.第36页/共65页37例例 用列主元消去法解如下方程组用列主元消去法解如下方程组 解解 对增广矩阵按列选主元再进行高斯消元对增广矩阵按列选主元再进行高斯消元 第37页/共65页38第38页/共65页39回代求解得回代求解得第39页/共65页40%magauss2.mfunction x=magauss2(A,b,flag)%用途：列主元Gauss消去法解线性方程组Ax=b%格式：x=magauss(A,b,flag),A为系数矩阵,b为右端项,若flag=0,%则不显示中间过程

11、，否则显示中间过程,默认为0,x为解向量if nargink t=A(k,:);A(k,:)=A(p,:);A(p,:)=t;t=b(k);b(k)=b(p);b(p)=t;end第40页/共65页41%消元 m=A(k+1:n,k)/A(k,k);A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-m*A(k,k+1:n);b(k+1:n)=b(k+1:n)-m*b(k);A(k+1:n,k)=zeros(n-k,1);if flag=0,Ab=A,b,endend%回代x=zeros(n,1);x(n)=b(n)/A(n,n);for k=n-1:-1:1 x(k)=(b(k)-A

12、(k,k+1:n)*x(k+1:n)/A(k,k);end第41页/共65页42全主元消去法全主元消去法定义定义此时交换此时交换 和和 的行及的行及A的列，使主元位置的元素的列，使主元位置的元素的绝对值具有给出的最大值的绝对值具有给出的最大值 ，然后进行第然后进行第 步消元过程步消元过程 注意：因为有列的交换，因此未知量的次序有改变，待消元注意：因为有列的交换，因此未知量的次序有改变，待消元过程结束时必须还原过程结束时必须还原.多使用列主元消去法多使用列主元消去法.第42页/共65页43Gauss消去法的实质是将矩阵消去法的实质是将矩阵 分解为分解为其中其中 -单位下三角矩阵，单位下三角矩阵，

13、-上三角矩阵上三角矩阵.事实上，线性方程组事实上，线性方程组经过经过 步消元过程后，有等价方程组步消元过程后，有等价方程组其中：其中：，而，而 和和 的形式为：的形式为：2.3 矩阵的三角分解与矩阵的三角分解与GaussGauss消去法的变形消去法的变形第43页/共65页44（1）可以直接验证可以直接验证 ，第44页/共65页45第45页/共65页46其中其中第46页/共65页47乘积乘积是下三角阵，且对角元全部等于是下三角阵，且对角元全部等于1 1 则则 也是对角元等于也是对角元等于1的下三角阵的下三角阵 用矩阵用矩阵 依次左乘原给方程组依次左乘原给方程组两边，得等价方程组两边，得等价方程组

14、 则则其中其中第47页/共65页48由于由于 为上三角阵，记为上三角阵，记 ,于是得到于是得到(2)第48页/共65页49Gauss逐步消去法等价于下述过程：逐步消去法等价于下述过程：2.求解三角形方程组求解三角形方程组 （回代过程）（回代过程）.(注意上面的全部讨论中要求注意上面的全部讨论中要求 )第49页/共65页50比较等式两边对应元素算出比较等式两边对应元素算出Doolittle分解分解第50页/共65页51Doolittle分解计算顺序为分解计算顺序为 第一层第一层 第二层第二层 第三层第三层 第51页/共65页52Crout分解：分解：比较两边对应的元素，得比较两边对应的元素，得第

15、52页/共65页53其中其中 、分别为单位下、上三角阵分别为单位下、上三角阵 例例实际上，进一步可以做分解实际上，进一步可以做分解第53页/共65页54首先我们来看一个命题首先我们来看一个命题:证明证明:我们对我们对A做分解做分解其中其中、分别为单位下、上三角阵分别为单位下、上三角阵 又由于又由于则则当当 为对称正定矩阵时，为对称正定矩阵时，A存在三角分解存在三角分解其中其中为下三角矩阵为下三角矩阵 1.对称正定阵的Cholesky分解第54页/共65页55于是有于是有由于由于 正定，正定，故有故有 取取令令即得即得证毕证毕我们将上面的这种分解称为我们将上面的这种分解称为Cholesky分解分

16、解.下面我们讨论下面我们讨论Cholesky分解的算法分解的算法.第55页/共65页56比较两边对应的元素，有：比较两边对应的元素，有：因因 正定，就有正定，就有，故，故以以 的第二行乘的第二行乘 的前两列的前两列 第56页/共65页57即得即得又可以解出又可以解出一般地，对一般地，对 有有由由 的正定性可知平方根中值的正定性可知平方根中值 为正的为正的 第57页/共65页58由矩阵乘法解得由矩阵乘法解得例例第58页/共65页59设线性方程组设线性方程组 的系数矩阵的系数矩阵 为三对角矩阵为三对角矩阵当当 的所有顺序主子矩阵非奇异时可作如下分解的所有顺序主子矩阵非奇异时可作如下分解 2 解三对角方程组的追赶法第59页/共65页60追赶法：追赶法：（1）分解（分解（Doolittle 分解）分解）对对 计算计算第60页/共65页61（2）解）解 （“追追”过程）过程）对对 计算计算（3）解）解 （“赶赶”过程）过程）对于对于 计算计算第61页/共65页62同样可以作同样可以作Crout分解：分解：对对 计算计算第62页/共65页63第63页/共65页64第64页/共65页湘潭大学数学与计算科学学院65感谢您的观看！第65页/共65页