重排成一個不動點
上一篇指南論證了「為什麼」我們要在一個巨大稀疏的 A x = b 上迭代，而不是去分解它：分解會把零填滿、把記憶體噎死，而迭代從頭到尾只把 A 乘上一個向量。現在我們來建出那兩個最古老的迭代法，它們都來自一個孩子氣的動作。取 A x = b 的第 i 個方程式——它把所有未知數綁在一起——然後只對第 i 個未知數 x_i 解開它，暫時假裝其他「所有」未知數都已經知道了。你會得到一個用其他未知數來表示 x_i 的公式。那個公式不是答案；它是一個「改進」猜測的食譜，而把一個猜測一遍又一遍地餵過它，就是一個定常迭代（stationary iteration）。
用拆分矩陣把這件事弄精確。寫成 A = M - N，其中 M 是某個容易求逆的部分，N 是剩下的。於是 A x = b 變成 M x = N x + b，這暗示了迴圈 x_{n+1} = M^{-1} (N x_n + b)：把你現在的猜測 x_n 代進右邊，解那個容易的 M 系統，下一個猜測 x_{n+1} 就跑出來了。這就是一個矩陣拆分，而每一種 M 的選法都給出一個不同的古典方法。竅門在於挑一個對它求解既便宜、又夠接近 A 讓迴圈真能收斂的 M。注意我們從不對 A 本身求逆——只對容易的 M——這正是迭代所提供的那筆划算交易。
Jacobi 法：所有人同時更新
最簡單的拆分把 M 挑成 A 的對角線而已。解一個對角系統易如反掌——把每個元素除以它的對角元——所以這是可能存在的最便宜的 M。這個選法就是 Jacobi 法：要得到 x_i 的新值，取它自己的方程式，用其他未知數的「舊」值把每一個其他項移到右邊，再除以對角元 a_ii。關鍵在於，每一個分量都是從同一個舊猜測更新出來的，所以你掃過方程式的次序無關緊要，而且你可以平行地算出所有分量。這是想像得到最民主的更新：在這一輪結束之前，沒有人聽得到任何其他人的消息。
Solve A x = b, A = [[10, -1, 2], b = [ 6, start x = (0, 0, 0)
[-1, 11, -1], 25,
[ 2, -1, 10]] -11]
Jacobi update (all from OLD x):
x1 = ( 6 + x2 - 2 x3) / 10
x2 = (25 + x1 + x3 ) / 11
x3 = (-11 - 2 x1 + x2) / 10
iter 0: x = (0.000, 0.000, 0.000)
iter 1: x = (0.600, 2.273, -1.100)
iter 2: x = (1.047, 2.227, -0.993) ... -> (1.043, 2.269, -1.082)Gauss-Seidel 法：消息一到就用
Jacobi 法浪費資訊。當你正在更新 x_2 時，你這一輪「早就」算出了一個新鮮、更好的 x_1——然而 Jacobi 卻堅持要用那個過時的 x_1。Gauss-Seidel 法用一個微小的改動修好它：當你由上往下掃過方程式時，每個新分量一可用就立刻採用。所以 x_2 是用全新的 x_1 算的；x_3 是用全新的 x_1 與 x_2 算的；以此類推。用拆分的語言講，M 現在是 A 的下三角部分（對角線加上它以下的一切），用前向代入求解。用更新鮮的數字幾乎總是收斂得更快——對例子裡那些乖巧的系統，大約比 Jacobi 快一倍，把迭代次數砍半。
這份速度是有代價的：因為每個分量現在都倚賴這趟掃描裡已經更新過的那些，結果就取決於掃描的「次序」，而你沒辦法像 Jacobi 那樣輕易地把單趟掃描平行化。Gauss-Seidel 法仍然可以靠對未知數做聰明的著色而平行化，但樸素版本本質上是循序的。所以這兩個方法做了誠實的取捨——Jacobi 法尷尬地易於平行，但在序列執行下每步較慢；Gauss-Seidel 法每步較快，卻依賴次序。沒有哪一個是放諸四海皆準的贏家，而且我們將會看到，兩者單獨用在嚴肅問題上通常都太慢，主要是當作積木使用。
譜半徑：迴圈會收攏嗎？
現在來看真正的問題。跑迴圈 x_{n+1} = G x_n + c，其中 G = M^{-1} N 是你的拆分裡內建的迭代矩陣。為什麼這些猜測會安定在真正的 x 上，而不是爆掉或永遠振盪？把不動點方程式 x = G x + c 從迭代式裡減掉，你會發現誤差服從 e_{n+1} = G e_n。所以 n 步之後誤差是 e_n = G^n e_0：迭代矩陣被一遍又一遍地作用在起始誤差上。於是收斂與否的整個問題，就是 G 的次方 G^n 是否縮到零的問題——而這由一個單一的數字主宰。
那個數字就是 G 的譜半徑（spectral radius），記作 rho(G)：G 的特徵值中絕對值最大的那個。乾淨的定理就是譜半徑收斂判準：當且僅當 rho(G) < 1 時，這個定常迭代對「每一個」起始猜測都收斂；而當 rho(G) > 1 時它發散。直覺是精確的——沿著每一個特徵方向，誤差每步都被那個特徵值乘一次，所以誤差只有在每個特徵值都嚴格落在單位圓內時才會死去。更棒的是，rho(G) 還決定了「速度」：每一步把誤差大致縮小 rho(G) 這個因子，所以 rho = 0.9 像爬行（你約需 22 步才換來一位小數），而 rho = 0.1 像衝刺（一步一位）。
SOR、殘量，與何時停手
如果 Gauss-Seidel 法總是把猜測往對的方向推，那為什麼不每一步「再多推一點」？那就是逐次超鬆弛（successive over-relaxation）：與其把 x_i 完全換成它的 Gauss-Seidel 值，不如取一個會衝過頭的加權混合，x_i_新 = (1 - w) x_i_舊 + w (Gauss-Seidel 值)，其中鬆弛因子 w 介於 1 與 2 之間。調到那個神奇的最佳 w 時，SOR能把一個要跑幾千趟掃描的方法，變成只要幾十趟——一個貨真價實、戲劇性的勝利。誠實的陷阱是：最佳的 w 取決於你通常事先不知道的譜半徑，一個糟糕的 w 可能不會比 Gauss-Seidel 好，而落在 (0, 2) 之外的 w 會直接發散。
你怎麼知道何時該收手？你沒辦法盯著誤差 e_n = x_n - x，因為你沒有真正的 x。你「能」算的，是殘量（residual）r_n = b - A x_n，它量度現在的猜測有多嚴重地不滿足那些方程式。殘量是你唯一誠實、可測量的回饋，所以一個實用的停止準則會盯著它：當相對殘量 ||b - A x_n||_2 / ||b||_2 掉到你設定的容忍度以下時就停手，比方說 1e-8。一個讓你保持誠實的告誡：小的殘量並「不」保證小的誤差。在一個病態的 A 上，誤差可能遠大於殘量所暗示的——條件數恰好就是從殘量到誤差的最壞情況放大倍率。
退一步看，這整個家族的極限就顯現出來了。Jacobi、Gauss-Seidel 與 SOR 都簡單、省記憶體、又對矩陣自由形式友善，但隨著問題變大，它們的譜半徑通常會悄悄爬向 1——把格點加細，rho 可能是 1 - O(h^2)，所以細網格上的迭代次數會爆炸。這正是為什麼接下來的指南要往前走：像共軛梯度法這樣的 Krylov 方法能從每一次矩陣乘向量裡榨出多得多的東西，而這些古老的定常迭代多半以多重網格裡的「平滑器」身分存活下來。無論如何都把它們學透——它們是你遇見拆分這個想法、以及每個後來的方法仍要向之負責的譜半徑的、最清楚的地方。