加治/数値計算の基礎/1章
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[加治/2010夏休み]]
&size(30){第1章〜数値計算の基礎〜};
#contents
*アルゴリズム [#ff8212e2]
-数学的には同じ答えを得られる計算であっても計算の方法を工夫することにより計算量を減らすことが出来ることがある。
**例1 $x^{32}$の計算 [#d914d75d]
普通に計算すれば
#texvc($x \times x \times \cdots \times x$)
と言うように$x$を31回掛け算することになる。しかし、
#texvc($a = x^2$)
とおき、同様に
#texvc($b = a^2(=x^4)\\c=b^2(=x^8)\\d=c^2(=x^{16})\\e=d^2(=x^{32})$)
と計算すれば、掛け算は5回で済む。
**例2 多項式の計算 [#yb83c250]
#texvc($y_4=a_0x^4+a_1x^3+a_2x^2+a_3x+a_4$)
の右辺を計算することを考える。通常この計算には10回の掛け算(4+3+2+1)と4回の足し算が必要となる。ただし、$x^4$を計算するときに、既に計算してある$x^3$,$x^4$の値を利用すれば、掛け算の回数は(4+1+1+1)(($x^2$の計算は$x\times x$、$x^3$の計算は$x^2\times x$、$x^4$の計算は$x^2\times x^2$ or $x^3\times x$だから、掛け算の回数は(2+2+2+1)じゃないの?))の7回で済む。
また、上式は
#texvc($y_1 = a_0x + a_1\\y_2 = y_1x + a_2\\y_3 = y_2x + a_3\\y_4 = y_3x + a_4$)
という計算に分解できる。このことは上から順に代入することにより確かめられる。ここで、それぞれの式では1回の掛け算と1回の足し算を行っているため、合計4回の掛け算と4回の足し算で計算できる。
これらの例ではある数値を計算するために2つの計算法を比較した。一般的に、目的となる数値を得るために行う一連の計算方法をアルゴリズムとよんでいるが、上の例のように同一の結果を得るアルゴリズムは一つではない。計算量の観点から言えば、上の2つの例では後に述べたものの方が優れていると言える。
**ここまでのまとめ [#i89ce76d]
-計算結果は同じものであってもアルゴリズムが違えば計算量、計算効率などは異なる。対象計算に対して最適なアルゴリズムを考えることが重要と言える。
*漸化式と反復法 [#u22cf40e]
[[前節の2番目の例>#yb83c250]]を一般化して$n$次多項式
#texvc($y_n = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + \cdots + a_{n-1}x + a_n$)
の値を求める問題を考える。この場合も
#texvc($y_1 = a_0x + a_1\\y_2 = y_1x + a_2 \\\vdots\\y_n = y_{n-1}x + a_n$)
とおき、上から順に$y_1,y_2,\cdots,y_n$を計算していけばよい。この手続きは、以下のようにまとめられる。
$y_0 = a_0$とおく。&br;
$i = 1,2,\cdots,n$の順に次式を計算する:
&aname(formular110){formula110};
#texvc($y_i = y_{i-1}x + a_i$)
これが多項式の値を求めるひとつのアルゴリズムである。
$y_i$を数列と考えたとき、[[formula110>#formula110]]のように数列の近接の項間に関係式が与えられた場合、その関係式を''漸化式''と言う。漸化式は数値計算ではいたるところに現れる。
**漸化式の応用例 [#u5d87fd7]
漸化式の応用例として、2次方程式&br;
&aname(formula112){formula112};
#texvc($x^2-x-1=0$)
を考える.この方程式は
#texvc($x=1+\frac{1}{x}$)
と変形できる。そこで、この式から漸化式&br;
&aname(formula113){formula113};
#texvc($x_{n+1}=1+\frac{1}{x_i}$)
をつくってみよう。((上記の式からなぜこの漸化式の形に変形できるのか分からない・・・))そして、$x_0=1$からはじめて、$x_0$,$x_1$,$x_2$,$\cdots$を計算すると
#texvc(1,2,1.5,1.667,1.6250,1.6154,1.6190,1.6176,\cdots)
となる.
この数列から、上の漸化式の値はある''一定の数''に近づくことが予想できる。
一定の数は元の方程式
#texvc($x^2-x-1=0$)
のひとつの根
#texvc(\alpha=\frac{1+\sqrt{5}}{2}=1.6181\cdots)
である。なぜなら、一定値$\alpha$に落ち着いたとすれば、漸化式の右辺の$x_i$も左辺の$x_i$もともに$\alpha$となるため、$\alpha$は方程式
#texvc(\alpha=1+\frac{1}{\alpha})
を満足するからである。逆に言えば、[[formula113>#formula113]]は、2次方程式[[formula112>#formula112]]の根を求める一つの方法になっている。この様に漸化式を利用して方程式の根を求める方法を''反復法''とよぶ。また、反復法に利用される漸化式を特に''反復式''とよんでいる。
方程式[[formular112>#formula112]]を解く反復式は一通りではなく、式を変形したりして反復法を適用すると答えは一緒になっても収束速度などに違いが出てくる。
**誤差 [#i1383b39]
コンピュータでは最終的に状態を1と0で状態や数値を区別する。その際、コンピューターは無限桁の計算ができるわけではないので、数値は有限の桁で表される。一方、実数を少数で表したとき無限桁になることが普通であり、0.1のように、たとえ10進数では有限桁の数であっても2進数では無限桁になってしまうこともある。その際、表現しきれない桁に対しては切り捨てや四捨五入が行われる。つまり、必然的に誤差が入る。
-''丸め誤差''&br;
上の様に、本来無限桁の数を有限桁で表現するために生じる誤差を丸め誤差という。
-''打ち切り誤差''&br;
コンピュータは、三角関数や指数関数など本来は四則演算で計算できない値を求めるときに、これらの関数を四則演算で計算可能な近似式で代用している。具体的には多項式を用いることが多いが、その場合、数学的には無限の項を持った多項式を用いないと正確には一致しない.
一方、コンピュータでは無限項の計算はできないため、有限項で打ちきってしまう。この時必然的に誤差が生じるが、子のような誤差を打ち切り誤差とよんでいる。
-''情報落ち''&br;
大きさが極端に違う2数の加減を行うとき、小さな数が無視される現象を情報落ちという。
-''桁落ち''&br;
ほぼ等しい2つの数の差を計算したとき、有効数字のほとんどが失われる現象を桁落ちとよんでいる。桁落ちは数値計算でもっとも注意しなければならない現象の一つである。
-''対策''&br;
これらの誤差により、計算結果が、期待していたものと大きく外れてしまう可能性もあるため、なるべく誤差を小さく止めるようなアルゴリズムを用いて計算する必要がある。
----
#comment
終了行:
[[加治/2010夏休み]]
&size(30){第1章〜数値計算の基礎〜};
#contents
*アルゴリズム [#ff8212e2]
-数学的には同じ答えを得られる計算であっても計算の方法を工夫することにより計算量を減らすことが出来ることがある。
**例1 $x^{32}$の計算 [#d914d75d]
普通に計算すれば
#texvc($x \times x \times \cdots \times x$)
と言うように$x$を31回掛け算することになる。しかし、
#texvc($a = x^2$)
とおき、同様に
#texvc($b = a^2(=x^4)\\c=b^2(=x^8)\\d=c^2(=x^{16})\\e=d^2(=x^{32})$)
と計算すれば、掛け算は5回で済む。
**例2 多項式の計算 [#yb83c250]
#texvc($y_4=a_0x^4+a_1x^3+a_2x^2+a_3x+a_4$)
の右辺を計算することを考える。通常この計算には10回の掛け算(4+3+2+1)と4回の足し算が必要となる。ただし、$x^4$を計算するときに、既に計算してある$x^3$,$x^4$の値を利用すれば、掛け算の回数は(4+1+1+1)(($x^2$の計算は$x\times x$、$x^3$の計算は$x^2\times x$、$x^4$の計算は$x^2\times x^2$ or $x^3\times x$だから、掛け算の回数は(2+2+2+1)じゃないの?))の7回で済む。
また、上式は
#texvc($y_1 = a_0x + a_1\\y_2 = y_1x + a_2\\y_3 = y_2x + a_3\\y_4 = y_3x + a_4$)
という計算に分解できる。このことは上から順に代入することにより確かめられる。ここで、それぞれの式では1回の掛け算と1回の足し算を行っているため、合計4回の掛け算と4回の足し算で計算できる。
これらの例ではある数値を計算するために2つの計算法を比較した。一般的に、目的となる数値を得るために行う一連の計算方法をアルゴリズムとよんでいるが、上の例のように同一の結果を得るアルゴリズムは一つではない。計算量の観点から言えば、上の2つの例では後に述べたものの方が優れていると言える。
**ここまでのまとめ [#i89ce76d]
-計算結果は同じものであってもアルゴリズムが違えば計算量、計算効率などは異なる。対象計算に対して最適なアルゴリズムを考えることが重要と言える。
*漸化式と反復法 [#u22cf40e]
[[前節の2番目の例>#yb83c250]]を一般化して$n$次多項式
#texvc($y_n = a_0x^n + a_1x^{n-1} + a_2x^{n-2} + \cdots + a_{n-1}x + a_n$)
の値を求める問題を考える。この場合も
#texvc($y_1 = a_0x + a_1\\y_2 = y_1x + a_2 \\\vdots\\y_n = y_{n-1}x + a_n$)
とおき、上から順に$y_1,y_2,\cdots,y_n$を計算していけばよい。この手続きは、以下のようにまとめられる。
$y_0 = a_0$とおく。&br;
$i = 1,2,\cdots,n$の順に次式を計算する:
&aname(formular110){formula110};
#texvc($y_i = y_{i-1}x + a_i$)
これが多項式の値を求めるひとつのアルゴリズムである。
$y_i$を数列と考えたとき、[[formula110>#formula110]]のように数列の近接の項間に関係式が与えられた場合、その関係式を''漸化式''と言う。漸化式は数値計算ではいたるところに現れる。
**漸化式の応用例 [#u5d87fd7]
漸化式の応用例として、2次方程式&br;
&aname(formula112){formula112};
#texvc($x^2-x-1=0$)
を考える.この方程式は
#texvc($x=1+\frac{1}{x}$)
と変形できる。そこで、この式から漸化式&br;
&aname(formula113){formula113};
#texvc($x_{n+1}=1+\frac{1}{x_i}$)
をつくってみよう。((上記の式からなぜこの漸化式の形に変形できるのか分からない・・・))そして、$x_0=1$からはじめて、$x_0$,$x_1$,$x_2$,$\cdots$を計算すると
#texvc(1,2,1.5,1.667,1.6250,1.6154,1.6190,1.6176,\cdots)
となる.
この数列から、上の漸化式の値はある''一定の数''に近づくことが予想できる。
一定の数は元の方程式
#texvc($x^2-x-1=0$)
のひとつの根
#texvc(\alpha=\frac{1+\sqrt{5}}{2}=1.6181\cdots)
である。なぜなら、一定値$\alpha$に落ち着いたとすれば、漸化式の右辺の$x_i$も左辺の$x_i$もともに$\alpha$となるため、$\alpha$は方程式
#texvc(\alpha=1+\frac{1}{\alpha})
を満足するからである。逆に言えば、[[formula113>#formula113]]は、2次方程式[[formula112>#formula112]]の根を求める一つの方法になっている。この様に漸化式を利用して方程式の根を求める方法を''反復法''とよぶ。また、反復法に利用される漸化式を特に''反復式''とよんでいる。
方程式[[formular112>#formula112]]を解く反復式は一通りではなく、式を変形したりして反復法を適用すると答えは一緒になっても収束速度などに違いが出てくる。
**誤差 [#i1383b39]
コンピュータでは最終的に状態を1と0で状態や数値を区別する。その際、コンピューターは無限桁の計算ができるわけではないので、数値は有限の桁で表される。一方、実数を少数で表したとき無限桁になることが普通であり、0.1のように、たとえ10進数では有限桁の数であっても2進数では無限桁になってしまうこともある。その際、表現しきれない桁に対しては切り捨てや四捨五入が行われる。つまり、必然的に誤差が入る。
-''丸め誤差''&br;
上の様に、本来無限桁の数を有限桁で表現するために生じる誤差を丸め誤差という。
-''打ち切り誤差''&br;
コンピュータは、三角関数や指数関数など本来は四則演算で計算できない値を求めるときに、これらの関数を四則演算で計算可能な近似式で代用している。具体的には多項式を用いることが多いが、その場合、数学的には無限の項を持った多項式を用いないと正確には一致しない.
一方、コンピュータでは無限項の計算はできないため、有限項で打ちきってしまう。この時必然的に誤差が生じるが、子のような誤差を打ち切り誤差とよんでいる。
-''情報落ち''&br;
大きさが極端に違う2数の加減を行うとき、小さな数が無視される現象を情報落ちという。
-''桁落ち''&br;
ほぼ等しい2つの数の差を計算したとき、有効数字のほとんどが失われる現象を桁落ちとよんでいる。桁落ちは数値計算でもっとも注意しなければならない現象の一つである。
-''対策''&br;
これらの誤差により、計算結果が、期待していたものと大きく外れてしまう可能性もあるため、なるべく誤差を小さく止めるようなアルゴリズムを用いて計算する必要がある。
----
#comment
ページ名: