當用內部點方法來解含有稠密行或退化的大型線性規劃問題，在解最小平方問題中，

當解趨近最佳解時，系統會趨近於singular的線性系統，在這種情況之下我們提出一

種有效而且穩定的方法來解決此問題。

Choi提出，對於有綢密行的矩陣Schur complement直接法會比加速的conjugate gra-

dient 方法來的有效，可是前者常會導致數值上的不穩定。Tomlin用 QR 分解法來解

I ．ｓ．ｐ．可是此法會導致fill-ins，破壞稀疏的特性。用Given rotations 會比

上述方法來得有效且較穩定。而我們的新方法將更進一步的改進它的穩定性。雖然 S

VD 是最穩定的方法，可是它會破壞矩陣的稀疏性，為了保持稀疏性，所以我們不採

用SVD 方法，我們的方法最主要的是在於將樓梯形矩陣分割成小塊，再用 QR 和局部

調換來分解此小塊以保持稀疏性和穩定性。

B =[EF/GH]，E 為樓梯形矩陣，對此矩陣的小塊，根據以下四規則由左上角到右

下角一個一個再分割和分解。

規則１：在處理現在的塊M 右下角最高位置的小塊之前，先將Ｍ底下的小塊處理完。

＜有可能底下的小塊有部份已處理過，但尚未完全處理＞

規則２：假如M 和參考的塊N 有共同的列＜行＞，則以Ｎ最高列＜最左行＞的位置為

準，向＜向上＞將M 分割成上下＜左右＞，M 和M ，兩小塊。

規則３：用 QR 加上行調換的方法，對M 做分解得到上三角矩陣R ．假如R 的底下還

有其它小塊，則用R 對角線元素和Giver rotation方法，由上往下將底下小塊的元素

消去。

規則４：任何在R 右邊的部份或做分解時所產生的零矩陣皆不做分解和分割。E 分解

完後，再對Ｆ剩餘的部份分解，經過行和列的調換，即可得到上三角矩陣R ．接著把

rank-deficient的部份和G ，用R 及高期消去法消掉並對Ｈ的部份做分解，得到我們

所要的分解。再經推導便可得到解ｌ．ｓ．ｐ．的式子。由誤差估計和數值結果告訴

我們，此法是穩定而且有效的。