《数值代数》课程教学资源（学习笔记）数值代数习题解答.pdf_大学文库

第一章线性方程组的直接解法 2 第一章线性方程组的直接解法 1. 假设输入方阵下标 1 到 n，A[i] 表示 A 的第 i 个行向量，O 代表 n 维零方阵 (采用增广矩阵求逆的思路)： def inverse(A, In): In = O; for j = 1 to n A[j] /= A[j][j] In[j][j] = 1/A[j][j] for j = 1 to n for i = j+1 to n In[i] ‐= A[i][j]In[j]; 2. 构造辅助 n 维向量 y，初始为零向量，设方阵下标为 1 到 n：令 k 从 n 到 1 循环，每次计算 xk = bk − Pn i=k skiyi skktkk − λ , yj = yj + xktjk(j ≥ n + 1 − k) 由定义可发现，每次循环的计算量都是 O(n)，因此总计算量为 O(n 2 )。证明思路：将矩阵分块为已算过的部分和将算的部分，已算过的部分通过 yi 进行“消除偏差”(yi 在每步后为假设 x 除了已算过的分量外均为 0 后被 T 左乘的结果) 后，即可通过直接的减法、除法得到将算的值。 3. 直接计算可验证其为逆。由定义 lk 只需满足前 k 个分量为 0，而 −lk 亦满足此要求，因此成立。 4. 由于 7 = 3 + 2 × 2, 8 = 4 + 2 × 2，可直接构造 L =   1 0 0 2 1 0 2 0 1  。 5. 若有 L1U1 = L2U2 = A，由 A 非奇异可知 L1, L2, U1, U2 非奇异，而 L −1 2 L1 = U2U −1 1 ，左侧为单位下三角阵，右侧为上三角阵，因此均只能是 I，从而得证。 6. 令 Lk = I + tke T k ，其中 tk 的前 k 个分量为 0，其余为 1，考虑 Ln . . . L1A = U 的结果。由于这相当于分别将 A 的每一行加到其下的所有行上，U 的左上角 n − 1 × n − 1 子矩阵为单位阵，最后一列为 1, 2, . . . , 2 n−1，其余为 0，即为所求。而所求的 L 为 L −1 1 . . . L−1 n ，除了主对角线外下三角部分的元素为 −1，满足要求。 7. 由对称阵定义，设变换后矩阵为 B，只需说明 bij = bji (i, j ≥ 2)，由高斯消去进行的行变换操作可知范围内 bij = aij − a1j ai1 a11，而 aij − a1j ai1 a11 = aji − aj1 a1i a11 = bji，从而得证。 8. 利用习题 7 结论，同乘 a11 后即需证明 |a11bkk| = |a11akk − a1kak1| > Pn j=2,j̸=k |a11akj − a1jak1|。而 Xn j=2,j̸=k |a11akj − a1jak1| ≤ Xn j=2,j̸=k |a11akj | + Xn j=2,j̸=k |a1jak1| = Xn j=2,j̸=k |a11akj | + Xn j=2 |a1jak1| − |a1kak1|

第一章钱性方程组的直接解法 3 ≤ lanal+lanaxl-lauakil <laal-lauakil s lanakx-aikaml 从而得证。又由习题7可知对称性保持，从而现在的主对角线对应元素是行列中的最大值，不需要再进行交换，由此即知列主元与直接消去结果相同。 9.不必储存L:将A与b同时左乘高斯变换阵，这样当A化为上三角阵时b也成为了合适的形式。此时再使用回代法即可。运算次数：高斯变换时，第k次需要对右下角n一k×n+1一k子方阵的每一个进行操作，每次操作需要减法、乘法、除法各一次，因此总数量为∑必=1n一)(m十1一)=n3一n。回代法需要的乘法运算数量为血-一严，因此总数量为n3+nm-n。 10.由习题7可知其对称，下面进一步说明正定。设变换后的B=LA,考虑C=LALT,由于右乘LT对应的操作为左下角右侧的列减去第一列，而此时第一列只有b:不为0，C的右下角仍然为A2,更进一步，由正定阵性质，相合变换后仍正定因此C为正定阵，由对称性可知C必然为diag(a11,A2):考虑特征值可知A2必然也为正定阵，由此得证。 s 下方一列可知MA1+A21=0,MA12+A2=S,左式可解出M=-A21A,代入右式即得结论 12.由于全主元第i次消去时将“：调整为右下角矩阵中最大元，此时其必然大于等于右侧的任何元素，而此后的操作并不会影响第i行及其上方的部分，大于等于本行右边的性质得以保存，从而得证。 13.通过列主元高斯消去，可得到PA=LU,利用习题1实现的求逆算法（对上三角阵类以）可得到L一与U1,再计算U-1L-1P即为A的逆。 14.记4，为A~1的第j列，考虑方程0=即可解出a,而其第i个分量即为所求（由于只需要知道一个分量，最后一步解Ua,=L-1e的过程进行部分即可)。 15.由于AT是严格对角占优阵，A的主对角线元素模长大于本列其他所有元素模长之和。类似习题8 估算可证明每次高斯消去后的A2仍满足A严格对角占优，从而选出的列主元即为主对角线上元素，因此直接高斯清元与列主元效果相同。由于每次保证了对角元模长是本列最大，当：≠方时有 ll<1。 16.(四由于(-e)+ye)=1-班yef,有(I-ye0+ye-班)=(1-)，由此即得非奇异时逆为1+，而直接计算行列式可验证1一熟=0时奇异， (2(I-yef)z=ek,即y=I-ee,存在解要求不能为0. 间第法类似高断消去，每次操作后成为())需要4左上角的元素丰零才能维线取解。利用分块考虑每次操作使用的方阵的k阶顺序主子式部分，其为单位下三角阵，与定理1.1,1完全相同可知每次得到的A-k左上角的元素非零等价于A的各阶顺序主子式非奇异。 17.若有A=L,T=L2Lg,则有L2L1=LT,由于左侧为下三角，右侧为上三角，最终乘积一定为对角阵。但由于LT=(LL2)=(LL)T,此对角阵与自己逆转置相同，每个元素只能为正负1。由于乙1与L2对角元为正，计算可知每个元素只能为此对角阵元素必须为正，因此即为单位阵，从而得证

