非線形方程式の近似解 (2分法，はさみうち法，Newton-Raphson法)

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

1 非線形方程式の近似解 (2分法，はさみうち法，Newton-Raphson法)
プログラミング論 非線形方程式の近似解 (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 概要 非線形方程式の近似解の求め方 2分法 はさみうち法 Newton-Raphson法

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

6 非線形方程式の近似解 非線形方程式 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

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

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

9 2分法 Bisection Method

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

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

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

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

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

15 (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))

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

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

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

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

20 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

21 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

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

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

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

25 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]とする．

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

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

28 例 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]

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

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

31 はさみうち法 Regula Falsi Method

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48 Newton-Raphson法 Newton-Raphson Method

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

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

51 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は解に近いことが期待される．

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

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

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

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

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

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

58

59

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

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

62 復習：2分法 2分法 f (x)=ｰx3ｰx2+5x+20 として f (x)=0 の解を探す (注意:f (x) は単調増加ではない)
ただし解が[-4,4]に存在は既知

63 復習：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]に

64 復習：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; 繰り返しの先頭に戻る