加治/数値計算の基礎/2章
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[加治/2010夏休み]]
&size(30){第2章 〜単一方程式の根};
#contents
*概要 [#h36e890c]
解の公式などでは解けなかったり、代数方程式は解けない、例えば$\cos x=x^2$といったように、普通の方法では解けそうもない方程式の解を、実数で少なくとも一つ求める方法。
*ニュートン法 [#yb5141e9]
**ニュートン法とは [#lcd54e8b]
微分を用いて方程式の解を数値的に求める方法の一つ。
**アルゴリズム [#b3016d3e]
#ref(newton_method.gif);
--根を求めたい方程式を$f(x)=0$という形に変形する。ここで$f(x)=0$は$x$の関数を意味する。&br;
ニュートン法は、関数$f(x)=0$の根が$y=f(x)$と$x$軸($y=0$)との交点であることを利用する。(ここで、根の一つを$\alpha$とする)
--任意の数$a$を方程式の近似値としてとる。関数$y=f(x)$を表す曲線上においてこの値に対応する点を$P$とすれば、$P$の座標は$(a,f(a))$となる。
--この点($(a,f(a))$)において曲線に接線を引き、その接線と$x$軸との交点を$Q$とする。
--この点$Q$の$x$座標を$b$としたとき、$b$はもとの$a$よりもよい近似値になっていると考えられる。
--そこでまた、点$Q$に対応する曲線上の点$R$において接線を引き、その接線と$x$軸との交点を$S$とする。
--$S$の座標値を$c$とすれば、$c$は$b$よりさらによい近似になる。
--以下、この手続きを続ければ、真の解$\alpha$にいくらでも近づくと考えられる。
-式の形で表すと・・・
--点$P$での接線の傾きは、
#tex(\frac{PA}{AQ}=\frac{f(a)-0}{a-b})
となる。
--一方、この接線の傾きを導関数を用いれば、$f'(a)$とも書ける。したがって、
#tex(f'(a)=\frac{f(a)-0}{a-b})
となり、
--この式を$b$について解けば&br;
&aname(formula114){formula114};
#tex(b=a-\frac{f(a)}{f'(a)})
が得られる。これがニュートン法の基礎式になる。
--ここで、ニュートン法のように、任意の値から始めて近似の制度を上げて徐々に真の値に近づけていく場合には、数列の形で根の近似値を表現するのが便利である。すなわち、この場合
#tex(a\to b\to c\to\cdots\to\alpha)
となる。このような時、$a,b,c,\cdots$という名前より、$x_0,x_1,x_2,\cdots$というように添字をつけた変数で書く。
--そうすると、$x_0$は''初期値''であり$x_1$は第1近似、$x_2$は第2近似、・・・となる。いま、$a$を$n$番目の第$n$近似、$b$を次の第$n+1$近似とすれば、[[formula114>数値計算の基礎#formula114]]は、&br;
&aname(formula115){formula115};
#tex(x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)})
となる。[[formula115>#formula115]]は、漸化式の形をしており、$n=0$からはじめて$n$をひとつずつ増加させながら右辺を計算することにより、
#tex(x_0\to x_1\to x_2\to\cdots);
の順に近似の精度が上がることになる。そこで、今後[[formula115>#formula115]]をニュートン法の基礎式とする。
**ニュートン法の注意 [#d8e7740f]
ニュートン法は初期値によって収束の速さが変わったり、また初期値によっては解が求まらないこともある。どうやって求めるんでしょうね。
*2分法 [#i5469f51]
ニュートン法は数々の利点を持っているため実際によく使われるが、最大の欠点として初期値によっては解が求まらないという点である。2分法は計算時間は多くかかるが確実に解が求まる方法である。
**アルゴリズム [#a9f1c8f6]
-はじめに2つの初期値を$a,b(a<b)$として&br;&aname(formula116){formula116};
#tex(f(a)f(b)<0);を満足するように選ぶ。&br;
この式は、$f(a)$と$f(b)$が異符号であることを意味しているため、曲線$y=f(x)$上の2点$(a,f(a))$,$(b,f(b))$は$x$軸をはさんで反対側にある→曲線が$x=a$、$x=b$の間のある点で少なくとも1回は$x$軸と交わる(中間値の定理)。これは根が$a$と$b$の間に少なくとも一つあることを意味する。
-$a$と$b$の中点を$c$とすれば、根は$a$と$c$の間か、または$c$と$b$の間に少なくとも一つある。((偶然に$c$が根であることもあり得るがその時はそれで計算が終了することになる。))&br;これはすなわち$f(a)f(c)<0$または$f(c)f(b)<0$のいずれかが成り立つことを意味している。
#ref(center.png);
-$f(a)f(c)<0$の場合は$c$を新たに$b$と見なし、$f(c)f(b)<0$の場合は$c$を新たに$a$と見なすことにすれば、[[formula116>#formula116]]と同じ状態になり、しかも区間の幅は半分になる。
-これらの手続きを繰り返せば、根の含まれている区間幅を限りなく0に近づけることができる。(実際には、計算誤差$\varepsilon$を指定し、区間幅がこの誤差以内になれば計算を打ち切れば良い。
**手順まとめ [#a87082a5]
+$f(a)f(b)<0$となるような$a,b(a<b)$を初期値にとる。(これはつまり、根をはさんで左右から絞っていくため)
+$c=(a+b)/2$とする。($a$と$b$の中点を$c$とするという意味)
+$b-a$があらかじめ指定した誤差より小さければ根を$c$とする。
+$f(a)f(c)<0$ならば、$c$を新たに$b$として2.に戻る。
+$f(c)f(b)<0$ならば、$c$を新たに$a$として2.に戻る。
-前提条件として、初期値$a$、$b$が見つかる事が2分法の前提条件となる。
**2分法の変形 [#s0c7e1b7]
2分法の変形として、2分法の中点$c$のかわりに、2点$a(,f(a))$と$(b,f(b))$を結ぶ直線と$x$軸の交点を$c$にとる方法もある。この2点を結ぶ直線は
#tex(y-f(a)=\frac{f(b)-f(a)}{b-a}(x-a))
であるから、$x$軸上では($y=0$で)
#tex(0-f(a)=\frac{f(b)-f(a)}{b-a}(c-a))
となる。したがって、
#tex(c=\frac{f(b)-bf(a)}{f(b)-f(a)})
となる。この法法の計算手順は2分法の計算手順の2.を
2'. $c=\frac{f(b)-bf(a)}{f(b)-f(a)}$
で置き換えるだけで、あとは全く同じである。
#ref(2bunhou_henkei.png);
-こちらの方法も、いつも2分法より高速に収束するとは限らず、逆に遅くなることもある。
----
#comment
終了行:
[[加治/2010夏休み]]
&size(30){第2章 〜単一方程式の根};
#contents
*概要 [#h36e890c]
解の公式などでは解けなかったり、代数方程式は解けない、例えば$\cos x=x^2$といったように、普通の方法では解けそうもない方程式の解を、実数で少なくとも一つ求める方法。
*ニュートン法 [#yb5141e9]
**ニュートン法とは [#lcd54e8b]
微分を用いて方程式の解を数値的に求める方法の一つ。
**アルゴリズム [#b3016d3e]
#ref(newton_method.gif);
--根を求めたい方程式を$f(x)=0$という形に変形する。ここで$f(x)=0$は$x$の関数を意味する。&br;
ニュートン法は、関数$f(x)=0$の根が$y=f(x)$と$x$軸($y=0$)との交点であることを利用する。(ここで、根の一つを$\alpha$とする)
--任意の数$a$を方程式の近似値としてとる。関数$y=f(x)$を表す曲線上においてこの値に対応する点を$P$とすれば、$P$の座標は$(a,f(a))$となる。
--この点($(a,f(a))$)において曲線に接線を引き、その接線と$x$軸との交点を$Q$とする。
--この点$Q$の$x$座標を$b$としたとき、$b$はもとの$a$よりもよい近似値になっていると考えられる。
--そこでまた、点$Q$に対応する曲線上の点$R$において接線を引き、その接線と$x$軸との交点を$S$とする。
--$S$の座標値を$c$とすれば、$c$は$b$よりさらによい近似になる。
--以下、この手続きを続ければ、真の解$\alpha$にいくらでも近づくと考えられる。
-式の形で表すと・・・
--点$P$での接線の傾きは、
#tex(\frac{PA}{AQ}=\frac{f(a)-0}{a-b})
となる。
--一方、この接線の傾きを導関数を用いれば、$f'(a)$とも書ける。したがって、
#tex(f'(a)=\frac{f(a)-0}{a-b})
となり、
--この式を$b$について解けば&br;
&aname(formula114){formula114};
#tex(b=a-\frac{f(a)}{f'(a)})
が得られる。これがニュートン法の基礎式になる。
--ここで、ニュートン法のように、任意の値から始めて近似の制度を上げて徐々に真の値に近づけていく場合には、数列の形で根の近似値を表現するのが便利である。すなわち、この場合
#tex(a\to b\to c\to\cdots\to\alpha)
となる。このような時、$a,b,c,\cdots$という名前より、$x_0,x_1,x_2,\cdots$というように添字をつけた変数で書く。
--そうすると、$x_0$は''初期値''であり$x_1$は第1近似、$x_2$は第2近似、・・・となる。いま、$a$を$n$番目の第$n$近似、$b$を次の第$n+1$近似とすれば、[[formula114>数値計算の基礎#formula114]]は、&br;
&aname(formula115){formula115};
#tex(x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)})
となる。[[formula115>#formula115]]は、漸化式の形をしており、$n=0$からはじめて$n$をひとつずつ増加させながら右辺を計算することにより、
#tex(x_0\to x_1\to x_2\to\cdots);
の順に近似の精度が上がることになる。そこで、今後[[formula115>#formula115]]をニュートン法の基礎式とする。
**ニュートン法の注意 [#d8e7740f]
ニュートン法は初期値によって収束の速さが変わったり、また初期値によっては解が求まらないこともある。どうやって求めるんでしょうね。
*2分法 [#i5469f51]
ニュートン法は数々の利点を持っているため実際によく使われるが、最大の欠点として初期値によっては解が求まらないという点である。2分法は計算時間は多くかかるが確実に解が求まる方法である。
**アルゴリズム [#a9f1c8f6]
-はじめに2つの初期値を$a,b(a<b)$として&br;&aname(formula116){formula116};
#tex(f(a)f(b)<0);を満足するように選ぶ。&br;
この式は、$f(a)$と$f(b)$が異符号であることを意味しているため、曲線$y=f(x)$上の2点$(a,f(a))$,$(b,f(b))$は$x$軸をはさんで反対側にある→曲線が$x=a$、$x=b$の間のある点で少なくとも1回は$x$軸と交わる(中間値の定理)。これは根が$a$と$b$の間に少なくとも一つあることを意味する。
-$a$と$b$の中点を$c$とすれば、根は$a$と$c$の間か、または$c$と$b$の間に少なくとも一つある。((偶然に$c$が根であることもあり得るがその時はそれで計算が終了することになる。))&br;これはすなわち$f(a)f(c)<0$または$f(c)f(b)<0$のいずれかが成り立つことを意味している。
#ref(center.png);
-$f(a)f(c)<0$の場合は$c$を新たに$b$と見なし、$f(c)f(b)<0$の場合は$c$を新たに$a$と見なすことにすれば、[[formula116>#formula116]]と同じ状態になり、しかも区間の幅は半分になる。
-これらの手続きを繰り返せば、根の含まれている区間幅を限りなく0に近づけることができる。(実際には、計算誤差$\varepsilon$を指定し、区間幅がこの誤差以内になれば計算を打ち切れば良い。
**手順まとめ [#a87082a5]
+$f(a)f(b)<0$となるような$a,b(a<b)$を初期値にとる。(これはつまり、根をはさんで左右から絞っていくため)
+$c=(a+b)/2$とする。($a$と$b$の中点を$c$とするという意味)
+$b-a$があらかじめ指定した誤差より小さければ根を$c$とする。
+$f(a)f(c)<0$ならば、$c$を新たに$b$として2.に戻る。
+$f(c)f(b)<0$ならば、$c$を新たに$a$として2.に戻る。
-前提条件として、初期値$a$、$b$が見つかる事が2分法の前提条件となる。
**2分法の変形 [#s0c7e1b7]
2分法の変形として、2分法の中点$c$のかわりに、2点$a(,f(a))$と$(b,f(b))$を結ぶ直線と$x$軸の交点を$c$にとる方法もある。この2点を結ぶ直線は
#tex(y-f(a)=\frac{f(b)-f(a)}{b-a}(x-a))
であるから、$x$軸上では($y=0$で)
#tex(0-f(a)=\frac{f(b)-f(a)}{b-a}(c-a))
となる。したがって、
#tex(c=\frac{f(b)-bf(a)}{f(b)-f(a)})
となる。この法法の計算手順は2分法の計算手順の2.を
2'. $c=\frac{f(b)-bf(a)}{f(b)-f(a)}$
で置き換えるだけで、あとは全く同じである。
#ref(2bunhou_henkei.png);
-こちらの方法も、いつも2分法より高速に収束するとは限らず、逆に遅くなることもある。
----
#comment
ページ名: