6.6_课后习题

6.6 课后习题

练习6.1 已知 A=[a131a2−32a]∈R3×3A = \left[ \begin{array}{rrr}a & 1 & 3\\ 1 & a & 2\\ -3 & 2 & a \end{array} \right]\in \mathbb{R}^{3\times 3} ，且Jacobi方法收敛,求 aa 的取值范围

练习6.2 写出求解线性方程组 Ax=bAx = b 的Jacobi, GS和SOR的分量形式，并讨论它们的收敛性，其

中 A=[5−32−36−12−13],b=[321].A = \left[ \begin{array}{rrr}5 & -3 & 2\\ -3 & 6 & -1\\ 2 & -1 & 3 \end{array} \right],b = \left[ \begin{array}{l}3\\ 2\\ 1 \end{array} \right].

练习6.3 若存在非奇异矩阵 WW , 使得 W(I−G)W−1W(I - G)W^{-1} 是对称正定矩阵, 则称迭代法

x(k+1)=Gx(k)+g,k=0,1,2,…x ^ {(k + 1)} = G x ^ {(k)} + g, \quad k = 0, 1, 2, \dots

是可对称化的. 现假定上述迭代法是可对称化的, 试证

(1) GG 的特征值全部为实数, 且都小于 1;
(2) 存在 γ\gamma , 使得下面的外推迭代法收敛

x(k+1)=(1−γ)x(k)+γ(Gx(k)+g),k=0,1,2,… .x ^ {(k + 1)} = (1 - \gamma) x ^ {(k)} + \gamma (G x ^ {(k)} + g), \quad k = 0, 1, 2, \dots .

练习6.4 设 A=[2031]A = \begin{bmatrix} 2 & 0 \\ 3 & 1 \end{bmatrix} , 构造迭代法

x(k+1)=x(k)+α(b−Ax(k)),k=0,1,2,… .x ^ {(k + 1)} = x ^ {(k)} + \alpha (b - A x ^ {(k)}), \quad k = 0, 1, 2, \dots .

问: 当 α∈R\alpha \in \mathbb{R} 取何值时, 该迭代法收敛, 什么时候收敛最快?

练习6.5 设 A∈Rn×nA \in \mathbb{R}^{n \times n} . 证明: ρ(A)<1\rho(A) < 1 的充要条件是 I−AI - A 非奇异, 且 (I−A)−1(I+A)(I - A)^{-1}(I + A) 的特征值具有正实部.

练习6.6 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 是对称三对角矩阵

A=[abb⋱⋱⋱⋱bba].A = \left[ \begin{array}{c c c c} a & b & & \\ b & \ddots & \ddots & \\ & \ddots & \ddots & b \\ & & b & a \end{array} \right].

计算矩阵 AA 的特征值和特征向量

练习6.7 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 对称正定, B∈Rn×kB \in \mathbb{R}^{n \times k} 列满秩, 试证明 BTABB^{\mathrm{T}}AB 对称正定.

练习 6.8∗6.8^{*} 设 A=D−E−E∗∈Cn×nA = D - E - E^{*} \in \mathbb{C}^{n \times n} , 其中 DD 是Hermite正定的. 令

Gω=(D−ωE)−1[(1−ω)D+ωE∗],G _ {\omega} = (D - \omega E) ^ {- 1} [ (1 - \omega) D + \omega E ^ {*} ],

其中 ω\omega 是实数. 证明 ρ(Gω)<1\rho(G_{\omega}) < 1 当且仅当

(1) AA 是正定的, 且 0<ω<20 < \omega < 2 , 或者
(2) AA 是负定的, 且 ω∉[0,2]\omega \notin [0,2] .

(提示: 利用和仿照引理 6.13 中的证明思路)

练习6.9 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 严格对角占优, 证明 ρ(GGS)<1\rho(G_{\mathrm{GS}}) < 1

(注: 不能直接使用定理 6.7 以及其证明过程)

练习6.10 设迭代格式 x(k+1)=Gx(k)+g,x^{(k + 1)} = Gx^{(k)} + g, 其中 GG 对称且 λ(G)∈[α,β],−1<α≤β<1.\lambda (G)\in [\alpha ,\beta ], - 1 < \alpha \leq \beta < 1. 试构造出相应的Chebyshev加速方法.

练习6.11 (定理6.36) 设 λmax⁡≥λmin⁡>0\lambda_{\max} \geq \lambda_{\min} > 0 ，则最小最大问题

min⁡α>0max⁡λmin⁡≤λ≤λmax⁡∣α−λα+λ∣\min _ {\alpha > 0} \max _ {\lambda_ {\min } \leq \lambda \leq \lambda_ {\max }} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right|

的解为

α∗=λmin⁡λmax⁡.\alpha_ {*} = \sqrt {\lambda_ {\min} \lambda_ {\max}}.

练习 6.12∗6.12^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 是对称正定的. 证明: 对任意正实数 α\alpha , 都有

ρ((αI+A)−1(αI−A))<1.\rho \big ((\alpha I + A) ^ {- 1} (\alpha I - A) \big) < 1.

如果 AA 只是正定呢？

练习 6.13∗6.13^{*} (定理 6.8) 设 A∈Rn×nA \in \mathbb{R}^{n \times n} , 若 AA 是不可约对角占优, 证明: Jacobi 迭代法和 G-S 迭代法都收敛.

练习 6.14∗6.14^{*} 证明: 对任意矩阵 A∈Cn×nA \in \mathbb{C}^{n \times n} 和任意正数 ε>0\varepsilon > 0 , 存在非奇异矩阵 LL , 使得

∥A∥L≤ρ(A)+ε,\| A \| _ {L} \leq \rho (A) + \varepsilon ,

