第八章 线性代数方程组解法new

第八章.线性代数方程组的解法,线性方程组求解问题在许多科学计算问题中都会遇到，如应力分析，电学网络，自由振动等。早在公元前250年我国就掌握了解方程组的消去法。在著名的数学专著九章算术中，就有有关线性方程组的求解方法。,九章算术全书246题，202术，分属九章：,第一章“方田”：各种形状田亩面积计算；第二章“粟米”：各种谷物间按比例交换；第三章“衰分”：比例分配计算；第四章“少广”：由面积或体积求边长或径长；第五章“商功”：各种土石工程、体积计算；第六章“均输”：合摊派赋税、徭役；第七章“盈不足”：双设法解题；第八章“方程”：线性方程组求解；第九章“勾股”：勾股测量问题。,1.引言,解线性方程组的两类方法：直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）,2.直接法Gauss消去法,Gauss消去法的基本思想,然后依次求x3,x2,x1。将线性方程组化为上三角形方程组的计算过程叫消元，自下而上解三角形方程组，计算x3,x2,x1的过程叫回代。,用矩阵形式来写即为：,用矩阵变换的角度来看，第一、二次消去分别相当于矩阵A左乘初等行变换阵：,和,由此看出：,用消去法解方程组的基本思想是用逐次消去未知数的方法把原来方程组化为与其等价的三角形方程组，而求解三角形方程组就容易了。换用矩阵的语言来说，上述过程就是用行的初等变换将原方程组系数矩阵化为简单的三角形形式，从而将求解原方程组的问题转化为求解简单方程组的问题。,一、Gauss消去法计算过程,相当于第i个方程-第一个方程数新的第i方程同解！第一方程不动！,上述消元过程除第一个方程不变以外,第2第n个方程全消去了变量1，而系数和常数项全得到新值：,系数矩阵与常数项：,消去过程算法,回代过程算法,Gauss消去法算法简述,消去第一列的n-1个系数要计算n*(n-1）个乘法。,二、Gauss消去法乘法计算量,每一步消去过程相当于左乘初等变换矩阵Lk,三、Gauss消去法的矩阵表示,LU形式,例1.,用Gauss消去法解线性方程组(用3位十进制浮点数计算）,解:,本方程组的精度较高的解为,用Gauss消去法求解(用3位十进制浮点数计算),主元,9999,回代后得到,与精确解相比,该结果相当糟糕,究其原因,在求行乘数时用了很小的数0.0001作除数,如果在求解时将1,2行交换,即,0.9999,回代后得到,这是一个相当不错的结果,3.高斯主元素消去法,Gauss列主元素消去法算法设计,4.约当消去法,消去法的基本思想是，通过将一个方程乘或除以某个常数，以及将两个方程相加减这两种手续，逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得出所求的解。所谓约当消去法，其特点是，它的每一步仅在一个方程中保留某个变元，而从其它的各个方程中消去该变元，这样经过反复消元后，所给方程组中的每个方程最终被加工成仅含一个变元的形式，从而得出所求的解。,高斯若当消去法,5.LU分解法,同样,综合以上分析,有,因此可以推导出,U的第一行,L的第一列,-(1),-(2),U的第r行,-(3),L的第r列,-(4),称上述(1)(4)式所表示的分解过程为LU分解,对于线性方程组,系数矩阵非奇异,经过LU分解后,线性方程组可化为下面两个三角形方程组,LU分解求解线性方程组,算法设计,6三对角方程组的解法,三对角方程组可用追赶法来求解。,追赶法的代数基础,定理设三对角矩阵为对角占优，则它可唯一分解成下二对角阵和单位上二对角阵的乘积：事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。,易得上述定理中的L是二对角线的下三角矩阵，U是二对角线的上三角矩阵。对于一般的n阶矩阵，可以通过把它们具体求出来加以验证（所谓构造法）。L的对角元的为1时，属于Doolittle分解，U的对角元为1，属于Crout分解。,Crout分解,Crout分解,Crout分解,求得L，U后，解，化为解以下两个三角形方程组,Crout分解,迭代法一个突出优点就是算法简单，因而编制程序比较容易。但是迭代法也有缺点,它要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性。发散的迭代过程是没有实用价值的。,解线性代数方程组的迭代法,1、迭代法的一般理论：,设线性方程组,所谓迭代法就是从任意向量出发，按照一定的法则逐次产生向量序列，使其收敛于方程组(1)的解向量的过程。,-(1),将其分解为两个矩阵的差:,其中，N是非奇异矩阵，因此代入(1)式得：,所以有,记则上式化为,-(2),明显方程组(1)与方程组(2)等价,从任意向量出发，使用递推公式：,-(3),其中，M为迭代矩阵，可产生向量序列：,若向量序列收敛于向量，即,则对方程组(3)两端同时取极限，得,因此向量是方程组(1)的解,定理：迭代法对任意初始值和右端向量d都收敛的充要条件是：(M)1,2、Jacobi迭代法：,将方程组(1)中系数矩阵A的主对角线元素构成的对角矩阵记为D,即D=diag,因此有,因此方程组(1)的等价形式为：,即可得到：,其中,由此得Jacobi迭代公式：,-(4),定理：若方程组(1)的系数矩阵A按行或按列对角占优,即，或,则Jacobi迭代法对任意初始值都收敛,Jacobi迭代公式的方程组形式：,Gauss-Seidel迭代法矩阵表示如下：,将系数矩阵A分解为：,其中，L,D,U分别为：,-(8),3、Gaus