用局部座標變換對角化
實對稱矩陣具有實特徵值和標準正交特徵向量基。Jacobi 特徵值方法反覆只旋轉兩個座標方向,以尋找這種對角結構。每次旋轉消去一個非對角元素,卻不改變特徵值。其他元素可能重新出現,所以重要的問題不是某個位置是否一直保持為零,而是非對角部分的總量是否減少。
這是特徵值算法,不是用於求解線性方程組的 Jacobi 平穩迭代。下文對實對稱 矩陣 在精確算術中工作,。有限精度可能破壞精確對稱性和精確消零;下述收斂證明本身並未建立捨入誤差界。
一次平面旋轉
定義 5.3.1
(Jacobi 平面旋轉)
選取下標 ,將對應的對稱 塊簡記為
令 除座標 外與單位矩陣相同,在這兩個座標上的塊為
更新採用 。
由於 正交,這是一種正交相似變換:對稱性和特徵值多重集均保持。在這個具體符號約定下,新的主元元素為
命題 5.3.2
(消去主元的旋轉)
若 ,無需旋轉。若 ,令 、,並選取
便使 ,並且新的對角元素為
證明
(解主元方程)
由於 ,條件 等價於 ,即 。所選的 是這個二次方程中模較小的根:當 時它是 , 的情形對稱。它滿足 。當 時方程為 , 是一個根。
展開 得 。由於 ,便得 。該 塊經正交相似變換,跡保持不變,所以 。
所選的根避免了在所示代數公式中對兩個很大且接近的數作減法。實際浮點程式碼中,即使計算 或 也可能上溢;縮放公式和仔細實現是另一個數值問題。
常見錯誤
(混用旋轉的符號約定)
其他教材可能選用轉置後的旋轉,使 的符號相反。更新式 、 的主元公式、 的公式以及對角元素的更新都取決於這個選擇,必須一起改變。若主元公式取自一種約定,更新卻取自另一種,得到的矩陣仍然與 相似,但其主元元素一般不為零。
二維例子
例題 5.3.3
(一次旋轉對角化 2 階矩陣)
對 ,有 ,故 、。一次旋轉給出
的列是歸一化特徵向量: 對應 1, 對應 3。將一列的符號反轉仍表示同一特徵方向。
概念視角幾何
旋轉到主軸
這個塊定義二次型 。記 ,主元方程 就是 ,而所選的根滿足 。把座標軸旋轉這個角度,交叉項便消失,新的座標軸就是這個二次型的主軸。在上面的例子中,主軸方向是 和 。
非對角部分的減少
定義 5.3.4
(非對角測度)
方陣 的非對角 Frobenius 測度的平方定義為
每個元素的兩個對稱位置都計入。
命題 5.3.5
(消去旋轉下的精確減少量)
若一次 Jacobi 旋轉消去 ,則
證明
(正交混合保持成對平方和)
對每個 ,數對 乘以一個正交 矩陣,故其平方和不變。由對稱性,相應行元素給出同樣貢獻。兩行兩列之外的元素不變。只有兩個主元位置從非對角和中消失,各貢獻 。這也說明為甚麼如果只統計一個三角部分,因子二會改變。
例題 5.3.6
(三對角矩陣的非對角測度)
對
。消去主元 的一次旋轉得到 。其他一些非對角元素會改變:與第三個座標耦合的兩個元素被旋轉。這裏 ,,被旋轉的數對 變成 ,其平方和仍為 。
例題 5.3.7
(第二次旋轉後的填入)
從上面的 繼續,其元素為 、、、、、。最大主元並列,模均為 ,選取 。取 、、,得 ,於是 ,,。旋轉後的矩陣約為
所以 ,與恆等式一致。第一次旋轉已置零的元素 ,現在約為 。兩步的保證上界為 ,實際值 低於此界。
常見錯誤
(以為已置零的元素會一直保持為零)
在座標 所在平面內的旋轉,會把第 、 行與列同其餘各行各列混合,所以一般會重新填入先前旋轉已清除的元素,上一個例子已經說明。收斂來自總測度 的減少,並不是來自元素一經置零便永遠固定。
最大主元收斂性
定義 5.3.8
(最大主元 Jacobi 方法)
在第 步,若 ,選取使 最大的 ,並應用上面的消零旋轉。並列時可任意選擇。如果非對角測度為零,則停止。
定理 5.3.9
(非對角測度的線性減少)
在精確算術下,使用最大主元策略有
因此,只要迭代無限繼續,就有 。當 時因子為零,一次非平凡旋轉便使矩陣對角化。
證明
(最大元素不小於平均值)
完整和式中有 個非對角元素。最大主元的模 至少不小於每一個,故 。將該界代入精確減少恆等式。當 時,因子嚴格介於零與一之間,反覆應用得到趨於零的幾何上界。
證明透視
主元規則與正交性各在哪裏起作用
這個證明用到兩個互相獨立的事實,各在一處起作用。旋轉的正交性給出精確恆等式 ,對任何使用消零旋轉的主元它都成立。主元規則只通過下界 起作用: 個平方數中最大的一個不小於它們的平均值。沒有這條規則時,恆等式仍然成立,但 可能為零,這時甚麼也不會減少。兩處計數必須採用同一個約定:恆等式減去主元的兩個副本,而平均值是對兩個三角部分一起取的。
下面的例子說明主元規則不能省去。
反例模式
忽略最大元素的主元規則
斷言:任何在固定位置施行消零旋轉的規則,都使非對角測度幾何地減少。取
則 。若算法始終選擇 ,且當所選元素為零時甚麼也不做,就會發現 ,矩陣保持不變,非對角測度永遠保持 。這不是對正確指定的循環 Jacobi 方法的反例;它只說明反覆選擇已為零的位置不滿足最大主元條件。最大主元是 :此時 ,,,一次旋轉便得到 ,。
累積旋轉與近似特徵對
令 ,。每個 都正交,且
記 為 的第 列,。
命題 5.3.10
(累積各列的殘差)
每個 都是單位向量, 是它對 的 Rayleigh 商,並且
證明
(由相似關係讀出殘差)
關係式 說明 。減去 後剩下 。各列 標準正交,所以其平方範數為 ,它是定義 的和的一部分。由於 是正交矩陣的一列,範數為一,而 就是 Rayleigh 商。
因此收斂定理給出每一列的殘差趨於零。對稱矩陣的殘差界說明,非對角範數小時,每個對角元素都接近某個特徵值。每一步的相似變換保持整個特徵值多重集。
常見錯誤
(由小殘差讀出極限特徵向量)
這些結論本身不能證明 的每一列都收斂到某個指定特徵向量,也不能說明某個對角下標對應事先指定的特徵值。特徵向量的符號不唯一,重特徵值的特徵空間也有不唯一的基。若聲稱特徵向量有極限,或單個特徵值具有某個收斂速度,還需額外假設和單獨論證。
實際停止規則可在 非零時,將 與相對此範數的容差比較。精確正交相似變換保持 Frobenius 範數。殘差估計解釋了該準則的意義;實際程式碼還須考慮浮點誤差,並單獨處理零矩陣。
練習與解答
快速檢查
(對 ,使用所述 約定求 和對應特徵向量。)
這裏 。
解答 · 答案
、,故所述旋轉給出 、,即 。列 和 分別對應 1 和 5。
快速檢查
(一個對稱 迭代矩陣滿足 。一次最大主元旋轉後,新的非對角測度平方有甚麼上界?)
使用因子 。
解答 · 答案
,所以新的平方測度至多為 。
快速檢查
(對上面的 三對角例子,不計算 的所有元素,解釋為甚麼消去 後非對角測度平方為 2。)
使用精確減少恆等式。
解答 · 答案
精確減少量是 ,因此從 4 變為 2。旋轉保持其餘成對元素的平方和。
快速檢查
(若 ,可對每個累積旋轉列和對應對角值說甚麼?這是否單獨證明了當 時這些列收斂?)
想一想對稱矩陣的殘差界。
解答 · 答案
每列都是單位向量,對其對角值的特徵對殘差範數至多為 ,所以由對稱性,必有某個特徵值與該對角值相差不超過 。單憑一次小殘差的觀察,並不能證明列的序列收斂到某個指定的特徵向量。