数值代数作业 1

习题一 T1

给出求下三角矩阵的逆矩阵的详细算法.

利用类似 Gauss 消元法的想法即可，这里为方便起见不选主元（仅仅在每次循环时多一步检查列绝对值最大元的操作），处理第 $k$ 列时，先消去严格下三角部分的数值：

$$L_{k}A,L_k=I-l_k{e}_k^{\mathrm{T}}$$

然后乘数值使得 $(k,k)$ 位为 $1$ .

% Input: 矩阵 A
% Output: A 的逆矩阵，就地操作
 
for j = 1:n
	% 计算对角线元素
	A(j,j) = 1 / A(j,j);
	% 计算当前列的下方非对角元素
	for i = j+1:n
		A(i,j) = (-A(i, j:i-1) * A(j:i-1, j)) / A(i,i);
	end
end

经过 MATLAB 验证准确. $\square$

习题一 T7

设 $A$ 对称且 $a_{11}\ne 0$ ，并假定经过一步 Gauss 消去之后，$A$ 具有如下形式

$$\left(\begin{array}{cc}{a}_{11}& a_1^{\mathrm{T}}\\ 0& A_2\end{array}\right)$$

证明 $A_2$ 仍然是对称阵.

证明与解：设题中经过一步之后的矩阵 $A$ 为 $A^{(1)}$ .考虑经过一次 Gauss 消去之后 $A_2$ 当中的元素. 其中 $A^{(1)}$ 整体第 $i$ 行 $j$ 列（其中 $i⩾2$ 以及 $j⩾2$）的元素为：

$$A_{ij}^{(1)}=a_{ij}-a_{1j}\cdot \frac{a_{i1}}{a_{11}}$$

而根据 $A$ 是对称阵，容易得到

$$A_{ij}^{(1)}=a_{ij}-a_{1j}\cdot \frac{a_{i1}}{a_{11}}=a_{ji}-a_{1i}\cdot \frac{a_{j1}}{a_{11}}=A_{ji}^{(1)}$$

这说明 $A_2$ 是对称阵. $\square$

习题一 T9

设 $A\in {\mathbb{R}}^{n\times n}$ 有三角分解，指出当把 Gauss 消去法应用于 $n\times (n+1)$ 矩阵 $[A,b]$ 时，怎样才能不必存储 $L$ 而解出 $Ax=b$ ？需要多少次乘法运算.

证明与解：首先对 $[A,b]$ ，先作行变换使得其中的 $A$ 变为上三角，也就是说先对整体做一次类似前代法的操作：

% 记 B = [A,b]
for j = 1:n-1
	% 按列
	for k = j+1:n
	% 逐行操作
		B(k,1:n+1) = B(k,1:n+1) - B(k,j) * B(j,1:n+1)/B(j,j)
	end
end

其中乘法次数应该为

$$\sum _{j=1}^{n-1}\sum _{k=j+1}^n(n+1)=\frac{1}{2}{n}^3-\frac{1}{2}n$$

然后对于上三角矩阵，再通过行变换将其变为对角阵：

for j = n:-1:2
	for k=1:j-1
		B(k,1:n+1) = B(k,1:n+1) - B(k,j) * B(j,1:n+1)/B(j,j)
	end
end

这里和先前的操作是对称的，同样需要 $\frac{1}{2}{n}^3-\frac{1}{2}n$ 次乘法操作.

最后还需要把对角线元素都化为 $1$ ，共 $n$ 次乘法操作，综上加起来共有 $n^3$ 次乘法操作. $\square$

习题一 T11

设

$$A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)$$

并且 $A_{11}$ 为 $k$ 阶非奇异阵，矩阵

$$S=A_{22}-A_{21}{A}_{11}^{-1}{A}_{12}$$

称为 $A_{11}$ 在 $A$ 中的 Schur 余阵，证明：如果 $A_{11}$ 有三角分解，那么经过 $k$ 步 Gauss 消去以后，$S$ 正好等于 $(\mathrm{1.1.4})$ 的矩阵 $A_{22}^{(k-1)}$ .

证明： 不难发现

$$\left(\begin{array}{cc}I& 0\\ -A_{21}{A}_{11}^{-1}& I\end{array}\right)A=\left(\begin{array}{cc}{A}_{11}& \ast \\ 0& S\end{array}\right)$$

