数値計算の基礎と応用 [新訂版] のキーワード

方針

できる限り式を書く．
調べたら良いものはキーワードだけ記述する．

本編

第1章 数値計算の基礎

真値$x$に対する近似値$x'$の誤差$\Delta x=x'-x$について，

• $|\Delta x|$を絶対誤差
• $\frac{|\Delta x|}{|x|}$を相対誤差
• $-\log_{10}\frac{|\Delta x|}{|x|}$を有効桁数

機械実数には以下の5つがある．

• 正規数
• 0
• 副正規数 : 正規数より絶対値の小さい有効桁数の少ない数
• $\pm\infty$ : 絶対値が正規数の限界を超えた演算の結果
• NaN : 不正規な演算の結果

2進浮動小数点は以下のような形式で表す．

$a=(-1)^s2^e\sum_{k=0}^{n}2^{-k}f_k$

$(-1)^s$は符号，$2^e$は指数，$\sum_{k=0}^{n}2^{-k}f_k$仮数という．

2進コードは以下のような形式になる．

$| s | e_m ... e_1 e_0 | f_1 f_2...f_n |$

このとき指数$e$は以下のような形式になる．

$e_{min}=2-2^m$
$e_{max}=2^m-1$
$e=(e_m ... e_1 e_0)-e_{max}$
$e_{min}-1 \leq e \leq e_{max}+1$
$f=0.f_1f_2...f_n$

このとき2進コードは以下の5種類がある．

• 正規数 : $e_{min} \leq e \leq e_{max}$のとき，$a=(-1)^s2^e(1.f_1f_2...f_n)_2$
• 0 : $e=e_{min}-1$，$f=0$のとき，$a=0$
• 副正規数 : $e=e_{min}-1$，$f\neq0$のとき，$a=(-1)^s2^{e_{min}}(0.f_1f_2...f_n)_2$
• $\pm\infty$ : $e=e_{max}+1$，$f=0$のとき，$a=\pm\infty$
• NaN :$e=e_{max}+1$，$f\neq0$のとき，$a=NaN$

丸め誤差は正規数の正確な演算の後に，仮数が$n+1$桁を超えると，$n+1$桁に丸めて正規数にしたときに起こる誤差．
丸めの

• 絶対誤差 : $|\hat{x}-x|=2^{e-n-1}$
• 相対誤差 : $\frac{|\hat{x}-x|}{|x|}=2^{-n-1}$

1変数関数$f(x)$の誤差伝搬

