● 講義資料

(1)

● 講義資料

▼ 講義予定

•

スツルムの二分法

•

収束の加速

● 前回の講義のまとめ

▼ ニュートン法について

• √

2

に代表される,代数方程式の解の近似値を求める方法として,以下のニュートン法が広く知られている.

•

区間

[a, b]

上で定義された実数値

C ² -級関数 f (x)

が, [a, b]上で単調増加かつ下に凸であり,

f (a) < 0, f (b) > 0

を満たしていると仮定する. この時,

x 0 = b, x n+1 = x n − f (x n )/f ^′ (x n )

により定義された数列

{ x ⁿ }

は,単調減少かつ下に有界であり, [a, b]上の

f (x) = 0

のただひとつの解

α

に収束する. さらに,ある定数

M > 0

が存在して,

| x ⁿ +1 − α | ≤ M | x ⁿ − α | ²

が成り立つ.

•

ニュートン法は以下の「逐次近似」の一例と考えられる.

• F : R −→ R

を

C ² -級関数とする.

この時,

x n+1 = F (x ⁿ )

によって数列

{ x ⁿ }

を定義して,写像

F

の固定点

(α = F (α)

を満たす点)を近似する方法を逐次近似と呼ぶ.

•

関数

f (x)

に対するニュートン法

x n+1 = x ⁿ − f (x ⁿ )/f ^′ (x ⁿ )

は,

F(x) = x − f (x)/f ^′ (x)

と定義した逐次近似である.

• R

のある近傍

U

と正定数

L < 1

が存在して,任意の

x, y ∈ U

に対して

| F (x) − F (y) | ≤ L | x − y |

を満たすとき,

F

は

U

上で縮小写像であると言う.

• C ² -級関数 F : R −→ R

が,

U ⊂ R

上で縮小写像であるとき,

F

は

U

にただひとつの固定点を持つ（縮小写像の原理）.

証明は,

x 0 ∈ U , x ⁿ +1 = F (x ⁿ )

で定義した点列

{ x ⁿ }

がコーシー列となることを示し,その収束先が固定点となることを示せばよい.

• C ² -級関数 F : R −→ R

に対する逐次近似

x ⁿ +1 = F (x ⁿ )

の固定点

α

があらかじめわかっている時を考える. この時,

| F ^′ (α) | < 1

が成り立てば,

α

の近傍で

F

は縮小写像となる. 特に,

(2)

•

逐次近似

x n+1 = F (x ⁿ )

が

α

に収束すると仮定する. この時,

ǫ ⁿ = | x ⁿ − α |

は

ǫ n+1 ≤ | F ^′ (α) | ǫ ⁿ + 1

2 | F ^′′ (α) | ǫ ² n + O(ǫ ³ n )

をみたす. 証明は,

α

で

F

を３次までテイラー展開して計算すればよい.

•

ニュートン法の収束の速さは,

f (x) = 0

の解が単根のとき,

ǫ n+1 ≤ Cǫ ² n

をみたし,

m

重根の時

ǫ ⁿ +1 ≤ m − 1 m ǫ ⁿ

をみたす.

証明は,

F (x) = x − f (x)/f ^′ (x)

と考え,上の結果を適用すればよい.

•

この結果から,ニュートン法は,解が単根の時と重根の時とでは,その収束の様子が質的に異ることがわかる.

•

さらに,ニュートン法の収束の判定には,次の結果を用いることができる.

1.

ある値

α

の近似列

{ x ⁿ }

が

| α − x n+1 | ≤ C | α − x ⁿ | ²

を満たしていると仮定する. この時, 任意の

0 < C < 1

に対して,

| x n+1 − x ⁿ | < Cǫ | x ⁿ |

が成り立つならば,

| α − x ⁿ | < ǫ | α |

が成り立つ.

2.

ある値

α

の近似列

{ x ⁿ }

が, ある

0 < L < 1

が存在して,

| α − x n+1 | ≤ L | α − x ⁿ |

を満たしていると仮定する. この時,

| x ⁿ +1 − x ⁿ | < (1 − L)ǫ | x ⁿ |

が成り立つならば,

| α − x ⁿ | < ǫ | α |

が成り立つ.

•

たとえば,ニュートン法の単根の場合には,収束の判定条件として,「

| x n+1 − x ⁿ | > ǫ | x ⁿ |

が成り立つ間,繰り返しを続ける」と書けば,そのループから脱出した時点では,

| x n+1 − x ⁿ | < ǫ | x ⁿ |

が成り立っているので,近似値

x n+1

は解

α

