第三章 线性方程组的解法 3.1 引言 3.2 解线性方程组的消去法 3.3 解线性方程组的矩阵分解法 3.4 解线性方程组的迭代法.

Presentation on theme: "第三章 线性方程组的解法 3.1 引言 3.2 解线性方程组的消去法 3.3 解线性方程组的矩阵分解法 3.4 解线性方程组的迭代法."— Presentation transcript:

1 第三章 线性方程组的解法 3.1 引言 3.2 解线性方程组的消去法 3.3 解线性方程组的矩阵分解法 3.4 解线性方程组的迭代法

2 3.1 引言 给定一个线性方程组 求解向量 x。

3 数值解法主要有两大类： 第一类是直接法。即按求精确解的方法运算求解。 第二类是迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组： 然后构造迭代格式 这称为一阶定常迭代格式，M 称为迭代矩阵。

4 3.2 解线性方程组的消去法 高斯消去法与高斯若当消去法 例1 第一步：先将方程（1）中未知数 的系数2除（1）的两 边，得到下列方程组：

5 再将第二个方程减去第一个方程的4倍，第三个方程减去
第一个方程的2倍。 第二步：将方程 中第二个方程的两边除以 的系数4

6 将第三个方程减去第二个方程： 第三步：为了一致期见，将第三个方程中的 系数变为1， 除以

7 我们来分析一下上述过程：整个过程分两大步。一是用
逐次消去未知数的方法，把原来的方程组化为与其等价的三 角形方程组。用矩阵的观点来看，就是用初等变换的方法将 方程组的系数矩阵进行初等变换，即

8 这样就将系数阵化为单位三角阵，这个过程称为“消元
过程”。二是解三角形方程组，称为“回代过程”，整个过程 称为“有回代过程的顺序消元法”。 下面我们来讨论一般的解n阶方程组的高斯消去法，且 就矩阵的形式来介绍这种新的过程：

9

10

11

12 一般地，第k步：即将矩阵变为如下

13

14

15 第n步：得到： 经过上述n步过程后，原系数矩阵A变为一个单位上三角 矩阵，即原方程组化为一个和它完全等价的三角形方程组， 即

16 高斯消去法： （1）消元过程： 对k=1,2, …, n 依次计算 (2) 回代过程：

17 例3.1 试用高斯消去法求解线性方程组 解 消元过程为

18 即把原方程组等价约化为 据之回代解得

19 为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即
相应地，计算公式可表述为： 从而得到解 这一无回代的消去法称为高斯-若当（Jordan）消去法

20 二、高斯-若当（Jordan）消去法 解

21

22 例 2 试用高斯-若当消去法求解例3.1的线性方程组。
因为

23 一般公式： 高斯约当消去法是一个具有消去过程而无回代过程的算法。 以上两种消去法都是沿系数矩阵的主对角线元素 进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。因此：

24

25 消去法的可行性和计算工作量 定理 3.1 如果的各阶顺序主子式均不为零，即有 即消去法可行。 推论 若系数矩阵严格对角占优，即有

26 定理 3.2 求解 n 阶线性方程组 (3-1) 的高斯消去法的乘除工作量约为 ，加减工作量约为 ；而高斯-若当消去法的乘除工作量约为 ，加减工作量约为 。
证 由式（3-4）知，高斯消去法在消元过程中第k步的工作量为 所以，消元过程的总工作量为

27 回代过程中的乘除和加减工作量均为 总工作量为 类似可得，高斯-若当消去法的工作量为

28 例 3.3 试用高斯-若当消去法求解如下矩阵方程 因为 解

29 $2 选主元素的消去法 主元素的选取通常采用两种方法，一种是全主元消去法,另一种是列主元消去法。 下面以例介绍选主元的算法思想 例 3.4 试用选主元消去法解线性方程组

30 解 （1）用全主元高斯消去法 回代解出： 还原得：

31 （2）用全主元高斯-若当消去法 故得解为 （3）用列主元高斯消去法 回代解得

