第三章 解线性方程组的直接法 （3.1） AX = b.

Presentation on theme: "第三章 解线性方程组的直接法 （3.1） AX = b."— Presentation transcript:

1 第三章 解线性方程组的直接法 （3.1） AX = b

2 §1 高斯消去法 1．三角形方程组的解法 （3.2） （3.3）

3 2．高斯消去法

4 消元公式 回代公式

5 列主元消去法计算步骤： 1、输入矩阵阶数n，增广矩阵 A(n,n+1); 2、对于 (1) 按列选主元：选取 l 使 (2) 如果 ，交换 A(n,n+1) 的第k行与底l 行元素 (3) 消元计算 ： 3、回代计算

6 4．无回代过程的主元消去法 算法： 第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行，
将主元行换至第一行，将第一个方程中x1的系数变为1，并从 其余n – 1个方程中消去x1。 第二步：在第二列后n – 1个元素中选主元，将第二个方程中x2的 系数变为1，并从其它n – 1个方程中消去x2。 ………… 第k步：在第k列后n – k个元素中选主元，换行，将第k个方程xk的系数 变为1，从其它n - 1个方程中消去变量xk，

7 消元公式为： 对k = 1, 2, …, 按上述步骤进行到第n步后，方程组变为： 即为所求的解

8 5．无回代消去法的应用 （1）解线性方程组系 设要解的线性方程组系为： AX = b1, AX = b2, … AX = bm 上述方程组系可以写为 AX = B = (b1, …, bm)

9 因此 X = A-1B 即为线性方程组系的解。 在计算机上只需要增加几组右端常数项的存贮单元， 其结构和解一个方程组时一样。 行 系数 右端

10 设A = (aij)nn是非奇矩阵，A  0，且令
（2）求逆矩阵 设A = (aij)nn是非奇矩阵，A  0，且令 由于 AA-1 = AX = I 因此，求A-1的问题相当于解下列线性方程组 相当于（1）中m = n, B = I 的情形。

11 （3）求行列式的值 用高斯消去法将 A化成

12 §2 解三对角方程组的追赶法

13

14 §3 矩阵的三角分解及其在解方程组中的应用  高斯消元法的矩阵形式: Step 1: L1－1 = 记 L1 = 记 于是

15

16

17 Step n  1: Lk = 其中

18 记为 L 记 U =

19 定理1：（矩阵的三角分解）设A为n  n实矩阵，如果
解AX = b用高斯消去法能够完成（限制不进行行的交 换，即 ），则矩阵A可分解 为单位下三角矩阵L与上三角知阵U的乘积。 A = LU 且这种分解是唯一的。

20 定理2：约化主元素（ , i = 1, 2, …, k） 充要条件是矩阵A的顺序主子式

21  杜立特分解法 /* Doolittle Factorization */：
—— LU 分解的紧凑格式 通过比较法直接导出L 和 U 的计算公式。 思路 反复计算, 很浪费哦 ……

22 直接三角分解法解AX = b的计算公式 (1) 对于r = 2, 3, …, n计算 （2）计算U的第r行元素 （3）计算L的第r 列元素 (r  n)

23 (4) (5)

24 §4 平方根法 1．矩阵的LDR分解 定理3：如果n阶矩阵A的所有顺序主子式均不等于零，
§4 平方根法 1．矩阵的LDR分解 定理3：如果n阶矩阵A的所有顺序主子式均不等于零， 则矩阵A存在唯一的分解式A = LDR其中L和R分别是 n阶单位下三角阵和单位上三角阵，D是n阶对角元素 的不为零的对角阵，上述分解也称为A的LDR分解。

25 2．平方根法 定理4：（对称正定矩阵的三角分解） 如果A为对称正定矩阵，则存在一个实的非奇异 下三角矩阵，使A=LLT ，且当限定的对角元素为正时， 这种分解是唯一的。

26 定理 将对称 正定阵 A 做 LU 分解 U = uij = A 对称 即 记 D1/2 = 则 仍是下三角阵
uij / uii 1 u22 unn 记为 A 对称 即 记 D1/2 = 则 仍是下三角阵 定理 设矩阵A对称正定，则存在非奇异下三角阵 使得 。若限定 L 对角元为正，则分解唯一。 注： 对于对称正定阵 A ，从 可知对任意k  i 有 。即 L 的元素不会增大，误差可控，不需选主元。

27 用平方根法解线性代数方程组的算法 （1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法： 对于 i = 1, 2,…, n 计算

28 （2）求解下三角形方程组 （3）求解LTX = y

29 3．改进平方根法 其中

