反復計算における収束判定について

収束判定

漸化式
\begin{equation}
x^{(k+1)}=x^{(k)}+\Delta^{(k)}
\end{equation}
に従って、\(\lim_{k\to\infty}x^{(k)}=a\)が適当な定数に収束する問題を考えます。
絶対誤差\(\varepsilon_A\)、相対誤差\(\varepsilon_R\)とすると、数値計算を終了する時は、以下の不等式が満たされる時にすると良いです。
\begin{equation}
|x^{(k+1)}-x^{(k)}|\lt \varepsilon_A + \varepsilon_R(|x^{(k)}|+|x^{(k+1)}|)
\end{equation}

判定式の意味

上記判定式の意味を考えましょう。上の判定式は絶対誤差による評価と相対誤差による評価をまとめて評価する式になっています。

相対誤差が重要な場合

本当の解が\(a=100\)であるとします。その時、\(x^{(k)}=100.3, x^{(k+1)}=100.2\)であったと仮定すると、大雑把に計算して
\begin{align}
|x^{(k+1)}-x^{(k)}| &\lt \varepsilon_A + \varepsilon_R(|x^{(k)}|+|x^{(k+1)}|) \\
0.1 &\lt \varepsilon_A + \varepsilon_R\times 100
\end{align}
となります。右辺は本来2倍ですが、2倍はそんなに重要ではないので無視しています。もし仮に、\(\varepsilon\equiv\varepsilon_A=\varepsilon_R\)としていれば、
\begin{align}
0.1 &\lt 100\varepsilon_R
\end{align}
と近似できます。以上から、本当の解が1より十分大きい場合、相対誤差で収束を評価する式になっていると言えます。
つまり上記の問題設定の場合、\(\varepsilon_R\gt 10^{-3}\)にしてあれば”収束した”として判定します。

絶対誤差が重要な場合

本当の解が\(a=0.01000\)であるとします。その時、\(x^{(k)}=0.01002, x^{(k+1)}=0.01001\)であったと仮定すると、大雑把に計算して
\begin{align}
|x^{(k+1)}-x^{(k)}| &\lt \varepsilon_A + \varepsilon_R(|x^{(k)}|+|x^{(k+1)}|) \\
0.00001 &\lt \varepsilon_A + \varepsilon_R\times 0.01
\end{align}
となります。右辺は本来2倍ですが、2倍はそんなに重要ではないので無視しています。もし仮に、\(\varepsilon\equiv\varepsilon_A=\varepsilon_R\)としていれば、
\begin{align}
0.00001 &\lt 0.01\varepsilon_A
\end{align}
と近似できます。以上から、本当の解が1より十分小さい場合、絶対誤差で収束を評価する式になっていると言えます。
つまり上記の問題設定の場合、\(\varepsilon_A\gt 10^{-3}\)にしてあれば”収束した”として判定します。