32 3.3 解线性方程组的矩阵分解法 一、 非对称矩阵的三角分解法 矩阵分解法的基本思想是： 对于给定的线性方程组 （1） 分解 可逆下三角矩阵 可逆上三角矩阵

33

34 显见S是一个可逆的下三角阵 ——解两个三角形方程组。

35 Crout分解（以四阶为例）

36

37

38 2.利用三角分解法解方程组

39

40

41 例1. 试用克洛特分解法解线性方程组

42

43 例2 试用克洛特分解法解线性方程组 解

44

45 解三对角型线性方程组的追赶法 1.用LU分解矩阵A

46

47

48 对称正定矩阵的三角分解 定义 3.1 若n 阶方矩阵 A 具有性质 且对任何n 维向量 成立 ，则称 A 为对称正定矩阵。 定理3.4 若A 为对称正定矩阵，则 (1) A的k阶顺序主子式 (2)有且仅有一个单位下三角矩阵L和对角矩阵D 使得 （3-16） 这称为矩阵的乔里斯基（Cholesky）分解。 (3)有且仅有一个下三角矩阵 ，使 （3-17） 这称为分解矩阵的平方根法。

49 （1）首先由A 对称正定知 证 且对任何k维非零向量 故 为 k 阶对称正定矩阵，所以 由惟一性得

50 以下推导平方根法和乔里斯基分解法的计算公式。
由此可建立平方根法的递推计算公式如下：

51 类似地，由 得 从而可建立乔里斯基分解法的递推计算公式为 对于 依次计算

52 例 3.7 试分别用平方根法和乔里斯基分解法分解矩阵
(1)

53

54 把平方根法应用于解方程组，则把 Ax=b 化为等价方程
相应的求解公式为

55 把乔里斯基分解法应用于解方程组，则 Ax=b 化为等价方程
相应的求解公式为

56 例3.8 试用平方根法求解对称线性方程组 解 由此，可先由上三角形线性方程组

57 再由下三角形线性方程组

58 例 试用乔里斯基分解法解线性方程组 解

59

60 3.4 解线性方程组的迭代法 雅可比迭代法与高斯-塞德尔迭代法 对 （3-23） 以分量表示即 约化便得 从而可建立迭代格式 雅可比（Jacobi）迭代

61 则雅可比迭代格式（3-24）可用矩阵表示为 MJ f J

62 对雅可比迭代格式修改得 高斯-塞德尔（G-S）迭代 用矩阵表示为 MG-S f G-S

63 例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解
线性方程组 解 相应的迭代公式为 雅可比迭代 高斯-塞德尔迭代 令 取四位小数迭代计算 由雅可比迭代得 由高斯-塞德尔迭代得

64 迭代法的收敛性 定义 3.2 设 n 阶线性方程组 的精确解为 x* 相应的一阶定常迭代格式为 如果其迭代解 收敛于精确解 ，即 则称迭代格式（3-26）收敛 命题 3.2 记 的充分必要条件为

65 定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 则该迭代格式对任何初始向量 均收敛。 相减得 证 定理得证。

66 则该迭代格式对任何初始向量 均收敛。 定理 3.6 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件 定理 3.7 若雅可比迭代法的迭代矩阵 满足条件（3-28）或（3-29），则雅可比迭代法与相应的高斯-塞德尔迭代法对任何初始向量 均收敛。 推论 如果线性代数方程组 A x = b的系数矩阵 A 为严格对角占优矩阵，即 则相应的雅可比迭代法与高斯-塞德尔迭代法对任何初始向量 均收敛。

67 定理 3.8 一阶定常迭代格式 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即
这里 为 M 的特征值 定理 3.9 若线性方程组（3-1）的系数矩阵A对称正定，则相应的高斯-塞德尔迭代法必收敛。

68 迭代法的应用说明 (1) 若系数矩阵非严格对角占优，采用等价变换使之约化为系数矩阵严格对角占优的线性方程组，然后用雅可比迭代法或高斯-塞德尔迭代法求解。 (2) 特殊情况可特殊处理，以减少工作量。 (3) 在实际计算时，由于无法知晓 x* ，因此计算的终止原则通常近似地采用以下条件关系式