方程式の根の近似計算

一変数の方程式$f(x)=0$の根の計算法を考えます。

ニュートン法

ニュートン法によって、方程式の近似解を計算することができます。

ニュートン法では、初期値$x_0$をスタートして、$f(x)=0$の解$x$に近づく数列$\{x_n\}$を作ります。 すなわち、

$$ x_0, x_1, x_2, \cdots \rightarrow x $$

1. アイデア

まず初めに、予想される真の解に近いと思われる値(初期値$x_0$)をひとつ取ります。

次に、$x_0$におけるグラフの切線と$x$軸の交差点を考えます。この交差点の値は、予想される真の解により近いものとなるのが一般と思われます。以後、この値に対してそこでグラフの切線を考え、同じ操作を繰り返していきます。

以下の計算手順の概念図では、青い線が関数 $f$ のグラフで、その切線を赤で示しています. $x_n$ よりも$x_{n+1}$ のほうが、 $f(x)=0$ の解 x についてのよりよい近似を与えています。

ニュートン法の一手順の概念図 (青い線が関数 f のグラフで、その接線を赤で示した). xn よりも xn+1 のほうが、 f(x)=0 の解 x についてのよりよい近似を与えている.(引用:Wikipedia)

ニュートン法の一手順の概念図

2. 定式化

良さそうな初期値$x_0$から、以下の反復式によって、真の解に収束しているような数列$\{x_n\}$を計算するのは可能です。

$$ x_{n} = x_{n-1} - \frac{ f(x_{n-1}) }{ f^{(1)}(x_{n-1}) } \quad (n\ge 1) $$

ここで、$f^{(1)}(x_{n-1})$は$x_{n-1}$における関数$f$の微分です。

3. 計算例

$\sqrt{2}$を算出するために、$f(x)=x^2-2$の解を求めることを考えます。

$$ x^2-2=0 $$

まず, 区間$[0,2]$上の$y=f(x)$のグラフを描きます。

この$f$について、ニュートン法の反復計算式は以下のようになります。 $$ x_{n} = x_{n-1} - \frac{ x_{n-1}^2-2 }{2 x_{n-1}} =\frac{1}{2} (x_{n-1} + \frac{2}{x_{n-1}} ) $$

次に、初期値$x_0=1$をスタートして、数列$x_n$を計算します。

演習1 

上記の反復計算では、近似解の数列が得られます。

例えば、以下のfor文によって、N回反復精算することができます。

N=5;
x0=1;
x=[x0];
for k=2:N
  x(k) = 0.5 * ( x(k-1) + 2/x(k-1))
end

実際の計算では、以下の終了条件も使用されます。

$$ |x_n - x_{n-1}|\le 10^{-12} $$

このとき、while文を使って反復計算するのはおすすめです。

また、反復計算では、x_new, x_old二つの変数のみを使って、計算することが可能です。

4. 収束オーダーの計算方法

$p$ を$f(x)=0$の解または精度の良い近似解とする。反復回数$n$が十分大きい時,反復計算で得られる数列$\{p_i\}$が以下の式を満たすことは考えられる。

$$ \frac{| p_n - p|}{|p_{n-1} - p |^{\alpha}} \approx \frac{| p_{n-1} - p|}{|p_{n-2} - p |^{\alpha}} \approx \lambda $$

ここで、$\lambda$は収束の定数である。

よって,$n\ge 2$のとき,次の式で収束オーダー $\alpha$ を計算できる。一般的に,$n$が大きい時,$\alpha$の計算結果が一定の値となる。

$$ \alpha \approx \frac{ \log (| p_{n-1} - p | / | p_n - p | )}{ \log (| p_{n-2} - p | / | p_{n-1} - p | ) } $$

演習2

以下のレポート課題を解いてください。

http://www.ces-alpha.org/download/gs/?label=F6&conf_id=NAP2020&verify=b6277

計算結果を以下の表にまとめるのはおすすめ。(CELLをクリックして、ソースコードを確認してください。)

$i$ Newton method Order
$0$ $p_0=0.2$ -
$1$ $p_1=?$ -
$2$ $p_2=?$ $\alpha=?$ ($p_0$, $p_1$, $p_2$から $\alpha$を計算する)
$3$ $p_3=?$ $\alpha=?$ ($p_1$, $p_2$, $p_3$から $\alpha$を計算する)