1 |
一個來自線性規劃解樓梯形最小平方問題的穩定方法黃聰明, HUANG,CONG-MING Unknown Date (has links)
當用內部點方法來解含有稠密行或退化的大型線性規劃問題,在解最小平方問題中,
當解趨近最佳解時,系統會趨近於singular的線性系統,在這種情況之下我們提出一
種有效而且穩定的方法來解決此問題。
Choi提出,對於有綢密行的矩陣Schur complement直接法會比加速的conjugate gra-
dient 方法來的有效,可是前者常會導致數值上的不穩定。Tomlin用 QR 分解法來解
I .s.p.可是此法會導致fill-ins,破壞稀疏的特性。用Given rotations 會比
上述方法來得有效且較穩定。而我們的新方法將更進一步的改進它的穩定性。雖然 S
VD 是最穩定的方法,可是它會破壞矩陣的稀疏性,為了保持稀疏性,所以我們不採
用SVD 方法,我們的方法最主要的是在於將樓梯形矩陣分割成小塊,再用 QR 和局部
調換來分解此小塊以保持稀疏性和穩定性。
B =[EF/GH],E 為樓梯形矩陣,對此矩陣的小塊,根據以下四規則由左上角到右
下角一個一個再分割和分解。
規則1:在處理現在的塊M 右下角最高位置的小塊之前,先將M底下的小塊處理完。
<有可能底下的小塊有部份已處理過,但尚未完全處理>
規則2:假如M 和參考的塊N 有共同的列<行>,則以N最高列<最左行>的位置為
準,向<向上>將M 分割成上下<左右>,M 和M ,兩小塊。
規則3:用 QR 加上行調換的方法,對M 做分解得到上三角矩陣R .假如R 的底下還
有其它小塊,則用R 對角線元素和Giver rotation方法,由上往下將底下小塊的元素
消去。
規則4:任何在R 右邊的部份或做分解時所產生的零矩陣皆不做分解和分割。E 分解
完後,再對F剩餘的部份分解,經過行和列的調換,即可得到上三角矩陣R .接著把
rank-deficient的部份和G ,用R 及高期消去法消掉並對H的部份做分解,得到我們
所要的分解。再經推導便可得到解l.s.p.的式子。由誤差估計和數值結果告訴
我們,此法是穩定而且有效的。
|
Page generated in 0.0231 seconds