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

标签：

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

Author

hari64boli64, 祭音Myyura

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.$$

题目描述

对复方阵 $X\in\mathbb C^{n\times n}$，定义

$$e^X=\sum_{k=0}^\infty\frac{X^k}{k!},\qquad X^0=I.$$

向量采用 Euclidean 范数，矩阵采用其诱导算子范数

$$\|X\|=\sup_{\|x\|=1}\|Xx\|,$$

可使用三角不等式及次乘性 $\|XY\|\le\|X\|\|Y\|$。

1. 证明

   $$\|e^X\|\le e^{\|X\|},\qquad \|e^X-I\|\le\|X\|e^{\|X\|},$$
   $$\|e^X-I-X\|\le\|X\|^2e^{\|X\|}.$$

2. 令 $A,B\in\mathbb C^{n\times n}$、$m\ge1$，并设

   $$P=e^{(A+B)/m},\qquad Q=e^{A/m}e^{B/m}.$$

   利用

   $$P^m-Q^m=\sum_{i=0}^{m-1}P^i(P-Q)Q^{m-1-i}$$

   证明

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

3. 定义 $f(X)=e^X-I$、$g(X)=e^X-I-X$，证明

   $$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).$$

4. 进一步证明误差估计

   $$\|P^m-Q^m\| \le\frac2m(\|A\|+\|B\|)^2e^{\|A\|+\|B\|}.$$

5. 对初值问题

   $$\dot x(t)=(A+B)x(t),\qquad x(0)=v,$$

   定义算子分裂序列 $\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,\ldots,2m-1).$$

   对任意 $0<\alpha<1$，证明

   $$\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\|^2e^{\|X\|} \\ \end{aligned}$$

(2)

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

$$\begin{aligned} \|P\|&\leq e^{(\|A\|+\|B\|)/m},\\ \|Q\|&\leq\|e^{A/m}\|\,\|e^{B/m}\| \leq e^{(\|A\|+\|B\|)/m},\\ \|P^iQ^{m-1-i}\| &\leq\|P\|^i\|Q\|^{m-1-i} \leq e^{\frac{m-1}{m}(\|A\|+\|B\|)}. \end{aligned}$$

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

一般には $P=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 \sum_{i=0}^{m-1}\|P^i\|\,\|P-Q\|\,\|Q^{m-1-i}\| \\ & \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)=e^{(A+B)t}v \end{aligned}$$

を得る。特に、

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

である。

一方、

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

である。

よって、

$$\begin{aligned} \|x(1)-\tilde{x}^{2m}\| & =\|(P^m-Q^m)v\| \\ & \leq \|P^m-Q^m\|\,\|v\| \\ & \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

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