计算方法方程组b 2013年最新西安交通大学《数值分析》ppt课件

2.2 Tridiagonal System 2.2 追赶法 将高斯消去法 直接应用于 三对角方程 三对角方程组 /* Tridiagonal Linear System */ Step 1: 追即消元 Step 2: 赶即回代： 一旦bi-ui-1ai=0 算法中断 2.2 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: 证明：只需证明公式中分母 bi-ui-1ai0,i=2,3,n-1。设 ki=bi-ui-1ai,根据右式和对角 占优条件，有 定理 若 A 为对角占优 /* diagonally dominant */ 的三对角 阵，既满足 ， 则追赶法可解以 A 为系数矩阵的方程组。 2.2 Tridiagonal System 例 求解三对角方程 iaibicidibi- uiai uiyixi 10211 0.50.51 212101.5.667.3331 312101.3330.750.251 412011.2511 解： 2.2 Tridiagonal System 2.3 Matrix Factorization 如果线性代数方程组能化成以下形式启示 2.3 三角分解法 /* Matrix Factorization */ 上三角阵Upper- triangular 下三角阵Lower- triangular Could we factorize A into triangular matrix directly? Sure! for example Doolittle Factorization, Crout Factorization etc. 高斯消元法的矩阵形式 /* Matrix Form of G.E. */： Step 1: 记 L1 =，则 Step n 1:其中 Lk = 2.3 Matrix Factorization Matrix Form of G.E. 记为 L 单位下三角阵 /* unitary lower-triangular matrix */ 记 U = A 的 LU 分解 /* LU factorization */ 2.3 Matrix Factorization Matrix Form of G.E. 2.3 Matrix Factorization Doolittle 道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */ 通过比较法直接导出L 和 U 的计算公式。 思 路 根据矩阵相乘法则，有 lii=1, i=1,2,n 2.3 Matrix Factorization Doolittle u11=a11, u12=a12, , u1n=a1n l21=a21/u11 l31=a31/u11 ln1=an1/u11 u22=a22l21u12, , u2n=a2nl21u1n l32=(a32l31u12)/u22 ln2=(an2ln1u12)/u22 uij lji 2.3 Matrix Factorization Doolittle Algorithm: Doolittle Factorization Step 1: u1j = a1j ; lj1= aj1/u11; ( j = 1, , n ) Step 2: compute uij and lji for i = 2, , n1; uij lji 2.3 Matrix Factorization Choleski 平方根法 /* Choleskis Method */： 对称 /* symmetric */ 正定 /* positive definite */ 矩阵的分解法 定义 一个矩阵 A 称为正定阵，如果 对任意非 零向量 都成立。 回顾：对称正定阵的几个重要性质 A1 亦对称正定，且 aii 0 A 的顺序主子阵 /* leading principal submatrices */ Ak 亦对 称正定 A 的特征值 /* eigen value */ i 0 A 的全部顺序主子式 det ( Ak ) 0 定义一个矩阵 A = ( aij )nn 称为对称阵，如果 aij = aji 。 证明： 根据矩阵相乘法则，有 一旦ljj=0算法 中断 定理 设矩阵A对称正定，则存在非奇异下三角阵 使得 。若限定 L 对角元为正，则分解唯一。 2.3 Matrix Factorization Choleski 证明：A是正定阵，所以A 的全部顺序主子式 det ( Ak ) 0 又对称正定矩阵A的各阶主子矩阵Ak都是对称正定矩阵，因此， 都可以分解成Ak=LkLkT，这里Lk是L的k阶主子矩阵，两边求行列 式，有 又因为det(Ak)0, k=1,2,n,所以恒有l2kk 0，故lkk 全部为 非零实数。 因此有 由于求lkk 时要开根号，根号前符号可正可负。如果我们限定 lkk 都取正值，则按计算公式可以唯一确定矩阵L。证毕。 2.3 Matrix Factorization Choleski 平方根法求解方程组 对称正定方程 Ax=b A=LLT LLTx=b 设LTx=y，那么求解方程可以归结为求解两个三角方程： Ly=b 和 LTx=y 2.3 Matrix Factorization Choleski 注：计算顺序是注：计算顺序是 d d 1 1 l l21 21 d d 2 2 l l31 31 l l32 32 d d 3 3 对称正定矩阵A可以分解成A=LDLT的形式，其中定理 改进的平方根法 单位下三角阵 对角阵 2.3 Matrix Factorization Choleski A=LDLT 改进平方根法求解方程组 对称正定方程 Ax=bLDLTx=b 左乘D-1 DLTx=yLTx=D-1y 设 DLTx=y，那么求解方程可以归结为求解两个三角方程： Ly=b 和 DLTx=y ? 2.3 Matrix Factorization Choleski 程序设计 因为A 对称，所以只需存半个 A，即 其中 2.3 Matrix Factorization Choleski 2 Matrix Factorization Tridiagonal System Lab 06. Crout Reduction for Tridiagonal Linear Systems Apply Crout Reduction to solve a given nn tridiagonal linear system Input There are several sets of inputs. For each set: The 1st line contains an integer 100 n 0 which is the size of a matrix. n = 1 signals the end of file. The 2nd line contains n1 real numbers . The 3rd line contains n real numbers . The 4th line contains n1 real numbers . The 5th line contains n real numbers . The numbers are separated by spaces. 2 Matrix Factorization Tridiagonal System Output Each entry of the solution is to be printed as in the C fprintf: fprintf(outfile, “%16.8en“, x ); If the method fails to give a solution, print the message “TheCroutmethodfailed.n”. /* here represents a space*/ The outputs of two test cases must be seperated by a blank line. Sample Input ( represents a space) 5 1