计算方法课件第三章线性代数方程组的数值解法-

1、第三章 线性代数方程组的数 值解法 3.1 引言3.2 解线性方程组的消去法3.3 解线性方程组的矩阵分解法3.4 解线性方程组的迭代法第三章 线性代数方程组的数3.1 引言3.1 引言 给定一个线性方程组求解向量 x。 3.1 引言 给定一个线性方程组求解向量 x。 第一类是直接法。即按求精确解的方法运算求解。第二类是迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组：数值解法主要有两大类：然后构造迭代格式这称为一阶定常迭代格式，M 称为迭代矩阵。 第一类是直接法。即按求精确解的方法运算求解。数值解法主要有两 3.2 解线性方程组的消去法 3.2.1 高斯消去法与高斯若当消

2、去法 例1 第一步：先将方程（1）中未知数 的系数2除（1）的两边，得到下列方程组： 3.2 解线性方程组的消去法 3.2.1 高斯消 再将第二个方程减去第一个方程的4倍，第三个方程减去第一个方程的2倍。 第二步：将方程 中第二个方程的两边除以 的系数4 再将第二个方程减去第一个方程的4倍，第三个方程 将第三个方程减去第二个方程： 第三步：为了一致期见，将第三个方程中的 系数变为1，除以 将第三个方程减去第二个方程： 第三步：为了一致期见， 我们来分析一下上述过程：整个过程分两大步。一是用逐次消去未知数的方法，把原来的方程组化为与其等价的三角形方程组。用矩阵的观点来看，就是用初等变换的方法将方

3、程组的系数矩阵进行初等变换，即 我们来分析一下上述过程：整个过程分两大步。 这样就将系数阵化为单位三角阵，这个过程称为“消元过程”。二是解三角形方程组，称为“回代过程”，整个过程称为“有回代过程的顺序消元法”。 下面我们来讨论一般的解n阶方程组的高斯消去法，且就矩阵的形式来介绍这种新的过程： 这样就将系数阵化为单位三角阵，这个过程称为计算方法课件第三章线性代数方程组的数值解法-计算方法课件第三章线性代数方程组的数值解法-计算方法课件第三章线性代数方程组的数值解法- 一般地，第k步：即将矩阵变为如下 一般地，第k步：即将矩阵变为如下计算方法课件第三章线性代数方程组的数值解法-计算方法课件第三章线

4、性代数方程组的数值解法- 第n步：得到： 经过上述n步过程后，原系数矩阵A变为一个单位上三角矩阵，即原方程组化为一个和它完全等价的三角形方程组，即 第n步：得到： 经过上述n步过程后，原系数矩阵A变为一高斯消去法： （1）消元过程： 对k=1,2, , n 依次计算 (2) 回代过程： 高斯消去法： (2) 回代过程： 例3.1 试用高斯消去法求解线性方程组 消元过程为 解 例3.1 试用高斯消去法求解线性方程组 消元过程为 解即把原方程组等价约化为 据之回代解得即把原方程组等价约化为 据之回代解得为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即 相应地，

5、计算公式可表述为： 从而得到解这一无回代的消去法称为高斯-若当（Jordan）消去法 为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为二、高斯-若当（Jordan）消去法 解二、高斯-若当（Jordan）消去法 解计算方法课件第三章线性代数方程组的数值解法-例 2 试用高斯-若当消去法求解例3.1的线性方程组。 因为 解例 2 试用高斯-若当消去法求解例3.1的线性方程组。 因一般公式： 高斯约当消去法是一个具有消去过程而无回代过程的算法。 以上两种消去法都是沿系数矩阵的主对角线元素进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k

6、)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。因此：一般公式： 高斯约当消去法是一个具有消去过程而无回代计算方法课件第三章线性代数方程组的数值解法- 3.2.2 消去法的可行性和计算工作量 定理 3.1 如果的各阶顺序主子式均不为零，即有即消去法可行。推论 若系数矩阵严格对角占优，即有 3.2.2 消去法的可行性和计算工作量 定理 3.1 定理 3.2 求解 n 阶线性方程组 (3-1) 的高斯消去法的乘除工作量约为 ，加减工作量约为 ；而高斯-若当消去法的乘除工作量约为 ，加减工作量约为 。由式（3-4）知，高斯消去法在消元过程中第k步的工作量为所以，消元过程的总工作量为证

7、定理 3.2 求解 n 阶线性方程组 (3-1) 的高斯消回代过程中的乘除和加减工作量均为总工作量为 类似可得，高斯-若当消去法的工作量为 回代过程中的乘除和加减工作量均为总工作量为 类似可得，高斯-例 3.3 试用高斯-若当消去法求解如下矩阵方程因为 解例 3.3 试用高斯-若当消去法求解如下矩阵方程因为 解 $2 选主元素的消去法 主元素的选取通常采用两种方法，一种是全主元消去法,另一种是列主元消去法。 下面以例介绍选主元的算法思想例 3.4 试用选主元消去法解线性方程组 $2 选主元素的消去法 主元素的选取通常采用两种方法，（1）用全主元高斯消去法 回代解出： 还原得： 解（1）用全主元

