南大数值分析课件第三章 解线性方程组的直接法.ppt

第三章解线性方程组的直接法
/* Direct Method for Solving Linear Systems */
求解
§1 高斯消元法/* Gaussian Elimination */
高斯消元法:
思路
首先将A化为上三角阵/* upper-triangular matrix */,再回代求解/* backward substitution */。
=
§1 Gaussian Elimination – The Method
消元
记
Step 1:设,计算因子
将增广矩阵/* augmented matrix */ 第 i 行 mi1 第1行,得到
其中
Step k:设,计算因子
且计算
共进行? 步
n  1
回代
What if ?
No unique solution exists.
What if ?
Then we must find the smallest integer k  i with
, and interchange the k-th row with the i-th row.
What if we can’t find such k ?
No unique solution exists.
定理
若A的所有顺序主子式/* determinant of leading principal submatrices */ 均不为0,则高斯消元无需换行即可进行到底,得到唯一解。
注:事实上,只要 A 非奇异,即 A1 存在,则可通过逐次消元及行交换,将方程组化为三角形方程组,求出唯一解。
§1 Gaussian Elimination – The Method
选主元消去法/* Pivoting Strategies */
例:单精度解方程组
/* 精确解为和*/
8个
8个
用Gaussian Elimination计算:
8个
小主元/* Small pivot element */ 可能导致计算失败。
§1 Gaussian Elimination – Pivoting Strategies
全主元消去法/* Complete Pivoting */
每一步选绝对值最大的元素为主元素,保证。
Step k: ①选取
② If ik  k then 交换第 k 行与第 ik 行;
If jk  k then 交换第 k 列与第 jk 列;
③消元
注:列交换改变了 xi 的顺序,须记录交换次序,解完后再换回来。
列主元消去法/* Partial Pivoting, or maximal column pivoting */
省去换列的步骤,每次仅选一列中最大的元。
§1 Gaussian Elimination – Pivoting Strategies
例:

注:列主元法没有全主元法稳定。
例:
注意:这两个方程组在数学上严格等价。

标度化列主元消去法/* Scaled Partial Pivoting */
对每一行计算。为省时间,si 只在初始时计算一次。以后每一步考虑子列中最大的 aik 为主元。
注:稳定性介于列主元法和全主元法之间。
§1 Gaussian Elimination – Pivoting Strategies
§1 Gaussian Elimination – Pivoting Strategies
实际应用中直接调用Gauss Elimination 解3阶线性方程组的结果:
结合全主元消去后的结果:
高斯-若当消去法/* Gauss-Jordan Method */
与 Gaussian Elimination 的主要区别:
每步不计算 mik ,而是先将当前主元 akk(k) 变为 1;
把 akk(k) 所在列的上、下元素全消为0;
Hey! Isn’t it better than Gaussian Elimination?
What makes you say so?
Obviously we no longer need the backward substitution!
You’d better wait till we go through the next section to draw your conclusion…
§1 Gaussian Elimination – Gauss-Jordan Method
运算量/* Amount putation */
§1 Gaussian Elimination – Amount putation
由于计算机中乘除