rej55's note

数学とか工学とかの話 勉強したことのメモなど

Krylov部分空間の基本

とても久しぶりの更新となりました.ブログ欲が出てきたので、復活したいと思います. 以前までの記事の書き方と変えて,単にまとめるだけでなく紹介する形の文体を取っていきたいと思います.

線形連立方程式数値計算法は数値シミュレーションを代表として工学上非常に重要な研究対象となっています.係数行列が正定値対称となる場合の線形連立方程式数値計算法として、一般に共役勾配法と呼ばれる反復法が非常に有効であることが知られています.

共役勾配法はKrylov部分空間法の一種で、Krylov部分空間と呼ばれる線形部分空間をベースに解を探索します.今回はKrylov部分空間の基本的な性質をまとめます.

定義

行列\( A \in \mathbb{R}^{n\times n} \)とベクトル\( b \in \mathbb{R}^n \)に対し,

\( \mathcal{K}_{r}(A;b) = \mathrm{span} ( b, Ab, A^{2} b, \ldots , A^{r-1} b ) \)

をKrylov部分空間と呼ぶ.

Krylov部分空間法は,\( r \)ステップにおける近似解を\( \mathcal{K}_{r}(A;b) \)の中から探すアルゴリズムとなっています.この近似解を\( \mathcal{K}_{r}(A;b) \)の基底を用いてどのように構成するのかによってさまざまなバリエーションがあります.

Krylov部分空間の基本的な性質を説明します.

補題

\( r\in \mathbb{N} \)に対し,

\( \mathcal{K}_{r}(A;b) \subseteq \mathcal{K}_{r+1}(A;b) \)

をみたす.

証明

Krylov部分空間の定義より明らか.(証明終)

定理

正則な行列\( A \in \mathbb{R}^{n\times n} \)とベクトル\( b \in \mathbb{R}^n \)を考える.\(\mathcal{K}_{r}(A;b) = \mathcal{K}_{r+1}(A;b) \)をみたす最小の\(r \in \mathbb{N}\)に対し,\( Ax = b \)をみたす\(x \in \mathbb{R}^n \)は\(\mathcal{K}_{r}(A;b)\)に含まれる.

証明

\(\mathcal{K}_{r}(A;b) = \mathcal{K}_{r+1}(A;b) \)であることから,

\( A^{r}b = c_{0}b + c_{1}Ab + \cdots + c_{r-1}A^{r-1}b \)

をみたす\(c_{0}, c_{1}, \ldots, c_{r-1} \)が存在する.ここで,\(c_{0} = 0\)とすると一次独立性から\(r \)が最小であることと矛盾するため,\(c_{0} \neq 0\)である.このとき,

\( A\left(\frac{1}{c_{0}}A^{r-1}b - \frac{c_{r-1}}{c_{0}}A^{r-2}b - \cdots - \frac{c_{1}}{c_{0}}b \right) = b \)

と変形できる.したがって,\(Ax = b\)をみたす\(x \)は,

\( x = \frac{1}{c_{0}}A^{r-1}b - \frac{c_{r-1}}{c_{0}}A^{r-2}b - \cdots - \frac{c_{1}}{c_{0}}b \)

となり,\( x \in \mathcal{K}_{r}(A; b) \)である.(証明終)

上記の定理はKrylov部分空間法に基づいて計算を行った場合における解の存在性を示しています. しかも,係数行列が\(n\)次の正方行列であれば,Krylov部分空間は\( \mathcal{K}_{n} \)以上に拡大することはないため,理論上反復計算を最大\( n\)ステップで終了させることができます.

しかしながら,実際には丸めなどの数値的な誤差の影響で必ず\( n \)ステップで収束するとは限りません.このあたりの話はまた別の機会に.

非線形システムの表現

有限次元の非線形制御対象は, 次のような微分方程式で表される.

\begin{align*} \dot{x} = f(x, u) \end{align*}

ここで, \( x(t)\)は状態ベクトルで, \( u(t) \)は入力である.

この非線形システムはいろいろな形態が考えられるため, この非線形なシステムのうちAffineな非線形システムに制限し, これに対しての可到達性, 可制御性, 安定性, フィードバック線形化について考えていくこととする. Affineな非線形システムは以下のような形で表現される.

\begin{align*} \dot{x} = f(x) + \sum_{i=1}^m g_i(x)u_i \ \ (i = 1, 2, \ldots, m) \end{align*}

