利用內點方法解線性規劃問題，其最費時的部份就是在解一最小平方問題。如果nor-
mal equation的矩陣為正定，知LDL 分解是穩定的方法；然而，對於矩陣為奇異（s-
ingular） 的情形，則可能會造成數值上的誤差，這篇論文，我們考慮線性規劃問題
，它的限制矩陣為大型，稀疏且angular 的結構；我們假設由此線性規劃問題來的n-
ormal 矩陣M 為奇異的，而Ｍ的對角線block 可能為近似奇異或奇異的，我們提出一
個block method利用LDL 分解和對角線性的pivoting來解normal equation 。我們同
時採用Chan及Stewart 提出的deflation 技巧來解半正定矩陣。
對於奇異且非正定矩陣，Chan建議一個演算法，能保證得到最小的pivot 。至於我們
的方法解半正定矩陣是非常有效的。在第二節，先考慮緊緻（dense ）矩陣的情況，
我們證明了一個定理，並由此定理得到一個演算法；對所有rank deficient的矩陣，
經過對角線的pivoting，必能在矩陣最後得到小的pivot 。第三節中，為了保持M 的
結構，我們推廣在第二節的演算法；利用blockmethod 即可達到目的，而第四節，則
討論deflation 方法能夠應用的情況。
Bunch 和Kaufman 於１９７７年曾提出幾個穩定的演算法來解非正定系統；我們發現
其中一個演算法應用到正定的矩陣，會與我們的演算法得到類似的結果，這是可以理
解的。但因為解問題的目的不同，並且針對矩陣Ｍ的特殊結構，不能對整個矩陣作p-
ivoting ，以免破壞稀疏的情形下，我們的演算法是有效的。此外，簡化Chan提出的
兩段演算法以得到小的pivot ，與同時使用deflation 方法和block method解退化的
線性規劃問題，是這篇論文的另一個結論。
|