2008年6月5日 非線形方程式の近似解 2分法，はさみうち法，Newton-Raphson法)

Presentation on theme: "2008年6月5日 非線形方程式の近似解 2分法，はさみうち法，Newton-Raphson法)"— Presentation transcript:

1 2008年6月5日 非線形方程式の近似解 2分法，はさみうち法，Newton-Raphson法)
プログラミング論 I 2008年6月5日 非線形方程式の近似解 2分法，はさみうち法，Newton-Raphson法)

2 for文復習 for(i=0; i<3; i++){ printf("Hello\n"); printf("World\n"); }

3 for文復習 for(i=0; i<3; i++){ printf("%d\n", i); } i=0;

4 練習 0 下のプログラムの出力は？ int i, j; for(i=0; i<3; i++){
for(j=0; j<2; j++){ printf("i=%d, j=%d\n", i, j); }

5 解答 0 i=0, j=0 i=0, j=1 i=1, j=0 i=1, j=1 i=2, j=0 i=2, j=1

6 練習 1 左のプログラムの出力は？ a = 12; b = 7; if( a < 10 ){ printf("A\n");
if( b < 10 ){ printf("B\n"); } else { printf("C\n"); } printf("D\n"); printf("E\n"); printf("F\n"); 左のプログラムの出力は？

7 解答 1 D E F

8 概要 非線形方程式の近似解の求め方 2分法 はさみうち法 Newton-Raphson法)

9 非線形方程式の近似解 解析的に解けない非線形方程式の近似解を求める方法． 非線形方程式の多くは解析的に解けない．
解の候補を方程式に代入すれば解か否かは判断可能 計算機により「解の候補を代入する」ことを繰り返し，解を探していく．

10 非線形方程式の近似解 非線形方程式 f (x) = 0 の解を求める y = f (x) とし，x から y を求めるのは容易．
例 : 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

11 非線形方程式の近似解の計算 ー 反復法 ー “反復法”は反復により方程式などの近似解を求める手法の総称．
具体例 : 2分法，はさみうち法， Newton-Raphson法など 基本的に，連続である関数の解を求める

12 非線形方程式の近似解の計算 ー 反復法 ー f (x) = 0 の近似解を求める例 解の候補の初期値を定める.
上記(2)を元に，より解に近い候補を求める 候補が解に十分近ければ終了． 近くない場合は，(2)に戻り繰り返す．

13

14

15 2分法 Bisection Method

16 2分法 反復法の一種． 初期値の区間内に解が存在すれば必ず収束し，必ず近似解が求まる． 収束速度は遅い． 連続な関数なら一般に使える

17 2分法 概要 方程式を f (x) = 0 とする (1) 解が存在する区間[a,b]を定める．
(2) m = (a+b)/2 とし，f (m)を求め， (3) 解がmより小さいか大きいか調べる． 　・ mより小さい→解は区間[a,m]に存在． 　・ mより大きい→解は区間[m,b]に存在． (解の存在区間が半分になり，解に近づいた)

18 2分法 概要 (4) 新しい区間を[a,b]とし， これが十分に狭いか調べる． 十分に狭ければ終了．
　　これが十分に狭いか調べる． 　　十分に狭ければ終了． 　　狭くなければ新区間を用いて(2)に戻る． ・初期区間[a,b]が定められないと，2分法は使えない．

19 2分法の例 f (x) = 0.1x3+x-16 とし f (x) = 0 の解を探す

20 2分法の例 f (x) = 0.1x3+x-16 (1) 初期の区間を[0,8]に定める． 解は[0,8]に存在する．
ただし，以下は既知であると仮定する． f (x)は単調増加であり実数解は1個 解は0～8の間に存在する (1) 初期の区間を[0,8]に定める． 解は[0,8]に存在する．

21 (8, f (8)) 解はこの区間に存在する (0, f (0)) 50 40 30 20 f (x) 10 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 -10 -20 x (0, f (0))

22 2分法の例 (2) 現在の区間 [0,8] の中心 4 に着目する． 解が 4 より小さいか，大きいかを調べる．
　　解が 4 より小さいか，大きいかを調べる． 　　f (4) = -5.6 ＜ 0 　　なので，4 は解としては小さすぎた． 　　解は4より大きく，[4,8]に存在する． 　　(区間は半分に狭まった)

23 f (x) は単調増加 なので， 解はこの区間に 存在しない. f (x) は単調増加 なので， 解はこの区間に 存在する 50 40 30
20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

24 2分法の例 (3) 現在の区間 [4,8] の中心 6 に着目する． 解が 6 より小さいか，大きいかを調べる．
　　解が 6 より小さいか，大きいかを調べる． 　　f (6) = 11.6 > 0 　　なので，6 は解としては大きすぎた． 　　解は6より大きく，[4,6]に存在する． 　　(区間はさらに半分に狭まった)

25 50 40 解はこの区間に 存在する 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

26 2分法の例 [4,6]の中間値 5 を 試す． f (5) = 1.5 > 0 で， 解は [4,5]に 存在する． 50 40 30
20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

27 2分法の例 [4,5]の中間値 4.5 を 試す． f (4.5) = -2.3875 < 0 で， 解は [4.5,5]に存在する．
50 [4,5]の中間値 4.5 を 試す． f (4.5) = < 0 で， 解は [4.5,5]に存在する． 40 30 20 f (x) 10 1 2 3 4 5 6 7 8 -10 -20 x

28 2分法の例 以下同様に繰り返し， 解が存在する区間を狭めていく． 区間が十分に小さくなったら終了する．

29 2分法の手順 方程式を f (x) = 0 とする (1)初期値(初期区間) xmin0 と xmax0定める．
すなわち，f (xmin0) f (xmax0)＜0 である． ここでは f (x)が単調増加関数であり， f (xmin0)＜０， f (xmax0)＞0 である例を扱う．

30 2分法の手順 (2) xmin0 と xmax0の中間値である xmid0 = (xmin0+xmax0)/2 を求める．

31 2分法の手順 (3) f (xmid0) を求め， f (xmid0)＜0 か f (xmid0)＞0 かを調べる．
・ f (xmid0)＜0 なら，解は xmid0 より大きい． 　解は区間は[xmid0 , xmax0]に存在する． 　xmin1=xmid0，xmax1=xmax0， ・ f (xmid0)＞0 なら，解は xmid0 より小さい． 新しい区間を[xmin1, xmax1]とする．

32 2分法の手順 (4) 解は区間 [xmin1 , xmax1]に存在している． 新しい区間が十分に狭ければ終了する． 以下同様に，
xmid1 = (xmin1+xmax1)/2 を求め， 解がf (xmid1)より小さいか，大きいかを調べ，さらに狭い新しい区間を求めていく． 区間が十分に狭くなったら終了．

33 2分法の特徴 1回繰り返すたびに解の存在する区間が半分に減っていく． 初期値が指定できれば必ず収束する． 収束の速度を予想できる．
これは他の手法と比べて収束が速いとは言えない． 初期値が指定できれば必ず収束する． 収束の速度を予想できる．

34 例 f (x) = x3-10 とする. f (x) = 0 の解を探す． 解は[0, 4]にあるのは既知であるとする．
[0,4]の中間2に着目. f (0)<0, f (2)>0, f (4)>0 なので解は[0,2] [0,2]の中間1に着目. f (0)<0, f (1)<0, f (2)>0 なので解は[1,2]

35 練習 2 f (x) = -x2+10 とする. f (x) = 0 の解を探す． 解は[-2,6]にあるのは既知であるとする．
2分法で解の範囲を狭めていく場合の，解の範囲の推移を記せ． 解の範囲の長さが1以下になったら終了． おまけ：ロンドン(London)はどこの国の首都？

36 解答 2 [-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になったので終了．

37 はさみうち法 Regula Falsi Method

38 はさみうち法 反復法の一種． 初期値の区間内に解が存在すれば必ず収束し，必ず近似解が求まる． 収束速度は2分法より速いと期待される
区間の長さはゼロに収束しない (2分法と異なる) 収束速度は2分法より速いと期待される 必ずしも速いとは限らない 2分法と似ているが，次の候補に1次近似を用いる

39 はさみうち法の前に 点(x0 , y0)を通り，傾きaの直線の式は y - y0 = a ( x - x0)
2点(x0 , y0)と(x1 , y1) を通る直線の傾きと式は 傾き 直線の式

40 はさみうち法 方程式を f (x) = 0 とする (1) 解が存在する区間[a,b]を定める．
(2) 2点 ( a , f (a) ) と ( b , f (b) ) を通る直線を　　求め，これを y = f (x) の近似直線とする． 　　近似直線がx軸と交わる点(m,0)を求める． 近似直線と y = f (x) が近ければ， mは解と近いことが期待される．

41 はさみうち法 2点( a , f (a) )と( b , f (b) ) を通る近似直線は 一次方程式 を解く 結果 となる
近似直線がx軸と交わる点(m,0)を求めるには 一次方程式 を解く 結果 となる

42 はさみうち法 (3) 解がmより小さいか大きいか調べる． ・ mより小さい→解は区間[a,m]に存在． (b-m) が十分に小さければ終了
　・ mより大きい→解は区間[m,b]に存在． (m-a) が十分に小さければ終了 (4) 新しい区間を[a,b]として， 　　これを用いて (2) に戻る

43 はさみうち法の例 f (x) = 0.1x3+x-50 とし f (x) = 0 の解を探す

44 はさみうち法の例 f (x) = 0.1x3+x-50 (1) 初期の区間を[0,8]に定める． 解は[0,8]に存在する．
ただし，以下は既知であると仮定する． f (x)は単調増加であり実数解は1個 解は0～8の間に存在する (1) 初期の区間を[0,8]に定める． 解は[0,8]に存在する．

45 解はこの区間に存在する f (0) より f (8) の方が 0 に近いので， x=0 より x=8 の方が，解に近いと期待される．

46 はさみうち法の例 (2) 2点(0, f (0) ) と (8, f (8) ) を通る近似直線を引く．
これがx軸と交わる点を(m0,0)とし，m0に着目する．

47 はさみうち法の例 f (0)= -50 ，f (8)=9.2 であり， (0, -50) と (8, 9.2) を通る直線は
x軸と交わる点を(m0,0)のm0を求めるには を解く 結果，m0 ≒ 6.76

48 はさみうち法の例 (3) 解がm0より小さいか，大きいかを調べる． f (m0) ≒ -12.40 なので， m0は解としては小さすぎた．

49 解はこの区間に 存在する 2分法では， [0,8]の中央の4を 用いて調査する． はさみうち法では， 近似直線の x切片(m0)を

50 はさみうち法の例 (4) 解は [m0,8]に存在する． (m0, f (m0)) と (8, f (8)) を通る近似曲線の
x切片(m1,0)を求める． m1 ≒ 7.47 , f (m1) ≒ なので， m1は解としては小さすぎた． 解はm1より大きく，[m1, 8]に存在する．

51 解はこの区間に 存在する

52 はさみうち法が2分法より効率が悪い例 はさみうち法では この点が解に近いと 期待して調査する 2分法では， 中央の4を 調査する

53 はさみうち法の特徴 初期値が指定できれば必ず解に収束する． 区間の長さはゼロに収束しない
2分法より速い収束が期待できるが，必ず速いわけではない． 「f (m)が十分に小さいこと」を収束条件とすることもある． 厳密には「(b-m)，(m-a) や| f (m)|が十分に小さいこと」は，解の精度を保証していない．

54 Newton-Raphson法 Newton-Raphson Method

55 Newton-Raphson法 反復法の一種． 必ず収束するとは限らない． 初期値が解に近ければ高速に収束する．
n回目の調査で使った点から1次近似直線を引き，そのx切片をn+1回目の候補とする 初期値は1個の値． 2分法やはさみうち法の様に区間ではない．

56 Newton-Raphson法 方程式を f (x) = 0 とする (1) 解に近い値 a0 を定める．
(2) y = f (x) に対して，( an , f (an) ) で接する 　　接線(1次近似直線)を引く． 　　接線は y – f (an) = f '(an) (x–an)

57 Newton-Raphson法 (3) 近似直線がx軸と交わる点(an+1,0)を求める．
　　すなわち，折線 y – f (an) = f ’(an) (x–an) が 　　y=0となる x を求め，その x がan+1である． 近似直線と y = f (x) が近ければ， an+1は解に近いことが期待される．

58 Newton-Raphson法 (4) |an-an+1| が十分に小さければ，終了． 　　小さく無ければ，(2)に戻る

59 Newton-Raphson法の例 f (x) = 0.1x3+x-5 とし f (x) = 0 の解を探す

60 Newton-Raphson法の例 f '(x) = 0.3x2+1 初期値a0=7とする．
y = f (x) と ( 7, f (7) )で接する接線を引き，接線がx軸と交わる点(a1, 0)を求め， このa1に着目する．

61 Newton-Raphson法の例 接線のx切片は ただし，( 7, f (7) )における接線は
y – f (7) = f ’(7)(x – 7) 接線のx切片は ≒ 4.69

62 近似直線 と y= f (x) が 近ければ， 近似直線のx切片は 解に近いと期待される． ( 7, f (7) ) ( 7, f (7) )で 接する接線 次に着目する点

63 Newton-Raphson法の例 y = f (x) と (a1, f (a1) )で接する接線を引き，接線がx軸と交わる点(a2, 0)を求め， 次は，このa2に着目する．

64

65

66 Neton-Raphson法で収束しない例
接点 接線 次の候補 次の候補 接線 接点

67 Newton-Raphson法の特徴 接線(1次近似直線)が，方程式と近ければ，高速に収束していく． 初期値が解に近くないと，収束しない．
傾きがゼロの箇所においても使えない． 「 | f (an)|が十分に小さいこと」を収束条件することもある． 厳密には「|an-an+1|や f (m)が十分に小さいこと」は，解の精度を保証していない．