算法导论28 Problems 答案

28-1

a

以下是多轮进行迭代的结果：

$\begin{array}{c|c}
L&U\
\begin{bmatrix}
1&0&0&0&0\
0&1&0&0&0\
0&0&1&0&0\
0&0&0&1&0\
0&0&0&0&1\
\end{bmatrix}&
\begin{bmatrix}
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
\end{bmatrix}\
\begin{bmatrix}
1&0&0&0&0\
-1&1&0&0&0\
0&0&1&0&0\
0&0&0&1&0\
0&0&0&0&1\
\end{bmatrix}&
\begin{bmatrix}
1&-1&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
\end{bmatrix}\
\begin{bmatrix}
1&0&0&0&0\
-1&1&0&0&0\
0&-1&1&0&0\
0&0&0&1&0\
0&0&0&0&1\
\end{bmatrix}&
\begin{bmatrix}
1&-1&0&0&0\
0&1&-1&0&0\
0&0&0&0&0\
0&0&0&0&0\
0&0&0&0&0\
\end{bmatrix}\
\begin{bmatrix}
1&0&0&0&0\
-1&1&0&0&0\
0&-1&1&0&0\
0&0&-1&1&0\
0&0&0&0&1\
\end{bmatrix}&
\begin{bmatrix}
1&-1&0&0&0\
0&1&-1&0&0\
0&0&1&-1&0\
0&0&0&0&0\
0&0&0&0&0\
\end{bmatrix}\
\begin{bmatrix}
1&0&0&0&0\
-1&1&0&0&0\
0&-1&1&0&0\
0&0&-1&1&0\
0&0&0&-1&1\
\end{bmatrix}&
\begin{bmatrix}
1&-1&0&0&0\
0&1&-1&0&0\
0&0&1&-1&0\
0&0&0&1&-1\
0&0&0&0&0\
\end{bmatrix}\
\begin{bmatrix}
1&0&0&0&0\
-1&1&0&0&0\
0&-1&1&0&0\
0&0&-1&1&0\
0&0&0&-1&1\
\end{bmatrix}&
\begin{bmatrix}
1&-1&0&0&0\
0&1&-1&0&0\
0&0&1&-1&0\
0&0&0&1&-1\
0&0&0&0&1\
\end{bmatrix}\
\end{array}$

b

根据题目28-1-a，可知对应求出$L$和$U$矩阵的$P=I_5$。

因此，可以通过反向替代求出$U\mathbf{x}=\mathbf{y}=(1,2,3,4,5)^T$。接下来，可以通过正向替代求出$\mathbf{x}=(15,14,12,9,5)^T$。

c

令$e_1,e_2,e_3,e_4,e_5$分别为每一维内的单位向量，考虑按照题目28-2-b的方法分别求解方程组$A\mathbf{x_1}=e_1,A\mathbf{x_2}=e_2,A\mathbf{x_3}=e_3,A\mathbf{x_4}=e_4,A\mathbf{x_5}=e_5$的解，分别得到：

$\begin{aligned}
\mathbf{x_1}&=(5,4,3,2,1)^T\
\mathbf{x_2}&=(4,4,3,2,1)^T\
\mathbf{x_3}&=(3,3,3,2,1)^T\
\mathbf{x_4}&=(2,2,2,2,1)^T\
\mathbf{x_5}&=(1,1,1,1,1)^T\
\end{aligned}$

因此得到$A^{-1}$为：

$A^{-1}=(\mathbf{x_1},\mathbf{x_2},\mathbf{x_3},\mathbf{x_4},\mathbf{x_5})=
\begin{bmatrix}
5&4&3&2&1\
4&4&3&2&1\
3&3&3&2&1\
2&2&2&2&1\
1&1&1&1&1\
\end{bmatrix}$

d

考虑对算法LU-DECOMPOSITION行为的讨论。由于$A$是一个三对角矩阵，因此主对角线上的元素$a{ii}(i< n)$，下方仅有至多一个元素不为$0$，它是$a{i+1,i}$。因此算法LU-DECOMPOSITION的第6行的for循环只需要对第$i+1$行处理即可。这意味着$L$矩阵的第$i$列只有元素$l{ii}$和$l{i+1,i}$可能非零，其它元素都是$0$。

