第三章 线性方程组的数值解法

《第三章 线性方程组的数值解法》由会员分享，可在线阅读，更多相关《第三章 线性方程组的数值解法（96页珍藏版）》请在金锄头文库上搜索。

1、,n阶线性代数方程组的一般形式为：,第三章 线性方程组的数值解法,问题的提出：,写成矩阵-向量形式,若矩阵 非奇异，即 的行列式 ，根据克莱姆（Gramer）法则，方程组有唯一 解：,其中 为系数矩阵， 为解向量， 为右端常向量。,其中 表示 ， 表示 中第 列换成 后所得的行列式。,当阶数较高时用这种方法求解是不现实的。 阶行列式有 项，每项又是 个数的乘积。对较大的 ，其计算量之大，是一般计算机难以完成的。而且，这时的舍入误差对计算结果的影响也较大。,直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差） 迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法

2、 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题,3.1 消去法,消去法的基本思想：是通过将一个方程乘或除以某个常数，以及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出所求的解。,消去法在线性代数中已有详细的讨论，在此只给出一些说明以及算法的具体描述。,高斯消去法属于直接法，一般由“消元过程”和“回代过程”两部分组成。先举几个简单实例，再对一般n阶方程组说明高斯消去法的基本思想。,消去法,3.1 高斯消去法 按自然顺序进行的消元法,例 1 用高斯消元法求解方程组,解 用第一个方程削去后两个方程中的 得,再用

3、第1个方程消去第2个方程中的 得,最后，经过会代求得原方程组的解为,例 2 解方程组,解：消元,回代得,消去法,下面讨论一般 n 阶线性方程组的高斯消去法。 记 为 ， 和 的元素分别记为 和 ， ，系数上标 代表第1次消元之前的状态。 第1次消元时，设 对每行计算乘数,用 乘以第1个方程，加到第 个方程，消去第 2个方程到第 个方程的未知数 ，得 即:,其中：,第 次消元 时，设第 次消元已完成，即有 其中： 设 ，计算乘数,只要 ，消元过程就可以进行下去，直到经过 消元之后，消元过程结束，得 也即,这是一个与原方程组等价的上三角形方程组。把经过 n-1次消元将线性方程组化为上三角形方程组的

4、计算过程称为消元过程。,当 时，对上三角形方程组自下而上逐步回代解方程组，计算 ,即 ,称为各次消元的主元素， 主元素所在的行称为主行。,高斯消去法的计算步骤为： 1消元过程 设 ，对 ，计算 2回代过程,综上所述，高斯消去法的框图如图3-1所示。从中可看出高斯消去法的计算机运算和存储方式的特点： 1按消元规则进行运算后，对角线以下元素为0。故对于对角线以下元素不用作计算，减小了计算量。,3对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元。,4回代后的数值仍放在常数项存储单元 这时 单元中存放的就是输出值,定理2 Ax=b 可用高 斯消元法求解的充分必要条件是：系数矩阵 A 的各

5、阶顺序主子式均不为零。,高斯消元法的条件,定理1 如果在消元过程中A的主元素 (k=1,2,n) ,则可通过高斯消元法求出Ax=b 的解。,引理 A的主元素 (k=1,2,n) 的充要条件是矩阵A的各阶顺序主子式不为零，即,定理：高斯消去法求解 阶线性方程组共需乘除法次数近似为 。 证明：见书P64,高斯消去法的计算量,例 1 解方程组,解法一 用高斯消元法求解（取5位有效数字），用第 一个方程消去第二个方程中的,3.1.2 高斯主元素消元法,因而再回代，得,而精确值为 显然该解与精确值相差太远，为了控制误差，采用另一种消元过程。,解法二 为了避免绝对值很小的元素作为主元，先交换两个方程，得到

