東京大学 情報理工学研究科 数理情報学 2018年8月実施 第4問

标签：

• Tokyo-University
• Lie-Trotter-Product-Formula-and-Operator-Splitting
• Matrix-Exponential
• Matrix-Norm

Author

hari64boli64

Description

$n$ 次複素正方行列 $X \in \mathbb{C}^{n \times n}$ に対し、$e^X := \sum_{k=0}^{\infty} \frac{1}{k!} X^k$ と定める。 ここで $X^0$ は $n$ 次単位行列 $I$ とする。 また、$n$ 次元複素ベクトル $x = (x_1, \ldots, x_n)^{\top} \in \mathbb{C}^n$ のノルムを $\|x\| := \left( \sum_{i=1}^{n} |x_i|^2 \right)^{1/2}$ と定める。 なお $\top$ は転置を表す。 さらに、行列 $X \in \mathbb{C}^{n \times n}$ のノルムを $\|X\| := \sup_{x \in \mathbb{C}^n, \|x\|=1} \|Xx\|$ と定める。 このとき、任意の $X, Y \in \mathbb{C}^{n \times n}$ に対し $\|X + Y\| \leq \|X\| + \|Y\|$ および $\|XY\| \leq \|X\| \|Y\|$ が成り立つ。 以下の設問に答えよ。

(1) $X \in \mathbb{C}^{n \times n}$ に対し、次の不等式を示せ：

$$\|e^X\| \leq e^{\|X\|}, \quad \|e^X - I\| \leq \|X\| e^{\|X\|}, \quad \|e^X - I - X\| \leq \|X\|^2 e^{\|X\|}$$

---

以下では、$A, B \in \mathbb{C}^{n \times n}$、$m$ を $1$ 以上の整数とし、$P := e^{(A+B)/m}, Q := e^{A/m} e^{B/m}$ とおく。

(2) 以下の不等式を示せ：

$$\|P^m - Q^m\| \leq m \|P - Q\| e^{\frac{m-1}{m} (\|A\| + \|B\|)}$$

ここで、等式 $P^m - Q^m = \sum_{i=0}^{m-1} P^i (P - Q) Q^{m-1-i}$ は証明せずに用いてよい。

(3) 以下の等式を示せ：

$$P - Q = g\left(\frac{A + B}{m}\right) - g\left(\frac{A}{m}\right) - g\left(\frac{B}{m}\right) - f\left(\frac{A}{m}\right) f\left(\frac{B}{m}\right)$$

ここで、$X \in \mathbb{C}^{n \times n}$ に対し、$f(X) := e^X - I, g(X) := e^X - I - X$ とする。

(4) 次の不等式を示せ：

$$\|P^m - Q^m\| \leq \frac{2}{m} (\|A\| + \|B\|)^2 e^{\|A\| + \|B\|}$$

(5) $n$ 次元複素ベクトル値関数 $x(t)$ に対する常微分方程式の初期値問題

$$\frac{d}{dt} x(t) = (A + B) x(t), \quad x(0) = v$$

を考える。$n$ 次元複素ベクトルの列 $\tilde{x}^0, \tilde{x}^1, \ldots, \tilde{x}^{2m}$ を、$\tilde{x}^0 = v$ かつ

$$\tilde{x}^{k+1} = \begin{cases} e^{B/m} \tilde{x}^k & (k \text{が偶数}), \\ e^{A/m} \tilde{x}^k & (k \text{が奇数}), \end{cases} \quad (k = 0, 1, \ldots, 2m-1)$$

で定める。このとき、$0 < \alpha < 1$ を満たす任意の実数 $\alpha$ に対し、以下が成り立つことを示せ：

$$\lim_{m \to \infty} m^\alpha \|x(1) - \tilde{x}^{2m}\| = 0.$$

Kai

(1)

