きょうの講義 数値 記号処理 2003.2.6 櫻井彰人 NumSymbol@soft.ae.keo.ac.jp http://www.sakura.comp.ae.keo.ac.jp/ 数値計算手法の定石 多項式近似 ( 復習 )» 誤差と手間の解析も 漸化式» 非線型方程式の求解 数値演算上の誤差 数値計算上の誤差 打ち切り誤差 (truncaton error)» 使う公式を有限項で打ち切る e = + + (/2!) 2 + (/3!) 3 +... 丸めの誤差 その他 (2) 多項式近似 p() = a 0 + a + a 2 2 +... + a n n 多項式 少ない四則演算回数で計算できる ( 多項式でなければ 収束までの反復計算等 ) 解析学的な操作 ( 微分や積分など ) が容易 多項式で近似した数値計算 多項式の計算 単純に計算 掛け算と足し算の回数が多い 個別の演算誤差が集積 正しくない値も (2-) 補間と外挿 いくつかの点で既知の値 値の分かっている点以外での値? 分かっているものを使って多項式をあてはめる 既知 : n+ 個の点での値 これらの点以外での値 たとえば 時間がかかる 乗算 を減らすために p() = a 0 + (a + (a 2 +... (a n- + a n )..) { k } { y k } k = 0,, 2,, n y All rghts reserved.
補間と外挿の定義と例 補間 (nterpolaton) 分かっている範囲内で 0 << n から に対応する値 たとえば 滑らかな文字フォントを作る 外挿 (etrapolaton) 分かっている範囲を超えて < 0 または n < なる に対応する値 たとえば 昨年までの理工学部合格者の入学手続き状況から 今年度の合格者を何番までに? 単純な補間 線型補間 すべての点を 次式 ( 直線 ) で結ぶ ( あれば ) ( 0,y 0 ),(,y )...,( n,y n ) を通る の一次式 y=p(), - << ( 各区間毎 ) y y = y + y ( ) Lagrange の補間多項式 相異なる n+ 個の点に対応する値が存在するとき これらの値をとる次のような n 次多項式がただ一つ存在する n j yk k = 0 j k k j Lagrange の補間多項式の誤差 関数 f() とそのラグランジュ n 次補間多項式 p n () による近似誤差が次のようになる * ( 0 <*< n ) が存在する n+ f ( *) ( 0)( )...( n ) ( n + )! ( 注 ) y = f( ) が成立しない ( 誤差がある ) ときには話が大幅に変わる 多項式近似 : 次数と近似精度 データ 線形 2 次多項式 全点を通る 4 次多項式 パラメータ数 2 3 5 近似精度悪いまあまあ誤差 =0 予測精度まあまあまあまあ悪い スプライン補間 Lagrange 補間 次数が上がると激しい振動» わずかな誤差が大きな影響 区間に分け 各区間ごとに個別の多項式で近似それらの多項式をつなぎあわせる スプライン (splne) 補間 All rghts reserved. 2
スプライン補間の条件 m 次スプラインS() 曲線 S() は連続 ( = 2,, n-) の区間の境目で» m- 階連続微分可能 演習 具体的に {,y } の組をいくつか与えて2 次や 3 次のスプライン関数を求めなさい (2-2) 級数展開と打ち切り誤差 各種の関数 級数展開して多項式に 無限級数をどこかで打ち切る 打ち切り誤差 (truncaton error) e = n n n= 0! m n= 0 n! 打ち切り誤差 (truncaton error) m + ( n + )! ( n + 2)! + m+ n +... (3) 漸化式 漸化式による繰り返し計算 収束性と計算量 ( 収束の速さ ) が問題 例題 : 非線型方程式を解く f()=0 例題 : 連立方程式を解く A=b (3-2) 2 分 (bsecton) 法 例題 : 非線型方程式 f()=0 を解く f() の値が正と負になる 2 点からはじめて 挟み撃ち f() b a m (a +b )/2 (3-3) 試行錯誤 (regula fals) 法 2 分法の中点の代わりに 2 点を結ぶ直線と 軸の交点を新たな点に f() (3-4)Newton 法 (Newton-Raphson 法 ) 関数 f() を の周囲で一次までの Taylor 展開で近似 f() ~ f( )+f ( )(- ) f()=0 の根 + の近似値を とする ( + と は非常に近い ). 0 ~ f( ) + f ( )( + - ) a b ṅew + = - f( )/f ( ) における接線と 軸との交点が ( +,0) となる All rghts reserved. 3
Newton-Raphson 法の原理 f() Newton-Raphson 法の収束性 ( 例 ) 反復演算での収束性が問題 たとえば N の平方根を求めるとすると f() = 2 - N + = - f( )/ f ( ) α 3 = f + f 0 ( ) '( ) lm{ + } N Newton-Raphson 法の収束の様子 50 の平方根を求める a0 = 50 から始め Mathematca で次の操作を繰り返してみよう» f[_] := ^2-50» a0 = 50» a = N[a0 - f[a0]/f [a0]]» a2 = N[a - f[a]/f [a]]» a3 = N[a2 - f[a2]/f [a2]]» a4 = N[a3 - f[a3]/f [a3]]» a5= N[a4 - f[a4]/f [a4]] Newton-Raphson 法の収束 まとめて Do ループで まず net 関数を定義» net[_, fun_] := N[ - fun[]/fun []] 次に a = 50 を代入しておく» a = 50 そして Do[a = net[a, f]; Prnt[j, :, a], {j,, 0}] 近似していく様子を図示してみよう Mathematca にはニュートン法の関数が FndRoot[^2-50 == 0, {, 50}] Newton-Raphson 法の収束性 ( 定理 ) 逐次近似の数列 0,, 2,... および根 α を含む区間内で 反復関数 F()=f()/f () の導関数 F () の最大値が K K< 数列 { + } は根 α に収束 証明の概要 : 反復関数の性質 F( ) = + 平均値の定理 F( 0 )-F(α)=( 0 -α)f ( 0 *) ただし 0 * ( 0,α) Newton-Raphson 法の収束性 ( 証明 ) - α < 0 - α K + - α < 0 - α K + K< lm -> + - α = 0 lm -> + = α All rghts reserved. 4
Newton-Raphson 法の収束の速さ 回の計算でどれだけ真の解に近づくか 誤差項 e = - α としたとき e + と e の関係? Newton-Raphson 法は 2 次の収束 N-R 法の収束の速さ ( 略証 ) 反復関数 F() を =α のまわりで Taylor 展開し その 2 次までの項をとると F( ) α+ (f (α)/2f (α))( -α) 2 + = F( ) より e + (f (α)/2f (α))e 2 となる f ''( α) e 2 f '( α) 2 e + (3-5)secant 法 はじめの2 点 ( 0,f( 0 )) (,f( )) を結ぶ直線と 軸の交点を 2 とする 上の操作を順に繰り返して 3, 4,... と求めていく f() secant lne secant 法の計算 secant 法のプログラムを書いてみよう 0 と を適当に決める =, 2, 3, 4,... に対して以下を繰り返す + f ( ) f ( ) = f ( ) f ( ) 2 0 (3-6) 不動点 (fed pont) 法 f() = g() - = 0 の形の方程式 y=g() と y= の交点の 座標 α 適当な 0 を決める =,2,3,... に対して + =g( ) を繰り返す y= y g() 復習 :2 分 (bsecton) 法 例題 : 非線型方程式 f()=0 を解く f() の値が正と負になる 2 点からはじめて 挟み撃ち f() 0 α a b m (a +b )/2 All rghts reserved. 5
復習 : 試行錯誤 (regula fals) 法 2 分法の中点の代わりに 2 点を結ぶ直線と 軸の交点を新たな点に f() 収束の速さの比較 2 分法 : e + = e /2 試行錯誤法 : e + ((f (α))/2(f (α)(α-a ))) e または e + ((f (α))/2(f (α)(α-b ))) e Newton-Raphson 法 : e + (f (α)/2f (α)) e 2 secant 法 : e + (f (α)/2f (α)) e e - 不動点法 : e + < K e Kは定数 a b ṅew All rghts reserved. 6