線形計算 |
作成日：2014-01-11 最終更新日： |
現在広く使われている線形計算の基本的算法に関して、その算法がどのような考えに基づいて導かれるかについて論じている。
第3章で連立１次方程式の解法IIIとして「共役勾配法」が解説されている。
そして「」内は「きょうやくこうばいほう」と読む．
という脚注がある。
共役は「きょうえき」と読むことも多いから、あえてこう脚注をふっているのだろう。
でも、読み方の違いが意味の違いになるのかどうか、私にはよくわからない。
行列 `A` とベクトル `bbx` が与えられているとき、 一般の `n` 元連立 1 次方程式 `A bbx = bb(b)` を解く一つの方法は反復法である。 これは、先の式を同値の `bbx = M bbx + bbc` に書き直して、`bbx^((k+1)) = Mbbx^((k)) + bbc` (`k` は繰り返し回数） の形で `bbx` を一定の精度になるまで反復する方法である。
上記の加速法で、列 `bbx^((0)), bbx^((1)), cdots, bbx^((k))` が生成されたとき、
`hat bbx^((k)) = sum_(j=0)^k alpha_j^((k)) bbx^((j)) (k = 0, 1, 2, cdots) `
を作って近似解を改良したい。ただし、`sum_(j=0)^k alpha_j^((k)) = 1` という制約をおく。 この係数 `alpha_j^((k))` に対して、多項式 `P_k(lambda) = sum_(j=0)^k alpha_j^((k)) lambda^j` を考え、 最適な加速ができる多項式を見つければよい。途中を省略して結論を述べると、 `ccP_k` を `k` 次以下の多項式全体を表す記号とすれば、次の最大最小化問題
`min_(P_k in ccP_k, P_k(1) = 1) max_(1 <= i <= n) |P_k(lambda_i)|`
を解けばよい。ここで、いくつかの仮定を持ち込むと、`k` 次のチェビシェフ多項式が出てくるのだ。驚きである。
p.83 からの第6章は、固有値問題の解法 I (ベキ乗法系）である。 ここでは、Schur 分解という用語が出てきている。シューア分解やシュール分解と呼ばれるようだ。 Google でシューア分解は 141 件、シュール分解は 143 件、シュア分解が310 件、シュアー分解が 4 件だったので、 最も多かったシュア分解 (Schur decomposition) の名前で呼ぼう。 Wikipedia によれば、シュア(Issaj Schur)は数学者であり、 代数学で成果を残したという。なお、Wikipedia のシュアに関する項はイサイ・シューアと書かれていて、 彼の名前を関した項目は、シュア分解のほか、シュールの不等式、シュアー補行列、シューア多項式など、 表記の揺れがある。
では、シュア分解とは何か、この本で調べてみよう。
一般の複素行列 `A` は，ユニタリ行列 `U` と上三角行列 `S` を用いて，
`A = U S U^tt(H)`
と分解できる（分解は一意ではない）．ここで`(*)^tt(H)` は共役転置を表す． `U = [bbu_1, cdots, bbu_n]` の列ベクトル `bbu_j` を Schur ベクトル と呼ぶ．
ここで、ユニタリ行列（ユニタリー行列）とはどういう行列だったか。これは `U U^tt(H) = I` となる行列のことだ 調べたらそうであったのだが、私は忘れてしまっていた。情けない。 ちなみに、`(*)^tt(H)` は共役転置を表すが、 同じ共役転置で`(*)^tt(**)` や`(*)^tt(†)` を使っている本もあるのでややこしい。 右肩の H を使う流儀は、Hermite (エルミート、エルミット) にちなんでいるのだろう。 そして、行列 `A^tt(H)` を `A` のエルミート共役行列（エルミット共役行列）または随伴行列と呼ぶ。 ちなみに、`(*) = (*)^tt(H)` となる行列はエルミート行列（エルミット行列）と呼ばれる。 次に読み進めていくと次の文章がある。
Hermite 対称でない場合に固有ベクトルではなく Schur ベクトルを計算するのは， これがユニタリ変換の繰り返しによって数値的に安定に計算できるからである．
ここで、Hermite 対称でない場合というが、どの行列が Hermite 対称でない場合なのか。そして、
だいたい Hermite 対称の場合とは何か。本文を読むと、
一般の複素行列 `A` が Hermite 対称でない場合ということがわかる。
というのは、ここで引用した本文の前に、`A` が Hermite 行列ならば
があるからだ。
ということは、Hermite 対称でないということは、エルミート行列ではない行列、ということだ。
エルミート対称とは、行列 `A` とそのエルミート行列 `A^tt(H)` が等しい、ということを表すのだろう。
ここまでで一苦労だ。
さらに、ユニタリ変換の繰り返しとあるが、ユニタリ変換とは何か。他の岩波講座を見てみると、
群と表現 (p.33) では
`tt(V)` から `tt(V)` への線型変換で，`tt(V)` の内積を保存し全射であるものをユニタリ変換(unitary transformation)という．
ベクトル解析と多様体II (p.160) では
ユニタリ・ベクトル空間`V^n` の複素正則線形変換であって，ベクトルの長さを変えないものをユニタリ変換という．
とある。ではユニタリ変換は具体的にはどんな行列なのだろうか。ユニタリ行列で与えられる一次変換はユニタリ変換なのだろうか。 結論からいうとそうなのだが、いろいろ調べてやっとわかるところに俺の弱さがある。 たとえば、ベクトル解析と多様体II (p.161) では次のように書かれている。
標準形のエルミート形式（中略）および対称反双線形形式（中略）をもつ数ベクトル空間 `CC^n` のユニタリ変換は
`U^(**)U = UU^(**) = I_n`
をみたすユニタリ行列 `U` で定まる複素線形変換である。
さて同書に戻って、シュア分解の解法を調べる。p.84 では、行列 `A` に対して有限回の演算で中間形 `hatA`をもとめ、
そこから固有値を反復計算によって固有値を求めると説明されている。中間形は、
`A`から有限回(`O(n^3)`回)の四則と開平演算によるユニタリ相似変換`hat A=U^(tt(H))AU`(中略)によって計算される．
とあるが、
ユニタリ相似変換とは何か。ユニタリ変換とどこが違うのか。
Wikipedia や OKwave などで調べると、相似変換は `n`次行列`A` を `n`次行列`B` に変換するときのことばで、 `n`次正則行列`P` により `B = P^-1AP` となる変換である。この `P` がユニタリ行列であれば、ユニタリ相似変換という。 難しいな。
第6章で、固有値問題の解法が述べられている。この章ではベキ乗法系の解法が解説されているが、
この解法では第1段の前処理のあと第2段で反復計算が必要となる。p.85 で
第2段の反復計算では，随分と凝ったさまざまな工夫の複雑な組合せから成り立っているので，
信頼できる数学ソフトウェアを利用するのがよい．
とある。どんなソフトウェアならよいのだろうか。
Wikipedia で固有値を調べると、解析ソフトウェアとして NAG と IMSL が挙げられている。 NAG 、IMSL ともに商用である。フリー（オープンソース）のものはないだろうか。
Wikipedia の数値解析ソフトウェアの項を調べると、線形計算のライブラリとして LAPACK があることがわかった。 LAPACK は EISPACK の流れを汲んでいるから、信頼できるものと思われる。
それから、数値計算処理のデパート（と勝手に俺が呼んでいる）Matlab に対抗すべく、 これに近い機能をもつオープンソースの octave がある。こちらも使えるだろう。
Matlab と並び称されているのが Mathematica や Maple である。 どちらも商用であるが世評は高く、役に立つと思う。
参考文献には、線形計算のソフトウェアを扱った書物として、G. H. Golub and C. F. van Loan: Matrix
Computations, 2nd ed. Johns Hopkins Univ. Press, 1989 が挙げられている。
この本は有名であるらしい。
たとえば、池辺八洲彦らの「現代線形代数―分解定理を中心として―」のまえがき ii ページでは、
ゴラブ・ヴァンロアン共著『行列計算』第3版(中略)などの標準的数値線形代数解説書
とある。
ちなみに、最新版は第4版(2013)で、http://www.cs.cornell.edu/cv/GVL4/golubandvanloan.htm にある。
目次を訳すと次の通り。
索引は 747 ページから始まるので、大部な書であることがわかる。 文献一覧だけでも 66 ページある。
数式記述はASCIIMathMLを、 数式表現はMathJax を用いている。
| 書 名 | 線形計算 |
| 著 者 | 森 正武、杉原 正顕、室田一雄 |
| 発行日 | 1994 年 2 月 10 日 |
| 発行元 | 岩波書店 |
| 定 価 | 3495 円（税別） |
| サイズ | |
| ISBN | 4-00-010418-3 |
| NDC |
