QR分解在求解线性方程组中的应用

题目描述：
我们考虑求解一个线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是一个 \(n \times n\) 的可逆方阵，\(\mathbf{b}\) 是已知的 \(n\) 维向量，\(\mathbf{x}\) 是未知向量。要求利用QR分解法求解这个方程组，并详细说明其原理、计算步骤和数值特性。

解题过程：

1. 核心思想：
   QR分解法的基本思路是将系数矩阵 \(A\) 分解为一个正交矩阵 \(Q\) 和一个上三角矩阵 \(R\) 的乘积，即 \(A = QR\)。然后利用正交矩阵的性质（\(Q^{-1} = Q^T\)）和上三角矩阵易于求解的特性，将原方程组转化为一个容易求解的三角方程组。

2. 第一步：对矩阵 \(A\) 进行QR分解：

   • 目标：找到正交矩阵 \(Q\)（满足 \(Q^T Q = I\)，其中 \(I\) 是单位阵）和上三角矩阵 \(R\)，使得 \(A = QR\)。
   • 常用方法：Householder变换或Givens旋转。这里以Householder变换为例简述过程：
     a. 令 \(A^{(0)} = A\)。
     b. 对 \(k = 1\) 到 \(n\)，构造Householder反射矩阵 \(H_k\)，使得它将 \(A^{(k-1)}\) 的第 \(k\) 列中主对角元以下的所有元素变为零。
     c. 计算 \(A^{(k)} = H_k A^{(k-1)}\)，最终得到上三角矩阵 \(R = A^{(n)}\)，且正交矩阵 \(Q = H_1^T H_2^T \cdots H_n^T\)。
   • 结果：得到分解 \(A = QR\)，其中 \(R\) 是上三角矩阵，\(Q\) 是正交矩阵。

3. 第二步：将原方程组转化为三角方程组：

   • 将 \(A = QR\) 代入 \(A\mathbf{x} = \mathbf{b}\)，得到 \(QR\mathbf{x} = \mathbf{b}\)。
   • 由于 \(Q\) 是正交矩阵，在等式两边同时左乘 \(Q^T\)，利用 \(Q^T Q = I\)，得到：

\[ R\mathbf{x} = Q^T \mathbf{b} \]

• 记 \(\mathbf{c} = Q^T \mathbf{b}\)，则原方程简化为：

\[ R\mathbf{x} = \mathbf{c} \]

 其中 $R$ 是上三角矩阵，$\mathbf{c}$ 是已知向量。

6. 第三步：回代法求解上三角方程组：
   • 上三角方程组 \(R\mathbf{x} = \mathbf{c}\) 的形式为：

\[ \begin{cases} r_{11}x_1 + r_{12}x_2 + \cdots + r_{1n}x_n = c_1 \\ r_{22}x_2 + \cdots + r_{2n}x_n = c_2 \\ \vdots \\ r_{nn}x_n = c_n \end{cases} \]

• 由于 \(A\) 可逆，\(R\) 的对角元 \(r_{ii} \neq 0\)。从最后一个方程开始，依次求解：

\[ x_n = \frac{c_n}{r_{nn}}, \quad x_{n-1} = \frac{c_{n-1} - r_{n-1,n}x_n}{r_{n-1,n-1}}, \quad \dots \]

 一般公式为：

\[ x_i = \frac{c_i - \sum_{j=i+1}^{n} r_{ij} x_j}{r_{ii}}, \quad i = n, n-1, \dots, 1 \]

8. 第四步：算法总结与数值特性：
   • 计算步骤：
     1. 对 \(A\) 进行QR分解，得到 \(Q\) 和 \(R\)。
     2. 计算 \(\mathbf{c} = Q^T \mathbf{b}\)。
     3. 解上三角方程组 \(R\mathbf{x} = \mathbf{c}\) 得到解 \(\mathbf{x}\)。
   • 数值稳定性：QR分解基于正交变换，不会放大舍入误差，通常比高斯消元法更稳定，尤其适用于病态矩阵。
   • 计算复杂度：QR分解需要大约 \(O(n^3)\) 次浮点运算，与LU分解同量级，但常数因子更大。求解三角方程组只需 \(O(n^2)\) 次运算。

通过以上步骤，我们利用QR分解将原线性方程组转化为一个易于求解的上三角方程组，从而得到精确且数值稳定的解。