其中 ∥A∥L≜∥LAL−1∥2\| A\| _L\triangleq \| LAL^{-1}\| _2

练习 6.15∗6.15^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} . 证明: ρ(A)<1\rho(A) < 1 的充要条件是存在对称正定矩阵 P∈Rn×nP \in \mathbb{R}^{n \times n} 使得 P−APATP - APA^{\mathsf{T}} 正定.

以下为可选题

练习6.16 证明Richardson迭代法的收敛性, 即定理6.11.

练习 6.17∗6.17^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} , 如果矩阵分裂 A=M−NA = M - N 满足 M−1≥0,N≥0M^{-1} \geq 0, N \geq 0 , 则称这个分裂为正则分裂. 假定 A−1≥0A^{-1} \geq 0 , 且 A=M−NA = M - N 是正则分裂, 试证明

ρ(M−1N)=ρ(A−1N)1+ρ(A−1N)<1.\rho (M ^ {- 1} N) = \frac {\rho (A ^ {- 1} N)}{1 + \rho (A ^ {- 1} N)} < 1.

练习 6.18∗6.18^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 严格对角占优且非负, 则结论 ρ(GGS)≤ρ(GJ)\rho(G_{\mathrm{GS}}) \leq \rho(G_{\mathrm{J}}) 是否成立? 若成立则给出证明, 若不成立则给出反例.

练习6.19 初值的选取对迭代法的收敛速度也有着很大的影响，请以Jacobi迭代法为例，初值取什么时收敛最快（真解除外）？什么初值收敛最慢？

练习 6.20∗6.20^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 对称正定, B∈Rn×mB \in \mathbb{R}^{n \times m} 满秩, 其中 n≥mn \geq m . 记 AA 的最大和最小特征值分别为 μ1\mu_{1} 和 μn\mu_{n} , 记 BB 的最大和最小奇异值分别为 σ1\sigma_{1} 和 σm\sigma_{m} . 证明: A=[ABB⊤0]\mathcal{A} = \left[ \begin{array}{cc} A & B \\ B^{\top} & 0 \end{array} \right] 的特征值满足

λ(A)∈I−∪I+,\lambda (\mathcal {A}) \in I ^ {-} \cup I ^ {+},

其中

I−=[12(μn−μn2+4σ12),12(μ1−μ12+4σm2)],I+=[μn,12(μ1+μ12+4σ12)].\begin{array}{l} I ^ {-} = \left[ \frac {1}{2} \left(\mu_ {n} - \sqrt {\mu_ {n} ^ {2} + 4 \sigma_ {1} ^ {2}}\right), \frac {1}{2} \left(\mu_ {1} - \sqrt {\mu_ {1} ^ {2} + 4 \sigma_ {m} ^ {2}}\right) \right], \\ I ^ {+} = \left[ \mu_ {n}, \frac {1}{2} \left(\mu_ {1} + \sqrt {\mu_ {1} ^ {2} + 4 \sigma_ {1} ^ {2}}\right) \right]. \\ \end{array}

练习 6.21∗6.21^{*} 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 对称正定, B∈Rn×mB \in \mathbb{R}^{n \times m} 满秩, C∈Rm×mC \in \mathbb{R}^{m \times m} 对称半正定, 其中 n≥mn \geq m , 记 AA 的最大和最小特征值分别为 μ1\mu_{1} 和 μn\mu_{n} , CC 的最大特征值为 ν1\nu_{1} , BB 的最大和最小奇异值分别为 σ1\sigma_{1} 和 σm\sigma_{m} . 证明: A=[ABB⊤C]\mathcal{A} = \left[ \begin{array}{cc} A & B \\ B^{\top} & C \end{array} \right] 的特征值满足

λ(A)∈I−∪I+,\lambda (\mathcal {A}) \in I ^ {-} \cup I ^ {+},

其中

I−=[12(μn−ν1−(μn+ν1)2+4σ12),12(μ1−μ12+4σm2)],I+=[μn,12(μ1+μ12+4σ12)].\begin{array}{l} I ^ {-} = \left[ \frac {1}{2} \left(\mu_ {n} - \nu_ {1} - \sqrt {\left(\mu_ {n} + \nu_ {1}\right) ^ {2} + 4 \sigma_ {1} ^ {2}}\right), \frac {1}{2} \left(\mu_ {1} - \sqrt {\mu_ {1} ^ {2} + 4 \sigma_ {m} ^ {2}}\right) \right], \\ I ^ {+} = \left[ \mu_ {n}, \frac {1}{2} \left(\mu_ {1} + \sqrt {\mu_ {1} ^ {2} + 4 \sigma_ {1} ^ {2}}\right) \right]. \\ \end{array}

练习 6.22∗6.22^{*} 设 A∈Rn×nA\in \mathbb{R}^{n\times n} 对称正定, B∈Rn×mB\in \mathbb{R}^{n\times m} 满秩,其中 n≥mn\geq m .记 AA 的最小特征值为 μn\mu_{n} .证明：

如果 μn≥4∥S∥2\mu_n \geq 4\|S\|_2 ，其中 S=BTA−1BS = B^{\mathsf{T}}A^{-1}B ，则 A~=[AB−BT0]\tilde{A} = \begin{bmatrix} A & B \\ -B^{\mathsf{T}} & 0 \end{bmatrix} 的特征值都是正实数。

练习 6.23∗6.23^{*} 试举例说明, 存在线性方程组 Ax=bAx = b , 使得 Jacobi 迭代法收敛, 但 G-S 方法不收敛.

以下为实践题

练习6.24 写出 Poisson 方程红黑排序的 SOR 和 SSOR 方法的迭代格式, 并编程实现. (以例 6.2 中的 Poisson 方程为例)

前の章6.5_交替方向法与HSS迭代法
次の章README