matlab解超靜定方程,超定方程和最小二乘法 | 學步園詳情 - 算法,超定方程組,線性方程求解,稀疏矩陣,最小二乘,Hadoop,大數據 mob64ca140f67e3 博客

對於稀疏的超定線性方程組 Ax = b（其中 A ∈ ℝᵐˣⁿ，m > n，即方程個數多於未知數個數），由於通常不存在精確解，我們尋求最小二乘意義下的最優解：

min ‖Ax - b‖₂²

當矩陣 A 是大型稀疏矩陣時，直接法（如QR分解、SVD）計算開銷大，因此常用迭代法或基於稀疏結構的優化算法。以下是幾種常用解法：

1. 正規方程法 (Normal Equations)

將最小二乘問題轉化為求解正規方程：

AᵀA x = Aᵀb

優點：轉化為對稱正定系統（若 A 列滿秩），可用共軛梯度法（CG）求解。
缺點：條件數 κ(AᵀA) = [κ(A)]²，可能嚴重病態，數值不穩定。
適用場景：A 非常稀疏且 AᵀA 仍保持良好稀疏結構時。

求解方式：使用 共軛梯度法 (Conjugate Gradient, CG) 迭代求解 AᵀA x = Aᵀb，無需顯式構造 AᵀA，只需矩陣-向量乘法操作。

2. LSQR 算法

由 Paige 和 Saunders 提出，是求解稀疏最小二乘問題的首選迭代法之一。

基於 Lanczos 雙正交化過程，將原問題投影到低維 Krylov 子空間。
求解 min ‖Ax - b‖ 的等價問題。
優點：

數值穩定（類似 SVD 的行為）
支持預處理（Preconditioning）
內存高效，適合大型稀疏系統
自動估計殘差和解的誤差

收斂性好，尤其適用於病態或條件數大的問題。

公式本質：通過 bidiagonalization 構造小型 bidiagonal 系統，再求其最小二乘解。

3. LSMR 算法

與 LSQR 類似，但更適用於 ill-conditioned 問題。

同樣基於 Golub-Kahan-Lanczos 過程。
求解的是相同最小二乘問題，但迭代方向更優。
優點：比 LSQR 收斂更穩定，尤其當 ‖r‖ 不易減小時。

LSMR 和 LSQR 都是 Krylov 子空間方法，廣泛用於科學計算庫（如 SciPy、MATLAB）。

4. 預處理共軛梯度法（PCG on Normal Equations）

若使用正規方程 AᵀA x = Aᵀb，可引入預處理器 M ≈ AᵀA 來加速收斂。

常用預處理器：

對角預處理（Jacobi）：M = diag(AᵀA)
不完全 Cholesky 分解（IC）
代數多重網格（AMG）等

通過預處理共軛梯度法（PCG）求解，僅需稀疏矩陣乘法。

5. QR 分解（稀疏版本）

對稀疏 A 進行 稀疏 QR 分解：

A = QR

其中 Q ∈ ℝᵐˣᵐ 正交，R ∈ ℝᵐˣⁿ 上三角（或梯形）。

則最小二乘解為：
x = R₁⁻¹ (Q₁ᵀ b)
其中 R₁ 是 R 的前 n 行 n 列上三角塊，Q₁ 是 Q 的前 n 列。

挑戰：稀疏 QR 分解需進行列選主元（列排序）以減少填充（fill-in）。
工具：SuiteSparse、SPQR（針對稀疏最小二乘）等庫提供高效實現。

6. 奇異值分解（SVD）與截斷 SVD

對 A 進行 SVD：A = UΣVᵀ

最小二乘解：x = V Σ⁺ Uᵀ b

優點：最穩定，能處理秩虧（rank-deficient）系統。
缺點：計算昂貴，不適合超大規模稀疏矩陣。
稀疏 SVD：使用 Lanczos 方法計算部分奇異值/向量（如 LSVD），適用於低秩近似。

7. 增廣系統法（Augmented System）

將最小二乘問題轉化為求解增廣線性系統：

[ I A ] [ r ] [ b ] [ Aᵀ 0 ] [ x ] = [ 0 ]

其中 r = b - Ax 是殘差。

使用 Krylov 方法（如 GMRES、MINRES）配合適當的預處理求解。
適合並行計算和稀疏結構。

總結對比

方法	適用性	穩定性	內存效率	是否需預處理
正規方程 + CG	小中規模，良態	中	高	推薦
LSQR	大型稀疏，通用	高	高	支持
LSMR	病態問題	高	高	支持
稀疏 QR	中小規模稀疏	高	中	否
截斷 SVD	秩虧或降噪	最高	低	否
增廣系統法	特殊結構或並行	高	高	推薦

mob64ca140f67e3 博客

mob64ca140f67e3 博客

博客 / 詳情