この方程式のうち, \( f(x) \)をドリフト項と呼ぶ.

正規直交系

ヒルベルト空間\( H\)でもユークリッド空間と同じように\( <x, y> = 0 \)となるようなベクトル\(x, y\)は直交するといい, \(x \perp y\)と表す. 0でないベクトルの集合\( \{\phi_j \} \)が, \begin{align*} j \neq k \Rightarrow <\phi_j, \phi_k> = 0 \end{align*} を満たすとき, \( \{\phi_j \} \)は直交系であるという. さらに, すべての\( j \)について\( ||\phi_j|| = 1\)となっているとき, 正規直交系であるという.

線形代数学においては, あるベクトル空間の任意のベクトルを, そのベクトル空間内で1次独立なベクトルの族を用いて表せるとき, そのベクトルの族を基底と呼ぶのであった. ヒルベルト空間でも同様に基底を定義できるが, その際1次独立なベクトルの族を有限とは限らず, 無限に選ぶことができる. また, 基底が正規直交系であるとき, 正規直交基底と呼ぶのも線形代数学におけるベクトル空間の理論と同様である.

例として, \( \frac{1}{\sqrt{2\pi}}, \frac{1}{\sqrt{\pi}}\cos{t}, \frac{1}{\sqrt{\pi}}\sin{t}, \cdots , \frac{1}{\sqrt{\pi}}\cos{nt}, \frac{1}{\sqrt{\pi}}\sin{nt}, \cdots \)は, \begin{align*} \int^\pi_{-\pi} \cos{mt} \cos{nt} dt = 0 (m \neq n) \end{align*}

\begin{align*} \int^\pi_{-\pi} \cos{mt} \cos{mt} dt = \pi (m \neq 0) \end{align*}

\begin{align*} \int^\pi_{-\pi} \sin{mt} \sin{nt} dt = 0 (m \neq n) \end{align*}

\begin{align*} \int^\pi_{-\pi} \sin{mt} \sin{mt} dt = \pi (m \neq 0) \end{align*}

\begin{align*} \int^\pi_{-\pi} \sin{mt} \cos{nt} dt = 0 \end{align*}

となることから, これらは正規直交系であるといえる. これらはフーリエ級数に関する理論で登場することとなる.

ヒルベルト空間

ある集合\(H\)が複素ベクトル空間を作り, 任意の\(x, y, z\in H \)に次の性質を満たす内積\(<x, y>\)が定義されているものとする. \begin{align*} <x, x>\geq 0, <x, x> = 0 \Leftrightarrow x=0 \end{align*} \begin{align*} <x, y> = \overline{<y, x>} \end{align*} \begin{align*} <\alpha x, y> = \alpha <x, y> \end{align*} \begin{align*} <x+y, z> = <x, z> + <y, z> \end{align*} このとき, \( H \)を内積空間と呼ぶ.

内積空間\( H \)において, ノルムは, \begin{align*} ||x|| = <x, x>^{1/2} \end{align*} とすればよい.

このとき, シュワルツの不等式 \begin{align*} |<x, y>| \leq ||x||\cdot||y|| \end{align*} が成立する.

シュワルツの不等式がいえると, 三角不等式が成立し, 内積空間\( H \)は, 先ほどのようにノルムを定義するとノルム空間となる.

先ほどのノルムを導入すると, 内積空間はノルム空間となり, 連続性や収束性を議論することができるようになる. とくに, ベクトル演算やノルムなどは連続となる. しかも, 内積空間では内積も連続になる.

内積空間\( H \)が, 内積から定義されるノルム\( ||x|| = <x, x>^{1/2} \)に関して完備になっているとき, \( H \)をヒルベルト空間と呼ぶ. ヒルベルト空間はバナッハ空間であるから, バナッハ空間で成り立つ諸定理はヒルベルト空間でも成り立つ.

線形作用素

