习题 2
Problem 1
- 证明下列命题：
- $n$ 维向量 $x$ 的一切范数均等价。
- $n$ 阶矩阵 $A$ 的一切范数均等价。
- 单位矩阵和置换矩阵的 $2-$范数均为 $1$
- 矩阵的列范数 $\Vert A\Vert_{1}=\max_{1\le j\le n}\sum_{i=1}^n|a_{ij}|$
ans.
- 未证明，可以利用 Jordan 标准型切入。
- 单位矩阵 $E$，$E^TE=E$ 的特征根均为 $1$ 从而， $2-$范数也为 $1$ 。置换矩阵 $P$ 就是每行每列有且仅有一个 $1$ 的矩阵，$P^TP=E$ 从而 $2-$ 范数也为 $1$ 。（注记：正交矩阵的 $2-$范数均为 $1$）
- 证明：
从而 $\Vert A\Vert\le \max_{1\le j\le n}\sum_{j=1}^n|a_{ij}|$ 不妨设当 $j=k$ 时右边式子取到最大值，从而只需取 $x=(0,\\cdots,1,\cdots,0)$ ，第 $k$ 个位置为 $1$ ， 其余为 $0$ 。即可证明等号可以成立
Problem 2
- 证明 (1) $\Vert x\Vert_{2}\le\Vert x\Vert_1\le \sqrt{n}\Vert x\Vert_{2}$ (2) $\Vert x\Vert_{\infty}\le \Vert x\Vert_1\le n\Vert x\Vert_{\infty}$ (3) $\Vert x\Vert_{\infty}\le \Vert x\Vert_2\le\Vert x\Vert_{\infty}$
ans. 三个不等式其实都是 Cauchy 不等式的应用
- $\sum x_i^2\le (\sum|x_i|)^2\le n\sum x_i^2$
- $(\max |x_i|^2)^2\le (\sum |x_i|)^2\le n\max |x_i|^2$
- $\max |x_i|^2\le \sum x_i^2\le n\max |x_i|^2$
Problem 3
- 若 $\Vert B\Vert<1$ ，证明 $I-B$ 非奇异,且有 $\frac{1}{1+\Vert B\Vert}\le\Vert(I-B)^{-1}\Vert\le \frac{1}{1-\Vert B\Vert}$
ans. 反证 $I-B$ 奇异，则 $\exists \eta \ne 0,s.t. (I-B)\eta=0\implies B\eta =\eta$ ，从而 $\Vert B\Vert\ge 1$ 矛盾。
又 $(I-B)^{-1}(I-B)=I\implies (I-B)^{-1}=I+(I-B)^{-1}B$
两边取范数，且利用三角不等式得 $\Vert (I-B)^{-1}\Vert\le 1+\Vert(I-B)^{-1}B\Vert\le 1+\Vert (I-B)^{-1}\Vert\cdot\Vert B\Vert$
将 $\Vert (I-B)^{-1}\Vert$ 解得 $\Vert (I-B)^{-1}\Vert\le \frac{1}{1-\Vert B\Vert}$
同样利用另外一边的三角不等式有 $\Vert (I-B)^{-1}\Vert\ge 1-\Vert(I-B)^{-1}B\Vert\ge 1-\Vert (I-B)^{-1}\Vert\cdot\Vert B\Vert$
解得 $\Vert (I-B)^{-1}\Vert\ge \frac{1}{1+\Vert B\Vert}$
Problem 4
- 设 $A$ 为非奇异方阵，而 $B$ 为任一奇异方阵，证明 $\frac{1}{\Vert A-B\Vert}\le\Vert A^{-1}\Vert$
ans. 利用第三题的结论。
$ \Vert (I-A^{-1} B)^{-1} \Vert \ge 1 $
整理得：
$ 1\le \Vert (I-A^{-1}B)^{-1}\Vert\le\Vert A^{-1}\Vert\cdot \Vert A-B\Vert $
Problem 5
- 求下列方阵的行范数，列范数，以及条件数。
ans. 行范数 $\Vert A\Vert_{\infty}=20,\Vert B\Vert_{\infty}=4$
列范数 $\Vert A\Vert_1=20,\Vert B\Vert_1=4$
逆矩阵 $A^{-1}=\begin{pmatrix}62 &-36 &-19\\ -36 &21 &11\\ -19 &11 &6\end{pmatrix},B^{-1}=\frac{1}{8}\begin{pmatrix}-5 &-2 &1 \\ -2 &-4 &2\\ 1 &2 &3\\ \end{pmatrix}$
条件数 $\mathrm{cond}_{\infty}(A)=20\times 117=2340,\mathrm{cond}_{\infty}(B)=4\times 1=4$
$\mathrm{cond}_1(A)=20\times117=2340,\mathrm{cond}(B)=4\times 1=4 $
Problem 6
- 给定线性方程组 $\begin{pmatrix}10^{-2}&1\\
1 &1\end{pmatrix}\begin{pmatrix}x_1\\
x_2\end{pmatrix}=\begin{pmatrix}1\\2\end{pmatrix}$
- 用分数表示出此方程的准确解
- 用 Guass 消元法过程中采用两位有效数字舍入计算
- 按列主元消元法过程中采用两位有效数字舍入计算
ans.
- 作初等行变换化为： $\begin{pmatrix}10^{-2} &1 &1\\ 0 &-99 &-98\end{pmatrix}$，解得 $x_1=\frac{100}{99},x_2=\frac{98}{99}$
- 过程中仅取两位有效数字作变换： $\begin{pmatrix}0.01 &1 &1\\ 0 &-99 &-98\end{pmatrix}$ ，解得 $x_1=1.00,x_2=0.99$
- 全主元消元法 $\begin{pmatrix}1 &1 &2\\ 10^{-2} &1 &1\end{pmatrix}\rightarrow\begin{pmatrix}1 &1 &2\\ 0 &0.99 &0.98\end{pmatrix}\implies \begin{cases}x_1=1.01\\ x_2=0.99\end{cases}$
Problem 7
- 线性方程组 $\begin{pmatrix}10^{-5} &10^{-5} &1\\
10^{-5} &-10^{-5} &1\\
1 &1 &2\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}2\times 10^{-5}\-2\times10^{-5}\\1\end{pmatrix}$
- 用 Guass 消元法过程中保留三位有效数字计算
- 用全主元消元法
- 先做代换 $x_3’=10^5x_3$ 在用选主元消元法求解
ans.
Guass 消元法
解得 $x_1=0,x_2=2,x_3=0$
全主元消元法：
方程有无穷多解
- 先做替换再消元
解得 $x_1=0,x_2=2,x_3=-1$
Problem 8
- $A$ 为对称正定矩阵，经过一次 Guass 消元法化为 $\begin{pmatrix}a_{11} &\alpha^T\\
0 &A_2 \end{pmatrix}$ 证明：
- $a_{ii}>0$
- $|a_{ij}|\le\sqrt{a_{ii}a_{jj}}\le\frac{1}{2}(a_{ii}+a_{jj})$
- $A$ 的绝对值最大的元素一定在对角线上
- $A_2$ 为对称正定矩阵
- $a_{ii}^{(2)}\le a_{ii},i=2,3,…n$
- $\max_{1\le i,j\le n}|a_{ij}^{(2)}|\le\max_{2\le i,j\le n}|a_{ij}|$
ans. 这几题其实都是高等代数里面正定矩阵的相关知识。
- $A$ 正定，则 $e_i\ne 0,e_i^TAe_i=a_{ii}>0$
- $f(x_1,…x_n)=x^TAx>0$ 令 $x_i,x_j\ne 0$ 其余 $x_k$ 均为 $0$ 则仍然有 $f=x^TAx>0$ ，从而可知 $\begin{pmatrix}a_{ii} &a_{ij}\\ a_{ji} &a_{jj}\end{pmatrix}$ 为正定矩阵，从而 $a_{ii}a_{jj}>a_{ij}^2$
显然有 $|a_{ij}|<\sqrt{a_{ii}a_{jj}}\le\frac{1}{2}(a_{ii}+a_{jj})$
- 反证 $|a_{ij}|$ 为绝对值最大的元，则由 $|a_{ij}|<\frac{1}{2}(a_{ii}+a_{jj})$ 可知 $a_{ii},a_{jj}$ 中一定有一个大于 $|a_{ij}|$ ,这与假设矛盾，即证
- $A_2=A_1-\frac{\alpha^T\alpha}{a_{11}}$ ，由于 $A_1$ 对称正定，所以 $A_2$ 对称显然，反证不是正定的，则 $\exists x\ne 0,x^T A_2x\le 0$ ，由于 $A=P^T\begin{pmatrix}a_{11} &0\\ 0 &A_1-\frac{\alpha^T\alpha}{a_{11}}\end{pmatrix}P$ 从而 $(0,x)^TA(0,x)=y^T\begin{pmatrix}a_{11} &0\\ 0 &A_1-\frac{\alpha^T\alpha}{a_{11}}\end{pmatrix}y<0$ 矛盾
- $a^{(2)}_{ii}=a_{ii}-\frac{a_{i1}}{a_{11}}a_{1i}
- 利用对称正定矩阵性质，最大值在对角线上，以及上面一题的结论立刻可得
Problem 9
- 用 Guass 消元法求解下列线性方程组，并求系数矩阵的行列式
ans.
解得 $x_1=1,x_2=2,x_3=0,x_4=-2,\det (A)=-144$
Problem 10
- 设 $A=\begin{pmatrix}1 &2 &3\\
2 &3 &4\\
3 &4 &4\end{pmatrix},b=\begin{pmatrix}2\\3\\3\end{pmatrix}$
- 求解线性方程组 $Ax=b$
求所有满足 $y^TAy<0$ 的 $y$
ans. $\begin{align}\begin{pmatrix}1 &2 &3 &2\\ 2 &3 &4 &3\\ 3 &4 &4 &3\end{pmatrix}\rightarrow &\begin{pmatrix}1 &2 &3 &2\\ 0 &-1 &-2 &-1\\ 0 &-2 &-5 &-3\end{pmatrix}\\ \rightarrow &\begin{pmatrix}1 &2 &3 &2\\ 0 &-1 &-2 &-1\\ 0 &0 &-1 &-1\end{pmatrix}\end{align}$
解得 $x_1=1,x_2=-1,x_3=1$
第二问其实就是一个对角化，但由于数据中涉及根号太过复杂。就略去了。
Problem 11
- $A$ 为实对称正定矩阵，证明 $D=\mathrm{diag}(a_{11},…a_{nn})$ 仍为实对称正定矩阵
ans. 其实只需要证明 $a_{ii}>0$ 即可，而这一点在 Problem 8 第一问中就解答过了，不证。
Problem 12
- 用下列方法求矩阵 $A=\begin{pmatrix}2 &1 &2\\
1 &2 &3\\
4 &1 &2\end{pmatrix}$ 的逆矩阵
- 解方程组 $Ax=e_i$
- 通过 $LU$ 三角分解
ans
- 利用解方程的方法，其实就是初等变换，一般手工计算逆矩阵都是这个办法
从而逆矩阵为 $A^{-1}=\begin{pmatrix}&-21/2 &4 &7/2\\&15 &-6 &-6 \\&7/2 &-1 &-3/2\end{pmatrix}$
- 利用 $LU$ 分解， $LU$ 分解本身不难，但是求三角矩阵的逆矩阵也不容易，这个方法计算量还是很大的，此处仅给出紧凑格式的 $LU$ 分解，三角矩阵的逆矩阵计算过程省略。
从而 $A=\begin{pmatrix}1 &0 &0\\ 1/2 &1 &0\\ 2 &-2/3 &1\end{pmatrix}\begin{pmatrix}2 &1 &2\\ 0 &3/2 &2\\ 0 &0 &-2/3\end{pmatrix}$
求逆：
Problem 13
- 设 $A,B$ 均为 $n$ 阶方阵， $I,O$ 分别为 $n$ 阶单位阵和 $n$ 阶零矩阵，求 $\begin{pmatrix}I &A &0\\
0 &I &B\\
0 &0 &I\end{pmatrix}$ $3n$ 阶矩阵的逆
ans. 方法还是做初等变化，分块矩阵的初等变化要注意左右乘不一样。
从而 $A^{-1}=\begin{pmatrix}I &-A &-AB\\ 0 &I &-B\\ 0 &0 &I\end{pmatrix}$
Problem 14
若 $A$ 为三对角矩阵，即 $A=\begin{pmatrix}a_1 &c_1 & &\\
b_2 &\ddots &\ddots &\\
&\ddots &\ddots &c_{n-1}\\
& &b_n &a_n \end{pmatrix}$且 $|a_i|\ge|b_i|+|c_i|,|a_1|>|c_1|,|a_n|>|b_n|,c_ib_i\ne 0$
证明 $A$ 的顺序主子式皆不为零
ans. 这题课本中其实已经给出了证明，这里我们再重新叙述一遍。
对 $n$ 进行数学归纳法，当 $n=1$ 时，$a_1>0$ 成立。
假设 $n-1$ 阶三对角矩阵成立。 由于
注意到 $|a_2-\frac{b_2}{a_1}c_1|\ge |a_2|-|\frac{c_1}{a_1}b_2|> |a_2|-|b_2|\ge|c_2|$ 从而为 $n-1$ 阶三对角矩阵，利用归纳原理即证。
Problem 15
- 求三对角矩阵 $\begin{pmatrix}1 &1 & &\\
1 &2 &1 & &\\
&1 &3 &1 &\\
& &1 &4 &1\\
& & &1 &5\end{pmatrix}$的 $LU$ 分解及其行列式的值
ans. $\begin{pmatrix}1 &1 & & &\\ 1 &2 &1 & &\\ &1 &3 &1 &\\ & &1 &4 &1\\ & & &1 &5\end{pmatrix}\rightarrow \begin{pmatrix}1 &1 & & &\\ 1 &1 &1 & &\\ &1 &2 &1 &\\ & &1/2 &7/2 &1\\ & & &2/7 &33/7\end{pmatrix}$
从而 $A=\begin{pmatrix}1 & & & &\\ 1 &1 & & &\\ &1 &1 & &\\ & &1/2 &1 &\\ & & &2/7 &1\end{pmatrix}\begin{pmatrix}1 &1 & & &\\ &1 &1 & &\\ & &2 &1 &\\ & & &7/2 &1\\ & & & &33/7\end{pmatrix}$
$\det A=1\cdot 1\cdot 2\cdot 7/2\cdot 33/7=33$
Problem 16
- 若 $A\in M^{n\times n}$ 为实对称矩阵或 Hermite 矩阵，证明 $\Vert A\Vert_2=\rho(A)$
ans. 实对称矩阵 $A^T=A$ ，
则 $\Vert A\Vert_2=\sqrt{\lambda_{\max}(A^TA)}=\max\sqrt{\lambda(A^2)}=\max|\lambda_i|$
即 $\Vert A\Vert_2=\rho(A)$
Hermite 矩阵 $A^\ast=A$ ，注意此时 $2-$ 范数的定义为 $\Vert A\Vert_2=\sqrt{\lambda_{\max}(A^\ast A)}$
其余只需模仿上面即可，不证。
Problem 17
- 若 $A\in M^{n\times n}$ 为正交矩阵，证明 $\mathbb{cond}_2(A)=1$
ans. 只需说明两点，正交矩阵的 $2-$ 范数为 $1$ ，正交矩阵的逆矩阵也是正交矩阵。而这两点是明显的，不证。
Problem 18
- 设 $m\times n$ 阶矩阵 $A$ 为列满秩矩阵，矩阵 $A$ 的条件数：
- 当 $m=n$ 时，上述条件数的定义与之前定义一致
- 设 $\lambda_i$ 为 $n$ 阶方阵 $A^TA$ 的特征值，证明：
- 求 $\begin{pmatrix}1 &1 &\cdots &1\\ \epsilon &0 &\cdots &0\\ 0 &\epsilon &\cdots &0\\ \vdots &\vdots & &\vdots\\ 0 &0 &\cdots &\epsilon\end{pmatrix}$ 的条件数 $\mathbb{cond}_2(A)$
ans. 我们先来证明一个引理： 以下范数均指 $2-$范数
则 $\max_{\Vert x\Vert=1}\Vert Ax\Vert^2=\lambda_{\max}(A^TA),\min_{\Vert x\Vert=1}\Vert Ax\Vert^2=\lambda_{\min}(A^TA)$
实对称矩阵正交相似于对角矩阵，且对角元素为特征根。
从而 $\max_{\Vert x\Vert=1}\Vert Ax\Vert^2=\max_{\Vert x\Vert=1}x^TA^TAx=\max_{\Vert x\Vert=1}x^TP^TDPx$
其中 $P$ 为正交矩阵，所以 $y:=Px,\Vert y\Vert=1$ 。这样我们不妨设 $\lambda_1$ 为特征值中模最大元素，$\lambda_2$ 为最小元素
则有 $\lambda_1y_1^2+…\lambda_ny_n^2$ ，则我们取 $y=e_1$，有最大值 $|\lambda_1|$ ，$y=e_2$ ，有最小值 $|\lambda_2|$
- 证明 $\max_{\Vert x\Vert_2=1}\Vert Ax\Vert_2/\min_{\Vert x\Vert_2=1}\Vert Ax\Vert_2$ 按照引理，这其实就是 $A^TA$ 的特征值的模的最大值除以最小值然后开平方。而 $\Vert A\Vert$ 就是 $A^TA$ 的模的最大值，只需说明 $\Vert A^{-1}\Vert$ 其实是 $A^TA$ 的特征值的模的最小值的倒数。
$\Vert A^{-1}\Vert =\sqrt{\lambda_{\max}(A^{-1})^TA^{-1}}=\sqrt{1/\lambda_{\min}A^TA}$
这里运用了 $A^{-1}$ 的特征值就是 $A$ 的特征值的倒数。
- 第二问其实第一问中已经做了回答
- 第三问
最大值为 $\epsilon^2+n$ ，最小值 $\epsilon^2$ 。从而条件数为 $(\epsilon^2+n)/{\epsilon^2}$
Problem 19
- 设 $A$ 为非奇异矩阵，且 $\Vert A^{-1}\Vert\cdot \Vert \delta A\Vert<1$ ，证明 $(A+\delta A)^{-1}$ 存在且有下列关系式：
ans. 先证非奇异，反证则 $\exists \eta \ne 0,s.t. (A+\delta A)\eta=0$ 再由 $A$ 非奇异，$(I+A^{-1}\delta A)\eta=0$ 有 $A^{-1}\delta A\eta=-\eta$ ，从而 $\Vert A^{-1}\delta A\Vert\ge 1$ 矛盾
又设 $(A\delta A)(A^{-1}+\delta A^{-1})=E$
则有 $A+\delta A^{-1}+\delta A A^{-1}+\delta A\delta A^{-1}=0$
而 $\delta A^{-1}=(A+\delta A)^{-1}-A^{-1}$ ，两边取模得
两边同除以 $\Vert A^{-1}\Vert$
Problem 20
- $A\in M^{n\times n}$ 非奇异， $b\in\mathbb{R}^n$ 非零，$A,b$ 分别有扰动 $\delta A,\delta b$ 若 $\Vert A^{-1}\Vert<1$ 证明：
ans. 设 $(A+\delta A)(x+\delta x)=b+\delta b$
从而 $A\delta x+\delta A x+\delta A\delta x=\delta b$
解出 $\delta x$
两边取范数
同除以 $\Vert x\Vert$ ：
注意到 $\Vert A\Vert\Vert x\Vert\ge\Vert b\Vert$整理最后一项就得到