$$\begin{aligned} \|e^X\| & =\left\lVert \sum_{k=0}^\infty \frac{1}{k!}X^k\right\rVert \\ & \leq \sum_{k=0}^\infty \frac{1}{k!}\left\lVert X^k\right\rVert \\ & \leq \sum_{k=0}^\infty \frac{1}{k!}\left\lVert X\right\rVert^k \\ & =e^{\|X\|} \\ \|e^X-I\| & =\left\lVert X^0+ \sum_{k=1}^\infty \frac{1}{k!}X^k -I\right\rVert \\ & =\left\lVert \sum_{k=1}^\infty \frac{1}{k!}X^k\right\rVert \\ & =\left\lVert X\sum_{k=0}^\infty \frac{1}{(k+1)!}X^k\right\rVert \\ & \leq \|X\|\left( \sum_{k=0}^{\infty} \frac{1}{(k+1)!} \|X\|^k \right) \\ & \leq \|X\|\left( \sum_{k=0}^{\infty} \frac{1}{k!} \|X\|^k \right) \\ & =\|X\|e^{\|X\|} \\ \|e^X-I-X\| & =\left\lVert X^0+X^1 +\sum_{k=2}^\infty \frac{1}{k!}X^k -I - X\right\rVert \\ & =\left\lVert \sum_{k=2}^\infty \frac{1}{k!}X^k\right\rVert \\ & =\left\lVert X^2 \sum_{k=0}^\infty \frac{1}{(k+2)!}X^k\right\rVert \\ & \leq \|X\|^2\left( \sum_{k=0}^{\infty} \frac{1}{(k+2)!} \|X\|^k \right) \\ & \leq \|X\|^2\left( \sum_{k=0}^{\infty} \frac{1}{k!} \|X\|^k \right) \\ & =\|X\|e^{\|X\|} \\ \end{aligned}$$

(2)

まず、一般の $0\leq i < m$ に対し、以下が成立する。

$$\begin{aligned} \left\lVert P^iQ^{m-1-i}\right\rVert & = \left\lVert e^{\frac{i(A+B)}{m}}e^{\frac{(m-1-i)A}{m}}e^{\frac{(m-1-i)B}{m}} \right\rVert \\ & \leq e^{\left\lVert\frac{i(A+B)}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)A}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)B}{m}\right\rVert} \\ & \leq e^{\left\lVert\frac{iA}{m}\right\rVert+\left\lVert\frac{iB}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)A}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)B}{m}\right\rVert} \\ & = e^{\left\lVert\frac{iA}{m}\right\rVert}e^{\left\lVert\frac{iB}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)A}{m}\right\rVert}e^{\left\lVert\frac{(m-1-i)B}{m}\right\rVert} \\ & = e^{\left\lVert\frac{iA}{m}\right\rVert+\left\lVert\frac{(m-1-i)A}{m}\right\rVert}e^{\left\lVert\frac{iB}{m}\right\rVert+\left\lVert\frac{(m-1-i)B}{m}\right\rVert} \\ & \leq e^{\frac{m-1}{m}\|A\|}e^{\frac{m-1}{m}\|B\|} \\ & = e^{\frac{m-1}{m}(\|A\|+\|B\|)} \\ \end{aligned}$$

ただし、途中で $e$ の単調性つまり、$x \leq y\Rightarrow e^x \leq e^y$ を用いた。

なお、$P \neq Q$ という事には十分に注意する必要がある。安易な指数法則は適用出来ない。

以上より、

$$\begin{aligned} \|P^m-Q^m\| & =\left\lVert \sum_{i=0}^{m-1}P^i(P-Q)Q^{m-1-i}\right\rVert \\ & \leq \|P-Q\|\left\lVert \sum_{i=0}^{m-1}P^iQ^{m-1-i}\right\rVert \\ & \leq \|P-Q\|m e^{\frac{m-1}{m}(\|A\|+\|B\|)} \end{aligned}$$

となる。

(3)

$f(X):=e^X-I,g(X):=e^X-I-X$ である。よって、

$$\begin{aligned} & g\left(\frac{A+B}{m}\right)-g\left(\frac{A}{m}\right)-g\left(\frac{B}{m}\right)-f\left(\frac{A}{m}\right)f\left(\frac{B}{m}\right) \\ = & \left(e^{\frac{A+B}{m}}-I-\frac{A+B}{m}\right)-\left(e^{\frac{A}{m}}-I-\frac{A}{m}\right)-\left(e^{\frac{B}{m}}-I-\frac{B}{m}\right)-\left(e^{\frac{A}{m}}-I\right)\left(e^{\frac{B}{m}}-I\right) \\ = & \left(e^{\frac{A+B}{m}}-\frac{A+B}{m}\right)-\left(e^{\frac{A}{m}}-\frac{A}{m}\right)-\left(e^{\frac{B}{m}}-\frac{B}{m}\right)-\left(e^{\frac{A}{m}}e^{\frac{B}{m}}-e^{\frac{A}{m}}-e^{\frac{B}{m}}\right) \\ = & e^{\frac{A+B}{m}}-e^{\frac{A}{m}}e^{\frac{B}{m}} \\ = & P-Q \end{aligned}$$

となる。

(4)

一部緩めの不等式評価になっていることに注意する必要があるが、以下のような式が成立する。

