當用內部點方法來解含有稠密行或退化的大型線性規劃問題，在解最小平方問題中，
當解趨近最佳解時，系統會趨近於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 及高期消去法消掉並對Ｈ的部份做分解，得到我們
所要的分解。再經推導便可得到解ｌ．ｓ．ｐ．的式子。由誤差估計和數值結果告訴
我們，此法是穩定而且有效的。
| Identifer | oai:union.ndltd.org:CHENGCHI/B2002005458 |
| Creators | 黃聰明, HUANG,CONG-MING |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | Unknown |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.002 seconds