Fw: [問題] 高斯消去法流程細節(已解決)

[EdisonX (閉上眼的魚)]

※ [本文轉錄自 Prob_Solve 看板 #1EnM7dB5 ]

作者: EdisonX (閉上眼的魚) 站內: Prob_Solve
標題: [問題] 高斯消去法流程細節
時間: Fri Nov 18 03:34:55 2011

最近有人拿了本書，問裡面 matrix 方面的問題，
主要是繞在高斯消去法之探討，但裡面的 code 跟我寫得很不一樣，
後來先上網找其他人寫得怎樣，主要也是分這兩派 。

關鍵是在 pivot 選取問題，若為 5*5 矩陣 matrix，
索引值從 0 計起，假設現在正要消 row 2，
該書之作法是

METHOD1

   matrix  從第 2 列 (當前列) 開始，一直到第 4 列 (最後一列)，
   歷遍所有元素 (所以是 a[2~4][2~4])，找到最大的元素絕對值，做為 pivot，
   假設找到的 pivot 是在 matrix[3][4] 這地方，
   那就要做 Rij(2,3)、Cij(2,4)，之後再做消去；
   如果找到的 pivot < eps，視為此方程組非唯一解。

所以在第 x 列要找 pivot 時，它花費了 x * n 的搜尋時間，
因為此法要找的 pivot 是要 「該列以下的最大元素值」。

這段流程讓人意外，
這和我自修看到的高斯消去法整個差很多，在「理論」書上是這麼做

METHOD 2

    matrix  一樣假設 5*5，索引值從 0 計起，
    假設現在消正要消 row 2 (a[row][row]，
    只要歷遍第 2~4 列之第 2 個元素 ( 所以是 a[2][2~4] )，
    只要找到 a[2][x] > eps ，就可視為 pivot，進行 Rij(2,x) 即可，
    再往後做消去；若找不到 a[2][x] > eps 之 x，視為此方程組非唯一解。 

我想問的是，是我想法有問題嗎？以 METHOD2 進行是比較容易出包嗎？
想了半天還是想不透 METHOD2 是不是有什麼「看不見的缺陷」，
畢竟這兩種作法整個在時間上的效能差很多，在此請教各位先進。

最後感謝各位撥冗閱讀，也請不吝指教，
小弟感激不盡。

--
If there is no tomorrow,
   I want to see u last time.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: EdisonX (180.177.78.41), 時間: 11/18/2011 03:37:57
推 rehearttw   :看不太懂... 是電腦演算法嗎？高中課本提供了一個
→ rehearttw   :基礎方法：以第一列第一行元素為準，消去其他列的
→ rehearttw   :的第一元素，再以第二列的第二元素為準，消去其他列
→ rehearttw   :（書上大多只有往下消）的第二行元素，如此下去
→ rehearttw   :為準元素若為零，則需做對調列的動作
→ rehearttw   :至於選擇哪一個為準，廣義的說法是以該列第一非零
→ rehearttw   :元素為準，可是比較可能先找到後方元素...
推 LimSinE     :應該是pivot要用來除，所以選絕對值大的數值誤差較小
→ EdisonX     :先謝謝L大與r大.這確實是程式碼/實際差異上的疑惑.
※ 編輯: EdisonX         來自: 180.177.78.41        (11/18 12:32)