2008年6月12日 非線形方程式の近似解 Newton-Raphson法

Presentation on theme: "2008年6月12日 非線形方程式の近似解 Newton-Raphson法"— Presentation transcript:

1 2008年6月12日 非線形方程式の近似解 Newton-Raphson法
プログラミング論 I 2008年6月12日 非線形方程式の近似解 Newton-Raphson法

2 for文復習 回数が決まっている繰り返し処理(n回とする)は, 必ず for(i=0; i<n; i++) とするのが分かりやすい(ことが多い)．

3 for文復習 100, 102, 104, の50個を表示 例 A for(i=100; i<200; i+=2){ printf("%d\n", i); }

4 for文復習 100, 102, 104, 106...198 の50個を表示 例 B for(i=0; i<50; i++){
x = i*2; printf("%d\n", x); }

5 練習 0 右の様に表示されるプログラムを 記述せよ． 倍精度浮動小数点の表示は， double x; printf("%lf\n", x);
右の様に表示されるプログラムを 記述せよ． 倍精度浮動小数点の表示は， double x; printf("%lf\n", x);

6 解答 0 int i; double x; for(i=0; i<10; i++){ x = 6.0 + 0.3*i;
printf("%lf\n", x); }

7 概要 非線形方程式の近似解 Newton-Raphson法 補間 n次多項式での近似 テイラー展開 関数の補間 ラグランジュの補間法

8 Newton-Raphson法 Newton-Raphson Method

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

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

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

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

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

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

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

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

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

18

19

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

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

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

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

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

25 補間

26 補間 (1) n次多項式での近似 テイラー展開 (2) 関数の補間 ラグランジュの補間法

