三对角矩阵的压缩存储公式推导

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 2 3 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。

三对角矩阵压缩存储三对角矩阵是一种特殊类型的矩阵，在存储和计算上具有一定的优势。

本文将从三对角矩阵的定义、特性、压缩存储方法以及相应的计算算法等方面进行介绍。

一、三对角矩阵的定义三对角矩阵是指除了主对角线上的元素外，只有上下相邻对角线上的元素不为零，其余元素都为零的矩阵。

例如，一个n阶的三对角矩阵可以表示为：\[ A = \begin{bmatrix}b_1 & c_1 & 0 & \cdots & \cdots & \cdots & 0 \\a_2 & b_2 & c_2 & 0 & \cdots & \cdots & 0 \\0 & a_3 & b_3 & c_3 & 0 & \cdots & 0 \\\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\0 & \cdots & \cdots & \cdots & \cdots & a_{n-1} & b_{n-1} \\ 0 & \cdots & \cdots & \cdots & \cdots & 0 & a_n \\\end{bmatrix} \]其中，b1, b2, ..., bn为主对角线上的元素；a2, a3, ..., an为下对角线上的元素；c1, c2, ..., cn-1为上对角线上的元素。

二、三对角矩阵的特性1. 三对角矩阵是一种稀疏矩阵，大部分元素都为零，只有O(n)个非零元素。

2. 三对角矩阵可以用来表示一些特定问题的线性方程组，如一维热传导方程、抛物线偏微分方程等。

三对角矩阵的压缩存储公式推导标题：深入探讨三对角矩阵的压缩存储公式推导在线性代数和数值计算中，三对角矩阵是一类特殊的矩阵，它在科学计算、工程问题和物理建模中有着广泛的应用。

三对角矩阵的压缩存储公式是对其特殊结构的一种有效利用，本文将深入探讨三对角矩阵的性质以及推导其压缩存储公式，帮助读者更好地理解和应用这一重要概念。

一、三对角矩阵的定义及性质三对角矩阵是指除了主对角线上的元素外，只有相邻对角线上的元素不为零的矩阵。

它具有以下的性质：1. 三对角矩阵是一种特殊的带状矩阵，具有较强的结构性质；2. 由于其大部分元素为零，因此可以采用压缩存储方式来节省存储空间；3. 在数值计算中，三对角矩阵往往会出现在线性方程组的求解、差分方程的离散化、特征值计算等问题中，因此了解其压缩存储公式对于优化算法和提高计算效率具有重要意义。

二、三对角矩阵的压缩存储公式推导三对角矩阵的压缩存储公式是一种基于其特殊结构的存储方式，可以将其非零元素存储在一个更小的数组中，从而节省存储空间和提高计算效率。

下面我们将对三对角矩阵的压缩存储公式进行推导。

假设我们有一个n阶的三对角矩阵A，其一般形式如下：\[ A = \begin{pmatrix} a_1 & b_1 & 0 & 0 & \cdots & \cdots & 0 \\ c_1 & a_2 & b_2 & 0 & \cdots & \cdots & 0 \\ 0 & c_2 & a_3& b_3 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\ 0 & \cdots & \cdots & c_{n-2} &a_{n-1} & b_{n-1} & 0 \\ 0 & \cdots & \cdots & \cdots & c_{n-1} & a_n \end{pmatrix} \]为了压缩存储这个矩阵，我们可以使用两个数组来存储非零元素，一个数组存储矩阵的对角线上的元素，另一个数组存储矩阵相邻对角线上的元素。

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

稀疏矩阵及其压缩存储方法1.基本概念稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。

设m行n列的矩阵含t个非零元素，则称以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。

特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。

如下三角阵、三对角阵、稀疏矩阵。

压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。

目的是节省大量存储空间。

n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。

2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构）三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。

它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。

当矩阵中的非0元素少于1/3时即可节省存储空间。

