PowerPoint プレゼンテーション

非線形方程式に対する
反復解法
非線形方程式とは?
方程式
f(x)=0
(f(x)はxの関数)
f(x)は線形(一次)  f(x)=ax + b
f(x)は非線形  それ以外の関数
2次式、
3次式: 5x 2  4 x  7,
高次式: x10  2 x7  4x
x
2
三角関数: sin( x  x ) 
2
指数関数: exp( x)  5
x3  2 x 2  4 x  1
反復解法の必要性
一次、二次の方程式: 公式を使えば簡単!
三次の方程式: 頑張れば手計算で解けるかも…
一般の非線形方程式: 手計算で解くのはほとんど無理
コンピュータ+アルゴリズムの利用
反復解法
x を繰り返し更新、近似的な解を求める
反復解法の種類
•
•
•
•
•
二分法
はさみうち法
割線法(セカント法)
ニュートン‐ラフソン法
減速ニュートン法
今週説明
来週説明
二分法(その1)
「中間値の定理」に基づく方法
f (a)  0, f (b)  0
 f (c)  0を満たすcがaと bの間に存在する
f(c)=0
a
f(a)<0
f(b)>0
c
b
二分法(その2)
1. f(a)<0 なる a と f(b)>0 なる b を求める
2. c=(a+b)/2 とおく
3. f(c) の絶対値が十分小さい => 終了
4. f(c)>0 ならば b = c, f (c) <0 ならば a = c とおく
5. 1へ戻る
f(b)>0
f(c)の絶対値は大きい
a
f(a)<0
b
c=(a+b)/2
f(c)>0 なので b = c
二分法(その3)
2. c=(a+b)/2 とおく
3. f(c) の絶対値が十分小さい => 終了
4. f(c)>0 ならば b = c, f (c) <0 ならば a = c とおく
5. 1へ戻る
f(c)<0 なので a = c
c=(a+b)/2
a
f(a)<0
f(b)>0
b
f(c)の絶対値はまだ大きい
二分法(その4)
f(b)>0
a
f(a)<0
a
b
b
方程式の解が
見つかる!
b
はさみうち法(その1)
a b
二分法の場合: c 
2
はさみうち法の場合:
a f (b)  b f (a)
c
f (b)  f (a)
c  2点(a, f (a))と (b, f (b))を結ぶ
線分と x軸の交点
f(b)>0
a
f(a)<0
c
b
f(c)>0 なので b = c
はさみうち法(その2)
c  2点(a, f (a))と (b, f (b))を結ぶ
線分と x軸の交点
c
a
f(a)<0
f(b)>0
b
f(c)<0 なので a = c
はさみうち法(その3)
f(b)>0
a
f(a)<0
a
b
方程式の解が
見つかる!
b
反復解法の性能評価
よい反復解法とは?
•わかりやすい
•プログラムを組みやすい
•反復回数が少ない
•解の精度が良い
 f(x) の絶対値がほとんど0
今週の課題(その1)
1. レポート用紙に書かれた関数に対して自分の手で二分
法・はさみうち法を実行し、解を求めよ。
また、二分法及びはさみうち法それぞれが得意・不得意
とするする関数はどのようなものか、自分の考えを
述べよ。
締め切り:12月15日(金)11時まで
問題1:所定のレポート用紙に書いて提出
問題2,3:PCを使って提出
今週の課題(その2)
2. はさみうち法のプログラムを作れ。
(二分法のプログラムを参考に)
3. 下記の3種類の方程式に対して二分法、はさみうち法を
適用し、反復回数および解の精度を比べて2つの解法を
評価せよ。
(1) a cos(x)  bx (解の探索区間は [20,20]) (2) ax3  x 2  b (解の探索区間は [20,20])
(3) ax  exp(bx) (解の探索区間は [0,20])
なお、上記の式の中で
a =学籍番号の下二桁目(0の場合は10)
b = 学籍番号の下一桁目(0の場合は10) とする。
例えば、A0071321の学生の場合 a = 2, b = 1