题目

26、证明/计算/分析题（5分）利用Doolittle分解，Cholesky方法和三对角追赶法三种方法求解线性方程组}4&1&01&5&20&2&8

26、证明/计算/分析题（5分） 利用Doolittle分解，Cholesky方法和三对角追赶法三种方法求解线性方程组 $\begin{pmatrix}4&1&0\\1&5&2\\0&2&8\end{pmatrix}\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\end{pmatrix}=\begin{pmatrix}5\\8\\10\end{pmatrix}$

题目解答

答案

解题思路

本题要求利用三种不同的矩阵分解方法（Doolittle 分解、Cholesky 方法、三对角追赶法）求解同一个线性方程组。
给定的方程组为 $Ax = b$，其中系数矩阵 $A$ 为：
$A = \begin{pmatrix} 4 & 1 & 0 \\ 1 & 5 & 2 \\ 0 & 2 & 8 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \\ 8 \\ 10 \end{pmatrix}$
观察矩阵 $A$ 的特点：

  1. 它是一个对称矩阵（$a_{ij} = a_{ji}$），且各阶顺序主子式均大于零，因此是正定矩阵，适合使用 Cholesky 方法。
  2. 它是一个三对角矩阵（非零元素仅分布在主对角线及其相邻的上下两条对角线上），因此适合使用 三对角追赶法（也称 Thomas 算法）。
  3. 对于一般方阵，可以使用 Doolittle 分解（即 $LU$ 分解，其中 $L$ 为单位下三角矩阵，$U$ 为上三角矩阵）。

我们将分别对这三种方法进行推导和求解。

核心解题步骤

1. 利用 Doolittle 分解法求解

Doolittle 分解法将矩阵 $A$ 分解为一个单位下三角矩阵 $L$ 和一个上三角矩阵 $U$ 的乘积，即 $A = LU$。
设：
$L = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix}, \quad U = \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{pmatrix}$
通过比较 $A = LU$ 的对应元素，按列和行的顺序计算：

  • 计算 $U$ 的第一行和 $L$ 的第一列：
    $u_{11} = a_{11} = 4$
    $u_{12} = a_{12} = 1$
    $u_{13} = a_{13} = 0$
    $l_{21} = \frac{a_{21}}{u_{11}} = \frac{1}{4}$
    $l_{31} = \frac{a_{31}}{u_{11}} = \frac{0}{4} = 0$

  • 计算 $U$ 的第二行和 $L$ 的第二列：
    $u_{22} = a_{22} - l_{21}u_{12} = 5 - \frac{1}{4} \times 1 = \frac{19}{4}$
    $u_{23} = a_{23} - l_{21}u_{13} = 2 - \frac{1}{4} \times 0 = 2$
    $l_{32} = \frac{a_{32} - l_{31}u_{12}}{u_{22}} = \frac{2 - 0 \times 1}{\frac{19}{4}} = \frac{8}{19}$

  • 计算 $U$ 的第三行：
    $u_{33} = a_{33} - l_{31}u_{13} - l_{32}u_{23} = 8 - 0 \times 0 - \frac{8}{19} \times 2 = 8 - \frac{16}{19} = \frac{136}{19}$

得到分解结果：
$L = \begin{pmatrix} 1 & 0 & 0 \\ \frac{1}{4} & 1 & 0 \\ 0 & \frac{8}{19} & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 4 & 1 & 0 \\ 0 & \frac{19}{4} & 2 \\ 0 & 0 & \frac{136}{19} \end{pmatrix}$

求解 $Ax = b \implies LUx = b$。
先解 $Ly = b$（向前代入）：
$\begin{pmatrix} 1 & 0 & 0 \\ \frac{1}{4} & 1 & 0 \\ 0 & \frac{8}{19} & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 8 \\ 10 \end{pmatrix}$

  • $y_1 = 5$
  • $\frac{1}{4}y_1 + y_2 = 8 \implies \frac{5}{4} + y_2 = 8 \implies y_2 = \frac{27}{4}$
  • $\frac{8}{19}y_2 + y_3 = 10 \implies \frac{8}{19} \times \frac{27}{4} + y_3 = 10 \implies \frac{54}{19} + y_3 = 10 \implies y_3 = \frac{136}{19}$

再解 $Ux = y$（向后代入）：
$\begin{pmatrix} 4 & 1 & 0 \\ 0 & \frac{19}{4} & 2 \\ 0 & 0 & \frac{136}{19} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ \frac{27}{4} \\ \frac{136}{19} \end{pmatrix}$

  • $\frac{136}{19}x_3 = \frac{136}{19} \implies x_3 = 1$
  • $\frac{19}{4}x_2 + 2x_3 = \frac{27}{4} \implies \frac{19}{4}x_2 + 2 = \frac{27}{4} \implies \frac{19}{4}x_2 = \frac{19}{4} \implies x_2 = 1$
  • $4x_1 + x_2 = 5 \implies 4x_1 + 1 = 5 \implies 4x_1 = 4 \implies x_1 = 1$

2. 利用 Cholesky 方法求解