（1）稀疏矩阵的三元组顺序表存储表示方法#define MAXSIZE 12500 // 假设非零元个数的最大值为12500typedef struct {int i, j; // 该非零元的行下标和列下标ElemType e; //非零元素的值} Triple; // 三元组类型typedef union { //共用体Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用int mu, nu, tu; // 矩阵的行数、列数和非零元个数} TSMatrix; // 稀疏矩阵类型（2）求转置矩阵的操作◆用常规的二维数组表示时的算法for (col=1; col<=nu; ++col)for (row=1; row<=mu; ++row)T[col][row] = M[row][col];其时间复杂度为: O(mu×nu)◆用三元组顺序表表示时的快速转置算法Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.mu = M.nu; T.nu = M.mu; T.tu = M.tu;if (T.tu) {for (col=1; col<=M.nu; ++col) num[col] = 0;for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];// 求M 中每一列所含非零元的个数cpot[1] = 1;for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1];// 求M 中每一列的第一个非零元在b.data 中的序号for (p=1; p<=M.tu; ++p) { // 转置矩阵元素col = M.data[p].j; q = cpot[col];T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i;T.data[q].e =M.data[p].e; ++cpot[col];} // for} // ifreturn OK;} // FastTransposeSMatrix其时间复杂度为: O(mu +nu)3.行逻辑联接的顺序表——压缩存储稀疏矩阵方法之二（链接存储结构）行逻辑联接的顺序表：稀疏矩阵中为了随机存取任意一行的非0元素，需要知道每一行的第一个非0元素在三元组表中的位置，因此将上述快速转置算法中指示行信息的辅助数组cpot 固定在稀疏矩阵的存储结构中，让每一行对应一个单链表，每个单链表都有一个表头指针，这种“带行链接信息”的三元组表即称为行逻辑联接的顺序表。

三对角矩阵公式推导我们先定义一个三对角矩阵，记作A：\[A = \begin{bmatrix}a_1 & b_1 & 0 & 0 & \dots & 0 \\c_1 & a_2 & b_2 & 0 & \dots & 0 \\0 & c_2 & a_3 & b_3 & \dots & 0 \\\vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\0 & \dots & 0 & c_{n-2} & a_{n-1} & b_{n-1} \\0 & \dots & 0 & 0 & c_{n-1} & a_n \\\end{bmatrix}\]我们想要找到一个矩阵B，使得A可以通过B的逆和B相乘得到。

如果我们能够找到相应的B，那么我们就可以得到A的逆矩阵。

通过观察，我们可以发现这个三对角矩阵有一些特点。

首先，对角线上的元素是$a_1, a_2, a_3, \dots, a_n$，即A的主对角线元素。

其次，A的上方对角线元素是$b_1, b_2, b_3, \dots,b_{n-1}$，下方对角线元素是$c_1, c_2, c_3, \dots, c_{n-1}$。

其他位置的元素都是零。

我们再来观察相应的矩阵B。

B的对角线上的元素是$b_1, b_2, b_3, \dots, b_{n-1}$，B的上方对角线元素是$c_1, c_2, c_3,\dots, c_{n-1}$，下方对角线元素是$c_1, c_2, c_3, \dots, c_{n-1}$。

其他位置的元素都是零。

根据矩阵乘法的定义，我们可以将矩阵B的逆矩阵写成如下形式：\[B^{-1} = \begin{bmatrix}d_1 & e_1 & 0 & 0 & \dots & 0 \\f_1 & d_2 & e_2 & 0 & \dots & 0 \\0 & f_2 & d_3 & e_3 & \dots & 0 \\\vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\0 & \dots & 0 & f_{n-2} & d_{n-1} & e_{n-1} \\0 & \dots & 0 & 0 & f_{n-1} & d_n \\\end{bmatrix}\]要得到A的逆矩阵，我们需要通过B的逆和B相乘。

第5章数组与广义表习题练习答案5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a02125.2 给出C语言的三维数组地址计算公式。

解：因为C语言的数组下标下界是0，所以Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表示三维数组。

Loc(A000)表示数组起始位置。

i、j、k表示当前元素的下标,d表示每个元素所占单元数。

5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求：(1)用i , j 表示k的下标变换公式。

(2)用k 表示i,j 的下标变换公式。