27 補間とは (x0, f (x0)), (x1, f (x1),…(xn, f (xn))が既知のとき，
それ(x0, x1,… xn)以外の点における関数の値を求める(予測する)

28 補間の例 x=6 (10, 6.6) f (5), f (10)が既知． f (6)が必要になったら？
8 (10, 6.6) f(x) 6 4 f (5), f (10)が既知． f (6)が必要になったら？ 近くの f (5)=2.4で代用する？ (5, 2.4) 2 5 10 15 20 25 30 x

29 f (5)と f (10)からf (6)を補間する おそらく f (5)より， 一次近似の方が正確． (10,6.6)
さらに正確な補間方法は？ (10,6.6) 直線を引いて(一次近似)， x=6 における値を予想． (5,2.4) f (5)=2.4 で代用

30 ・近似は補間と密接な関係． ・関数をn次多項式で近似する． 関数の式が既知であることが前提 ・テイラー展開

31 一次式で近似 接線 y =f (a)+f '(a)(x-a)=g(x) y = f (x) 近似に 用いた点
1.5 y =f (a)+f '(a)(x-a)=g(x) 1 y = f (x) 0.5 近似に 用いた点 y x y = f (x) の接線 y = g(x)は，y =f (x)の一次近似線． f (a) = g(a) かつ f '(a) = g'(a) となっている． つまり，x=a において， 「yの値」と「傾き(一階微分)」が一致している． -0.5 -1

32 二次式で近似 y =f (a)+f '(a)(x-a)=g(x) 近似に x=aに近いほど 用いた点 y = f (x) 近似は正確
1.5 y =f (a)+f '(a)(x-a)=g(x) 1 0.5 近似に 用いた点 x=aに近いほど 近似は正確 y = f (x) y x y = h(x)は，y =f (x)の二次近似曲線． (y=f (x)を近似した二次曲線) f (a) = h(a) かつ f '(a) = h'(a) かつ f ''(a) = h''(a)． x=a において 「y」と「一階微分」と「二階微分」が が一致している．一次近似よりより正確な近似． -0.5 -1

33 三次式で近似 y = i(x)は，y =f (x)の三次近似曲線．
ここは xの式 ここは 定数である y = i(x)は，y =f (x)の三次近似曲線． f (a)=i (a)，f '(a)= i (a)， f ''(a)= i ''(a)，f '''(a)=i '''(a) よって，x=a において，yの値，1～3階微分が一致．

34 テイラー展開 Taylor expansion
f (x) を以下の級数に展開する a=0の場合， マクローリン展開

35 テイラー展開 テイラー展開を有限個の級数で打ち切る Rnはラグランジュの剰余項 =0のとき，
換言すると =0のとき，展開の次数を上げていくと より正確な近似になっていく．

36 テイラー展開 近似線 1次 2次 0次 5次 6次 y=sin(x) 4次 3次

37 n次多項式による近似 基本的に近似点の近傍では次数を上げるほど，正確な近似になる

38 単語の説明 この区間を 補うことを 補外，外挿 という この区間を補うことを 補間，内挿という

39 (2) 関数の補間 関数の式が未知の場合も使える

40 補間 既知の f (xi)から，f (6)を補間する例を考える．

41 0次補間 x=6に一番近い，x=5を採用する． 既知の点 既知の点 f (6)を補間 f (6) = f (5)

42 1次補間 (5, f (5)), (10, f (10)) を通る1次関数(直線)で補間する． 近似直線を用いて f (6)を補間 既知の点

43 1次補間 2点(a , f (a))と(b , f (b))より，x=mにおける yの値 f (m)を予測する

44 2次補間 3点を通る2次関数を求め，その2次関数(放物線)で補間する． (5, f (5)), (10, f (10)),
これを近似曲線とする 近似曲線を用いて f (6)を補間

45 2次補間 3点(x0, y0), (x1, y1), (x2, y2) を通る2次曲線の求め方(の例)
2次曲線は y=ax2+bx+c で表せる． (3個の未知数が決まれば，2次曲線が決まる) (x, y)=(x0, y0), (x, y)=(x1, y1), (x, y)=(x2, y2)を代入すれば，方程式が3本立つ． よって，3元1次連立方程式を解けば2次曲線は求まる． 後で，別の方法(ラグランジュの補間法)を紹介する

46 2次補間 求めた2次近似曲線 y=g (x) に， x=m を代入し，g(m)を補間値として用いる．
1次補間(直線による予測)より，正確であることが期待できる．

47 練習 1 y=f (x)は，2点 (1, 1), (2,4) を通る． f (1.5) と f (3) を，一次補間(補外) により予測せよ

48 解答 1 両点を通る直線 傾き (1, 1)を通り，傾き3の式は x = 1.5 のとき，y = 2.5 x = 3 のとき，y = 7

49 ラグランジュの補間法 既知の点n+1個を全て通る n次式を求める

50 ラグランジュの補間法 n+1個の点を通る，n次方程式P(x)で補間
通る点を(x0, f (x0)), (x1, f (x1)),…, (xn, f (xn)) として 以下の方法により，P(x)が求まる ただし

51 ラグランジュの補間法 (xｰxk)以外 (xkｰxk)以外 Lk(x)の分子は x の n次多項式．分母は定数．
f (xk) は定数．よって， f (xk)Lk(x)は x の n次多項式． よって，　　　　　　　　　　　　　は x の n次多項式．

52 ラグランジュの補間法の例 4点(x0, f (x0)), (x1, f (x1)), (x2, f (x2)), (x3, f (x3))を通る，3次曲線の方程式 y = P(x) は， (xｰx2) 以外 (x2ｰx2) 以外

53 ラグランジュの補間法の例 y = P(x) は，(x2, f (x2))を通るか確認
ゼロ ゼロ y=P(x)は (x2 , f (x2)) を通る 3次曲線 １ (x=x2なら 分子と分母 が一致) ゼロ = f (x0)×0 + f (x1)×0 + f (x2)×1 + f (x3)×0 = f (x2)

54 ラグランジュの補間法の例 4次曲線で 近似し，補間

55 ラグランジュ補間法の問題点 を11点を用いて ラグランジュ補間法で補間 端の方は 全く近く いない 補間曲線は， 確かに 全ての点を
通過している を11点を用いて ラグランジュ補間法で補間 端の方は 全く近く いない y=1/(x2+1) ラグランジュ補間法 による予想 正解

56 ラグランジュの補間法の問題点 補間の点数が増えると，激しく振動する 点数が増えると， (全ての補間点を通過しているのは事実だが)
補間のn多項式の次数が大きくなり振動する． 次数が高いほど好ましいのではない．

57 (3次)スプライン補間 区間ごとに，別々の 3次多項式を用意し 補間する この区間を 3次関数 で補間 この区間を 3次関数 で補間
y=1/(x2+1) この区間を 3次関数 で補間 補間点

58 練習 2 3点 (x0, y0), (x1, y1), (x2, y2) を通る，2次方程式を書け．
ただし，　　記号と，　記号は使用しないこと

59 解答 2