方程式を解く 知的情報処理 ３ 非線形方程式を解く 一変数 代数方程式を解くことは昔から重要な問題であった 算木にもたくさんある 数学競技会(例: 30題を40 50日で解く)で出された ３次 ４次代数方程式が一般的に解けた Scipione del Ferro (465-56), Niccoló Fontana Tartaglia(499547), Girolamo Cardano (50-576) 慶應義塾大学理工学部 櫻井彰人 ５次以上の代数方程式は一般的には解けない Niels Henrik Abel (80-89), Évariste Galois (8-83) 一般的に解く 係数を記号にして 四則と根号のみで 解を記述する Mathematica で解いてみよう http://www.sakurai.comp.ae.keio.ac.jp/classes/intinfproc-class/005/algebraiceq0.nb 方程式を数値的に解く 根の公式 有限の計算手順 がないとしたらどう するか 近似計算 と 試行錯誤 の組合せ でも どういう風に 試行錯誤 をするか グラフを描く 0 0. 0. 0.3 0.4 0.5 0.6 0.7 0.8 0.9...3.4.5.6.7.8.9 f().000 0.70 0.408 0.7-0.36-0.375-0.584-0.757-0.888-0.97 -.000-0.969-0.87-0.703-0.456-0.5 0.96 0.83.43.59 3.000 f ( ) = 3 3 + のとき f ( ) = 0となる を求める 4 3 3 0-0 - - 解がありそう 0.5.5
y ２分法 bisection method Regula Falsi 法 連続関数 f() に対して もし f(a)f(b)<0 (a<b) ならば a と b の間に f(c)=0 となる c がある という性質を利用して 何とかして f(0)f()<0 (0< ) なる 0 と を見出し i+ (i++i)/ かつ新しい i+は i+と i のどちらかで f の符号が i+ のものと異なるように選ぶ 英語では False-Position method. 語源は不明 分法の中点のかわりに (i,f(i)) と (i+,f(i +)) の点 を通る直線と 軸の交点を次の候補点とする 分法と同様に常に符号の異なる点で挟む f() i + = i + f(b) y=f() 新i+ i a f(c) c i+ i+= (i++i)/ i f ( i + ) f (i + ) f ( i ) i + i f(i+) f(i) i+ b i+ * i+ i f(i ) f(a) f(i+ ) 挟み撃ち Bracketing 法 割線 Secant 法 以上のように 根のある場所を それを含む閉区 間で近似し その閉区間をだんだん小さいしてい く方法を総称して挟み撃ち法と呼ぶ 安全確実であるが 一般に遅いのが欠点 そうでない方法を Open method という 日本語訳 不詳 まず Regula Falsi を改良してみよう Regula Falsi とそっくり 違いは 符号の異なる点で挟 む ことは要求しない (i,f(i)) と (i+,f(i +)) の点を通る直線と 軸の交点を 次の候補点 i + とする. i + は i + そのまま. f() i + = i + f ( i + ) f (i + ) f ( i ) i + i f(i+) f(i) i+ i+ i * f(i+ ) f(i ) i+ i
Secant 法の収束 不動点 Fied-Point 法 確かに速い f()=0 という方定式を 工夫 して これが大切 = g() という形にする 0 を初期値 うまく選ぶ とし i+ = g(i) という繰返しを行 う 収束すれば それが解 f ( ) = 3 3 + のとき f ( ) = 0となる で =.5 付近のもの 0. 分法 0.00 0.0000. 0 7. 0 9 Regula Falsi. 0 Secant 法. 0 3 4 6 8 0 不動点法の収束と発散 変換方法 収束する場合も あれば発散する 場合もある 不動点 * の周 囲で g'() < で あれば収束する r を求めるには別の変換方法が必要 3 3 + = 0 を = 3 3 と変形 r3 r i+ = g(i ) r
変換 変換 これなら求まる 一点も収束点がないこともある 3 3 + = 0 を 3 + と変形 = 3 g' ( ) > + = 0 を = と変形 g' ( ) < = g() どちらの交点でも g ' ( ) > g' ( ) > Newton-Raphson 法 原理 図で見る Newton-Raphson 法 f()=0 の解を求めることを考える. f() を i の周 りで Taylor 展開する. よりよい近似値となるであ ろう なってほしい i+ での値は 接線を引き 軸との交点を求める f ( i + ) = f ( i ) + f ( i )(i + i ) f ( ) = 4 + 3 4 = 0 f(i+) の方が f(i) より0に近いので 0とおく 0 = f ( i ) + f ( i )( i + i ) これから i + = i f ( i ) f ( i ) 根 * i+ i
Newton-Raphson 法の収束 Newton-Raphson 法の特徴 確かに速い 収束が速い: 次の収束 ε i + α ε i f ( ) = 3 3 + のとき f ( ) = 0となる で =.5 付近のもの 0. 分法 0.00 微分が必要: 一変数のときはさほどの問題では ないが 多変数のときは大問題 逆行列を計算する必要があるが これが大変 微分値で 割り算 : 0.0000 Newton-Raphson. 0 7 Regula Falsi. 0 9 挟み撃ち法ではない. 0 傾きが0に近くなると問題発生 解に近づくとは限らない Secan 法. 0 3 4 6 8 0 重根の問題 重根問題とその対策 重根とは 問題は f () が 0 に近くなること f ( ) = 5 4 + 46 3 90 + 8 7 二重根 三重根 丸め誤差が発生し 変なところで 本当に 0 になった り 0-割り算発生 問題 0 にならなかったり こっちは問題ではない 収束が次になる 現在では あまり問題ではない 対策 一次の収束でよければ Secant 法が安定していて計 算も速い 勧めない 次の収束を維持するには u= u(i ) f ( i ) f ( i ) f() i + = i すなわち i + = i f () u (i ) [ f (i )] f (i ) f (i ) i + = i m f(i ) f (i )
大域的な収束 プログラム 大域的な収束は保証されない Java のアプレットがあります 非常に分かりやす い 試してみてください http://www.apropos-logic.com/nc/ Mathematica のプログラムはこれです http://www.sakurai.comp.ae.keio.ac.jp/classes/intinfproc-class/005/nonlineareq-0.nb レポート課題 レポート課題: 注意 各自の学籍番号を seed として -00 から +00 までの擬似乱数を7個生成し それらを係数とす る７次代数方程式の根 近似値 をすべて求めよ 複素数根があるので注意されたし 提出期間: 0/4 0/8 日付が変わらないうちに 提出先 注: 求解プログラムは自分でMathematicaを用いて作 成する といっても 変更点はないか 注: 複素数に対しても Newton Raphson の式はその まま使える 下記２点については Mathematica のヘルプ ま たはマニュアル で調べてください Mathematica における擬似乱数の生成 Mathematica における複素数 メールにします が アドレスは次回に連絡します 件名は 学籍番号 半角数字 と氏名を併記したものとしてくださ い 間は半角の空白 例: 345678 矢上太郎 作成方法 ファイル形式は plain tet, Mathematica notebook, MSWord, pdf のいずれかとします 但し メールで提出するにあたって zip, lha, またはgz 形式 で圧 縮してから添付してください 考察をしっかり 説得的に書いてください その他 レポートは 各自 独自に作成してください