三角分解解线性程组的公式.ppt

yfnie@nwpu.edu.cn 且A 的第 个分量为 即有 （b） 结合（a），（b）得 取向量 其中 （j=1，2，…，n） （2）证明与（1）类似。 算子范数（续） 这说明 证明 （3）因A为实矩阵，故 为实对称的，并且还是非负定的。 设 为任一非零向量，则有 故 的特征值排列为 其中 为标准正交的特征向量， 为组合系数。设 算子范数（续） 证明 即 从而得到 取 , 则 算子范数（续） 证明 * * 的求解过程为: 可推导求解单位下三角形方程组 的递归公式为 : 求解上三角形方程组 的递归公式为: 三角分解解线性方程组的公式 直接三角分解法 发现计算 的规律与计算 的规律相同,因此计算 的求方程组的过程可用三角分解的紧凑格式取代。事实上，这只要把 做为A的第n＋1列进行直接三角分解即可。 Reamrk：上述直接三角分解法所对应的是Gauss顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。 续 设对 的分解已完成k-1步，即L 的前k-1列,U之的前k-1行已求出： 第k步计算：先选主元，再计算列，最后计算行 3.3 列主元直接三角分解法 参选主元量 若 ,则需将第k行与第ik行完全交换，这样满足前面情形，按第一种情形实施计算。 1. 正定矩阵的Cholesky分解 定义：设A为n阶 对称正定矩阵，L是非奇异下三角矩阵，称 为矩阵A的Cholesky分解。 定理: n阶 对称正定矩阵A一定存在分解: 其中L为单位下三角阵，D是对角元全为正的对角阵且这种分解式唯一; 其中L为下三角阵，当限定L的对角元为正时的分解式唯一（Cholesky分解）. 3.4 平方根法（Cholesky分解） 证明： 因为 因为 A对称正定，故其顺序主式 ， 有唯一的Doolittle分解 从而A 平方根法（Cholesky分解） 定理证明 （D可逆） 平方根法（Cholesky分解） 即 ,由Doolittle分解的唯一性，及 的分解过程可知该分解式的唯一性。 续1 由Doolittle分解的唯一性有 改写 则 这时 为一般的下三角矩阵，故 ，若 的对角元全为正时，由Doolittle分解的唯一性及上述分解的推理过程，可以得到Cholesky分解的唯一性。 平方根法（Cholesky分解） 续2 第一步 ： 平方根法（Cholesky分解）： 分解公式 设L前k-1列元素已求出，则第k步 平方根法（Cholesky分解） 在分解过程中有n次开方运算，故Cholesky分解法也称为平方根法。 用Gauss顺序消去法求解对称正定的方程组Ax＝b， 由 用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。 这表明用Gauss顺序消去法求解对称正定方程组也不用选主元。 几点说明 从运算量的角度看，平方根法是有利的，用平方根法解Ax＝b所需乘除法的运算次数为： 令有n次开方运算。 n次开方运算一般使用迭代法，所需乘除法的运算次数大约为n的常数倍。故平方根法总的乘除法运算次数大约为 为避免开方运算，也可对A做 分解。 续 矩阵对角占优的概念 类似地，也可定义按列对角占优和按列严格对角占优的概念。通常的对角占优是指按行或者按列。 则称矩阵A按行严格对角占优。 则称矩阵A按行对角占优。 3.5 三对角线性方程组求解 满足严格对角占优条件 严格对角占优的矩阵行列式不等于零 ，故该系数矩阵的各级顺序主子式不等于零。 追赶法解三对角方程组 若A为上述三对角阵时，则A有三角分解： 追赶法解三对角方程组 分解公式 追赶法解三对角方程组 由 得 由 得 方程求解公式 追赶法解三对角方程组 Remark：只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为5n－4。上述方法称为解三对角方程组的追赶法，又称为Thomas方法。 说明 其中Ai，Bi，Ci均为q阶矩阵， ， 是q维向量。对于这种方程组，可以类似地建立追赶法。 追赶法解块状三对角方程组 追赶法解块状三对角方程组 其中I为q阶单位矩阵，Li和