石少俭算法讲座7高斯消元法.ppt

《石少俭算法讲座7高斯消元法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、直接法:经过有限步运算后可求得方程组精确解的方法(不计舍入误差!)（2.1节）迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。分为两类：逐次逼近法(一般有限步内得不到精确解)（2.2节）共轭斜量法（不考虑计算过程的舍入误差，只用有限步就收敛于方程组的精确解）（2.3节）解线性方程组的两类方法解线性方程组的直接法(DirectMethodforSolvingLinearSystems)高斯消去法(GaussianElimination)思路首先将A化为上三角阵(upper-triangularmatrix)，此过程称

2、为消去过程，再求解如下形状的方程组，此过程称为回代求解(backwardsubstitution)。=§2.1.1求解的高斯消去法和选主元高斯消去法将增广矩阵的第i行+li1第1行，得到：消去过程：第一步：设，计算因子其中第k步：设，计算因子将增广矩阵的第i行+lik第k行，得到：其中定理：若A的所有顺序主子式均不为0，则高斯消去法能顺序进行消元，得到唯一解。回代过程：共进行n1步，得到运算量（AmountofComputation）（1）用克莱姆（Cramer）法则求解n阶线性方程组每个行列式由n!项相加，而每项包含了n个因子

3、相乘，乘法运算次数为(n-1)n!次.仅考虑乘(除)法运算,计算解向量包括计算n+1个行列式和n次除法运算,乘(除)法运算次数N=(n+1)(n-1)n!+n.当n=8时,N＝200，0000（2）高斯消去法:第1个消去步，计算li1(i=2,3，…，n)，有n-1次除法运算.使aij(1)变为aij(2)以及使bi(1)变为bi(2)有n(n-1)次乘法运算.第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次乘法运算.乘法运算总次数为：除法运算总次数为:(n-1)+…+1=n(n-1)/2回代过程的计算除法运算次数为n次.

4、乘法运算的总次数为n+(n-1)+…+1=n(n-1)/2次Gauss消去法除法运算次数为: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，通常也说Gauss消去法的运算次数与n3同阶，记为O(n3)二、选主元消去法在高斯消去法消去过程中可能出现的情况，这时高斯消去法将无法进行；即使主元素但很小，其作除数，也会导致其它元素数量级的严重增长和舍入误差的扩散例：单精度解方程组/*精确解为和*/8个8个用Gauss消去法计算：8个小主元/*Smallpivo

5、telement*/可能导致计算失败。列主元消去法在第k步消元前，在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元。若p≠k，交换第k个与第p个方程后，再继续消去计算.这种方法称为列主元Gauss消去法。列主元Gauss消去法保证了｜lik｜≤1(i=k+1,k+2,…，n).为避免这种情况的发生,可通过交换方程的次序，选取绝对值大的元素作主元.基于这种思想导出了“选主元消去法”全主元消去法在第k步消去前，在系数矩阵右下角的n-k+1阶主子阵中，选绝对值最大的元素作为主元素。(1)Ifpkthen交换第k行与第p行;Ifqkt

6、hen交换第k列与第q列;(2)消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。