矩陣的 Modified Gram Schmidt 方法

矩陣的 QR 分解在電腦運算中可能造成誤差，本文探討一下一種改進版本的 Gram-Schmidt 正交化方法。

經典的 Gram-Schmidt 方法可能造成數值不穩定性。在電腦中，舍入誤差可能會累積，造成得到的正交基並不具有正交性。

經典的 Gram-Schmidt

我們先來回顧一下經典的 Gram-Schmidt 方法：

for j = 1 : n
    v_j = x_j
    for k = 1 : j - 1
        v_j = v_j - ( (v_k^T x_j) / (v_k^T v_k) ) * v_k
    endfor
endfor

最終我們將 v_j 歸一化得到標準正交基 q_j = (v_j)/(|v_j|) 。

注意：CGS 始終使用原始向量 x_j 與之前的基向量計算投影

數學證明

簡單進行數學證明

定義第 j 步生成的向量 v_j

$$v_j = x_j - \sum_{k=1}^{j-1} ( (v_k^T x_j) / (v_k^T v_k) ) v_k$$

選取任意一個之前的基向量 v_m（其中 1 ≤ m < j），計算它與 v_j 的內積 v_m^Tv_j： $$v_m^T v_j = v_m^T ( x_j - \sum_{k=1}^{j-1} ((v_k^T x_j) / (v_k^T v_k)) v_k )$$

利用內積的線性性質，將 v_m^T 乘進去：

$$v_m^T v_j = v_m^T x_j - \sum_{k=1}^{j-1} ((v_k^T x_j) / (v_k^T v_k)) (v_m^T v_k)$$

由於前提假設 v₁, …, v_j − 1 是兩兩正交的，所以在求和符號 ∑ 中：

• 當 k ≠ m 時，v_m^Tv_k = 0 。
• 當且僅當 k = m 時，v_m^Tv_k = v_m^Tv_m ≠ 0 。

因此，求和項中只剩下 k = m 這一項：

v_m^Tv_j = v_m^Tx_j − ((v_m^Tx_j)/(v_m^Tv_m))(v_m^Tv_m)

分子分母中的標量 v_m^Tv_m 相互抵消：

v_m^Tv_j = v_m^Tx_j − v_m^Tx_j

v_m^Tv_j = 0

證畢

誤差分析

如果在 CGS（經典格拉姆-施密特正交化）中計算 q₂ 時發生誤差，導致 q₁^Tq₂ = δ 是一個很小但非零的數值，這個誤差將不會在隨後的任何計算中被修正：

v₃ = x₃ − (q₁^Tx₃)q₁ − (q₂^Tx₃)q₂

q₂^Tv₃ = q₂^Tx₃ − (q₁^Tx₃)δ − (q₂^Tx₃) = −(q₁^Tx₃)δ

q₁^Tv₃ = q₁^Tx₃ − (q₁^Tx₃) − (q₂^Tx₃)δ = −(q₂^Tx₃)δ

我們可以看出 v₃ 與 q₁ 或 q₂ 都不正交。

改進的 Gram-Schmidt (MGS)

for j = 1 : n
    v_j = x_j
endfor

for j = 1 : n
    q_j = v_j / ||v_j||_2
    for k = j + 1 : n
        v_k = v_k - (q_j^T v_k) q_j
    endfor
endfor

最終我們將 v_j 歸一化得到標準正交基 q_j = (v_j)/(|v_j|) 。

區別在於，一旦算出來一個向量 q，立即用它去更新後面所有的向量（減去向量在 q 上的投影），使得後面所有的向量與這個向量 q 正交。

誤差分析

假設 MGS 出現：q₁^Tq₂ = δ 很小但非零。

對於第三個向量 v₃ ：

• 初始狀態：v₃⁽⁰⁾ = x₃
• j = 1 : v₃⁽¹⁾ = v₃⁽⁰⁾ − (q₁^Tv₃⁽⁰⁾)q₁
• j = 2 : v₃ = v₃⁽¹⁾ − (q₂^Tv₃⁽¹⁾)q₂

此時 v₃ 是第三個向量在歸一化之前的最終形式。

讓我們檢查正交性，假設不再產生其他誤差：

q₂^Tv₃ = q₂^Tv₃⁽¹⁾ − (q₂^Tv₃⁽¹⁾) = 0

所以，我們保留了對 q₂ 的正交性。

接下來看 q₁：

q₁^Tv₃ = q₁^Tv₃⁽¹⁾ − (q₂^Tv₃⁽¹⁾)δ

q₂^Tv₃⁽¹⁾ = q₂^Tv₃⁽⁰⁾ − (q₁^Tv₃⁽⁰⁾)δ

q₁^Tv₃⁽¹⁾ = q₁^Tv₃⁽⁰⁾ − (q₁^Tv₃⁽⁰⁾) = 0

由此可得： q₁^Tv₃ = −(q₂^Tv₃⁽⁰⁾ − (q₁^Tv₃⁽⁰⁾)δ)δ = −q₂^Tv₃⁽⁰⁾δ + q₁^Tv₃⁽⁰⁾δ²

由於 δ 非常小，δ² 就更小了。因此 q₁^Tv₃ 中的誤差和 CGS 差不多，但我們消除了 q₂^Tv₃ 中的誤差，使得誤差更小。

總結

在電腦中，由於浮點運算的特殊性，有許多數學方法需要重新考慮，儘量提高數值穩定性。這使得我們有必要重新審視我們學習過的數學知識，針對電腦的特殊性進行重新設計與優化。