を相対誤差

ǫ

で近似していると考えてよいことがわかる.

(3)

▼ その他の求根アルゴリズム

•

初回に解説した二分法と今回のニュートン法のほかに,簡単な求根アルゴリズムとしては,以下のものが知られている.

以下では, 関数

f

は区間

[a, b]

上で定義された, 単調増加関数であり,

f (a) < 0, f (b) > 0

と仮定する. また,区間

[a, b]

における

f (x) = 0

の一意的な解を

α

とする.

•

「はさみうち法」などと呼ばれる方法.

–

二分法では,繰り返しの際に

c ⁿ = (a ⁿ + b ⁿ )/2

における

f (c ⁿ )

の値の正負によって,区間を取り替えていた.

–

これを

(a ⁿ , f(a ⁿ )), (b ⁿ , f(b ⁿ ))

を結ぶ直線と

x

軸との交点を

c ⁿ

とおいて,

f (c ⁿ )

の値の正負によって区間を取り替える方法である.

–

二分法と同じく,「一次収束」する.

–

二分法と同じく, 任意の

n

に対して,

α ∈ [a ⁿ , b ⁿ ]

が成り立つ. したがって,求めた近似値の精度保証が容易である.

•

「割線法」

–

関数

f

が区間

[a, b]

で下に凸であると仮定できるとき,ニュートン法で「接線」を取った

代わりに, (x

ⁿ , f (x ⁿ )), (x ⁿ +1 , f (x ⁿ +1 ))

を通る直線と

x

軸の交点を

x ⁿ +2

とおく方法.

–

収束の次数は

(1 + √

5)/2

となる. （ニュートン法よりも収束が遅い）

–

関数の微分

f ^′

が複雑な式になっている場合や,

f ^′

を数値的にしか求めることができない場合には,ニュートン法よりも誤差を小さくできる可能性がある.

(4)

● 講義資料

▼ スツルム列の定義とスツルムの定理

区間

[a, b]

で定義された, deg

f ^k > deg f k+1

をみたす多項式の列

{ f ^k } ⁿ ^k =0

が

Strume

列をなすとは,

1.

任意の

x ∈ [a, b]

に対して,

f ^k (x)

と

f k+1 (x)

は同時には

0

にならない.

2. f k (x 0 ) = 0

ならば

f k − 1 (x 0 )f k+1 (x 0 ) < 0, 3. f ⁿ

は定符号,

4. f 0

は重根を持たない（f

0 (x) = 0

ならば

f 0 ^′ (x)f 1 (x) > 0

をみたす）

ことを言う.

区間

[a, b]

上で定義された多項式列

{ f ^k } ⁿ k=0

がスツルム列をなし,

f 0 (a)f 0 (b) 6 = 0

であると仮定する. このとき,

f 0 (x), f 1 (x), . . . , f ⁿ (x)

の符号変化の回数を

N (x)

とおくと,区間

[a, b]

における

f 0 (x)

の根の個数は

N(a) − N (b)

に等しい. これをスツルムの定理を呼ぶ.

▼ スツルム列の例

•

ルジャンドル多項式：

P ⁿ

(n + 1)P n+1 (x) = (2n + 1)xP ⁿ (x) − nP ⁿ ₋ 1 (x), P 0 (x) = 1, P 1 (x) = x, Z ¹

− 1

P ⁿ (x)P ^m (x) dx = C ⁿ δ ^nm

•

第１種チェビシェフ多項式：

T ⁿ

T n+1 (x) = 2xT ⁿ (x) − T ⁿ ₋ 1 (x), T 0 (x) = 1, T 1 (x) = x, Z ¹

− 1

T ⁿ (x)T ^m (x) dx

√ 1 − x ² = C ⁿ δ ^nm , T n (cos(t)) = cos(nt),

•

第２種チェビシェフ多項式：

U ⁿ

(5)

•

エルミート多項式:

H ⁿ

H ⁿ +1 (x) = 2xH ⁿ (x) − 2nH ⁿ ₋ 1 (x), H 0 (x) = 1, H 1 (x) = 2x, Z

R

H ⁿ (x)H ^m (x)e ⁻ ^x

²

dx = C ⁿ δ ^nm , U ⁿ ₋ 1 (cos(t)) = sin(nt)

sin(t) ,

•

任意の多項式

f

に対して,

f 0 = f , f 1 = f ^′

とおき,ユークリッドの互除法

f ^k = g ^k f k+1 − f k+2

で作られる列

{ f ^k } ⁿ k=0

は,

f ⁿ

が

0

