工程经济学：第五章 线性代数方程组的数值解法

1、 第五章 线性代数方程组的数值解法p36引言关于线性方程组的数值解法一般有两类。直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）. 代表性的算法是高斯(Gauss)消去法。计算代价高.迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法. 简单实用。思路首先将A通过初等行变换化为上三角阵，此过程称为消去过程，再求解如下形状的方程组，此过程称为回代求解。=5.1 高斯消去法一. 三角方程组的解法下三角方程组的前代求解 上三角方程组的回代求解：二 高斯消去法步骤如下：第一步：则设 Ax=b. 记A(1)=A b(1)=b第二步：则重复上述过程, 最后得原方程组

2、的同解方程组 消元过程Gauss 消去法定理：若A的所有顺序主子式 均不为0，则高斯消去法能顺序进行消元，得到唯一解。高斯消去法条件高斯消去法存在的问题：如果某个 ,但很小，会引入较大的误差。1.在高斯消去法消去过程中可能出现 的情况，这时高斯消去法将无法进行三 高斯列主元消去法具体步骤为：基本思想：在每轮消元之前，选列主元素（绝对值最大的元素） 以第二步为例:挑选从第二行开始的第二列中的最大元素,交换行将其变为主元 如此至多经过n-1步,就得到与之同解的上三角形方 程组的增广矩阵,再用回代过程即可得方程组的解.5.2 矩阵的三角分解法若矩阵A有分解：A=LU，其中L为下三角阵，U为上三角阵，

3、则称该分解为A的LU分解。若矩阵A有分解：A=LU一 矩阵的三角分解(下三角阵上三角阵)第一行乘 m21加到第二行第一行乘 m31加到第三行第一行乘 mn1加到第n行记 L1 = EnE3E2 高斯消元法第一步：等价于L1A(1)=A(2), L1b(1)=b(2)A(1)b(1)A(2)b(2)高斯消元法的矩阵形式A(2)b(2)A(3)b(3)第二步消元等价于L2A(2)=A(3), L2b(2)=b(3)其中Lk A(k)=A(k+1), Lkb(k)=b(k+1)一般第k步消元的矩阵表示为Lk =其中A(n)注： （1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolitt

4、le 分解 （2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 L定理5.1：二 矩阵的直接三角分解直接计算 A 的 LU 分解(例) （续）1)2)3)一般计算公式 计算量与 Gauss 消去法同. a11 a12 a13 a1n u11 u12 u13 u1n a21 a22 a23 a2n l21 u22 u23 u2n a31 a32 a33 a3n l31 l32 u33 u3n an1 an2 an3 ann ln1 ln2 ln3 unn.(1)(3)(5)(2n-1)(2) (4) (6) (2n)紧凑格式旧元素减去左边行与顶上列向量的点积计算行不用除法

5、计算列要除主对角元注：例 求矩阵的Doolittle分解LU 分解求解线性方程组例:用矩阵的直接三角分解法解方程组或 用 Doolittle 分解法结束 41三 解三对角线性方程组的 追赶法设三对角方程组 为Ax=d,即:其中|i-j|1时,aij=0,且满足如下的条件:(1)|b1|c1|0,|bn|an|0(2)|bi|ai|+|ci|, aici0, i=2,3,n-1.可以证明A的Crout分解形式为：LU由矩阵乘法 43用矩阵乘法比较和Crout 分解可推导总结算法步骤如下:1.分解计算2.解Ly=d3.解Ux=y追的过程赶的过程定理 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n)四 系数矩阵为对称正定矩阵方程组的平方根法 A对称：AT=A A正定：A的各阶顺序主子式均大于零。即 证明： DU0 即为L、U分解中的UDU0推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩阵。Cholesky分解U从而： 其中 为下三角阵。Cholesky分解的求法计算公式:求解对称正定方程组Ax=b的平方根法(计算公式) ：1分解计算 平方根法缺点及优点 优点：可以减少存储单元。 缺点：存在