求解线方程组的数值解法

《求解线方程组的数值解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章求解线性方程组的数值解法泰山学院信息科学技术系解线性方程组的两类方法:直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解)§3.1解线性方程组的直接法一、高斯消去法思路首先将方程组Ax=b化为上三角方程组，此过程称为消去过程，再求解上三角方程组，此过程称为回代过程.§3.1.1高斯消去法和选主元高斯消去法将增广矩阵的第i行+li1第1行，得到：消去过程：第一步：设，计算因子其中第k步：设，计算因子且计算共进行n1步，得到定理：若A的所有顺序主子式均不为0，则高斯消去法

2、能顺序进行消元，得到唯一解。回代过程：二、选主元消去法为避免这种情况的发生,可通过交换方程的次序，选取绝对值大的元素作主元.基于这种思想导出了主元素法在高斯消去法消去过程中可能出现的情况，这时高斯消去法将无法进行；即使主因素但很小，其作除数，也会导致其它元素数量级的严重增长和舍误差的扩散列主元消去法在第k步消元前，在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元。若p≠k，交换第k个与第p个方程后，再继续消去计算.这种方法称为列主元Gauss消去法。列主元Gauss消去法保证了｜lik｜≤1(i=k+1,k+2,…，n).全主元消去法在第k步消去前，在系数矩阵右下角的n-k+1阶

3、主子阵中，选绝对值最大的元素作为主元素。(1)Ifpkthen交换第k行与第p行;Ifqkthen交换第k列与第q列;(2)消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。运算量（AmountofComputation）（1）用克莱姆（Cramer）法则求解n阶线性方程组每个行列式由n!项相加，而每项包含了n个因子相乘，乘法运算次数为(n-1)n!次.仅考虑乘(除)法运算,计算解向量包括计算n+1个行列式和n次除法运算,乘(除)法运算次数N=(n+1)(n-1)n!+n.（2）高斯消去法:在第1个消去步，计算li1(i=2,3，…，n)，有n-1次除法运算.使a

4、ij(1)变为aij(2)以及使bi(1)变为bi(2)有n(n-1)次乘法运算和n(n-1)次加(减)法运算.在第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次乘法运算和相同的加(减)法运算.首先统计乘法运算总次数.将每个消去步的乘法运算次数相加，有n(n-1)+(n-1)(n-2)+…+3.2+2.1=n(n-1)(n+1)/3加(减)法运算次数总计也为n(n-1)(n+1)/3.除法运算总次数为n+(n-1)+…+1=n(n-1)/2回代过程的计算除法运算次数为n次.乘法运算和加法运算的总次数都为n+(n-1)+…+1=n(n-1)/2次Gauss消去法除法运算次数

5、为:n(n-1)/2+n=n(n+1)/2，乘法运算次数为:n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6，加(减)法运算次数为:n(n-1)(2n+5)/6通常也说Gauss消去法的运算次数与n3同阶，记为O(n3)全主远消去法:比高斯消去法多出　比较，保证稳定，但费时。列主元消去法:比高斯消去法只多出的　比较，略省时。§2.1.2三角分解法高斯消元法的矩阵形式每一步消去过程相当于左乘初等变换矩阵LkA的LU分解(LUfactorization)定理2.1.4：若A的所有顺序主子式均不为0，则A的LU分解唯一（其中L为单位下三角阵）。证明：由§1中定

6、理可知，LU分解存在。下面证明唯一性。若不唯一，则可设A=L1U1=L2U2，推出上三角矩阵对角线上为1的下三角矩阵注：（1）L为单位下三角阵而U为一般上三角阵的分解称为Doolittle分解（2）L为一般下三角阵而U为单位上三角阵的分解称为Crout分解。Doolittle分解法：通过比较法直接导出L和U的计算公式。思路一般计算公式计算量与Gauss消去法同.LU分解求解线性方程组§2.1.4求解正定方程组的Cholesky方法回顾：对称正定阵A的几个重要性质（1）A1亦对称正定，且aii>0（2）A的顺序主子阵Ak亦对称正定（3）A的特征值i>0（4）A的全部顺序主子式de

7、t(Ak)>0定理2.1.6设矩阵A对称正定，则存在唯一的对角元全为正的下三角阵G使得A＝GGT计算格式为§2.1.5求解三对角方程组的追赶法定理：若A为对角占优的三对角阵，且满足则方程组有唯一的LU分解。直接比较等式两边的元素，可得到计算公式（p.66）第二步:追—即解：第三步:赶—即解：第一步:对A作Crout分解