QR分解法解线性方程组
题目描述
给定一个线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是一个 \(m \times n\) 的矩阵（通常 \(m \geq n\)），\(\mathbf{b}\) 是已知向量，\(\mathbf{x}\) 是待求解的未知向量。QR分解法通过将矩阵 \(A\) 分解为一个正交矩阵 \(Q\) 和一个上三角矩阵 \(R\) 的乘积，将原问题转化为易于求解的三角方程组。
解题过程
1. QR分解的基本原理
QR分解的目标是将矩阵 \(A\) 分解为：
\[A = QR \]
其中：
- \(Q\) 是 \(m \times m\) 的正交矩阵（即 \(Q^T Q = I\)），
- \(R\) 是 \(m \times n\) 的上三角矩阵（即当 \(i > j\) 时，\(R_{ij} = 0\)）。
若 \(m > n\)，\(R\) 可写为 \(R = \begin{bmatrix} R_1 \\ 0 \end{bmatrix}\)，其中 \(R_1\) 是 \(n \times n\) 的上三角矩阵。
2. 分解过程：以Gram-Schmidt正交化为例
假设 \(A\) 的列向量线性无关，Gram-Schmidt正交化的步骤如下：
- 设 \(A\) 的列向量为 \(\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_n\)。
- 逐步构造正交向量 \(\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n\) 和上三角矩阵 \(R\) 的元素：
- \(\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|\)，并令 \(r_{11} = \|\mathbf{a}_1\|\)。
- 对于 \(j = 2\) 到 \(n\)：
- 计算投影系数：\(r_{ij} = \mathbf{q}_i^T \mathbf{a}_j\)（对 \(i = 1\) 到 \(j-1\)），
- 计算正交向量：\(\mathbf{v}_j = \mathbf{a}_j - \sum_{i=1}^{j-1} r_{ij} \mathbf{q}_i\)，
- 归一化：\(\mathbf{q}_j = \mathbf{v}_j / \|\mathbf{v}_j\|\)，并令 \(r_{jj} = \|\mathbf{v}_j\|\)。
- 最终 \(Q = [\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n]\)，\(R\) 由 \(r_{ij}\) 构成的上三角矩阵。
3. 转化为三角方程组
将 \(A = QR\) 代入原方程：
\[QR\mathbf{x} = \mathbf{b} \]
两边左乘 \(Q^T\)（利用 \(Q^T Q = I\)）：
\[R\mathbf{x} = Q^T \mathbf{b} \]
记 \(\mathbf{y} = Q^T \mathbf{b}\)，则问题简化为求解：
\[R\mathbf{x} = \mathbf{y} \]
由于 \(R\) 是上三角矩阵，可通过回代法快速求解。
4. 回代求解
假设 \(R\) 是 \(n \times n\) 的上三角矩阵（若 \(m > n\)，取 \(R\) 的前 \(n\) 行）：
- 从最后一行开始求解：
\[ x_n = \frac{y_n}{r_{nn}} \]
- 对于 \(i = n-1, n-2, \dots, 1\)：
\[ x_i = \frac{y_i - \sum_{j=i+1}^n r_{ij} x_j}{r_{ii}} \]
5. 算法稳定性与注意事项
- 当 \(A\) 接近奇异时，Gram-Schmidt可能数值不稳定，建议使用改进的Gram-Schmidt或Householder变换。
- 若 \(m > n\)，方程组可能无解，QR分解给出最小二乘解（需额外处理残差部分）。
通过以上步骤，QR分解将原问题转化为正交变换和三角方程组求解，适用于数值稳定的线性方程组求解。