QR分解法解线性方程组

字数 3028 2025-10-25 20:03:52

QR分解法解线性方程组

题目描述
给定一个线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是一个 \(m \times n\) 的矩阵（通常 \(m \geq n\)，即方程数大于等于未知数个数），\(\mathbf{b}\) 是已知的 \(m\) 维向量。要求利用 QR 分解法求解向量 \(\mathbf{x}\)，使得 \(A\mathbf{x}\) 尽可能接近 \(\mathbf{b}\)。当 \(A\) 列满秩（即秩为 \(n\)）时，QR 分解可得到唯一的最小二乘解。

解题过程

QR 分解的基本概念
QR 分解是将矩阵 \(A\) 分解为一个正交矩阵 \(Q\) 和一个上三角矩阵 \(R\) 的乘积，即 \(A = QR\)。
- 正交矩阵 \(Q\) 满足 \(Q^T Q = I\)（单位矩阵）。
- 上三角矩阵 \(R\) 的所有非零元素位于主对角线及其上方。
- 当 \(A\) 为 \(m \times n\) 矩阵时，\(Q\) 是 \(m \times m\) 方阵，\(R\) 是 \(m \times n\) 的上三角矩阵（若 \(m > n\)，则 \(R\) 下半部分为零）。
QR 分解的构造方法（以 Gram-Schmidt 过程为例）
假设 \(A\) 的列向量为 \(\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_n\)。通过以下步骤构造标准正交基 \(\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n\)：
- 第一步：归一化第一个列向量

\[ \mathbf{u}_1 = \mathbf{a}_1, \quad \mathbf{q}_1 = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|}. \]

第二步：从后续列向量中减去在前一方向上的投影，确保正交性

\[ \mathbf{u}_2 = \mathbf{a}_2 - (\mathbf{q}_1^T \mathbf{a}_2) \mathbf{q}_1, \quad \mathbf{q}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|}. \]

第 \(k\) 步（通用公式）：

\[ \mathbf{u}_k = \mathbf{a}_k - \sum_{i=1}^{k-1} (\mathbf{q}_i^T \mathbf{a}_k) \mathbf{q}_i, \quad \mathbf{q}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}. \]

最终得到 \(Q = [\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n]\)，而 \(R\) 的元素由投影系数决定：

\[ R = \begin{bmatrix} \mathbf{q}_1^T \mathbf{a}_1 & \mathbf{q}_1^T \mathbf{a}_2 & \cdots & \mathbf{q}_1^T \mathbf{a}_n \\ 0 & \mathbf{q}_2^T \mathbf{a}_2 & \cdots & \mathbf{q}_2^T \mathbf{a}_n \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{q}_n^T \mathbf{a}_n \end{bmatrix}. \]

注意：若 \(m > n\)，\(R\) 的下半部分补零。

利用 QR 分解求解线性方程组
将 \(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}. \]

当 \(m = n\) 时，\(R\) 是方阵，可直接通过回代法求解。
当 \(m > n\) 时，\(R\) 为“高瘦”矩阵，但有效部分是其前 \(n\) 行组成的上三角块，剩余行全为零。此时取前 \(n\) 行方程求解，得到最小二乘解。

回代法求解上三角系统
假设 \(R\) 是 \(n \times n\) 上三角矩阵，方程组形式为：

\[ \begin{cases} r_{11}x_1 + r_{12}x_2 + \cdots + r_{1n}x_n = y_1, \\ r_{22}x_2 + \cdots + r_{2n}x_n = y_2, \\ \vdots \\ r_{nn}x_n = y_n. \end{cases} \]

从最后一行开始反向求解：

第 \(n\) 行：\(x_n = y_n / r_{nn}\)。
第 \(k\) 行（\(k = n-1, n-2, \dots, 1\)）：

\[ x_k = \frac{y_k - \sum_{j=k+1}^{n} r_{kj} x_j}{r_{kk}}. \]

示例（3×3 系统）
设 \(A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\), \(\mathbf{b} = \begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}\)。
- QR 分解：
  通过 Gram-Schmidt 过程：
  \(\mathbf{q}_1 = \frac{1}{\sqrt{2}} [1, 1, 0]^T\),
  \(\mathbf{u}_2 = [1,0,1]^T - (\mathbf{q}_1^T [1,0,1]^T) \mathbf{q}_1 = [0.5, -0.5, 1]^T\),
  \(\mathbf{q}_2 = \frac{[0.5,-0.5,1]^T}{\sqrt{1.5}}\),
  类似得 \(\mathbf{q}_3\)。最终构造 \(Q\) 和 \(R\)。
- 求解：计算 \(\mathbf{y} = Q^T \mathbf{b}\)，再解 \(R\mathbf{x} = \mathbf{y}\) 得 \(\mathbf{x} = [1, 1, 1]^T\)。

总结
QR 分解通过正交化将原问题转化为易求解的上三角系统，适用于满秩或超定方程组，且数值稳定性优于高斯消元法。