第一章线性方程组的直接解法 3 ≤ Xn j=2,j̸=k |a11akj | + |a11ak1| − |a1kak1| < |a11akk| − |a1kak1| ≤ |a11akk − a1kak1| 从而得证。又由习题 7 可知对称性保持，从而现在的主对角线对应元素是行列中的最大值，不需要再进行交换，由此即知列主元与直接消去结果相同。 9. 不必储存 L：将 A 与 b 同时左乘高斯变换阵，这样当 A 化为上三角阵时 b 也成为了合适的形式。此时再使用回代法即可。运算次数：高斯变换时，第 k 次需要对右下角 n − k × n + 1 − k 子方阵的每一个进行操作，每次操作需要减法、乘法、除法各一次，因此总数量为 Pn k=1(n − k)(n + 1 − k) = 1 3 n 3 − 1 3 n。回代法需要的乘法运算数量为 (n−1)n 2 ，因此总数量为 1 3 n 3 + 1 2 n 2 − 5 6 n。 10. 由习题 7 可知其对称，下面进一步说明正定。设变换后的 B = LA，考虑 C = LALT，由于右乘 L T 对应的操作为左下角右侧的列减去第一列，而此时第一列只有 b11 不为 0，C 的右下角仍然为 A2，更进一步，由正定阵性质，相合变换后仍正定，因此 C 为正定阵，由对称性可知 C 必然为 diag(a11, A2)。考虑特征值可知 A2 必然也为正定阵，由此得证。 11. 设 k 次后对应左乘的 L 为 Lk O M In−k ! ，则由算法有 Lk O M In−k ! A11 A12 A21 A22! = Uk N O S ! 。考虑下方一列可知 MA11 + A21 = O, MA12 + A22 = S，左式可解出 M = −A21A −1 11 ，代入右式即得结论。 12. 由于全主元第 i 次消去时将 uii 调整为右下角矩阵中最大元，此时其必然大于等于右侧的任何元素，而此后的操作并不会影响第 i 行及其上方的部分，uii 大于等于本行右边的性质得以保存，从而得证。 13. 通过列主元高斯消去，可得到 P A = LU，利用习题 1 实现的求逆算法 (对上三角阵类似) 可得到 L −1 与 U −1，再计算 U −1L −1P 即为 A 的逆。 14. 记 aj 为 A−1 的第 j 列，考虑方程 LU aj = ej 即可解出 aj，而其第 i 个分量即为所求 (由于只需要知道一个分量，最后一步解 U aj = L −1 ej 的过程进行部分即可)。 15. 由于 AT 是严格对角占优阵，A 的主对角线元素模长大于本列其他所有元素模长之和。类似习题 8 估算可证明每次高斯消去后的 A2 仍满足 AT 2 严格对角占优，从而选出的列主元即为主对角线上元素，因此直接高斯消元与列主元效果相同。由于每次保证了对角元模长是本列最大，当 i ̸= j 时有 |lij | < 1。 16. (1) 由于 (I − yeT k )(I + yeT k ) = I − ykyeT k ，有 (I − yeT k )(I + yeT k − ykI) = (1 − yk)I，由此即得非奇异时逆为 I + yeT k 1 − yk ，而直接计算行列式可验证 1 − yk = 0 时奇异。 (2) (I − yeT k )x = ek，即 xky = I − ek，存在解要求 xk 不能为 0。 (3) 算法类似高斯消去，每次操作后成为 Ik M O An−k ! ，需要 An−k 左上角的元素非零才能继续取解。利用分块考虑每次操作使用的方阵的 k 阶顺序主子式部分，其为单位下三角阵，与定理 1.1.1 完全相同可知每次得到的 An−k 左上角的元素非零等价于 A 的各阶顺序主子式非奇异。 17. 若有 A = L1L T 1 = L2L T 2 ，则有 L −1 2 L1 = L T 2 L −T 1 ，由于左侧为下三角，右侧为上三角，最终乘积一定为对角阵。但由于 L T 2 L −T 1 = (L −1 1 L2) T = (L −1 2 L1) −T，此对角阵与自己逆转置相同，每个元素只能为正负 1。由于 L1 与 L2 对角元为正，计算可知每个元素只能为此对角阵元素必须为正，因此即为单位阵，从而得证

第一章线性方程组的直接解法 4 18. 带宽 2n + 1，也即 |i − j| > n 的部分均为 0，由平方根法的计算过程对 k 归纳可得 lik 亦会满足 |i − k| > n 的部分为 0(对 k + 1 时的情况，在 |i − k − 1| > n 时，ai,k+1 = 0，且 Pk p=1 liplkp 的每一个 lip 均为 0，因此 li,k+1 = 0)，又因其为三角阵，可知带宽为 n + 1。 19. 设 L = Lk O M Nn−k ! ，直接计算可知 A = LkL T k LkMT MLT k MMT + Nn−kNT n−k ! ，从而有结论 (由 Lk 为对角均正的下三角阵，也可推出 Ak 正定对称)。 20. 类似习题 10 的过程，在每次高斯变换左乘 Lk 时，同时右乘 L T k 。每次右乘不改变右下角的子矩阵，因此仍可通过定理 1.1.1 推知操作可进行至结束。由于每步保持对称性，在进行 n − 1 次消去后即得对角阵，此时 A = L −1 1 . . . L−1 n−1DL−T n−1 . . . L−T 1 ，即可合并为 LDLT。 21. 利用平方根法计算可知 L =   4 0 0 0 1 3 0 0 2 2 2 0 1 1 3 1   ，进一步计算得原方程组解为 x =   1 1 1 1   。 22. 假设输入方阵下标 1 到 n，O 代表 n 维零方阵 (实际计算过程与平方根法完全相同，只是改变计算顺序。实际操作时可直接用 A 的对应部分保存 l，此处为清晰将两矩阵分开)： def Cholesky(A, l): l = O for i = 1 to n for j = 1 to i‐1 l[i][j] = a[i][j] for p = 1 to j‐1 l[i][j] ‐= l[i][p]*l[j][p] l[i][j] /= l[j][j]; l[i][i] = a[i][i] for p = 1 to i‐1 l[i][i] ‐= l[i][p]*l[i][p] l[i][i] = sqrt(l[i][i]) 23. 假设正定对称矩阵 A 可以分解为 LDLT，则 A−1 = (L −1 ) T D−1L −1，利用习题 1 的算法可算出 L −1，再计算转置，D−1 即为每个对角元取倒数，最后计算乘法即可。 24. (1) 由 Hermite 性计算知 A 对称、B 反对称，从而 C 对称。由正定 (x + yi) H(A + Bi)(x + yi) > 0，从而 x T Ax + y T Ay + y TBx − x TBy > 0，此即为 x T y T A −B B A ! x y ! > 0，由于 x, y 可任取，知 C 正定。 (2) 此方程即 A −B B A ! x y ! = b c ! ，利用上题结论可知 A −B B A ! 为对称正定阵，从而由改进平方根法作出分解 LDLT 后即可通过 LDLT x y ! = b c ! 解出所求的 x, y

