ニュートン法の解説とそれを背景とする入試問題

更新日時 2021/08/17

ニュートン法(Newton’s method)は,方程式の解を高速に計算するアルゴリズムである。

ニュートン法と呼ばれるアルゴリズムに関連した入試問題とその背景を解説します。

目次
  • ニュートン法に関連する極限の問題

  • 接線を考える

  • ニュートン法のアルゴリズムまとめ

ニュートン法に関連する極限の問題

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

例題

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

方針

漸化式で表される数列の極限は,まず不動点を求めてから不等式を作ってはさみうちの原理を用いるという手順で解きます。詳しくは→漸化式で表される数列の極限

二項間漸化式を解くのに似た手法で不等式を作り出します。

解答

α=12(α+2α)\alpha=\dfrac{1}{2}\left(\alpha+\dfrac{2}{\alpha}\right) を解くと,α=2\alpha=\sqrt{2} となる。もとの漸化式と辺々引き算して,

an+1α=12(anα)+(1an1α)a_{n+1}-\alpha=\dfrac{1}{2}(a_n-\alpha)+\left(\dfrac{1}{a_n}-\dfrac{1}{\alpha}\right)

ここで任意の nn に対して,an>α=2a_n > \alpha=\sqrt{2} であることが帰納的に分かる(注)ので,1an1α<0\dfrac{1}{a_n}-\dfrac{1}{\alpha} <0 であり,

an+1α<12anα|a_{n+1}-\alpha| <\dfrac{1}{2}|a_n-\alpha|

という不等式を得る。

この不等式を繰り返し用いてはさみうちの原理を用いると,limnan=2\displaystyle\lim_{n\to\infty}a_n=\sqrt{2}

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

接線を考える

上記の問題の背景を解説します。

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

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

x=12(a+2a)x=\dfrac{1}{2}\left(a+\dfrac{2}{a}\right) となります。

ニュートン法

つまり,さきほどの漸化式 an+1=12(an+2an)a_{n+1}=\dfrac{1}{2}\left(a_n+\dfrac{2}{a_n}\right) は,点 AA に対して点 BB を対応させるような変換を表しています。より正確に述べると 数列を a1,a2a_1,a_2\cdots と順番に求めていくのは「放物線に代入して接線を引いて xx 軸との交点を求める」操作を繰り返すことに対応しているわけです。

α=2\alpha=\sqrt{2} に収束するのは図形的に当然ですね。(ただし,初期値が 2\sqrt{2} より大きい場合)

ニュートン法のアルゴリズムまとめ

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

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

実際に,一般の関数 f(x)f(x) に対してニュートン法を適用して漸化式を導出してみると:

ニュートン法の漸化式

y=f(x)y=f(x)(a,f(a))(a,f(a)) における接線の方程式は,yf(a)=f(a)(xa)y-f(a)=f'(a)(x-a) であり,接線と xx 軸の交点の xx 座標は,

x=af(a)f(a)x=a-\dfrac{f(a)}{f'(a)} となります。

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

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