Without pivoting 的意思是不換 rows
Small round off error 會隨著 Gaussian elimination 運算而累積, 尤其在大矩陣的情況很容易發生!
這樣光解一個大一點的線性系統都有問題了. 舉例來說:
以下是一個人為設計過的例子 (contrived example):
英文時間: contrived 意思是 人為的，不自然的;牽強的
Gaussian elimination 步驟如果 forward 不交換 rows, 得到上圖左下方的結果.
然後開始做 backward, 先計算 $x_2$.
注意到 $2+\epsilon=2$, 因為 $2$ 離下一個最大的數值差距為 $2\epsilon$, 所以會有 round off error. Check here.
<aside> 💡
$2+\epsilon=2$ (round-off error), 但是 $2-\epsilon\neq 2$ (沒有 round-off error); $-2-\epsilon=-2$ (round-off error), $-2+\epsilon\neq -2$ (沒有 round-off error)
</aside>
同理 $4-\epsilon=4$, 因為 $4$ 離下一個最大的數值差距為 $4\epsilon$. 這導致 $x_2$ 會 exactly 等於 $2$.
所以套回去 $x_1$ 會得到錯誤的 $0$ 結果, 合理的結果是 $x_1$ 很接近 $3$ 才對.
下一段會說明如何做出合理結果, 縱使仍發生 round-off error.
Partial pivoting 是指 row interchangable (full pivoting 表示交換也可以發生在 column 之間)
作法很簡單, 每一次的 Gaussian elimination 時, 使用 row interchange 來使得該 pivot 的 magnitude 最大.
這極其簡單的作法極大的增加了系統的穩定性.