第二章钱性方程组的敏度分析与消去法的舍入误差分析第二章线性方程组的敏度分析与消去法的舍入误差分析 1.正定性：由于a,>0可知其良定，进一步由定义可知。齐次性：直接代入计算可知。三角不等式：记士=(a14,,anxn),=(ah,,anh,由于l2+/l2之z+l2,代入可知此范数具有三角不等式。 2.利用x+2≤x2+Iy2的证明过程可知取等当且仅当xy=zl,同平方得(1+…十工nP=(好+…+x2)(所+…+)，作差配方有∑c,(斯-斯)2=0，即可知，y各分量成比例。 3.直接计算A3=∑aP=∑=∑1la,P=∑1a服。 4.左：由二范数定义有A2≥业，其中B=(（61,bn),平方得A脆之，利用习题3，将右侧进行加权平均有‖A脂之∑，德能，即IAB胫≥∑，Ab,胫=AB,最后一步再次运用了习题3。右：利用左可知川BTATIle≤IBT2 lATI,而二范数与Frobenius范数均在转置下不变，因此同作转置即可。 5正定、齐次：由定义直接得。三角不等式：maxijla与+b,l≤max(lal+）≤max+max,两边同乘n即可相容性：max∑kakb≤max∑la≤maxax,两边同乘n即可。 v不满足相容：n维时两个全1矩阵的乘积为全n矩阵，当n>1时即可知v不满足相容性。仅当：若A不正定，由定义存在非零的x使得xTA≤0，此时不满是正定性或根号内为负数，不为范数。 7.正定性：由akA=n可知方程组Ax=0中可以选出n个独立方程，从而由x∈Rn可知解只能为x=0,由此利用Ax=0片A=0可知正定齐次性：由原范数齐次性，直接计算IAA=AAx=AAx,由此得证三角不等式：由Ax+‖A≥Ar+A=A(+)训可知成立。 8.先说明I-A可逆。由Al<1与AI≤An可知limn A=O,从而p(A)<1。考虑A的Jordan标准型J可发现对角元素模长小于l,而其右侧的副对角线上元素模长不超过 1,从而估算可知中任何元素不超过Ck(A),此级数求和收敛，因此∑。A收敛。由于 (-A)∑二A-1-A,取极限可知收敛极限即为(1-A)-1。 -2--+-=- 9.由于A可逆，{Az∈R"y=R",从而A-1‖=max=A-1z=maxA=A-1Az= maxl-z=max,=(min,)=(min=A)），因此得证。 10.由L下三角，U上三角可知a,=∑欢=1x,但只有当k≤mimi,j时才可能k,均非0，从而之后的项可忽略，对第i行可写成=，lu,又由LU分解性质可知a=1,从而 a一4=∑二lu,由于所有下标对应，写为行向量后即为题中形式

第二章线性方程组的敏度分析与消去法的舍入误差分析 5 第二章线性方程组的敏度分析与消去法的舍入误差分析 1. 正定性：由于 αi > 0 可知其良定，进一步由定义可知。齐次性：直接代入计算可知。三角不等式：记 x ′ = (α1x1, . . . , αnxn), y′ = (α1y1, . . . , αnyn)，由于 ∥x ′∥2 + ∥y ′∥2 ≥ ∥x ′ + y ′∥2，代入可知此范数具有三角不等式。 2. 利用 ∥x + y∥2 ≤ ∥x∥2 + ∥y∥2 的证明过程可知取等当且仅当 x T y = ∥x∥∥y∥，同平方得 (x1y1 + · · · + xnyn) 2 = (x 2 1 + · · · + x 2 n )(y 2 1 + · · · + y 2 n )，作差配方有 P i 1 时即可知 ν 不满足相容性。 6. 当：由 A 正定，其可作 Cholesky 分解 LLT，由定义可发现 f(x) = ∥L T x∥2，由 L T 可逆可知其正定，直接计算可知齐次，又由 L T (x + y) = L T x + L T y 可知满足三角不等式，故为范数。仅当：若 A 不正定，由定义存在非零的 x 使得 x T Ax ≤ 0，此时不满足正定性或根号内为负数，不为范数。 7. 正定性：由 rank A = n 可知方程组 Ax = 0 中可以选出 n 个独立方程，从而由 x ∈ R n 可知解只能为 x = 0，由此利用 ∥Ax∥ = 0 ⇔ Ax = 0 可知正定。齐次性：由原范数齐次性，直接计算 ∥λx∥A = ∥Aλx∥ = λ∥Ax∥，由此得证。三角不等式：由 ∥Ax∥ + ∥Ay∥ ≥ ∥Ax + Ay∥ = ∥A(x + y)∥ 可知成立。 8. 先说明 I − A 可逆。由 ∥A∥ < 1 与 ∥An∥ ≤ ∥A∥ n 可知 limn→∞ An = O，从而 ρ(A) < 1。考虑 A 的 Jordan 标准型 J 可发现对角元素模长小于 1，而其右侧的副对角线上元素模长不超过 1，从而估算可知 J k 中任何元素不超过 Cknρ(A) k，此级数求和收敛，因此 P∞ k=0 Ak 收敛。由于 (I − A) Pn−1 k=0 Ak = I − An，取极限可知收敛极限即为 (I − A) −1。 1 + ∥(I − A) −1∥∥A∥ ≥ 1 + ∥(I − A) −1A∥ ≥ ∥(I − A) −1 (I − A) + (I − A) −1A∥ = ∥(I − A) −1∥，同除以 1 − ∥A∥ 后移项即得证。 9. 由于 A 可逆，{Ax|x ∈ R n} = R n，从而 ∥A−1∥ = max∥x∥=1 ∥A−1x∥ = max∥Ax∥=1 ∥A−1Ax∥ = max∥Ax∥=1 ∥x∥ = maxx ∥x∥ ∥Ax∥ = minx ∥Ax∥ ∥x∥ −1 = min∥x∥=1 ∥Ax∥ −1，因此得证。 10. 由 L 下三角，U 上三角可知 aij = Pn k=1 likukj，但只有当 k ≤ min i, j 时才可能 lik, ukj 均非 0，从而之后的项可忽略，对第 i 行可写成 aij = Pi k=1 likukj，又由 LU 分解性质可知 lii = 1，从而 aij − uij = Pi−1 k=1 likukj，由于所有下标 j 对应，写为行向量后即为题中形式

第二章线性方程组的敏度分析与消去法的舍入误差分析 6 将此式两边取一范数后，利用三角不等式与l≤1可知lah+∑二il1之u,由此归纳可得‖1≤-2-1-‖al1+Ia≤2-1川A‖c,右边的不等号是由于A。为所有‖aF中最大的一个。由此，吃，u1≤2n-1Ae,从而IUx≤2n-1‖Ax。 1.(4=35-187）（-370375/20=(52+750376+婴)=8M637 (2)6=(1,1)T时x=(188,-188.5)7,而6=(1,1.1)7时x=(169.3,-169.75)7 (3)x=(1,-1)T时b=(1,2)T,而x=(1.1,-1)T时b=(38.5,77.2)T。 12.由于I川≥川且川>0，可知川≥1，从而(A)=AA-‖≥AA‖≥1。 13.右侧即为A-1II(A+E)-AI(A+E)-≥IA1-(A+E)-‖=I(A+E)-1-A1,从而得证。 14.由于1)=Ⅱ1x,1+-,4,代表每次乘法运算的舍入产生的误差，o=0。从而可知的上界为(1+叫m-1-1,由定理2.3.3，当(m-1)u≤0.01时即不超过1.01(n-1)u: 15.由定义可知（∑1）=∑1xⅡ，(1+，其中d表示每次加法运算产生的误差，d1=0。由 ≤0.01可知k知≤0.01当k≤n时成立，从而由定理23.3考虑每个x右边的(1+)个数可知结论。 16.设a为A的第i个行向量，则(Ar)=(ax)-∑1a1+)Π=，1+d),其中表示乘法运算产生的误差，dk代表加法运算产生的误差，1k=0,由于，的右侧乘上了 n j-1 n-j+2j≠1 个误差项，由定理2.3.3可知结论成立。 2=1+四L+,其中d表示每次加法运算产生的误差，6=0：由于每个一 n个误差项，的误差必在(1-)”与(1+)”之间。由于均为正，最大误差在同取+或-时，因此即有2∈1-，1+u门，于是a≤mm+O 18.类似第一章习题18可说明L与U均为带宽为2的带状矩阵，利用习题10等式，当A为三对角阵时，由于其他项都为0，有=-l-11,i≥2，从而由l≤1可知≥lal+-1≥ udl.i>2。由于0为带宽2的上三角阵，当且仅当i=j-1或j时4≠0，从而4，-1l≤a-1+4,-2l a-lu≤la+出-1d≤a-ld+a,因此U中任何元素不超过2 naxi lagl,从而得证。 1g.利用习题10等式可知。 -叫=∑二l第一章习题15已说明每一步分解中A的右下角子矩阵为列对角占优，因此∑二<l,于是ul≤lal+maxk<u 对上式归纳，ul≤al,此后每次最大值最多增加lal,因此i≤方时ul≤∑-1lal≤ ∑1lal≤2al而由于其为上三角阵，i<j时恒为0，从而p≤2。 20.由算法过程可以发现，由于每个元素所在的行列最多还有m个其他元素，计算[.U的过程中每个元素至多产生m次减法、m次乘法与1次除法的误差，由定理23.3可知每个元素的误差至多为(2m+1)u+O(u2),而计算回A的部分需要m次乘法与m一1次加法，类似得最终误差为 (2m-1)(2m+1)u+0(u2),当u较小时以4m2u为上界，m=3时即为36u 21.由算法过程可以发现，计算L的过程中每个元素至多产生n次减法、n次乘法与1次除法或开方的误差，而计算回A得过程中最多需要n次乘法与n一1次加法，类似习题20知最终误差为 Π-1(1+d),类似引理2.4.1计算方法可知条件下误差可以用4.09m2u控制

第二章线性方程组的敏度分析与消去法的舍入误差分析 6 将此式两边取一范数后，利用三角不等式与 |lij | ≤ 1 可知 ∥a T i ∥1 + Pi−1 j=1 ∥u T j ∥1 ≥ ∥u T i ∥1，由此归纳可得 ∥u T i ∥1 ≤ Pi−1 j=1 2 i−1−j∥a T j ∥1 + ∥a T i ∥1 ≤ 2 i−1∥A∥∞，右边的不等号是由于 ∥A∥∞ 为所有 ∥a T i ∥ 中最大的一个。由此，∀i, ∥u T i ∥1 ≤ 2 n−1∥A∥∞，从而 ∥U∥∞ ≤ 2 n−1∥A∥∞。 11. (1) A−1 = 375 −187 −376 375/2! , κ∞(A) = (752 + 750)(376 + 375 2 ) = 846377 (2) b = (1, 1)T 时 x = (188, −188.5)T，而 b = (1, 1.1)T 时 x = (169.3, −169.75)T。 (3) x = (1, −1)T 时 b = (1, 2)T，而 x = (1.1, −1)T 时 b = (38.5, 77.2)T。 12. 由于 ∥I∥∥I∥ ≥ ∥I∥ 且 ∥I∥ > 0，可知 ∥I∥ ≥ 1，从而 κ(A) = ∥A∥∥A−1∥ ≥ ∥AA−1∥ ≥ 1。 13. 右侧即为 ∥A−1∥∥(A + E) − A∥∥(A + E) −1∥ ≥ ∥A−1 − (A + E) −1∥ = ∥(A + E) −1 − A−1∥，从而得证。 14. 由于 fl( Qn i=1 xi) = Qn i=1 xi(1 + δi−1)，δi 代表每次乘法运算的舍入产生的误差，δ0 = 0。从而可知 ε 的上界为 (1 + u) n−1 − 1，由定理 2.3.3，当 (n − 1)u ≤ 0.01 时即不超过 1.01(n − 1)u。 15. 由定义可知 fl( Pn i=1 xi) = Pn i=1 xi Qn j=i (1 + δj )，其中 δi 表示每次加法运算产生的误差，δ1 = 0。由 nu ≤ 0.01 可知 ku ≤ 0.01 当 k ≤ n 时成立，从而由定理 2.3.3 考虑每个 xi 右边的 (1 + δj ) 个数可知结论。 16. 设 a T i 为 A 的第 i 个行向量，则 fl(Axi) = fl(a T i x) = Pn j=1 aijxj (1+λij ) Qn k=j (1+δik)，其中 λij 表示乘法运算产生的误差，δik 代表加法运算产生的误差，δ1k = 0，由于 aij 的右侧乘上了    n j = 1 n − j + 2 j ̸= 1 个误差项，由定理 2.3.3 可知结论成立。 17. fl(x T x) = Pn i=1 x 2 i (1 + λi) Qn j=i (1 + δi)，其中 δi 表示每次加法运算产生的误差，δ1 = 0。由于每个 x 2 i 右侧最多有 n 个误差项，每个 xi 的误差必在 (1 − u) n 与 (1 + u) n 之间。由于 x 2 i 均为正，最大误差在同取 + 或 − 时，因此即有 fl(x T x) xT x ∈ [(1 − u) n ,(1 + u) n ]，于是 α ≤ nu + O(u 2 )。 18. 类似第一章习题 18 可说明 L 与 U 均为带宽为 2 的带状矩阵，利用习题 10 等式，当 A 为三对角阵时，由于其他项都为 0，有 u T i = a T i −li,i−1u T i−1 , i ≥ 2，从而由 |lij | ≤ 1 可知 |a1j | ≥ |u1j |, |aij |+|ui−1,j | ≥ |uij |, i ≥ 2。由于 U 为带宽 2 的上三角阵，当且仅当 i = j −1 或 j 时 uij ̸= 0，从而 |uj−1,j | ≤ |aj−1,j |+|uj−2,j | = |aj−1,j |, |uii| ≤ |aii| + |ui−1,i| ≤ |ai−1,i| + |aii|，因此 U 中任何元素不超过 2 maxi,j |aij |，从而得证。 19. 利用习题 10 等式可知 aij − uij = Pi−1 k=1 likukj，第一章习题 15 已说明每一步分解中 A 的右下角子矩阵为列对角占优，因此 Pi−1 k=1 |lik| < 1，于是 |uij | ≤ |aij | + maxk<i |ukj |。对上式归纳，|u1j | ≤ |a1j |，此后每次最大值最多增加 |aij |，因此 i ≤ j 时 |uij | ≤ Pi k=1 |akj | ≤ Pj k=1 |akj | ≤ 2|ajj |，而由于其为上三角阵，i < j 时恒为 0，从而 ρ ≤ 2。 20. 由算法过程可以发现，由于每个元素所在的行列最多还有 m 个其他元素，计算 L, U 的过程中每个元素至多产生 m 次减法、m 次乘法与 1 次除法的误差，由定理 2.3.3 可知每个元素的误差至多为 (2m + 1)u + O(u 2 )，而计算回 A 的部分需要 m 次乘法与 m − 1 次加法，类似得最终误差为 (2m − 1)(2m + 1)u + O(u 2 )，当 u 较小时以 4m2u 为上界，m = 3 时即为 36u。 21. 由算法过程可以发现，计算 L 的过程中每个元素至多产生 n 次减法、n 次乘法与 1 次除法或开方的误差，而计算回 A 得过程中最多需要 n 次乘法与 n − 1 次加法，类似习题 20 知最终误差为 Q4n 2−1 i=1 (1 + δi)，类似引理 2.4.1 计算方法可知条件下误差可以用 4.09n 2u 控制

第三章最小二乘问题的解法第三章最小二乘问题的解法 1c-(▣)a-(0)w(6) /6311 3933 3 2.C 可发现C的零化子空间一组基为 1311 1311 3/5 特解为0 2/15 ，由此通解为x0+au+bu,a,b∈R。 0 0 3.由乘正交阵不改变二范数可知变换前后二范数必然相同，从而a=5。由定义设H=1-2wwT, 可知2ww(1,0,4,6,3,4)F=(0,-5,0,0,3,4),也即2(1,0,4,6,3,4)Tw=(0,-5,0,0,3,4),可得 w=号(0，-5,0,0,3,4). 4.即5c+12s=-5s+12c,有17s=7,解得s=12,c=2,此时a=132。 -aa+bb+b2c=0 5.即-s1+c2=0,设8=a+bi,=a十bi可知。若=0，取 -b1a-a1b+a2c=0 s=1,c=0即可，否则方程组中a,b线性无关，可令c=1得到此方程的特解，再对模长进行归一化（三个分量同时除以模长）即可。 6.当，≠0时，类似习5解方程可构造二阶Gs方阵Q使得Q的第二个分量为0，记其度为0，则a,4在向量a的第i,j行时，计算知Q(,j,0)a可使4=0，且不影响i,j外的其他行于是得到算法：对x除第一行外的每一行，若为0则跳过，否则找到对应将其置为0的Q(1,,9) 同理，对y除第一行外的每一行找到P1,k,),则T=nP(1,k,-)Π=，Q(1,方，)即为所求。证明：记Q=I1Q(1,i,9,),P=1P(1,k,k小，则根据构造过程可知Qx=Py=e1,而每个 Givens方阵的逆为其转置，也即将0变为-0，于是P的逆为T=nP(1,k,-0s),即有P-1Qx=y: 7.类似习题3，先计算a-,设H为1-2w7,可发现2(wx)w=x-a,从而先令o=ay-工，再计算w=高即可得到H。 8.思路事实上与定理3.3.1完全一致，只是改变操作顺序与边的序号。归纳构造： H.操作前，后k-1列已符合要求，而H.将倒数第k列(0，.，0，an-k+1,,an,4n+1,,an)T变为(0...0.0.0m4 ,.0.,.,.0)T。这样得到的只有第n-k+1与后m一n个分量非零，而后k-1列这些分量都是0，因此利用x,w非零分量不重合时(1-2)x=x-2(ux)w= 可知不会破坏己符合婴求的部分，从而成立。 9.由定理31.4知只需求解LTLz=LTP%,由于L为单位下三角，其列满秩，于是LTL2=LTP% 有唯解。将其分解为口（白）后，计算发现即为求解以：=P%,而这可以直接适过求解 L?0=LTP%与L12=0两个方程得到解。当Ux=z时，由于z满足LTLz=LTP%,代入知LTLUx=LTPb,于是UTLTLUx=UTLT Pb,. 即ATAr=ATPb,由定理3.1.4可知结论

第三章最小二乘问题的解法 7 第三章最小二乘问题的解法 1. C = 35 44 44 56! , d = 9 12! ，解为 −1 1 ! 。 2. C =   6 3 1 1 3 9 3 3 1 3 1 1 1 3 1 1   , d =   4 3 1 1   ，可发现 C 的零化子空间一组基为 u =   0 −1 0 3   , v =   0 0 1 −1   ，而一个特解为 x0 =   3/5 2/15 0 0   ，由此通解为 x0 + au + bv, a, b ∈ R。 3. 由乘正交阵不改变二范数可知变换前后二范数必然相同，从而 α = 5。由定义设 H = I − 2wwT，可知 2wwT (1, 0, 4, 6, 3, 4)T = (0, −5, 0, 0, 3, 4)，也即 2w T (1, 0, 4, 6, 3, 4)T w = (0, −5, 0, 0, 3, 4)，可得 w = √ 2 10 (0, −5, 0, 0, 3, 4)。 4. 即 5c + 12s = −5s + 12c，有 17s = 7c，解得 s = 7 √ 2 26 , c = 17√ 2 26 ，此时 α = 13√ 2 2 。 5. 即 −sx1 + cx2 = 0，设 s = a + bi, xi = ai + bi i 可知    −a1a + b1b + b2c = 0 −b1a − a1b + a2c = 0 。若 |x1| = 0，取 s = 1, c = 0 即可，否则方程组中 a, b 线性无关，可令 c = 1 得到此方程的特解，再对模长进行归一化 (三个分量同时除以模长) 即可。 6. 当 aj ̸= 0 时，类似习题 5 解方程可构造二阶 Givens 方阵 Q 使得 Q ai aj ! 的第二个分量为 0，记其角度为 θ，则 ai , aj 在向量 α 的第 i, j 行时，计算知 Q(i, j, θ)α 可使 aj = 0，且不影响 i, j 外的其他行。于是得到算法：对 x 除第一行外的每一行，若为 0 则跳过，否则找到对应将其置为 0 的 Q(1, j, θj )。同理，对 y 除第一行外的每一行找到 P(1, k, θk)，则 Q1 k=n P(1, k, −θk) Qn j=1 Q(1, j, θj ) 即为所求。证明：记 Q = Qn j=1 Q(1, j, θj )，P = Qn k=1 P(1, k, θk)，则根据构造过程可知 Qx = P y = e1，而每个 Givens 方阵的逆为其转置，也即将 θ 变为 −θ，于是 P 的逆为 Q1 k=n P(1, k, −θk)，即有 P −1Qx = y。 7. 类似习题 3，先计算 α = ∥x∥2 ∥y∥2 ，设 H 为 I −2wwT，可发现 2(w T x)w = x−αy，从而先令 w0 = αy−x，再计算 w = w0 ∥w0∥2 即可得到 H。 8. 思路事实上与定理 3.3.1 完全一致，只是改变操作顺序与边的序号。归纳构造： Hk 操作前，后 k −1 列已符合要求，而 Hk 将倒数第 k 列 (0, . . . , 0, an−k+1, . . . , an, an+1, . . . , am) T 变为 (0, . . . , 0, α, an−k+2, . . . , an, 0, . . . , 0)T。这样得到的 wk 只有第 n − k + 1 与后 m − n 个分量非零，而后 k − 1 列这些分量都是 0，因此利用 x, w 非零分量不重合时 (I − 2wwT )x = x − 2(w T x)w = x 可知不会破坏已符合要求的部分，从而成立。 9. 由定理 3.1.4 知只需求解 L TLz = L T P b，由于 L 为单位下三角，其列满秩，于是 L TLz = L T P b 有唯一解。将其分解为 H L1 O ! 后，计算发现即为求解 L T 1 L1z = L T P b，而这可以直接通过求解 L T 1 z0 = L T P b 与 L1z = z0 两个方程得到解。当 Ux = z 时，由于 z 满足 L TLz = L T P b，代入知 L TLUx = L T P b，于是 U TL TLUx = U TL T P b，即 AT Ax = AT P b，由定理 3.1.4 可知结论

第四章线性方程组的古典迭代解法 8 10. 由定理 3.1.4 可知 AT AXb = AT b 对任何 b 成立，取 b 为 ei 并拼接可知 AT AXI = AT I，从而 AT AX = AT，同取转置有 XT AT A = A。在 AT AX = AT 两边同时左乘 XT 可知 AX = XT AT AX = XT AT = (AX) T，从而得证第二个式子，而 A = XT AT A = (AX) T A = AXA，从而得证第一个式子。 11. 定义 Givens 函数 g(a, b) = arccos a √ a 2 + b 2 ，用于生成左乘 (a, b) T 使 b 成为 0 的 θ，下文 I 为单位阵，G(i, j, θ) 与书上定义相同，乘法为矩阵乘法： def QR(A, Q): Q = I for i = n downto 3 if (A[i][1] != 0) Q = Q * G(i‐1,i,‐g(A[i‐1][1],A[i][1])) A = G(i‐1,i,g(A[i‐1][1],A[i][1])) * A for i = 2 to n if (A[i][i‐1] != 0) Q = Q * G(i‐1,i,‐g(A[i‐1][i‐1],A[i][i‐1])) A = G(i‐1,i,g(A[i‐1][i‐1],A[i][i‐1])) * A 算法分为两步，第一步自下而上第一列的每个元素与上面的元素合并 (只要为 0 则跳过)，这样合并后，每次合并过程可能让下三角部分的 ai,i−1 变为非 0，但其他元素不会受影响。于是，完全合并后，矩阵除了上三角部分，至多还有 ai,i−1 一条对角线非零。第二步针对这条对角线再用 Givens 方阵操作，可发现此时不会再影响下三角部分，因此最多通过 (n − 1) + (n − 2) = 2n − 3 个 Givens 方阵即可实现上三角化，再对应计算 Q 即可。 12. 等式的证明：直接利用 ∥x∥ 2 2 = x T x 展开计算可发现成立。当 ∥Ax−b∥2 为最小时，任意 ∥A(x+αw)−b∥2 ≥ ∥Ax−b∥2，于是 2αwT AT (Ax−b)+α 2∥Aw∥ 2 ≥ 0 对任何 α, w 成立。由于 α 与 w 同时取相反数不影响结果，可不妨设 α > 0，此时即需要 2w T AT (Ax − b) + α∥Aw∥ 2 ≥ 0 恒成立。若 AT (Ax − b) ̸= 0，假设其第 i 个分量不为 0，可取合适的 w ∈ {±ei}，使 2w T AT (Ax − b) < 0，再令 α → 0 即有矛盾。于是，必须 AT (Ax − b) = 0，即 AT Ax = AT b。第四章线性方程组的古典迭代解法 1. A1 在 Jacobi 迭代法迭代矩阵是   0 1/2 −1/2 −1 0 −1 1/2 1/2 0   ，谱半径为 √ 5 2 ，不收敛；而 G-S 迭代法迭代矩阵是   0 1/2 −1/2 0 −1/2 −1/2 0 0 −1/2   ，谱半径为 1 2，收敛

第四章钱性方程组的古典迭代解法 0-22 A2在Jacobi选代法迭代矩阵是谱半径为0，收敛：而G-S迭代法迭代矩阵是 0-22 02-3 谱半径为2，不收敛 002 2.由谱半径可知B特征值全为0，考虑Jordan标准型可发现必有Bm=O,而m=Bmxo十Bm-1g+ +Bg+9 由Bm=0知xn=(Bm-1+ ,+)g,进一步计算可发现Bn十g仍为xn,也就是此即为精确解且此后不再变化。 3.(1)也即x+号+x+2az1r3>0对非零向量恒成立成立，a∈(-1,1)时配方知满足要求，否则 ==1,x2=0得矛盾。于是结论为a∈(-1,1)： 00-a (②)Jacobi法代法迭代矩阵是 000 ,特征值为0，-，a,收敛需谱半径小于1，即ae(-1,1) -a00 00-a (3)G-S迭代法迭代矩阵是 000 ,特征值为0,0，a2,收敛需谱半径小于1，即a∈(-1,1)。 00a2 4.先证明：可以找到排列方阵P使得PA左上角元素非零，右下角n一1阶子矩阵非奇异。考虑Laplace展开det(A)=∑：aa(-l)+1det(A),其中A为去掉a,所在行列的子矩阵。由于行列式非零，右边至少有一项非零，不妨设为t,则a1与dt(A)均非零，取P为交换1与t的置换阵即可验证成立。于是，通过归纳，一阶时成立，假设n一1阶时成立，n阶时先取出如上的乃，再对右下角取出符 10 合要求的Q,令P=(0QB即可。 5.利用定理424，只需说明B、<1,面∑：=兴1=<1，于是其对：取最大值也小于1，从而得证。 6.归纳，一阶时可直接说明成立，若n-1阶时成立，下证n阶成立。记m4=a-∑a, 利用第一章习8的证明过程中的小于号步骤，经过一步高斯消去，剩下的A2乘11后的对角元 a11ak-a1k41减去∑=2a1a与-a1yal至少为aa-∑j=l#la11a财l=mka于是除以a1l后得其至少为mk 于是，|det(Al=anldet(A2川≥laulITR_2mk≥I=1mk。 *归纳可发现这题的界可以作较大改进 7.由于b不影响收敛性，不妨设其为0，则有工n+1=(D-L)1LTxn,于是(D-L)xn+1=LTxn。两边同左乘与+，利用xTA=TATt分解为L,D计算可发现 x+1An+1-An=-(n-xn+i)TD(n-xn+i)≤0 于是若A不正定，存在非零x使xAx≤0。若某次选代中x与x+1不同，则由D正定知 +1A红+1-A加n<0,于是x+1A加n+1<0,此后不增，不可能收敛到解。否则，工一直不变，由非零亦不是解，从而矛盾

第四章线性方程组的古典迭代解法 9 A2 在 Jacobi 迭代法迭代矩阵是   0 −2 2 −1 0 −1 −2 −2 0   ，谱半径为 0，收敛；而 G-S 迭代法迭代矩阵是   0 −2 2 0 2 −3 0 0 2   ，谱半径为 2，不收敛。 2. 由谱半径可知 B 特征值全为 0，考虑 Jordan 标准型可发现必有 Bn = O，而 xn = Bnx0 + Bn−1 g + · · · + Bg + g，由 Bn = O 知 xn = (Bn−1 + · · · + I)g，进一步计算可发现 Bxn + g 仍为 xn，也就是此即为精确解且此后不再变化。 3. (1) 也即 x 2 1 + x 2 2 + x 2 3 + 2ax1x3 > 0 对非零向量恒成立成立，a ∈ (−1, 1) 时配方知满足要求，否则令 x1 = x3 = 1, x2 = 0 得矛盾。于是结论为 a ∈ (−1, 1)。 (2) Jacobi 迭代法迭代矩阵是   0 0 −a 0 0 0 −a 0 0   ，特征值为 0, −a, a，收敛需谱半径小于 1，即 a ∈ (−1, 1)。 (3) G-S 迭代法迭代矩阵是   0 0 −a 0 0 0 0 0 a 2   ，特征值为 0, 0, a2，收敛需谱半径小于 1，即 a ∈ (−1, 1)。 4. 先证明：可以找到排列方阵 P 使得 P A 左上角元素非零，右下角 n − 1 阶子矩阵非奇异。考虑 Laplace 展开 det(A) = P i ai1(−1)i+1 det(Ai1)，其中 Aij 为去掉 aij 所在行列的子矩阵。由于行列式非零，右边至少有一项非零，不妨设为 t，则 at1 与 det(At1) 均非零，取 P 为交换 1 与 t 的置换阵即可验证成立。于是，通过归纳，一阶时成立，假设 n − 1 阶时成立，n 阶时先取出如上的 P0，再对右下角取出符合要求的 Q，令 P = 1 0 0 Q ! P0 即可。 5. 利用定理 4.2.4，只需说明 ∥B∥∞ < 1，而 Pn j=1 |bij | = P j̸=i aij aii = ∑ j̸=i |aij | |aii| < 1，于是其对 i 取最大值也小于 1，从而得证。 6. 归纳，一阶时可直接说明成立，若 n − 1 阶时成立，下证 n 阶成立。记 mi = |aii| − P j̸=i aij 利用第一章习题 8 的证明过程中的小于号步骤，经过一步高斯消去，剩下的 A2 乘 a11 后的对角元 |a11akk − a1kak1| 减去 Pn j=2,j̸=k |a11akj − a1jak1| 至少为 |a11akk| − Pn j=1,j̸=k |a11akj | = mk|a11|，于是除以 |a11| 后得其至少为 mk。于是，| det(A)| = |a11|| det(A2)| ≥ |a11| Qn k=2 mk ≥ Qn k=1 mk。 * 归纳可发现这题的界可以作较大改进 7. 由于 b 不影响收敛性，不妨设其为 0，则有 xn+1 = (D − L) −1L T xn，于是 (D − L)xn+1 = L T xn。两边同左乘 x T n 与 x T n+1，利用 x T Ax = x T AT x 分解为 L, D 计算可发现 x T n+1Axn+1 − x T nAxn = −(xn − xn+1) T D(xn − xn+1) ≤ 0 于是若 A 不正定，存在非零 x 使 x T Ax ≤ 0。若某次迭代中 xn 与 xn+1 不同，则由 D 正定知 x T n+1Axn+1 − x T nAxn < 0，于是 x T n+1Axn+1 < 0，此后不增，不可能收敛到解。否则，x 一直不变，由非零亦不是解，从而矛盾

第四章线性方程组的古典选代解法 10 8.若不收敛，则p(H)≥1，即有A使得H=a入la≥1，则计算知AHB入=(1-la)AHPA。记入=a+i可发现正定阵对任何复向量入仍有XP以>0，AB入>0，于是矛盾。 9.w=1时，计算发现即为Jacobi达代矩阵，也即要证，当p(I-C)<1时，p(I-wC)<1,w∈(0,1) 若否，有(I-wC)入=a入，ll≥1，于是(I-C)入=(+1)X。记c=,乘共轭计算此特征值的模长平方为 c2la2+(e-12-2c-1)cRe(a)≥c2la+(c-1)2-2e-1)d4al=(dal-)+122laP21 从而矛盾。 10.与定理4.2.6类似，由于 I-B=D-1/2w-1D)-1/Au-1D)-1/PD2 I+B=D-/P(2I-(-1D-1/PAw-1D)-2)Dp 特征值均为正实数，因此(u-1D)-1/2A(u-1D)1/2,2I-(u-1D)-1/2A(u-1D)-1/2正定对称，从而相合得结论。 1山.直接计算可得 XI-L =(D-wL)-((A+w-1)D-XwL-wU) 类似定理4.29，只需说明≥1时(A+w-1)D-wL-wU严格对角占优或不可约对角占优。同除以w得（二+1）D-AL-U,由习题9证明过程知二+1模长大于等于X,从而严格对角占优或不可约对角占优性仍保持，即得证。 12.非对角线非零元素为12,13,21,24,31,34,42,43，分为S1-{,S2={2,3,S={4即可。 13.(a)直接计算a1=V反，而考虑到-1可知a+1-一立，利用第一章习题18可知除了a与a+1 外的元素均为0，因此只需要考虑a4:的递推。由T的对角线为2，有+1i+1十+1：=2，因此a+1+1=2-之，解得a=√中，于是a+1a=-√告。 (仙)与上方类似，递推可得L为L=1,L+14=-本，U为U:=中，U41=-1. (©)由于T的特征值互不相同，其特征向量能张成全空间，即特征向量作为列构成的矩阵P可逆。而TP=PD,其中D为特征值排列为的对角阵，于是T=PDP-1,由条件，D,P均已知。原方程化为PDP-U+UPDP-1=hF,记=P-1UP,则DU+UD=h2P-FP. 按如下步骤求解：先计算P-1,复杂度n3,然后计算P-1FP,矩阵乘法复杂度可不超过n3。而注意到D为对角阵，DU%+U%D可直接逐元素求解，于是解DU%+UoD=h2P-1FP的复杂度为m2,最后计算U=PP-1,复杂度n3,最终复杂度O(n3) 14.先说明8=2时的情况，由于对两边取行列式可知t(）=d(D 0 ,当B和C2同乘的系数为1 B2 D2 D2-B2DiC2 时不影响。 10 若s=k时成立，考虑s=k+1时，左乘 0,右乘01-DC O-HB.D I 00 可以使右下角元素变为D。-B,DC。,C,D,部分变为O,而左上部分不变，于是det(A)= det(A,-)det(D.-B,DC.),利用归纳假设知与μ无关

第四章线性方程组的古典迭代解法 10 8. 若不收敛，则 ρ(H) ≥ 1，即有 λ 使得 λH = αλ, |α| ≥ 1，则计算知 λ HBλ = (1 − |α| 2 )λ HP λ。记 λ = a + bi 可发现正定阵对任何复向量 λ 仍有 λ HP λ > 0, λHBλ > 0，于是矛盾。 9. ω = 1 时，计算发现即为 Jacobi 迭代矩阵，也即要证，当 ρ(I −C) < 1 时，ρ(I −ωC) < 1, ω ∈ (0, 1)。若否，有 (I − ωC)λ = αλ, |α| ≥ 1，于是 (I − C)λ = α−1 ω + 1 λ。记 c = 1 ω，乘共轭计算此特征值的模长平方为 c 2 |α| 2 + (c − 1)2 − 2(c − 1)c Re(α) ≥ c 2 |α| 2 + (c − 1)2 − 2(c − 1)c|α| = (c(|α| − 1) + 1)2 ≥ |α| 2 ≥ 1 从而矛盾。 10. 与定理 4.2.6 类似，由于 I − B = D−1/2(ω −1D) −1/2A(ω −1D) −1/2D1/2 I + B = D−1/2 2I − (ω −1D) −1/2A(ω −1D) −1/2 D1/2 特征值均为正实数，因此 (ω −1D) −1/2A(ω −1D) −1/2 , 2I − (ω −1D) −1/2A(ω −1D) −1/2 正定对称，从而相合得结论。 11. 直接计算可得 λI − Lω = (D − ωL) −1 ((λ + ω − 1)D − λωL − ωU) 类似定理 4.2.9，只需说明 |λ| ≥ 1 时 (λ + ω − 1)D − λωL − ωU 严格对角占优或不可约对角占优。同除以 ω 得 ( λ−1 ω + 1)D − λL − U，由习题 9 证明过程知 λ−1 ω + 1 模长大于等于 λ，从而严格对角占优或不可约对角占优性仍保持，即得证。 12. 非对角线非零元素为 12, 13, 21, 24, 31, 34, 42, 43，分为 S1 = {1}, S2 = {2, 3}, S3 = {4} 即可。 13. (a) 直接计算 a11 = √ 2，而考虑到 −1 可知 ai+1,i = − 1 aii，利用第一章习题 18 可知除了 aii 与 ai+1,i 外的元素均为 0，因此只需要考虑 aii 的递推。由 Tn 的对角线为 2，有 a 2 i+1,i+1 + a 2 i+1,i = 2，因此 a 2 i+1,i+1 = 2 − 1 a 2 ii ，解得 aii = q i+1 i ，于是 ai+1,i = − q i i+1。 (b) 与上方类似，递推可得 L 为 Lii = 1, Li+1,i = − i i+1，U 为 Uii = i+1 i , Ui,i+1 = −1。 (c) 由于 T 的特征值互不相同，其特征向量能张成全空间，即特征向量作为列构成的矩阵 P 可逆。而 T P = P D，其中 D 为特征值排列为的对角阵，于是 T = P DP −1，由条件，D, P 均已知。原方程化为 P DP −1U + UP DP −1 = h 2F，记 U0 = P −1UP，则 DU0 + U0D = h 2P −1F P。按如下步骤求解：先计算 P −1，复杂度 n 3，然后计算 P −1F P，矩阵乘法复杂度可不超过 n 3。而注意到 D 为对角阵，DU0 + U0D 可直接逐元素求解，于是解 DU0 + U0D = h 2P −1F P 的复杂度为 n 2，最后计算 U = P U0P −1，复杂度 n 3，最终复杂度 O(n 3 )。 14. 先说明 s = 2 时的情况，由于 D1 C2 B2 D2 ! = I O B2D −1 1 I ! D1 O O D2 − B2D −1 1 C2 ! I D−1 1 C2 O I ! 对两边取行列式可知 det D1 C2 B2 D2 ! = det D1 O O D2 − B2D −1 1 C2 ! ，当 B2 和 C2 同乘的系数为 1 时不影响。若 s = k 时成立，考虑 s = k + 1 时，左乘   I O O O I O O −µBsD −1 s−1 I   ，右乘   I O O O I − 1 µ D −1 s−1Cs O O I   可以使右下角元素变为 Ds − BsD −1 s−1Cs，Cs, Ds 部分变为 O，而左上部分不变，于是 det(A) = det(As−1) det(Ds − BsD −1 s−1Cs)，利用归纳假设知与 µ 无关