算法导论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,u_1}\)。因此算法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(x_i)=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'(x_i)=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} a_i&=y_i\\ a_i+b_i+c_i+d_i&=y_{i+1}\\ b_i&=D_i\\ b_i+2c_i+3d_i&=D_{i+1} \end{aligned}\right.\)

因此可以直接计算出：

\(\left\{\begin{aligned} a_i&=y_i\\ b_i&=D_i\\ c_i&=3y_{i+1}-3y_i-D_{i+1}-2D_i\\ d_i&=D_{i+1}-2y_{i+1}+2y_i+D_i \end{aligned}\right.\)

由于每个数\(y_i,y_{i+1},D_i,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}-3y_0-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}+2D_n=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

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

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

\(\left\{\begin{aligned} f_i(0)&=y_i\\ f_i(t_i)&=y_{i+1}\\ f_i'(0)&=D_i\\ f_i'(t_i)&=D_{i+1} \end{aligned}\right.\)

将其求解后，可以使用\(y_i,y_{i+1},D_i,D_{i+1}\)来表示\(a_i,b_i,c_i,d_i\)的值。

按照题目28-2-b类似的方式，可以得出\(f''_i(t_i)=f_{i+1}''(0)\)，化简后得到\(2c_i+6d_{i}t_i=2c_{i+1}\)。代入上面的式子，可以得到一个关于\(D_i,D_{i+1},D_{i+2}\)的等式。

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

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