Cholesky 分解适用于对称正定矩阵，将 $A$ 分解为 $A = GG^T$，其中 $G$ 是下三角矩阵。
设 $G = \begin{pmatrix} g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ g_{31} & g_{32} & g_{33} \end{pmatrix}$。

  • $g_{11} = \sqrt{a_{11}} = \sqrt{4} = 2$
  • $g_{21} = \frac{a_{21}}{g_{11}} = \frac{1}{2}$
  • $g_{31} = \frac{a_{31}}{g_{11}} = 0$
  • $g_{22} = \sqrt{a_{22} - g_{21}^2} = \sqrt{5 - (\frac{1}{2})^2} = \sqrt{\frac{19}{4}} = \frac{\sqrt{19}}{2}$
  • $g_{32} = \frac{a_{32} - g_{31}g_{21}}{g_{22}} = \frac{2 - 0}{\frac{\sqrt{19}}{2}} = \frac{4}{\sqrt{19}}$
  • $g_{33} = \sqrt{a_{33} - g_{31}^2 - g_{32}^2} = \sqrt{8 - 0 - (\frac{4}{\sqrt{19}})^2} = \sqrt{8 - \frac{16}{19}} = \sqrt{\frac{136}{19}}$

求解 $Gy = b$ 和 $G^T x = y$。

  • $Gy = b \implies 2y_1 = 5 \implies y_1 = \frac{5}{2}$；$\frac{1}{2}y_1 + \frac{\sqrt{19}}{2}y_2 = 8 \implies y_2 = \frac{27}{2\sqrt{19}}$；$\frac{4}{\sqrt{19}}y_2 + \sqrt{\frac{136}{19}}y_3 = 10 \implies y_3 = \frac{136}{19\sqrt{\frac{136}{19}}} = \sqrt{\frac{136}{19}}$
  • $G^T x = y$ 向后代入，同理可求得 $x_1 = 1, x_2 = 1, x_3 = 1$。

3. 利用三对角追赶法求解

三对角矩阵 $A$ 可以表示为：
$\begin{pmatrix} b_1 & c_1 & 0 \\ a_2 & b_2 & c_2 \\ 0 & a_3 & b_3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \end{pmatrix}$
对应本题数据：
$b_1=4, c_1=1$；$a_2=1, b_2=5, c_2=2$；$a_3=2, b_3=8$；$d_1=5, d_2=8, d_3=10$。

追（向前消元）：

  • $\beta_1 = b_1 = 4, \gamma_1 = d_1 = 5$
  • $\beta_2 = b_2 - a_2 \frac{\beta_1}{\beta_1} = 5 - 1 \times \frac{1}{4} = \frac{19}{4}$
  • $\gamma_2 = d_2 - a_2 \frac{\gamma_1}{\beta_1} = 8 - 1 \times \frac{5}{4} = \frac{27}{4}$
  • $\beta_3 = b_3 - a_3 \frac{\beta_2}{\beta_2} = 8 - 2 \times \frac{2}{\frac{19}{4}} = 8 - \frac{16}{19} = \frac{136}{19}$
  • $\gamma_3 = d_3 - a_3 \frac{\gamma_2}{\beta_2} = 10 - 2 \times \frac{\frac{27}{4}}{\frac{19}{4}} = 10 - \frac{54}{19} = \frac{136}{19}$

赶（向后回代）：

  • $x_3 = \frac{\gamma_3}{\beta_3} = \frac{\frac{136}{19}}{\frac{136}{19}} = 1$
  • $x_2 = \frac{\gamma_2 - c_2 x_3}{\beta_2} = \frac{\frac{27}{4} - 2 \times 1}{\frac{19}{4}} = \frac{\frac{19}{4}}{\frac{19}{4}} = 1$
  • $x_1 = \frac{\gamma_1 - c_1 x_2}{\beta_1} = \frac{5 - 1 \times 1}{4} = 1$

标准答案

解：

利用 Doolittle 分解、Cholesky 方法以及三对角追赶法，求解该线性方程组的步骤与结果如下：

  1. Doolittle 分解法：
    将系数矩阵 $A$ 分解为单位下三角矩阵 $L$ 与上三角矩阵 $U$ 的乘积，即 $A=LU$。
    求得 $L = \begin{pmatrix} 1 & 0 & 0 \\ \frac{1}{4} & 1 & 0 \\ 0 & \frac{8}{19} & 1 \end{pmatrix}$，$U = \begin{pmatrix} 4 & 1 & 0 \\ 0 & \frac{19}{4} & 2 \\ 0 & 0 & \frac{136}{19} \end{pmatrix}$。
    通过解 $Ly = b$ 和 $Ux = y$，可得方程组的解为：
    $\mathbf{x_1 = 1, \quad x_2 = 1, \quad x_3 = 1}$

  2. Cholesky 方法：
    因 $A$ 为对称正定矩阵，可将其分解为 $A=GG^T$（$G$ 为下三角矩阵）。
    求得下三角矩阵 $G = \begin{pmatrix} 2 & 0 & 0 \\ \frac{1}{2} & \frac{\sqrt{19}}{2} & 0 \\ 0 & \frac{4}{\sqrt{19}} & \sqrt{\frac{136}{19}} \end{pmatrix}$。
    依次求解 $Gy = b$ 和 $G^T x = y$，同样可得方程组的解为：
    $\mathbf{x_1 = 1, \quad x_2 = 1, \quad x_3 = 1}$

  3. 三对角追赶法：
    针对三对角矩阵，采用追赶法（Thomas 算法）进行求解。
    通过向前“追”的过程，计算中间系数 $\beta_i, \gamma_i$；再通过向后“赶”的过程，回代求解 $x_i$。
    最终求得方程组的解为：
    $\mathbf{x_1 = 1, \quad x_2 = 1, \quad x_3 = 1}$

答：利用上述三种方法求解，该线性方程组的解均为 $\mathbf{x_1 = 1, x_2 = 1, x_3 = 1}$。