解线性代数方程组.doc

求解线性方程组的直接解法 5.3??????特殊矩阵的三角分解 ①? 实对称矩阵的LDLT分解 设A是实对称阵,且A的所有顺序主子式均不为零，则LDR分解中R=LT, 故可用以作LDLT分解.这就是说,当A的对角元素非零时，我们可以作LU分解,也就得到LDLT分解,L相同,是单位上三角阵,U的对角元素构成D.不过没有利用对称性,存储量运算量都未能节省—预计是一半。试用n=3的计算表格说明如何实现节省。 d1=u11 =a11 u12=a12 l21=u12/d1 u13=a13 l31=u13/d1 ? d2=u22=a22-l21u12 u23=a23-l21u13 l32=u23/d2 ? ? u33=a33-l31u13-l32u23 这样,可用上半部元素逐列计算D,LT。也可用下半部元素逐行计算L,D。引进輔助量t1, t2代替u1j,u2j,并利用对称性得到： d1=a11 ? ? t1=a21 l21= t1/d1 d2= a22-t1l21 ? t1=a31 l31=t1/d1 t2=a32-t1l21 l32=t2/d2 d3=a33-t1l31-t2l32 ? 据此不难写出LDLT分解A=LDLT的计算公式和程序(逐行计算L,D). d1=a11 for i=2:n for j=1:i-1 tj=aij-lj1t1-lj2t2-…-lj,j-1tj-1 lij=tj/dj end di=aii-li1t1-li2t2-…- li,i-1ti-1 end 存储约n(n+1)/2单元,乘加运算各约n3/6. 利用LDLT分解解Ax=b分四步: 1．分解A=LDLT 2．解 Lg=b 求g 3．解 Dy=g 求y 4．解 LTx=y 求x ? ②???? 实对称正定矩阵的LLT分解 A实对称正定时顺序主子式皆正,可作LDLT,D的对角元素皆正,有正的平方根。因此有LLT分解A=LLT,L下三角阵,对角元素皆正,是LDLT中的LD1/2.乃可用上半部元素逐列计算LT. l11=a111/2 l21= a12/l11 l31=a13/l11 ? l22=(a22-l212)1/2 l32=(a23-l21l31)/l22 ? ? l33=a33-l312-l322 也可用下半部元素逐行计算L.计算表格和算法安排如下: l11=a111/2 ? ? l21= a21/l11 l22=(a22-l212)1/2 ? l31= a31/l11 l32=(a32-l31l21)/l22 l33=(a33-l312-l322)1/2 ? l11=a111/2 for i=2:n for j=1:i-1 lij=(aij-li1lj1-li2lj2-…-li,j-1lj,j-1)/djj end end 存储量,运算量同LDLT分解,但要n次求平方根. 利用LLT分解解Ax=b分三步: 1．分解A=LLT 2．解 Lg=b 求g 3．解 LTx=g 求x ? ③???? 三对角方程组的追赶法 消去法或LU分解用于三对角方程组有特殊形式,即称追赶法.设Ax=f: b1x1+ c1x2=f1 aixi-1+bixi+ cixi+1=fi i=2,3,n-1 anxn-1+bnxn=fn A是三对角阵,则L,U同样结构.L的对角元素为α2,α3,…，αn,U的对角元素为β1,β2,…,βn,上对角元素同A. 1．分解A=LU: β1= b1,αi=ai/βi-1,βi= bi-αi ci-1, i=2,3,…,n 2．解 Lg=f求g: g1=f1,gi=fi-αifi-1, i=2,3,…,n 3．解 Ux=g求x: xn=gn/βn,x i=(gi-cixi+1)/βi, i=n-1,n-2,…,1 编程时，A可用三个一维数组，f用一个一维数组.L,U存入A。g，x 存入f。 还有一种计算格式,消去时用主元素除主行元素,即分解A为下三角矩阵和单位上三角矩阵之积,相当于对AT作LU分解. 括号中是单位上三角矩阵的上对角元素.计算步骤: 1．分解A=LU: β1=b1,γ1=c1/β1,βi=bi-aiγi-1,γi=ci/βi, i=2,3,…,n 2．解 Lg=f 求g: g1=f1/β1,gi=(fi-aigi-1)/βi, i=2,3,…,n 3．解 Ux=g 求x: xn=gn,x i=gi-γixi+1, i=n-1,n-2,…,1 三对角矩阵是带形矩阵的特例.所谓带形矩阵是那些主对角线附近几条对角线以外元素皆零的矩阵,即aij≠0,仅当-m1j-im2.带形矩阵的LU分解也保持结构. ?5.4 向量和矩阵的范数 引入实数的绝对值和复数的模(也称