ε-N論法について #C

はじめに

明治大学総合数理 Advent Calender 2017の13日目の記事。早くも私は5回目。前回でNetworkの反応拡散方程式についての連載が終わったので、新しい事柄を書いていく。連載にするかはまだ未定。

目標

ε-N論法を説明し、その応用を少し見る。

ε-N論法について(実数ver.)

ε-N論法とは数列の極限の概念を「ちゃんと」定義するものである。その中身は下の感じ。

$\{x_i\} \ (i = 1, 2, \cdots)$を実数上の数列とする。この数列が$i \to \infty$のとき、$x$に収束するとは、任意の正の実数$\varepsilon$に対して、ある自然数$N$が存在して、$N$以上の任意の自然数$n$に対して$|x_n - x| < \varepsilon$であることを言う。

細かく見て意味を理解しよう。

「$\{x_i\} \ (i = 1, 2, \cdots)$を実数上の数列とする。」
- $\{1, \frac{1}{2}, \frac{1}{3}, \cdots\}$みたいに全部実数な数列について話している。
「この数列が$i \to \infty$のとき、$x$に収束するとは、」
- つまりは$\lim_{i \to \infty}x_i = x$を定義したいと言っている。
「任意の正の実数$\varepsilon$に対して、」
- 何でもいいからある正の数を選ぼう。
「ある自然数$N$が存在して、」
- 3で選んだ$\varepsilon$に対して、何か自然数$N$が決まると言っている。
「$N$以上の任意の自然数$n$に対して$|x_n - x| < \varepsilon$であることを言う。」
- 4で決まった$N$を上回るような$n$を選べば、「数列の$n$番目以降の数」と$x$の差は3で適当に選んできた$\varepsilon$より小さくなると言っている。

つまり、総括すると数列が何らかの値に収束するなら、数列の「十分大きい数」番目以降の実数は全部極限の値に近いよってことである。

ε-N論法について(一般ver.)

上では実数の収束について見た。だが、実際見回してみると、色んな種類の「何か」の列がある。例えば、２次元のベクトルの列、一般にm次元のベクトルの列、複素数の列、関数の列などなど。これらにも何らかの形で極限ってあるでしょって観点からε-N論法を一般化する。そのためにはまずノルムと距離という2つの概念を導入する。

実数やベクトルなどの「もの」は大きさが計れる。実数で一番慣れ親しまれている計り方は絶対値である。-3の大きさだったら3という具合。じゃあベクトルだったら？これもいつも使うであろう、二乗して和を取る方法がある。例えば$\boldsymbol{x} = (1, -2, 3)$であったら$\sqrt[]{1^2 + (-2)^2 + 3^2} = \sqrt{14}$といった感じである。でも、$|1 + 2 + 3| = |6|$という風に要素の絶対値を全部足すような大きさだって考えることもできる。

このような感じで「もの」が変われば、その大きさの計り方が変わる。しかも「もの」が変わらなくても、色んな「もの」の計り方がある。しかし、共通していることは「大きさを計る」ということ。あるルールで「もの」を計ったとき、その「もの」の大きさのことをノルムという。$\boldsymbol{x}$のノルムを$||\boldsymbol{x}||$と書く。

(関数のノルムは例えば、定義域の中の上限($\sup$)とかで計れる。詳しいことは関数解析をやりましょう。)

ノルムを定義すると、そこから自然と距離を定義することができる。距離とは「もの」と別の「もの」の近さであるから、2つのものの差の大きさで定義する。すなわち、$\boldsymbol{x}$と$\boldsymbol{y}$の距離は$||\boldsymbol{x} - \boldsymbol{y}||$と書ける。

(注) そもそも距離は同じ性質を持つもの同士でしか計ることができない。例えば2次元のベクトル同士は差を考えられるが、2次元と3次元は比べることができない。

ここで、ようやく極限の話に戻る。そもそも実数が収束するとは、数列の「十分大きい数」番目以降の実数は全部極限の値に近いということだった。この「近い」という概念が距離を使うことによって、実数だけじゃなくて一般にベクトルなどの列に収束を定義することができる。つまり、

$\{x_i\} \ (i = 1, 2, \cdots)$を「何か」の列とする。この列が$i \to \infty$のとき、$x$に収束するとは、任意の正の実数$\varepsilon$に対して、ある自然数$N$が存在して、$N$以上の任意の自然数$n$に対して$||x_n - x|| < \varepsilon$であることを言う。

収束する列の性質

今まで見てきたことは、極限を$x$として、その極限に収束するかどうかだった。だが、実際にこの$x$を計算して求めることは多くの場合大変であったり、計算では求まらないことだってある。そんなときでも極限の値$x$を使わずに収束を論じることができる手法がある。それがCauchyの判定法である。それは次のような定理として与えられる。また実数に戻って、

