● 前回の講義のまとめ
• e
の近似値を計算する方法としては,e x
のテイラー展開e x = X
k=0
x k
k! (1)
を用いる方法がある.
• π
の近似値を計算する他の方法としては, arctan(x)のテイラー展開arctan(x) = X
k=0
( − 1) k x 2k+1
2k + 1 (2)
を用いる方法がある.
•
これらいずれの方法も,以下の問題がある.– e
の近似値を求めるためには, (1)をx = 1
として用いる必要があり,π
の近似値を求めるため には, (2)をx = 1
として用いる必要がある. そのため,それぞれの巾級数がx = 1
で収束して いる必要がある.– (1)
または(2)
を計算する際には, 無限級数の部分和（k= n
までの和）を計算する必要があり, そのための誤差（打ち切り誤差）を評価する必要がある.•
前者の問題については,それぞれの巾級数の収束半径を求める必要がある.– (1)
の右辺の巾級数の収束半径は∞
であるので,x = 1
のとき右辺の巾級数は絶対収束し,e = X
k=0
1
k! (3)
をみたす.
– (2)
の右辺の巾級数の収束半径は1
であるので,x = 1
のとき右辺の巾級数が収束して,π
4 = X
k=0
( − 1) n
2k + 1 (4)
がなりたつかどうかは,収束半径の議論だけではわからない. しかし,実際,
P ( − 1)
n(2k+1)!
は収束し,Abel
の定理より, (4)が成り立つ.•
打ち切り誤差の評価は以下のようになる.– (3)
の右辺の級数のk = n
までの部分和a n =
n
X
k=0
1 k!
と
e
との誤差は以下の評価をみたす.| e − a n | = X
k=n+1
1 k! ≤ 1
n!
したがって,打ち切り誤差が
ǫ
未満,すなわち,| e − a n | < ǫ
を満たすようにするためには,1
n! < ǫ
をみたす最小のn
まで計算すればよい.– (4)
の打ち切り誤差を議論するために,有限の等比級数n
X
k=0
( − x 2 ) k = 1 + x 2k+1 1 + x 2
を考える. この両辺を積分することにより,arctan(x) −
n
X
k=0
( − 1) k x 2k+1 2k + 1)
≤ Z x
0
t 2k+1 1 + t 2 dt ≤
( O(n − 1 ), x = 1,
O(x 2n+2 ), | x | < 1. (5)
を得る. このことから,π/4
の近似値を得るために(2)
をx = 1
で利用することは得策ではな いことがわかる.• π = 4 arctan(1)
の値を近似するには,マチンの公式arctan(1) = arctan(1/5) − 4 arctan(1/239)
などの(2)
を小さなx
で計算する公式を利用する必要がある.• | x | < 1
の場合の(2)
の打ち切り誤差は(5)
より,arctan(x) −
n
X
k=0
( − 1) k x 2k+1 2k + 1)
≤ x 2n+2 2n + 2
となるので,x 2n+2 < ǫ(2n + 2)
をみたす最小のn
まで計算すればよい.•
なめらかな関数f (x)
の零点を計算する方法として,区間縮小法とニュートン法がある.•
連続関数f [a, b] −→ R
が, [a, b]上単調増加であり,f (a) < 0, f (b) > 0
をみたすとき,中間値の定理より,
f (x) = 0
のただ一つの零点α
が(a, b)
に存在する. このことを利用して,以下の区間縮小法により
α
の近似値を得ることができる.– m = (a + b)/2
とおき,f (m) > 0
のとき,α ∈ (a, m)
がなりたつ. 逆にf (m) < 0
ならばα ∈ (m, b)
が成り立つ.– α
の近似値を絶対誤差ǫ
で求めるためには,それぞれのステップで得られた区間の幅b n − a n
がb n − a n < 2ǫ
を満たすまで上記のステップを繰り返し,α
の近似値として(a n + b n )/2
とすれ ばよい.• C 2
級の関数f [a, b] −→ R
が, [a, b]上単調増加であり,下に凸,f (a) < 0, f (b) > 0
をみたすとき,f (x) = 0
のただ一つの零点α
が(a, b)
に存在する. この零点α
の近似値を得る方法として,以下のニュートン法がある.
– x 0 = b
ととり,{ x n }
をx n+1 = x n − f (x n ) f ′ (x n )
で定める. これは, (x
n , f (x n ))
におけるy = f (x)
のグラフの接線とx
軸との交点をx n+1
と することに他ならない.– f (x)
の零点が単根で,ニュートン法が適用可能な時, ニュートン法による零点α
の近似列{ x n }
は| x n+1 − α | ≤ C | x n − α | 2
をみたす. （二次収束する）–
一般に数列{ x n }
がα
に収束することが保証されていても,| x n − x n − 1 |
を評価することにより| x n − α |
を評価することはできない.–
数列{ x n }
がα
に収束し,その収束が二次収束の時,| x n+1 − x n | ≤ ǫ 2 | x n |
ならば| x n − α | ≤ ǫ | α |
が成り立つ. すなわち,ニュートン法で単根の場合には,繰り返しの終了条件としてこの条件を 使うことができる.
● 講義資料
▼ 講義予定
•
ニュートン法と逐次近似•
収束の加速▼ 計算結果
★ 多角形近似による
π
の計算の加速1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1
1 10 100 1000 10000 100000
None Romberg 1 Romberg 2 Aitken
● 実習内容
1.
第３回の講義内容の円周率の値の近似値を求める計算（方法３）の収束を, Ronberg加速を用いて加 速計算しなさい.2.
第３回の講義内容の円周率の値の近似値を求める計算（方法３）の収束を, Ronberg加速を２段用い て加速計算しなさい.3.
第３回の講義内容の円周率の値の近似値を求める計算（方法３）の収束を, Aitken加速を用いて加速 計算しなさい.4.
ニュートン法をf (x) = (x + 1)(x − 1) 2
に適用し, その計算をRomberg
加速またはAitken
加速を 用いて加速計算しなさい.● レポート問題
★ レポート問題
以下の問題は評価対象のレポート問題です.
【レポート問題
02】
ニュートン法を用いてf (x) = x 2 − cos(x)
の正の零点の近似値を相対誤差10 − 12
で 求めるプログラムを書きなさい. また,f [a, b] −→ R
が[a, b]
で単調増加,下に凸,f (a) < 0, f (b) > 0
をみたすとき,x 0 = b
ととったニュートン法の列{ x n }
が, [a, b]内のf (x)
の唯一の零点α
に収束 することを証明し,あるC > 0
が存在して,| x n+1 − α | ≤ C | x n − α | 2
をみたすことを証明しなさい. さらにこの時,
| x n+1 − x n | ≤ ǫ 2 | x n |
ならば| x n − α | ≤ ǫ | α |
が成り立つことを示し,この主張がニュートン法の収束判定にどのように利用できるかをのべなさい.
この問題については,
A: 10
点B: 6
点C: 0
点と採点します. （中間的な点をつける可能性あり）★ 注意事項
【締め切り】 問題
02
については,電子メールで提出する場合には,２００９年６月１０日（水）１４：０ ０までに届くように提出すること. 「計算結果の考察」をレポート用紙に書いたもので提出する場合 には,２００９年６月１０日（水）の講義時間に提出すること. （教育実習等がある場合には申し出 てください. 締め切りを延長します）★ レポート問題
(Extra)
以下の問題は評価対象のレポート問題ですが,この問題を「評価の点の満点」にはカウントしません.（つ まり,以下の問題での得点は「ボーナスポイント」となります.）
【レポート問題
E01
】f (x) = (x − 1) 3 (x + 1)
の正の零点の近似値を, ニュートン法の近似列をAitken
加速をすることにより,相対誤差10 − 12
で求めるプログラムを書きなさい.【レポート問題
E02
】 ニュートン法でf ′
を計算するところを「微分商」に置き換えたもの,すなわち,x n+1 = x n − f (x n ) x n − x n − 1
f (x n ) − f (x n − 1 )
によって
f (x) = 0
の解を求める方法を割線法と呼ぶ.なめらかな関数
f [a, b] −→ R
が[a, b]
で単調増加,下に凸,f (a) < 0, f (b) > 0
の時,x 0 , x 1
を適切 にとったとき,割線法による近似列{ x n }
は, [a, b]内のf (x)
のただひとつの零点に収束することを 示し,その近似誤差ǫ n = | x n − α |
は,あるL > 0
とC > 0
が存在して,ǫ n+1 ≤ Lǫ n ǫ n − 1 , ǫ n+1 ≤ Cǫ p n , p = 1 + √ 5 2
をみたすことを証明しなさい. さらに,
x n
が相対誤差ǫ
でα
を近似しているための, 割線法のプロ グラム内で判定可能な条件を導きなさい.問題