• 絶対誤差 : 元の絶対誤差の$f'(x)$倍
• 相対誤差 : 元の相対誤差の$\frac{xf'(x)}{f(x)}$倍

多変数関数$f(x_1,x_2,...,x_n)$の誤差伝搬

• 絶対誤差 : 各要素の絶対誤差$\Delta x_i$に対して$\frac{\delta f}{\delta x_i}$倍したもの

桁落ちは絶対値の近い加減算のときに，有効桁数が少なくなること．乗除算では起こりにくい．

桁落ちの回避方法3選

• 分子の有利化 : $\sqrt{1+x}-1=\frac{x}{\sqrt{1+x}+1}$
• 指数法則とsinh : $e^{3x}-e^x=e^{2x}(e^x-e^{-x})=2e^{2x}\sinh x$
• 積和公式と倍角公式 : $cos(a+x)-cos(a)=-2sin(a+x/2)sin(x/2)$や$1-cos2x=2sin^2x$

第2章 関数計算

様々な関数の値をコンピュータで計算する方法．
基礎は関数近似の理論．

$n$次多項式$p_n(x)=a_0x^n+a_1x^{n-1}+...+a_{n-1}x+a_n$はネスティング法で計算すると早い．

補助的な$k$次多項式$y_k=a_0x^k+a_1x^{k-1}+...+a_k$，$y_0=a_0$を初期値としたとき，$y_k=y_{k-1}x+a_k$と計算し，最終的に$y=y_n=p_n(x)$を得る．

ある関数$f(x)$を計算するときに，多項式に変形することがある．
多項式の変形には以下の方法を使うことが有名である．

• テイラー展開 : 基本的な関数は既にテイラー展開されている
• 多項式補間 : 高階微係数の計算が簡単ではない場合，使われる
• チェビシェフ補間 : 誤差を小さくできる
• ニュートン補間 : ラグランジュ補間の別形式

第3章 数値積分

関数の定積分を有限個の関数地を使って近似する方法．

関数$f(x)$の有限区間$[a,b]$において，$n$個の内分点$x_1,x_2,...,x_n$をとり，その分点を使って積分する方法を$n$点補間型積分則という．

積分則には以下の3つがある．

• 中点則
• 台形則（滑らかな周期関数の1周期積分と滑らかな急減少関数の無限積分にとても有効）
• シンプソン則

ある積分を滑らかな急減少関数の無限積分に変換するときに，2重指数的に減少するような変換する方法を2重指数型積分公式という．

基本的な変換式はこれ．
$\int_{a}^{b}f(x)dx=\int_{-\infty}^{\infty}g(t)dt, g(t)=f(\phi(t))\phi'(t)$

具体的に，

• 有限区間$[a,b]$上の積分には，$r=(b-a)/2, c=(a+b)/2$として，$\phi(t)=r\tanh (\frac{\pi}{2}\sinh t)+c, \phi'(t)=\frac{\pi r \cosh t}{2\cosh^2 (\frac{\pi}{2}\sinh t)}$
• 半無限区間$[0,\infty)$上の緩減少関数の積分には，$\phi(t)=e^{\frac{\pi}{2}\sinh t}, \phi'(t)=\frac{\pi}{2}(\cosh t)e^{\frac{\pi}{2}\sinh t}$
• 無限区間$(-\infty,\infty)$上の緩減少関数の積分には，$\phi(t)=\sinh (\frac{\pi}{2}\sinh t), \phi'(t)=\frac{\pi}{2}(\cosh t)\cosh (\frac{\pi}{2}\sinh t)$

第4章 線形変換の誤差

ベクトルのノルムは以下の3つがある。

1. 1-ノルム : $ ||\textbf{x}||_ 1=\sum_{i=1}^{n} |x_i| $
2. 2-ノルム : $ ||\textbf{x}||_ 2=\sqrt{\sum_{i=1}^{n} |x_i|^2} $
3. $\infty$-ノルム : $ ||\textbf{x}||_ \infty=max_{1\leq i \leq n}|x_i| $

ベクトルの誤差について、

• 絶対誤差 : $||\Delta\textbf{y}|| \leq ||A||*||\Delta\textbf{x}||$
• 相対誤差 : $\frac{||\Delta\textbf{y}||}{||\textbf{y}||} \leq ||A|| *||A^{-1}|| *\frac{||\Delta\textbf{x}||}{{||\textbf{x}||}}$

行列のノルムは以下の3つがある。

1. 1-ノルム : $ ||\textbf{A}||_ 1=max_{1\leq j \leq n}\sum_{i=1}^{m} |a_{ij}| $
2. 2-ノルム : $ ||\textbf{A}||_ 2=\sqrt{\rho AA^T} $
3. $\infty$-ノルム : $ ||\textbf{A}||_ \infty=max_{1\leq i \leq n}|a_{ij}| $

行列$A$の条件数は$cond(A)=||A|| *||A^{-1}||$とあらわす。

第5章 線形方程式の直接解法

下三角行列と前進代入法

A\textbf{x}=
\left(
\begin{array}{ccccc}
a_{11} & & & O \\
a_{21} & a_{22} & & \\
\vdots & \vdots & \ddots & \\
a_{n1} & a_{n2} & \cdots & a_{nn}
\end{array}
\right)

\left(
\begin{array}{c}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{array}
\right)

=

\left(
\begin{array}{c}
b_1 \\
b_2 \\
\vdots \\
b_n
\end{array}
\right)

=\textbf{b}

と上三角行列と後進代入法によって直接求めることができる．

下三角行列と前進代入法は以下の式で求めることができる．

$i=1,2,...,n$の順に
$x_i=(b_i-\sum_{j=1}^{i-1}a_{ij}x_j)/a_{ii}$で求めることができる．

一般的な行列も前進消去によって上三角行列もしくは下三角行列に変形できる．部分ピボット法や正則性判定を行う必要がある．

相対誤差は，$\frac{||\Delta\textbf{x}||}{||\textbf{x}||} \leq ||A|| *||A^{-1}|| *\frac{||\Delta\textbf{b}||}{{||\textbf{b}||}}$である．

第6章 線形逆変換の構成

行列$A$をLU分解によって下三角行列と上三角行列に分解する．

$A=LU$

対称正定値行列$A$をコレスキー分解法によって下三角行列と上三角行列に分解する．

$A=LL^T$

逆行列$A^{-1}$も求めることができるが，どんな値になるのか興味をもったときのみ調べた方が良い．LU分解の3倍の時間がかかる，丸め誤差の影響を受ける，$n \times n$の2次元配列を要するため．

第7章 帯係数行列の線形方程式

帯行列に対して帯LU分解や帯コレスキー分解がある．

特殊な行列の場合，その構造を利用してより計算量の小さくなるような工夫をすることができるようになる．

第8章 最小2乗法

$m < n$のとき，過剰条件方程式という．

A\textbf{x}=
\left(
\begin{array}{ccccc}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{array}
\right)

\left(
\begin{array}{c}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{array}
\right)

=

\left(
\begin{array}{c}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{array}
\right)

=\textbf{b}

この方程式は一般には解をもたない．そこで$||\textbf{b}-A\textbf{x}||_{2}^{2}$

正規方程式
$A^TA\textbf{x}=A^T\textbf{b}$
を求めても良いが，数値計算上不安定になる．

ハウスホルダー変換とハウスホルダーQR分解法によって解を求められる．

第9章 非線形方程式

反復法によって求める．

2分法，ニュートン法，割線法がある．

第10章 固有値問題の数値解法

反復法によって求める．

累乗法や逆反復法がある．

第11章 常微分方程式

ルンゲ・クッタ法によって求められる．

第12章 偏微分方程式

有限差分法，ガウス・ザイデル法，SOR法がある．

感想

前半はメモできる分量であったが，後半はその体力がなくなった．
LU分解やQR分解，固有値固有ベクトルを求めるものは有名だったので省いた．
第11章と第12章はまったく記憶になかった．

参考文献
杉浦 羊，数値計算の基礎と応用 : 数値解析学への入門 新訂版，サイエンス社，2009，ISBN978-4-7819-1240-0