§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(当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 − + = − = = = − 定理：设三对角方程组系数矩阵满足下列条件： 则它可分解为 其中 为已给出的，且分解是唯一的 证明略
追赶法的计算公式 A=LU分解公式:{=a/ln1(=2,3,…,m) u;=b-C_I 解Ly=d得: Dk=dk -lkyk(k=2, 3, ..,n) 再解Ux=y得: y x=(vk-Ckx+)/lk(k=n-1,n-2…,1) 追赶法的基本思想与 Gause消去法及三角分解法相同,只 是由于系数中出现了大量的零可使计算公式简化减少了计 算量。可证,当系数矩阵为严格对角占优时,此方法具有良好 的数值稳定性
追赶法的计算公式 1 1 1 1 1 1 1 1 / ( 2,3, , ) ( 2,3, , ) / : ( ) / ( 1, 2, ,1) , i i i i i i i k k k k n n n k k k k k u b A LU l a u i m u b c l y d Ly d y d l y k n x y u Ux y x y c x u k n n Gause − − − + = = = = = − = = = − = = = = − = − − 分解公式： 解 得： 再解 得 追赶法的基本思想与 消去法及三角分解法相同只 是由于系数中出现了大 , , , , 量的零 可使计算公式简化 减少了计 算量。可证 当系数矩阵为严格对角占优时 此方法具有良好 的数值稳定性
§5向量和矩阵的范数 向量范数 向量范数定义: 设对任意向量x∈R",按一定的规则有一实数 与之对应,记为x若满足 1,‖x≥0,且‖x=0当且仅当x=0;(正定) 2,|ax=al·|‖,a为任意实数(齐次) 3,‖x+川sx+y,对任意x,y∈R (三角不等式) 则称‖x‖为向量的范数
§5.向量和矩阵的范数 一、向量范数 : , , , 1, 0 , 0 0; ( ) 2, , ( ) 3, , n n x R x x x x x x x x y x y , x y R = = = + + 向量范数定义 设对任意向量 按一定的规则有一实数 与之对应 记为 若 满足 且 当且仅当 正定 为任意实数 齐次 对任意 ( ) x x 三角不等式 则称 为 向量 的范数
向量范数例 =√x2+…+x2=(x2 A.=max1x…xy=max|xl 1≤in X xC X 1/p
向量范数例 x x x ( x ) n n i ∑ 1 2 i 2 1 2 2 1 2 = ++ = = 1 i 1 1 n n i x x x x = = + + = x max{ x , , x } max{ x } i n n i 1≤≤ ∞ = 1 = 1/ 1 , p n p p i i x x = =
可验证上面范数均满足范数定义的条件。 以∞o-范数为例 满足条件1,2显然。 由于x,y∈R为向量,而其分量x2y(i=1,…,n) 为实数,故有 lx+Ill =max{x;+y}≤max x+y1} 1<i<n ≤max{x}+ma×y}=1+y
1 1 1 1 - : 1,2 , , ( 1, , ) max max max max n i i i i i i i n i n i i i n i n x y R x y i n x y x y x y x y x y = + = + + + = + 可验证上面范数均满足范数定义的条件。 以 范数为例 满足条件 显然。 由于 为向量，而其分量 为实数，故有
例:计算向量x=(1,-2,3)的各种范数。 解:|x1=6,‖x=3,|x2=√14 如果R"中两个范数‖‖和‖·,存在实数 m,M>0,使得对任意n维向量x,都有 m|≤|x≤M|x, 则称这两个范数是等价的 对两个等价范数而言,同一向量序列有 相同的极限
1 2 ' ' (1, 2,3) 6, 3, 14. , 0 , T n x x x x R m M n x m x x M x = − = = = 例：计算向量 的各种范数。 解： 如果 中两个范数 和 ，存在实数 ，使得对任意 维向量 都有 ， 则称这两个范数是等价的。 对两个等价范数而言，同一向量序列有 相同的极限