$$\begin{aligned} \|P-Q\| & = \left\lVert g\left(\frac{A+B}{m}\right)-g\left(\frac{A}{m}\right)-g\left(\frac{B}{m}\right)-f\left(\frac{A}{m}\right)f\left(\frac{B}{m}\right) \right\rVert \\ & \leq \left\lVert g\left(\frac{A+B}{m}\right)\right\rVert+\left\lVert g\left(\frac{A}{m}\right)\right\rVert+\left\lVert g\left(\frac{B}{m}\right)\right\rVert+\left\lVert f\left(\frac{A}{m}\right)f\left(\frac{B}{m}\right) \right\rVert \\ & \leq \left\lVert \frac{A+B}{m}\right\rVert^2 e^{\frac{\|A+B\|}{m}}+\left\lVert \frac{A}{m}\right\rVert^2 e^{\frac{\|A\|}{m}}+\left\lVert \frac{B}{m}\right\rVert^2 e^{\frac{\|B\|}{m}}+\left\lVert \frac{A}{m}\right\rVert\left\lVert \frac{B}{m} \right\rVert e^{\frac{\|A\|}{m}+\frac{\|B\|}{m}} \\ & = \frac{1}{m^2} \left(\|A+B\|^2 e^{\frac{\|A+B\|}{m}}+ \|A\|^2 e^{\frac{\|A\|}{m}}+ \|B\|^2 e^{\frac{\|B\|}{m}}+ \|A\| \|B\| e^{\frac{\|A\|}{m}+\frac{\|B\|}{m}}\right) \\ & \leq \frac{1}{m^2} \left(\|A+B\|^2 e^{\frac{\|A\|+\|B\|}{m}}+ \|A\|^2 e^{\frac{\|A\|+\|B\|}{m}}+ \|B\|^2 e^{\frac{\|A\|+\|B\|}{m}}+ \|A\| \|B\| e^{\frac{\|A\|+\|B\|}{m}}\right) \\ & = \frac{1}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(\|A+B\|^2 + \|A\|^2 + \|B\|^2 + \|A\| \|B\| \right) \\ & \leq \frac{1}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(\|A\|^2+2\|A\|\|B\|+\|B\|^2 + \|A\|^2 + \|B\|^2 + \|A\|\|B\| \right) \\ & = \frac{1}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(2\|A\|^2+3\|A\|\|B\|+2\|B\|^2 \right) \\ & \leq \frac{1}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(2\|A\|^2+4\|A\|\|B\|+2\|B\|^2 \right) \\ & = \frac{2}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(\|A\|+\|B\|\right)^2 \\ \end{aligned}$$

よって、

$$\begin{aligned} \|P^m-Q^m\| & \leq \|P-Q\|m e^{\frac{m-1}{m}(\|A\|+\|B\|)} \\ & \leq \frac{2}{m^2}e^{\frac{\|A\|+\|B\|}{m}} \left(\|A\|+\|B\|\right)^2 m e^{\frac{m-1}{m}(\|A\|+\|B\|)} \\ & = \frac{2}{m} \left(\|A\|+\|B\|\right)^2 e^{\|A\|+\|B\|} \\ \end{aligned}$$

が示される。

(5)

常微分方程式を解いて、

$$\begin{aligned} x(t)=ve^{(A+B)t} \end{aligned}$$

を得る。特に、

$$\begin{aligned} x(1)=ve^{A+B}=v P^m \end{aligned}$$

である。

一方、

$$\begin{aligned} \tilde{x}^{2m}=v\left(e^{\frac{A}{m}}e^{\frac{B}{m}}\right)^m=vQ^m \end{aligned}$$

である。

よって、

$$\begin{aligned} \|x(1)-\tilde{x}^{2m}\| & =\|vP^m-vQ^m\| \\ & \leq \|v\|\|P^m-Q^m\| \\ & \leq \|v\|\frac{2}{m} \left(\|A\|+\|B\|\right)^2 e^{\|A\|+\|B\|} \\ & =\frac{C}{m} \end{aligned}$$

となる。ただし、$C$ は $m$ に依存しない定数である。

よって、

$$\begin{aligned} \lim_{m \to \infty} m^\alpha \|x(1)-\tilde{x}^{2m}\| & \leq \lim_{m \to \infty} {m^\alpha \frac{C}{m}} \\ & =\lim_{m \to \infty} \frac{C}{m^{1-\alpha}} \\ & =0 \end{aligned}$$

となるので、

$$\begin{aligned} \lim_{m \to \infty} m^\alpha \|x(1)-\tilde{x}^{2m}\|=0 \end{aligned}$$

が示される。

Knowledge

連立１階線形常微分方程式の解は、行列の指数関数を用いて表す事が出来る。