线性代数方程组的解法

上一页上一页下一页下一页湘潭大学数学与计算科学学院1第五章第五章 线性代数方程组的解法线性代数方程组的解法5.1 预备知识预备知识上一页上一页下一页下一页湘潭大学数学与计算科学学院2 求解线性方程组求解线性方程组 其中其中 且且。上一页上一页下一页下一页湘潭大学数学与计算科学学院3 利用利用 法则求解时存在的困难是：当方程法则求解时存在的困难是：当方程组的阶数组的阶数 很大时，计算量为很大时，计算量为常用计算方法常用计算方法:(1)直接解法：直接解法：它是一类精确方法，即若不考虑计它是一类精确方法，即若不考虑计算过程中的算过程中的舍入误差舍入误差，那么通过有限步运算可以获得，那么通过有限步运算可以获得方程解的方程解的精确结果精确结果.Gauss 逐步（顺序）消去法、逐步（顺序）消去法、Gauss主元素法、矩阵分解法等；主元素法、矩阵分解法等；上一页上一页下一页下一页湘潭大学数学与计算科学学院4 (2)迭代解法迭代解法：所谓迭代方法，就是构造某种：所谓迭代方法，就是构造某种极限过程极限过程去逐步去逐步逼近逼近方程组的解方程组的解.经典迭代法有经典迭代法有：迭代法、迭代法、迭代法、迭代法、逐次超松弛（逐次超松弛（SOR）迭代法等；）迭代法等；上一页上一页下一页下一页湘潭大学数学与计算科学学院5 向量空间及相关概念和记号向量空间及相关概念和记号 1 向量的范数向量的范数上一页上一页下一页下一页湘潭大学数学与计算科学学院6例例:设设求求根据定义根据定义:上一页上一页下一页下一页湘潭大学数学与计算科学学院7范数的等价性范数的等价性例如：例如：上一页上一页下一页下一页湘潭大学数学与计算科学学院8设设为为中的一个给定中的一个给定向量序列向量序列若对若对则称向量序列则称向量序列 收敛收敛于向量于向量 命题命题:当当时时这是因为这是因为2 向量序列的收敛问题向量序列的收敛问题上一页上一页下一页下一页湘潭大学数学与计算科学学院9利用向量范数的等价性及向量范数的连续性利用向量范数的等价性及向量范数的连续性,容易容易得到定理的证明得到定理的证明 上一页上一页下一页下一页湘潭大学数学与计算科学学院10对于对于 上的任何上的任何向量范数向量范数,我们可以定义我们可以定义矩阵范数矩阵范数.1.1.矩阵的范数矩阵的范数5.1.2 矩阵的一些相关概念及记号矩阵的一些相关概念及记号上一页上一页下一页下一页湘潭大学数学与计算科学学院11定理定理 矩阵的矩阵的从属范数从属范数具有下列具有下列基本性质基本性质：1），当且仅当，当且仅当 时，时，2)4)时时5)、定理中的性质 1),2)和 3)是一般范数所满足的基本性质，性质 4)、5)被称为相容性条件，一般矩阵范数并不一定满足该条件.上一页上一页下一页下一页湘潭大学数学与计算科学学院12三种从属范数计算：三种从属范数计算：（1）矩阵的）矩阵的1-范数（范数（列和范数列和范数）:（3）矩阵的）矩阵的2-范数范数:其中其中 :的最大特征值的最大特征值（2）矩阵的）矩阵的 -范数（范数（行和范数行和范数）:上一页上一页下一页下一页湘潭大学数学与计算科学学院13解：解：按定义按定义例例 已知矩阵已知矩阵 求求上一页上一页下一页下一页湘潭大学数学与计算科学学院14矩阵范数的矩阵范数的等价定理等价定理：对对 、，存在常数，存在常数 和和 ，使得：，使得：几种常用范数的等价关系：几种常用范数的等价关系：上一页上一页下一页下一页湘潭大学数学与计算科学学院152.谱半径：谱半径：此时此时若若 为为对称阵对称阵，（因为因为 ）上一页上一页下一页下一页湘潭大学数学与计算科学学院16关于矩阵的谱半径与矩阵的范数之间有如下关系.上一页上一页下一页下一页湘潭大学数学与计算科学学院17定义定义称称矩阵序列矩阵序列 是是收敛收敛的，的，如果如果存在存在 ，使得，使得 此时称此时称 为矩阵序列为矩阵序列 的极限的极限 记为记为矩阵序列矩阵序列 的的充分必要条件充分必要条件为为 3.矩阵级数的收敛性矩阵级数的收敛性上一页上一页下一页下一页湘潭大学数学与计算科学学院18上一页上一页下一页下一页湘潭大学数学与计算科学学院19 该定理将被应用于解方程组的扰动分析和Gauss消去法的舍入误差分析.上一页上一页下一页下一页湘潭大学数学与计算科学学院204 矩阵的条件数矩阵的条件数 上一页上一页下一页下一页湘潭大学数学与计算科学学院21上一页上一页下一页下一页湘潭大学数学与计算科学学院225 几种特殊矩阵几种特殊矩阵 且至少有一且至少有一 个使不等式严格成立，则称矩阵个使不等式严格成立，则称矩阵 为为按行对角占优矩阵按行对角占优矩阵。若。若 严格不等严格不等 式均成立，则称式均成立，则称 为为按行严格对角占优矩阵按行严格对角占优矩阵.类似地，可以给出矩阵类似地，可以给出矩阵 为为按列（严格）对角按列（严格）对角占优矩阵占优矩阵的定义的定义.上一页上一页下一页下一页湘潭大学数学与计算科学学院23证明证明 我们只证按行严格对角占优的情形，这时有从而 矛盾上一页上一页下一页下一页湘潭大学数学与计算科学学院24上一页上一页下一页下一页湘潭大学数学与计算科学学院255.2 Gauss消去法、矩阵分解消去法、矩阵分解上一页上一页下一页下一页湘潭大学数学与计算科学学院262.1 Gauss消去法消去法下面通过简单例子导出一般算法。下面通过简单例子导出一般算法。设给定方程组设给定方程组(1)上一页上一页下一页下一页湘潭大学数学与计算科学学院27乘以第一个方程，这样方程组（乘以第一个方程，这样方程组（1 1）(2)化为化为其中：其中：显然方程组（显然方程组（2）和原方程组（）和原方程组（1）等价）等价 若若，则以第，则以第个方程减去个方程减去 (1)上一页上一页下一页下一页湘潭大学数学与计算科学学院28 得到得到(3)其中其中依此方法继续下去，得到依此方法继续下去，得到以（以（2 2）的第）的第个方程个方程减去减去(2)上一页上一页下一页下一页湘潭大学数学与计算科学学院29（4）从（从（4）的最后一个方程组得到）的最后一个方程组得到其中其中上一页上一页下一页下一页湘潭大学数学与计算科学学院30再将再将代入（代入（4 4）倒数第二个方程，可得：）倒数第二个方程，可得：类似地，得到：类似地，得到：我们称将方程组（我们称将方程组（1）按以上步骤化为等价方程组）按以上步骤化为等价方程组（4）的过程为解线性方程组的）的过程为解线性方程组的消元过程消元过程 从（从（4）中得出解的过程称为高斯消去法的）中得出解的过程称为高斯消去法的回代过程回代过程（4）上一页上一页下一页下一页湘潭大学数学与计算科学学院31一般情形一般情形对于一般的对于一般的阶线性代数方程组阶线性代数方程组 即即1.消元过程消元过程首先消去第一列除首先消去第一列除 之外的所有元素，之外的所有元素，上一页上一页下一页下一页湘潭大学数学与计算科学学院32设设总可由消元过程得到系数矩阵为上三角阵的线性代数总可由消元过程得到系数矩阵为上三角阵的线性代数方程组，其第方程组，其第步的结果为步的结果为上一页上一页下一页下一页湘潭大学数学与计算科学学院33其中其中这里取这里取 2.回代过程回代过程若通过消元过程原方程组已化为等价的三角形若通过消元过程原方程组已化为等价的三角形方程组方程组上一页上一页下一页下一页湘潭大学数学与计算科学学院34且且 ,则逐步回代可得原方程组的解则逐步回代可得原方程组的解上一页上一页下一页下一页湘潭大学数学与计算科学学院35Gauss逐步消去法有如下的缺点逐步消去法有如下的缺点：任一主元任一主元 ，就无法做下去，就无法做下去任一任一 绝对值很小时绝对值很小时,也不行（舍入误差的影响大）也不行（舍入误差的影响大）2.2 Gauss主元素主元素消去法消去法下面我们讨论下面我们讨论列主元消去法列主元消去法.假设假设Gauss消去法的消元过程进行到消去法的消元过程进行到 第第 步，步，上一页上一页下一页下一页设设上一页上一页下一页下一页湘潭大学数学与计算科学学院37并令并令 为达到最大值为达到最大值 的最小行标的最小行标 ，则交换则交换 和和 中的第中的第 行和第行和第 行，行，再进行消元过程的第再进行消元过程的第 步步.这时每个乘子这时每个乘子 都满足都满足 可以防止有效数字大量丢失而产生误差可以防止有效数字大量丢失而产生误差.上一页上一页下一页下一页湘潭大学数学与计算科学学院38例例 用列主元消去法解如下方程组用列主元消去法解如下方程组 解解 对增广矩阵按列选主元再进行高斯消元对增广矩阵按列选主元再进行高斯消元 上一页上一页下一页下一页湘潭大学数学与计算科学学院39上一页上一页下一页下一页湘潭大学数学与计算科学学院40回代求解得回代求解得上一页上一页下一页下一页湘潭大学数学与计算科学学院41function x=magauss2(A,b,flag)%用途：列主元Gauss消去法解线性方程组Ax=b%格式：x=magauss(A,b,flag),A为系数矩阵,b为右端项,若flag=0,%则不显示中间过程，否则显示中间过程,默认为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上一页上一页下一页下一页湘潭大学数学与计算科学学院42%消元 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(k,k+1:n)*x(k+1:n)/A(k,k);end上一页上一页下一页下一页湘潭大学数学与计算科学学院43全主元消去法全主元消去法定义定义此时交换此时交换 和和 的行及的行及A的列，使主元位置的元素的列，使主元位置的元素的绝对值具有给出的最大值的绝对值具有给出的最大值 ，然后进行第然后进行第 步消元过程步消元过程 注意：因为有列的交换，因此未知量的注意：因为有列的交换，因此未知量的次序有改变，待消元过程结束时必须还原次序有改变，待消元过程结束时必须还原.多使用列主元消去法多使用列主元消去法.上一页上一页下一页下一页湘潭大学数学与计算科学学院44Gauss消去法的实质是将矩阵消去法的实质是将矩阵 分解为分解为其中其中 -单位下三角矩阵，单位下三角矩阵，-上三角矩阵上三角矩阵.事实上，线性方程组事实上，线性方程组经过经过 步消元过程后，有等价方程组步消元过程后，有等价方程组其中：其中：，而，而 和和 的形式为：的形式为：2.3 矩阵的三角分解与矩阵的三角分解与GaussGauss消去法的变形消去法的变形上一页上一页下一页下一页湘潭大学数学与计算科学学院45（1）可以直接验证可以直接验证 ，上一页上一页下一页下一页湘潭大学数学与计算科学学院46上一页上一页下一页下一页湘潭大学数学与计算科学学院47其中其中上一页上一页下一页下一页湘潭大学数学与计算科学学院48乘积乘积是下三角阵，且对角元全部等于是下三角阵，且对角元全部等于1 1 则则 也是对角元等于也是对角元等于1的下三角阵的下三角阵 用矩阵用矩阵 依次左乘原给方程组依次左乘原给方程组两边，得等价方程组两边，得等价方程组 则则其中其中上一页上一页下一页下一页湘潭大学数学与计算科学学院49由于由于 为上三角阵，记为上三角阵，记 ,于是得到于是得到(2)上一页上一页下一页下一页湘潭大学数学与计算科学学院50Gauss逐步消去法等价于下述过程：逐步消去法等价于下述过程：2.求解三角形方程组求解三角形方程组 （回代过程）（回代过程）.(注意上面的全部讨论中要求注意上面的全部讨论中要求 )上一页上一页下一页下一页湘潭大学数学与计算科学学院51比较等式两边对应元素算出比较等式两边对应元素算出Doolittle分解分解上一页上一页下一页下一页湘潭大学数学与计算科学学院52Doolittle分解计算顺序为分解计算顺序为 第一层第一层 第二层第二层 第三层第三层 上一页上一页下一页下一页湘潭大学数学与计算科学学院53Crout分解：分解：比较两边对应的元素，得比较两边对应的元素，得上一页上一页下一页下一页湘潭大学数学与计算科学学院54其中其中 、分别为单位下、上三角阵分别为单位下、上三角阵 例例实际上，进一步可以做分解实际上，进一步可以做分解上一页上一页下一页下一页湘潭大学数学与计算科学学院55首先我们来看一个命题首先我们来看一个命题:证明证明:我们对我们对A做分解做分解其中其中、分别为单位下、上三角阵分别为单位下、上三角阵 又由于又由于则则当当 为对称正定矩阵时，为对称正定矩阵时，A存在三角分解存在三角分解其中其中为下三角矩阵为下三角矩阵 1.对称正定阵的对称正定阵的Cholesky分解分解上一页上一页下一页下一页湘潭大学数学与计算科学学院56于是有于是有由于由于 正定，正定，故有故有 取取令令即得即得证毕证毕我们将上面的这种分解称为我们将上面的这种分解称为Cholesky分解分解.下面我们讨论下面我们讨论Cholesky分解的算法分解的算法.上一页上一页下一页下一页湘潭大学数学与计算科学学院57比较两边对应的元素，有：比较两边对应的元素，有：因因 正定，就有正定，就有，故，故以以 的第二行乘的第二行乘 的前两列的前两列 上一页上一页下一页下一页湘潭大学数学与计算科学学院58即得即得又可以解出又可以解出一般地，对一般地，对 有有由由 的正定性可知平方根中值的正定性可知平方根中值 为正的为正的 上一页上一页下一页下一页湘潭大学数学与计算科学学院59由矩阵乘法解得由矩阵乘法解得例例上一页上一页下一页下一页湘潭大学数学与计算科学学院60设线性方程组设线性方程组 的系数矩阵的系数矩阵 为三对角矩阵为三对角矩阵当当 的所有顺序主子矩阵非奇异时可作如下分解的所有顺序主子矩阵非奇异时可作如下分解 2 解三对角方程组的追赶法解三对角方程组的追赶法上一页上一页下一页下一页湘潭大学数学与计算科学学院61追赶法：追赶法：（1）分解（分解（Doolittle 分解）分解）对对 计算计算上一页上一页下一页下一页湘潭大学数学与计算科学学院62（2）解）解 （“追追”过程）过程）对对 计算计算（3）解）解 （“赶赶”过程）过程）对于对于 计算计算上一页上一页下一页下一页湘潭大学数学与计算科学学院63同样可以作同样可以作Crout分解：分解：对对 计算计算上一页上一页下一页下一页湘潭大学数学与计算科学学院64上一页上一页下一页下一页湘潭大学数学与计算科学学院65