清华大学数值分析第2章_845001349.doc

第2章 线性代数方程组与矩阵运算 本章自学内容： 线性代数方程组的直接解法 线性代数方程组的迭代解法 矩阵分解 2.1 线性代数方程组的直接解法 一、Gauss消去法 1. 将增广矩阵经过一系列的初等行变换变成右上三角矩阵。即 其中为单位上三角矩阵（除最后一列外） 对于k从0开始直到n-2作以下两步（假设对于任意的k有≠0）： (1) 归一化 / ，j＝k＋1，…，n－1 / (2) 消元 － ，i＝k＋1，…，n－1；j＝k＋1，…，n－1 － ，i＝k＋1，…，n－1 2. 进行回代，依次解出，…，，。 /， ，k＝n－2，…，1，0 分析：·时间复杂度 归一化 n – k + 1 消去 (n – k + 1)(n – k) 共 回代 总共 多项式界算法 ·空间复杂度 in place ·可靠性 当||＝0时，运算就会中断（因为出现分母为0的情况）； 即使||≠0，但当||很小时，一方面会损失精度，另一方面还可能 会导致商太大而使计算产生溢出。 数值计算是不稳定的。 二、选主元 1) 列选主元 采用列主元的高斯消去法是不影响求解结果的。 2) 全选主元 ＝ JS(0：n－1) JS(k)记忆做到第k步时，与第k列进行交换的列号。 全选主元高斯消去法求解线性代数方程组的步骤如下： (1) 对于k从0到n－2做以下运算： ·全选主元 ·系数矩阵归一化 / ，j＝k＋1，…，n－1 ·常数向量归一化 / ·系数矩阵消元 － ，i＝k＋1，…，n－1；j＝k＋1，…，n－1 ·常数向量消元 － ，i＝k＋1，…，n－1 (2) 进行回代 ·解出 / ·回代逐个解出 ，…，，。即 ，k＝n－2，…，1，0 (3) 恢复解向量 三、Gauss-Jordan消去法 (1) 对于k从0到n－1做以下运算： 全选主元 ·系数矩阵归一化 / ，j＝k＋1，…，n－1 ·常数向量归一化 / ·系数矩阵消元 －，i＝0，1，…，n－1；i≠k j＝k＋1，…，n ·常数向量消元 － ，i＝0，1，…，n－1；i≠k 归一化 n – k + 1 消去 (n – k + 1)(n – 1) 共 四、三对角方程组 = 高斯消去法求解三对角方程组的步骤如下： 1) 对于k从0到n－2做以下运算： 系数矩阵归一化 常数向量归一化 系数矩阵消元 常数向量消元 经过这一步后，方程组变为 = 2) 进行回代 解出 回代逐个解出，…，，。即 ，k＝n－2，…，1，0 “追”的过程需要做4(n－1)次乘除法，而“赶”的过程需要做n次乘除法。因此，“追赶法”的计算工作量为(5n－4)次乘除法。 当三对角方程组中的系数矩阵（三对角矩阵）满足条件 ||＞|| ||＞||＋|| ，k＝1，2，…，n－2 ||＞|| 时，“追赶法”的计算过程中不会出现中间结果数量级的巨大增长和舍入误差的严重积累。 2.2 病态方程组 某些方程组系统对于增广矩阵元素的微小变化是很敏感的，这样的系数矩阵称为病态矩阵。 例：中度病态矩阵 解为 =[2.40481 1.60321]