数値解析(第四章) 関数を近似する

数値解析 (第四章)
関数を近似する
関数の近似はなぜ必要か
モティベーション
• 複雑な関数を計算機が可能な演算に還元しなければならない
• できるだけ計算量を減らしたい
• できるだけデータ量を減らしたい
• 通常は多項式で近似するが，できるだけ滑らかに近似したい
⇓
補間多項式， Taylor 近似，最小二乗法など
数値解析
補間とは (1)
有限個のデータから関数全体を復元したい
この曲線をより計算量と記憶容量の少ないもので近似したい
3
2
1
0.2
0.4
0.6
0.8
1.0
例えば 4 点を選んで直線で結ぶと
3
2
1
0.2
0.4
0.6
0.8
1.0
計算量は少ないが不自然
数値解析
補間とは (2)
もう一点増やして
3
2
1
0.2
0.4
0.6
0.8
1.0
もっと増やせば
3
2
1
0.2
0.4
0.6
0.8
1.0
だいぶよくなったが，つなぎ目が不自然
データをそんなに増やせないときはどうするか
数値解析
補間とは (3)
いま行ったことは，
２点 (a, f (a)), (b, f (b)) を結ぶ直線 (一次式，一次多項式) を求めただけ
これでも点と点の距離が近ければよい近似が得られる
このような近似法を一次補間と呼んでいる。
二点 (a, f (a)), (b, f (b)) を結ぶ直線の式は
f (b) − f (a)
(x − a)
y = f (a) +
b−a
x−b
x−a
=
f (a) +
f (b)
a−b
b−a
数値解析
n 次補間 (1)
n 次 (多項式) 補間とは
n + 1 点 (x0 , f0 ), (x1 , f1 ), · · · , (xn , fn ) を通る n 次多項式 Pn (x)
を作ることを言う。そのような多項式 Pn (x) は
Pn (x) =
n
X
li (x) fi ,
i=0
(x − x0 ) (x − x1 ) · · · (x − xi−1 ) (x − xi+1 ) · · · (x − xn )
li (x) =
(xi − x0 ) (xi − x1 ) · · · (xi − xi−1 ) (xi − xi+1 ) · · · (xi − xn )
n
Y
x − xj
=
xi − xj
j=0, j6=i
で与えられる (Lagrange の補間)。
問上の式で与えられる Pn (x) が Pn (xi ) = fi (i = 0, 1, . . . , n) を満たすことを
示せ。
数値解析
n 次補間 (2)
問二点 (0, 0), (1, 1) を通る一次補間多項式を作れ。
問三点 (0, 0), (1/2, 1/4), (1, 1) を通る二次補間多項式を作れ。
数値解析
n 次補間 (3)
定理相異なる n + 1 点を通る n 次多項式は一つしか存在しない。
証明
そのような多項式が２つあったとする。それらを P (x) と Q(x) とする。この２
つはどちらも相異なる n + 1 点 (xi , fi ) (i = 0, 1, . . . , n) を通るとする。すなわち
P (xi ) = Q(xi ) = fi ,
i = 0, 1, . . . , n
とする。そうすると n 次多項式 R(x) = P (x) − Q(x) は
R(xi ) = P (xi ) − Q(xi ) = 0,
i = 0, 1, . . . , n
となり n + 1 点で 0 となる (n + 1 個の解を持つ )。 ⇒ 矛盾
数値解析
Lagrange 補間多項式の計算法
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
P := 0;
for i := 0 to n do
li := 1;
for j := 0 to n do
if j 6= i then
li := li ∗ (x − xj )/(xi − xj );
end if
end for
P := P + fi ∗ li ;
end for
問上のプログラムで乗算の回数は何回になるか。
数値解析
Lagrange 補間の誤差
関数 f (x) の値 (xi , f (xi )) (i = 0, 1, . . . , n) から n 次補間多項式を作ったとき，
その誤差 e(x) = Pn (x) − f (x) は
f (n+1) (ξ)
ϕ(x)
e(x) = −
(n + 1)!
となる。ここで
ϕ(x) =
n
Y
(x − xi )
i=0
であり， ξ は x に依存して決まる未知の値である。
• x = xi (i = 0, . . . , n) では誤差が０になる (当たりまえ )
• x = xi (i = 0, . . . , n) の近くでは誤差が小さくなる
• f (n+1) (x) = 0 なら e(x) = 0 となる (f (x) が n 次の多項式の場合)
• maxx |ϕ(x)| が大きく振動する関数ならば補間の性質も悪くなる ⇒ チェビ
シェフ点
数値解析
標本点をどのように配置するか
等間隔:
b−a
xi = a +
i,
n
i = 0, 1, . . . , n
チェビシェフ点:
b+a b−a
−
cos
xi =
2
2
-1.0
2i + 1
π
2(n + 1)
1.0
1.0
0.5
0.5
0.5
-0.5
1.0
-1.0
0.5
-0.5
-0.5
-0.5
-1.0
-1.0
1.0
a = −1, b = 1 の場合の等間隔点とチェビシェフ点の比較
数値解析
ϕ(x) の比較 (n = 10 の場合)
0.010
0.005
x
-1.0
0.5
-0.5
1.0
-0.005
-0.010
チェビシェフ点 (太線) と等間隔点 (細線)
数値解析
チェビシェフ補間の例
f (x) =
1
1+25x2
の補間多項式の比較
1.5
1.0
0.5
-1.0
-0.5
0.5
1.0
等間隔に標本点を配置すると端の方で振動が激しくなる
数値解析
最小二乗近似
最小二乗近似とは (1)
実験データに「もっともらしく」当てはまる式 (直線 or 曲線) を探す
12
10
8
6
4
2
2
4
6
8
10
-2
• データは測定時の誤差を含んでいる
• 物理的考察 (経験) より現象を説明するモデルが存在することもある
数値解析
最小二乗近似とは (2)
12
10
8
6
4
2
2
4
6
8
10
-2
これは不自然！
12
10
8
6
4
2
2
4
6
8
-2
これも不自然！ (多項式補間)
数値解析
10
最小二乗近似とは (3)
12
10
8
6
4
2
2
4
6
8
10
-2
これはもっともらしい
どうやってこの「もっともらしい」直線を引くか
数値解析
「もっともらしく」とは
測定データ (xi , yi ) (i = 1, . . . , n) がある
当てはめる直線の式 (モデル ) を y = a x + b とする
「もっともらしく」とは
モデルから得られる値と測定データの差 ei (= yi − (a xi + b)) の２乗和
E(a, b) :=
n
X
e2i =
i=1
を最小にするように a, b を決める。
数値解析
n
X
i=1
(yi − (a xi + b))2
どうやって a, b を決めるか (1)
E(a, b) を展開すると
E(a, b) =
=
n
X
yi2
i=1
n
X
i=1
− 2 yi (a xi + b) + (a xi + b)
x2i
!
a 2 + n b2 + 2
n
X
i=1
−2
n
X
i=1
yi
!
b+
xi
!
n
X
2
ab − 2
n
X
i=1
yi2
i=1
a に関しても， b に関しても二次式で a2 (b2 ) の係数は正である。
⇒ 下に凸な関数
∂E(a, b)
∂E(a, b)
=
= 0 となる点で極小値を持つ。
E(a, b) は
∂a
∂b
数値解析
xi yi
!
a
どうやって a, b を決めるか (2)
∂E(a, b)
=2
∂a
∂E(a, b)
=2
∂b
n
X
i=1
n
X
i=1
x2i
xi
!
!
Pn
2
x
i
Pi=1
n
i=1 xi
a+2
n
X
xi
i=1
a + 2nb − 2
!
b−2
n
X
n
X
xi yi
i=1
yi
i=1
!
!
=0
=0
⇓
Pn
Pn
xi yi
a
i=1 xi
i=1
P
=
n
n
b
i=1 yi
⇓
a = (n Sxy − Sx Sy )/(n Sxx − Sx2 )
b = (Sxx Sy − Sx Sxy )/(n Sxx − Sx2 )
Sxx =
n
X
i=1
数値解析
x2i ,
Sxy =
n
X
i=1
xi yi
Sx =
n
X
i=1
xi ,
Sy =
n
X
i=1
yi
別なケース
測定データ (xi , yi , zi ) (i = 1, 2, . . . , n) にうまく当てはまるような平面
z = a x + b y + c を決める場合は
E(a, b, c) =
n
X
(zi − (a xi + b yi + c))2
i=1
という関数を作り，それを a, b, c で偏微分し 0 と置いた方程式を解く。
問 a, b, c を求める方程式を導け。
数値解析

Download Report