$\{x_i\} \ (i = 1, 2, \cdots)$を実数上の数列とする。この数列が$i \to \infty$のとき、$x$に収束するとき、任意の正の実数$\varepsilon$に対して、ある自然数$N$が存在して、$N$以上の任意の自然数$n$と$m$に対して$|x_n - x_m| < \varepsilon$である。また、逆も成り立つ。

つまり、数列が何らかの値に収束するなら、数列の「十分大きい数」番目以降の実数(ここでは$n$と$m$番目)の差の大きさは十分小さいよということである。「数列の「十分大きい数」番目以降の実数(ここでは$n$と$m$番目)の差の大きさは十分小さいよ」という性質が成り立つような数列のことをCauchy列という。

最後に1文「また、逆も成り立つ。」と付け加えたことにも気づいてほしい。これは実数だからこそ成り立っている話で、先程の定理を換言すれば、

実数上では収束列はCauchy列だし、Cauchy列は収束列である。

ということを意味している。一応実数に限らず複素数や実数を要素に持つベクトルに成り立つ事柄である。

(しかし、一般に逆が成り立つかどうかはいちいちチェックせねばならないことであり、もし「もの」が属する空間全域で成り立つとしたら、その空間は完備であるという。最も簡単な例は、ある$n$次元の有界領域上で連続な関数全体が果たして「完備」かどうかは、自明ではなくちゃんと調べねばならないことである。詳しく知りたかったら、関数解析をやりましょう(2度目))

応用例

例えばNewton法(リンクはWikipedia)という方程式の解を近似的に求める手法がある。その内容をざっくり説明すると、

$f(x)=0$の解の近くの値$x_0$を適当に取り、$$x_{n + 1} = x_n - \frac{f(x)}{f'(x)}$$により数列$\{x_n\}$を得ると、この数列は$f(x) = 0$の解に収束する。

収束するための細かな条件などはWikipediaなどに任せるとして、とにかく何らかの値に収束することがわかっているということである。理論はやはりわかるが、これを実装するとなると、無限なんてどうしたら良いのかとなる。どれだけ漸化式を計算して何番目の$x_n$まで求めれば良いのか。そこで出て来るのがε-N論法とCauchyの判定法である。再掲すると

$\{x_i\} \ (i = 1, 2, \cdots)$を実数上の数列とする。この数列が$i \to \infty$のとき、$x$に収束するとは、任意の正の実数$\varepsilon$に対して、ある自然数$N$が存在して、$N$以上の任意の自然数$n$に対して$|x_n - x| < \varepsilon$であることを言う。

実数上では収束列はCauchy列だし、Cauchy列は収束列である。

つまり、Netwon法では収束することがわかっているのだから、何か適当に$\varepsilon$(例えば0.01とか)を取ってきて、ある十分大きいn番目の$x_n$と解$x$との差が$\varepsilon$となれば収束したことにしてしまえば良い。

しかし、問題はその$x$は求めたいものだから、予めわかっているなら苦労しないよ、ということになる。だから、そこで出てくるのがCauchyの収束判定なのであって、十分に大きい$n$番目と$m$番目($m = n + 1$とかにするとやりやすい)の値を比べて、それらの差が$\varepsilon$以下になったら収束したことにしてしまえばよいのである。

以上を踏まえてcにてNetwon法を実装すると以下のようになる。
$f(x) = x^2 - 2 = 0$の解の一つ、$x = \sqrt[]{2}$を求めるために$x_0 = 0.5$としている。

newton.c

#include <stdio.h>
#include <math.h>

#define e 0.0000000001

double f(double x);
double next(double x);

int main() {
    double x, nextX;

    x = 1.0;
    nextX = next(x);

    // Cauchyの判定法 (n番目とn + 1番目で比べている)
    while (fabs(x - nextX) >= e) {
        x = nextX;
        nextX = next(x);
    }

    printf("%1.10f\n", x);
}

double f(double x){
    return x * x - 2.0;
}

double next(double x) {
    return x - f(x) / (2.0 * x);
}

実行するとちゃんと

1.4142135624

と返ってきてくれて$\sqrt[]{2}$の「ひとよひとよひとみごろ」が十分近似できていることがわかる。

最後に

Newton法がうまくいくのは、「実数が完備である」という性質が諸に効いている。数列の収束先の値もまた実数となって、ちゃんと「存在」してくれているのである。そして、その収束先の「存在性」だけわかっておけば、Cauchyの判定法から数列をCauchy列として見ることで、未知なる収束先を得ることができるのである。こうして完備性は、どこに答えがあるかはわからないが、どこかに確実にあることを保証してくれているのだ。

結論

ε-N論法について説明し、実際にどうやって使われるかを見た。