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

《第八章 线性代数方程组解法new.ppt》由会员分享，可在线阅读，更多相关《第八章 线性代数方程组解法new.ppt（61页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第八章.线性代数方程组的解法 线性方程组求解问题在许多科学计算问题中都会遇到，如应力分析，电学网络，自由振动等。早在公元前250年我国就掌握了解方程组的消去法。在著名的数学专著九章算术中，就有有关线性方程组的求解方法。九章算术全书246题，202术，分属九章：第一章“方田”：各种形状田亩面积计算；第二章“粟米”：各种谷物间按比例交换；第三章“衰分”：比例分配计算；第四章“少广”：由面积或体积求边长或径长；第五章“商功”：各种土石工程、体积计算；第六章“均输”：合摊派赋税、徭役；第七章“盈不足”：双设法解题；第八章“方程”：线性方程组求解；第九章“勾股”：勾股测量问题。1.引言 解线性方程组的两

2、类方法：直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）2.直接法Gauss 消去法Gauss消去法的基本思想 然后依次求x3,x2,x1。将线性方程组化为上三角形方程组的计算过程叫消元，自下而上解三角形方程组，计算x3,x2,x1的过程叫回代。用矩阵形式来写即为：用矩阵变换的角度来看，第一、二次消去分别相当于矩阵A左乘初等行变换阵：和由此看出：用消去法解方程组的基本思想是用逐次消去未知数的方法把原来方程组化为与其等价的三角形方程组，而求解三角形方程组就容易了。换用矩阵的语言来说

3、，上述过程就是用行的初等变换将原方程组系数矩阵化为简单的三角形形式，从而将求解原方程组的问题转化为求解简单方程组的问题。一、Gauss 消去法计算过程相当于第i个方程-第一个方程数新的第i方程同解！第一方程不动！上述消元过程除第一个方程不变以外,第2第 n 个方程全消去了变量 1，而系数 和常数项全得到新值：系数矩阵与常数项：消去过程算法回代过程算法Gauss消去法算法简述消去法算法简述 消去第一列的 n-1 个系数要计算n*(n-1）个乘法。二、Gauss消去法乘法计算量每一步消去过程相当于左乘初等变换矩阵Lk三、Gauss消去法的矩阵表示i+1行 i+1行LU形式例1.用Gauss消去法解

4、线性方程组(用3位十进制浮点数计算）解:本方程组的精度较高的解为用Gauss消去法求解(用3位十进制浮点数计算)主元9999回代后得到与精确解相比,该结果相当糟糕究其原因,在求行乘数时用了很小的数0.0001作除数如果在求解时将1,2行交换,即0.9999回代后得到这是一个相当不错的结果3.高斯主元素消去法Gauss列主元素消去法算法设计列主元素消去法算法设计 4.约当消去法约当消去法 消去法的基本思想是，通过将一个方程乘或除以某个常数，以及将两个方程相加减这两种手续，逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得出所求的解。所谓约当消去法约当消去法，其特点是，它的每一步仅在一

5、个方程中保留某个变元，而从其它的各个方程中消去该变元，这样经过反复消元后，所给方程组中的每个方程最终被加工成仅含一个变元的形式，从而得出所求的解。高斯若当消去法5.LU 分解法同样综合以上分析,有因此可以推导出U的第一行L的第一列-(1)-(2)U的第r行-(3)L的第r列-(4)称上述(1)(4)式所表示的分解过程为LU分解对于线性方程组系数矩阵非奇异,经过LU分解后线性方程组可化为下面两个三角形方程组LU 分解求解线性方程组算法设计6 三对角方程组的解法三对角方程组的解法三对角方程组可用追赶法追赶法来求解。追赶法的代数基础追赶法的代数基础 定理定理 设三对角矩阵 为对角占优，则它可唯一分解

6、成下二对角阵 和单位上二对角阵 的乘积：事实上，追赶法的求解过程就是将系数矩阵 分解两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。易得上述定理中的L是二对角线的下三角矩阵，U是二对角线的上三角矩阵。对于一般的n阶矩阵，可以通过把它们具体求出来加以验证（所谓构造法）。L的对角元的为1时，属于Doolittle分解，U的对角元为1，属于Crout分解。Crout分解Crout分解Crout分解求得L，U后，解 ，化为解以下两个三角形方程组Crout分解 迭代法一个突出优点就

7、是算法简单，因而编制程序比较容易。但是迭代法也有缺点,它要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性。发散的迭代过程是没有实用价值的。解线性代数方程组的迭代法1、迭代法的一般理论：设线性方程组所谓迭代法就是从任意向量 出发，按照一定的法则逐次产生向量序列 ，使其收敛于方程组(1)的解向量 的过程。-(1)将其分解为两个矩阵的差:其中，N是非奇异矩阵，因此代入(1)式得：所以有记 则上式化为 -(2)明显方程组(1)与方程组(2)等价从任意向量 出发，使用递推公式：-(3)其中，M为迭代矩阵，可产生向量序列：若向量序列 收敛于向量 ，即则对方程组(3)两端同时取极限，得因此向量

8、是方程组(1)的解定理：迭代法对任意初始值 和右端向量d都收敛的充要条件是：(M)12、Jacobi迭代法：将方程组(1)中系数矩阵A的主对角线元素构成的对角矩阵记为D,即D=diag ,因此有 因此方程组(1)的等价形式为：即可得到：其中由此得Jacobi迭代公式：-(4)定理：若方程组(1)的系数矩阵A按行或按列对角占优即，或则Jacobi迭代法对任意初始值 都收敛Jacobi迭代公式的方程组形式：Gauss-Seidel迭代法矩阵表示如下：将系数矩阵A分解为：其中，L,D,U分别为：-(8)3、Gauss-Seidel迭代法：将分解式(8)方程组(1)得等价方程组：即可得到：其中，由此得Jacobi迭代公式：若系统矩阵A对称正定，则求解AX=b的与雅克比迭代法对应的高斯-赛德尔迭代法对任意初始向量都收敛。高斯高斯塞德尔迭代公式塞德尔迭代公式超松弛法超松弛法