中国科学院：《数值计算方法》第四章 高斯消去法的变形

§4高斯消去法的变形 二、平方根法 工程实际计算中,线性方程组的系数矩阵常常具有对 称正定性,即其各阶顺序主子式及全部特征值均大于零。 矩阵的这一特性使它的三角分解也有更简单的形式,从而 导出一些特殊的解法,如平方根法与改进的平方根法 定理:设是对称正定矩阵,则存在唯一的非 奇异下三角阵L,使得 A= LL 且L的对角元素皆为正 (证明略)

§4.高斯消去法的变形 二、平方根法 工程实际计算中，线性方程组的系数矩阵常常具有对 称正定性，即其各阶顺序主子式及全部特征值均大于零。 矩阵的这一特性使它的三角分解也有更简单的形式，从而 导出一些特殊的解法，如平方根法与改进的平方根法。 , ( ) T A L A LL L = 定理：设 是对称正定矩阵，则存在唯一的非 奇异下三角阵 使得 且 的对角元素皆为正。 证明略

平方根 Cholesky分解法)法 由A=LC|l21l2 :‖0 2 0|: 其中l>0(i=1,2,…,n)由矩阵乘法及lk=0(当<k时) k=1 ∑lk)/1(=j+1…,n) 这里规定∑=0。计算顺序是按列进行,即 k=1 h1->hn1(=2,3,…,n)→>l2->l2(t=3,…,n)>…

平方根(Cholesky分解法）法 11 11 12 1 21 22 22 2 1 2 1 1 2 2 1 0 0 0 0 0 0 0 ( 1, 2, , ). 0 ( ), ( ) ( 1, 2, , ), ( ) / ( 1, n T n n n nn nn ii jk j jj jj jk k ij ij ik jk jj l l l l l l l l A LL l l l l l i n l j k l a l j n l a l l l i j − =         = =      = =  = − = = − = +  由 其中 由矩阵乘法及 当 时 得 1 1 0 1 11 1 22 2 , ); 0 ( 2,3, , ) ( 3, , ) j k k i i n l l i n l l i n − = =         = → = → → = →  这里规定 。计算顺序是按列进行，即 

当矩阵A完成平方根分解后,求解Ax=b,即求解两个 三角形方程组 (1)Ly=b,求y;(2)Dx=y,求x y=(b-∑从y)/l(= k=1 (y-∑ 1,…,1) k=i+1 由于的对称性,平方根法的乘除运算量为n3/6数量 级,约是Gaws消去法的一半。上机计算时,所需存储单 元也少,只要存储的下三角部分和右端项b,计算中L存 放在的存储单元,y,x存储在b存储单元。 但这种方法在求L时需作n次开方运算,这样又增加了 计算量 为了避免开方,可使用改进的平方根方法

1 1 1 , ; 2 . ( ) / ( 1,2, , ). ( ) / ( , 1, ,1). T i i i ik k ii k n i i ki k ii k i A Ax b Ly b y L x y x y b l y l i n x y l x l i n n − = = + = = = = − = = − = −   当矩阵 完成平方根分解后，求解 ，即求解两个 三角形方程组 (1) 求 （ ） ，求 3 / 6 , A n Gauss A b L A y x b L n 由于 的对称性，平方根法的乘除运算量为 数量 级，约是 消去法的一半。上机计算时，所需存储单 元也少，只要存储 的下三角部分和右端项 ，计算中 存 放在 的存储单元， 存储在 的存储单元。 但这种方法在求 时需作 次开方运算，这样又增加了 计算量。 为了避免开方，可使用改进的平方根方法

追赶法 在数值计算中,如三次样条插值或用差分方法解常微分方 程边值问题,常常会遇到求解以下形式的方程组 a, b2C2 简记Ax=d b 此系数矩阵的非零元素集中分布在主对角线及其相邻两次对角线 上,称为三对角矩阵。方程组称为三对角方程组

三、追赶法 1 1 1 1 2 2 2 2 2 1 1 1 1 1 . i i i i i n n n n n n n n n b c x d a b c x d a b c x d Ax d a b c x d a b x d − − − − −                         = =                           在数值计算中，如三次样条插值或用差分方法解常微分方 程边值问题，常常会遇到求解以下形式的方程组 简记 此系数矩阵的非零元素集中分布在主对角线及其相邻两次对角线 上，称为三对角矩阵。方程组称为三对角方程组

定理:设三对角方程组系数矩阵满足下列条件: >0 b|≥a|+cac;≠0(i=2,3…,n-1) >0 则它可分解为 A= lU 其中c(i=1,2,…,n-1)为已给出的,且分解是唯一的 (证明略)

1 1 1 1 2 2 2 3 1 0 0( 2,3, , 1) 0 1 1 1 1 ( 1,2, , 1) . ( ) i i i i i n n n n n i b c b a c a c i n b a u c l u c A LU l c l u c i n −       +  = −             = =     = − 定理：设三对角方程组系数矩阵满足下列条件： 则它可分解为 其中 为已给出的，且分解是唯一的 证明略