PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 高斯消去法流程細節

看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間13年前 (2011/11/18 03:35)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/2 (看更多)

最近有人拿了本書，問裡面 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 ※ EdisonX:轉錄至看板 Math 11/18 03:37