收斂速率

收斂速率是一個迭代過程逼近其極限的速度——誤差縮小的快慢。這個詞有兩種密切相關的用法，值得分清。廣義上它就是「多快」，涵蓋階（誤差每步是平方還是只是縮放）以及，對給定的階，乘上誤差的那個常數因子。在常被「速率」一詞指稱的狹義、技術意義上，它是線性收斂中的漸近常數：滿足 e_{n+1} 約等於 C 乘以 e_n 的因子 C，其中 C 越小越快。

對線性收斂的方法，速率就是一切，因為階固定為 1，只有收縮因子能區分快方法與爬行方法。若誤差每步乘以 C，則 k 步後約為起點的 C^k 倍，你每次迭代約獲得 -log10(C) 個十進位數：C = 0.5 每步約獲得 0.30 位，C = 0.1 每步獲得整整一位，而 C = 0.99 則爬行，須約 230 步才獲得一位。許多基本方法是線性的，其成敗繫於這個常數——雅可比與高斯-賽德爾迭代以其迭代矩陣譜半徑 rho 設定的速率收斂，而最速下降法隨條件數增大而變慢。

收斂速率重要，因為它直接換算成迭代次數、進而換算成成本。它也是預條件所拉動的槓桿：好的預條件子不改變方法的階，卻縮小其有效速率常數（對共軛梯度法則是縮小控制它的條件數），把數百次迭代變成少數幾次。與階一樣，速率是漸近、局部的描述——它告訴你迭代安頓進其階段後最終的速度，未必是最初幾步的不規則行為。