QR分解法解线性方程组题目描述给定一个线性方程组 \( A\mathbf{x} = \mathbf{b} \)，其中 \( A \) 是一个 \( m \times n \) 的矩阵（通常 \( m \geq n \)，即方程数大于等于未知数个数），\( \mathbf{b} \) 是已知的 \( m \) 维向量。要求利用 QR 分解法求解向量 \( \mathbf{x} \)，使得 \( A\mathbf{x} \) 尽可能接近 \( \mathbf{b} \)。当 \( A \) 列满秩（即秩为 \( n \)）时，QR 分解可得到唯一的最小二乘解。解题过程 QR 分解的基本概念 QR 分解是将矩阵 \( A \) 分解为一个正交矩阵 \( Q \) 和一个上三角矩阵 \( R \) 的乘积，即 \( A = QR \)。正交矩阵 \( Q \) 满足 \( Q^T Q = I \)（单位矩阵）。上三角矩阵 \( R \) 的所有非零元素位于主对角线及其上方。当 \( A \) 为 \( m \times n \) 矩阵时，\( Q \) 是 \( m \times m \) 方阵，\( R \) 是 \( m \times n \) 的上三角矩阵（若 \( m > n \)，则 \( R \) 下半部分为零）。 QR 分解的构造方法（以 Gram-Schmidt 过程为例）假设 \( A \) 的列向量为 \( \mathbf{a}_ 1, \mathbf{a}_ 2, \dots, \mathbf{a}_ n \)。通过以下步骤构造标准正交基 \( \mathbf{q}_ 1, \mathbf{q}_ 2, \dots, \mathbf{q}_ n \)：第一步：归一化第一个列向量 \[ \mathbf{u}_ 1 = \mathbf{a}_ 1, \quad \mathbf{q}_ 1 = \frac{\mathbf{u}_ 1}{\|\mathbf{u}_ 1\|}. \] 第二步：从后续列向量中减去在前一方向上的投影，确保正交性 \[ \mathbf{u}_ 2 = \mathbf{a}_ 2 - (\mathbf{q}_ 1^T \mathbf{a}_ 2) \mathbf{q}_ 1, \quad \mathbf{q}_ 2 = \frac{\mathbf{u}_ 2}{\|\mathbf{u}_ 2\|}. \] 第 \( k \) 步（通用公式）： \[ \mathbf{u}_ k = \mathbf{a} k - \sum {i=1}^{k-1} (\mathbf{q}_ i^T \mathbf{a}_ k) \mathbf{q}_ i, \quad \mathbf{q}_ k = \frac{\mathbf{u}_ k}{\|\mathbf{u}_ k\|}. \] 最终得到 \( Q = [ \mathbf{q}_ 1, \mathbf{q}_ 2, \dots, \mathbf{q}_ n ] \)，而 \( R \) 的元素由投影系数决定： \[ R = \begin{bmatrix} \mathbf{q}_ 1^T \mathbf{a}_ 1 & \mathbf{q}_ 1^T \mathbf{a}_ 2 & \cdots & \mathbf{q}_ 1^T \mathbf{a}_ n \\ 0 & \mathbf{q}_ 2^T \mathbf{a}_ 2 & \cdots & \mathbf{q}_ 2^T \mathbf{a}_ n \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{q}_ n^T \mathbf{a}_ n \end{bmatrix}. \] 注意：若 \( m > n \)，\( R \) 的下半部分补零。利用 QR 分解求解线性方程组将 \( 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}. \] 当 \( m = n \) 时，\( R \) 是方阵，可直接通过回代法求解。当 \( m > n \) 时，\( R \) 为“高瘦”矩阵，但有效部分是其前 \( n \) 行组成的上三角块，剩余行全为零。此时取前 \( n \) 行方程求解，得到最小二乘解。回代法求解上三角系统假设 \( R \) 是 \( n \times n \) 上三角矩阵，方程组形式为： \[ \begin{cases} r_ {11}x_ 1 + r_ {12}x_ 2 + \cdots + r_ {1n}x_ n = y_ 1, \\ r_ {22}x_ 2 + \cdots + r_ {2n}x_ n = y_ 2, \\ \vdots \\ r_ {nn}x_ n = y_ n. \end{cases} \] 从最后一行开始反向求解：第 \( n \) 行：\( x_ n = y_ n / r_ {nn} \)。第 \( k \) 行（\( k = n-1, n-2, \dots, 1 \)）： \[ x_ k = \frac{y_ k - \sum_ {j=k+1}^{n} r_ {kj} x_ j}{r_ {kk}}. \] 示例（3×3 系统）设 \( A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \), \( \mathbf{b} = \begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix} \)。 QR 分解：通过 Gram-Schmidt 过程： \( \mathbf{q}_ 1 = \frac{1}{\sqrt{2}} [ 1, 1, 0 ]^T \), \( \mathbf{u}_ 2 = [ 1,0,1]^T - (\mathbf{q}_ 1^T [ 1,0,1]^T) \mathbf{q}_ 1 = [ 0.5, -0.5, 1 ]^T \), \( \mathbf{q}_ 2 = \frac{[ 0.5,-0.5,1 ]^T}{\sqrt{1.5}} \), 类似得 \( \mathbf{q}_ 3 \)。最终构造 \( Q \) 和 \( R \)。求解：计算 \( \mathbf{y} = Q^T \mathbf{b} \)，再解 \( R\mathbf{x} = \mathbf{y} \) 得 \( \mathbf{x} = [ 1, 1, 1 ]^T \)。总结 QR 分解通过正交化将原问题转化为易求解的上三角系统，适用于满秩或超定方程组，且数值稳定性优于高斯消元法。