《数值分析5高斯消元法“算法化”》课件.pptVIP

《数值分析》5 线性方程组的标准形式 高斯消元法“算法化” 初等矩阵与高斯变换 富比尼矩阵与LU分解 确定小行星轨道 以太阳为原点在轨道平面 内建立直角坐标系,取天文测量单位,在五个不同时间观察小行星,测得坐标数据： x 4.5596 5.0816 5.5546 5.9636 6.2756 y 0.8145 1.3685 1.9895 2.6925 3.5265 通过计算确定椭圆方程 a1x2 + 2a2xy + a3 y2 +2a4 x + 2a5 y + 1 = 0 2/18 a1xj2 + 2a2xjyj + a3 yj2 +2a4 xj + 2a5 yj + 1 = 0 五个点的坐标(xj, yj) (j= 1,2,3,4,5)代入二次曲线方程,得关于a1,a2,a3,a4,a5 的方程组 3/18 线性方程组的标准形式 a11x1+ a12x2+····+ a1nxn = b1 a21x1+ a22x2+····+ a2nxn = b2 ········································· an1x1+ an2x2+····+ annxn = bn A X = b 4/18 克莱姆法则解线性方程组 (1)? 输入矩阵A和右端向量b; 高斯消元法 第一步: 将方程组消元化为三角形方程组; 第二步: 解三角形方程组,得原方程组的解。 (4) 计算并输出x1 = D1 / D,····, xn=Dn/D, 结束。 (3) 对k=1,2,···,n用b替换A的第k列数据,并计算替换后矩阵的行列式值Dk; (2)计算A的行列式D,如果D=0,则输出错误信息结束,否则进行第(3)步; 5/18 回代过程 ( 解上三角方程组) 计算：xn = bn /ann (a11…ann≠0) xk=[bk－(ak , k+1xk+1+ … + ak n)] / ak k (k =n－1，…，1) 除法: n次; 乘法: n(n-1)/2次, 共n(n+1)/2次乘除法运算 6/18 消元过程(化一般方程组为上三角方程组) 增广矩阵 (4×5)阶 ? n×(n+1) 阶 7/18 计算3个数: [m21 m31 m41]T = [a21 a31 a41]T / a11 用-m21乘矩阵第一行后加到矩阵第二行; 用-m31乘矩阵第一行后加到矩阵第三行; 用-m41乘矩阵第一行后加到矩阵第四行; 第一轮消元后 8/18 消元过程的算法化: 消元因子: 消元中非零元数据刷新: 复杂度分析: 除法: 3次···························· (n-1次)， 乘法: 3×4=12次 ················(n-1)×n次 消元因子 9/18 第二轮消元后 计算2个数：[m32 m42]T = [a32(1) a42(1)]T / a22(1) 用-m32乘矩阵第二行后加到矩阵第三行; 用-m42乘矩阵第二行后加到矩阵第四行; 10/18 第三轮消元后 用-m43乘矩阵第三行后加到矩阵第四行; 计算: m43=a43(2)/a33(2) 对应于三角形方程组 = 11/18 n阶方程组消元过程乘法次数: (n-1)n+(n-2)(n-1)+…+1×2=(n3-n)/3 除法次数: (n-1)+(n-2)+…+1=n(n-1)/2 回代过程：n(n+1)/2 总工作量: n2+(n3-n)/3 n 2 3 4 5 6 Gs 6 17 36 65 106 Gm 8 51 364 2885 25206 12/18 初等矩阵与Gauss变换 第一行乘 –m21 加到第二行 ············ F1 = En····E3E2 I ? 13/18 第一轮消元: A(1) = F1 A F1 = En····E3E2 14/18 记 e1T=[ 1 0 ··· 0 ] = I – m1 e1T 15/18 Fk = I – mkekT ( k = 1, 2, ···, n – 1) ········ ekT=[ 0 ··· 0 1 0 ··· 0 ] 16/18 Gauss消元结果 A(n – 1) = Fn-1Fn-2·······F1 A Fk = I – mkekT ( k = 1, 2, ···, n – 1) Fk 被称为 Frobenius矩阵, 其重要性质有 Fk-1= I + mkekT ( k = 1, 2, ···, n – 1) F1-1F2-1 ······ Fn-1-1