ch3线性代数方程组的数值解法.ppt
第三章第三章 线性代数方程组的数线性代数方程组的数 值解法值解法 3.1 引言3.2 解线性方程组的消去法3.3 解线性方程组的矩阵分解法3.4 解线性方程组的迭代法3.1 引言引言 给定一个线性方程组求解向量 x。第一类是直接法直接法。即按求精确解的方法运算求解。第二类是迭代法迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组：数值解法主要有两大类：然后构造迭代格式这称为一阶定常迭代格式一阶定常迭代格式，M 称为迭代矩阵迭代矩阵。3.2 解线性方程组的消去法解线性方程组的消去法 3.2.1 高斯消去法与高斯若当消去法高斯消去法与高斯若当消去法 例1 第一步：先将方程（第一步：先将方程（1）中未知数）中未知数 的系数的系数2除（除（1）的两）的两边，得到下列方程组：边，得到下列方程组：再将第二个方程减去第一个方程的再将第二个方程减去第一个方程的4倍，第三个方程减去倍，第三个方程减去第一个方程的第一个方程的2倍。倍。第二步：将方程第二步：将方程 中第二个方程的两边除以中第二个方程的两边除以 的系数的系数4 将第三个方程减去第二个方程：将第三个方程减去第二个方程：第三步：为了一致期见，将第三个方程中的第三步：为了一致期见，将第三个方程中的 系数变为系数变为1，除以除以 我们来分析一下上述过程：整个过程分两大步。一是用我们来分析一下上述过程：整个过程分两大步。一是用逐次消去未知数的方法，把原来的方程组化为与其等价的三逐次消去未知数的方法，把原来的方程组化为与其等价的三角形方程组。角形方程组。用矩阵的观点来看用矩阵的观点来看，就是用初等变换的方法将，就是用初等变换的方法将方程组的系数矩阵进行初等变换，即方程组的系数矩阵进行初等变换，即 这样就将系数阵化为单位三角阵，这个过程称为这样就将系数阵化为单位三角阵，这个过程称为“消元消元过程过程”。二是解三角形方程组二是解三角形方程组，称为，称为“回代过程回代过程”，整个过程，整个过程称为称为“有回代过程的顺序消元法有回代过程的顺序消元法”。下面我们来讨论一般的解下面我们来讨论一般的解n阶方程组的高斯消去法，且阶方程组的高斯消去法，且就矩阵的形式来介绍这种新的过程：就矩阵的形式来介绍这种新的过程：一般地，第第k步步：即将矩阵变为如下 第第n步：步：得到：经过上述n步过程后，原系数矩阵A变为一个单位上三角矩阵，即原方程组化为一个和它完全等价的三角形方程组，即高斯消去法高斯消去法：（1）消元过程）消元过程：对k=1,2,n 依次计算(2)回代过程回代过程：例3.1 试用高斯消去法求解线性方程组 消元过程为 解解即把原方程组等价约化为 据之回代解得为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即 相应地，计算公式可表述为：从而得到解这一无回代的消去法称为高斯高斯-若当若当（Jordan）消去法消去法 二、高斯二、高斯-若当若当（Jordan）消去法消去法 解解例例 2 试用高斯-若当消去法求解例3.1的线性方程组。因为 解解一般公式：一般公式：高斯约当消去法是一个具有消去过程而无回代过程的算法。以上两种消去法都是沿系数矩阵的主对角线元素进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。因此：3.2.2 消去法的可行性和计算工作量消去法的可行性和计算工作量 定理定理 3.1 如果的各阶顺序主子式均不为零，即有即消去法可行。推论推论 若系数矩阵严格对角占优严格对角占优，即有 定理定理 3.2 求解 n 阶线性方程组(3-1)的高斯消去法的乘除工作量约为 ，加减工作量约为 ；而高斯-若当消去法的乘除工作量约为 ，加减工作量约为 。由式（3-4）知，高斯消去法在消元过程中第k步的工作量为所以，消元过程的总工作量为证证回代过程中的乘除和加减工作量均为总工作量为 类似可得，高斯-若当消去法的工作量为 例例 3.3 试用高斯-若当消去法求解如下矩阵方程因为 解解$2 选主元素的消去法选主元素的消去法 主元素的选取通常采用两种方法，一种是全主元消去法全主元消去法,另一种是列主元消去法列主元消去法。下面以例介绍选主元的算法思想例例 3.4 试用选主元消去法解线性方程组（1）用全主元高斯消去法 回代解出：还原得：解解 （2）用全主元高斯-若当消去法 故得解为 （3）用列主元高斯消去法 回代解得 3.3 解线性方程组的矩阵分解法解线性方程组的矩阵分解法 一、一、非对称矩阵的三角分解法非对称矩阵的三角分解法 对于给定的线性方程组 矩阵分解法的基本思想是：（1）分解可逆下三角矩阵可逆上三角矩阵显见S是一个可逆的下三角阵解两个三角形方程组。Crout分解分解（以四阶为例）2.利用三角分解法解方程组利用三角分解法解方程组 例1.试用克洛特分解法解线性方程组 例2 试用克洛特分解法解线性方程组 解解 3.3.2 解三对角型线性方程组的追赶法解三对角型线性方程组的追赶法 1.用用LU分解矩阵分解矩阵A 3.3.3 对称正定矩阵的三角分解对称正定矩阵的三角分解 定义定义 3.1 若n 阶方矩阵 A 具有性质 且对任何n 维向量 成立 ，则称 A 为对称正定矩阵。定理定理3.4 若A 为对称正定矩阵，则 (1)A的k阶顺序主子式 (2)有且仅有一个单位下三角矩阵L和对角矩阵D 使得 （3-16）这称为矩阵的乔里斯基乔里斯基（Cholesky）分解分解。(3)有且仅有一个下三角矩阵 ，使 （3-17）这称为分解矩阵的平方根法平方根法。（1）首先由A 对称正定知 且对任何k维非零向量 故 为 k 阶对称正定矩阵，所以 由惟一性得 证证以下推导平方根法和乔里斯基分解法的计算公式。由此可建立平方根法的递推计算公式如下：类似地，由 得 从而可建立乔里斯基分解法的递推计算公式为 对于 依次计算例例 3.7 试分别用平方根法和乔里斯基分解法分解矩阵 (1)解解把平方根法应用于解方程组，则把 Ax=b 化为等价方程 相应的求解公式为 把乔里斯基分解法应用于解方程组，则 Ax=b 化为等价方程 相应的求解公式为 例例3.8 试用平方根法求解对称线性方程组 解解由此，可先由上三角形线性方程组 再由下三角形线性方程组 例例3.9 试用乔里斯基分解法解线性方程组 解解 3.4 解线性方程组的迭代法解线性方程组的迭代法 3.4.1 雅可比迭代法与高斯雅可比迭代法与高斯-塞德尔迭代法塞德尔迭代法 对 （3-23）以分量表示即 约化便得 雅可比雅可比（Jacobi）迭代迭代 从而可建立迭代格式则雅可比迭代格式（3-24）可用矩阵表示为 MJf J用矩阵表示为 对雅可比迭代格式修改得高斯高斯-塞德尔塞德尔（G-S）迭代迭代 f G-SMG-S例例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解 线性方程组 解解高斯-塞德尔迭代雅可比迭代令 取四位小数迭代计算 由雅可比迭代得 由高斯-塞德尔迭代得 相应的迭代公式为 3.4.2 迭代法的收敛性迭代法的收敛性 定义定义 3.2 设 n 阶线性方程组 的精确解为 x*相应的一阶定常迭代格式为 如果其迭代解 收敛于精确解 ，即 则称迭代格式（3-26）收敛 命题命题 3.2 记 的充分必要条件为 定理定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 则该迭代格式对任何初始向量 均收敛。证证 定理得证。相减得 则该迭代格式对任何初始向量 均收敛。定理定理 3.6 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 定理定理 3.7 若雅可比迭代法的迭代矩阵 满足条件（3-28）或（3-29），则雅可比迭代法与相应的高斯-塞德尔迭代法对任何初始向量 均收敛。推论推论 如果线性代数方程组 A x=b的系数矩阵 A 为严格对角占优矩阵，即则相应的雅可比迭代法与高斯-塞德尔迭代法对任何初始向量 均收敛。定理定理 3.8 一阶定常迭代格式 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即 这里 为 M 的特征值 定理定理 3.9 若线性方程组（3-1）的系数矩阵A对称正定，则相应的高斯-塞德尔迭代法必收敛。3.4.3 迭代法的应用说明迭代法的应用说明 (1)若系数矩阵非严格对角占优，采用等价变换使之约化为系数矩阵严格对角占优的线性方程组，然后用雅可比迭代法或高斯-塞德尔迭代法求解。(3)在实际计算时，由于无法知晓 x*，因此计算的终止原则通常近似地采用以下条件关系式(2)特殊情况可特殊处理，以减少工作量。
