第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: （蓝色）建筑工程中的结构力学问题;

Presentation on theme: "第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: （蓝色）建筑工程中的结构力学问题;"— Presentation transcript:

1 第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: （蓝色）建筑工程中的结构力学问题;
第三章 线性代数方程组的解法 在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如: （蓝色）建筑工程中的结构力学问题; 用最小二乘法求实验数据的曲线拟合问题; 用差分法或者有限元法解常微分方程，偏微分方程边值问题。 大型线性方程组 计算量大 高效率、高精度算法

2 直接法 线性代数方程组的解法 迭代法 Gauss消去法 三角分解法 …… Jacobi迭代法 Gauss-Seidel迭代法 超松弛迭代法

3 设有线性方程组 记

4 §1 直接法 上三角方程组 4

5 写出矩阵形式为： 上三角矩阵 5

6 若uii≠0（i=1,2,……n）,则由下至上依次可算得
回代过程 方法简单、计算量小 6

7 1.1 Gauss消元法 线性代数方程组 三角形方程组 回代求解 例 用高斯消元法解方程组 Step1: 用第一个方程消去后两个方程中的x1

8 Step2: 用第二个方程消去第三个方程中的x2
上三角方程组 Step3: 回代求解 Step1 Step2 消元过程 Step3 回代过程

9 考虑方程组 增广矩阵表示

10 第一次消元 条件：

11 第二次消元 条件：

12 第k次消元 条件：

13 第n-1次消元(最后一次消元)

14 回代求解

15 Gauss消元法能进行的条件： 约化主元素 （去掉箭头边框）充要条件 矩阵A的顺序主子式 即

16 例 用高斯消去法解线性方程组 16

17 解 回代得

18 1.2 列主元消元法 ≠0 （k=1,2,……n-1）； 高斯消去法的问题： 顺序消元法 若 很大，舍入误差会放大。 主元消元法：
若 很大，舍入误差会放大。 顺序消元法 主元消元法： 与高斯消去法相似； 防止舍入误差的增长； 选绝对值最大的作为约化主元，进行列或行交换。 完全主元消元法 行主元消元法 列主元消元法 行、列交换 列交换 行交换 18

19 具体过程： 设k步消元得到： 19

20 在进行第k+1步消元前，选出第k+1列中位于对角线及其以下元素绝对值中的最大值者，即使得
将第t行和第k行互相交换； 再按高斯消元法进行第k步消元； 20

21 例 用列主元高斯消去法解线性方程组 21

22 解 回代得

23 1.3 矩阵的三角（LU）分解法 基本思想 下角阵 上三角阵 ①由下三角方程组 LY=b 求 Y ②由上三角方程组 UX=Y 求 X

24 Doolittle分解 Crout分解 追赶法 平方根法 A为一般稠密矩阵 常用三角分解法 A为三对角线矩阵 A为对称正定矩阵

25 1.3.1 Doolittle分解法 高斯消元法 消元 若

26 单位下三角阵 上三角阵 Doolittle分解 Gauss消元法，实质是将系数矩阵进行Doolittle分解！

27 证明Doolittle分解的唯一性 设对于矩阵A，同时有两种Doolittle分解 分解唯一 （定理3.12） 单位下三角阵 上三角阵

28 Doolittle分解法

29 A第一行 A第一列 A第二行 A第二列

30 L和U的计算公式

31 例 用Doolittle分解法解线性方程组

32

33 求解 ① LY=b Y=(14,-10,-72)T X=(1,2,3)T ② UX=Y

34 1.3.2 Crout分解法 下三角阵 单位上三角阵 利用矩阵乘法，可以逐一求出L和U中的各个元素！

35 1.3.3 追赶法 常微分方程边值问题 热传导方程 三次样条函数 …… 三对角线方程

36 Gauss消元法 u1 q1 第一次消元

37 u2 q2

38 第二次消元

39 u3 …… q3

40 第n-1次消元

41 回代求解 “追”：按公式顺序求出ui，qi 消元 回代 “赶”：按公式逆序求出xn，xn-1 …… x2，x1

42 例 用追赶法解线性方程组

43

44

45 1.3.4 平方根法 要求： A为对称正定矩阵 A对称正定 再分解

46

47 A对称 分解唯一性

48 ①根据矩阵乘法确定 中的元素 ②求解

49 例 用平方根法解线性方程组 解： A是对称正定矩阵，可用平方根法求解

50

51 直接法：经过有限步算术运算，可求得方程组的精确解的方法。多应用于阶数较低的线性代数方程组。
线性代数方程组的数值解法： 直接法：经过有限步算术运算，可求得方程组的精确解的方法。多应用于阶数较低的线性代数方程组。 迭代法：用某种极限过程去逐步逼近线性方程组精确解，可求得方程组的近似解的方法。多应用于求解大型线性代数方程组。 51

