Abstract
決定矩陣 rank 的方法, 最可信賴的變換方法是 rank revealing QR(RRQR) 和 rank revealing LU (RRLU) 分解. 首先, 我們定義何謂RRQR 分解.定義: (Rank Revealing QR 分解)給一 m 乘 n ( m 大於或等於 n ) rank 是 r 的矩陣 A. 如果存在一調換矩陣 P 和 orthogonal 矩陣 Q, 使得 / \ | R_{11} R_{12} | Q A P =| 0 R_{22} | | 0 0 | \/其中, (n-r) 乘 (n-r) 上三角矩陣 R_{22} 的最大奇異值 ( singularvalue ) 很小而且遠小於 r 乘 r 上三角矩陣 R_{11} 的最小奇異值,則此分解稱之為 RRQR 分解. 1987, T. F. Chan 提出一種方法, 但此方法只能証明 R_{22} 對角線的元素很小, 對於 R_{22} 的最大奇異值只能証明跟 2 的 n-r 次方有關, 因此當 n-r 值大時, 無法保證可以得到RRQR 分解. 1992, Y. P. Hong 和 C. T. Pan 證明 RRQR 分解的存在性, 但此方法僅是理論的證明, 無法實際應用到計算上, 因此我們針對此缺點, 提出一套實用性高而且保證可得到 RRQR 分解的理論與方法.利用在 RRQR 分解所得到的結果, 應用到 LU 分解上, 我們可得一 RRLU 分解, 以下我們定義 RRLU 分解.定義: (Rank Revealing LU 分解)對一rank r 的 n 乘 n 矩陣 A. 如果存在調換矩陣 P 和 Q, 使得/ \ / \ | L_{11} 0 | | U_{11} U_{12} | P A Q = | | | |, |L_{21} I | | 0 U_{22} | \ /\ /其中, (n-r) 乘 (n-r) 上三角矩陣 U_{22} 的最大奇異值 ( singular value ) 很小而且遠小於 r 乘 r L_{11}U_{11} 的最小奇異值, 則此分解稱之為 rank revealing LU (RRLU) 分解. 1984,T. F. Chan 提出一種選取調換矩陣 P 和 Q 的方法, 解決了 nullity等於 1 的矩陣. 1992, 我們將 Chan 所證明的結果推廣至一般的情況,也就是 nullity 大於或等於 1, 證明了 RRLU 的存在性.接著我們利用RRQR 分解中對調換矩陣的選取方法, 建立一套更為完整而且實用的方法與理論架構.