第9回

計算情報学Ｉ
名古屋大学 情報文化学部
自然情報学科３年
第９回
鈴木泰博
情報文化学部・大学院情報科学研究科
複雑系科学専攻
Science of
interactions
Agenda
計算情報学 Ｉ 第９回
1.
2.
3.
4.
5.
6.
7.
前回のつづき(ラグランジュ補間）
数値積分とは
離散近似
台数公式
シンプソンの公式
ロンバーグ積分法
チェックテスト（第2回）について
Science of
interactions
ラグランジュ補間
一般にＮ＋１の場合関数 lj(x),(j=1,2,3,…N)を以下のように定義する。
l j ( x)
( x x0 )( x x1 ) L ( x x j 1 )( x x j 1 ) L ( x xN )
(xj
x0 )( x j
x1 ) L ( x j
x j 1 )( x j
x j 1 )L( x j
xN )
ここでlj(x)は、
l j ( x)
1 (i
0 (i
j)
j)
N
を満たす。そこで、PN(x)を、 PN ( x)
y j l j ( x) と定義すると、高々Ｎ次の多項式となり、
j 0
PN ( x j )
yj
を満たす。この多項式をラグランジュの補間多項式とよぶ。
⇒例を考えるとわかります。
Science of
interactions
ラグランジュ補間
N
PN ( x)
y j l j ( x)
j 0
m=3の場合
p3 ( x)
演習
( x x2 )( x x3 )
f1
( x1 x2 )( x1 x3 )
( x x1 )( x x3 )
f2
( x2 x1 )( x2 x3 )
( x x1 )( x x2 )
f3
( x3 x1 )( x3 x2 )
P3(x)が(x 1,f 1), (x 2,f 2),(x 3,f 3)を通ることを確かめよ。
Science of
interactions
演習
ラグランジュ補間
演習: 以下のx kとf kに対する補間多項式を求めよ。
xk 0 1 2
fk 1 0 1
ヒント：m=3の場合のラグランジュ多項式
p3 ( x)
( x x2 )( x x3 )
f1
( x1 x2 )( x1 x3 )
( x x1 )( x x3 )
f2
( x2 x1 )( x2 x3 )
( x x1 )( x x2 )
f3
( x3 x1 )( x3 x2 )
Science of
interactions
解答
ラグランジュ補間
演習: 以下のx kとf kに対する補間多項式を求めよ。
xk
0
1
2
fk
1
0
1
p3 ( x)
( x x2 )( x x3 )
f1
( x1 x2 )( x1 x3 )
( x x1 )( x x3 )
f2
( x2 x1 )( x2 x3 )
( x x1 )( x x2 )
f3
( x3 x1 )( x3 x2 )
より、
( x 1)( x 2)
( x 0)( x 2)
1
0
(0 1)(0 2)
(1 0)(1 2)
1
1
( x 1)( x 2)
x( x 1) ( x 1) 2
2
2
p3 ( x)
( x 0)( x 1)
1
( 2 0)(2 1)
Science of
interactions
ラグランジュ補間の誤差
1
f ( x) P ( x)
(n 1)!
( x) f n 1 ( )
n
where, ( x)
k 0
( x xk )
証明の概略
H ( x)
f ( x) P ( x)
where, G ( x)
( x)G ( x)
f ( x) P ( x)
( x)
とおくと、
H ( x) 0
H ( xk ) f ( xk ) P ( xk )
( xk )G ( xk )
0
H(x)はx, x 0,…,x nのn+2の点で0となる。
Science of
interactions
ラグランジュ補間の誤差
(つづき）
ロルの定理より
H’(z)はn+1の異なる点で0となる
H’’(z)はnの異なる点で0となる
H’’’(z)はn-1の異なる点で0となる。
…
H (n+1) (ξ)=0なるξがx,x 0,x 1,…,x nの区間内に存在
する。
H (n+1) (ξ) = f (n+1) (ξ) – π (n+1) (ξ)G(x)=0
また、P(x)はn次多項式だから0となり、
π (n+1) (ξ)=(n+1)!より、
H ( x) f ( x) P ( x)
1
( n 1)
G ( x)
f
( )
1
(n 1)!
f ( x) P ( x)
H ( x)
f ( x) P ( x)
( x)G ( x)
f ( x) P ( x)
where , G ( x)
( x)
( n 1)!
ルンゲの現象
1
(n 1)!
f ( n 1) ( ) ( x)
f ( n 1) ( ) ( x)
Science of
interactions
0
一般の場合
n点の補間
P ( x)
a0
a1 x a 2 x
2
L an x
n
命題: n点を通るn次多項式は唯一である。
証明: P(x)以外に与えられたn+1点を通るn次以下の多項式
をQ(x)とする。すると、P(x)とQ(x)の差は、D(x)=P(x)-Q(x)
となり、高々n次の多項式となる。
D(xk)=P(xk)-Q(xk)=fk – fk = 0, k=0,1,2,…,n
となるので、D(x)はn+1の零点を持つ。しかし、代数学の
基本定理より高々n次の多項式はnの零点しか持たない。
よって、恒等的にD(x)=0となるから、
P(xk)-Q(xk)=0より、P(x)=Q(x).
別証明：P(x)の係数行列はn次正方行列となる。この行列はVandermonde
行列式となるため、正則となり係数は一意に決まる。
Science of
interactions
積分とはナニカ？
積分F(x)
d
b
a
c
x1
x2
x3
x4
x1
x2
x3
積分公式
各種の積分法
積分とは求積であり、微分の逆演算である
求積
微係数
y = F(X)
原始関数
d
c
b
x4
d
c
b
a
a
x1
x2
x3
x4
x1
x2
x3
x4
Science of
interactions
y3
Si
x1
x2
台形公式
y4
h
2
x3
x4
S
Si
n
y0
y1
2
例: y = 1/x
y0
2
y1
y2
y2
2
y1
y2 L yn 1
y3
2
yn
h
2
L
yn 1
yn
2
h
Science of
interactions
台形公式
∼誤差と分割数の関係
台形公式＝折れ線補間…つまり１次のラグランジュ補間
被積分関数F(x)に対して台形公式では(xk, fk), (xk+1, fk+1)を結んだ折れ線の面積計算
しているから、
F ( x)
x xj
xj
xj
1
1
fj
x xj
xj
1
xj
fj
1
となる。F(x)の誤差はラグランジュ補間の誤差式より、
f ( x) F ( x)
f ( )
( x x j )( x x j 1 )
2
これより、誤差は
| f ( x) F ( x) |
と評価できる。
1
max | f ( ) | | ( x x j )( x x j 1 ) |
2 x j xj 1
Science of
interactions
台形公式の誤差の評価
xj
|
xj
1
xj
f ( x) dx
xj
1
max | f ( ) |
2
xj
xj
xj
a
xj
a
1
h
x
a
h
b a
N
|
xj
xj
1
b
sh
1
f ( x)dx
1
0
とおくと
1
0
1
xj
F ( x)dx |
xj
xj
1
1
xj
| f ( x) F ( x) | dx
| ( x x j )( x x j 1 ) | dx
| ( x x j )( x x j 1 )dx
| (a
sh a )(a
sh (a
h)) | hds...dx
(a
sh)ds
| s ( s 1)h 3 |ds
h3
6
xj
xj
1
max | f ( ) |
2
1
F ( x)dx |
xj
xj
1
xj
xj
1
| f ( x) F ( x) | dx
| ( x x j )( x x j 1 ) | dx
h3
max | f ( ) |
12
Science of
interactions
台形公式の誤差の評価
1
max | f ( ) | | ( x x j )( x x j 1 ) |
x
2 j xj 1
| f ( x) F ( x) |
より、この積分における誤差は、
|
…
分点数
xj
1
xj
f ( x)dx
xj
xj
1
max | f ( ) |
2
1
F ( x)dx |
xj
xj
1
例 F(x)=exp(x)
xj+1
xj
1
| f ( x) F ( x) | dx
| ( x x j )( x x j 1 ) | dx
3
xj
xj
h
1
b a
max | f ( ) |
N
12
12
N
3
max | f ( ) |
(b a ) 3
max | f ( ) |
2
12 N
台形公式を用いる場合、区間の分点数をふやしていくと、誤差は1/N2に比例
Science of
interactions
して小さくなる。つまり、Nを前の分点数の２倍(e.g.2,4,8,..)にしていくと効率がよくなる。
ニュートン・コーツの公式
(Newton-Cotes)
台形公式＝１次のラグランジュ補間
…
分点数
xj
では、さらに高次のラグランジュ補間を用いたら？
→ニュートン・コーツの公式
xj+1
次数
α0
α1
α2
α3
1
1/2
1/2
2
1/3
4/3
1/3
3
3/8
9/8
9/8
3/8
4
14/45
64/45
24/45
64/45
α5
誤差
O(h3)
O(h5)
O(h5)
14/45
O(h7)
Science of
interactions
シンプソンの公式
1つ飛ばし（2n）でスライドしてゆく
…
それらをすべて足し合わせる
ことにより、積分を行う。
⇒シンプソンの公式
xj-1 xj xj+1
この区間だけ2次のラグランジュ補間を行う。
⇒ニュートン・コーツは積分区間全体をＮ分点するのに対し、シンプソンの公式
では、２ｈの区間で積分区間を区切って、その部分の面積を2次のラグランジュ
Science of
補間を用いて求め、足し合わせる。
interactions
シンプソンの公式
P2 ( x)
( x x1 )( x x2 )
( x0 x1 )( x0 x2 )
f0
b
P2 ( x)
a
0
x0
a
x1
a
a
2h
x
a
sh
h
b a
2
hds
1
b
a
例：シンプソンの
公式
f
1 1
1
x1 )( x0
( x0
2
b
x2 )
a
4
h,
3
f ( x)dx
h
( f0
3
f2
( x x0 )( x x1 )
( x2 x0 )( x2 x1 )
f2
( x x1 )( x x2 )dx
2
2h))
1 2
1
3
(
s
1
)(
s
2
)
h
ds
h
2 0
3
2h
b
dx
f0
( x x0 )( x x2 )
( x1 x0 )( x1 x2 )
1
(a (a h))(a (a
h
0
x2
0
f1
0
(a
sh (a
h))(a
sh (a
2h))hds
1
h
3
2
h
( f0
3
4 f1
2 f2
4 f1
4 f3
f2 )
2 f4 L f 2n )
Science of
interactions
シンプソンの公式の誤差
| f ( x) F ( x) |
|
x0
a
x1
a
h
x2
a
2h
x
h
a sh
b a
2
b
dx
hds
xj
xj
1
1
max | f ( 3) ( ) | | ( x x0 )( x x1 )( x x2 ) |
3! x j x j 1
f ( x)dx
xj
xj
1
F ( x)dx |
xj
xj
1
| f ( x) F ( x) | dx
xj 1
1
( 3)
max | f ( ) |
| ( x x0 )( x x1 )( x x2 ) | dx
x
j
3!
2
1
ここはh4/2になる
(3)
max | f ( ) | | s ( s 1)(s 2) | h 4 ds
0
3!
h4
h4
( 3)
max | f ( ) |
N max | f ( 3) ( ) |
12
12
(b a ) 4
(3)
max
|
f
( )|
3
12 N
“定数の大きさ”や“不等式による”評価であるため、一般にはシンプソンの公式の方
が必ず台形公式より良いとも言えない(最もよい評価でシンプソンの公式の誤差は
Science of
interactions
5
O(h ))。
台形公式とシンプソンの公式の関係
分点数N=2nとする。このとき台形公式による積分近似値をTn,シンプソンの公式に
よる積分近似値をSnとする。すると、TnとSnの間には以下の関係が成立する。
Sn
4
1
T
Tn
1
n 1
3
3
4h 1
f ( a ) f (a
3 2
h)
f (a
2h) L f (b h)
1
f (b)
2
2h 1
1
f ( a ) f ( a 2 h ) f ( a 4 h ) L f (b 2 h )
f (b)
3 2
2
h
f (a ) 4 f (a h) 2 f (a sh) L 2 f (b 2h) 4 f (b h)
3
Sn 1
f (b)
Science of
interactions
ロンバーグ積分法
分割数を N=2n (n=0,1,2,…)とし、各nに対して台形公式によって計算された積分
近似値をTn(0)とする。そして、以下の漸化式により Tn(k) (k=1,2,3,…)を計算する。
T0( 0)
T1( 0)
T2( 0)
M
Tn( 01)
Tn( 0)
(1)
1
(1)
2
T
T
Tn( k )
T2( 2)
Tn(11) Tn( 21) L Tn( k1 1)
Tn(1) Tn(1) L Tn( 2 )
4 k Tn( k 1) Tn( k1 1)
4k 1
Tn( k )
Science of
interactions
チェックテスト（第２回）の説明
•
•
•
•
配点20点（満点）
時間60分
持ち込み不可・再試験はなし
欠席の場合は零点と評価し最終試験の際に調整（次
のスライドで詳説）
• 出題範囲は以下の通り；
– 逐次法、ニュートン法
• Aitkenなどの加速法は出題範囲に含まない
– 補間と誤差評価
• 最小２乗法は出題範囲に含まない
– 数値積分
Science of
interactions