52 §2 向量和矩阵的范数 为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量——向量和矩阵的范数。 52

53 2.1向量的范数 对空间直角坐标系任意向量 其长度为： 它满足如下三个条件： ①对任意向量X，|X|≥0，|X|=0当且仅当X =0;
非负性 ②对任意常数c和向量X ，有|c X |=|c|·| X |; 齐次性 ③对任意向量X和Y，有| X + Y |≤| X | + | Y |。 三角不等式 推广

54 定义1 设N(X)=||X||是定义在Rn上的实函数，如果它满足如下条件：
向量范数的定义 定义1 设N(X)=||X||是定义在Rn上的实函数，如果它满足如下条件： ①非负性 对任意向量X，||X||≥0，||X||=0当且仅当X =0; ②齐次性 对任意常数c和向量X ，有||c X ||=||c||·|| X ||; ③三角不等式 对任意向量X和Y，有|| X + Y ||≤|| X || +|| Y ||。 则称N(X)=||X||为Rn上向量X的范数 54

55 最常用的是三种向量范数 向量的1-范数： 向量的2-范数： 向量的∞-范数： 示例结果：12，5倍根号10，5 例 求 的三种范数。 55

56 2.2矩阵的范数 定义2 矩阵A∈Rn×n，设N(A)=||A||是矩阵A的实函数，如果它满足如下条件：
①非负性 对任意矩阵A，||A||≥0，||A||=0当且仅当A =0; ②齐次性 对任意常数c和矩阵A ，有||c A ||=|c|·|| A ||; ③三角不等式 对任意矩阵A和B，有|| A + B ||≤|| A || + || B ||; ④矩阵乘法不等式 对任意矩阵A和B，有||AB|| ≤|| A || || B ||。 则称N(A)=||A||为Rn×n上矩阵A的范数

57 向量 X 矩阵 A 向量范数 ||X|| 矩阵、向量相乘的相容性 协调 矩阵范数 ||A|| || AX ||≤||A|| ||X||

58 矩阵A的r范数 矩阵的1-范数： 矩阵的2-范数： 矩阵的∞-范数： 列模 谱模 行模 表示 的最大特征值

59 例 求矩阵的1-范数，2-范数，∞-范数 解：

60 2.3 矩阵的条件数 例 病态方程组

61 ① 仅b有扰动

62 ② 仅A有扰动

63 条件数 常用的条件数 定义4 若 ，AX=b为病态方程组； 若 相对的小，AX=b为良态方程组。

64 例 判断如下方程组的性态 解： >>1 该方程组是病态方程组

65 方程组可能病态的情形： ① 用选主元消去法消元过程中出现小主元； ②系数行列式的绝对值相对很小； ③系数矩阵的各元素间在数量级上相差很大且无 规律； ④出现了相对很大的解。

66 §3 迭代法 非线性方程求根 f (x) = 0 x = g (x) 等价变换 线性代数方程组求根 等价变换 初始向量

67 迭代公式 迭代矩阵 收敛 迭代序列 发散

68 例 求解线性方程组 解： 将原方程组改写为 迭代格式

69 精确解

70 设线性方程组的一般形式为

71 依此类推,线性方程组可化为

72

73 令

74 Jacobi迭代法 等价

75 3.1 Jacobi迭代法 分量形式 矩阵形式 例 用Jacobi迭代法求解方程组,误差不超过10-4

76 解: ①分量形式 ②矩阵形式

77

78

79 依此类推 X4 = ε = X5 = ε = X6 = ε = X7 = ε = X8 = ε = X9 = ε = ×10-4 X10 = ε = ×10-4 X11 = ε = ×10-4 X12 = ε = ×10-5 迭代次数 为12次

80 分析Jacobi迭代法的迭代过程，其分量形式为

81 即

82

83 Gauss-Seidel迭代法

84 3.2 Gauss-Seidel迭代法 分量形式 矩阵形式

85 用Gauss-Seidel迭代法求解方程组,误差不超过10-4。
例 用Gauss-Seidel迭代法求解方程组,误差不超过10-4。 解: ①分量形式

86 ②矩阵形式

87

88 依此类推 X3 = ε = X4 = ε = X5 = ε = X6 = ε = X7 = ε = 迭代次数为7次

89 迭代法收敛的充要条件 定理 迭代法收敛的充要条件是 ，其中B迭代矩阵， 为迭代矩阵的谱半径，定义为

90 例 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组，判断其收敛性。
解： ①Jacobi迭代法 收敛

91 ②Gauss-Seidel迭代法 收敛

92 3.3 超松弛迭代法（SOR方法） 松弛因子 分量形式

93 矩阵形式 低松弛法 超松弛法

94 例 用迭代法解方程组，要求精确到0.001 解： ①Jacobi迭代法 迭代公式 取初始向量

95 ②Gauss-Seidel迭代法 取初始向量

96 ③SOR迭代法 取初始向量