でない定数である時,スツルム列をなす.

-1 -0.5 0 0.5 1

Legendre Polynomial (n=0...4)

-2 -1 0 1 2

-1 -0.5 0 0.5 1

Chebyshev Polynomial of 1st kind (n=0...4)

-2 -1 0 1 2

-1 -0.5 0 0.5 1

Chebyshev Polynomial of 2nd kind (n=0...4)

P 11 (x)

の零点：

+0.9782286581461, +0.8870625997681, +0.7301520055740, +0.5190961292068, +0.2695431559523,

+0.0000000000000,

− 0.2695431559523, − 0.5190961292068,

− 0.7301520055741, − 0.8870625997681, − 0.9782286581461.

(6)

▼ 収束の加速

次の図は,単位円に接する正多角形の周長による円周率の近似計算を, Romberg加速と

Aitken

加速を使って加速した例である.

1e-16 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 1

10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09

original 1 step 2 step Aitken

次の図は, 単位円に接する正多角形の周長による円周率の近似計算を, Romberg加速を用いて計算している例であり,

λ

の値を正しい値から取り替えて計算した例である.

1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01

10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09

original 0.25 0.245 0.255 0.24 0.26 0.20 0.30

次の図は, arctan(x)の近似値のテイラー展開による近似計算を, Aitken 加速を使って加速した例である.

0.0001 0.01 1

original x=1.00 Aitken x=1.00 original x = 0.99 Aitken x = 0.99 original x = 0.90 Aitken x = 0.90

(7)

● 実習内容

（以下で「★」の数は推奨の程度を示します. 多いほど推奨の度合いが大きい. また,「†」は難易度またはマニアックな程度を表します. 多いほど難しいかマニアックかです.）

1.

（★★★）単位円に接する多角形の周長による円周率の近似計算を

Romberg

加速によって計算しなさい. （この資料の最初の図のような図を書きなさい）

2.

（★★★）単位円に接する多角形の周長による円周率の近似計算を２段階の

Romberg

3.

（★★★）単位円に接する多角形の周長による円周率の近似計算を

Aitlen

4.

（★★★）テイラー展開による

arctan(1), arctan(0.99)

の近似値の計算を

Aitlen

加速によって計算しなさい. （この資料の２つめの図のような図を書きなさい）

5.

（★★）f

(x) = (x ² − 2) ^k

に対するニュートン法による

√

2

の近似計算を, Aitken 加速によって計算しなさい.

6.

（★★†）f

(x) = (x ² − 2) ^k

に対するニュートン法による

√

2

の近似計算を,

k ≥ 2

の時に

Romberg

加速によって計算しなさい.

7.

（★★）ルジャンドル多項式,第１種チェビシェフ多項式,第２種チェビシェフ多項式の

n = 5

までのグラフを描画しなさい.

8.

（★）エルミート多項式の

n = 5

までのグラフを描画しなさい.

9.

（★★★）ルジャンドル多項式, 第１種チェビシェフ多項式, 第２種チェビシェフ多項式の

n = 20

までのすべての零点を求めなさい. これらの多項式の根は,すべて実であり, [

− 1, 1]

に存在することを仮定してよい.

10.

（★★††）エルミート多項式の

n = 10

までのすべての零点を求めなさい. エルミート多項式の根は,すべて実であることを仮定してよい.

11.

（★†††）f

(x) = 144x ⁷ − 36x ⁶ − 196x ⁵ + 49x ⁴ + 56x ³ − 14x ² − 4x + 1

のすべての零点を求めなさい. この多項式の根は, すべて実であり, [

− 2, 2]

この問題では,スツルム列を手で（または, Mathematicaなどで）計算しておき,係数を浮動小数点数でかくとよい.

12.

（★†††††）f

(x) = 144x ⁸ + 252x ⁷ + 164x ⁶ − 19x ⁵ − 110x ⁴ − 19x ³ + 19x ² + 2x − 1

のすべての零点を求めなさい. この多項式のすべての根は, [

− 2, 2]

● 講義資料

•

•

• √

2

•

[a, b]

C 2 -級関数 f (x)

f (a) < 0, f (b) > 0

x 0 = b, x n+1 = x n − f (x n )/f ′ (x n )

{ x n }

f (x) = 0

α

M > 0

| x n +1 − α | ≤ M | x n − α | 2

•

• F : R −→ R

C 2 -級関数とする.

x n+1 = F (x n )

{ x n }

F