6、,再回代，解得,结果与准确解非常接近。这个例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。,为避免上述错误，可在每一次消元之前增加一个选主元的过程，将绝对值大的元素交换到主对角线的位置。根据交换的方法可分成全选主元和列选主元两种方法。,列主元素消元法,列选主元是当变换到第k 步时，从k列的 及以下的各元素中选取绝对值最大的元素，然后通过行交换将其交换到 的位置上。交换系数矩阵中的两行（包括常数项），相当于两个方程的位置交换了。,例：求解线性方

7、程组,解法一：用列主元素消元法，方程组增广矩阵为：,交换1、3行（列选主）,消元,消元,回代计算解为,选主元,全选主元素消元法,全选主元是当变换到第k 步时，从右下角 n-k+1阶子阵中选取绝对值大的元素，然后通过行交换与列交换将其交换到a kk 的位置上，并且保留交换的信息，以供后面调整解向量中分量的次序时使用。,交换1、3行 交换1、3列,回代计算得,从而原方程的解为,消元,消元,比较而言,Gauss顺序消去法条件苛刻,且数值不稳定; Gauss全主元消去法工作量偏大，算法复杂；对于Gauss-Jordan消去法形式上比其他消元法简单，且无回代求解，但计算量大。因此从算法优化的角度考虑，

8、Gauss列主元消去法比较好。,消去法小节,3.2 矩阵三角分解法,3.2.1 矩阵三角分解原理 应用高斯消去法解 阶线性方程 经过 步消去后得出一个等价的上三角形方程组 ，对上三角形方程组用逐步回代就可以求出解来。这个过程也可通过矩阵分解来实现。 将非奇异阵分解成一个下三角阵 和上三角阵 的乘积 ： 称为对矩阵 的三角分解，又称 分解。,高斯消去法解线性代数方程组的一种变形解法。,杜里特尔分解：把 分解成一个单位下三角阵 和一个上三角阵 的乘积。 克劳特分解: 把 分解成一个下三角阵 和一个单位上三角阵 的乘积。,杜里特尔分解 A=LU,杜里特尔分解,杜里特尔分解(一般算法),由矩阵乘法规则

9、,即：,由此可得 的第一行元素和 的第一列元素,当已得出 的前 行元素和 的前 列元素，则对于 ，由,又可得计算 的第 行元素和 的第 列元素的公式:,所以,矩阵三角分解算法总结：,有了矩阵 A 的LU分解计算公式，当求解线性方程组 时，等价于求解 。这时可归结为利用递推计算相继求解两个三角形方程组（系数矩阵为三角矩阵）。用顺代，由 求出 ，再利用回代，由 求出 。,3.2.2 解线性方程组的三角分解法,用杜里特尔三角分解法解线性方程组 的计算方法：,克劳特分解求方程组步骤：略,其它矩阵分解法求解特殊的线性方程组：,平方根法：主要用于求解正定矩阵的线性方程组 追赶法：主要用于求解特殊矩阵的三对

10、角方程组 见书 P78P87,用LU 直接分解的方法求解线性方程组的计算量为 ，和高斯消去法的计算量的数量级基本相同。,消去法和矩阵三角分解法比较,当方程组系数矩阵不变，只有右侧向量b变化时，用LU分解法比消去法速度快。因为右侧向量b的改变不影响LU的变化。,高斯消去法和LU分解法是等价的，其关键是把一般方程组变为三角方程组，只是实现途径不同。,向量收敛的定义：,3.6 迭代法,生成向量序列 x(k) ，若,迭代法基本思想：,将方程组 Ax=b ( |A|0 ) 转化为与其等价的方程组,x = Bx+f,雅可比迭代法,对线性方程组可以建立不同的迭代格式。下面介绍构造迭代格式的几种常用方法，雅克

