第11回プログラマのための数学勉強会のノート (連立一次方程式の反復解法 / 二次形式 / 多変数関数の極値 / 重積分 / 線形微分方程式)

このページはプログラマのための数学勉強会を聴講したときの個人的なノートである。

第11回プログラマのための数学勉強会(2013/11/21)の資料
http://nineties.github.io/math-seminar/11.html

第11回プログラマのための数学勉強会(2013/11/21)の動画
http://www.youtube.com/watch?v=_uHsrc0XIB4

連立一次方程式の反復解法 2013/11/23

http://nineties.github.io/math-seminar/11.html#/3

• 直接解法(ガウス消去法やLU分解法)は比較的サイズが小さい連立一次方程式に向いている
  • メモリの消費が大きいので
    • 100万次元だと行列の要素が1兆個にもなる
• 反復解法はサイズが大きく疎な(係数に0が多い)連立一次方程式に向いている
• 疎行列
  • ほとんどの成分が0である行列
  • 記憶容量を節約でき、疎行列に適したさまざまなアルゴリズムも存在する
• 疎行列の保存方式
  • 行優先のCSR(Compressed Sparse Row)方式
  • 列優先のCSC(Compressed Sparse Column)方式
  • すでにある行列を保存する場合に向いている
  • 行列を組み立てる途中では圧縮した状態では非効率なので連結リストやハッシュテーブルを使うとよい
  • 行列×列ベクトルの計算が通常は \( \mathcal{O}(n^2) \) の計算量がかかるが、 これらの疎行列では \( \mathcal{O}(非零要素数) \) で済む
• 反復法
  • 線形反復法、ニュートン法も反復法 -> 第4回
• ヤコビ法
  http://nineties.github.io/math-seminar/11.html#/8
  • 対角行列を使う方法
  • 計算の打ち切りの条件は \( \frac{\left\|\mathbf{x}_{i+1} - \mathbf{x}_i\right\|}{\left\|\mathbf{x}\right\|} \) など相対誤差で評価すること。ノルムでなくても成分同士の差の最大値でもよい。
  • スペクトル半径
    http://nineties.github.io/math-seminar/11.html#/12
  • ヤコビ法の収束条件
    http://nineties.github.io/math-seminar/11.html#/13
• ガウス・ザイデル法
  http://nineties.github.io/math-seminar/11.html#/14
• 逐次過大緩和法(SOR法)
  http://nineties.github.io/math-seminar/11.html#/14

二次形式 2013/11/23

http://nineties.github.io/math-seminar/11.html#/15

• 2次の項のみの多変数関数を行列の積で表す形式
• \( f(\mathbf{x}) = \mathbf{x}^T \mathbf{Ax} \)
  \( \mathbf{A}^T = \mathbf{A} \) (つまり \( \mathbf{A} \) は対称行列)
• 例 \[ \begin{aligned} f(x,y) &= x^2 + 3xy + 2y^2 \\ &= \begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} 1 & \frac{3}{2} \\ \frac{3}{2} & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \end{aligned} \]
• 実対称行列
  • 実数係数の多項式の\( \mathbf{A} \)は実数成分の対称行列になりこれを実対称行列という
  • 実対称行列の固有値はすべて実数である
    http://nineties.github.io/math-seminar/11.html#/20
  • 実対称行列の直交行列により対角化可能
    http://nineties.github.io/math-seminar/11.html#/21
• 二次形式の標準形
  http://nineties.github.io/math-seminar/11.html#/23
  • \(x^2\)や\(y^2\)の項のみになり、\(xy\)の項がなくなる

多変数関数の極値 2013/11/23

http://nineties.github.io/math-seminar/11.html#/26

• ヘッセ行列
  • \(n\)変数関数について\(\mathbf{a}\)について
  • \[ \mathbf{H}(f)(\mathbf{a}) = \left. \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n} \\ \frac{\partial^2 f}{\partial x_2\partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n\partial x_1} & \frac{\partial^2 f}{\partial x_n\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \\ \end{pmatrix} \right|_{\mathbf{x}=\mathbf{a}}\]
  • 対称行列になる
• 極値の判定 http://nineties.github.io/math-seminar/11.html#/31
  • \(\mathrm{grad}f(\mathbf{A}) = \mathbf{0}\) かつ \( \mathbf{H} \)の固有値がすべて正 \(\Rightarrow\) 極小値
  • \(\mathrm{grad}f(\mathbf{A}) = \mathbf{0}\) かつ \( \mathbf{H} \)の固有値がすべて負 \(\Rightarrow\) 極大値

重積分 2013/11/26

http://nineties.github.io/math-seminar/11.html#/34

• 一変数関数の定積分
  • リーマン和の極限 \[ \int_a^b f(x) \mathrm{d}x = \lim_{n \rightarrow \infty} \sum_{i=1}^n f(t_i)(x_i - x_{i-1}) \]
• 二変数関数の定積分
  http://nineties.github.io/math-seminar/11.html#/37
• 重積分の性質
  http://nineties.github.io/math-seminar/11.html#/40
• 重積分から累次積分(逐次積分)への変換
  http://nineties.github.io/math-seminar/11.html#/42
• 積分変数の変換
  http://nineties.github.io/math-seminar/11.html#/49
  • \[ \int_D f(x,y) \mathrm{d}x \mathrm{d}y = \int_{D^{\prime}} f(\phi(p,q),\psi(p,q)) \left| J \right| \mathrm{d}p \mathrm{d}q \]
  • ヤコビアン
    • \[ J = \det \begin{pmatrix} \frac{\partial \phi}{\partial p} & \frac{\partial \phi}{\partial q} \\ \frac{\partial \psi}{\partial p} & \frac{\partial \psi}{\partial q} \\ \end{pmatrix} \]
• 平行四辺形の面積は行列式で表せる
  http://nineties.github.io/math-seminar/11.html#/47
• 二変数に限らず一般に\(n\)変数でも同じ
  http://nineties.github.io/math-seminar/11.html#/52
• 多重積分の数値計算は累次積分に変換して数値積分を繰り返せばよいが、計算量ば爆発的に増えてしまう。 積分区間を\(n\)に分割するとして\(m\)重積分は \( \mathcal{O}(n^m) \) の計算量になってしまう。 従って多重積分の数値積分はモンテカルロ法がよく使われる。
• 実際に計算する多変数関数では、疎行列と同じようにすべての変数が関わりあうのではなく、 一部の変数同士のみが影響をしあう。その場合にグラフ理論などを使って、 どのように計算量を減らすかの工夫が必要。

線形微分方程式 2013/11/26

• \[ P(x) \frac{\mathrm{d}^2 y}{\mathrm{d}x^2} + Q(x) \frac{\mathrm{d}y}{\mathrm{d}x} = 0 \] の微分方程式の解を \( y_1, y_2 \) とすると、 \( ay_1 + by_2 \) も解となる。-> 2次の線形空間
  すべての解はこの2次の線形空間に収まる
• \[ \frac{\mathrm{d}}{\mathrm{d}x} e^{kx} = k e^{kx} \] は、\(k\)を固有値、\( e^{kx} \) を固有ベクトルと捉えることもできる。