30 改进平方根法解对称正定方程组的算法

31 令LTX = y，先解下三角形方程组LDY = b得

32 §5 向量和矩阵的范数 1．向量的范数 定义1：设X  R n，Ｘ 表示定义在Rn上的一个实值函数，
§5 向量和矩阵的范数 1．向量的范数 定义1：设X  R n，Ｘ 表示定义在Rn上的一个实值函数， 称之为X的范数，它具有下列性质： (1) 非负性：即对一切X  R n，X  0, Ｘ >0 (2) 齐次性：即对任何实数a  R，X  R n， （3）三角不等式：即对任意两个向量X、Y R n，恒有

33 三个常用的范数： 设X = (x1, x2,…, xn)T，则有 （1） （2） （3）

34 定理5：定义在Rn上的向量范数 是变量X分量的
一致连续函数。 定理6：在Rn上定义的任一向量范数 都与范数 等价， 即存在正数 M 与 m ( M>m ) 对一切XRn，不等式 成立。 推论：Rn上定义的任何两个范数都是等价的。

35 对常用范数，容易验证下列不等式：

36 定义2：设给定Rn中的向量序列{ }，即 其中 若对任何i (i = 1, 2,…, n )都有 则向量 称为向量序列{ }的极限，或者说向量序列{ } 依坐标收敛于向量，记为

37 定理7：向量序列{Xk}依坐标收敛于X*的充要条件是
向量序列依范数收敛与依坐标收敛是等价的。 2．矩阵的范数 定义3：设A为n 阶方阵，Rn中已定义了向量范数 ， 则称 为矩阵A的范数或模， 记为 。

38 矩阵范数的基本性质： （1）当A = 0时， ＝0，当A  0时， > 0 （2）对任意实数和任意A，有 （3）对任意两个n阶矩阵A、B有 （4）对任意向量XRn，和任意矩阵A，有 （5）对任意两个n阶矩阵A、B，有

39 定理8：设n 阶方阵A = (aij)nn，则
（Ⅰ）与 相容的矩阵范数是 （Ⅱ）与 相容的矩阵范数是 其中1为矩阵ATA的最大特征值。 （Ⅲ）与 相容的矩阵范数是

40 3．A 的范数与A 的特征值之间的关系 定理9：矩阵A 的任一特征值的绝对值不超过A的范数。 定义4：矩阵A 的诸特征值的最大绝对值称为A的谱半径， 记为：

41 §6 线性方程组的性态和解的误差分析 求解 时，A 和 的误差对解 有何影响？  设 A 精确， 有误差 ，得到的解为 ，即 又
§6 线性方程组的性态和解的误差分析 求解 时，A 和 的误差对解 有何影响？  设 A 精确， 有误差　 ，得到的解为 ，即 绝对误差放大因子 相对误差放大因子 又

42 大 是关键  设 精确，A有误差 ，得到的解为 ，即 的误差放大因子，称为 A的条件数，记为cond (A) , 越 则 A 越病态，
§2 Error Analysis for 是关键 的误差放大因子，称为 A的条件数，记为cond (A) , 越 则 A 越病态， 难得准确解。  设 精确，A有误差 　 ，得到的解为 ，即 大 Wait a minute … Who said that ( I + A1 A ) is invertible? (只要 A充分小，使得

43 定义5：设A 为n 阶非奇矩阵，称数 为矩阵A的条件数，
记为cond( A )。 条件数的性质： ⅰ）cond ( A )≥1 ⅱ）cond ( kA )= cond ( A ) k 为非零常数 ⅲ）若 ， 则

44 2.9  106  行列式很大或很小（如某些行、列近似相关）；  元素间相差大数量级，且无规则；  主元消去过程中出现小主元；
例：Hilbert 阵 cond (H2) = 27 cond (H3)  748 2.9  106 cond (H6) = cond (Hn)  as n   注：一般判断矩阵是否病态，并不计算A1，而由经验得出。  行列式很大或很小（如某些行、列近似相关）；  元素间相差大数量级，且无规则；  主元消去过程中出现小主元；  特征值相差大数量级。

45  改善方法：  近似解的误差估计及改善： 设 的近似解为 ，则一般有 误差上限 若 可被精确解出，则有 就是精确解了。
设　　 的近似解为　 ，则一般有 误差上限 cond (A)  改善方法： Step 1:　　　　　近似解 Step 2: 若　 可被精确解出，则有 就是精确解了。 Step 3: Step 4: 经验表明：若 A 不是非常病态（例如： ），则如此迭代可达到机器精度；但若 A 病态，则此算法也不能改进。