CP计算魏惋理方程组解.ppt

解线性方程组的直接法和迭代法 线性方程组的解 ? 运算量 （1）用克莱姆（Cramer）法则求解n阶线性方程组 一、高斯消去法 第1个消去步， 计算li1(i=2,3，…，n)， 有n-1次除法运算. 使aij(1)变为 aij(2) 以及使bi(1)变为bi(2)有n(n-1)次乘法运算. 回代过程的计算 除法运算次数为n次. 乘法运算的总次数为 n+(n-1)+…+1=n(n-1)/2次 为避免这种情况的发生, 可通过交换方程的次序，选取绝对值大的元素作主元. 基于这种思想导出了： “选主元消去法” 选主元法包括： 列主元 全主元 列主元消去法 在第k 步消元前，在系数矩阵第k 列的对角线以下的元素中找出绝对值最大的元。 §5.2 解线性方程组的迭代法 迭代法的基本思想 Jacobi 迭代 Jacobi 迭代 GS 迭代 SOR 迭代 Jacobi、GS 和 SOR 算法 举例 举例（续） 举例（续） 矩阵分裂法 迭代法的Matlab实现 雅可比迭代的MATLAB程序 写成矩阵形式: 称为 GS 迭代矩阵 此迭代格式称为高斯-塞德尔 (Gauss-Seidel) 迭代 k = 0, 1, 2, … 解得 称为 SOR 迭代矩阵 为了得到更好的收敛效果，可在修正项前乘以一个参数 w，于是就得到所谓的逐次超松弛迭代法，简称 SOR迭代，其中 w 称为松弛因子。此时 在 GS 迭代中 解得 Jacobi 算法 GS 算法 SOR 算法 解： 例：解线性方程组 取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留4位。 Jacobi 迭代格式： 令 则迭代得： x(1) = ( 0.5000, 2.6667, -2.5000 )T x(21) = ( 2.0000, 3.0000, -1.0000 )T GS 迭代格式 得 x(1) = ( 0.5000, 2.8333, -1.0833 )T x(9) = ( 2.0000, 3.0000, -1.0000 )T SOR 迭代格式 取 w = 1.1，得 x(1) = ( 0.5500, 3.1350, -1.0257 )T x(7) = ( 2.0000, 3.0000, -1.0000 )T 如何确定SOR迭代中的最优松弛因子是一件很困难的事。 Jacobi 迭代 GS 迭代 SOR 迭代 A = M - N M = D, N = M – A = L + U M = D – L, N = U * * 直接法: 经过有限步运算后可求得方程组精确解的方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。分为两类： 逐次逼近法(一般有限步内得不到精确解) 共轭斜量法（不考虑计算过程的舍入误差，只用有限步就收敛于方程组的精确解） 解线性方程组的两类方法 §5.1 解线性方程组的直接法 高斯消去法 思路 首先将A化为上三角阵，此过程称为消去过程，再求解如下形状的方程组，此过程称为回代求解。 = 求解 的高斯消去法和选主元高斯消去法 将增广矩阵的第 i 行 + li1 ? 第1行，得到： 消去过程： 第一步：设 ，计算因子 其中 第k步：设 ，计算因子 将增广矩阵的第 i 行 + lik ? 第k行，得到： 其中 定理：若A的所有顺序主子式 均不为0，则高斯消去法能顺序进行消元，得到唯一解。 回代过程： 共进行 n ? 1步，得到： 每个行列式由n!项相加，而每项包含了n个因子相乘，乘法运算次数为(n-1)n !次. 仅考虑乘(除)法运算,计算解向量包括计算n+1个行列式和n次除法运算,乘(除)法运算次数N=(n+1)(n-1)n!+n. 当n=8时,N＝200，0000 第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次 乘法运算. 乘法运算总次数为： 除法运算总次数为: (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) 二、 选主元消去法 在高斯消去法消去过程中可能出现 的情况，这时 高斯消去法将无法进行；即使主元素 但很小， 其作除数 ，也会导致其它元素数量级的严重增长和舍入 误差的扩