Document

プログラミング論 I
2009年5月21日
補間
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2009
補間
2
補間
• (1) n次多項式での近似
– テイラー展開
• (2) 関数の補間
– ラグランジュの補間法
3
補間とは
• (x0, f (x0)), (x1, f (x1),…(xn, f (xn))が既知の
とき，
それ(x0, x1,… xn)以外の点における関数の値
を求める(予測する)
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
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
6
(1) n次多項式での近似
・近似は補間と密接な関係．
・関数をn次多項式で近似する．
関数の式が既知であることが前提
・テイラー展開
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の値」と「傾き(一階微分)」が一致している．
8
二次式で近似
y  f (a)  f ' (a)( x  a)
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
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」と「一階微分」と「二階微分」が
が一致している．一次近似よりより正確な近似．
9
三次式で近似
1
1
2
i ( x)  f (a )  f ' (a )( x  a )  f ' ' (a )( x  a )  f ' ' ' (a )( x  a ) 3
2
6
1
i ' ( x)  f ' (a )  f ' ' (a )( x  a )  f ' ' ' (a )( x  a ) 2
ここは
2
xの式
i ' ' ( x)  f ' ' (a )  f ' ' ' (a )( x  a )
ここは
i ' ' ' ( x)  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階微分が一致．
10
テイラー展開 Taylor expansion
• f (x) を以下の級数に展開する


k 0
f
(k )
(a)
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
5

f ' ' ' ' (a )( x  a ) 
f (a )( x  a)  ...
11
24
120
テイラー展開
• テイラー展開を有限個の級数で打ち切る
 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
lim R
換言すると nn =0のとき，展開の次数を上げていくと
より正確な近似になっていく．
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次
13
n次多項式による近似
• 基本的に近似点の近傍では次数を上げる
ほど，正確な近似になる
14
単語の説明
10
f(x)
8
6
4
この区間を
補うことを
補外，外挿
という
この区間を補うことを
補間，内挿という
2
0
0
5
10
15
x
20
25
30
15
(2) 関数の補間
関数の式が未知の場合も使える
16
補間
既知の f (xi)から，f (6)を補間する例を考える．
10
f(x)
8
6
4
2
0
0
5
10
15
x
20
25
30
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
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
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
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
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次曲線は求
まる．
後で，別の方法(ラグランジュの補間法)を紹介する 22
2次補間
• 求めた2次近似曲線 y=g (x) に，
x=m を代入し，g(m)を補間値として用いる．
• 1次補間(直線による予測)より，正確である
ことが期待できる．
23
練習 0
y=f (x)は，2点 (1, 1), (2,4) を通る．
f (1.5) と f (3) を，一次補間(補外)
により予測せよ 8
7
6
f(x)
5
4
3
2
1
0
0
1
2
x
3
24
解答 0
• 両点を通る直線
傾き
4 1
3
2 1
(1, 1)を通り，傾き3の式は
y  1  3( x  1)
y  3x  2
x = 1.5 のとき，y = 2.5
x = 3 のとき，y = 7
25
ラグランジュの補間法
既知の点n+1個を全て通る
n次式を求める
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
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
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ｰx2)
以外
(x2ｰx2)
以外
( x  x0 )( x  x1 )( x  x2 )
 f ( x3 )
( x3  x0 )( x3  x1 )( x3  x2 ) 29
ラグランジュの補間法の例
• y = P(x) は，(x2, f (x2))を通るか確認
( x  x1 )( x  x2 )( x  x3 )
y  P( x2 )  f ( x0 )
( x0  x1 )( x0  x2 )( x0  x3 )
y=P(x)は
(x2 , f (x2))
を通る
3次曲線
( 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なら
分子と分母
が一致)
ゼロ
= f (x0)×0 + f (x1)×0 + f (x2)×1 + f (x3)×0 = f (x2)30
ラグランジュの補間法の例
10
f(x)
8
4次曲線で
近似し，補間
6
4
2
0
0
5
10
15
x
20
25
30
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
ラグランジュ補間法
による予想32
ラグランジュの補間法の問題点
• 補間の点数が増えると，激しく振動する
– 点数が増えると，
(全ての補間点を通過しているのは事実だが)
補間のn多項式の次数が大きくなり振動する．
– 次数が高いほど好ましいのではない．
33
(3次)スプライン補間
1.5
この区間を
3次関数
で補間
区間ごとに，別々の
3次多項式を用意し
補間する
1
y=1/(x2+1)
この区間を
3次関数
で補間
補間点
0.5
0
-5
-3
-1
1
-0.5
3
5
34
練習 1
• 3点 (x0, y0), (x1, y1), (x2, y2) を通る，2次方
程式を書け．
– ただし，  記号と， 記号は使用しないこと
35
解答 1
( x  x1 )( x  x2 )
f ( x0 )
( x0  x1 )( x0  x2 )
( x  x0 )( x  x2 )
 f ( x1 )
( x1  x0 )( x1  x2 )
( x  x0 )( x  x1 )
 f ( x2 )
( x2  x0 )( x2  x1 )
36

Download Report