プログラミング論 I

プログラミング論 I
補間
http://www.ns.kogakuin.ac.jp/~ct13140/Prog
補間
C-2
補間
• (1) n次多項式での近似
– テイラー展開
• (2) 関数の補間
– ラグランジュの補間法
C-3
補間とは
• (x0, f (x0)), (x1, f (x1),…(xn, f (xn))が既知の
とき，
それ(x0, x1,… xn)以外の点における関数の値
を求める(予測する)
C-4
補間の例
x=6
10
f(x)
8
(10, 6.6)
6
4
f (5), f (10)が既知．
f (6)が必要になったら？
近くの f (5)=2.4で代用する？
(5, 2.4)
2
0
0
5
10
15
x
20
25
30
C-5
f (5)と f (10)からf (6)を補間する
おそらく f (5)より，
一次近似の方が正確．
さらに正確な補間方法は？
7
6
(10,6.6)
f(x)
5
直線を引いて(一次近似)，
x=6 における値を予想．
4
3
2
(5,2.4)
f (5)=2.4 で代用
1
4
6
8
x
10
12
C-6
(1) n次多項式での近似
・近似は補間と密接な関係．
・関数をn次多項式で近似する．
関数の式が既知であることが前提
・テイラー展開
C-7
一次式で近似
接線
1.5
y =f (a)+f '(a)(x-a)=g(x)
1
0.5
y
近似に
用いた点
0
0
-0.5
-1
y = f (x)
x

2

y = f (x) の接線 y = g(x)は，y =f (x)の一次近似線．
f (a) = g(a) かつ f '(a) = g'(a) となっている．
つまり，x=a において，
「yの値」と「傾き(一階微分)」が一致している．
C-8
二次式で近似
1.5
y =f (a)+f '(a)(x-a)=g(x)
1
0.5
y
近似に
用いた点
0
0
-0.5
-1
x
y = f (x)

2
y  f (a )  f ' ( a )( x  a )
1
 f ' ' ( a )( x  a ) 2
2
 h( x )
x=aに近いほど
近似は正確

y = h(x)は，y =f (x)の二次近似曲線．
(y=f (x)を近似した二次曲線)
f (a) = h(a) かつ f '(a) = h'(a) かつ f ''(a) = h''(a)．
x=a において「y」と「一階微分」と「二階微分」が
が一致している．一次近似よりより正確な近似．
C-9
三次式で近似
i ( x) 
i ' ( x) 
i ' ' ( x) 
i ' ' ' ( x) 
1
1
2
f (a)  f ' (a )(x  a )  f ' ' (a )(x  a )  f ' ' ' (a)(x  a) 3
2
6
1
f ' (a )  f ' ' (a)(x  a)  f ' ' ' (a)(x  a) 2
ここは
2
xの式
f ' ' (a )  f ' ' ' (a )(x  a )
ここは
定数である
f ' ' ' (a)
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階微分が一致．
C-10
テイラー展開 Taylor expansion
• f (x) を以下の級数に展開する
 f (k ) (a)

k 0
k!
( x  a)
k
a=0の場合，
マクローリン展開
1
1
2
3
f (a )  f ' (a )(x  a )  f ' ' (a )(x  a )  f ' ' ' (a )(x  a )
2
6
1
1 (5)
4

f ' ' ' ' (a )(x  a ) 
f (a )(x  a ) 5  ...
24
120
C-11
テイラー展開
• テイラー展開を有限個の級数で打ち切る
 n1 f (k ) (a)

f ( x)   
( x  a) k   Rn
 k 0 k!



Rnはラグランジュの剰余項
• lim Rn =0のとき， f ( x) 
n
 f ( k ) (a)

k 0
k!
( x  a) k
Rn
換言すると lim
n =0のとき，展開の次数を上げていくと
より正確な近似になっていく．
C-12
テイラー展開近似線
1次
2
2次
1.5
1
0次
0.5
5次
6次
0
-0.5
-1
-1.5
-2
0

0.5
2
1
y=sin(x)
3次
4次
C-13
n次多項式による近似
• 基本的に近似点の近傍では次数を上げる
ほど，正確な近似になる
C-14
単語の説明
10
f(x)
8
6
4
この区間を
補うことを
補外，外挿
という
この区間を補うことを
補間，内挿という
2
0
0
5
10
15
x
20
25
30
C-15
(2) 関数の補間
関数の式が未知の場合も使える
C-16
補間
既知の f (xi)から，f (6)を補間する例を考える．
10
f(x)
8
6
4
2
0
0
5
10
15
x
20
25
30
C-17
0次補間
x=6に一番近い，x=5を採用する．
7
6
既知の点
f(x)
5
既知の点
4
3
f (6)を補間
2
f (6) = f (5)
1
4
6
8
x
10
12
C-18
1次補間
(5, f (5)), (10, f (10)) を通る1次関数(直線)で補間する．
7
近似直線を用いて
f (6)を補間
6
既知の点
f(x)
5
既知の点
4
3
f (5)  f (10)
f (6) 
(6  5)  f (a)
5  10
2
1
4
6
8
x
10
12
C-19
1次補間
• 2点(a , f (a))と(b , f (b))より，x=mにおける
yの値 f (m)を予測する
• 2点(a , f (a))と(b , f (b)) を通る直線の式
f (a )  f (b)
y  f (a) 
( x  a)
a b
これに，x=mを代入して，
f (a)  f (b)
f ( m) 
(m  a)  f (a)
a b
C-20
2次補間
3点を通る2次関数を求め，その2次関数(放物線)で補間する．
8
f(x)
6
(5, f (5)), (10, f (10)),
(15, f (15)) を通る2次曲線．
これを近似曲線とする
4
近似曲線を用いて
f (6)を補間
2
0
4
6
8
10
12
x
14
16
C-21
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次曲線は求
まる．
後で，別の方法(ラグランジュの補間法)を紹介する C-22
2次補間
• 求めた2次近似曲線 y=g (x) に，
x=m を代入し，g(m)を補間値として用いる．
• 1次補間(直線による予測)より，正確である
ことが期待できる．
C-23
ラグランジュの補間法
既知の点n+1個を全て通る
n次式を求める
C-26
ラグランジュの補間法
• n+1個の点を通る，n次方程式P(x)で補間
通る点を(x0, f (x0)), (x1, f (x1)),…, (xn, f (xn)) として
以下の方法により，P(x)が求まる
P( x) 
n
 f ( xk ) Lk ( x)
k 0
x  xm
ただし Lk ( x)  m
0 xk  xm
n
mk
C-27
ラグランジュの補間法
x  xm
Lk ( x)  
m  0 xk  xm
n
m k
( x  x0 )  ( x  xk 1 )(x  xk 1 )  ( x  xn )

( xk  x0 )  ( xk  xk 1 )(xk  xk 1 )  ( xk  xn )
(xｰxk)以外
(xkｰxk)以外
Lk(x)の分子は x の n次多項式．分母は定数．
よって，Lk(x)はxのn次多項式．
f (xk) は定数．よって， f (xk)Lk(x)は x の n次多項式．
よって，P ( x) 
n
 f ( xk ) Lk ( x)は x の n次多項式．
k 0
C-28
ラグランジュの補間法の例
• 4点(x0, f (x0)), (x1, f (x1)), (x2, f (x2)), (x3, f (x3))を
通る，3次曲線の方程式 y = P(x) は，
( x  x1 )(x  x2 )(x  x3 )
y  P ( x)  f ( x0 )
( x0  x1 )(x0  x2 )(x0  x3 )
( x  x0 )(x  x2 )(x  x3 )
 f ( x1 )
( x1  x0 )(x1  x2 )(x1  x3 )
( x  x0 )(x  x1 )(x  x3 )
 f ( x2 )
( x2  x0 )(x2  x1 )(x2  x3 )
( x  x0 )(x  x1 )(x  x2 )
 f ( x3 )
( x3  x0 )(x3  x1 )(x3  x2 )
(xｰx2)
以外
(x2ｰx2)
以外
C-29
ラグランジュの補間法の例
• y = P(x) は，(x2, f (x2))を通るか確認
( x  x1 )(x  x2 )(x  x3 )
y  P ( x2 )  f ( x0 )
( x0  x1 )(x0  x2 )(x0  x3 )
( x  x0 )(x  x2 )(x  x3 )
 f ( x1 )
( x1  x0 )(x1  x2 )(x1  x3 )
y=P(x)は
(x2 , f (x2))
を通る
3次曲線  f ( x2 )
( x  x0 )(x  x1 )(x  x3 )
( x2  x0 )(x2  x1 )(x2  x3 )
( x  x0 )(x  x1 )(x  x2 )
 f ( x3 )
( x3  x0 )(x3  x1 )(x3  x2 )
ゼロ
ゼロ
１
(x=x2なら
分子と分母
が一致)
ゼロ
= f (x0)×0 + f (x1)×0 + f (x2)×1 + f (x3)×0 = f (x2) C-30
ラグランジュの補間法の例
10
f(x)
8
4次曲線で
近似し，補間
6
4
2
0
0
5
10
15
x
20
25
30
C-31
ラグランジュ補間法の問題点
1.5
補間曲線は，
確かに
全ての点を
通過している
y
1
端の方は
全く近く
いない
1
2
x 1
を11点を用いて
ラグランジュ補間法で補間
y=1/(x2+1)
0.5
Lagrange補間
補間点
0
-5
-3
-1
-0.5
1
3
正解
5
ラグランジュ補間法
による予想 C-32
ラグランジュの補間法の問題点
• 補間の点数が増えると，激しく振動する
– 点数が増えると，
(全ての補間点を通過しているのは事実だが)
補間のn多項式の次数が大きくなり振動する．
– 次数が高いほど好ましいのではない．
C-33
(3次)スプライン補間
1.5
この区間を
3次関数
で補間
区間ごとに，別々の
3次多項式を用意し
補間する
1
y=1/(x2+1)
この区間を
3次関数
で補間
補間点
0.5
0
-5
-3
-1
1
-0.5
3
5
C-34

Download Report