MATLAB-ch017(数值计算-稀疏局阵)20090922.ppt

第17讲 数值计算——稀疏矩阵 引言 §17.1稀疏矩阵的存储 一、稀疏矩阵的存储方式 二、稀疏存储的特点 3、需要三个数组来实现稀疏存储 三、稀疏矩阵和全元素矩阵之间的转化 〖例17-1〗 〖例17-1〗（续1） §17.2稀疏矩阵的创建 一、直接创建稀疏矩阵 2、直接创建稀疏矩阵命令sparse 〖例17-3〗 二、稀疏带状矩阵的创建 例17-5 三、从外部文件输入稀疏矩阵 1、spconvert函数 1、spconvert函数（续1） 例17-5 例17-5（续1） 例17-5（续2） §17.3稀疏矩阵的查看 一、whos命令二、nnz命令三、nonzeros命令四、nzmax命令 五、find命令 五、find命令 §17.4稀疏矩阵的运算 一、运算规则 一、运算规则（续1） 一、运算规则（续2） 一、运算规则（续3） 一、运算规则（续4） 二、稀疏矩阵运算的常用命令 例17-12 例17-12（续1） 例17-12（续2） 例17-12（续3） 小 结 5、参与矩阵扩展时，只要有一个是稀疏的，则所得的结果也是稀疏的。 参与的矩阵扩展(如[A B;C D]的子矩阵)中，只要有一个是稀疏的，则所得的结果也稀疏。也就是说，矩阵采用cat函数或方括号连接对于混合算于将产生稀疏结果。 6、在矩阵赋值语句中，将以原矩阵形式给出结果。 在矩阵赋值语句中，将以原矩阵形式(稀疏还是全元素)给出结果。也就是说，若矩阵S稀疏，不管i，j是标量或是向量，在赋值语句右侧的T=S(i,j)将产生稀疏结果；而赋值语句左侧的子矩阵索引T(i,j)=S中，将产生全元素的结果。 在MATLAB中，提供有针对稀疏矩阵进行运算的函数命令，常用运算命令如表17-1所示。 n=250; %给出矩阵的阶数 rand(state,1) %为重复产生相同的矩阵而设 rand(state,2) A=sprandsym(n,0.015)+100*speye(n,n); %建立(100×100)随机正定稀疏矩阵 subplot(1,2,1) spy(A,b,10) title(矩阵A的结构图) 〖例17-12〗example17-12.m 全元素矩阵，稀疏矩阵和最小排序稀疏矩阵三角分解所需时间的比较。 subplot(1,2,2) d=symmmd(A); %采用最小排序法 spy(A(d,d),b,10) title(最小排序法) B=full(A) %给出A的全元素形式 ％下面比较三个矩阵的cholesky分解 format long e tic,L1=chol(B); t1=toc %全元素时，分解所用的计算时间 tic,L2=chol(A); t2=toc %稀疏时，分解所用的计算时间 tic,L3=chol(A(d,d)); t3=toc ％最小排序时，分解所用计算时间 t1= 1.09999999999994e-001 t2= 6,000000000000227e-002 t3= 0 程序运行结果如图17-10所示。 在稀疏结构绘图命令spy中，第二个参数定义画图颜色，第三个参数使色点较大，便于观察。 图17-10 稀疏矩阵结构 * * 张建瓴 工程实践中，往往需要解大型的线性方程组。而对于一个用矩阵描写的线性方程来说，n个未知数的问题就涉及一个n×n的方程组，解这个方程就需要n2个数字的内存和正比于n3的计算时间。这样解一个大型(如上千阶)方程组就很不容易处理(即使现在的计算机技术不断提高)，有时对于计算所用的时间要求更为苛刻。 在大多数情况下，一个未知数只和数量不多的其他变量有关，即关系矩阵是稀疏矩阵。 在MATLAB中，有一种解决该问题的方法，即使用稀疏矩阵。它只存储矩阵的少量非零元素，而不存储那些零元素，也不对它们进行操作，从而节省了内存和时间。稀疏矩阵计算的复杂性和代价仅取决于稀疏矩阵的非零元素数目，而与该矩阵的总元素个数无关。 在MATLAB中有两种存储矩阵的方式：一种是全元素(Pull)存储，另一种是稀疏(Sparse)存储。 1、全元素存储 全元素存储就是存储矩阵的每一个元素，零值元素和其他元素一样需要相同的存储空间。 2、稀疏存储 稀疏存储仅存储那些非零元素及其下标，对于有较多零元素的大型矩阵，这种存储将显著减少所需的存储空间。 1、只存储矩阵的非零元素 只存储矩阵的非零元素，并且存储按列进行。 2、按列进行存储 （1）只存储矩阵