数值分析第三章 解线性方程组的直接方法

1、Ch5 解线性方程组的直接方法,求解,高斯消元法,消元,记,其中,Step k：设 ，计算因子 且计算,共进行 ？ 步,n 1,回代,No unique solution exists,What if we cant find such k ,No unique solution exists,定理,若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解,注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解,1 Gau

2、ssian Elimination The Method,选主元消去法,例：单精度解方程组,用Gaussian Elimination计算,8个,小主元 /* Small pivot element */ 可能导致计算失败,全主元消去法 /* Complete Pivoting *,每一步选绝对值最大的元素为主元素，保证,Step k: 选取,If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列,消元,注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来,列主元消去法 /* Partial Pivoting, or maxi

3、mal column pivoting *,省去换列的步骤，每次仅选一列中最大的元,例,注：列主元法没有全主元法稳定,例,标度化列主元消去法 /* Scaled Partial Pivoting *,对每一行计算 。为省时间，si 只在初始时计算一次。以后每一步考虑子列 中 最大的 aik 为主元,注：稳定性介于列主元法和全主元法之间,1 Gaussian Elimination Pivoting Strategies,2 三角分解法 /* Matrix Factorization *,高斯消元法的矩阵形式 /* Matrix Form of G.E. *,Step 1,2 Matrix Fa

4、ctorization Matrix Form of G.E,单位下三角阵 /* unitary lower-triangular matrix *,A 的 LU 分解 /* LU factorization *,Hey hasnt GE given me enough headache? Why do I have to know its matrix form,When you have to solve the system for different with a fixed A,Could you be more specific, please,Factorize A first,

5、 then for every you only have to solve two simple triangular systems and,2 Matrix Factorization Matrix Form of G.E,证明：由1中定理可知，LU 分解存在。下面证明唯一性,若不唯一，则可设 A = L1U1 = L2U2 ，推出,Upper-triangular,Lower-triangular With diagonal entries 1,注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Cr

6、out 分解,2 Matrix Factorization Doolittle,道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form *,反复计算, 很浪费哦,2 Matrix Factorization Choleski,平方根法 /* Choleskis Method */： 对称 /* symmetric */ 正定 /* positive definite */ 矩阵的分解法,回顾：对称正定阵的几个重要性质,A1 亦对称正定，且 aii 0,若不然，则,对任意 , 存在 , 使得 , 即,A 的顺序主子阵 /*

7、 leading principal submatrices */ Ak 亦对 称正定,对称性显然。对任意 有 , 其中,A 的特征值 /* eigen value */ i 0,设对应特征值 的非零特征向量 为 ，则,A 的全部顺序主子式 det ( Ak ) 0,因为,2 Matrix Factorization Choleski,将对称 正定阵 A 做 LU 分解,即,Why is uii 0,Since det(Ak) 0,则 仍是下三角阵,注： 对于对称正定阵 A ，从 可知对任意k i 有 。即 L 的元素不会增大，误差可控，不需选主元,2 Matrix Factorization

8、 Choleski,Algorithm: Choleskis Method To factor the symmetric positive definite nn matrix A into LLT, where L is lower triangular. Input: the dimension n; entries aij for 1 i, j n of A. Output: the entries lij for 1 j i and 1 i n of L. Step 1 Set ; Step 2 For j = 2, , n, set ; Step 3 For i = 2, , n1

9、, do steps 4 and 5 Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ; Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP,因为A 对称，所以只需存半个 A，即 其中,运算量为 O(n3/6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间(p.50-51,HW: p.54 #2, #5, #6,2 Matrix Factorization Tridiagonal System,追赶法解三对角方程组 /* Crout

10、 Reduction for Tridiagonal Linear System *,Step 1: 对 A 作Crout 分解,直接比较等式两边的元素，可得到计算公式（p.52,Step 2: 追即解,Step 3: 赶即解,与G.E.类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解,2 Matrix Factorization Tridiagonal System,Hey, what does diagonally dominant mean,It means that the diagonal entries of the matrix are very LARGE,Well, how large is LARGE,They satisfy the following inequality,注： 如果 A 是严格对角