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

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

1、3.1 问题的提出 在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的插值问题，经济运行中的投入产出问题以及大地测量、机械与建筑结构的设计计算问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的求解对于实际问题是极其重要的。,第3章 线性方程组解法,常见的线性方程组是方程个数和未知量个数相同的n阶线性方程组，一般形式为,简记为 Ax=b，其中,( 3.1 ),一般b0, 当系数矩阵A非奇异(即detA0) 时，方程组（3.1）有惟一解。,线性方程组的数值解法一般有两

2、类： 直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。 迭代法: 就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解),3.2 消去法,3.2.1 三角方程组的解法 先用一个简单实例来说明Gauss法的基本思想 例3.1 解线性方程组,3.2.2 高斯消去法 我们知道,线性方程组(3.1)用矩阵形式表示为,( 3.3 ),解线性方程组（3.1）的高斯（Gauss）消去法的消元过程就

3、是对( 3.3 )的增广矩阵进行行初等变换。记, 消元过程,高斯消去法的消元过程由n-1步组成： 第1步 设 ,把(3.3)中的第一列中元素 消为零,令,用 乘以第1个方程后加到第 个方程上去,消去 第2n个方程的未知数 ,得到 即,第k步 （k=2,3,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组,记,只要 ,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,即,(3.7),（2）回代过程 就是对上三角方程组（3.7）自下而上逐步回代解方程组计算，即,（3）高斯消去法的计算步骤： 消元过程;设 计算, 回代过

4、程,(4) Gauss消去法计算量 ,消元计算: 第k 步 除法次数： n-k 求消元因子 乘法次数： (n-k)(n-k+1) 消元 第k 步共： (n-k)(n-k+2) 消元过程需要 回代计算: 对方程组的高斯消元法一共,方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A的结果。事实上，第1列消元将A(1)=A化为A(2)，若令：,则根据距阵左乘有L1A(1)=A(2),(5)高斯消去法的适用条件 (6)高斯消去法的另外一种理解,第2列消元将A(2)化为A(3)，若令：,0,0,0,0,一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现

5、的情况，这时消去法将无法进行；即使 ，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。,3.2.3 追赶法(特殊矩阵的高斯消去法) 在数值计算中,有一种系数矩阵是三对角方程组,简记为Ax=f,A满足条件 （1） （2） （3）,3.2.4 列主元高斯消去法,第k步的消元因子 交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k) 为主元素，并称使用主元素的消元法为主元素法 根据主元素选取范围分为：列主元素法、行主元

6、素法、全主元素法,记笔记,主元素法的意义,例3.2 用高斯消去法求下列方程组的解,解： 确定乘数 ，再计算系数,假设计算在4位浮点十进值的计算机上求解,则有,这时方程组的实际形式是,由此回代解出 ,但这个解不满足原方程组,解是错误的。这是因为所用的除数太小使得上式在消元过程中“吃掉”了下式，解决这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变为,得到消元后的方程组,这时,因而方程组的实际形式是,由此回代解出 ,这个结果是正确的,可见用高斯消去法解方程组时,小主元可能导致计算失败,因为用绝对值很小的数作除数,乘数很大,引起约

7、化中间结果数量级严重增长,再舍入就使得计算结果不可靠了,故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。,列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。 例3.4 用列主元高斯消去法解下列线性方程组,解：选择-20作为该列的主元素，,计算l21 =10/-20=-0.5 l31=1/-20=-0.05,记笔记,列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元,例3.5 用列主元高斯消去法求解解方程组,解:,3.3 矩阵的直接分解及其在解方程组中的应用,矩阵三角分解法是高斯消去法解线性方程组的

8、一种变形解法,3.3.1 矩阵分解的紧凑格式,应用高斯消去法解n阶线性方程组Ax=b, 经过n步消元之后, 得出一个等价的上三角型方程组 A(n) x=b(n), 对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。 将非奇异阵A分解成一个下三角阵L和一个上三角阵U的乘积 A=LU 称为对矩阵A的三角分解，又称LU分解,由矩阵乘法规则,由此可得U的第1行元素和L的第1列元素,再确定U的第k行元素与L的第k列元素,对于k=2,3, ,n计算： 计算U的第k行元素,（j=k,k+1,n）, 计算L的第k列元素,（i=k,k+1,n）,利用上述计算公式便可逐步求出U与L的各元素

