解线性代数方程————————————————————————————————作者：————————————————————————————————日期：求解线性方程组的直接解法5.3特殊矩阵的三角分解①实对称矩阵的LDL T分解设A是实对称阵,且A的所有顺序主子式均不为零，则LDR分解中R=L T, 故可用以作LDL T分解.这就是说,当A的对角元素非零时，我们可以作LU分解,也就得到LDL T分解,L相同,是单位上三角阵,U的对角元素构成D.不过没有利用对称性,存储量运算量都未能节省—预计是一半。

试用n=3的计算表格说明如何实现节省。

d1=u11 =a11u12=a12l21=u12/d1u13=a13l31=u13/d1d2=u22=a22-l21u12u23=a23-l21u13l32=u23/d2u33=a33-l31u13-l32u23这样,可用上半部元素逐列计算D,L T。

也可用下半部元素逐行计算L,D。

引进輔助量t1, t2代替u1j,u2j,并利用对称性得到：d1=a11t1=a21l21= t1/d1d2= a22-t1l21t1=a31 l31=t1/d1t2=a32-t1l21l32=t2/d2d3=a33-t1l31-t2l32据此不难写出LDL T分解A=LDL T的计算公式和程序(逐行计算L,D).d1=a11for i=2:nfor j=1:i-1t j=a ij-l j1t1-l j2t2-…-l j,j-1t j-1l ij=t j/d jendd i=a ii-l i1t1-l i2t2-…- l i,i-1t i-1end存储约n(n+1)/2单元,乘加运算各约n3/6.利用LDL T分解解Ax=b分四步:1．分解A=LDL T2．解Lg=b 求g3．解Dy=g 求y4．解L T x=y 求x②实对称正定矩阵的LL T分解A实对称正定时顺序主子式皆正,可作LDL T,D的对角元素皆正,有正的平方根。

