2014/05/23

入試問題の背景としてのニュートン法

分野: 極限,微分  レベル: 最難関大学

ニュートン法は,コンピュータを用いて方程式の解を高速に計算する手法

頻出の極限の問題

ニュートン法について解説する前に,まずは以下の頻出問題について考えます。

初期値 $a_1=2$ と漸化式 $a_{n+1}=\dfrac{1}{2}(a_n+\dfrac{2}{a_n})$ で表される数列の極限を求めよ

方針:漸化式で表される数列の極限は,まず不動点を求めてから不等式を作ってはさみうちの原理を用いるという手順で解きます。詳しくは→漸化式で表される数列の極限
二項間漸化式を解くのに似た手法で不等式を作り出します。

解答

$\alpha=\dfrac{1}{2}(\alpha+\dfrac{2}{\alpha})$ を解くと,$\alpha=\sqrt{2}$ となる。もとの漸化式と辺々引き算して,
$a_{n+1}-\alpha=\dfrac{1}{2}(a_n-\alpha)+(\dfrac{1}{a_n}-\dfrac{1}{\alpha})$
ここで任意の $n$ に対して,$a_n > \alpha=\sqrt{2}$ であることが帰納的に分かる(注)ので,$\dfrac{1}{a_n}-\dfrac{1}{\alpha} <0$ であり,
$|a_{n+1}-\alpha| <\dfrac{1}{2}|a_n-\alpha|$
というご所望の不等式を得る。
この不等式を繰り返し用いてはさみうちの原理を用いると,$\displaystyle\lim_{n\to\infty}a_n=\sqrt{2}$

注:この不等式を自力で思いつくのは難しいので実際の問題ではたいてい誘導がついています。しかし,以下のニュートン法の解説で分かるように $a_{n} > \alpha$ が成立するのは自然な事実です。

接線を考える

上記の問題の背景を解説します。
実は方程式 $x^2-2=0$ の解をコンピュータを用いて高速に求める方法を適用すると上記の漸化式が出現します。(コンピュータは基本的に無理数は扱えないので $\sqrt{2}$ に近い有理数を計算します。)

そこで,突然ですが,$y=x^2-2$ という放物線上の点$(a,a^2-2)$ における接線の方程式を求めると,$y=2ax-a^2-2$ となります。これと $x$ 軸の交点の $x$ 座標は,
$x=\dfrac{1}{2}(a+\dfrac{2}{a})$ となります。

ニュートン法

つまり,上記の漸化式は点 $A$ に対して点 $B$ を対応させるような変換を表しています。より正確に述べると数列を $a_1,a_2\cdots$ と順番に求めていくのは「放物線に代入して接線を引いて $x$ 軸との交点を求める」操作を繰り返すことに対応しているわけです。
$\alpha=\sqrt{2}$ に収束するのは図形的に当然ですね。(ただし,初期値が $\sqrt{2}$ より大きい場合)

ニュートン法

上記では $y=x^2-2$ にニュートン法を用いて方程式 $x^2-2=0$ の解を計算する方法を与えましたが,同様にして,(ある程度性質のよい関数なら)いろいろな関数 $f(x)$ に対して $f(x)=0$ の解を計算することができます。つまり,ニュートン法を用いれば代数的に解けない方程式もコンピュータを用いて近似値を求めることができるのです!

しかも,ニュートン法は収束がとてもはやい(二次収束と呼ばれる)ので複雑な方程式も短時間で近似値を求めることができます。

実際に一般の関数 $f(x)$ に対してニュートン法を適用して漸化式を導出してみます:
$y=f(x)$ の$(a,f(a))$ における接線の方程式は,$y-f(a)=f'(a)(x-a)$ であり,接線と $x$ 軸の交点の $x$ 座標は,
$x=a-\dfrac{f(a)}{f'(a)}$ となる。

ニュートン法を背景とした入試問題は思いのほか多いようです。

Tag: いろいろな方程式の解き方まとめ

分野: 極限,微分  レベル: 最難関大学