標準正交基令座標及投影計算簡便,但給定的一組基往往並非標準正交。Gram–Schmidt 在不改變輸入列表各個初始段所生成子空間的前提下,構造標準正交列表。其關鍵步驟是殘差:減去早先方向已能解釋的部分,再把餘下部分歸一化。零殘差表示線性相關,而不是一個可以歸一化的方向。
現有內積課證明了 Gram–Schmidt;空間與映射提供向量空間基礎。本節進一步討論初始段生成空間、相關列表及薄 QR。
記號與約定
設 為有限維實或複內積空間。採用第一變量線性的內積。在標準正交列座標下,
因此,向量 沿單位向量 的係數為 ,而不是 。星號表示共軛轉置;在實數域上就是普通轉置。
定義 9.1.1
(對標準正交列表的殘差)
設 是 中的標準正交列表,。 對該列表的殘差為
列表為空時求和為空,。列表 的有序初始段生成空間是子空間 ,。
減去早先的方向
先假設 線性無關。遞迴定義 為 對 的殘差,並令 。
定理 9.1.2
(線性無關輸入的 Gram–Schmidt)
設 線性無關。令
則每個 ,遞迴因而有定義;列表 標準正交;而且
證明
(正交性、殘差非零與初始段生成空間相等)
對 作歸納,假設 標準正交,且初始段生成空間如所述。對每個 ,
所以殘差垂直於早先所有保留方向。它不可能為零:否則定義式會令 屬於這些方向的生成空間;由歸納,該空間就是它之前的輸入向量所生成的空間,與線性無關矛盾。因此可合法歸一化,得到一個與其他向量垂直的新單位向量。
重構方程為
它說明 ,所以 的初始段生成空間包含於 的。反過來,每個殘差都是 與早先 的線性組合,因而是 的線性組合,所以 屬於 的初始段生成空間。兩個包含關係都成立。
證明透視
線性無關用在哪裏,以及為何兩個包含關係都要證
證明只用一次線性無關:使 ,這才容許作除法。正交性則不需要它,因為抵消 對任何殘差都成立。歸納假設用了兩次:早先 的標準正交性令求和只剩一項;早先初始段生成空間相等,則把「」翻譯成「 是 的線性組合」。
單憑正交性不能證明生成空間相等: 個標準正交向量可以落在另一個 維子空間內。由重構方程得到的包含關係,加上維數計算或另一方向的直接包含,才完成論證。沒有線性無關時,同一計算在每個非零步驟仍給出正交性,但遇到零殘差,遞迴便停止。
結果依賴輸入次序。最終生成空間固定,但改變次序通常會產生不同的中間方向。把某個輸入乘以複相位,也可能改變其歸一化方向。固定的是所述遞迴構造,並約定殘差範數取正實數。
常見錯誤
(把係數的兩個變量次序寫反)
對第一變量線性的內積, 在 中的係數是 。在 中取 ,。正確係數為 ,殘差 ,與 垂直。反了次序的係數 給出 ,它與 的內積為 。在實數域上兩種次序相同,所以這個錯誤只在 上出現。
相關列表需要略去輸入
對一般有序列表,保留截至目前所得的標準正交列表。從下一個輸入減去它在該列表生成空間上的投影。若殘差非零,加入其歸一化向量;若為零,略去這個輸入,保持當前列表不變。
在每個階段,保留列表的生成空間等於輸入初始段的生成空間。零殘差等價於當前向量屬於先前保留方向的生成空間,所以略去它不會損失資訊。非零殘差令維數增加一。歸納可知,即使原列表有零向量或重複向量,最終保留列表仍是整個輸入生成空間的一組標準正交基。
這是精確算術結論。在浮點計算中,很小的殘差並不自動證明精確的線性相關。數值門檻需要另作誤差分析;本章不作這類數值斷言。
反例模式
對相關列表使用 Gram–Schmidt
命題:對任意 個向量執行線性無關情形的遞迴,必得 個標準正交向量。在 取 ,。則 ,,投影為 ,故 。公式 要除以 :不存在第二個單位向量;生成空間只是一條直線,其中放不下長度為 的標準正交列表。修正:略去殘差為零的輸入,並報告保留向量的個數,此處為 。
例題 9.1.3
(含重複方向的相關列表)
在 取 ,,。首先 。對 :,投影為 ,殘差為 ,略去 。對 :,投影為 ,,,所以 。保留列表 有兩個向量,等於輸入列表的秩。驗算:,且 。
三角形重構就是薄 QR 分解
設 為列向量線性無關的實或複 矩陣,所以 。對其各列應用構造,令 ,並定義
定理 9.1.4
(薄 QR 分解)
若 是列向量線性無關的 矩陣,則 ,其中 , 為上三角矩陣且對角元素為正實數。這個分解是唯一的。
證明
(存在性來自重構,唯一性來自被強制的各步)
存在性就是把重構方程 逐列讀出,再加上 的標準正交性。
唯一性:設 是任一符合要求的分解。第一列強制給出 ;單位範數及正對角約定強制 ,並確定 。歸納地,設 已確定。把 與 ()作內積,固定 。餘下的部分是 ,所以它的正範數固定 ,進而固定 。
這裏 只包含所需的 個標準正交列。當 , 是到列空間的投影,而不是環境空間上的恆等算子。若沒有正對角約定,符號或複相位便可在兩個因子之間轉移。
對相關列,保留的 有 列,重構矩陣的尺寸為 。它不是一個方形可逆三角矩陣。略去零殘差後,若不改變這些尺寸,便不能聲稱得到滿列秩情況的 QR 分解。
例題 9.1.5
( 矩陣的薄 QR)
設 ,兩列為 ,。則 ,。其次 , ,。所以 ,。驗算 ,並重構第二列:。因 ,:例如 把 送到 。
以 Gram 矩陣核對計算
對滿列秩分解,
行列式恆等式來自兩個方形三角因子的行列式相乘;即使在複數情況,對角元素也都是正實數。更一般地,Gram 矩陣第 行、第 列的元素為 。它正定當且僅當向量線性無關,因為它在係數列處的二次值,就是相應線性組合的範數平方。
這提供了殘差長度的一個有用獨立檢查。對上面的例子, 的行列式為 ,而 。但它不能取代標準正交性檢查:只有正確的行列式,並不能確定每個內積。
概念視角代數
三角因子就是 Cholesky 因子
由於 ,而 是對角元為正的上三角矩陣, 就是 Gram 矩陣 的 Cholesky 因子;對正定矩陣而言,在對角元為正的約定下這個因子唯一。因此對 的各列做 Gram–Schmidt,所得三角矩陣與只對 Gram 矩陣做分解所得的相同,無須構造 。在上面的例子中,,其中 。
同一構造適用於多項式
向量不一定是座標列。對次數有界的實多項式,定義
這是內積。對稱性及雙線性由積分得到。若非零多項式的範數平方為零,連續性及區間中某個非零取值點,會給出一個小區間,使其平方在該區間上有正下界,產生矛盾。這樣的點存在,因為非零多項式不可能在整個區間上為零。
所以,對單項式應用 Gram–Schmidt 會產生標準正交多項式。其係數由實際的內積積分得到,不能把單項式座標列當作歐氏向量。
例題 9.1.6
(在 上把 標準正交化)
,所以 。對 :(被積函數為奇函數),故 ,,。對 :,在 方向的投影為 ,而 。於是 ,,所以 。驗算:。
清單及常見錯誤
- 對線性無關輸入,每個殘差都非零,而且每個初始段的生成空間保持不變。
- 對相關輸入,略去零殘差,並報告保留基的維數。不要除以零。
- 在第一變量線性的約定下,係數為 ;複數域上不能省略共軛。
- 線性無關列的薄 QR 滿足 , 上三角且對角為正實數。這些要求給出唯一性。
- 對非歐氏內積,應使用它實際的配對計算係數及範數。
對一個擬定答案,要檢查配對、殘差範數及重構。正交向量未必是單位向量;標準正交列表未必生成所需空間;矩陣乘積尺寸正確亦不足夠,它還必須重構輸入。
小測
快速檢查
(在 中對 , 作一步 Gram–Schmidt:求 和殘差 。)
解答 · 答案
。,所以投影為 ,。它與 垂直:。
快速檢查
(把 中的列表 交給帶略去規則的 Gram–Schmidt。保留多少個向量?哪一個輸入被略去?)
解答 · 答案
保留兩個。,,而 對它們的殘差為 ,所以第三個輸入被略去。個數等於 。
快速檢查
(若 是 矩陣的薄 QR 分解,且 ,是否有 ?)
解答 · 答案
沒有。 的秩為 ,不可能是單位矩陣。它是到 的列空間的正交投影;只有 成立。