因此有LL T 分解A =LL T ,L 下三角阵,对角元素皆正,是LDL T 中的LD 1/2.乃可用上半部元素逐列计算L T .l 11=a 111/2 l 21= a 12/l 11 l 31=a 13/l 11l 22=(a 22-l 212)1/2 l 32=(a 23-l 21l 31)/l 22l 33=a 33-l 312-l 322也可用下半部元素逐行计算L .计算表格和算法安排如下:l 11=a 111/2l 21= a 21/l 11 l 22=(a 22-l 212)1/2l 31= a 31/l 11 l 32=(a 32-l 31l 21)/l 22l 33=(a 33-l 312-l 322)1/2l 11=a 111/2 for i =2:nfor j =1:i -1l ij =(a ij -l i 1l j 1-l i 2l j 2-…-l i ,j-1l j ,j-1)/d jjend2/121,2221)(-----=i i i i ii ii l l l a l Λ end存储量,运算量同LDL T 分解,但要n 次求平方根.利用LL T 分解解Ax =b 分三步:1．分解A =LL T2．解 Lg =b 求g 3．解 L T x =g 求x③ 三对角方程组的追赶法消去法或LU 分解用于三对角方程组有特殊形式,即称追赶法.设Ax =f : b 1x 1+ c 1x 2=f 1a i x i-1+b i x i +c i x i+1=f i i=2,3,n -1 a n x n-1+b n x n =f nA 是三对角阵,则L ,U 同样结构.L 的对角元素为α2,α3,…，αn ,U 的对角元素为β1,β2,…,βn ,上对角元素同A .1．分解A =LU : β1= b 1,αi =a i /βi-1,βi = b i -αi c i -1, i=2,3,…,n 2．解 Lg =f 求g : g 1=f 1,g i =f i -αi f i -1, i=2,3,…,n 3．解 U x =g 求x : x n =g n /βn ,x i =(g i -c i x i +1)/βi , i=n -1,n -2,…,1编程时，A 可用三个一维数组，f 用一个一维数组.L ,U 存入A 。

g ，x存入f 。

还有一种计算格式,消去时用主元素除主行元素,即分解A 为下三角矩阵和单位上三角矩阵之积,相当于对A T 作LU 分解.⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--n nnn n nnn g g g a a f f f b a c c b a c b M M O O O O O M M O O O O O 2112221121122211)()()(βγγβγβ括号中是单位上三角矩阵的上对角元素.计算步骤:1．分解A =LU : β1=b 1,γ1=c 1/β1,βi =b i -a i γi -1,γi =c i /βi , i=2,3,…,n 2．解 Lg =f 求g : g 1=f 1/β1,g i =(f i -a i g i -1)/βi , i=2,3,…,n 3．解 U x =g 求x : x n =g n ,x i =g i -γi x i +1, i=n -1,n -2,…,1 三对角矩阵是带形矩阵的特例.所谓带形矩阵是那些主对角线附近几条对角线以外元素皆零的矩阵,即a ij ≠0,仅当-m 1<j-i <m 2.带形矩阵的LU 分解也保持结构.5.4 向量和矩阵的范数引入实数的绝对值和复数的模(也称绝对值)来表示实数和复数的”大小”,从而带来许多用处.例如,数列收敛的概念就是通过绝对值来表示的.范数这个概念就是这些表示”大小”的数值普遍化.它在研究数值计算方法的收敛性和稳定性中有着重要的应用. ① 向量的范数定义1. 如果向量)(n n C R x 或∈的某个实值函数x x N =)( ，满足条件：1. 正定性:║x ║≥0,║x ║=0 iff x =02. 齐次性:║c x ║=│c │║x ║, C c ∈∀3.三角不等式:①║x +y ║≤║x ║+║y ║ ② | y x - |y x -≤则称C n 中定义了向量范数║x ║为向量x 的范数。

可见向量范数是向量的一种具有特殊性质的实值函数。

常用向量范数有：（令x =( x 1,x 2,…,x n )T ）1-范数： ║x ║1=│x 1│+│x 2│+…+│x n │ 2-范数： ║x ║2=(│x 1│2+│x 2│2+…+│x n │2)1/2 ∞-范数： ║x ║∞=max(│x 1│,│x 2│,…,│x n │)易得║x ║∞≤║x ║2≤║x ║1≤n 1/2║x ║2≤n ║x ║∞P -范数： ).,1[,)(11∞∈=∑=P x xni P Pi P其中定理1.C n 中任意两种向量范数║x ║α,║x ║β是等价的,即m ,M >0使m ║x ║α≤║x ║β≤M ║x ║可根据范数的连续性来证明它.由定理1可得。

定理2.0lim lim )()(=-⇔=*∞→*∞→x x x x k k k k ，其中•为向量的任一种范数。

此时称{x (k )}收敛于x ,记作x (k ) →x (k →∞),或x x k k =∞→)(lim 。

② 矩阵的范数定义2.设R X C X n n ∈→∈•⨯:,满足1. 正定性:║X ║≥0,║X ║=0 iff X =02. 齐次性:║c X ║=│c │║X ║, C c ∈∀3. 三角不等式:║X +Y ║≤║X ║+║Y ║4. 相容性: ║XY ║≤║X ║║Y ║ 则称C n ⨯n 中定义了矩阵范数,║X ║为矩阵X 的范数.注意:矩阵X 可视为n 2维向量,故有前三条性质.因此定理1,2中向量的等价性和向量序列收敛的概念与性质等也适合于矩阵.第四条,是考虑到矩阵乘法关系而设.║Ax ║≤║A ║║x ║所谓由向量范数导出的矩阵范数与该向量范数就是相容的.定理3. 设A 是n ×n 矩阵,║•║是n 维向量范数则║A ║=max{║Ax ║/║x ║=1}= max{║Ax ║/║x ║，x ≠0}是一种矩阵范数,称为由该向量范数导出的矩阵范数或算子范数,它们具有相容性或者说是相容的。

单位矩阵的算子范数为1。

可以证明任一种矩阵范数总有与之相容的向量范数.例如定义:║x ║=║X ║,X =(xx …x )常用的三种向量范数导出的矩阵范数是1-范数:║A ║1= max{║Ax ║1/║x ║1=1}=∑=≤≤ni jj nj a 11max2-范数:║A ║2=max{║Ax ║2/║x ║2=1}=1λ,λ1是A T A 的最大特征值.∞-范数:║A ║∞=max{║Ax ║∞/║x ║∞=1}=∑=≤≤nj ij ni a 11max此外还有Frobenius 范数:∑==nj i ij Fa A1,212)(.它与向量2-范数相容.③ 矩阵譜半径定义3.设A 是n ×n 矩阵,λi 是其特征值,i =1,2,…,n .称i ni A λρ≤≤=1max )(为A 的譜半径.譜半径是矩阵的函数,但非矩阵范数.对任一矩阵范数有如下关系:ρ(A )≤║A ║因为任一特征对λ,x ,Ax =λx ,令X =(xx …x ),可得AX =λX .两边取范数,由矩阵范数的相容性和齐次性就导出结果.定理3. 矩阵序列I ,A ,A 2,…A k ,…收敛于零的充分必要条件是ρ(A )<1.5.5 误差分析① 病态现象例3给出一个方程组顺序消去法解的误差很大,主元素法解的误差很小.该方程组数据有微小变化时解的变化也小.但有些方程组不是这样的,数据有微小变化时解的变化大.换句话说后一种方程组对数据变化敏感,前一种方程组对数据变化不敏感,这两种方程组(和相应的矩阵)分别称为病态的和良态的. 例5. 病态方程组⎥⎦⎤⎢⎣⎡→⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡→⎥⎦⎤⎢⎣⎡110001.220001.1111,02220001.1111例6. 病态矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--------=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=-28004200168014042006480270024016802700120012014024012016,7/16/15/14/16/15/14/13/15/14/13/12/14/13/12/11144H H H 4取五位有效数字,其逆误差在前面第二、三位上:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--2871.14310.0-1726.1144.20-4310.0-6650.12771.3- 246.491726.12771.3-1229.972.122144.20- 246.4972.122248.16② 扰动分析与矩阵条件数现在考虑系数、右端项有扰动时解的变化,也就是数据有误差时解的误差. 设Ax =b ,右端项有扰动A (x +δx )=b +δb ,A 可逆解皆存在惟一,其差δx =A -1δb, ║δx ║≤║A -1║║δb ║, ║δx ║/║x ║≤(║A -1║║A ║)║δb ║/║b ║再考虑系数有扰动(A +δA )(x +δx )=b.首先,当A 可逆,║A -1║║δA ║<1时A +δA 可逆.因为此时ρ(A -1δA )≤║A -1δA ║≤║A -1║║δA ║<1,I +A -1δA 可逆,从而A +δA=A (I +A -1δA )可逆.原方程与扰动方程解皆存在惟一,二方程相减有A δx = -δA (x +δx ), δx = -A -1δA (x +δx )两边取范数可得║δx ║≤║A -1║║δA ║(║x ║+║δx ║)从而有AAA AA A xxδδδ111---≤类似的方法不难导出一般情况下,即系数、右端项都有扰动时的估计:⎪⎪⎭⎫⎝⎛+-≤--A A x xA A AA A A xxδδδδδ111 注意到估计式表明:║A -1║║A ║不大,对解的影响也不大; ║A -1║║A ║越大,扰动对解的影响也越大.这就是说该向量是方程组敏感性以及病态或良态的度量，称为矩阵的条件数,记为Cond(A )ν=║A -1║ν║A ║ν.它有如下性质:1. Cond(A )≥12. Cond(c A )=Cond(A ),c ≠03. Cond(A )2=║A -1║2║A ║2=21λλ称为谱条件数。