数値解析
概要
数値解析（numerical analysis）とは、方程式の解・積分・微分方程式の解・行列の固有値などの近似値を有限回の四則演算で求める方法を作り、その誤差・収束の速さ・安定性・計算量を数学的に調べる分野である。誤差には、極限を有限の操作で置き換える打ち切り誤差、有限桁で数を表す丸め誤差、入力の誤差があり、問題の条件数とアルゴリズムの安定性の組み合わせで精度が決まる。同じ漸化式 $I_n=1-nI_{n-1}$ でも、前向きに計算すると出発値の誤差が $n!$ 倍になり、後ろ向きに計算すると誤差が縮むことが、安定性の典型例である。Newton 法、LU 分解、補間、Gauss 求積、Euler 法などが主な方法である。
前提知識: 誤差(数値解析), Newton法, Lagrange補間
数値解析（numerical analysis）は、方程式の解・積分・微分方程式の解・行列の固有値のように、連続的な数学の問題の答えを、有限回の四則演算で近似的に求める方法（アルゴリズム）を作り、その誤差・収束の速さ・計算量を数学的に調べる分野である。答えの式が分かっていても、その式をどの順序で計算するかによって、得られる数値の精度は大きく変わる。逆に、答えの式が分からない問題でも、誤差の上界を保証しながら近似値を求めることができる。
この記事は分野の入口として、典型的な問題と方法、誤差の考え方をまとめ、関連する記事を案内する。あわせて、この分野らしい議論の例として、漸化式で積分の値を求めるときに誤差がどう伝わるかを証明し、同じ漸化式でも計算の向きによって結果がまったく違うことを示す。
定義
数学の問題（入力から出力を定める写像）に対し、有限回の算術演算と比較からなる手続きで出力の近似値を求める方法を 数値解法 あるいは アルゴリズム という。数値解法を作り、次の 3 点を数学的に調べる分野を 数値解析 という。
- 誤差：近似値と真の値の差の大きさ。打ち切り（極限を有限の操作で置き換えること）による誤差と、数を有限桁で表すことによる丸め誤差を含む。
- 収束：刻み幅を小さくする、反復の回数や節点の個数を増やすなど、近似を精密にしたときに誤差が $0$ に近づくか、どの速さで近づくか。
- 安定性と計算量：途中で生じた小さな誤差が増幅されないか、必要な演算の回数はどれだけか。
誤差の測り方（絶対誤差・相対誤差、前進誤差・後退誤差、条件数）と、浮動小数点数の丸めのモデルは 誤差(数値解析) にまとめてある。問題そのものが入力の小さな変化に敏感かどうか（条件数）と、アルゴリズムが途中の誤差を増幅するかどうか（安定性）は別のことで、精度はこの 2 つの組み合わせで決まる（同記事の命題「前進誤差は条件数と後退誤差の積で決まる」）。
収束の速さは次のように言い表す。反復で作る列 $x_k\to x^*$ について、$|x_{k+1}-x^*|\le C|x_k-x^*|^p$（$p=1$ なら $0< C< 1$）となる定数があるとき、$p$ 次収束 という。$p=1$ を 線形収束、$p=2$ を 2 次収束 という。刻み幅 $h$ を使う方法で誤差が $Ch^p$ 以下になるとき、方法の 次数 は $p$ であるという。
典型的な問題と方法
| 問題 | 代表的な方法 | 誤差・収束について分かること | 記事 |
|---|---|---|---|
| 非線形方程式 $f(x)=0$ | 二分法、Newton 法 | Newton 法は単根の近くで 2 次収束 | Newton法 |
| 連立 1 次方程式 | Gauss の消去法（LU 分解） | 分解に約 $\frac23n^3$ 回の演算、部分ピボット選択で成分の増大は $2^{n-1}$ 倍以下 | LU分解 |
| 最小二乗問題 | 正規方程式、QR 分解、特異値分解 | 正規方程式は条件数を 2 乗にする | 最小二乗法、特異値分解、Moore–Penrose逆行列 |
| 関数の補間・近似 | Lagrange 補間、Chebyshev 多項式 | 補間の誤差は $\frac{f^{(n)}(\xi)}{n!}\prod_i(x-x_i)$ | Lagrange補間、Chebyshev多項式、Weierstrassの近似定理 |
| 数値積分 | 台形公式、Simpson の公式、Gauss 求積 | 台形公式の誤差は $h^2$ の定数倍以下、Gauss 求積は $n$ 点で次数 $2n-1$ まで正確 | 台形公式とSimpsonの公式（高校数学）、直交多項式、Euler–Maclaurinの公式 |
| 常微分方程式 | Euler 法、Runge–Kutta 法 | Euler 法の大域誤差は $h$ の定数倍以下で、安定のための刻み幅の制限がある | 応用数学 |
| 偏微分方程式 | 差分法、有限要素法 | 有限要素法の誤差は部分空間での最良近似の定数倍以下 | Lax–Milgramの定理 |
$f$ を $[a,b]$ 上の連続関数で $f(a)f(b)< 0$ とする。$a_0:=a$、$b_0:=b$ とし、中点 $c_k:=\frac{a_k+b_k}2$ で $f(a_k)f(c_k)\le0$ なら $[a_{k+1},b_{k+1}]:=[a_k,c_k]$、そうでなければ $[c_k,b_k]$ とする（$f(c_k)=0$ なら止めてよい）。どの段でも両端の $f$ の値は異符号か一方が $0$ なので、中間値の定理 により $[a_k,b_k]$ は $f$ の零点を含み、長さは $\frac{b-a}{2^k}$ である。よって $[a_k,b_k]$ の中の零点 $x^*$ について $|c_k-x^*|\le\frac{b-a}{2^{k+1}}$ である。誤差の上界は毎回半分になるが、誤差そのものが毎回減るとは限らない（$c_0$ がたまたま零点に近いと、$c_1$ のほうが遠くなりうる）。Newton 法と違って $f$ の微分可能性も初期値の近さもいらず、そのかわり速さは 2 次収束に及ばない。$f(x)=x^2-2$、$[a,b]=[1,2]$ では、$c_{10}$ と $\sqrt2$ の差は $2^{-11}< 5\times10^{-4}$ 以下である。
表の「分かること」はどれも、各記事の定理に仮定付きで述べられている。Newton 法は Newton法 の定理「局所収束と2次収束」、LU 分解は LU分解 の命題「分解と代入の演算回数」と定理「部分ピボット選択での増大率の上界」、正規方程式は 最小二乗法 の命題「正規方程式の条件数」、補間の誤差は Lagrange補間 の定理「補間の誤差」、台形公式は 台形公式とSimpsonの公式（高校数学） の定理「台形公式の誤差の上界」、Gauss 求積は 直交多項式 の定理「Gauss 求積」、Euler 法は 応用数学 の定理「Euler 法の大域誤差」と命題「Euler 法の安定性の条件」、有限要素法は Lax–Milgramの定理 の命題「Céaの誤差評価」である。
誤差の 3 つの源
- データの誤差．入力が測定値や前の計算の結果なら、はじめから誤差を含む。その影響の大きさは問題の条件数で決まり、アルゴリズムをどう工夫しても減らせない。
- 打ち切り誤差．微分を差分で、積分を有限和で、無限級数を有限和で置き換えることによる誤差である。刻み幅や項数で制御でき、方法の次数が速さを決める。
- 丸め誤差．計算機は数を有限桁で表すので、1 回の演算ごとに相対的に小さな誤差（単位丸め誤差の程度）が入る。1 回分は小さいが、演算の回数が多いと積み重なり、アルゴリズムによっては増幅される。
打ち切り誤差を十分小さくしても、丸め誤差が増幅されれば全体の誤差は小さくならない。$e^{-20}$ を Taylor 多項式の和で計算すると、打ち切り誤差は $10^{-34}$ 未満なのに、大きな項どうしの打ち消し合いで正しい桁がほとんど残らない（誤差(数値解析) の反例「打ち切り誤差が小さくても全誤差は小さくない」）。下の例は、打ち切り誤差のない漸化式でも、丸め誤差がどう伝わるかで結果が決まることを示す。
読む順の目安
- 誤差の言葉．誤差(数値解析) で絶対誤差・相対誤差、条件数、丸めのモデルを押さえる。この記事の下の例は、その「安定性」の具体例である。
- 方程式を解く．Newton法 で 2 次収束の仕組みを見る。連立 1 次方程式は LU分解、最小二乗問題は 最小二乗法 と 特異値分解。
- 関数を近似する．Lagrange補間 で補間多項式の存在と誤差を見て、Chebyshev多項式 の最小最大の性質と Weierstrassの近似定理 で、多項式による近似の限界と可能性を知る。
- 積分する．台形公式とSimpsonの公式（高校数学） から始め、Euler–Maclaurinの公式 で台形公式の誤差の構造を、直交多項式 と Legendre多項式 で Gauss 求積を学ぶ。
- 微分方程式を解く．応用数学 の Euler 法の誤差と安定性の議論から、刻み幅と精度・安定性の関係を見る。偏微分方程式の有限要素法の基礎は Lax–Milgramの定理 にある。
議論の例：漸化式の安定性
誤差の伝わり方の一般式
実数 $a_k,b_k$（$k\ge1$）について、列 $(y_k)$ を $y_k=a_ky_{k-1}+b_k$ で定める。各段で誤差 $\delta_k$ が加わった列 $(\tilde y_k)$ を
$$
\tilde y_0=y_0+\delta_0,\qquad\tilde y_k=a_k\tilde y_{k-1}+b_k+\delta_k\quad(k\ge1)
$$
とすると、$n\ge0$ について
$$
\tilde y_n-y_n=\sum_{k=0}^n\Bigl(\prod_{j=k+1}^na_j\Bigr)\delta_k
$$
である（空の積は $1$）。特に、すべての $k$ で $|\delta_k|\le\delta$ なら $|\tilde y_n-y_n|\le\delta\sum_{k=0}^n\prod_{j=k+1}^n|a_j|$ である。
$e_k:=\tilde y_k-y_k$ とおく。2 つの漸化式を引くと、$b_k$ が消えて $e_k=a_ke_{k-1}+\delta_k$（$k\ge1$）、$e_0=\delta_0$ である。主張の式を $n$ についての帰納法で示す。$n=0$ では右辺は $\delta_0$ である。$n-1$ で成り立てば
$$
e_n=a_n\sum_{k=0}^{n-1}\Bigl(\prod_{j=k+1}^{n-1}a_j\Bigr)\delta_k+\delta_n=\sum_{k=0}^{n-1}\Bigl(\prod_{j=k+1}^na_j\Bigr)\delta_k+\delta_n
$$
で、最後の $\delta_n$ は $k=n$ の項（空の積 $1$ を掛けたもの）なので、$n$ でも成り立つ。不等式は三角不等式から従う。$\square$
$\delta_k$ は、計算機での丸め誤差や、出発値 $y_0$ の誤差を表す。$|a_j|\le1$ ならどの $\delta_k$ も増幅されず、誤差は高々 $(n+1)\delta$ である。逆に $|a_j|$ が大きいと、はじめの小さな誤差が $\prod|a_j|$ 倍に拡大される。
積分を漸化式で求める
$n\ge0$ について
$$
I_n:=\int_0^1x^ne^{x-1}\,dx
$$
とおく。
- $I_0=1-e^{-1}$ であり、$n\ge1$ について $I_n=1-nI_{n-1}$ である。
- $n\ge0$ について $\dfrac1{e(n+1)}< I_n< \dfrac1{n+1}$ である。
1：$I_0=\bigl[e^{x-1}\bigr]_0^1=1-e^{-1}$ である。$n\ge1$ では 部分積分 により $I_n=\bigl[x^ne^{x-1}\bigr]_0^1-n\int_0^1x^{n-1}e^{x-1}dx=1-nI_{n-1}$ である。
2：$0< x< 1$ で $e^{-1}< e^{x-1}< 1$ なので、$x^n$ を掛けて積分すると $\frac1{e(n+1)}< I_n< \frac1{n+1}$ である（$\int_0^1x^n\,dx=\frac1{n+1}$。被積分関数の差は $(0,1)$ で正の連続関数なので不等号は等号にならない）。$\square$
漸化式 $I_n=1-nI_{n-1}$ は、$I_0$ から順に $I_1,I_2,\dots$ を計算する方法（前向き）を与える。同じ式を $I_{n-1}=\frac{1-I_n}n$ と書き直すと、大きな $N$ から $I_{N-1},I_{N-2},\dots$ と逆に計算する方法（後ろ向き）にもなる。数学的には同じ式だが、誤差の伝わり方は正反対である。
各段の誤差が $|\delta_k|\le\delta$ であるとする。
- 前向き：$\tilde I_0=I_0+\delta_0$、$\tilde I_k=1-k\tilde I_{k-1}+\delta_k$ で計算すると
$$ \tilde I_n-I_n=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\delta_k $$
であり、出発値だけに誤差がある場合（$\delta_k=0$、$k\ge1$）は $\tilde I_n-I_n=(-1)^nn!\,\delta_0$ である。 - 後ろ向き：$N>n$ とし、$\tilde I_N:=0$ から $\tilde I_{k-1}=\frac{1-\tilde I_k}k+\delta_{k-1}$（$k=N,N-1,\dots,n+1$）で計算すると
$$ |\tilde I_n-I_n|\le\frac{n!}{(N+1)!}+e\,\delta $$
である。
1：thm-na-propagation を $a_j=-j$、$b_j=1$ で使うと、$\prod_{j=k+1}^n(-j)=(-1)^{n-k}\frac{n!}{k!}$ である。
2：$z_m:=I_{N-m}$（$0\le m\le N-n$）とおくと、$z_m=-\frac1{N-m+1}z_{m-1}+\frac1{N-m+1}$ なので、thm-na-propagation を $a_m=-\frac1{N-m+1}$ で使える。出発値の誤差は $\delta_0':=\tilde I_N-I_N=-I_N$ で、lem-na-integral の 2 により $|\delta_0'|< \frac1{N+1}$ である。$z$ の $m$ 段目は $I_{N-m}$ を求める段で、そこで加わる誤差は $\delta_{N-m}$ である。$m=N-n$ での係数は、$\delta_0'$ に対して $\prod_{j=n+1}^N\frac1j=\frac{n!}{N!}$、$\delta_k$（$n\le k\le N-1$）に対して $\prod_{j=n+1}^{k}\frac1j=\frac{n!}{k!}$ の絶対値をもつ。よって
$$
|\tilde I_n-I_n|\le\frac{n!}{N!}\cdot\frac1{N+1}+\delta\sum_{k=n}^{N-1}\frac{n!}{k!}
$$
である。$\frac{n!}{k!}\le\frac1{(k-n)!}$ なので最後の和は $\sum_{i\ge0}\frac1{i!}=e$ 以下である。$\square$
前向きでは、$I_0$ をどれほど精密に与えても、その誤差が $n!$ 倍に拡大される（$20!\approx2.4\times10^{18}$）。後ろ向きでは、出発値をでたらめに $0$ としても、その誤差は $\frac{n!}{N!}$ 倍に縮み、各段の丸め誤差も合計で $e\,\delta$ 以下にとどまる。
倍精度の浮動小数点数で計算した結果である（真の値は精度を上げた数値積分で求めた）。
| $n$ | 真の値 $I_n$ | 前向きの計算値 | 後ろ向き（$N=30$、出発値 $0$）の誤差の絶対値 |
|---|---|---|---|
| $5$ | $0.145532940573\ldots$ | $0.145532940573\ldots$ | $2.0\times10^{-17}$ |
| $10$ | $0.0838770701034\ldots$ | $0.0838770700583\ldots$ | $2.9\times10^{-18}$ |
| $15$ | $0.0590175408793\ldots$ | $0.0590337936419\ldots$ | $1.1\times10^{-18}$ |
| $18$ | $0.0501198549581\ldots$ | $-0.0294536707515\ldots$ | （計算せず） |
| $20$ | $0.0455448840758\ldots$ | $-30.1923948855\ldots$ | $2.8\times10^{-16}$ |
前向きの $I_{18}$ は負になり、lem-na-integral の 2 に反する。$I_{20}$ の誤差 $-30.2379\ldots$ は、倍精度で表した $I_0$ の誤差 $\delta_0=-1.2428\ldots\times10^{-17}$ の $20!$ 倍 $-30.2379\ldots$ と 10 桁近く一致し、途中の段の丸め誤差の影響は見えない。後ろ向きの $n=20$ の誤差は、cor-na-forward-backward の 2 の第 1 項 $\frac{20!}{31!}=2.96\ldots\times10^{-16}$ 以下である。
この例が示すのは、同じ数学の式でも、どの量からどの量を計算するかで問題の条件数が違うことである。$I_0$ から $I_n$ を求める問題は入力の誤差を $n!$ 倍にする条件の悪い問題で、$I_N$ から $I_n$ を求める問題は誤差を $\frac{n!}{N!}$ 倍にする条件のよい問題である。条件数については 誤差(数値解析) の定義「スカラー問題の相対条件数」を参照。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-na-propagation から誤差が増えないと言うための $\lvert a_j\rvert\le1$ | 前向きの漸化式 $I_k=1-kI_{k-1}$（$a_j=-j$） | 出発値の誤差が $n!$ 倍になる |
| Newton法 の 2 次収束の、零点が単根であること | $f(x)=x^2$ | 反復は $x_{k+1}=x_k/2$ で、線形収束にとどまる |
| 直交多項式 の Gauss 求積の、節点を直交多項式の根にとること | $\int_{-1}^1f\,dx\approx f(-1)+f(1)$ | $x^2$ で $\frac23$ でなく $2$ を返し、次数 $2n-1=3$ まで正確にならない |
| 台形公式とSimpsonの公式（高校数学） の誤差の上界の、$f''$ が有界であること | $f(x)=\sqrt x$（$[0,1]$） | 分割を倍にしても誤差は約 $2.8$ 分の $1$ にしかならず、$h^2$ に比例しない |
1 行目は cor-na-forward-backward の 1 と ex-na-double で確かめた。2 行目は Newton法 の注意「反例：収束しない初期値と2次収束しない零点」、3 行目は 直交多項式 の例「反例の確かめ」の 4、4 行目は 台形公式とSimpsonの公式（高校数学） の例「反例：端で $f''$ が有界でない」にある。
補足
- 数値解析と応用数学．数値解析は、微分方程式のモデルを解く、データに曲線を当てはめるといった応用数学の多くの場面で、最後の段を受け持つ（応用数学）。
- 理論の道具．収束の証明には、関数を多項式で近似する理論（Weierstrassの近似定理、Chebyshev多項式 の最小最大の性質）、関数解析（一様有界性原理 による数値積分の公式の列の収束の判定、Lax–Milgramの定理 による有限要素法の誤差評価）が使われる。
- 誤差の上界を計算で保証する．定理の誤差の上界は、$\max\lvert f''\rvert$ のような量が分からないと数値にならない。丸めの向きを制御する区間演算などで、真の値を必ず含む区間を計算機に出させる方法を精度保証付き数値計算という（誤差(数値解析) の節「安定性と精度保証」）。漸化式の例のように、計算の向きを変えるだけで出発値の誤差に掛かる係数が $n!$ から $\frac{n!}{N!}$ に変わることもあり、上界を計算できる形に持ち込むことが数値解析の仕事の一部である。
- 反復法と不動点．Newton 法を含む多くの反復法は、写像の不動点を求める問題と見なせ、縮小写像であれば線形収束する（Newton法 の命題「Newton写像の不動点と縮小性」）。
関連項目
- 前提: 誤差(数値解析), Newton法, Lagrange補間
- 方法: LU分解, 最小二乗法, 特異値分解, 直交多項式, Legendre多項式
- 比較: 応用数学
- 発展: 一様有界性原理, Lax–Milgramの定理, Euler–Maclaurinの公式
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
