Document

プログラミング論 I
2010年5月6日
非線形方程式の近似解
(2分法，はさみうち法，Newton-Raphson法)
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2010
for文復習
for(i=0; i<3; i++){
printf("Hello\n");
printf("World\n");
}
i=0;
printf("Hello\n");
printf("World\n");
i=1;
printf("Hello\n");
printf("World\n");
i=2;
printf("Hello\n");
printf("World\n");
B-2
for文復習
for(i=0; i<3; i++){
printf("%d\n", i);
}
i=0;
printf("%d\n", i);
i=1;
printf("%d\n", i);
i=2;
printf("%d\n", i);
B-3
概要
• 非線形方程式の近似解の求め方
– 2分法
– はさみうち法
– Newton-Raphson法)
B-4
非線形方程式の近似解
• 解析的に解けない非線形方程式の近似解
を求める方法．
– 非線形方程式の多くは解析的に解けない．
– 解の候補を方程式に代入すれば解か否かは
判断可能
– 計算機により「解の候補を代入する」ことを繰
り返し，解を探していく．
B-5
非線形方程式の近似解
• 非線形方程式 f (x) = 0 の解を求める
例 : f (x) = x4+ax3+bx2+cx+d
y = f (x) とし，x から y を求めるのは容易．
y から x を求めることができない．
x に具体的な数値を代入し，yを求めるのは容易
例 : f (x) = x4+2x3+3x2+4x+5 に x = 2を代入，
f (2) = 41
B-6
非線形方程式の近似解の計算
ー反復法ー
•
“反復法”は反復により方程式などの近
似解を求める手法の総称．
– 具体例 : 2分法，はさみうち法，
Newton-Raphson法など
•
基本的に，連続である関数の解を求める
B-7
非線形方程式の近似解の計算
ー反復法ー
•
f (x) = 0 の近似解を求める例
(1)解の候補の初期値を定める.
(2)候補を f (x) に代入し，解であるか否か，解に
近いか調べる．
(3)上記(2)を元に，より解に近い候補を求める
(4)候補が解に十分近ければ終了．
近くない場合は，(2)に戻り繰り返す．
B-8
2分法
Bisection Method
2分法
• 反復法の一種．
• 初期値の区間内に解が存在すれば必ず
収束し，必ず近似解が求まる．
• 収束速度は遅い．
• 連続な関数なら一般に使える
B-10
2分法概要
方程式を f (x) = 0 とする
(1) 解が存在する区間[a,b]を定める．
(2) m = (a+b)/2 とし，f (m)を求め，
(3) 解がmより小さいか大きいか調べる．
・ mより小さい→解は区間[a,m]に存在．
・ mより大きい→解は区間[m,b]に存在．
(解の存在区間が半分になり，解に近づいた)
B-11
2分法概要
(4) 新しい区間を[a,b]とし，
これが十分に狭いか調べる．
十分に狭ければ終了．
狭くなければ新区間を用いて(2)に戻る．
・初期区間[a,b]が定められないと，2分法は
使えない．
B-12
2分法の例
• f (x) = 0.1x3+x-16 とし f (x) = 0 の解を探す
50
40
f (x)
30
20
10
0
-10
0
1
2
3
4
5
6
7
8
-20
x
B-13
2分法の例
• f (x) = 0.1x3+x-16
ただし，以下は既知であると仮定する．
– f (x)は単調増加であり実数解は1個
– 解は0～8の間に存在する
(1) 初期の区間を[0,8]に定める．
解は[0,8]に存在する．
B-14
(8, f (8))
50
40
f (x)
30
解はこの区間に存在する
20
10
0
-10
0
1
2
3
4
5
6
7
8
-20
x
(0, f (0))
B-15
2分法の例
(2) 現在の区間 [0,8] の中心 4 に着目する．
解が 4 より小さいか，大きいかを調べる．
f (4) = -5.6 ＜ 0
なので，4 は解としては小さすぎた．
解は4より大きく，[4,8]に存在する．
(区間は半分に狭まった)
B-16
50
40
f (x) は単調増加
なので，
解はこの区間に
存在しない.
f (x)
30
20
10
f (x) は単調増加
なので，
解はこの区間に
存在する
0
-10
0
1
2
3
4
5
6
7
8
-20
x
B-17
2分法の例
(3) 現在の区間 [4,8] の中心 6 に着目する．
解が 6 より小さいか，大きいかを調べる．
f (6) = 11.6 > 0
なので，6 は解としては大きすぎた．
解は6より大きく，[4,6]に存在する．
(区間はさらに半分に狭まった)
B-18
50
40
解はこの区間に
存在する
f (x)
30
20
10
0
-10
0
1
2
3
4
5
6
7
8
-20
x
B-19
2分法の例
50
[4,6]の中間値 5 を
試す．
f (5) = 1.5 > 0 で，
解は [4,5]に
存在する．
40
f (x)
30
20
10
0
-10
0
1
2
3
4
5
6
7
8
-20
x
B-20
2分法の例
50
[4,5]の中間値 4.5 を
試す．
30
f (4.5) = -2.3875 < 0 で，
20 解は [4.5,5]に存在する．
f (x)
40
10
0
-10
0
1
2
3
4
5
6
7
8
-20
x
B-21
2分法の例
以下同様に繰り返し，
解が存在する区間を狭めていく．
区間が十分に小さくなったら終了する．
B-22
2分法の手順
方程式を f (x) = 0 とする
(1)初期値(初期区間) xmin0 と xmax0定める．
解は [xmin0 , xmax0] に存在する必要がある．
すなわち，f (xmin0) f (xmax0)＜0 である．
ここでは f (x)が単調増加関数であり，
f (xmin0)＜０， f (xmax0)＞0 である例を扱う．
B-23
2分法の手順
(2) xmin0 と xmax0の中間値である
xmid0 = (xmin0+xmax0)/2 を求める．
B-24
2分法の手順
(3) f (xmid0) を求め，
f (xmid0)＜0 か f (xmid0)＞0 かを調べる．
f (x) は増加関数なので，
・ f (xmid0)＜0 なら，解は xmid0 より大きい．
解は区間は[xmid0 , xmax0]に存在する．
xmin1=xmid0，xmax1=xmax0，
・ f (xmid0)＞0 なら，解は xmid0 より小さい．
新しい区間を[xmin1, xmax1]とする．
B-25
2分法の手順
(4) 解は区間 [xmin1 , xmax1]に存在している．
新しい区間が十分に狭ければ終了する．
以下同様に，
xmid1 = (xmin1+xmax1)/2 を求め，
解がf (xmid1)より小さいか，大きいかを調
べ，さらに狭い新しい区間を求めていく．
区間が十分に狭くなったら終了．
B-26
2分法の特徴
• 1回繰り返すたびに解の存在する区間が
半分に減っていく．
– これは他の手法と比べて収束が速いとは言え
ない．
• 初期値が指定できれば必ず収束する．
• 収束の速度を予想できる．
B-27
例
f (x) = x3-10 とする. f (x) = 0 の解を探す．
解は[0, 4]にあるのは既知であるとする．
– [0,4]の中間2に着目.
f (0)<0, f (2)<0, f (4)>0 なので解は[2,4]
– [2,4]の中間3に着目.
f (2)<0, f (3)>0, f (4)>0 なので解は[2,3]
B-28
練習 A
f (x) = -x2+10 とする. f (x) = 0 の解を探す．
解は[-2,6]にあるのは既知であるとする．
• 2分法で解の範囲を狭めていく場合の，解
の範囲の推移を記せ．
• 解の範囲の長さが1以下になったら終了．
• おまけ：ロンドン(London)はどこの国の首都？
B-29
解答 A
• [-2,6]の中間2に着目．
f (-2)>0, f (2)>0, f (6)<0 なので解は[2,6]
• [2,6]の中間4に着目．
f (2)>0, f (4)<0, f (6)<0 なので解は[2,4]
• [2,4]の中間3に着目．
f (2)>0, f (3)>0, f (4)<0 なので解は[3,4]
• 解の範囲の長さが1になったので終了．
B-30
はさみうち法
Regula Falsi Method
はさみうち法
• 反復法の一種．
• 初期値の区間内に解が存在すれば必ず
収束し，必ず近似解が求まる．
– 区間の長さはゼロに収束しない (2分法と異なる)
• 収束速度は2分法より速いと期待される
– 必ずしも速いとは限らない
• 2分法と似ているが，次の候補に1次近似
を用いる
B-32
はさみうち法の前に
点(x0 , y0)を通り，傾きaの直線の式は
y - y0 = a ( x - x0)
2点(x0 , y0)と(x1 , y1) を通る直線の傾きと式は
傾き
直線の式
y0  y1
y0  y1
y  y0 
( x  x0 )
x0  x1
x0  x1
B-33
はさみうち法
方程式を f (x) = 0 とする
(1) 解が存在する区間[a,b]を定める．
(2) 2点 ( a , f (a) ) と ( b , f (b) ) を通る直線を
求め，これを y = f (x) の近似直線とする．
近似直線がx軸と交わる点(m,0)を求める．
近似直線と y = f (x) が近ければ，
mは解と近いことが期待される．
B-34
はさみうち法
2点( a , f (a) )と( b , f (b) ) を通る近似直線は
f (a)  f (b)
y  f (a) 
( x  a)
a b
近似直線がx軸と交わる点(m,0)を求めるには
一次方程式
f (a )  f (b)
0  f (a) 
(m  a)
a b
を解く
bf (a)  af (b)
結果 m  f (a)  f (b) となる
B-35
はさみうち法
(3) 解がmより小さいか大きいか調べる．
・ mより小さい→解は区間[a,m]に存在．
(b-m) が十分に小さければ終了
・ mより大きい→解は区間[m,b]に存在．
(m-a) が十分に小さければ終了
(4) 新しい区間を[a,b]として，
これを用いて (2) に戻る
B-36
はさみうち法の例
• f (x) = 0.1x3+x-50 とし f (x) = 0 の解を探す
10
0
0
1
2
3
4
5
6
7
8
f (x)
-10
-20
-30
-40
-50
x
B-37
はさみうち法の例
• f (x) = 0.1x3+x-50
ただし，以下は既知であると仮定する．
– f (x)は単調増加であり実数解は1個
– 解は0～8の間に存在する
(1) 初期の区間を[0,8]に定める．
解は[0,8]に存在する．
B-38
10
0
0
1
2
3
4
5
6
7
8
f (x)
-10
-20
-30
解はこの区間に存在する
-40
-50
x
f (0) より f (8) の方が 0 に近いので，
x=0 より x=8 の方が，解に近いと期待される．
B-39
はさみうち法の例
(2) 2点(0, f (0) ) と (8, f (8) ) を通る近似直線
を引く．
これがx軸と交わる点を(m0,0)とし，m0に
着目する．
B-40
はさみうち法の例
f (0)= -50 ，f (8)=9.2 であり，
(0, -50) と (8, 9.2) を通る直線は
(50)  9.2
y  (50) 
( x  0)
08
x軸と交わる点を(m0,0)のm0を求めるには
(50)  9.2
0  (50) 
(m0  0) を解く
08
結果，m0 ≒ 6.76
B-41
はさみうち法の例
(3) 解がm0より小さいか，大きいかを調べる．
f (m0) ≒ -12.40
なので， m0は解としては小さすぎた．
解はm0より大きく，[m0,8]に存在する．
(ただし m0≒ 6.76)
B-42
10
0
0
1
2
3
4
5
6
7
8
f (x)
-10
-20
-30
2分法では，
[0,8]の中央の4を
用いて調査する．
はさみうち法では，
近似直線の
x切片(m0)を
用いて調査する．
-40
-50
x
解はこの区間に
存在する
B-43
はさみうち法の例
(4) 解は [m0,8]に存在する．
(m0, f (m0)) と (8, f (8)) を通る近似曲線の
x切片(m1,0)を求める．
m1 ≒ 7.47 , f (m1) ≒ -12.40
なので， m1は解としては小さすぎた．
解はm1より大きく，[m1, 8]に存在する．
B-44
10
0
0
1
2
3
4
5
6
7
8
f (x)
-10
-20
-30
-40
-50
x
解はこの区間に
存在する
B-45
はさみうち法が2分法より効率が
悪い例
5
はさみうち法では
この点が解に近いと
期待して調査する
4
3
2分法では，
中央の4を
調査する
f (x)
2
1
0
-1
0
1
2
3
4
5
6
7
8
-2
-3
x
B-46
はさみうち法の特徴
• 初期値が指定できれば必ず解に収束する．
• 区間の長さはゼロに収束しない
• 2分法より速い収束が期待できるが，必ず
速いわけではない．
• 「f (m)が十分に小さいこと」を収束条件とす
ることもある．
• 厳密には「(b-m)，(m-a) や| f (m)|が十分に
小さいこと」は，解の精度を保証していない．
B-47
Newton-Raphson法
Newton-Raphson Method
Newton-Raphson法
•
•
•
•
反復法の一種．
必ず収束するとは限らない．
初期値が解に近ければ高速に収束する．
n回目の調査で使った点から1次近似直線
を引き，そのx切片をn+1回目の候補とする
• 初期値は1個の値．
– 2分法やはさみうち法の様に区間ではない．
B-49
Newton-Raphson法
方程式を f (x) = 0 とする
(1) 解に近い値 a0 を定める．
(2) y = f (x) に対して，( an , f (an) ) で接する
接線(1次近似直線)を引く．
接線は y – f (an) = f '(an) (x–an)
B-50
Newton-Raphson法
(3) 近似直線がx軸と交わる点(an+1,0)を求める．
すなわち，折線 y – f (an) = f ’(an) (x–an) が
y=0となる x を求め，その x がan+1である．
f ( an )
an 1  an 
f ' ( an )
近似直線と y = f (x) が近ければ，
an+1は解に近いことが期待される．
B-51
Newton-Raphson法
(4) |an-an+1| が十分に小さければ，終了．
小さく無ければ，(2)に戻る
B-52
Newton-Raphson法の例
• f (x) = 0.1x3+x-5 とし f (x) = 0 の解を探す
60
50
40
f(x)
30
20
10
0
0
1
2
3
4
5
6
7
8
-10
x
B-53
Newton-Raphson法の例
• f '(x) = 0.3x2+1
• 初期値a0=7とする．
• y = f (x) と ( 7, f (7) )で接する接線を引き，
接線がx軸と交わる点(a1, 0)を求め，
このa1に着目する．
B-54
Newton-Raphson法の例
ただし，( 7, f (7) )における接線は
y – f (7) = f ’(7)(x – 7)
接線のx切片は
f (7 )
a1  7 
≒ 4.69
f ' (7 )
B-55
近似直線と y= f (x) が
近ければ，
近似直線のx切片は
解に近いと期待される．
60
50
40
( 7, f (7) )
f(x)
30
20
10
( 7, f (7) )で
接する接線
0
0
1
2
3
4
5
6
7
8
-10
x
次に着目する点
B-56
Newton-Raphson法の例
• y = f (x) と (a1, f (a1) )で接する接線を引き，
接線がx軸と交わる点(a2, 0)を求め，
次は，このa2に着目する．
B-57
60
50
40
f(x)
30
20
10
0
0
1
2
3
4
5
6
7
8
-10
x
B-58
6
5
4
f(x)
3
2
1
0
2
2.5
3
3.5
4
-1
-2
x
B-59
Neton-Raphson法で収束しない例
接点
接線
次の候補
次の候補
接線
接点
B-60
Newton-Raphson法の特徴
• 接線(1次近似直線)が，方程式と近ければ，高速
に収束していく．
• 初期値が解に近くないと，収束しない．
• 微分できないとNewton-Raphson法は使えない．
– 傾きがゼロの箇所においても使えない．
• 「 | f (an)|が十分に小さいこと」を収束条件するこ
ともある．
• 厳密には「|an-an+1|や f (m)が十分に小さいこと」
は，解の精度を保証していない．
B-61
復習：2分法
• 2分法
f (x)=ｰx3ｰx2+5x+20
として f (x)=0 の解を探す
(注意:f (x) は単調増加ではない)
ただし解が[-4,4]に存在は既知
50
40
30
f(x)
20
10
0
-4
-3
-2
-1 -10 0
1
2
3
4
-20
-30
x
B-62
復習：2分法
• 解は[-4,4]で，f (-4)>0, f (4)<0
中間値0に着目．
f (-4)>0, f (0)>0, f (4)<0 なので，解は[0,4]に
• 解は[0,4]で，f (0)>0, f (4)<0
中間値2に着目．
f (0)>0, f (2)>0, f (4)<0 なので，解は[2,4]に
• 解は[2,4]で，f (2)>0, f (4)<0
中間値3に着目．
f (2)>0, f (3)<0, f (4)<0 なので，解は[2,3]に
B-63
復習：2分法
min=??, max=??;
(max-min)が大きいなら繰り返す
mid=(min+max)/2;
f(min)*f(mid)>0 同符号なら
解は[mid,max]
min = mid;
f(min)*f(mid)<0 異符号なら
解は[min,mid]
max = mid;
繰り返しの先頭に戻る
B-64

Download Report