左侧的矩阵实际上就是 Gauss 变换矩阵 $L$ ，计算过程就是消元过程，根据消元计算过程的唯一性，$S=A_{22}^{(k-1)}$ . $\square$

习题一 T16

形如 $N(y,k)=I-y{e}_k^{\mathrm{T}}$ 的矩阵称作 Gauss-Jordan 变换，其中 $y\in {\mathbb{R}}^n$ . (1) 假定 $N(y,k)$ 非奇异，试给出计算其逆元的方式；

(2) 向量 $x\in {\mathbb{R}}^n$ 满足何种条件才能保证存在 $y\in {\mathbb{R}}^n$ ，使得

$$N(y,k)x=e_k?$$

(3) 给出一种利用 Gauss-Jordan 变换求 $A\in {\mathbb{R}}^{n\times n}$ 的逆矩阵 $A^{-1}$ 的算法，并且说明 $A$ 满足何种条件才能保证你的算法能够进行到底.

证明与解：

(1) 考虑分块矩阵：

$$M=\left(\begin{array}{cc}I& y\\ e_k^{\mathrm{T}}& 1\end{array}\right)$$

可作初等变换使得

$$\begin{array}{rl}\left(\begin{array}{cc}M& I\end{array}\right)& \Rightarrow \left(\begin{array}{cccc}I& y& I& 0\\ e_k^{\mathrm{T}}& 1& 0& I\end{array}\right)\\ & \Rightarrow \left(\begin{array}{cccc}I-y{e}_k^{\mathrm{T}}& 0& I& -y\\ e_k^{\mathrm{T}}& 1& 0& I\end{array}\right)\\ & \Rightarrow \left(\begin{array}{cccc}I& 0& (I-y{e}_k^{\mathrm{T}}{)}^{-1}& \ast \\ 0& 1& \ast & \ast \end{array}\right)\end{array}$$

因此考虑 $M^{-1}$ 的左上角部分即可，同样利用另一种方式的初等变换，即直接消元：

$$\begin{array}{rl}\left(\begin{array}{cc}M& I\end{array}\right)& \Rightarrow \left(\begin{array}{cccc}I& y& I& 0\\ e_k^{\mathrm{T}}& 1& 0& I\end{array}\right)\\ & \Rightarrow \left(\begin{array}{cccc}I& y& I& 0\\ 0& 1-e_k^{\mathrm{T}}y& -e_k^{\mathrm{T}}& I\end{array}\right)\\ & \Rightarrow \left(\begin{array}{cccc}I& 0& I+(1-e_k^{\mathrm{T}}y{)}^{-1}y{e}_k^{\mathrm{T}}& -(1-e_k^{\mathrm{T}}y{)}^{-1}y\\ 0& 1-e_k^{\mathrm{T}}y& -e_k^{\mathrm{T}}& I\end{array}\right)\\ & \Rightarrow \left(\begin{array}{cccc}I& 0& I+(1-e_k^{\mathrm{T}}y{)}^{-1}y{e}_k^{\mathrm{T}}& \ast \\ 0& 1& \ast & \ast \end{array}\right)\end{array}$$

因此

$$(I-y{e}_k^{\mathrm{T}}{)}^{-1}=I+(1-e_k^{\mathrm{T}}y{)}^{-1}y{e}_k^{\mathrm{T}}$$

(2) 先变换为

$$y=\frac{x-e_k}{e_k^{\mathrm{T}}x}$$

因此仅需保证 $x$ 的第 $k$ 个分量不为 $0$ 即可.

(3) 根据 (1) 和 (2) ，将 $A$ 表示为列向量集合

$$A=(x_1,x_2,\cdots ,x_n)$$

我们要求

$$BA=(B{x}_1,B{x}_2,\cdots ,B{x}_n)=(e_1,e_2,\cdots ,e_n)$$

因此，利用 Gauss-Jordan 变换求

$$B{x}_i=e_i$$

共 $n$ 个线性方程组即可，利用 Gauss 消元法时，每一步的 Gauss 变换矩阵形如 Gauss-Jordan 阵.

根据 (2) ，算法能进行到底的条件就是对于每个 $x_i$ ，其第 $i$ 个分量不为 $0$ . $\square$