?53特殊矩阵及其压缩存储 531特殊矩阵 1·对称矩阵 若一个n阶方阵A中元素满足下列条件: a=a1其中0≤i,j≤n1,则称A为对称 矩阵 例如,图5-1是一个3*3的对称矩阵。 23 A=254 图5-1一个对称矩阵
5.3 特殊矩阵及其压缩存储 5.3.1 特殊矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 ≤i, j≤n-1 ， 则称A为对称 矩阵。 例如，图5-1是一个3*3的对称矩阵。 A= 3 4 6 2 5 4 1 2 3 图 5-1 一个对称矩阵 1．对称矩阵
它72:三角矩阵 (1)上三角矩阵 即矩阵上三角部分元素是随机的,而下三角部分元 素全部相同(为某常数C)或全为0,具体形式见 图5-2(a) (2)下三角矩阵 即矩阵的下三角部分元素是随机的,而上三角部 分元素全部相同(为某常数C)或全为0,具体形 式见图5-2(b)。 do 01 a n-10n-1 an-In-l n-1n-1 (a)上三角矩阵 (b)下三角矩阵 图5-2三角矩阵
2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元 素全部相同（为某常数C）或全为0，具体形式见 图5-2(a)。 （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部 分元素全部相同（为某常数C）或全为0，具体形 式见图5-2(b)。 1 0 1 1 1 1 1 0 1 1 0 0 ... ... ... ... ... ... ... n− n− n− n− a a a a a c a c c (a) 上三角矩阵 （b）下三角矩阵 1 1 11 1 1 00 01 0 1 ... ... ... ... ... ... − − − − n n n n c c c a c a a a a a 图 5-2 三角矩阵
′3.对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中 心的带状区域中,区域外的值全为0,则称为对角 角矩阵等。 例如,图5-3为7×7的三对角矩阵(即有三条对角 线上元素非0)。 0000 000 0 00 00a 0 000a 000005 0000a 00000 图5-3一个7×7的三对角矩阵
3．对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中 心的带状区域中，区域外的值全为0，则称为对角 矩阵。常见的有三对角矩阵、五对角矩阵、七对 角矩阵等。 例如，图5-3为77的三对角矩阵（即有三条对角 线上元素非0）。 6 5 6 6 5 4 5 5 5 6 4 3 4 4 4 5 3 2 3 3 3 4 2 1 2 2 2 3 1 0 1 1 1 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a a a a a a a a a a a a a a a a a a 图 5-3 一个 77 的三对角矩阵
gx5.3.2压缩存储 1.对称矩阵 若矩阵A是对称的,对称的两个元素可以共用一个存 储单元,这样,原来n阶方阵需m2个存储单元,若采用 压缩存储,仅需n(n+1)2个存贮单元,将近节约一半存 贮单元,这就是实现压缩的好处。但是,将n阶对称方 入阵存放到一个向量空间S到21-1 我们怎样找到Sk]与a]订的一一对称应关系呢?使我们 在sk]中直接找到a[订[i 我们仅以行优先存放分两种方式讨论:
5.3.2 压缩存储 1．对称矩阵 若矩阵Ann是对称的，对称的两个元素可以共用一个存 储单元，这样，原来n 阶方阵需 n 2个存储单元，若采用 压缩存储，仅需 n(n+1)/2个存贮单元，将近节约一半存 贮单元，这就是实现压缩的好处。但是，将n阶对称方 阵存放到一个向量空间s[0]到s[ -1] 中， 我们怎样找到s[k]与a[i][j]的一一对称应关系呢？使我们 在s[k]中直接找到a[i][j]。 2 n(n+1) 我们仅以行优先存放分两种方式讨论：
(1)只存放下三角部分 由于对称矩阵关于主对角线对称,故我们只需存放主 对角线及主对角线以下的元素。这时,aO[0存入 s[0],a[10]存入s1],a[11入s2],…,具体参 见图5-4。这时Sk]与a的对应关系为: (计+1)2+j当 +1)2+i当i<j 上面的对应关系读者很容易推出:当运时,在下三角 部分中,aj前面有i行,共有1+2+3++个元素,而a是 第i行的第j个元素,即有k=1+2+3+.+计+j=(i+1)/2+j;当还 时,a在上三角部分中,但与aji对称,故只需在下三角部 分中找叫即可,故只需将i与j交换即可,即k=j+1)2+i
（1）只存放下三角部分 由于对称矩阵关于主对角线对称，故我们只需存放主 对角线及主对角线以下的元素。这时， a[0][0]存入 s[0]，a[1][0] 存入s[1]，a[1][1]存入 s[2]，…，具体参 见图5-4。这时s[k]与a[i][j]的对应关系为： i(i+1)/2+j 当 i≥j k= j(j+1)/2+i 当 i<j 上面的对应关系读者很容易推出：当i≥j 时，aij在下三角 部分中，aij前面有i行，共有1+2+3+…+i个元素，而aij是 第i行的第j个元素，即有k=1+2+3+…+i+j=i(i+1)/2+j；当i<j 时，aij在上三角部分中，但与aji对称，故只需在下三角部 分中找aij即可，故只需将i与j交换即可，即k=j(j+1)/2+i