京都大学 情報学研究科 システム科学専攻 2022年8月実施 数学【I】 Author 机智的若叶 , 祭音Myyura
Description ベクトル x x x m m m A x = b A x = b A x = b m m m A A A P − Q P - Q P − Q P x = Q x + b P x = Q x + b P x = Q x + b x 0 x_0 x 0 x n + 1 = Q x n + b x_{n+1} = Q x_n + b x n + 1 = Q x n + b x n + 1 = P − 1 ( Q x n + b ) x_{n+1} = P^{-1} (Q x_n + b) x n + 1 = P − 1 ( Q x n + b ) A A A P P P
ただし、m m m Z Z Z Z − 1 Z^{-1} Z − 1 Z T Z^T Z T ρ ( Z ) \rho (Z) ρ ( Z ) ρ ( Z ) \rho (Z) ρ ( Z ) Z Z Z λ i \lambda_i λ i ( i = 1 , … , m ) (i = 1, \ldots, m) ( i = 1 , … , m ) max i ∣ λ i ∣ \max_i |\lambda_i| max i ∣ λ i ∣
(i) P − 1 P^{-1} P − 1 P x = Q x + b P x = Q x + b P x = Q x + b x n + 1 = Q x n + b x_{n+1} = Q x_n + b x n + 1 = Q x n + b
x − x n + 1 = P − 1 Q ( x − x n ) x - x_{n+1} = P^{-1} Q (x - x_n) x − x n + 1 = P − 1 Q ( x − x n ) となる。
P − 1 Q P^{-1} Q P − 1 Q n → ∞ n \to \infty n → ∞ x 0 x_0 x 0 x n x_n x n ρ ( P − 1 Q ) \rho (P^{-1} Q) ρ ( P − 1 Q )
以下の設問では、次の方程式をヤコビ法を用いて解く場合について考える。
A x = b , A = [ 12 − 4 3 − 3 4 0 3 − 2 4 ] , b = [ 5 1 − 3 ] (1) A x = b, \quad A = \begin{bmatrix} 12 & -4 & 3 \\ -3 & 4 & 0 \\ 3 & -2 & 4 \end{bmatrix}, \quad b = \begin{bmatrix} 5 \\ 1 \\ -3 \end{bmatrix} \tag{1} A x = b , A = 12 − 3 3 − 4 4 − 2 3 0 4 , b = 5 1 − 3 ( 1 ) (ii) P P P Q Q Q P − 1 P^{-1} P − 1
(iii) P − 1 Q P^{-1} Q P − 1 Q P − 1 Q P^{-1} Q P − 1 Q
(iv) x 0 = [ 0 0 0 ] x_0 = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} x 0 = 0 0 0 x 1 x_1 x 1
(v) A − 1 A^{-1} A − 1
行列 A A A n × n n \times n n × n a i j ( i , j = 1 , … , n ) a_{ij} (i, j = 1, \ldots, n) a ij ( i , j = 1 , … , n )
∑ j = 1 n a i j = 1 , i = 1 , … , n \sum_{j=1}^n a_{ij} = 1, \quad i = 1, \ldots, n j = 1 ∑ n a ij = 1 , i = 1 , … , n を満たすと仮定する。以下の設問に答えよ。ただし、u u u n n n
(i) A u = u A u = u A u = u
(ii) 任意の零ベクトルでない n n n x x x x x x x m x_m x m i ∈ { 1 , … , n } i \in \{1, \ldots, n\} i ∈ { 1 , … , n }
∣ ∑ j = 1 n a i j x j ∣ ≤ ∣ x m ∣ \left| \sum_{j=1}^n a_{ij} x_j \right| \leq |x_m| j = 1 ∑ n a ij x j ≤ ∣ x m ∣ が成り立つことを示せ。
(iii) A A A λ \lambda λ ∣ λ ∣ ≤ 1 |\lambda| \leq 1 ∣ λ ∣ ≤ 1
(iv) n = 2 n = 2 n = 2 A A A
A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1 A = \begin{bmatrix}
1 - \alpha & \alpha \\
\alpha & 1 - \alpha
\end{bmatrix}, \quad 0 < \alpha \leq 1 A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1 を取るとする。
設問 (i) から、A A A λ 1 = 1 \lambda_1 = 1 λ 1 = 1 u = u / 2 u = u / \sqrt{2} u = u / 2 λ 2 \lambda_2 λ 2 w w w w w w
(v) 設問 (iv) の A A A A k A^k A k
B = lim k → ∞ A k B = \lim_{k \to \infty} A^k B = k → ∞ lim A k が存在する α \alpha α B B B
题目描述
考虑用迭代法求解关于向量 x x x m m m A x = b Ax=b A x = b m m m A = P − Q A=P-Q A = P − Q
给定适当初值 x 0 x_0 x 0 x n + 1 = Q x n + b x_{n+1}=Qx_n+b x n + 1 = Q x n + b
x n + 1 = P − 1 ( Q x n + b ) . x_{n+1}=P^{-1}(Qx_n+b). x n + 1 = P − 1 ( Q x n + b ) . 特别地，取 P P P A A A Z − 1 Z^{-1} Z − 1 Z T Z^{\mathrm T} Z T ρ ( Z ) \rho(Z) ρ ( Z ) m m m Z Z Z ρ ( Z ) \rho(Z) ρ ( Z ) Z Z Z
（i）当 P − 1 P^{-1} P − 1
P x = Q x + b , x n + 1 = P − 1 ( Q x n + b ) Px=Qx+b,\qquad
x_{n+1}=P^{-1}(Qx_n+b) P x = Q x + b , x n + 1 = P − 1 ( Q x n + b ) 可得
x − x n + 1 = P − 1 Q ( x − x n ) . x-x_{n+1}=P^{-1}Q(x-x_n). x − x n + 1 = P − 1 Q ( x − x n ) . 假设 P − 1 Q P^{-1}Q P − 1 Q ρ ( P − 1 Q ) \rho(P^{-1}Q) ρ ( P − 1 Q ) n → ∞ n\to\infty n → ∞ x n x_n x n x 0 x_0 x 0
以下使用 Jacobi 法求解
A x = b , A = [ 12 − 4 3 − 3 4 0 3 − 2 4 ] , b = [ 5 1 − 3 ] . (1) Ax=b,\qquad
A=
\begin{bmatrix}
12&-4&3\\
-3&4&0\\
3&-2&4
\end{bmatrix},
\qquad
b=
\begin{bmatrix}
5\\1\\-3
\end{bmatrix}.
\tag{1} A x = b , A = 12 − 3 3 − 4 4 − 2 3 0 4 , b = 5 1 − 3 . ( 1 ) （ii）求 P , Q , P − 1 P,Q,P^{-1} P , Q , P − 1
（iii）求 P − 1 Q P^{-1}Q P − 1 Q
（iv）取
x 0 = [ 0 0 0 ] , x_0=
\begin{bmatrix}0\\0\\0\end{bmatrix}, x 0 = 0 0 0 , 求 x 1 x_1 x 1
（v）先求 A − 1 A^{-1} A − 1
设 A A A n × n n\times n n × n a i j a_{ij} a ij
∑ j = 1 n a i j = 1 , i = 1 , … , n . \sum_{j=1}^na_{ij}=1,\qquad i=1,\ldots,n. j = 1 ∑ n a ij = 1 , i = 1 , … , n . 令 u u u n n n
（i）证明 A u = u Au=u A u = u
（ii）对任意非零实向量 x x x x m x_m x m i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n }
∣ ∑ j = 1 n a i j x j ∣ ≤ ∣ x m ∣ . \left|\sum_{j=1}^na_{ij}x_j\right|
\leq|x_m|. j = 1 ∑ n a ij x j ≤ ∣ x m ∣. （iii）证明 A A A λ \lambda λ ∣ λ ∣ ≤ 1 |\lambda|\leq1 ∣ λ ∣ ≤ 1
（iv）令 n = 2 n=2 n = 2
A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1. A=
\begin{bmatrix}
1-\alpha&\alpha\\
\alpha&1-\alpha
\end{bmatrix},
\qquad0<\alpha\leq1. A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1. 由第（i）问可知 A A A λ 1 = 1 \lambda_1=1 λ 1 = 1 u / 2 u/\sqrt2 u / 2 λ 2 \lambda_2 λ 2 w w w
（v）对第（iv）问的矩阵 A A A A k A^k A k
B = lim k → ∞ A k B=\lim_{k\to\infty}A^k B = k → ∞ lim A k 存在的 α \alpha α B B B
Jacobi 迭代法 ：从矩阵分裂构造迭代矩阵并执行首步迭代。谱半径与迭代收敛 ：利用误差递推和特征分解给出任意初值收敛的充要条件。随机矩阵的谱性质 ：由非负行和为 1 证明单位特征值及其他特征值的模界。二阶对称矩阵幂极限 ：通过正交谱分解判断幂序列是否收敛并计算极限投影。
Kai (i)
ρ ( P − 1 Q ) ≤ 1 \rho(P^{-1}Q) \le 1 ρ ( P − 1 Q ) ≤ 1 (ii)
P = [ 12 0 0 0 4 0 0 0 4 ] Q = P − A = [ 0 4 − 3 3 0 0 − 3 2 0 ] P − 1 = [ 1 12 0 0 0 1 4 0 0 0 1 4 ] \begin{aligned}
P &= \begin{bmatrix} 12 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 4 \end{bmatrix} \\
Q &= P - A = \begin{bmatrix} 0 & 4 & -3 \\ 3 & 0 & 0 \\ -3 & 2 & 0 \end{bmatrix} \\
P^{-1} &= \begin{bmatrix} \frac{1}{12} & 0 & 0 \\ 0 & \frac{1}{4} & 0 \\ 0 & 0 & \frac{1}{4} \end{bmatrix} \\
\end{aligned} P Q P − 1 = 12 0 0 0 4 0 0 0 4 = P − A = 0 3 − 3 4 0 2 − 3 0 0 = 12 1 0 0 0 4 1 0 0 0 4 1 (iii)
P − 1 Q P^{-1}Q P − 1 Q λ \lambda λ
0 = det ( t I − P − 1 Q ) = λ 3 − 7 16 λ + 3 32 = 1 32 ( 2 λ − 1 ) ( 4 λ − 1 ) ( 4 λ + 3 ) ∴ λ = 1 2 , 1 4 , − 3 4 \begin{aligned}
0 &= \text{det}(tI - P^{-1}Q) \\
&= \lambda^{3} - \frac{7}{16} \lambda + \frac{3}{32} \\
&= \frac{1}{32} (2 \lambda - 1) (4 \lambda - 1) (4 \lambda + 3) \\
\therefore \ \
\lambda &= \frac{1}{2}, \frac{1}{4}, -\frac{3}{4}
\end{aligned} 0 ∴ λ = det ( t I − P − 1 Q ) = λ 3 − 16 7 λ + 32 3 = 32 1 ( 2 λ − 1 ) ( 4 λ − 1 ) ( 4 λ + 3 ) = 2 1 , 4 1 , − 4 3 である。よって、
ρ ( P − 1 Q ) = 3 4 \rho(P^{-1}Q) = \frac{3}{4} ρ ( P − 1 Q ) = 4 3 (iv)
x 1 = P − 1 b = [ 5 12 1 4 − 3 4 ] \begin{aligned}
x_1 = P^{-1}b = \begin{bmatrix} \frac{5}{12} \\ \frac{1}{4} \\ -\frac{3}{4} \end{bmatrix}
\end{aligned} x 1 = P − 1 b = 12 5 4 1 − 4 3 (v)
x = [ 1 1 − 1 ] \begin{aligned}
x = \begin{bmatrix} 1 \\ 1 \\ -1 \end{bmatrix}
\end{aligned} x = 1 1 − 1 (i)
a i j a_{ij} a ij A A A i i i j j j
A u = [ ∑ j = 1 n a 1 j , ∑ j = 1 n a 2 j , … ∑ j = 1 n a n j ] T = u \begin{aligned}
Au = \big[\sum_{j=1}^n a_{1j}, \sum_{j=1}^n a_{2j}, \ldots \sum_{j=1}^n a_{nj} \big]^T = u
\end{aligned} A u = [ j = 1 ∑ n a 1 j , j = 1 ∑ n a 2 j , … j = 1 ∑ n a nj ] T = u である。
(ii)
すべての要素が非負であり、
∣ ∑ j = 1 n a i j x j ∣ ≤ ∑ j = 1 n a i j ∣ x j ∣ ≤ ∑ j = 1 n a i j ∣ x m ∣ = ∣ x m ∣ \begin{aligned}
|\sum_{j=1}^n a_{ij} x_j| \le \sum_{j=1}^n a_{ij}|x_j| \le \sum_{j=1}^n a_{ij} |x_m| = |x_m|
\end{aligned} ∣ j = 1 ∑ n a ij x j ∣ ≤ j = 1 ∑ n a ij ∣ x j ∣ ≤ j = 1 ∑ n a ij ∣ x m ∣ = ∣ x m ∣ (iii)
固有ベクトルを [ x 1 , x 2 , … , x n ] T [x_1, x_2, \ldots, x_n]^T [ x 1 , x 2 , … , x n ] T x j x_j x j
∣ ∑ j = 1 n a i j x j ∣ = ∣ λ x j ∣ \begin{aligned}
\lvert \sum_{j=1}^n a_{ij} x_j \rvert = |\lambda x_j|
\end{aligned} ∣ j = 1 ∑ n a ij x j ∣ = ∣ λ x j ∣ (ii) より、
∣ ∑ j = 1 n a i j x m ∣ = ∣ λ x m ∣ ≤ ∣ x m ∣ ∴ ∣ λ ∣ ≤ 1 \begin{aligned}
&|\sum_{j=1}^n a_{ij} x_m| = |\lambda x_m| \le |x_m| \\
&\therefore |\lambda| \le 1
\end{aligned} ∣ j = 1 ∑ n a ij x m ∣ = ∣ λ x m ∣ ≤ ∣ x m ∣ ∴ ∣ λ ∣ ≤ 1 (iv)
tr ( A ) = λ 1 + λ 2 = 2 − 2 α ∵ λ 1 = 1 ∴ λ 2 = 1 − 2 α \begin{aligned}
&\text{tr} (A) = \lambda_1 + \lambda_2 = 2 - 2\alpha \\
&\because \lambda_1 = 1\ \ \ \therefore \lambda_2 = 1-2\alpha
\end{aligned} tr ( A ) = λ 1 + λ 2 = 2 − 2 α ∵ λ 1 = 1 ∴ λ 2 = 1 − 2 α ( A − ( 1 − α ) I ) w = 0 ⇒ w = [ 1 2 , − 1 2 ] T \begin{aligned}
(A - (1 - \alpha)I) w = 0 \Rightarrow w = [\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}]^T
\end{aligned} ( A − ( 1 − α ) I ) w = 0 ⇒ w = [ 2 1 , − 2 1 ] T (v)
α ≠ − 1 \alpha \neq -1 α = − 1
P − 1 A P = Λ = [ 1 0 0 1 − 2 α ] \begin{aligned}
P^{-1}AP = \Lambda = \begin{bmatrix} 1 & 0 \\ 0 & 1-2 \alpha \end{bmatrix}
\end{aligned} P − 1 A P = Λ = [ 1 0 0 1 − 2 α ] P = [ v , w ] = [ 1 2 − 1 2 1 2 1 2 ] \begin{aligned}
P = [v,w] = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}
\end{aligned} P = [ v , w ] = [ 2 1 2 1 − 2 1 2 1 ] P − 1 = [ 1 2 1 2 = 1 2 1 2 ] \begin{aligned}
P^{-1} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ =\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}
\end{aligned} P − 1 = [ 2 1 = 2 1 2 1 2 1 ] B = [ 1 2 − 1 2 1 2 1 2 ] \begin{aligned}
B = \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix}
\end{aligned} B = [ 2 1 2 1 − 2 1 2 1 ]