11、比迭代法和高斯塞德尔迭代法。,设方程组,分别从上式n个方程中分离出n个变量，如下：,等价方程组,建立迭代格式,称为雅可比(Jacobi)迭代法又称简单迭代法。,高斯塞德尔迭代法,或缩写为,称为高斯塞德尔（Gauss Seidel）迭代法。,例1 用雅可比迭代法解方程组,雅克比迭代格式,Gauss-Seidel,迭代格式为,例2 用GaussSeidel 迭代法解上题。,取 x(0)=(0,0,0)T 计算如下：,以上介绍的两种迭代法，一般地说，高斯塞德尔比雅克比要好，但也不完全是这样。,关于迭代法的一些问题：,为了使迭代法计算加速，可采用松弛法。（略）,迭代法存在收敛性问题。（略）,3.3 向

12、量与矩阵的范数,问题的提出,向量范数概念是三维欧氏空间中向量长度概念的推广,在数值分析中起着重要作用.,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对 （n维向量空间）中向量及 （ 维矩阵空间）中矩阵的“大小”及“距离”引进某种度量向量与矩阵范数的概念.,平面向量 x 大小：用 距离 反映。,3.3 向量与矩阵的范数,引入范数的目的：,实数大小：用绝对值反映,复数大小：用模反映,高维空间向量 x “大小” 用 反映？,将度量长度数值的计算方法引入高维空间，用来反映空间向量的大小，就是范数的概念。,为了研究线性方程组近似解的误差估计和迭代法的收敛性等。,3.3.1 向量的范数,由

13、定义可知，向量 的范数 是按一定规律与 对应的实数，该实数的值没有确定，但只要满足这三个条件，这个实数就是向量 的一种范数。因此定义中的三个条件称为范数公理。,当 时，,向量范数 有如下性质,证：利用条件，有,证：,它们分别叫做向量的-范数、1-范数、2-范数、p -范数（0p+）。 p -范数是以上范数的统一表达形式。,常用的向量范数: 满足定义的范数不是唯一的.,设 x = ( x1 , x2 , , xn)T ，常用的向量范数有,对于范数，有 当 时，有 ， 只有当 时，才有 对任意实数 ，因为 ，所以 。 对任意向量 ，有,因此 是n维空间的一种范数,例：范数的证明,不难证明这几种范数

14、满足下述关系,事实上，对 Rn 上任意两种向量范数 |x| , |x| ，都存在与 x 无关的正常数 c1 , c2 使,这种性质称为向量范数的等价性。,按不同方式规定的范数,其值一般不同。但在各种范数下考虑向量序列收敛性的结论是一致的。即向量序列如对某一种范数收敛则对其它范数也收敛，且有相同的极限。这样，在研究某一具体问题时，可以选择一较易简单的范数。,矩阵范数是用于定义矩阵“大小”的量。 由于在大多数与估计误差有关的问题中,矩阵和向量的乘积经常出现,所以希望引进一种矩阵的范数,它与向量范数有某种关系。,3.3.2 矩阵的范数,矩阵范数的性质： ,且仅当 时， ； 对任意实数 ， ； 对同维

15、方阵 ，有:,相容性条件： 由矩阵范数的定义可直接得到 ，即有 ，称为相容性条件。即所给的矩阵范数与向量范数是相容的。,证明 p92,矩阵范数与向量范数的关系：,证明：,矩阵范数与向量范数的关系：,常用的矩阵范数有（矩阵范数的求取）,它们分别叫做矩阵的-范数、1-范数。,解,验证相容性,3.4 方程组的性态,3.4.1 方程组的性态和矩阵的条件数,例 1 解方程组 其中,现用绝对精确的计算（即不带任何舍入误差的计算） 求解，可以看出,此时，我们发现对于两组不同的自由项,它的差只有,而所得解 与 之差却是,两组不同的右端其分量之差不过是 可是解的差高 达 之1860倍像这样的方程组或矩阵A 就叫做病态的,定义1 若方程组 Ax=b 的系数矩阵 A 或右端向量 b 的微小变化（小扰动）引起解产生巨大变化,则称此方程组为病态方程组; A称为病态矩阵, 否则称为良态方程组, A 称为良态矩阵。,定理：设 非奇异， ，且 则,