２００４年度・数理解析・計算機数学２・第４回 1
● 前回の講義のまとめ
• （代数）方程式の解を求めるための方法として, 以下の２つを考察した.
1. 区間縮小法（二分法）
2. ニュートン法（逐次近似）
• 区間縮小法は「中間値の定理」を応用したものであり , 連続な関数 f : R −→ R に対して , f (a) < 0, f (b) > 0, f
(x) > 0 on [a, b] をみたすとき, f (x) = 0 の区間 (a, b) での唯一の解 α を求める方法で ある .
• Newton 法は , なめらかなな関数 f : R −→ R に対して , f (a) < 0, f (b) > 0, f
(x) > 0 on [a, b], f
(x) < 0 on (a, b) をみたすとき, f (x) = 0 の区間 (a, b) での唯一の解 α を求める方法である.
• Newton 法は x
n+1= ϕ(x
n) に従う「逐次近似」と考えられる. （Newton 法では ϕ(x) = x−f (x)/f
(x) である.）この逐次近似は, α = ϕ(α) をみたす α に対して（これが逐次近似の収束先の候補） |ϕ
(α)| < 1 をみたすときに収束し,
|x
n+1− α| ≤ |ϕ
(α)| |x
n− α| + |ϕ
(α)|
2 |x
n− α|
2+ O(|x
n− α|
3) をみたす.
特に Newton 法で, 解が単根のとき（f
(α) = 0 のとき）,
|x
n+1− α| ≤ |f
(α)|
2|f
(α)| |x
n− α|
2となり , 二次収束する .
解が m 重根（f
(α) = · · · = f
(m)(α) = 0 のとき）
|x
n+1− α| ≤ m − 1
m |x
n− α|
となり, 一次収束する.
● 講義資料
【多角形近似による π の計算】
半径 1 の円に内接する正 n 角形の周長を {n}, 外接する正 n 角形の周長を {L
n} とすると, それら の間には次の関係式が成り立つ.
2n
= 2n
1 −
1 − (
n/n)
22 , (1)
L
2n= 2n
2L
n−1 +
1 + (L
n/n)
2(2) 特に,
L
2n=
nL
n2(
n+ L
n) (3)
が成り立つ.
ex04.tex,v 1.3 2004-10-21 15:01:32+09 naito Exp
2 ２００４年度・数理解析・計算機数学２・第４回
(1), (2)
で求めた結果6 3.000000000000 1.415926535898e-01 3.464101615138 3.225089615480e-01 12 3.105828541230 3.576411235954e-02 3.215390309173 7.379765558368e-02 24 3.132628613281 8.964040308556e-03 3.159659942097 1.806728850770e-02 48 3.139350203047 2.242450542921e-03 3.146086215131 4.493561541609e-03 96 3.141031950891 5.607026992633e-04 3.142714599645 1.121946055519e-03 192 3.141452472285 1.401813044488e-04 3.141873049980 2.803963903339e-04 384 3.141557607912 3.504567817103e-05 3.141662747055 7.009346501397e-05 768 3.141583892149 8.761440857263e-06 3.141610176600 1.752300998925e-05 1536 3.141590463237 2.190353031395e-06 3.141597034323 4.380733283238e-06 3072 3.141592106043 5.475467448335e-07 3.141593748817 1.095227323500e-06 6144 3.141592516588 1.370016384783e-07 3.141592927873 2.742835794045e-07 12288 3.141592618641 3.494900369105e-08 3.141592725623 7.203305862902e-08 24576 3.141592645321 8.268577378345e-09 3.141592671741 1.815149142104e-08 49152 3.141592645321 8.268577378345e-09 3.141592618901 3.468864662182e-08 98304 3.141592645321 8.268577378345e-09 3.141592671741 1.815149142104e-08 196608 3.141592645321 8.268577378345e-09 3.141591935882 7.177075596054e-07 393216 3.141593669849 1.016259633779e-06 3.141592671741 1.815149142104e-08 786432 3.141592303812 3.497780554085e-07 3.141581007580 1.164601016823e-05 1572864 3.141608696225 1.604263501065e-05 3.141592671741 1.815149142104e-08 3145728 3.141586839655 5.813934751853e-06 3.141406154738 1.864988519102e-04 6291456 3.141674265022 8.161143196439e-05 3.140543492401 1.049161188954e-03 12582912 3.141674265022 8.161143196439e-05 3.140006864691 1.585788898564e-03 25165824 3.143072740170 1.480086580246e-03 3.134945375659 6.647277931202e-03 50331648 3.159806164941 1.821351135134e-02 3.140006864691 1.585788898564e-03 100663296 3.181980515339 4.038786174967e-02 3.224515243535 8.292258994476e-02 201326592 3.354101966250 2.125093126599e-01 2.791117213059 3.504754405309e-01
(1), (3)
で求めた結果6 3.000000000000 1.415926535898e-01 3.464101615138 3.225089615480e-01 12 3.105828541230 3.576411235954e-02 3.215390309173 7.379765558368e-02 24 3.132628613281 8.964040308556e-03 3.159659942098 1.806728850771e-02 48 3.139350203047 2.242450542921e-03 3.146086215131 4.493561541641e-03 96 3.141031950891 5.607026992633e-04 3.142714599645 1.121946055577e-03 192 3.141452472285 1.401813044488e-04 3.141873049980 2.803963900422e-04 384 3.141557607912 3.504567817103e-05 3.141662747057 7.009346700260e-05 768 3.141583892149 8.761440857263e-06 3.141610176605 1.752301475211e-05 1536 3.141590463237 2.190353031395e-06 3.141597034322 4.380731969622e-06 3072 3.141592106043 5.475467448335e-07 3.141593748776 1.095186032973e-06 6144 3.141592516588 1.370016384783e-07 3.141592927409 2.738194293528e-07 12288 3.141592618641 3.494900369105e-08 3.141592721999 6.840888167048e-08 24576 3.141592645321 8.268577378345e-09 3.141592670320 1.672993787949e-08 49152 3.141592645321 8.268577378345e-09 3.141592657820 4.230679806483e-09 98304 3.141592645321 8.268577378345e-09 3.141592651571 2.018949007976e-09 196608 3.141592645321 8.268577378345e-09 3.141592648446 5.143763193161e-09 393216 3.141593669849 1.016259633779e-06 3.141592646884 6.706170285753e-09 786432 3.141592303812 3.497780554085e-07 3.141593158366 5.047766484800e-07 1572864 3.141608696225 1.604263501065e-05 3.141592731089 7.749923858213e-08 3145728 3.141586839655 5.813934751853e-06 3.141600713637 8.060046841507e-06 6291456 3.141674265022 8.161143196439e-05 3.141593776631 1.123040727080e-06 12582912 3.141674265022 8.161143196439e-05 3.141634020311 4.136672081900e-05 25165824 3.143072740170 1.480086580246e-03 3.141654142537 6.148894750746e-05 50331648 3.159806164941 1.821351135134e-02 3.142363281250 7.706276599238e-04 100663296 3.181980515339 4.038786174967e-02 3.151060584250 9.467930659948e-03 201326592 3.354101966250 2.125093126599e-01 3.166445069301 2.485241571103e-02
ex04.tex,v 1.3 2004-10-21 15:01:32+09 naito Exp
２００４年度・数理解析・計算機数学２・第４回 3
1e-09 1e-08 1e-07 1e-06 1e-05 0.0001 0.001 0.01 0.1 1
1 10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09
"0_1_1.error"
"0_1_2.error"
"0_2_2.error"
【改良した多角形近似による π の計算】
{
n}, {L
n} の間には次の関係式が成り立つ .
2n
=
√ 2
n1 +
1 − (
n/n)
2(4)
(4), (2) で求めた結果
6 3.000000000000 1.415926535898e-01 3.464101615138 3.225089615480e-01 12 3.105828541230 3.576411235954e-02 3.215390309173 7.379765558368e-02 24 3.132628613281 8.964040308554e-03 3.159659942098 1.806728850771e-02 48 3.139350203047 2.242450542925e-03 3.146086215131 4.493561541643e-03 96 3.141031950891 5.607026992824e-04 3.142714599645 1.121946055576e-03 192 3.141452472285 1.401813043294e-04 3.141873049980 2.803963900324e-04 384 3.141557607912 3.504567793389e-05 3.141662747057 7.009346705722e-05 768 3.141583892148 8.761441473215e-06 3.141610176605 1.752301489777e-05 1536 3.141590463228 2.190361741317e-06 3.141597034322 4.380731734255e-06 3072 3.141592105999 5.475905195951e-07 3.141593748771 1.095181560107e-06 6144 3.141592516692 1.368976332294e-07 3.141592927385 2.737953055387e-07 12288 3.141592619365 3.422440686407e-08 3.141592722039 6.844882260992e-08 24576 3.141592645034 8.556099828638e-09 3.141592670702 1.711220720679e-08 49152 3.141592651451 2.139022736714e-09 3.141592657868 4.278053467033e-09 98304 3.141592653055 5.347531306654e-10 3.141592654659 1.069515587204e-09 196608 3.141592653456 1.336855071088e-10 3.141592653857 2.673812282694e-10 393216 3.141592653556 3.341815713043e-11 3.141592653657 6.684741649110e-11 786432 3.141592653581 8.351097591230e-12 3.141592653607 1.671507376955e-11 1572864 3.141592653588 2.084554751036e-12 3.141592653594 4.181988089158e-12 3145728 3.141592653589 5.173639294753e-13 3.141592653591 1.048494624456e-12 6291456 3.141592653590 1.247890679679e-13 3.141592653590 2.655653474903e-13 12582912 3.141592653590 2.620126338115e-14 3.141592653590 7.061018436616e-14 25165824 3.141592653590 1.332267629550e-15 3.141592653590 2.220446049250e-14 50331648 3.141592653590 4.884981308351e-15 3.141592653590 1.021405182655e-14 100663296 3.141592653590 6.661338147751e-15 3.141592653590 7.549516567451e-15 201326592 3.141592653590 7.105427357601e-15 3.141592653590 7.105427357601e-15
ex04.tex,v 1.3 2004-10-21 15:01:32+09 naito Exp
4 ２００４年度・数理解析・計算機数学２・第４回
1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1
1 10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09
"0_4_1.error"
"0_4_2.error"
