数值分析——线性方程组直接解法Hilbert矩阵

实验五 解线性方程组的直接方法实验5.1 （主元的选取与算法的稳定性）问题提出：Gauss 消去法是我们在线性代数中已经熟悉的。

但由于计算机的数值运算是在一个有限的浮点数集合上进行的，如何才能确保Gauss 消去法作为数值算法的稳定性呢？Gauss 消去法从理论算法到数值算法，其关键是主元的选择。

主元的选择从数学理论上看起来平凡，它却是数值分析中十分典型的问题。

实验内容：考虑线性方程组n n n R b R A b Ax ∈∈=⨯,,编制一个能自动选取主元，又能手动选取主元的求解线性方程组的Gauss消去过程。

实验要求：（1）取矩阵⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=1415157,6816816816M O O O b A ，则方程有解T x )1,,1,1(*Λ=。

取n=10计算矩阵的条件数。

让程序自动选取主元，结果如何？（2）现选择程序中手动选取主元的功能。

每步消去过程总选取按模最小或按模尽可能小的元素作为主元，观察并记录计算结果。

若每步消去过程总选取按模最大的元素作为主元，结果又如何？分析实验的结果。

（3）取矩阵阶数n=20或者更大，重复上述实验过程，观察记录并分析不同的问题及消去过程中选择不同的主元时计算结果的差异，说明主元素的选取在消去过程中的作用。

（4）选取其他你感兴趣的问题或者随机生成矩阵，计算其条件数。

重复上述实验，观察记录并分析实验结果。

思考题一：（Vadermonde 矩阵）设⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=∑∑∑∑====n i i n n i i n i i n i i n n n n n n n x x x x b x x x x x x x x x x x x A 002010022222121102001111M ΛM ΛM M M ΛΛΛ，， 其中，n k k x k ,,1,0,1.01Λ=+=，（1）对n=2,5,8，计算A 的条件数；随n 增大，矩阵性态如何变化？（2）对n=5，解方程组Ax=b ；设A 的最后一个元素有扰动10-4，再求解Ax=b（3）计算（2）扰动相对误差与解的相对偏差，分析它们与条件数的关系。

Hilbert 代数方程组的数值解法1 Hilbert 矩阵的条件数和矩阵的阶数的关系编制Matlab 程序：clear,clc format long %format short for n=1:14; A=hilb(n); %A=rand(n);condA(n)=cond(A,inf); endplot(log10(condA)) 得出图形图1：Hilbert 矩阵和阶次的关系由图可见a.Hilbert 矩阵的2-条件数的对数与阶次近似正比;b.阶次超过12后，计算困难，舍入误差会导致计算不准 结论：Hilbert 矩阵的2-条件数随阶次指数增长，关系大概是： Log 10(Cond(A))= 1.33791720780254(n-1)0246810121424681012141618nl o g 10(c o n d A )条件数的对数-阶次2.各种求解方法的对比2.1 直接法：Gauss 消去方法（程序见附录，下同）在双精度型变量下，即eps=2.220446049250313e-016，对于直接法Gauss 消去方法，求解Hilbert 矩阵方程组，在阶次n=13时，解得: X=[1 0.99997 1.0013 0.97881 1.1906 -0.035441 4.6171 -7.3967 14.089 -12.542 9.9162 -2.3817 1.5624]出现明显错误，可见Gauss 消去方法对病态问题比较敏感。

求解阶次不高。

2.2 Jacobi 迭代法很遗憾，jakobi 迭代法的迭代矩阵的谱半径随阶次线性上升（程序见附录2），普遍大于1，计算结果发送，无法迭代出满意的结果。

需放弃图2：Jacobi 迭代矩阵的谱半径2.3 Gauss-Seidel 迭代与SOR 迭代求解先分析SOR 迭代矩阵的谱半径和松弛因子w 的关系0510152025510152025阶次谱半径Jacobi 迭代收敛性分析图3：SOR 迭代矩阵的谱半径和松弛因子w 的关系可以发现SOR 迭代和G-S 迭代的谱半径都普遍接近于1，因此松弛因子的选择对计算结果的影响不大。

1 / 7 数值分析课程实验报告题目：病态线性方程组的求解理论分析表明，数值求解病态线性方程组很困难。

考虑求解如下的线性方程组的求解Hx = b ，期中，期中H 是Hilbert 矩阵，()ij n n H h ´=，11ij h i j =+-，i ，j = 1,2，…，n 1.估计矩阵的2条件数和阶数的关系2.对不同的n ，取(1,1,,1,1))nx =Î，分别用Gauss 消去，Jacobi 迭代，Gauss-seidel 迭代，SOR 迭代和共轭梯度法求解，比较结果。

3.结合计算结果，试讨论病态线性方程组的求解。

解答过程1.估计矩阵的2-条件数和阶数的关系矩阵的2-条件数定义为：1222()Cond A A A-=´，将Hilbert 矩阵带入有：1222()Cond H H H -=´调用自编的Hilbert_Cond 函数对其进行计算，取阶数n = 50，可得从，可得从1阶到50阶的2-条件数，以五位有效数字输出，其中前10项见表1。

表1.前十阶Hilbert 矩阵的2-条件数阶数1 2 3 4 5 2-条件数1 19.281 524.06 1.5514e+004 4.7661e+005 阶数6 7 8 9 10 2-条件数1.4951e+007 4.7537e+008 1.5258e+010 4.9315e+011 1.6025e+013 从表1可以看出，随着阶数每递增1，Hilbert 矩阵的2-条件数都至少增加一个数量级，但难以观察出明显的相依规律。

故考虑将这些数据点绘制在以n 为横轴、Cond （H ）2为纵轴的对数坐标系中（编程用Hilbert_Cond 函数同时完成了这个功能），生成结果如图1。

图1.不同阶数下Hilbert 矩阵的2-条件数分布条件数分布由图可见，当维数较小时，在y-对数坐标系中Cond （H ）2与n 有良好的线性关系；但n 超过10后，线性趋势开始波动，n 超过14后更是几乎一直趋于平稳。

（Hilbert 矩阵）病态线性方程组的求解理论分析表明，数值求解病态线性方程组很困难。

考虑求解如下的线性方程组的求解Hx = b ，期中H 是Hilbert 矩阵，()ij n n Hh ，11ij h i j ，i ，j = 1,2，…，n 1.估计矩阵的2条件数和阶数的关系2.对不同的n ，取(1,1,,1)nx K ?，分别用Gauss 消去，Jacobi 迭代，Gauss-seidel 迭代，SOR 迭代和共轭梯度法求解，比较结果。

3.结合计算结果，试讨论病态线性方程组的求解。

第1小题：condition.m %第1小题程序t1=20;%阶数n=20x1=1:t1;y1=1:t1;for i=1:t1H=hilb(i);y1(i)=log(cond(H));endplot(x1,y1);xlabel('阶数n');ylabel('2-条件数的对数（log(cond(H)）');title('2-条件数的对数（log(cond(H)）与阶数n 的关系图');t2=200;%阶数n=200x2=1:t2;y2=1:t2;for i=1:t2H=hilb(i);y2(i)=log(cond(H));endplot(x2,y2);xlabel('阶数n');ylabel('2-条件数的对数（log(cond(H)）');title('2-条件数的对数（log(cond(H)）与阶数n 的关系图');画出Hilbert 矩阵2-条件数的对数和阶数的关系n=200时n=20时从图中可以看出，1）在n小于等于13之前，图像近似直线log（cond（H））~1.519n-1.8332）在n大于13之后，图像趋于平缓，并在一定范围内上下波动，同时随着n的增加稍有上升的趋势第2小题：solve.m%m第2小题主程序N=4000;xGauss=zeros(N,1);xJacobi=zeros(N,1);xnJ=zeros(N,1);xGS=zeros(N,1);xnGS=zeros(N,1);xSOR=zeros(N,1);xnSOR=zeros(N,1);xCG=zeros(N,1);xnCG=zeros(N,1);for n=1:N;x=ones(n,1);t=1.1;%初始值偏差x0=t*x;%迭代初始值e=1.0e-8;%给定的误差A=hilb(n);b=A*x;max=100000000000;%可能最大的迭代次数w=0.5;%SOR迭代的松弛因子G=Gauss(A,b);[J,nJ]=Jacobi(A,b,x0,e,max);[GS,nGS]=G_S(A,b,x0,e,max);[S_R,nS_R]=SOR(A,b,x0,e,max,w);[C_G,nC_G]=CG(A,b,x0,e,max);normG=norm(G'-x);xGauss(n)=normG;normJ=norm(J-x);nJ;xJacobi(n)=normJ;xnJ(n)=nJ;normGS=norm(GS-x);nGS;xGS(n)=normGS;xnGS(n)=nGS;normS_R=norm(S_R-x);nS_R;xSOR(n)=normS_R;xnSOR(n)=nS_R;normC_G=norm(C_G-x);nC_G;xCG(n)=normC_G;xnCG(n)=nC_G;endGauss.m%Gauss消去法function x=Gauss(A,b)n=length(b);l=zeros(n,n);x=zeros(1,n);%消去过程for i=1:n-1for j=i+1:nl(j,i)=A(j,i)/A(i,i);for k=i:nA(j,k)=A(j,k)-l(j,i)*A(i,k);endb(j)=b(j)-l(j,i)*b(i);endend%回代过程x(n)=b(n)/A(n,n);for i=n-1:-1:1c=A(i,:).*x;x(i)=(b(i)-sum(c(i+1:n)))/A(i,i);endJacobi.m%Jacobi迭代,x0表示迭代初值,e表示允许误差(迭代停止条件),n表示迭代次数,m 可能最大的迭代次数function [x,n]=Jacobi(A,b,x0,e,m)n=length(A);D=diag(diag(A));U=-triu(A,1);L=-tril(A,-1);B=D\(L+U);f=D\b;x=B*x0+f;n=1;while norm(x-x0)>ex0=x;x=B*x0+f;n=n+1;if n>mdisp('Jacobi迭代次数过多，迭代可能不收敛');break;endendG_S.m%Gauss-Seidel迭代,x0表示迭代初值,e表示允许误差(迭代停止条件),n表示迭代次数,m可能最大的迭代次数function [x,n]=G_S(A,b,x0,e,m)n=length(A);D=diag(diag(A));U=-triu(A,1);L=-tril(A,-1);B=(D-L)\U;f=(D-L)\b;x=B*x0+f;n=1;while norm(x-x0)>ex0=x;x=B*x0+f;n=n+1;if n>mdisp('Gauss-Seidel迭代次数过多，迭代可能不收敛');break;endendSOR.m%SOR超松弛迭代,x0表示迭代初值,e表示允许误差(迭代停止条件),n表示迭代次数,m可能最大的迭代次数,w松弛因子function [x,n]=SOR(A,b,x0,e,m,w)n=length(A);D=diag(diag(A));U=-triu(A,1);L=-tril(A,-1);B=(D-w*L)\((1-w)*D+w*U);f=(D-w*L)\b*w;x=B*x0+f;n=1;while norm(x-x0)>ex0=x;x=B*x0+f;n=n+1;if n>mdisp('SOR超松弛迭代次数过多，迭代可能不收敛');break;endendCG.m%CG共轭梯度法,x0表示迭代初值,e表示允许误差(迭代停止条件),n表示迭代次数,m可能最大的迭代次数function [x,n]=CG(A,b,x0,e,m)r=b-A*x0;p=r;alpha=(r'*r)/(p'*(A*p));x=x0+alpha*p;r1=b-A*x;n=1;while norm(r1)>ebelta=(r1'*r1)/(r'*r);p=r1+belta*p;r=r1;x0=x;alpha=(r'*r)/(p'*(A*p));x=x0+alpha*p;r1=b-A*x;n=n+1;if n>mdisp('CG共轭梯度法迭代次数过多，迭代可能不收敛');break;endend。

病态线性代数方程组的求解理论的分析表明，求解病态的线性代数方程组是困难的。

考虑方程组Hx = b 的求解，其中H 为Hilbert 矩阵，n n ij h H ⨯=)(，11-+=j i h ij ，n j i ,...,2,1,=1. 估计Hilbert 矩阵2-条件数与阶数的关系；2. 选择问题的不同维数，分别用Gauss 消去法，Jacobi 迭代，GS 迭代和SOR 迭代求解，比较结果；3. 讨论病态问题求解的算法。

解： 1、取Hilbert 矩阵阶数最高分别为n=20和n=100。

采用Hilbert 矩阵的2-条件数作为实验的比较对象，画出的曲线如下图所示：lg(())n cond H n从图中可以看出，在n ≤13之前，图像接近直线，在n ＞13之后，图像趋于平缓，在一定的范围内上下波动。

为了比较图像的线性部分，作出一条直线与已知曲线进行比较。

比较直线的关系式为：833.1519.1))(lg(-=n H cond n ，结果下图所示。

nl g (c o n d (H n ))lg(cond(Hn))~n 关系图从图2中可以看出，当n 较小时，n H cond n ~))(lg(之间近似满足线性关系。

当n 继续增大到100时，n H cond n ~))(lg(关系图下图所示：从图中可以看出，图像的走势符合在n=20时的猜想，在n 大于一定的值之后，图像趋于平缓，且在一定范围内震荡，同时又有一定上升趋势，但上升速度很慢。

2、选择不同的阶数n ，设方程组的精确解为xz=(1,1,…,1)T进行计算，用四种方法解x_Guass1、x_Jacobi1、x_GS1、x_SOR1对比表如下nl g (c o n d (H n ))lg(cond(Hn))~n关系图nl g (c o n d (H n ))lg(cond(Hn))~n 关系图Gauss消去法求解：选择问题的阶数为3~8时，用Gauss消去法求得的解与精确解一致，当阶数为9~14时，解开始出现偏差，而且n越大，偏差越大。

因‖R０‖＜１，故lim‖R０‖k→∞２k＝０．则２k‖Rk‖≤‖R０‖→０（k→∞），－１即Rk→０（k→∞）．Rk＝I－ACk，故当Rk→０时，Ck→A．四、习题１畅用Gauss消去法解方程组２x１＋x２＋x３＝４，３x１＋x２＋２x３＝６，x１＋２x２＋２x３＝５．２畅（１）设A是对称矩阵且a１１≠０，经过Gauss消去法一步后，A约化为a１１０证明A２是对称矩阵．（２）用Gauss消去法解对称方程组０畅６４２８x１＋０畅３４７５x２－０畅８４６８x３＝０畅４１２７，０畅３４７５x１＋１畅８４２３x２＋０畅４７５９x３＝１畅７３２１，－０畅８４６８x１＋０畅４７５９x２＋１畅２１４７x３＝－０畅８６．３畅（１）用表达式（７畅４）证明其中aij＝aij．（１）a１TA２．aij＝aij－li１a１j－li２a２j－…－li，k－１ak－１，j，i，j≥k，（k）（１）（１）（２）（k－１）（r）（２）使Gauss消去法中arj＝urj（j≥r），利用（１）证明urj＝arj－k∑lrkukj（j＝r，r＋１，…，n），＝１lir＝（air－k∑likukr）／urr（i＝r＋１，…，n）．＝１４畅设方程组x１＋２x２＋３x３＝１，５x１＋４x２＋１０x３＝０，３x１－０．１x２＋x３＝２．r－１r－１３１８（１）试用Gauss全主元消去法求解．（２）试用Gauss列主元消去法求解．５畅设A为n阶非奇异矩阵且有分解式A＝LU，其中L为单位下三角阵，U为上三角阵，求证A的所有顺序主子式均不为零．２，…，n－１）时，则有６畅由Gauss消去法证明：当Δi≠０（i＝１，A＝LU，其中L为单位下三角阵，U为上三角阵．７畅设A为n阶矩阵，若｜aii｜＞j∑｜aij｜（i＝１，２，…，n），则称A＝１j≠in为对角优势矩阵．试证明：设A是对角优势矩阵，又设经过Gauss消去法一步后，A具有形式a１１０α１TA２，则A２是对角优势矩阵．且由此推断：对于对称的对角优势矩阵，用Gauss消去法和部分（列）主元Gauss 消去法可得到同样的结论．８畅设Lk为指标是k的初等下三角矩阵，即１筹Lk＝１mk＋１，k…mnk１筹１．（除第k列对角元下元素外，Lk与单位阵I相同）求证当i，j＞k时，L珟k＝IijLkIij也是一个指标为k的初等下三角矩阵，其中Iij 为初等排列矩阵．９畅试推导矩阵A的Crout分解的计算公式：A＝LU，其中L为下三角矩阵，U 为单位上三角矩阵．１０畅设UX＝b，其中U为三角矩阵．（１）就U为上及下三角矩阵推导一般的求解公式．（２）计算解三角形方程组UX＝b的乘除法次数．３１９（３）设U为非奇异矩阵，试推导求U３２３T－１的计算公式．１１畅用平方根法（Cholesky分解）解方程组２２０３５９１－２１０３０１２５９１７０１－２１－２A＝－４－６４１８２x１x２x３x１x２x３００１－２８－１６．－２０，b＝５＝３．７１０＝１６．３０１１０－１－１１２畅用LDL分解法解方程组３３５－２A＝１００１３畅用追赶法解三对角方程组AX＝b，其中．１４畅求矩阵A的LU分解，并利用分解结果计算A．１５畅下述矩阵能否分解为A＝LU，其中L为单位下三角矩阵，U为上三角矩阵．若能分解，那么分解是否唯一？１A＝２４２４６３７０．６０．１０．５０．３１３１２３１１１６２５１５６１５．４６１，B＝２１，C＝２１６畅设A＝F唱范数．１７畅求证：，计算A的行范数、列范数、２唱范数及（１）‖X‖∞≤‖X‖１≤n‖X‖∞，３２０（２）‖A‖F≤‖A‖２≤‖A‖F．n×n１８畅设P∈R范数．定义且为非奇异矩阵，又设‖X‖为R上一向量‖X‖P＝‖PX‖．n试证明‖X‖P是R上向量的一种范数．１９畅设X∈R，X＝（x１，x２，…，xn），求证：p→∞nTn２０畅证明：当且仅当与Y线性相关且XY≥０时，才有Tlim（i∑｜xi｜＝１np）１＝１max｜xi｜＝‖X‖∞．≤i≤n‖X＋Y‖２＝‖X‖２＋‖Y‖２．２１畅设A∈Rn×n，求证特征值相等λ（AA）＝λ（AA）．TT２２畅证明：如果A＝（α１，α２，…，αn）是按列分块的，则‖A‖２F＝‖α１‖２＋‖α２‖２＋…＋‖αn‖２．２２２－１２３畅证明：如果‖B‖＜１，则‖I－（I－B）‖≤‖B‖．２４畅证明：对任何矩阵算子范数有‖I‖＝１（其中I是单位矩阵），‖A‖‖A－１‖≥１．nj≠i２５畅（１）如果A是对角优势矩阵，即｜aii｜＞j∑｜aij｜（i＝１，２，＝１…，n），证明aii≠０（i＝１，２，…，n）．（２）设A为对角优势矩阵，使A＝DB，其中D＝diag（aii），证明B＝I－C，其中‖C‖∞＜１，因此由定理（７畅１６），A是非奇异阵．（３）证明：如果应用Gauss消去法解对角优势方程组，则所有元素akk≠０．（k）２６畅设‖A‖s、‖A‖t为任意两种R明存在常数c１、c２＞０，使n×n上矩阵算子范数，证n×nc１‖A‖s≤‖A‖t≤c２‖A‖s（对一切A∈R）．３２１２７畅设A＝１００９９９９９８，计算A的条件数cond（A）ν（ν＝２，∞）．２８畅证明：如果A是正交阵，则Cond（A）２＝１．２９畅设A，B∈Rn×n且‖·‖为Rn×n上矩阵的算子范数，证明TT３０畅设A为对称正定矩阵，且其分解为A＝LDL＝WW，其中W＝L，求证：T１Cond（A·B）≤Cond（A）·Cond（B）．（１）cond（A）２＝（cond（W）２）．２（２）cond（A）２＝cond（W）２·cond（W）２．３１畅设对称正定矩阵A＝试计算‖A－１T２－１－１２，λ２，且找出b１‖２＝１／λ，‖A‖２＝λ２及cond２（A）＝（常数）及扰动δb，使‖δb‖２‖δX‖２＝cond２（A）．２２３２畅求下面两个方程组的解，并利用矩阵的条件数估计‖δX‖．２４０－１７９２４０－１７９畅５－３１９２４０２４０x１x２＝x１x２３４＝，即AX＝b，３４，即（A＋δA）（X＋δX）＝b．－３１９畅５３３畅已知Hilbert矩阵３２２１H３＝１１T１＝b时，若H３及b有微小误‖δX‖∞．∞７畅０００３－７T．（１）计算H３的条件数cond∞（H）．１１１３４７（２）解方程H３X＝差（取３位有效数字），估计解X的误差３４畅设A＝２畅０００１－２－１１，b＝，已知方程组AX＝b的精确解为X＝（３，－１）．（１）计算条件数cond∞（A）．计算剩余r＝b－AX珚．（２）若近似解X珚＝（２．９７，－１．０１），（３）利用定理７畅２０计算不等式右端，并与不等式左端比较，此结果说明什么？３５畅填空题（１）X＝（２，３，－４），则‖X‖１＝，‖X‖２＝，‖X‖∞TT＝．１－３２－１０２０１，则‖A‖１＝，ρ（A）＝．０－１则cond２（A）＝．２０a，为使A可分解为A＝LL，其中L为３２３T（２）A＝－１２－１１２（３）A＝（４）设A＝１０a２对角线元素为正的下三角形矩阵，a的取值范围，取a＝１，则L＝．五、习题解答１畅解为消去第２、３两个方程中的x１，取l２１＝，l３１＝．将第２个方程减去－l２１倍的第１个方程，第３个方程减去－l３１倍的第１个方程，得２x１＋x２＋x３－＝４，x２＋x３＝０，x２＋x３＝３．为消去第３个方程中的x２，取l３２＝－３．将第３个方程减去－l３２倍的第２个方程，得三角方程组２x１＋x２＋x３＝４，－１１x２＋x３＝０，３x３＝３．回代，算出方程组的解x３＝３／３＝１，x２＝０－１x３（１）－１＝１，x１＝（４－x２－x３）／２＝１．２畅解（１）记A＝（aij）＝（aij）．经Gauss消元一步后，A２的元素为a（２）ij（１）＝a（１）ij（１）i１（１）－a１j．１１（１）（１）（１）因A是对称的，所以有aij＝aji，ai１＝aj１，于是有３２４a故A２是对称的．（２）ij＝a（１）jij１（１）（２）－a１i＝aji．１１（１）（２）用Gauss消去法求解所给对称方程组，得X＝（４畅５８６０３５，－０畅６３１５２２８，２畅７３５１９９）．倡T ３畅解（１）因aij＝aij（k）（k－１）－li，k－１ak－１，j，（k－１）而故aij＝aij（k）（k－２）（１）aij（k－１）＝aij（k－２）－li，k－２ak－２，j，（k－２）（k－１）－li，k－２ak－２，j－li，k－１ak－１，j＝…（k－２）（１）（２）（k－２）（k－１）＝aij－li１a１j－li２a２j－…－li，k－２ak－２，j－li，k－１ak－１，j，i，j≥k．（２）由（１）有urj＝a又０＝air由此解出（r＋１）（r）rj＝arj－k∑lrkakj（j＝r，r＋１，…，n）．＝１（k）r－１＝air－li１u１r－li２u２r－…－lirurr．lir＝likukrair－k∑＝１rrr－１．４畅解（１）选主元为１０，将第一行与第二行交换，第１列与第３列交换，得１０x３＋４x２＋５x１＝０，３x３＋２x２＋x１＝１，x３－０．１x２＋３x１＝２．消去第２、３方程中的x３，得１０x３＋４x２＋５x１＝０，０畅８x２－０．５x１＝１，－０．５x２＋２．５x１＝１．第２次选的主元为２畅５．将上述第２个方程与第３个方程交３２５换，第２列与第３列交换，得１０x３＋５x１２畅５x１消去第３方程中的未知数x１，得１０x３＋５x１＋４x２＝０，２畅５x１－０．５x２＝２，０．７x２＝１．４．回代求得，x２＝２，x１＝１．２，x３＝－１．４．得（２）列主元为５，将第１行与第２行交换，再消去x１，５x１＋４x２＋１０x３＝０，１畅２x２＋x３＝１，－２．５x２－５x３＝２．列主元为－２．５，将第２行与第３行交换，再消去x２，得５x１＋４x２＋１０x３＝０，－２畅５x２－５x３回代求得x３＝－１．４，x２＝２，x１＝１．２．５畅证设A、L、U的k阶顺序主子矩阵分别为Ak、Lk、Uk（k＝１，２，…，n），显然Ak＝LkUk．由A＝LU分解的定义可知，L１U的各阶顺序主子式均不为零，即故det（Lk）＝１，det（Uk）≠０．det（Ak）＝det（Lk）det（Uk）≠０，k＝１，…，n，＝２，－１畅４x３＝１畅９６．＋４x２＝０，－０．５x２＝２，－０．５x１＋０．８x２＝１．即A的各阶顺序主子式均不为零．（i）６畅证因Δi≠０，（i＝１，２，…，n－１）（Δi是i阶顺序主子式），所以aii≠０（i＝１，２，…，n－１），则Gauss消去法可进行到底，即存３２６在指标为i的初等下三角阵Li，使Ln－１Ln－２…L１A＝U，故A＝L１其中L＝L１－１－１－１（２）－１…Ln－２Ln－１U＝LU，－１－１…Ln－２Ln－１为下单位三角阵，U是上三角阵．aij＝aij－（２）７畅证记A２＝（aij），则有i１a１j．１１nj≠in又A是对角优势矩阵，可知｜aii｜＞j∑｜aij｜，i＝１，２，…，n．故＝１∑｜a｜＝j∑j＝２＝２（２）ijj≠innnj≠ii１aij－a１j１１≤j∑｜aij｜＋j∑＝２＝２j≠i｜ai１｜｜a１j｜１１j≠in｜aij｜n∑｜a１j｜＝j∑｜aij｜－｜ai１｜＋＝１１１j＝２j≠ij≠i≤｜aii｜－＝｜aii｜－≤｜aii｜－≤aii－ni１（｜a１１｜－j∑｜a１j｜）＝２１１j≠ini１（｜a１１｜－j∑｜a１j｜＋｜a１i｜）＝２１１ni１｜a１i｜（｜a１１｜－j∑｜a１j｜＞０．）＝２１１i１（２）a１i＝｜aii｜（i＝２，…，n）．１１即A２也是对角优势矩阵．若A是对角优势矩阵，经Gauss消元一步后．A→A（２）＝a１１０αTA２．由上述证明及第２题结论知，A２仍是对角优势矩阵，即｜a｜＞j∑｜aij｜（i＝２，…，n）．＝２（２）ii（２）由对称性也有３２７｜a｜＞i∑｜a｜＝i∑｜aij｜，（j＝２，…，n）．＝２＝２（２）jj（２）ji（２）i≠ji≠jnn这正好与Gauss顺序消去而第二步消元前所选列主元应为a２２，（k）法的主元相同．以此类推第k次所选主元就是akk，所以用Gauss （２）顺序消去法和列主元消去法得到同样的结果．８畅证因１筹Lk＝１mk＋１，k…mnk０，１，０，…，０）．故ek＝（０，…，T第k列＝I－lkek．筹TT其中I是单位阵，lk＝（０，…，０，－mk＋１，k，…，－mik，…，－mn，k），L珟k＝IijLkIij＝Iij（I－lkek）Iij＝IijIIij－（Iijlk）（ekIij）＝I－lkek′TTT仍是指标为k的初等下三角阵，其中lk＝（０，…，０，－mk＋１，k，…，mjk，…，－mik，…，－mnk）．′T９畅解设A＝LU，即a１１a１２…a１na２１a２２…a２n…………an１an２…ann根据矩阵乘法，有ai１＝li１u１１＝li１，i＝１，…，n，a１j＝l１１u１j，得u１j＝３２８，j＝２，…，n．１１＝l１１l２１l２２……筹ln１ln２…lnn１u１２１…u２３筹……筹筹u１nu２n…un－１，n１．现设L的前k－１列与U的前k－１行已算好，因akk－１ik＝r∑＝１lirurk＝r∑＝１lirurk＋likukk（i＝k，…，n，ukk＝１），k－１所以lik＝aik－r∑＝１lirurk（i＝k，…，n）．同样akk－１kj＝r∑＝１lkrurj＝r∑＝１lkrurj＋lkkukj（j＝k＋１，…，n），k－１kj所以u－r∑＝１lkrurjkj＝akk，j＝k＋１，…，n．综上，Crout分解公式li１＝ai１，i＝１，２，…，n，u１j＝a１j／l１１，j＝２，…，n，lk－１ik＝aik－r∑＝１lirurk，i＝k，…，n，uk－１kj＝（akj－r∑＝１lkrurj）／lkk，j＝k＋１，…，n．１０畅解（１）设U为上三角阵，则有u１１……u１nx１b１u２２…u２nx２筹……＝b２…．unnxnbn由unnxn＝bn，得xn＝bn／unn．一般地，由uiixi＋ui，i＋１xi＋１＋…＋uinxn＝bi，得nxbi－j＝∑ijxji＝ui＋１ii（i＝n－１，n－２，…，１）．当U是下三角矩阵时，有３２９u１１u２１…un１u２２…un２筹…unnx１x２ (x)n＝b１b２…bn．由u１１x１＝b１，得x１＝b１／u１１．一般地，由ui１x１＋ui２x２＋…＋uiixi＝bi，i＝２，…，n，得xi＝（bi－j∑uijxj）／uii，i＝２，…，n．＝１（２）乘法次数，对固定的i有n－i次，i从１到n，所以总乘法次数R（n－i）＝i∑i＝R＝i∑＝１＝１除法次数D，D＝n．＋n故总的乘除法次数＝＋n＝．２nn－１i－１．（３）设Uu１１…筹－１＝V，这里V也是上三角阵，即u１n…unn v１１…筹v１n (v)nnj１＝UV＝１筹１．V按行计算，i＝n－１，…，１，vij＝－k＝i＋１∑uikvkjii，j＝i＋１，…，n．vii＝，i＝１，２，…，n．ii２２３＝２＞０，Δ３＝２３２２０３０１２＞０．１１畅解因系数矩阵顺序主子式Δ１＝３＞０，Δ２＝３２且系数矩阵对称，故为正定方程组．按照算法（７畅９）得３３０l１１＝，l２１＝２／，l３１＝，l２２＝则有３２３２２０３０１２由２／得再由２／y１＝－y１y２y３５＝３，７＝２／－２／－．，l３２＝－，l３３＝．５１１，y２＝－，y３＝．x１x２x３＝５／－１／，１／－得x３＝１１，x２＝，x１＝１．１２畅解此方程组的系数矩阵为对称正定矩阵，因此可用改进的平方根法，用算式（７畅１１）得到d１＝a１１＝３，t２１＝a２１＝３，l２１＝d２＝a２２－t２１l２１＝５－３＝２，t３２＝a３２－t３１l２１＝９－１＝８，l３２＝t２１３＝＝１，１３１５＝，１t３１＝a３１＝５，l３１＝３２８２＝＝４，d３＝a３３－t３１l３１－t３２l３２＝．２３３１１则A＝LDL＝T３１２１１１５／３２．１５／３２１２／３１由LY＝b，即１y１１０１１y２＝１６，５／３２１y３３０得y１＝１０，y２＝６，y３＝４／３．再解DLTX＝Y，得x３＝２，x２＝－１，x１＝１．１３畅解设－２１００１u１d１１－２１０l２１u２d２０１－２１＝l ３１u３００１－２l４１由分解公式（７畅１５）计算得d１＝１，d２＝１，d３＝１，u１＝－２，l２＝－１，u２＝－３，l３＝－２，u３＝－４，l４＝－３，u４＝－５．由公式（７畅１６）解１y１１－１１LY＝b＝痴y２１－２１y＝３０，－１y４－１得y１＝１，y２＝３，y３＝１，y４＝－１．再由公式（７畅１７）解３３２d３．u４－２UX＝Y痴１－x１１－４１－x２x３＝１３１，１－x４１３７６得x４＝，x３＝－，x２＝－，x１＝－．１４畅解由矩阵的三角分解公式（７畅６），计算得１－２４８A＝LU＝２１０１０－３２．３－１１００－７６１００－０．５０畅２－０畅１３６９－１－１L＝－２１０，U＝０畅１－０畅０４２１１．－５１１－０畅０１３１６所以－０畅２１５５０畅０６３１－０畅１３６９－１－１－１A＝UL＝０畅０１０５５０畅０５７８９－０畅０４２１１．０畅０６５３－０畅０１３１６－０畅０１３１６１５畅解设A能分解，则有１A＝LU＝l２１l３１０１l３２００１u１１００u１２u２２０u１３u３３u３３１＝２４２４６３１．７由分解公式（７畅６）知，u１１＝１，u１２＝２，u１３＝３，l２１＝２，l３１＝４，u２２＝０，而a３２＝l３２u２２＋l３１u１２＝０＋４×２＝８与a３２＝６矛盾，故A的LU分解不能进行．但A为非奇异阵，所以存在排列阵P，使PA＝LU．即将A的１行与２行交换，则可分解为LU．设B＝LU，则１２３１２３１１＝１１l２１l３１０１l３２００１u１１００u１２u２２０u１３u２３u３３３３３．由分解公式（７畅６）知，u１１＝u１２＝u１３＝１，l２１＝２，l３１＝３，u２２＝０．而由３＝l３１u１２＋l３２u２２，得３＝３＋l３２u２２．故l３２可任选，即B的三角分解存在且不唯一．因C的各阶顺序主子均不为０，故由定理７畅４知，C的三角分解存在且唯一．１６畅解A的行范数６＋０．５，０．１＋０．３｝＝１．１．‖A‖∞＝max｛０．A的列范数６＋０．１，０．５＋０．３｝＝０．８．‖A‖１＝max｛０．‖A‖F＝（０．３６＋０．２５＋０．０１＋０．０９）AA＝T１／２＝０．８４２６．０畅３３０畅３４．０畅６０畅５０畅１０畅３０畅６０畅１０畅６０畅３＝２０畅３７０畅３３｜λI－AA｜＝Tλ－０畅３７－０畅３３－０畅３３λ－０畅３４＝λ－０．７１λ＋０．０１６９＝０．所以λmax（AA）＝０．６８５，则‖A‖２＝１７畅证（１）由定义知，‖X‖∞≈０畅８３．n＝１max｜xi｜≤i∑｜xi｜≤i≤n＝１＝‖X‖１≤i∑max｜xi｜＝n‖X‖∞，＝１１≤i≤n∞n从而‖X‖２∞≤‖X‖１≤n·‖X‖TT．（２）由范数定义有‖A‖２＝λmax（AA）≤λ１（AA）＋λ２（AA）＋…＋λn（AA）TT＝AA的对角元之和＝i∑a＋i∑a＋…＋i∑ani＝１＝１＝１T２１i２２２i２nnn＝j∑∑a＝i∑∑aij＝‖A‖F．＝１i＝１＝１j＝１２２nnnn又‖A‖２＝λmax（AA）２T３３４≥＝从而TTT［λ１（AA）＋λ２（AA）＋…＋λn（AA）］１２‖A‖F．‖A‖F≤‖A‖２≤‖A‖F．注：此处用到了矩阵的特征值之和等于其对角线上元素之和的概念．从所证不等式也知道，矩阵的２唱范数可由F唱范数得到控制；矩阵的２唱范数与F唱范数是等价的．１８畅证只要证明‖X‖P＝‖PX‖满足范数定义的（１），（２），（３）．（１）因P非奇异，故对任意X≠0，PX≠0，则‖X‖P＝‖PX‖＞０；当X＝0时，PX ＝0，则‖X‖（２）对任意实数α，‖αX‖P＝‖PαX‖＝‖αPX‖＝｜α｜‖PX‖＝｜α｜‖X‖（３）‖X＋Y‖PPP＝‖PX‖＝０；当‖X‖P＝‖PX‖＝０时，则PX＝0，即X＝0．．＝‖P（X＋Y）‖＝‖PX＋PY‖≤‖PX‖＋‖PY‖＝‖X‖P＋‖Y‖P．综上所述，‖X‖P是R上的一种向量范数．１９畅证因‖X‖p∞n＝１max｜xi｜≤i∑｜xi｜≤n·１max｜xi｜＝n·‖X‖≤i≤n≤i≤n＝１‖X‖∞≤（i∑｜xi｜）＝１np１／ppnppp∞，两边开p次方有≤n‖X‖∞．１而plim＝１，故→∞２０畅证由Cauchy不等式，有｜（X，Y）｜≤‖X‖２‖Y‖２，且当且仅当X、Y线性相关时，有３３５lim（i∑｜xi｜）p→∞＝１pn１／p１＝‖X‖∞．｜（X，Y）｜＝‖X‖２‖Y‖２；又当且仅当XY≥０时，有｜（X，Y）｜＝（X，Y）．T故（X，Y）＝‖X‖２‖Y‖２当且仅当X、Y线性相关，且XYT≥０时，所以‖X＋Y‖２＝（X＋Y，X＋Y）＝（X，X）＋２（X，Y）＋（Y，Y）＝‖X‖２＋２‖X‖２‖Y‖２＋‖Y‖２２２＝（‖X‖２＋‖Y‖２）２当且仅当X、Y线性相关，且X，Y≥０时，即‖X＋Y‖２＝‖X‖２＋‖Y‖２迟痴X，Y线性相关，且XY≥０．T２１畅证由于I－A及记B＝μIATTOμI－AIμIAATTAμIAμIμIO２２AμI－AATT，．（７畅２６）（７畅２７）μIOAμIμIμI－AAATOμI．对（７畅２６）、（７畅２７）两式两边取行列式得μdet（B）＝μdet（μI－AA），nnnn２２T记λ＝μ≠０，故２μdet（B）＝μdet（μI－AA）．TTT２２畅证设A＝（α１α２…αn）按列分块，即αj＝（α１j，α２j，…，αnj）（j ＝１，２，…，n），则‖αj‖＝i∑αij．而＝１２２２Tndet（λI－AA）＝det（λI－AA）．‖α１‖＋‖α２‖２２nn２ij２２＋…＋‖αn‖＝j∑‖αj‖２＝１２２２nn２２n＝j∑（∑α）＝j∑∑αij＝‖A‖F．＝１i＝１＝１i＝１２３畅证因‖B‖＜１，由定理７畅１６知I－B可逆且‖（I－B）－１‖≤，所以３３６‖I－（I－B）－１‖＝‖（I－B）≤‖（I－B）≤－１－１（I－B－I）‖‖‖B‖‖B‖．２４畅证由矩阵算子范数定义有‖I‖＝maxX≠O由矩阵范数的相容性有‖A‖‖A优势矩阵，则j＝１j≠i０－１‖IX‖‖X‖＝max＝１．X≠O‖≥‖AA－１‖＝‖I‖＝１．２５畅证（１）用反证法．若有某个i０使ai０i０＝０，因A是对角∑｜ai０j｜＜｜ai０j０｜＝０．n这是不可能的．得证．（２）因A＝DB，即a１１A＝a２１…an１而１B＝a２１２２…n１nn１２１１１………………１n１１a２n２２…１＝１１１１３３７…………a１na２n…anna１１a２２筹ann１２１２２…n１nn a１２１１１………………a１n１１２n２２…１＝DB．＝０－－－a２１２２n１nn －１２１１０…………－１n１１＝I－C．a２n２２０‖C‖∞＝maxi∑j＝１nj≠iaijii＝max∑ij＝１n｜aij｜＜１i ij≠in｜aij｜＜｜aii｜）．所以由定理（这是因为A是对角优势矩阵，则j∑＝１j≠i７畅１６知，B＝I－C为非奇异阵．由（１）aii≠０，故D非奇异．因此A＝DB 非奇异．２，…，n．而a１１（３）设A为对角优势阵，由（１）知aii≠０，i＝１，＝a １１，所以a１１≠０．又设经Gauss消元一步后A具有形式：（１）（１）a１１０（２）（k）α１TA２．（２）由习题７知，A２也是对角优势矩阵．又由（１）知aii≠０，i＝２，…，n，即有a２２≠０．如此类推akk≠０．２６畅证因‖A‖s＝maxX≠O‖AX‖s．s对一切X都有由定理７畅１０知，存在a１，a２＞０，b１，b２＞０，a１‖AX‖s≤‖AX‖t≤a２‖AX‖s，与b１‖X‖s≤‖X‖t≤b２‖X‖s．于是１‖AX‖s‖AX‖t２‖AX‖s≤≤．１st２s令１２＝c１＝c２，故有１２c１‖AX‖s‖AX‖t‖AX‖s≤≤c２．sts３３８c１maxX≠0即‖AX‖s‖AX‖t‖AX‖s２max≤max≤c．X≠0X≠0stsc１‖AX‖s≤‖AX‖t≤c２‖AX‖s．１００９９A－１２７畅解A＝９９９８＝，则－９８９９‖A－１９９－１００．‖A‖∞＝１９９，‖A－１‖∞＝１９９，所以∞因A是对称矩阵，故cond（A）∞＝‖A‖‖∞＝１９９×１９９＝３９６０１．λmax（A）．min＝λ－１９８λ－１＝０，２cond（A）２＝由det（λI－A）＝得即λ－１００－９９－９９λ－９８λ１＝１９８畅００５０５０３，λ２＝－０畅００５０５０３５．cond（A）２＝λ１＝３９２０６．２T－１２８畅证因A是正交阵，故A＝Acond（A）２＝max＝min，则max＝１．minmax＝min－１－１２９畅证由条件数的定义及矩阵范数的相容性，有cond（AB）＝‖AB‖‖（AB）＝‖A‖‖AT－１‖‖‖A≤‖A‖‖B‖‖B‖‖‖‖B‖‖B＝cond（A）cond（B）．３０畅证（１）因A＝WW，所以cond（A）２＝‖A‖２‖A２－１－１T‖２＝‖WW‖２‖（WW）TT－１‖２＝‖W‖２‖W‖２＝（cond（W）２）．２２T（２）由习题２１知，λ（WW）＝λ（WW），则３３９‖W‖２＝TTTmax＝－T故由（１）得，cond（W）２＝‖W‖２‖Wmax＝‖W‖２．－１‖２＝‖W‖２‖W２T‖２＝cond（W）２．３１畅解由cond（A）２＝［cond（W）２］＝cond（W）２cond（W）２．｜λI－A｜＝λ－２１＝λ－４λ＋３＝０，２解得所以‖A设b＝－１λ１＝１，λ２＝３．‖２＝１，‖A‖２＝３，cond（A）２＝，δb＝１１，这时有λ２＝３．１１－１‖δX‖２‖δb‖２＝cond（A）２．２２事实上，设X＋δX＝Y，则A（X＋δX）＝b＋δb，即２－１解得y１＝又解得x１＝所以δX＝＝２－１２y１y２＝２０，４２，y２＝．２－１１１，x２＝－．－１２x１x２＝１－１，＋＝＝３．而cond（A）２＝３４０‖δb‖２＝cond（A）２２＝cond（A）２＝３，故‖δX‖２‖δb‖２＝cond（X）２．２２３２畅解记A＝T２４０－１７９－３１９２４０T，δA＝０－０畅５－０畅５０则AX＝b的解X＝（４，３），而（A＋δA）（X＋δX）＝b的解（X＋δX）＝（８，６）．故‖X‖而A－１∞＝４，‖δX‖＝２４０１７９－１－１∞＝４．，∞∞３１９２４０‖A‖‖δA‖‖δA‖cond∞（A）＝‖A∞‖‖∞∞＝６２６畅２，＝０畅５６０１２．＝０畅５，‖A由推论７畅１９畅２得‖δX‖∞∞‖δA‖∞∞０畅５６０１２≤＝≤１畅２７４，∞１－cond∞（A）∞∞‖δX‖∞≤１畅２７４‖X‖∞≤５畅１０，表明估计‖δX‖∞＝４略大，是符合实际的．９３３畅解（１）H３－１－３６１９２－１８０３０－１８０；１８０＝－３６３０‖H３‖∞＝所以cond∞（H３）＝７４８．－１，‖H３‖∞＝４０８，（２）方程组在H３及b有微小变化时为１畅０００畅５０００畅３３３０畅５０００畅３３３０畅２５００畅３３３０畅２５００畅２００x１＋δx１x２＋δx２x３＋δx３１畅８３＝１畅０８０畅７８３３４１简记为（H３＋δH３）（X＋δX）＝b＋δb，它的精确解为X＋δX＝（１畅０８９５１２５３８，０畅４８７９６７０６２，１畅４９１００２７９８）．T而H３X＝b的精确解X＝（１，１，１），于是δX＝（０畅０８９５，－０畅５１２０，０畅４９１０）．‖δH３‖∞‖δb‖∞－３≈０畅１８×１０＜０畅０２％，≈０畅１８２％３∞∞而‖δX‖∞≈５１畅２％．∞这表明H３及b的相对误差不超过０畅３％，而引起解的相对误差超过５０％．由推论７畅１９畅２，可得‖δX‖∞≤∞≤３∞１－cond∞（H３）３∞‖δb‖∞‖δH３‖∞＋３∞∞TT４０８（（０畅０００２）＋０畅００１８２）≤０畅８９７４＝８９畅７４％．这个估计结果比实际误差大是合理的．３４畅解（１）先算出A于是cond∞（A）＝‖A（２）r＝b－AX珚＝＝７畅０００３－７－１＝‖∞１００００２００００‖A‖－∞１００００２０００１２畅０００１－２＝，－１＝４０００１×３畅０００１≈１２００１２．－１１０畅０５－０畅０５．２畅９７－１畅０１７畅０００３－７－６畅９５０３－６畅９５∞∞（３）依定理７畅２０，右端为cond∞（A）而左端为３４２‖r‖＝１２００１２×０畅０５≤８５７畅１９２，‖X－X珚‖∞０畅０３＝＝０畅０１．∞这表明当A为病态矩阵时，尽管剩余‖r‖很小，误差估计仍然较大，因此，当A病态时用‖r‖大小作为检验解的准确度是不可靠的．３５畅解（１）‖X‖１＝９，‖X‖２＝２（３）由１１２０a＞０，得a＜３，故a的取值范围－＜a＜２，‖X‖∞＝５．２（２）‖A‖１＝４，ρ（A）＝１（｜λI－A｜＝（λ－１），λ１，２＝１）．０a２，取a＝１时，L＝１００００．２３４３。