5.3.1特殊矩阵 1、对称矩阵 a00a01………aon-1 a 10 a a 在一个n阶方阵A中,若元 素满足下述性质: a=a]p0≤≌n-1 n-1n-1 则称A为对称矩阵。如图51便是一个5阶对称矩阵。对称矩 阵中的元素关于主对角线对称,故只要存储矩阵中上三角或 下三角中的元素,让每两个对称的元素共享一个存储空间, 这样,能节约近一半的存储空间。不失一般性,我们按“行 优先顺序”存储主对角线(包括对角线)以下的元素,其存 储形式如图所示: 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 ⚫ 1、对称矩阵 5.3.1 特殊矩阵 ⚫ 在一个n阶方阵A中，若元 素满足下述性质： aij=aji 0≦i,j≦n-1 ⚫ 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩 阵中的元素关于主对角线对称，故只要存储矩阵中上三角或 下三角中的元素，让每两个对称的元素共享一个存储空间， 这样，能节约近一半的存储空间。不失一般性，我们按“行 优先顺序”存储主对角线（包括对角线）以下的元素，其存 储形式如图所示： a00 a01 …. … ….. a0n-1 a10 a11…….. ……. a1n-1 an-10 an-11 …….. an-1n-1 …………………
1、对称矩阵 a00a01 aon 10 10an1∴∴an a20a21a23 an-10 an-11 an-12.a n-1n-1 1n-10an-11…an-1n-1 图51对称矩阵 ●在这个下三角矩阵中,第恰有ⅰ1个元素,元素总数为: (+1)=n(+1)/2。这样可将n2个压缩到n(n+1)2个元的空间 中 因此,我们可以按图中箭头所指的次序将这些元素存放在 个向量sa0n(n+1)2-们]中。为了便于访问对称矩阵A中的 元素,我们必须在a和sa啊之间找一个对应关系。 北京邮电大学自动化学院
北京邮电大学自动化学院 12 a00 a10 a 11 a20 a21 a23 ……………….. an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 a00 a01 …. … ….. a0n-1 a10 a11…….. ……. a1n-1 an-10 an-11 …….. an-1n-1 …………………. 图 5.1 对称矩阵 ⚫ 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2。这样可将n 2个压缩到n(n+1)/2个元的空间 中。 ⚫ 因此，我们可以按图中箭头所指的次序将这些元素存放在一 个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的 元素，我们必须在aij和sa[k]之间找一个对应关系。 1、对称矩阵
1、对称矩阵 ij,则a在下三角形中。a之前的行(从第0行到第i-1 行)一共有1+2+…+=(+2个元素,在第行上,a之前 恰有个元素(即a0,an1a2,…,a1),因此有: k=i(+1)2+0≤k<n(n+1)2 若i<j,则a是在上三角矩阵中。因为a=a,所以只要交换 上述对应关系式中的利即可得到: k可j+1)2+i 0≤k<n(n+1)2 令max(l),J=min(i),则k和i,j的对应关系可统一为: ·k=(+1)/2+J 0≤k<n(n+1)2 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 ⚫ i≧j，则aij在下三角形中。 aij之前的i行（从第0行到第i-1 行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上， aij之前 恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有： 1、对称矩阵 ⚫ k=i*(i+1)/2+j 0≦k<n(n+1)/2 ⚫ 若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换 上述对应关系式中的i和j即可得到： ⚫ k=j*(j+1)/2+i 0≦ k<n(n+1)/2 ⚫ 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： ⚫ k=I*(I+1)/2+J 0≦ k<n(n+1)/2
●因此,an的地址可用下列式计算: Loc(a=Loc(sak】) .=LOC(sa[o]+k*d=LOc(sa[o]+[(+1)/2+J]*d) 有了上述的下标交换关系,对于任意给定一组下标(,j),均 可在sak中找到矩阵元素a,反之,对所有的k=0,1,2n(n 1)/2-1,都能确定sa〖k中的元素在矩阵中的位置()。由此, 称sa[n(n+1)2]为阶对称矩阵A的压缩存储,见下图: aoo a10a11 a20 an-1 0 an-1n-1 k=01 23 n(n-1)/2 n(n-1)/2 ·例如a2和a12均存储在sa4]中,这是因为 k=(1)/2+J=2*(2+1)2+1=4 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ⚫ 因此，aij的地址可用下列式计算： ⚫ LOC(aij)=LOC(sa[k]) ⚫ =LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d） a00 a10 a11 a20 …… an-1 0 …… an-1,n-1 ⚫ 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均 可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n- 1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此， 称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图： ⚫ k= 0 1 2 3 n(n-1)/2 n(n-1)/2-1 ⚫ 例如a21和a12均存储在 sa[4]中，这是因为 ⚫ k=I*(I+1)/2+J=2*(2+1)/2+1=4
2、三角矩阵 以主对角线划分,三角矩阵有上三角和下三角两种。 ●上三角矩阵如图所示,它的下三角(不包括主对角线)中的 元素均为常数。 下三角矩阵正好相反,它的主对角线上方均为常数,如图所 示。在大多数情况下,三角矩阵常数为零。 a00a01 a 00 0n-1 a10 a11 1n-1 n-10an-11 n-1n-1 n-1n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2三角矩阵 北京邮电大学自动化学院
北京邮电大学自动化学院 15 ⚫ 以主对角线划分，三角矩阵有上三角和下三角两种。 2、三角矩阵 a00 a01 … a 0 n-1 c a11 … a1 n-1 …………….. c c … a n-1 n-1 (a)上三角矩阵 a00 c … c a10 a11 … c …………….. an-1 0 an-1 1 … an-1 n-1 (b)下三角矩阵 图5.2 三角矩阵 ⚫ 上三角矩阵如图所示，它的下三角（不包括主对角线）中的 元素均为常数。 ⚫ 下三角矩阵正好相反，它的主对角线上方均为常数，如图所 示。在大多数情况下，三角矩阵常数为零