同理，主对角线上的元素$a{ii}(i< n)$，油坊方仅有至多一个元素不为$0$，它是$a{i,u1}$。因此算法LU-DECOMPOSITION的第10行的for循环只需要对第$i+1$列处理即可，根据上面的结论，第9行的for循环也只会处理到第$i+1$行。这意味着$U$矩阵的第$i$行只有元素$u{ii}$和$u_{i,i+1}$可能非零，其它元素都是$0$。

因此，只需要$O(n)$的时间就可以构造出三对角矩阵的$L$矩阵和$R$矩阵。由于$L,U$中每行每列至多只有$2$个元素非$0$，因此可以在$O(n)$的时间内完成后向替代和前向替代，求出原方程的解，原结论成立。

考虑使用题目28-1-c的方法求逆矩阵，即计算$n$个线性方程组的解，计算每个解需要花费$O(n)$的时间，因此构造出$A^{-1}$需要$n\cdot O(n)=O(n^2)$的时间。由于构建一个矩阵至少需要$\Omega(n^2)$的时间，因此其它求解$A$逆矩阵的算法将不会低于$\Omega(n^2)$。原结论成立。

e

证明过程和题目28-1-d类似。由于$A$是一个三对角矩阵，因此算法LUP-DECOMPOSITION的第6行和第15行for循环最多只需要执行到第$i+1$行；因此，在LUP-DECOMPOSITION执行的过程中，当处理到第$k$行时，因为可能需要和第$k+1$行交换元素，因此$a_{k,k+2}$也有可能非$0$。但总而言之，第$k$行其它元素必定非$0$，因此和第13行和第17行的for循环只需要执行到第$k+2$列，此外13行的for循环的起点只需要设成$\max{1,k-1}$即可，因为第$k$行和第$k+1$行的前$k-2$个元素均为$0$，可以免去交换。

因此，对三对角矩阵执行算法LUP-DECOMPOSITION后，得到的$L$矩阵的第$i$列只有元素$l{ii}$和$l{i+1,i}$可能非零，其它元素都是$0$；得到的$U$矩阵的第$i$行只有元素$u{ii},u{i,i+1},u_{i,i+2}$可能非零，其它元素都是$0$。

因此，只需要$O(n)$的时间就可以构造出三对角矩阵的$L$矩阵和$R$矩阵，以及序列$\pi$。由于$L,U$中每行每列至多只有$3$个元素非$0$，因此可以在$O(n)$的时间内完成后向替代和前向替代，求出原方程的解，原结论成立。

28-2

a

考虑第$i$个样条的曲线的系数。由于$f(xi)=f(i)=y_i,f(x{i+1})=f(i+1)=y{i+1}$，因此有$f_i(0)=y_i,f_i(1)=y{i+1}$。类似的，由于$f’(xi)=D_i,f’(x{i+1})=D{i+1}$，因此有$f_i’(0)=D_i,f_i’(1)=D{i+1}$。那么可以列出如下关于$a_i,b_i,c_i,d_i$的四元一次方程组：