(α = F (α)

•

f (x)

x n+1 = x n − f (x n )/f ′ (x n )

F(x) = x − f (x)/f ′ (x)

• R

U

L < 1

x, y ∈ U

| F (x) − F (y) | ≤ L | x − y |

F

U

• C 2 -級関数 F : R −→ R

U ⊂ R

F

U

x 0 ∈ U , x n +1 = F (x n )

{ x n }

• C 2 -級関数 F : R −→ R

x n +1 = F (x n )

α

| F ′ (α) | < 1

α

F

•

x n+1 = F (x n )

α

ǫ n = | x n − α |

ǫ n+1 ≤ | F ′ (α) | ǫ n + 1

2 | F ′′ (α) | ǫ 2 n + O(ǫ 3 n )

α

F

•

f (x) = 0

ǫ n+1 ≤ Cǫ 2 n

m

ǫ n +1 ≤ m − 1 m ǫ n

F (x) = x − f (x)/f ′ (x)

•

•

1.

α

{ x n }

| α − x n+1 | ≤ C | α − x n | 2

0 < C < 1

| x n+1 − x n | < Cǫ | x n |

| α − x n | < ǫ | α |

2.

α

{ x n }

0 < L < 1

| α − x n+1 | ≤ L | α − x n |

| x n +1 − x n | < (1 − L)ǫ | x n |

| α − x n | < ǫ | α |

•

| x n+1 − x n | > ǫ | x n |

| x n+1 − x n | < ǫ | x n |

x n+1

α

C ² -級関数 f (x)

x 0 = b, x n+1 = x n − f (x n )/f ^′ (x n )

{ x ⁿ }

| x ⁿ +1 − α | ≤ M | x ⁿ − α | ²

C ² -級関数とする.

x n+1 = F (x ⁿ )

{ x ⁿ }

x n+1 = x ⁿ − f (x ⁿ )/f ^′ (x ⁿ )

F(x) = x − f (x)/f ^′ (x)

• C ² -級関数 F : R −→ R

x 0 ∈ U , x ⁿ +1 = F (x ⁿ )

{ x ⁿ }

• C ² -級関数 F : R −→ R

x ⁿ +1 = F (x ⁿ )

| F ^′ (α) | < 1

x n+1 = F (x ⁿ )

ǫ ⁿ = | x ⁿ − α |

ǫ n+1 ≤ | F ^′ (α) | ǫ ⁿ + 1

2 | F ^′′ (α) | ǫ ² n + O(ǫ ³ n )

ǫ n+1 ≤ Cǫ ² n

ǫ ⁿ +1 ≤ m − 1 m ǫ ⁿ

F (x) = x − f (x)/f ^′ (x)

{ x ⁿ }

| α − x n+1 | ≤ C | α − x ⁿ | ²

| x n+1 − x ⁿ | < Cǫ | x ⁿ |

| α − x ⁿ | < ǫ | α |

{ x ⁿ }

| α − x n+1 | ≤ L | α − x ⁿ |

| x ⁿ +1 − x ⁿ | < (1 − L)ǫ | x ⁿ |

| α − x ⁿ | < ǫ | α |

| x n+1 − x ⁿ | > ǫ | x ⁿ |

| x n+1 − x ⁿ | < ǫ | x ⁿ |

c ⁿ = (a ⁿ + b ⁿ )/2

f (c ⁿ )

(a ⁿ , f(a ⁿ )), (b ⁿ , f(b ⁿ ))

c ⁿ

f (c ⁿ )

α ∈ [a ⁿ , b ⁿ ]

ⁿ , f (x ⁿ )), (x ⁿ +1 , f (x ⁿ +1 ))

x ⁿ +2

f ^′

f ^′

f ^k > deg f k+1

{ f ^k } ⁿ ^k =0

f ^k (x)

f k − 1 (x 0 )f k+1 (x 0 ) < 0, 3. f ⁿ

f 0 ^′ (x)f 1 (x) > 0

{ f ^k } ⁿ k=0

f 0 (x), f 1 (x), . . . , f ⁿ (x)

P ⁿ

(n + 1)P n+1 (x) = (2n + 1)xP ⁿ (x) − nP ⁿ ₋ 1 (x), P 0 (x) = 1, P 1 (x) = x, Z ¹

P ⁿ (x)P ^m (x) dx = C ⁿ δ ^nm

T ⁿ

T n+1 (x) = 2xT ⁿ (x) − T ⁿ ₋ 1 (x), T 0 (x) = 1, T 1 (x) = x, Z ¹

T ⁿ (x)T ^m (x) dx

√ 1 − x ² = C ⁿ δ ^nm , T n (cos(t)) = cos(nt),

U ⁿ