9、求解 Ly=b , 即计算:,求解 Ux=y , 即计算：,显然, 当 时, 解Ax=b直接三角分解法计算才能完成。设A为非奇异矩阵, 当 时计算将中断或者当 绝对值很小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。 用直接三角分解法解Ax=b大约需要 次乘除法。,例3.8 用三角分解法解方程组,求解 Ly=b 得 y= 2，2，1T 求解 Ux=y 得 x= -1，0，1 T 所以方程组的解为,3.3.2 改进平方根法(特殊矩阵的三角分解) 工程实际计算中,线性方程组的系数矩阵 常常具有对称正定性，其各阶顺序主子式及全

10、部特征值均大于0。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法，如平方根法与改进的平方根法。,将A=LLT展开，写成,按矩阵乘法展开，可逐行求出分解矩阵L的元素，计算公式是对于i=1,2,n,j=i+1, i+2,n,这一方法称为平方根法, 它所需要的乘除次数约 为数量级,比LU分解节省近一般的工作量。,例3.9 平方根法求解方程组,解: 因方程组系数矩阵对称正定,设A= ,即：,由Ly=b解得,由 解得,由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵A分解成,的形式，其中,记笔记,3.4 向

11、量范数和矩阵范数,为了研究线性方程组近似解的误差估计 和迭代法的收敛性, 有必要对向量及矩阵的 “大小”引进某种度量-范数的概念。向量范 数是用来度量向量长度的,它可以看成是二、 三维解析几何中向量长度概念的推广。用Rn 表示n维实向量空间。,记笔记,定义3.2 对任一向量XRn, 按照一定规则确定一个实 数与它对应, 该实数记为|X|, 若|X|满足下面三个性质: (1) |X|0；|X|=0当且仅当X=0； (2) 对任意实数， | X|=| | |X|； 对任意向量YRn，|X+Y| |X|+|Y| 则称该实数|X|为向量X的范数,3.4.1 向量范数,在Rn中，常用的几种范数有：,记笔

12、记,其中x1,x2, ,xn分别是X的n个分量。以上定义的 范数分别称为1-范数，2-范数和-范数 可以验证它们都是满足范数性质的，其中 是由内积导出的向量范数。,当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。 有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。 设x*为Ax=b的精确解，x为其近似解，则其绝对误差可表示成|x- x* |，其相对误差可表示成,记笔记,或,例3.10 证明对任意同维向量x , y 有,证：,即,例3.11 设x=(1, 0, -1, 2)T, 计算,解: =1+0+|-1|+2=4,定义3.4 ( 向量序列的极限 ) 设 为 中的

13、 一向量序列， , 记 。如果 (i =1,2, n)，则称 收敛于向量 ，记为,定理3.8 （向量范数的等价性）设 为 上任意两种向量范数, 则存在常数C1, C20, 使得对任意 恒有,（证:略）,定义3.3,同样，矩阵范数和向量范数密切相关，向量范数 有相应的矩阵范数，即,3.4.2 矩阵范数,矩阵的范数性质,矩阵范数的性质可由向量范数定义直接验证。 (1) 设A0, x0, 使Ax0, 根据向量范数的性 质Ax 0, 所以,0,x0, 使Ax =0, 则,=0,当A=0时,矩阵范数的性质可由向量范数定义直接验证,(2),根据向量范数的性质,矩阵范数的性质可由向量范数定义直接验证,(3)

14、,矩阵范数的性质可由向量范数定义直接验证,(4),定义3.7（矩阵的谱半径）设 的特征 值为 , 称 为A的 谱半径。 例 3.12 计算方阵,的三种常用范数,例3.12 计算方阵,的三种范数,解,先计算,所以 ,从而,定理3.1 设A为n阶方阵, 则对任意矩阵范数 都有 证: 设 为A的特征值，x是 对应于的特征向 量,则 x=Ax。两端取范数并依据其性质 得,由于x0，故 ，所以,凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解

15、线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。,3.5 迭代法,3.5.1 迭代法及其收敛性 迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地 对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。,设 非奇异， ，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组 将上式改写成迭代式,选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法,如果 存在极限 则称迭代法是收敛的，否则就是发散的。 收敛时，在迭代公式 中当 时， , 则 , 故 是方程组 的解。 对于给定的方程组可以构造各种迭代公式。 并非全部收敛,例1 用迭代法求解线性方程