$\left{\begin{aligned}
ai&=y_i\
a_i+b_i+c_i+d_i&=y{i+1}\
bi&=D_i\
b_i+2c_i+3d_i&=D{i+1}
\end{aligned}\right.$

因此可以直接计算出：

$\left{\begin{aligned}
ai&=y_i\
b_i&=D_i\
c_i&=3y{i+1}-3yi-D{i+1}-2Di\
d_i&=D{i+1}-2y_{i+1}+2y_i+D_i
\end{aligned}\right.$

由于每个数$yi,y{i+1},Di,D{i+1}$都是已知的，因此我们可以以$O(n)$的时间直接在计算出这$4n$个系数。

b

如果二阶仍然保持连续性限制，那么有$f{i}’’(1)=f{i+1}’’(0)$。也就是可以得到

$$2c_i+6d_{i}=2c_{i+1}$$

将题目28-2-a的方程组的解代入此式，化简后即可得到

$$D_i+4D_{i+1}+D_{i+2}=3(y_{i+2}-y_i)$$

其中，$i=0,1,2,\dots,n-2$。将所有下标同时减去$1$即可得到原题目结论。

c

如果假设$x=0$是拐点，那么有$f’’(0)=0$，即$f’’i(0)=0$，可以得到$c_0=0$。代入$c_0=3y{1}-3y0-D{1}-2D_0$，可以得到$D_1+2D_0=3(y_1-y_0)$。

同样的，如果假设$x=n$也是拐点，那么有$f’’(n)=0$，即$f’’{n-1}(1)=0$，可以得到$2c{n-1}+6d{n-1}=0$。代入$c{n-1}=3y{n}-3y{n-1}-D{n}-2D{n-1},d{n-1}=D{n}-2y{n}+2y{n-1}+D{n-1}$，可以得到$D{n-1}+2Dn=3(y_n-y{n-1})$。

d

根据题目28-2-b和题目28-2-c的结论，可以写成如下关于$D$的$n+1$元线性方程组：

$$\begin{bmatrix} 2 & 1 & 0 & 0& \cdots & 0 & 0 & 0\\ 1 & 4 & 2 & 0& \cdots & 0 & 0 & 0\\ 0 & 1 & 4 & 2& \cdots & 0 & 0 & 0\\ 0 & 0 & 1 & 4& \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots &\vdots & \ddots & \vdots & \vdots &\vdots\\ 0 & 0 & 0 & 0&\cdots & 1 & 4 & 2\\ 0 & 0 & 0 & 0&\cdots & 0& 1 & 2 \end{bmatrix} \begin{bmatrix} D_0\\ D_1\\ D_2\\ D_3\\ \vdots\\ D_{n-1}\\ D_n\\ \end{bmatrix} = \begin{bmatrix} 3(y_1-y_0)\\ 3(y_2-y_0)\\ 3(y_3-y_1)\\ 3(y_4-y_2)\\ \vdots\\ 3(y_n-y_{n-2})\\ 3(y_n-y_{n-1}) \end{bmatrix}$$

将上面的方程组简化成$AD=Y$，那么可以发现，$A$是题目28-1中提到的三对角矩阵。

e

由于$A$是一个非奇异矩阵，也是一个三对角矩阵，因此按照题目28-1-e的结论，题目28-2-d所构造出的关于向量$D$的方程组可以在$O(n)$的时间计算出来。

计算出$D$后，按照题目28-2-a的结论，$f$中的每个样条的每个系数可以在$O(n)$时间内计算出来。

因此这种插值方式可以在$O(n)$时间内完成。

f

对于更一般的点值$(x0,y_0),(x_1,y_1),\dots,(x_n,y_n)$，其中$x_i\le x{i+1}$，并且$0\le i<n$。如果$x\in[xi,x{i+1}]$，那么$f(x)=fi(x-x_i)$，其中$f_i(x)$的定义域是$[0,x{i+1}-xi]$，令$t_i=x{i+1}-x_i$。

按照题目28-2-a类似的方式，可以导出如下关于$a_i,b_i,c_i,d_i$的方程组。

$\left{\begin{aligned}
fi(0)&=y_i\
f_i(t_i)&=y{i+1}\
fi’(0)&=D_i\
f_i’(t_i)&=D{i+1}
\end{aligned}\right.$

将其求解后，可以使用$yi,y{i+1},Di,D{i+1}$来表示$a_i,b_i,c_i,d_i$的值。

按照题目28-2-b类似的方式，可以得出$f’’i(t_i)=f{i+1}’’(0)$，化简后得到$2ci+6d{i}ti=2c{i+1}$。代入上面的式子，可以得到一个关于$Di,D{i+1},D_{i+2}$的等式。

按照题目28-2-c类似的方式，也可以得出两条分别关于$D0,D_1$的等式和$D{n-1},D_n$的等式。

最终由此构造出来的线性方程组仍然是$AD=Y$的形式，并且$A$仍然是一个三对角矩阵，之后构建出函数$f$的方法和题目28-2-e相同。