2007/11/19 大体の概要 ` ` 先週の授業を思い出すこと加速とは無限遠方もしくは、ある近くの点を近似すること ` ` 近くの点の場合は補外ということが多い目的 ` ` 計算量の節約丸め誤差を避ける演習2 加速法 Richardson加速収束の種類 ` 指数収束 ` ` ` ` ` ` ` ` 誤差の「定数」部分はわからないことが多い ` この定数部分を推察して削除するのがRichardson加速 ` 有限要素法、有限差分法、etc. 例えば、誤差はO(h^2)とはわかるが、c h^2のcが不明指数収束より早いどうせすぐに収束するのであまり考えなくてもいい Richardson加速実験片側差分法 ` ` f ' ( x) ≅ f ( x + Δx ) − f ( x ) Δx Δx 2 Δx 3 = f ' ( x) + f ' ' ( x) + f ' ' ' ( x) + f ' ' ' ' ( x) + " Δx 2 6 24 このΔxの値を2-nとしたものをanとおくそうすると、anは an = f ' ( x ) + ` 数値微分や数値積分等では誤差のオーダーは解析的 ` 簡単に言えば、多項式(以下)で収束するもの anの誤差が1/nとか1/n^2とか十分大きなnでは、nを1増やしても誤差はほとんど縮まない Richardson加速の例 ` ` 超一次収束 ` ` 指数収束で用いる誤差がすでにわかっている場合に有効対数収束 ` ` ` それなりに扱いやすい誤差が指数で収束していく n n n f ' ' ( x) ⎛ 1 ⎞ f ' ' ' ( x) ⎛ 1 ⎞ f ' ' ' ' ( x) ⎛ 1 ⎞ ⎜ ⎟ +" ⎜ ⎟ + ⎜ ⎟ + 2 ⎝ 2⎠ 6 ⎝ 4⎠ 24 ⎝ 8 ⎠ これに対してRichardson加速が適用できる 1 2007/11/19 Aitken加速 ` ` ` ` ` Euler変換指数収束で用いる誤差の収束率がわからない場合 ` ` しかし、指数収束していることはわかっている場合指数収束しそうな場合 ` ` ` ` ` 誤差が解析的であるという仮定 ` ` 2 3 4 ` error = a1h + a2 h + a3 h + a4 h + " ` ` ` ` ` an = n個のサンプルからn-1項削除可能 ` ` どちらの場合も、誤差を自分で解析すること ` 別にむずかしくない ` 以下の二つから選択 ` Euler変換を用いて総和 (−1) の極限 k = 0 2k + 1 n 数列 an = ∑ 1 1 1 1 log 2 = 1 − + − + − " 2 3 4 5 普通にAitken加速で求められるはず多段加速も試してみる n π2 1 ` 数列 an = ∑ 2 → 6 k =0 k ` ` ` 多項式補外を用いてRomberg積分 1 ∫ exp( x)dx 0 2n ` f ( x + 2−n ) − f ( x − 2−n ) 2 * 2 −n 課題3(Optional) Aitken加速を用いた問題以下の二つから選択 k ` f ( x + 4 − n ) − f ( x) 4−n 中央差分(2次)で刻み幅を 1/2 ずつにする an = Romberg列 1, 1/2, 1/4, 1/8, .... Bulirsh列 1, 1/2, 1/3, 1/4, 1/6, 1/8, 1/12, 1/16, 1/24, 1/32, 1/48, ... Harmonic列 1, 1/2, 1/3, 1/4, 1/5, 1/6, ... 課題2 ` 片側差分(1次)の刻み幅を 1/4 ずつにするいくつかのhの選び方がある ` n項あれば、Richardson加速はn-1回適用可能最初の方には適用しない方がいい可能性がある Richardson加速を用いた数値微分 2題から選択そうすると、多項式の各項を削除することで計算可能 ` ` 従ってRichardson加速を無理やり適用する何回も適用できる課題1 誤差が差分hの多項式で表現されていると仮定 ` 指数収束の場合は意味がない交代数列ということは、収束率=-1と考えられる一項前のデータとの差が指数的に減っていけば指数収束と言える当然ながら解析的にわかる場合もある多項式補外 ` ` 指数収束はデータの推移をみると何となくわかることも ` 「対数収束」する「交代数列の和」において効果があるこのままでは求められないので、 an = ∑ k =0 1 k2 として実験をする ` ` ` Romberg列、Bulirsh列、Harmonic列から2つ以上選択計算量と精度などを考察すること等間隔格子を用いた台形公式で計算する 2