8、高斯消去法 回代解出： 还原得： 解 （2）用全主元高斯-若当消去法 故得解为 （3）用列主元高斯消去法 回代解得 （2）用全主元高斯-若当消去法 故得解为 （3） 3.3 解线性方程组的矩阵分解法 一、 非对称矩阵的三角分解法 对于给定的线性方程组 矩阵分解法的基本思想是： （1） 分解可逆下三角矩阵可逆上三角矩阵 3.3 解线性方程组的矩阵分解法 一、 非对称矩阵的计算方法课件第三章线性代数方程组的数值解法-显见S是一个可逆的下三角阵解两个三角形方程组。显见S是一个可逆的下三角阵解两个三角形方程组。Crout分解（以四阶为例） Crout分解（以四阶为例） 计算方法课件第三章线性代数方程组

9、的数值解法-计算方法课件第三章线性代数方程组的数值解法-2.利用三角分解法解方程组 2.利用三角分解法解方程组 计算方法课件第三章线性代数方程组的数值解法-计算方法课件第三章线性代数方程组的数值解法- 例1. 试用克洛特分解法解线性方程组 例1. 试用克洛特分解法解线性方程组 计算方法课件第三章线性代数方程组的数值解法- 例2 试用克洛特分解法解线性方程组 解 例2 试用克洛特分解法解线性方程组 解计算方法课件第三章线性代数方程组的数值解法- 3.3.2 解三对角型线性方程组的追赶法 1.用LU分解矩阵A 3.3.2 解三对角型线性方程组的追赶法 1.用LU计算方法课件第三章线性代数方程组的数

10、值解法-计算方法课件第三章线性代数方程组的数值解法- 3.3.3 对称正定矩阵的三角分解 定义 3.1 若n 阶方矩阵 A 具有性质 且对任何n 维向量 成立 ，则称 A 为对称正定矩阵。 定理3.4 若A 为对称正定矩阵，则 (1) A的k阶顺序主子式 (2)有且仅有一个单位下三角矩阵L和对角矩阵D 使得 （3-16）这称为矩阵的乔里斯基（Cholesky）分解。 (3)有且仅有一个下三角矩阵 ，使 （3-17）这称为分解矩阵的平方根法。 3.3.3 对称正定矩阵的三角分解 定义 3.1 若 （1）首先由A 对称正定知 且对任何k维非零向量 故 为 k 阶对称正定矩阵，所以 由惟一性得 证

11、（1）首先由A 对称正定知 且对任何k维非零向量 以下推导平方根法和乔里斯基分解法的计算公式。 由此可建立平方根法的递推计算公式如下： 以下推导平方根法和乔里斯基分解法的计算公式。 由此可建立平方类似地，由 得 从而可建立乔里斯基分解法的递推计算公式为 对于 依次计算类似地，由 例 3.7 试分别用平方根法和乔里斯基分解法分解矩阵 (1) 解例 3.7 试分别用平方根法和乔里斯基分解法分解矩阵 计算方法课件第三章线性代数方程组的数值解法-把平方根法应用于解方程组，则把 Ax=b 化为等价方程 相应的求解公式为 把平方根法应用于解方程组，则把 Ax=b 化为等价方程 相应把乔里斯基分解法应用于解

12、方程组，则 Ax=b 化为等价方程 相应的求解公式为 把乔里斯基分解法应用于解方程组，则 Ax=b 化为等价方程 例3.8 试用平方根法求解对称线性方程组 解由此，可先由上三角形线性方程组 例3.8 试用平方根法求解对称线性方程组 解由此，可先由上再由下三角形线性方程组 再由下三角形线性方程组 例3.9 试用乔里斯基分解法解线性方程组 解 例3.9 试用乔里斯基分解法解线性方程组 解计算方法课件第三章线性代数方程组的数值解法- 3.4 解线性方程组的迭代法 3.4.1 雅可比迭代法与高斯-塞德尔迭代法 对 （3-23）以分量表示即 约化便得 雅可比（Jacobi）迭代 从而可建立迭代格式 3.

13、4 解线性方程组的迭代法 3.4.1 雅可比迭代则雅可比迭代格式（3-24）可用矩阵表示为 MJf J则雅可比迭代格式（3-24）可用矩阵表示为 MJf J用矩阵表示为 对雅可比迭代格式修改得高斯-塞德尔（G-S）迭代 f G-SMG-S用矩阵表示为 对雅可比迭代格式修改得高斯-塞德尔（G-S）迭例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解 线性方程组 解高斯-塞德尔迭代雅可比迭代令 取四位小数迭代计算 由雅可比迭代得 由高斯-塞德尔迭代得 相应的迭代公式为例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解解高 3.4.2 迭代法的收敛性 定义 3.2 设 n 阶线性方程组 的精

14、确解为 x* 相应的一阶定常迭代格式为 如果其迭代解 收敛于精确解 ，即 则称迭代格式（3-26）收敛 命题 3.2 记 的充分必要条件为 3.4.2 迭代法的收敛性 定义 3.2 设 n 阶定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 则该迭代格式对任何初始向量 均收敛。 证 定理得证。 相减得 定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵则该则该迭代格式对任何初始向量 均收敛。 定理 3.6 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 定理 3.7 若雅可比迭代法的迭代矩阵 满足条件（3-28）或（3-29），则雅可比迭代法与相应的高斯-塞德尔迭代法对任何初始向量 均收敛。 推论 如果线性代数方程组 A x = b的系数矩阵 A 为严格对角占优矩阵，即则相应的雅可比迭代法与高斯-塞德尔迭代法对任何初始向量 均收敛。 则该迭代格式对任何初始向量 均收敛。 定理 3.8 一阶定常迭代格式 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即 这里 为 M 的特征值 定理