((X, Y \)をノルム空間とすると, \(X, Y \)はベクトル空間であるから, 写像\(T : X\to Y\)は, \begin{align*} T(\alpha_1 x_1 + \alpha_2 x_2) = \alpha_1 Tx_1 + \alpha_2 Tx_2, \ \ \ (x_1, x_2 \in X) \end{align*} となる. ただし, \(\alpha_1, \alpha_2\)はスカラーである. このとき, \(T \)を\(X \)から\(Y \)への線形作用素と呼ぶ. また, 作用素\( T \)の定義される点\( x\in X \)の集合\( D(T) \)を定義域と呼び, \(R(T) = \{Tx|x\in D(T)\}\)を値域と呼ぶ.

ここで, 線形作用素\( T \)に対してある\( M>0 \)がとれて, \begin{align*} ||Tx|| \leq M||x|| \end{align*} を満たすとき, \( T \)は有界であるという.

定理

\(X, Y \)をノルム空間とする. 線形作用素\( T: X\to Y \)が連続であることと有界であることは同値である.

証明

(必要性) 線形作用素\( T \)が\(x = 0 \)で連続であるとする. このとき, \( \epsilon = 1 \)ととると, 連続性の定義から \begin{align*} \exists \delta >0: ||x||<\delta \Rightarrow ||Tx||<1 \end{align*} となる. 任意の\(x \neq 0\)に対し, \(z = \delta x/2||x|| \)とおくと, \(||z|| = \delta/2 < \delta \)なので, \begin{align*} ||Tz|| = \frac{\delta}{2||x||} ||Tx||<1 \end{align*} すなわち, \begin{align*} ||Tx|| < \frac{2}{\delta} ||x|| \end{align*} となり, \( M = 2/\delta \)ととれば有界であるといえる.

(十分性) 線形作用素\( T \)が有界であるとき, \( x_n \to x\)とすると, \begin{align*} ||Tx_n - Tx|| = ||T(x_n - x)|| \leq M||x|| \to 0 \end{align*} となり, \(Tx_n \to Tx \)となり, 連続である.

証明終

また, 線形作用素\( T \)が有界であるとき, \(M \)の下限を\(||T||\)で表し, \( T \)のノルムと呼ぶ. また, 上限の定義から

\begin{align*} ||T|| = \sup_{||x||=1}||Tx|| \end{align*}

\begin{align*} ||T|| = \sup_{||x||\neq 0} \frac{||Tx||}{||x||} \end{align*}

となる.

縮小写像の原理

ノルム空間\( X \)の部分集合\( X_1, X_2 \)について, 写像\(F: X_1 \to X_2 \)が, 任意の\( x, y \in X_1 \)に対し,

\begin{align*} ||F(x) - F(y)|| \leq k||x-y||, \ \ \ (0\leq k <1) \end{align*}

を満たすとき, 写像\( F \)は縮小写像であるという. また, このとき\( F \)はリプシッツ連続であり, \( k \)をリプシッツ定数と呼ぶ. ただし, \( k \)は0から1の間に限らなくても正の値を持てばリプシッツ連続であり, 1より小さいときの場合のみ縮小写像と呼んでいる.

\( B \)がバナッハ空間であるとき, 写像\( F_B: B \to B \)が縮小写像であるとき, \(F_B\)はただ一つの不動点\( (z\in B: F_B(z) = z) \)が存在する. これを縮小写像の原理と呼ぶ.

このとき, 任意の\(x_n \in B \ (n \in \mathbb{N}) \) (ただし, \(x_n = F_B(x_{n-1}) \))としたとき,

\begin{align*} \lim_{n\to\infty} x_n = z \end{align*}

となることが知られている.

すなわち, 縮小写像であれば, 初期値を適当に決めて反復法で計算することにより厳密解へ収束するということになる.

バナッハ空間

大学の1年生の解析学で学ぶような実数の収束性は, 距離の概念を通して定義するように学んできた. より一般に収束を考える場合, ベクトル空間の各要素にノルムが定義されている必要がある.

ベクトル空間\(X\)の各要素\(x, y\)に, 以下の3つの性質を満たすようなノルム\( ||x|| \)が定義されているとき, \(X\)をノルム空間と呼ぶ.

\( ||x|| \geq 0, ||x||=0 \Leftrightarrow x=0 \)

\( ||\alpha x|| = |\alpha| ||x|| \)

\( ||x+y||\leq ||x||+||y|| \)

このようなノルム空間を考えることで, ベクトル空間で収束を考えることができる.

ノルム空間での点列\( \{ x_n \} \)を考え, これが\( a\in X\)に収束するとは,

\( ||x_n -a||\to 0 \ \ (n\to \infty) \)

となることである.

一般に, ノルム空間\( X \)において, 任意のコーシー列が\( X \)の点に収束する場合, \( X \)は完備であるといい, 完備なノルム空間のことをバナッハ空間と呼ぶ.