Ch7解线性方程组的直接方法.doc

Ch7、解线性方程组的直接方法1、引言对线性方程组 (1)令，则(1)可记为 (2)求解的数值方法有如下两类：1、直接法 2、迭代法存贮量大； 存贮量小；计算时间短； 计算时间长；程序复杂； 程序简单；适用于A为低阶矩。 适用于A为高阶稀疏矩阵。2、 Gauss消去法1、消元过程记为 (3)若，令，用乘第一个方程后加到第个方程上，则(3)变为 记为一般地，对若，令，类似地可消去从第到第个方程中的，直至将方程化为上三角方程。 记为2、回代过程3、矩阵的LU分解矩阵A的第一行乘后加到第行的变换，相当于用矩阵左乘矩阵A一般地，第步所用变换对应于矩阵Gauss消去法可用矩阵描述如下： ，即，记上三角，下三角，则 矩阵的LU分解。定理1：当方阵A的顺序主子式时，A可唯一地分解为单位下三角阵L与上三角阵U之积，即A=LU。设，则对，即，只要经两次回代即可解出方程。3、Gauss列主元消去法1、Gauss消去法中的称为主元，从理论上讲仅需即可，但从数值计算的角度来看，其绝对值越小，引起的舍入误差就越大，反之舍入误差就小。为了减小舍入误差，提高算法的数值稳定性，可在每步消元过程中选主元，具体有：总体选主元(每步系数矩阵中绝对值最大者)按列选主元(在第k步中，从中选绝对值最大者)2、计算过程只须在Gauss消去法中加入选主元过程。在中选出绝对值最大者，然后放在(k,k)位置（交换行）。4、追赶法与Cholesky分解1、追赶法对三对角方程 首先由第一个方程解出，令，则，代入第二个方程得，即，令，有，类似地可推出下列公式 其中 ，将代入最后一个方程，令，则，代入即可依次求出。上述求解过程可分为两个部分：依次确定，称之为追的过程；依相反次序确定，称之为赶的过程。即2、对称正定阵的分解定理2：设A对称，且A的各阶顺序主子式均不为零，则A可唯一地分解为，其中L为单位下三角阵，D为对角阵。定理3：设A对称正定，则A可唯一地分解为，其中L为对角元大于零的下三角阵。证：由定理2，又A正定，有中的，故其中为下三角。（Cholesky分解）设A对称正定，则可化为，即，经回代即可解。计算机解法：A为一般方阵时，用LU分解（Gauss消去法）；A对称正定时，用Cholesky分解。5、向量和矩阵的范数一、向量的范数1、定义：设或，为定义在上的一个实值函数，若满足非负性：，当且仅当；齐次性：对，有；三角不等式：对，有；则称为上的一个向量范数。2、常用向量范数对，有范数 ；1-范数 ；2-范数 ；p-范数 定理4：中的一切范数都是等价的，即对任意两种范数，总有正数m和M，使3、向量序列的收敛性定义：设为中的向量序列，并记，若，则称收敛于，记为定理5：，为任一范数。二、矩阵的范数1、定义：若矩阵的某个实值函数满足； 相容性；则称为上的一个矩阵范数。2、常用矩阵范数 行范数； 列范数 2-范数； F-范数3、谱半径定义：设A的特征值为，称为A的谱半径。定理6：A的谱半径不超过A的范数，即。证：设为A的任一特征值，为相应的特征向量，即，则 相容性，故，即。定理7：若，则可逆，且。证：若不可逆，即，有非零解亦即有，使， ，矛盾，故可逆。，得6、误差分析和矩阵的条件数1、右端向量误差对解的影响设的右端向量有误差，相应的解为，则，又，故2、系数矩阵误差对解的影响设的系数矩阵有误差，相应的解为，则，由定理7，若，则可逆，且，故3、矩阵的条件数定义：设A非奇异，则称为的条件数。；若A为正交阵，则。 常用条件数：；4、病态方程组 条件数刻画了方程组的解对原始数