3.2 的满秩分解把 A A A 拆成「基 × \times × 坐标」:B B B 的列撑起列空间,C C C 逐列记账。但这组基是斜的 ——第一章 1.5 已经算过账:在斜基下做内积要拖着度量矩阵,在标准正交基下一切公式都短(例 1.5.B 末尾那句「这正是标准正交基的价值」)。而 1.5.6 的 Gram–Schmidt 正交化恰好保证:任何一组基都能掰成标准正交基 。把这两件事拼起来,就得到本章的又一副眼镜——把满秩分解里的「斜骨架」掰直,让左因子成为酉矩阵 :
A = Q R , Q 酉, R 上三角 . A=QR,\qquad Q\ \text{酉},\ R\ \text{上三角}. A = QR , Q 酉 , R 上三角 .
右边这个形状就是QR 分解 。它在本节先以「方阵分解定理」的面貌出现(满秩方阵存在、且在「正线」约定下唯一,定理 3.4.1 ),随后被推广到长方阵(推论 3.4.1 ),最后变成一台机器——QR 算法 :反复做 QR 分解,就能把矩阵的全部特征值 一个一个挤到对角线上(QR 算法 )。一台「分解」喂养出一台「算法」,这是本章前面两节没有的待遇。
素材与说明(本节无录播)
本页依据课程第三章课件 3.4 QR 分解 (16 页,存于 _sources/matrix/3.4-QR分解.pdf)整理。本节无对应录播 ,故不引用课堂口述与时间戳:课件的定义、定理、注记与例题照录并保留原编号 (定义 3.4.1、定理 3.4.1、注 1、例 3.4.1–例 3.4.4、定义 3.4.2、推论 3.4.1);课件省略的证明(定理 3.4.1 的唯一性、推论 3.4.1 的构造)由本编补出并逐处标注「本编补」;例 3.4.3、例 3.4.4 的课件笔误见勘误与补注 (E3.6、E3.7),正文按核算后的自洽写法演算。本编新增例题用字母编号(例 3.4.A 、例 3.4.B(新增 )。
先交代定义。课件把复、实两个版本并列给出——差别只在「酉 / 正交」这一对词:
定义 3.4.1 · QR 分解(酉三角分解 / 正交三角分解)
若复方阵 A A A 可分解为
A = Q R , A=QR, A = QR ,
其中 Q Q Q 为酉矩阵 ,R R R 为上三角矩阵 ,则称矩阵 A A A 可作 QR 分解 或酉三角分解 。若在分解式 A = Q R A=QR A = QR 中,矩阵 A A A 是实方阵,Q Q Q 为正交矩阵 ,R R R 为上三角矩阵,则称分解式 A = Q R A=QR A = QR 为正交三角分解 。
课件紧接着抛出思考题:复方阵 A A A 在何种条件下可进行 QR 分解? 答案是:满秩就够了——而且满秩时还能附送一份「唯一性」,前提是给 R R R 戴上一条约定:「正线上三角阵」指对角元素全为正实数的上三角矩阵 (课件在定理 3.4.1 中首次使用这个词,此处先立此存照)。
定理 3.4.1 · QR 分解定理
若复方阵 A A A 满秩,则存在酉矩阵 Q Q Q 及正线上三角阵 R R R 满足
A = Q R A=QR A = QR
且分解唯一 。
课件给的分析只有三行,但字字有用——它把 QR 分解放回了 1.3 的「换基」框架:
记 A = [ a 1 , ⋯ , a n ] A=[\boldsymbol{a}_1,\cdots,\boldsymbol{a}_n] A = [ a 1 , ⋯ , a n ] ,Q = [ z 1 , ⋯ , z n ] Q=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_n] Q = [ z 1 , ⋯ , z n ] ,则 a 1 , ⋯ , a n \boldsymbol{a}_1,\cdots,\boldsymbol{a}_n a 1 , ⋯ , a n 和 z 1 , ⋯ , z n \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n z 1 , ⋯ , z n 均为 C n \mathbb C^n C n 的一组基。根据 QR 分解式知 [ a 1 , ⋯ , a n ] = [ z 1 , ⋯ , z n ] R [\boldsymbol{a}_1,\cdots,\boldsymbol{a}_n]=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_n]R [ a 1 , ⋯ , a n ] = [ z 1 , ⋯ , z n ] R ,其中矩阵 R R R 是从基 z 1 , ⋯ , z n \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n z 1 , ⋯ , z n 到基 a 1 , ⋯ , a n \boldsymbol{a}_1,\cdots,\boldsymbol{a}_n a 1 , ⋯ , a n 的过渡矩阵 。
于是「A A A 能否 QR 分解」被翻译成:「能否选一组标准正交基 z 1 , ⋯ , z n \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n z 1 , ⋯ , z n ,使得旧基 a 1 , ⋯ , a n \boldsymbol{a}_1,\cdots,\boldsymbol{a}_n a 1 , ⋯ , a n 在它下的过渡矩阵 R R R 是上三角 (再配正对角)」。而 Gram–Schmidt(Gram–Schmidt 正交化 )恰好就是干这个的:它的构造顺序「先定 z 1 \boldsymbol{z}_1 z 1 ,再用 z 1 \boldsymbol{z}_1 z 1 加工 z 2 \boldsymbol{z}_2 z 2 ,……」天然保证每个 a k \boldsymbol{a}_k a k 只用到前 k k k 个 z \boldsymbol{z} z ——这正是「上三角」三个字的算法化身。
存在性证明(课件路线:Gram–Schmidt 即算法,本编展开)
A A A 满秩 ⇒ \Rightarrow ⇒ a 1 , ⋯ , a n \boldsymbol{a}_1,\cdots,\boldsymbol{a}_n a 1 , ⋯ , a n 线性无关,是 C n \mathbb C^n C n 的基。对它执行 Gram–Schmidt(Gram–Schmidt 正交化 )并单位化:
y 1 = a 1 , y k = a k − ∑ i = 1 k − 1 ( a k , z i ) z i , z k = y k ∥ y k ∥ , k = 2 , ⋯ , n , \boldsymbol{y}_1=\boldsymbol{a}_1,\qquad \boldsymbol{y}_k=\boldsymbol{a}_k-\sum_{i=1}^{k-1}(\boldsymbol{a}_k,\boldsymbol{z}_i)\,\boldsymbol{z}_i,\qquad \boldsymbol{z}_k=\frac{\boldsymbol{y}_k}{\|\boldsymbol{y}_k\|},\quad k=2,\cdots,n, y 1 = a 1 , y k = a k − i = 1 ∑ k − 1 ( a k , z i ) z i , z k = ∥ y k ∥ y k , k = 2 , ⋯ , n ,
(标准正交组下 ( a k , z i ) ( z i , z i ) = ( a k , z i ) \dfrac{(\boldsymbol{a}_k,\boldsymbol{z}_i)}{(\boldsymbol{z}_i,\boldsymbol{z}_i)}=(\boldsymbol{a}_k,\boldsymbol{z}_i) ( z i , z i ) ( a k , z i ) = ( a k , z i ) ;各 y k ≠ 0 \boldsymbol{y}_k\neq\boldsymbol{0} y k = 0 由列无关保证——若 y k = 0 \boldsymbol{y}_k=\boldsymbol{0} y k = 0 ,则 a k \boldsymbol{a}_k a k 落进前 k − 1 k-1 k − 1 列的张成,Gram–Schmidt 正交化 的「张成不变」)。把构造式移项:
a k = ∑ i = 1 k − 1 ( a k , z i ) z i + ∥ y k ∥ z k = ∑ i = 1 k r i k z i , r i k = { ( a k , z i ) , i < k , ∥ y k ∥ , i = k , \boldsymbol{a}_k=\sum_{i=1}^{k-1}(\boldsymbol{a}_k,\boldsymbol{z}_i)\,\boldsymbol{z}_i+\|\boldsymbol{y}_k\|\,\boldsymbol{z}_k =\sum_{i=1}^{k}r_{ik}\boldsymbol{z}_i,\qquad r_{ik}=\begin{cases}(\boldsymbol{a}_k,\boldsymbol{z}_i),& i<k,\\[2pt] \|\boldsymbol{y}_k\|,& i=k,\end{cases} a k = i = 1 ∑ k − 1 ( a k , z i ) z i + ∥ y k ∥ z k = i = 1 ∑ k r ik z i , r ik = { ( a k , z i ) , ∥ y k ∥ , i < k , i = k ,
即 [ a 1 , ⋯ , a n ] = [ z 1 , ⋯ , z n ] R [\boldsymbol{a}_1,\cdots,\boldsymbol{a}_n]=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_n]R [ a 1 , ⋯ , a n ] = [ z 1 , ⋯ , z n ] R ,R R R 的元素恰如课件所列:
R = [ ∥ y 1 ∥ ( a 2 , z 1 ) ⋯ ( a n , z 1 ) ∥ y 2 ∥ ⋯ ( a n , z 2 ) ⋱ ⋮ 0 ∥ y n ∥ ] . R=\begin{bmatrix} \|\boldsymbol{y}_1\|&(\boldsymbol{a}_2,\boldsymbol{z}_1)&\cdots&(\boldsymbol{a}_n,\boldsymbol{z}_1)\\ &\|\boldsymbol{y}_2\|&\cdots&(\boldsymbol{a}_n,\boldsymbol{z}_2)\\ &&\ddots&\vdots\\ \boldsymbol{0}&&&\|\boldsymbol{y}_n\| \end{bmatrix}. R = ∥ y 1 ∥ 0 ( a 2 , z 1 ) ∥ y 2 ∥ ⋯ ⋯ ⋱ ( a n , z 1 ) ( a n , z 2 ) ⋮ ∥ y n ∥ .
令 Q = [ z 1 , ⋯ , z n ] Q=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_n] Q = [ z 1 , ⋯ , z n ] :各列标准正交的方阵是酉矩阵(列向量刻画 2.5.1 ),而 R R R 是上三角阵、对角元 ∥ y k ∥ > 0 \|\boldsymbol{y}_k\|>0 ∥ y k ∥ > 0 为正实数——正线 ✓。故 A = Q R A=QR A = QR 为所求分解。∎
∎
(注意对角元是残差 y k \boldsymbol{y}_k y k 的范数 ,不是 ∥ a k ∥ |\boldsymbol{a}_k| ∥ a k ∥ :先减掉在已有方向上的成分,剩下的才量长度。另外本节内积沿用全书的「第一变元线性」约定(定义 1.4.1 后的说明),系数 ( a k , z i ) (\boldsymbol{a}_k,\boldsymbol{z}_i) ( a k , z i ) 正是按这个约定从移项中读出来的。)
课件对唯一性只字未证。它值得补——因为证明里藏着一个此后反复使用的小事实(上三角的酉阵必为对角阵):
唯一性证明(课件未给,本编补:相差的只能是对角酉阵)
设 A = Q 1 R 1 = Q 2 R 2 A=Q_1R_1=Q_2R_2 A = Q 1 R 1 = Q 2 R 2 ,两组都满足「Q i Q_i Q i 酉、R i R_i R i 正线上三角」。满秩在这里进场 :rank R i = rank A = n \operatorname{rank}R_i=\operatorname{rank}A=n rank R i = rank A = n (乘酉矩阵不改秩,相似不变量 2.4.4 的秩款),故 R 1 R_1 R 1 、R 2 R_2 R 2 可逆。于是
Q 2 H Q 1 = R 2 R 1 − 1 = : W . Q_2^{\mathrm H}Q_1=R_2R_1^{-1}=:W . Q 2 H Q 1 = R 2 R 1 − 1 =: W .
左边是酉矩阵之积,仍是酉矩阵(正交 / 酉矩阵的运算性质 2.5.2 );右边是上三角阵之积再求逆,仍是上三角阵,且对角元 = = = 正 / / / 正 > 0 >0 > 0 。下面证明:既是上三角又是酉、且对角为正的矩阵只能是 I I I 。对列归纳:
第 1 1 1 列只有 w 11 w_{11} w 11 一个可能非零的分量(下三角部分为零),而酉矩阵各列范数为 1 1 1 ,故 ∣ w 11 ∣ = 1 |w_{11}|=1 ∣ w 11 ∣ = 1 ;
设前 j − 1 j-1 j − 1 列已是 e 1 , ⋯ , e j − 1 \boldsymbol{e}_1,\cdots,\boldsymbol{e}_{j-1} e 1 , ⋯ , e j − 1 。第 j j j 列与它们正交:⟨ 列 j , 列 i ⟩ = w i i ‾ w i j = 0 \langle\text{列}j,\text{列}i\rangle=\overline{w_{ii}}\,w_{ij}=0 ⟨ 列 j , 列 i ⟩ = w ii w ij = 0 ,逐个推出 w i j = 0 w_{ij}=0 w ij = 0 (i < j i<j i < j );再由范数 1 1 1 得 ∣ w j j ∣ = 1 |w_{jj}|=1 ∣ w jj ∣ = 1 。
于是 W W W 是对角阵且 ∣ w i i ∣ = 1 |w_{ii}|=1 ∣ w ii ∣ = 1 ;对角为正实数迫使 w i i = 1 w_{ii}=1 w ii = 1 ,即 W = I W=I W = I 。代回:Q 2 H Q 1 = I ⇒ Q 1 = Q 2 Q_2^{\mathrm H}Q_1=I\Rightarrow Q_1=Q_2 Q 2 H Q 1 = I ⇒ Q 1 = Q 2 ,R 2 R 1 − 1 = I ⇒ R 2 = R 1 R_2R_1^{-1}=I\Rightarrow R_2=R_1 R 2 R 1 − 1 = I ⇒ R 2 = R 1 。∎
读出两件事 :① 唯一性的全部关键在「正线」——它把对角酉阵那一圈自由度(相角 / 正负号)锁死成 1 1 1 ;② 证明第一步就用了 R 1 R_1 R 1 可逆,不满秩时论证整体失效 (届时分解是否存在、是否唯一都要重新问,见 3.4.2 的例 3.4.2)。
∎
先看手算一遍的感觉——一个小而完整的 GS 分解:
例 3.4.A(新增)· 用 Gram–Schmidt 手算一个 QR 分解
求 A = [ 3 1 4 2 ] A=\begin{bmatrix}3&1\\ 4&2\end{bmatrix} A = [ 3 4 1 2 ] 的 QR 分解(Q Q Q 正交、R R R 正线上三角)。
解答 · 例 3.4.A
det A = 2 ≠ 0 \det A=2\neq0 det A = 2 = 0 ,满秩 ✓,可套 定理 3.4.1 。记 a 1 = ( 3 , 4 ) T \boldsymbol{a}_1=(3,4)^{\mathrm T} a 1 = ( 3 , 4 ) T 、a 2 = ( 1 , 2 ) T \boldsymbol{a}_2=(1,2)^{\mathrm T} a 2 = ( 1 , 2 ) T 。
第一步(正交化) :y 1 = a 1 \boldsymbol{y}_1=\boldsymbol{a}_1 y 1 = a 1 ,∥ y 1 ∥ = 5 \|\boldsymbol{y}_1\|=5 ∥ y 1 ∥ = 5 ,z 1 = ( 3 5 , 4 5 ) T \boldsymbol{z}_1=\left(\tfrac35,\tfrac45\right)^{\mathrm T} z 1 = ( 5 3 , 5 4 ) T ;
( a 2 , z 1 ) = 3 5 + 8 5 = 11 5 , y 2 = a 2 − 11 5 z 1 = ( − 8 25 , 6 25 ) T , ∥ y 2 ∥ = 2 5 , z 2 = ( − 4 5 , 3 5 ) T . (\boldsymbol{a}_2,\boldsymbol{z}_1)=\tfrac35+\tfrac85=\tfrac{11}{5},\qquad \boldsymbol{y}_2=\boldsymbol{a}_2-\tfrac{11}{5}\boldsymbol{z}_1=\left(-\tfrac{8}{25},\ \tfrac{6}{25}\right)^{\mathrm T},\qquad \|\boldsymbol{y}_2\|=\tfrac{2}{5},\ \ \boldsymbol{z}_2=\left(-\tfrac45,\ \tfrac35\right)^{\mathrm T}. ( a 2 , z 1 ) = 5 3 + 5 8 = 5 11 , y 2 = a 2 − 5 11 z 1 = ( − 25 8 , 25 6 ) T , ∥ y 2 ∥ = 5 2 , z 2 = ( − 5 4 , 5 3 ) T .
第二步(读出 R R R ) :r 11 = ∥ y 1 ∥ = 5 r_{11}=\|\boldsymbol{y}_1\|=5 r 11 = ∥ y 1 ∥ = 5 ,r 22 = ∥ y 2 ∥ = 2 5 r_{22}=\|\boldsymbol{y}_2\|=\tfrac25 r 22 = ∥ y 2 ∥ = 5 2 ,r 12 = ( a 2 , z 1 ) = 11 5 r_{12}=(\boldsymbol{a}_2,\boldsymbol{z}_1)=\tfrac{11}{5} r 12 = ( a 2 , z 1 ) = 5 11 。
拼装与验算 :
Q = [ 3 5 − 4 5 4 5 3 5 ] , R = [ 5 11 5 0 2 5 ] , Q R = [ 3 33 25 − 8 25 4 44 25 + 6 25 ] = [ 3 1 4 2 ] = A ✓ Q=\begin{bmatrix}\tfrac35&-\tfrac45\\ \tfrac45&\tfrac35\end{bmatrix},\qquad R=\begin{bmatrix}5&\tfrac{11}{5}\\ 0&\tfrac25\end{bmatrix},\qquad QR=\begin{bmatrix}3&\tfrac{33}{25}-\tfrac{8}{25}\\ 4&\tfrac{44}{25}+\tfrac{6}{25}\end{bmatrix}=\begin{bmatrix}3&1\\ 4&2\end{bmatrix}=A\ \checkmark Q = [ 5 3 5 4 − 5 4 5 3 ] , R = [ 5 0 5 11 5 2 ] , QR = [ 3 4 25 33 − 25 8 25 44 + 25 6 ] = [ 3 4 1 2 ] = A ✓
且 Q T Q = I Q^{\mathrm T}Q=I Q T Q = I 、det Q = 9 25 + 16 25 = 1 \det Q=\tfrac{9}{25}+\tfrac{16}{25}=1 det Q = 25 9 + 25 16 = 1 ✓,R R R 正线上三角 ✓。
读法 :R R R 是「从 z \boldsymbol{z} z 基到 a \boldsymbol{a} a 基」的过渡矩阵——a 2 = 11 5 z 1 + 2 5 z 2 \boldsymbol{a}_2=\tfrac{11}{5}\boldsymbol{z}_1+\tfrac25\boldsymbol{z}_2 a 2 = 5 11 z 1 + 5 2 z 2 正是 R R R 第二列。另外这个 Q = [ cos θ − sin θ sin θ cos θ ] Q=\begin{bmatrix}\cos\theta&-\sin\theta\\ \sin\theta&\cos\theta\end{bmatrix} Q = [ cos θ sin θ − sin θ cos θ ] (cos θ = 3 5 \cos\theta=\tfrac35 cos θ = 5 3 ,sin θ = 4 5 \sin\theta=\tfrac45 sin θ = 5 4 )就是 2.5 的 Givens 旋转 (Givens 旋转矩阵 2.5.3 ):二维的 QR 分解 = 把坐标系转正——这不是巧合,是把平面「掰直」的代数痕迹。∎
课件用一个最小的反例说明「正线」这根线不能抽掉:
注 1(课件原文)· 不要求对角元为正实数,则 QR 分解不唯一
若不要求上三角阵 R R R 的对角元素全为正实数,则导致矩阵 A A A 的 QR 分解不唯一。
例 3.4.1(课件原文)· 单位阵的两种 QR 分解
考查 I 2 I_2 I 2 的 QR 分解:
I 2 = [ 1 0 0 1 ] [ 1 0 0 1 ] ≜ Q R , I 2 = [ − 1 0 0 1 ] [ − 1 0 0 1 ] ≜ Q 1 R 1 . I_2=\begin{bmatrix}1&0\\ 0&1\end{bmatrix}\begin{bmatrix}1&0\\ 0&1\end{bmatrix}\triangleq QR,\qquad I_2=\begin{bmatrix}-1&0\\ 0&1\end{bmatrix}\begin{bmatrix}-1&0\\ 0&1\end{bmatrix}\triangleq Q_1R_1 . I 2 = [ 1 0 0 1 ] [ 1 0 0 1 ] ≜ QR , I 2 = [ − 1 0 0 1 ] [ − 1 0 0 1 ] ≜ Q 1 R 1 .
两个分解里的 Q Q Q 、Q 1 Q_1 Q 1 都是正交矩阵、R R R 、R 1 R_1 R 1 都是上三角矩阵,但 R 1 R_1 R 1 的第一个对角元是 − 1 -1 − 1 ——正线被破坏,唯一性随之失效。
(本编补一句:I 2 I_2 I 2 的这两个分解连 R R R 都不同,说明自由度在「符号 / 相角」而不只在 Q Q Q ;下一个注把自由度数清。)
本编补注 · 不唯一的程度:恰好相差一个对角酉阵
唯一性证明的最后一步其实已经把账算清了:若 A = Q R = Q ′ R ′ A=QR=Q'R' A = QR = Q ′ R ′ 是满秩方阵的两种 QR 分解(只要求 R R R 、R ′ R' R ′ 为可逆 上三角阵),则
W = R ′ R − 1 = Q ′ H Q W=R'R^{-1}=Q'^{\mathrm H}Q W = R ′ R − 1 = Q ′ H Q
既是酉阵又是上三角阵,故 W = diag ( w 1 , ⋯ , w n ) W=\operatorname{diag}(w_1,\cdots,w_n) W = diag ( w 1 , ⋯ , w n ) ,∣ w i ∣ = 1 |w_i|=1 ∣ w i ∣ = 1 (上面归纳证明的前半段,不需要正线)。于是任意两种分解恰好相差一个对角酉阵 :
Q ′ = Q W , R ′ = W H R ( 对角元变为 w i ‾ r i i ) . Q'=QW,\qquad R'=W^{\mathrm H}R\quad(\text{对角元变为 }\overline{w_i}\,r_{ii}). Q ′ = Q W , R ′ = W H R ( 对角元变为 w i r ii ) .
实方阵 :w i = ± 1 w_i=\pm1 w i = ± 1 ,故 n n n 阶实满秩方阵恰有 2 n 2^n 2 n 种 QR 分解——「正线」从 2 n 2^n 2 n 里选出唯一的 1 1 1 个;
复方阵 :w i = e i θ i w_i=e^{\mathrm i\theta_i} w i = e i θ i 可以连续取值,不要求正线时分解有无穷多(一族 n n n 维相角)。
这也解释了注 1 的措辞为什么是「导致 不唯一」:正线不是存在性条件,而是从这一族分解里挑出唯一代表 的规约。
例 3.4.B(新增 · 承接例 3.4.A)· 数清一个矩阵的全部 QR 分解
写出 A = [ 3 1 4 2 ] A=\begin{bmatrix}3&1\\ 4&2\end{bmatrix} A = [ 3 4 1 2 ] (例 3.4.A )的全部 QR 分解(Q Q Q 正交、R R R 可逆上三角,不要求正线),并指出其中哪一个是正线版本。
解答 · 例 3.4.B(新增
由本编补注,全部分解由对角正交阵 D = diag ( ± 1 , ± 1 ) D=\operatorname{diag}(\pm1,\pm1) D = diag ( ± 1 , ± 1 ) 从正线版本 ( Q , R ) (Q,R) ( Q , R ) 生成:( Q D , D R ) (QD,\ DR) ( Q D , D R ) 。共 2 2 = 4 2^2=4 2 2 = 4 种:
( [ 3 5 − 4 5 4 5 3 5 ] , [ 5 11 5 0 2 5 ] ) , ( [ − 3 5 − 4 5 − 4 5 3 5 ] , [ − 5 − 11 5 0 2 5 ] ) , ( [ 3 5 4 5 4 5 − 3 5 ] , [ 5 11 5 0 − 2 5 ] ) , ( [ − 3 5 4 5 − 4 5 − 3 5 ] , [ − 5 − 11 5 0 − 2 5 ] ) . \begin{aligned} &\left(\begin{bmatrix}\tfrac35&-\tfrac45\\ \tfrac45&\tfrac35\end{bmatrix},\ \begin{bmatrix}5&\tfrac{11}{5}\\ 0&\tfrac25\end{bmatrix}\right), &&\left(\begin{bmatrix}-\tfrac35&-\tfrac45\\ -\tfrac45&\tfrac35\end{bmatrix},\ \begin{bmatrix}-5&-\tfrac{11}{5}\\ 0&\tfrac25\end{bmatrix}\right),\\[6pt] &\left(\begin{bmatrix}\tfrac35&\tfrac45\\ \tfrac45&-\tfrac35\end{bmatrix},\ \begin{bmatrix}5&\tfrac{11}{5}\\ 0&-\tfrac25\end{bmatrix}\right), &&\left(\begin{bmatrix}-\tfrac35&\tfrac45\\ -\tfrac45&-\tfrac35\end{bmatrix},\ \begin{bmatrix}-5&-\tfrac{11}{5}\\ 0&-\tfrac25\end{bmatrix}\right). \end{aligned} ( [ 5 3 5 4 − 5 4 5 3 ] , [ 5 0 5 11 5 2 ] ) , ( [ 5 3 5 4 5 4 − 5 3 ] , [ 5 0 5 11 − 5 2 ] ) , ( [ − 5 3 − 5 4 − 5 4 5 3 ] , [ − 5 0 − 5 11 5 2 ] ) , ( [ − 5 3 − 5 4 5 4 − 5 3 ] , [ − 5 0 − 5 11 − 5 2 ] ) .
(验算其一:D = diag ( 1 , − 1 ) D=\operatorname{diag}(1,-1) D = diag ( 1 , − 1 ) 时 ( Q D ) ( D R ) = Q D 2 R = Q R = A (QD)(DR)=Q D^2 R=QR=A ( Q D ) ( D R ) = Q D 2 R = QR = A ✓,且 D R DR D R 仍上三角、对角 ( 5 , − 2 5 ) (5,-\tfrac25) ( 5 , − 5 2 ) 。)正线版本只有第一个 ——r 11 > 0 r_{11}>0 r 11 > 0 逼出 d 1 = 1 d_1=1 d 1 = 1 ,r 22 > 0 r_{22}>0 r 22 > 0 逼出 d 2 = 1 d_2=1 d 2 = 1 ,两条合起来 D = I D=I D = I 。∎
定理 3.4.1 只管满了秩的方阵。课件接着追问两步:不满秩的复方阵是否可作 QR 分解?长方矩阵呢? 两个答案都在例子里。
例 3.4.2(课件原文)· 不满秩方阵:分解仍在,正线没了
考察矩阵 A = [ 1 1 0 0 ] A=\begin{bmatrix}1&1\\ 0&0\end{bmatrix} A = [ 1 0 1 0 ] 的 QR 分解。
解答(课件路线,本编补细节)
rank A = 1 < 2 \operatorname{rank}A=1<2 rank A = 1 < 2 :不满秩。取 a 1 = ( 1 , 0 ) T \boldsymbol{a}_1=(1,0)^{\mathrm T} a 1 = ( 1 , 0 ) T ,它张成列空间 R ( A ) R(A) R ( A ) 且已是单位向量——R ( A ) R(A) R ( A ) 的标准正交基;再补 e 2 \boldsymbol{e}_2 e 2 得 C 2 \mathbb C^2 C 2 的标准正交基,于是 Q = I 2 Q=I_2 Q = I 2 ,且
A = [ 1 0 0 1 ] [ 1 1 0 0 ] ≜ Q R , A=\begin{bmatrix}1&0\\ 0&1\end{bmatrix}\begin{bmatrix}1&1\\ 0&0\end{bmatrix}\triangleq QR, A = [ 1 0 0 1 ] [ 1 0 1 0 ] ≜ QR ,
其中 R R R 的第二行全零(a 2 = a 1 \boldsymbol{a}_2=\boldsymbol{a}_1 a 2 = a 1 落在已有方向上,GS 的残差 y 2 = 0 \boldsymbol{y}_2=\boldsymbol{0} y 2 = 0 )——R R R 不再是正线上三角矩阵 (r 22 = 0 r_{22}=0 r 22 = 0 )。
(本编补:此时 定理 3.4.1 的唯一性彻底失效——R R R 不可逆,唯一性证明第一步就走不动;而且自由度比「对角酉阵」大得多:第二个标准正交向量可换成 e i θ e 2 e^{\mathrm i\theta}\boldsymbol{e}_2 e i θ e 2 (任意相角),更高维、秩亏更多的情形里,「补齐」一列甚至可以在整个正交补里任选。结论:存在性常在,唯一性需要满秩 + + + 正线 。)∎
长方阵的例子需要先安一个定义——「列正交」的矩阵不必是方阵,酉矩阵的刻画(列向量刻画 2.5.1 )要放宽使用:
定义 3.4.2 · 列 / 行正交规范矩阵
设 Q ∈ C m × n Q\in\mathbb C^{m\times n} Q ∈ C m × n 。若
Q H Q = I n , Q^{\mathrm H}Q=I_n, Q H Q = I n ,
则矩阵 Q Q Q 称为列正交规范矩阵 ,Q H Q^{\mathrm H} Q H 称为行正交规范矩阵 。
(读法:Q H Q = I n Q^{\mathrm H}Q=I_n Q H Q = I n 逐元读出即「各列长度 1 1 1 、两两正交」——正是 列向量刻画 2.5.1 对长方 情形的自然放宽:n n n 列标准正交,但 m > n m>n m > n 时它们只是 C m \mathbb C^m C m 的一部分基。注意 Q Q H ≠ I m QQ^{\mathrm H}\neq I_m Q Q H = I m (把 m m m 维向量先压到 n n n 维再放回去,补空间被抹掉了),故列正交规范的长方阵不是酉矩阵 。它自动列满秩,Q H Q^{\mathrm H} Q H 是它的一个左逆——定理 3.1.1 的一号应用;它还保范:∥ Q x ∥ 2 = x H Q H Q x = ∥ x ∥ 2 |Q\boldsymbol{x}|^2=\boldsymbol{x}^{\mathrm H}Q^{\mathrm H}Q\boldsymbol{x}=|\boldsymbol{x}|^2 ∥ Q x ∥ 2 = x H Q H Q x = ∥ x ∥ 2 。)
例 3.4.3(课件原文,含一处课件笔误,见 E3.6)· 长方矩阵的分解
考察矩阵 B = [ 3 3 0 1 4 4 ] B=\begin{bmatrix}3&3\\ 0&1\\ 4&4\end{bmatrix} B = 3 0 4 3 1 4 (3 × 2 3\times2 3 × 2 ,列满秩)的分解问题。
解答(课件路线;B 的 ( 3 , 2 ) (3,2) ( 3 , 2 ) 元课件印作 0 0 0 ,据其后全部公式反推应为 4 4 4 ,见勘误 E3.6)
第一步(GS 正交化两列) :a 1 = ( 3 , 0 , 4 ) T \boldsymbol{a}_1=(3,0,4)^{\mathrm T} a 1 = ( 3 , 0 , 4 ) T ,∥ a 1 ∥ = 5 \|\boldsymbol{a}_1\|=5 ∥ a 1 ∥ = 5 ,z 1 = ( 3 5 , 0 , 4 5 ) T \boldsymbol{z}_1=\left(\tfrac35,0,\tfrac45\right)^{\mathrm T} z 1 = ( 5 3 , 0 , 5 4 ) T ;
( a 2 , z 1 ) = 9 5 + 16 5 = 5 , y 2 = a 2 − 5 z 1 = ( 0 , 1 , 0 ) T , ∥ y 2 ∥ = 1 , z 2 = ( 0 , 1 , 0 ) T . (\boldsymbol{a}_2,\boldsymbol{z}_1)=\tfrac{9}{5}+\tfrac{16}{5}=5,\qquad \boldsymbol{y}_2=\boldsymbol{a}_2-5\boldsymbol{z}_1=(0,1,0)^{\mathrm T},\qquad \|\boldsymbol{y}_2\|=1,\ \ \boldsymbol{z}_2=(0,1,0)^{\mathrm T}. ( a 2 , z 1 ) = 5 9 + 5 16 = 5 , y 2 = a 2 − 5 z 1 = ( 0 , 1 , 0 ) T , ∥ y 2 ∥ = 1 , z 2 = ( 0 , 1 , 0 ) T .
(y 2 \boldsymbol{y}_2 y 2 正好落在 e 2 \boldsymbol{e}_2 e 2 上——这正是课件选这组数据的原因:第二列减掉在 z 1 \boldsymbol{z}_1 z 1 上的成分后残差是现成的坐标向量。)
B = [ 3 5 0 0 1 4 5 0 ] [ 5 5 0 1 ] ≜ Q 1 R 1 , Q 1 ∈ C 3 × 2 , R 1 ∈ C 2 × 2 , B=\begin{bmatrix}\tfrac35&0\\ 0&1\\ \tfrac45&0\end{bmatrix}\begin{bmatrix}5&5\\ 0&1\end{bmatrix}\triangleq Q_1R_1,\qquad Q_1\in\mathbb C^{3\times2},\ R_1\in\mathbb C^{2\times2}, B = 5 3 0 5 4 0 1 0 [ 5 0 5 1 ] ≜ Q 1 R 1 , Q 1 ∈ C 3 × 2 , R 1 ∈ C 2 × 2 ,
其中 Q 1 Q_1 Q 1 是列正交规范矩阵(验算 Q 1 H Q 1 = I 2 Q_1^{\mathrm H}Q_1=I_2 Q 1 H Q 1 = I 2 ✓),R 1 R_1 R 1 是正线上三角阵 ✓。验算 Q 1 R 1 Q_1R_1 Q 1 R 1 :第一列 5 z 1 = ( 3 , 0 , 4 ) T 5\boldsymbol{z}_1=(3,0,4)^{\mathrm T} 5 z 1 = ( 3 , 0 , 4 ) T ✓,第二列 5 z 1 + z 2 = ( 3 , 1 , 4 ) T 5\boldsymbol{z}_1+\boldsymbol{z}_2=(3,1,4)^{\mathrm T} 5 z 1 + z 2 = ( 3 , 1 , 4 ) T ✓。∎
例 3.4.3 续(课件原文)· 补齐成完全分解
再考察矩阵 B = [ 3 3 0 1 4 4 ] B=\begin{bmatrix}3&3\\ 0&1\\ 4&4\end{bmatrix} B = 3 0 4 3 1 4 的分解问题:把 Q 1 Q_1 Q 1 的两列补齐 C 3 \mathbb C^3 C 3 的一组标准正交基。
解答(第二步:补齐)
补齐 C 3 \mathbb C^3 C 3 的标准正交基 :再取 z 3 = ( − 4 5 , 0 , 3 5 ) T \boldsymbol{z}_3=\left(-\tfrac45,0,\tfrac35\right)^{\mathrm T} z 3 = ( − 5 4 , 0 , 5 3 ) T ——与 z 1 \boldsymbol{z}_1 z 1 (内积 − 12 25 + 12 25 = 0 -\tfrac{12}{25}+\tfrac{12}{25}=0 − 25 12 + 25 12 = 0 ✓)、z 2 \boldsymbol{z}_2 z 2 (内积 0 0 0 ✓)都正交且单位。于是
Q 1 = [ 3 5 0 0 1 4 5 0 ] ⟶ Q = [ 3 5 0 − 4 5 0 1 0 4 5 0 3 5 ] ( 酉矩阵 ) , Q_1=\begin{bmatrix}\tfrac35&0\\ 0&1\\ \tfrac45&0\end{bmatrix}\ \longrightarrow\ Q=\begin{bmatrix}\tfrac35&0&-\tfrac45\\ 0&1&0\\ \tfrac45&0&\tfrac35\end{bmatrix}\quad(\text{酉矩阵}), Q 1 = 5 3 0 5 4 0 1 0 ⟶ Q = 5 3 0 5 4 0 1 0 − 5 4 0 5 3 ( 酉矩阵 ) ,
B = [ 3 5 0 − 4 5 0 1 0 4 5 0 3 5 ] [ 5 5 0 1 0 0 ] = Q R . B=\begin{bmatrix}\tfrac35&0&-\tfrac45\\ 0&1&0\\ \tfrac45&0&\tfrac35\end{bmatrix}\begin{bmatrix}5&5\\ 0&1\\ 0&0\end{bmatrix}=QR . B = 5 3 0 5 4 0 1 0 − 5 4 0 5 3 5 0 0 5 1 0 = QR .
R = [ R 1 0 ] 3 × 2 R=\begin{bmatrix}R_1\\ \boldsymbol{0}\end{bmatrix}_{3\times2} R = [ R 1 0 ] 3 × 2 :上面是 2 × 2 2\times2 2 × 2 正线上三角 R 1 R_1 R 1 ,下面垫一行零。∎
把这个例子的结构抽出来,就是课件的推论——列满秩长方阵的完全 QR 分解 :
推论 3.4.1 · 列满秩长方阵
设 A ∈ C n m × n A\in\mathbb C^{m\times n}_n A ∈ C n m × n (列满秩,n ≤ m n\le m n ≤ m ),则 A A A 可分解为
A = U R , R = [ R 1 0 ( m − n ) × n ] m × n , A=UR,\qquad R=\begin{bmatrix}R_1\\ \boldsymbol{0}_{(m-n)\times n}\end{bmatrix}_{m\times n}, A = U R , R = [ R 1 0 ( m − n ) × n ] m × n ,
其中 U U U 是 m m m 阶酉矩阵,R 1 R_1 R 1 为正线上三角阵。
证明(课件未给,本编补:GS + + + 基扩充)
GS :A A A 列满秩 ⇒ \Rightarrow ⇒ 各列线性无关 ⇒ \Rightarrow ⇒ GS 各步残差 y k ≠ 0 \boldsymbol{y}_k\neq\boldsymbol{0} y k = 0 ,得标准正交组 z 1 , ⋯ , z n \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n z 1 , ⋯ , z n 与 A = Q 1 R 1 A=Q_1R_1 A = Q 1 R 1 (Q 1 ∈ C m × n Q_1\in\mathbb C^{m\times n} Q 1 ∈ C m × n 列正交规范,R 1 R_1 R 1 正线上三角——定理 3.4.1 存在性证明逐字照搬,只是不再补满 n n n 列)。
补齐 :把 z 1 , ⋯ , z n \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n z 1 , ⋯ , z n 扩充为 C m \mathbb C^m C m 的一组基(推论 1.3.1 ),再对扩充后的整组做 GS——由「张成不变」(Gram–Schmidt 正交化 ),前 n n n 个向量原封不动 ,只把新添的向量逐一正交化、单位化,得标准正交基 z 1 , ⋯ , z n , z n + 1 , ⋯ , z m \boldsymbol{z}_1,\cdots,\boldsymbol{z}_n,\boldsymbol{z}_{n+1},\cdots,\boldsymbol{z}_m z 1 , ⋯ , z n , z n + 1 , ⋯ , z m 。令 U = [ z 1 , ⋯ , z m ] U=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_m] U = [ z 1 , ⋯ , z m ] (列标准正交的方阵,酉,列向量刻画 2.5.1 ),则
U [ R 1 0 ] = [ z 1 , ⋯ , z n ] R 1 + 0 = Q 1 R 1 = A . ■ U\begin{bmatrix}R_1\\ \boldsymbol{0}\end{bmatrix}=[\boldsymbol{z}_1,\cdots,\boldsymbol{z}_n]R_1+\boldsymbol{0}=Q_1R_1=A.\qquad\blacksquare U [ R 1 0 ] = [ z 1 , ⋯ , z n ] R 1 + 0 = Q 1 R 1 = A . ■
∎
读法(本编提炼)· QR 分解是满秩分解的「正交升级」
对照 3.2 :满秩分解 A = B C A=BC A = BC 里,B B B 的列是 R ( A ) R(A) R ( A ) 的任意 一组基。现在 推论 3.4.1 说:A A A 列满秩时,把 B B B 的列掰成标准正交基 (Q 1 Q_1 Q 1 )、坐标表 C C C 就自动变成上三角 (R 1 R_1 R 1 ):
A = Q 1 ⏟ B 的正交版 R 1 ⏟ C 的上三角版 (列满秩时 r = n ) . A=\underbrace{Q_1}_{B\ \text{的正交版}}\ \underbrace{R_1}_{C\ \text{的上三角版}}\qquad\text{(列满秩时 } r=n \text{)}. A = B 的正交版 Q 1 C 的上三角版 R 1 (列满秩时 r = n ) .
「上三角」的含义在过渡矩阵读法里看得分明:每个 a k \boldsymbol{a}_k a k 只用前 k k k 个标准正交方向表出 ——第 k k k 根梁只搭在更早立好的轴上。所以 QR 分解 = 满秩分解 + + + 「基按 GS 顺序立轴」。方阵满秩时(定理 3.4.1 ),A = Q R A=QR A = QR 本身就是一个满秩分解(Q Q Q 列满秩、R R R 满秩方阵自然行满秩);不满秩时(例 3.4.2 型),坐标表出现零行 ——对应 GS 中「残差为零、无需新轴」的退化步。
到此为止,QR 只是「一种好看的分解」。课件接下来的一页给它加了一个头衔——
QR 算法 :计算小规模矩阵所有特征值稳定有效的方法,二十世纪在科学和工程上有最大贡献与影响的十大算法 之一。
(本编注:所谓「十大算法」指 2000 年 IEEE《Computing in Science & Engineering》评选的「世纪十大算法」,与快速傅里叶变换、单纯形法等并列;QR 算法由 J. G. F. Francis 于 1961 年前后提出,至今仍是稠密矩阵特征值计算的标准内核。)算法本身只有三行:
QR 算法(课件原文,格式化排版)
输入 :可逆阵 A A A (n n n 阶复方阵)。令 A 1 = A A_1=A A 1 = A 。对 k = 1 , 2 , ⋯ k=1,2,\cdots k = 1 , 2 , ⋯ 循环:
对 A k A_k A k 作 QR 分解:A k = Q k R k A_k=Q_kR_k A k = Q k R k ;
令 A k + 1 = R k Q k A_{k+1}=R_kQ_k A k + 1 = R k Q k (交换左右 )。
收敛 :若可逆阵 A A A 的各特征值模值互不相同,则序列 { A k } \{A_k\} { A k } 收敛于一个上三角阵,此时上三角阵的对角元素即为 A A A 的特征值。
为什么「交换左右再乘回去」能挤出一个上三角阵?课件用一道思考题点破了机关——每一步迭代都是一次酉相似 :
思考的解答(课件分析):为什么收敛的上三角阵的对角元素就是 A A A 的特征值
由 A k = Q k R k A_k=Q_kR_k A k = Q k R k 得 R k = Q k H A k R_k=Q_k^{\mathrm H}A_k R k = Q k H A k ,代回迭代式:
A k + 1 = R k Q k = Q k H A k Q k , A_{k+1}=R_kQ_k=Q_k^{\mathrm H}A_kQ_k, A k + 1 = R k Q k = Q k H A k Q k ,
即 A k + 1 A_{k+1} A k + 1 与 A k A_k A k 相似 (而且是酉相似),它们具有相同的特征值。递推成链:
A k = ( Q 1 Q 2 ⋯ Q k − 1 ) H A ( Q 1 Q 2 ⋯ Q k − 1 ) , k = 1 , 2 , ⋯ , A_k=(Q_1Q_2\cdots Q_{k-1})^{\mathrm H}\,A\,(Q_1Q_2\cdots Q_{k-1}),\qquad k=1,2,\cdots, A k = ( Q 1 Q 2 ⋯ Q k − 1 ) H A ( Q 1 Q 2 ⋯ Q k − 1 ) , k = 1 , 2 , ⋯ ,
故每个 A k A_k A k 都与 A A A 相似 、特征值始终不变(相似不变量 2.4.4 )。若 A k → Λ A_k\to\Lambda A k → Λ (上三角),则由特征多项式各系数随矩阵元连续,Λ \Lambda Λ 的特征值也是 A A A 的特征值;而上三角阵的特征值就是对角元——对角元素即 A A A 的特征值 。QR 算法利用矩阵乘法和 QR 分解实现了特征值求解。∎
∎
(相似性保证的是「如果 收敛,极限必是特征值」;「是否收敛」由「模值互异」这一充分条件担保——它的边界见本小节末的本编注。另外注意迭代里隐藏的排序:模互异时对角元按模从大到小 排定,下面的例子里 4.7321 > 3 > 1.2679 4.7321>3>1.2679 4.7321 > 3 > 1.2679 正是这个次序。)
例 3.4.4(课件原文,本编核算并改一处印误,见 E3.7)· 用 QR 算法求特征值
利用 QR 分解求矩阵 A = [ 2 1 0 1 3 1 0 1 4 ] A=\begin{bmatrix}2&1&0\\ 1&3&1\\ 0&1&4\end{bmatrix} A = 2 1 0 1 3 1 0 1 4 的特征值。
解答(课件路线;数值由本编按同一算法双精度复核)
第一步(分解 A 1 A_1 A 1 ) :A 1 = A = Q 1 R 1 A_1=A=Q_1R_1 A 1 = A = Q 1 R 1 。按 GS(正线版本,四位小数):
Q 1 = [ 0.8944 − 0.4082 0.1826 0.4472 0.8165 − 0.3651 0 0.4082 0.9129 ] , R 1 = [ 2.2361 2.2361 0.4472 0 2.4495 2.4495 0 0 3.2863 ] . Q_1=\begin{bmatrix}0.8944&-0.4082&0.1826\\ 0.4472&0.8165&-0.3651\\ 0&0.4082&0.9129\end{bmatrix},\qquad R_1=\begin{bmatrix}2.2361&2.2361&0.4472\\ 0&2.4495&2.4495\\ 0&0&3.2863\end{bmatrix}. Q 1 = 0.8944 0.4472 0 − 0.4082 0.8165 0.4082 0.1826 − 0.3651 0.9129 , R 1 = 2.2361 0 0 2.2361 2.4495 0 0.4472 2.4495 3.2863 .
(课件此页把 Q 1 Q_1 Q 1 的第 1 1 1 、2 2 2 列连同 R 1 R_1 R 1 的第 1 1 1 、2 2 2 行取了相反符号——R 1 R_1 R 1 对角出现两个负数,不合正线约定;又把 Q 1 Q_1 Q 1 的 ( 2 , 3 ) (2,3) ( 2 , 3 ) 元印作 − 0.3561 -0.3561 − 0.3561 ,按 GS 应为 − 0.3651 -0.3651 − 0.3651 ,见勘误 E3.7。上面给出的是规约后的正确版本,验算 Q 1 R 1 = A Q_1R_1=A Q 1 R 1 = A 至四位小数 ✓。)
第二步(迭代) :A 2 = R 1 Q 1 A_2=R_1Q_1 A 2 = R 1 Q 1 ,再分解、再交换,往复。课件报告:
A 10 = [ 4.7282 0.0781 0 0.0781 3.0035 − 0.0020 0 0.0048 1.2680 ] , A 20 = [ 4.7321 0.0008 0 0.0008 3.0000 0 0 0 1.2679 ] . A_{10}=\begin{bmatrix}4.7282&0.0781&0\\ 0.0781&3.0035&-0.0020\\ 0&0.0048&1.2680\end{bmatrix},\qquad A_{20}=\begin{bmatrix}4.7321&0.0008&0\\ 0.0008&3.0000&0\\ 0&0&1.2679\end{bmatrix}. A 10 = 4.7282 0.0781 0 0.0781 3.0035 0.0048 0 − 0.0020 1.2680 , A 20 = 4.7321 0.0008 0 0.0008 3.0000 0 0 0 1.2679 .
非对角元逐轮衰减:k = 10 k=10 k = 10 时约 1 0 − 2 10^{-2} 1 0 − 2 ,k = 20 k=20 k = 20 时约 1 0 − 3 10^{-3} 1 0 − 3 ——序列肉眼可见地收敛到上三角阵。
(本编复算注:用双精度 Householder QR 复核同一迭代,A 10 A_{10} A 10 的最大非对角元约 5 × 1 0 − 2 5\times10^{-2} 5 × 1 0 − 2 、A 20 A_{20} A 20 约 5 × 1 0 − 4 5\times10^{-4} 5 × 1 0 − 4 ,与课件的 0.0781 0.0781 0.0781 、0.0008 0.0008 0.0008 同数量级但不逐位相同——中间数值随实现与舍入(课件全程四位数)而异;对角元的收敛位置则完全一致 。)
第三步(读特征值) :对比该矩阵特征值精确解(本编补推导):
f A ( λ ) = det ( λ I − A ) = ( λ − 3 ) [ ( λ − 3 ) 2 − 3 ] , λ 1 = 3 + 3 = 4.7321 , λ 2 = 3 , λ 3 = 3 − 3 = 1.2679 , f_A(\lambda)=\det(\lambda I-A)=(\lambda-3)\big[(\lambda-3)^2-3\big],\qquad \lambda_1=3+\sqrt3=4.7321,\quad \lambda_2=3,\quad \lambda_3=3-\sqrt3=1.2679, f A ( λ ) = det ( λ I − A ) = ( λ − 3 ) [ ( λ − 3 ) 2 − 3 ] , λ 1 = 3 + 3 = 4.7321 , λ 2 = 3 , λ 3 = 3 − 3 = 1.2679 ,
(展开:λ 3 − 9 λ 2 + 24 λ − 18 \lambda^3-9\lambda^2+24\lambda-18 λ 3 − 9 λ 2 + 24 λ − 18 ;λ = 3 \lambda=3 λ = 3 代入为 0 0 0 ,再解二次 λ 2 − 6 λ + 6 = 0 \lambda^2-6\lambda+6=0 λ 2 − 6 λ + 6 = 0 。)与 A 20 A_{20} A 20 的对角元逐位吻合 ✓。∎
本编注 · 收敛条件的边界:等模特征值会卡住
「各特征值模值互不相同」是充分 条件,不是客气话。反例就用 3.5 即将出场的那张旋转矩阵:
A = [ 0 − 1 1 0 ] ( 正交矩阵,特征值 ± i 等模 ) . A=\begin{bmatrix}0&-1\\ 1&0\end{bmatrix}\quad(\text{正交矩阵,特征值 }\pm\mathrm i\ \text{等模}). A = [ 0 1 − 1 0 ] ( 正交矩阵,特征值 ± i 等模 ) .
它自己的 QR 分解(正线版)是 A = A ⋅ I A=A\cdot I A = A ⋅ I (Q = A Q=A Q = A 酉、R = I R=I R = I 正线),于是 A 2 = R 1 Q 1 = I ⋅ A = A A_2=R_1Q_1=I\cdot A=A A 2 = R 1 Q 1 = I ⋅ A = A ——迭代卡死在原地 ,{ A k } \{A_k\} { A k } 恒为 A A A ,永远不收敛到上三角阵。等模特征值(如实的旋转阵、含 ± λ \pm\lambda ± λ 对的矩阵)都会出现这类「原地打转或极限不为三角」的现象;实用中的补救(先化成 Hessenberg 形、加位移)是《数值分析》课程的主题。这也提示 QR 算法的极限 其实是 A A A 的一个 Schur 型——正是下一节的内容。
课程预告 · 从分解到 Schur 型
QR 算法的收敛极限「酉相似于上三角阵」并不是迭代碰巧的礼物:任何复方阵都酉相似于上三角阵 (Schur 引理,3.5 的定理 3.5.2)——QR 算法只是在数值上把这个存在的事实算出来 。更有趣的是证明:对相似变换矩阵 P P P 作 QR 分解 P = U R P=UR P = U R ,普通相似立刻升级成酉相似。两节在此接轨。
考情速递(本编依据课件小结与前章课堂考情整理;本讲无录播,未见老师原话)
课件小结页亲排:「重要结论:QR 分解定理;重要算法:QR 算法 」——对应两条考试主线:计算大题手算 QR (GS 全流程,正线规约是隐形评分点)与概念 / 小计算考 QR 算法 (相似性论证、收敛条件的充分性)。课件的思考题三连问(满秩?不满秩?长方?)是判断题的题源,注 1 与例 3.4.1 的「不唯一」几乎必考其一。跨章联动:二维 QR 的 Q Q Q 常常就是 Givens 旋转(例 3.4.A )或 Householder 反射(习题 R2-1,见竞技场 )——2.5 老师原话点名这两个矩阵「容易变形」(01:14:16)。分级清单、限时赛制与计时器集中在考场竞技场 。
一条主线 :满秩分解的正交化 ⇒ \Rightarrow ⇒ 定义 3.4.1(A = Q R A=QR A = QR :酉 × \times × 上三角)⇒ \Rightarrow ⇒ 定理 3.4.1(满秩方阵存在且正线下唯一;R R R 是「z \boldsymbol z z 基到 a \boldsymbol a a 基」的过渡矩阵,GS 即算法)⇒ \Rightarrow ⇒ 不唯一 = = = 对角酉阵自由度(实:2 n 2^n 2 n 种)⇒ \Rightarrow ⇒ 放宽前提(例 3.4.2 不满秩:零行;定义 3.4.2 列正交规范;例 3.4.3 + + + 推论 3.4.1:长方阵补零块)⇒ \Rightarrow ⇒ QR 算法(A k + 1 = Q k H A k Q k A_{k+1}=Q_k^{\mathrm H}A_kQ_k A k + 1 = Q k H A k Q k 酉相似链,模互异 ⇒ \Rightarrow ⇒ 收敛上三角,对角元 = = = 特征值)。
两句话记住它 :GS 立轴,坐标上三角 ——把 A A A 的列逐个减掉在已有标准正交方向上的成分,坐标表自动变成「只用前 k k k 个轴」的三角形。正线锁相角 ——不规定对角为正,分解就差一圈子符号 / 相角。
常见错误清单 · 自查五条
把 r k k r_{kk} r kk 写成 ∥ a k ∥ \|\boldsymbol{a}_k\| ∥ a k ∥ :对角元是 GS 残差 y k \boldsymbol{y}_k y k 的范数(先减成分、再量长度);∥ a k ∥ \|\boldsymbol{a}_k\| ∥ a k ∥ 只有在 a k \boldsymbol{a}_k a k 与前各轴已正交时才等于 r k k r_{kk} r kk ;
复数情形系数的共轭放错边 :本节系数是 ( a k , z i ) (\boldsymbol{a}_k,\boldsymbol{z}_i) ( a k , z i ) ——第一变元线性(定义 1.4.1 约定);若你的教材用第二变元线性,公式要相应换成 r i k = ( z i , a k ) r_{ik}=(\boldsymbol{z}_i,\boldsymbol{a}_k) r ik = ( z i , a k ) ,两套不能混用;
对长方阵硬套定理 3.4.1 :那是方阵 定理;长方阵(列满秩)用推论 3.4.1,R R R 是 m × n m\times n m × n 的「上三角 + + + 零块」,写成 n × n n\times n n × n 会形状对不上;
以为不满秩就没有 QR 分解 :例 3.4.2 说明分解常在,丢掉的是唯一性 (R R R 不可逆,证明失效;且自由度不再只是对角酉阵);也别忘了列正交规范(Q H Q = I n Q^{\mathrm H}Q=I_n Q H Q = I n )与酉矩阵(还需为方阵)的区别;
QR 算法两条方向性错误 :迭代式是 A k + 1 = Q k H A k Q k A_{k+1}=Q_k^{\mathrm H}A_kQ_k A k + 1 = Q k H A k Q k (把 Q k Q_k Q k 左乘 H \mathrm H H 、右乘原样 ),写成 Q k A k Q k H Q_kA_kQ_k^{\mathrm H} Q k A k Q k H 就错了;收敛条件「模互异」丢掉后,把旋转阵这类等模例子也当成「会收敛」——它会原地卡死。
即时自测(不看上文,5 分钟)
背写定义 3.4.1 与定理 3.4.1,并说出「正线」在唯一性证明的哪一步把自由度锁死;
求 A = [ 1 1 2 0 ] A=\begin{bmatrix}1&1\\ 2&0\end{bmatrix} A = [ 1 2 1 0 ] 的 QR 分解(Q Q Q 正交、R R R 正线上三角)并回代验证;
Q ∈ C 3 × 2 Q\in\mathbb C^{3\times2} Q ∈ C 3 × 2 满足 Q H Q = I 2 Q^{\mathrm H}Q=I_2 Q H Q = I 2 :它是酉矩阵吗?Q Q H = QQ^{\mathrm H}= Q Q H = ?∥ Q x ∥ \|Q\boldsymbol{x}\| ∥ Q x ∥ 与 ∥ x ∥ \|\boldsymbol{x}\| ∥ x ∥ 有何关系?
复述推论 3.4.1 的构造证明,「补齐」一步为什么不会破坏前 n n n 个标准正交向量?
旋转阵 A = [ 0 − 1 1 0 ] A=\begin{bmatrix}0&-1\\ 1&0\end{bmatrix} A = [ 0 1 − 1 0 ] 的 QR 迭代为什么卡死?这暴露了收敛条件的什么缺口?
解答 · 即时自测
A = Q R A=QR A = QR ,Q Q Q 酉(实:正交)、R R R 上三角(正线 = = = 对角全正实数);满秩方阵存在且唯一。锁死的一步:W = R 2 R 1 − 1 W=R_2R_1^{-1} W = R 2 R 1 − 1 既酉又上三角 ⇒ \Rightarrow ⇒ 对角 ∣ w i i ∣ = 1 |w_{ii}|=1 ∣ w ii ∣ = 1 ,对角为正 ⇒ w i i = 1 ⇒ W = I \Rightarrow w_{ii}=1\Rightarrow W=I ⇒ w ii = 1 ⇒ W = I 。
z 1 = 1 5 ( 1 , 2 ) T \boldsymbol{z}_1=\tfrac{1}{\sqrt5}(1,2)^{\mathrm T} z 1 = 5 1 ( 1 , 2 ) T ;( a 2 , z 1 ) = 1 5 (\boldsymbol{a}_2,\boldsymbol{z}_1)=\tfrac{1}{\sqrt5} ( a 2 , z 1 ) = 5 1 ,y 2 = ( 4 5 , − 2 5 ) T \boldsymbol{y}_2=(\tfrac45,-\tfrac25)^{\mathrm T} y 2 = ( 5 4 , − 5 2 ) T ,∥ y 2 ∥ = 2 5 \|\boldsymbol{y}_2\|=\tfrac{2}{\sqrt5} ∥ y 2 ∥ = 5 2 ,z 2 = 1 5 ( 2 , − 1 ) T \boldsymbol{z}_2=\tfrac{1}{\sqrt5}(2,-1)^{\mathrm T} z 2 = 5 1 ( 2 , − 1 ) T 。Q = 1 5 [ 1 2 2 − 1 ] Q=\tfrac{1}{\sqrt5}\begin{bmatrix}1&2\\ 2&-1\end{bmatrix} Q = 5 1 [ 1 2 2 − 1 ] (对称且正交,det = − 1 \det=-1 det = − 1 ),R = [ 5 1 5 0 2 5 ] R=\begin{bmatrix}\sqrt5&\tfrac{1}{\sqrt5}\\ 0&\tfrac{2}{\sqrt5}\end{bmatrix} R = [ 5 0 5 1 5 2 ] ;验算 Q R = [ 1 1 5 + 4 5 2 2 5 − 2 5 ] = [ 1 1 2 0 ] QR=\begin{bmatrix}1&\tfrac15+\tfrac45\\ 2&\tfrac25-\tfrac25\end{bmatrix}=\begin{bmatrix}1&1\\ 2&0\end{bmatrix} QR = [ 1 2 5 1 + 5 4 5 2 − 5 2 ] = [ 1 2 1 0 ] ✓。
不是(非方阵);Q Q H QQ^{\mathrm H} Q Q H 是到 R ( Q ) R(Q) R ( Q ) 的正交投影矩阵 ≠ I 3 \neq I_3 = I 3 (e 3 \boldsymbol{e}_3 e 3 方向被抹掉);∥ Q x ∥ = ∥ x ∥ \|Q\boldsymbol{x}\|=\|\boldsymbol{x}\| ∥ Q x ∥ = ∥ x ∥ (保范)。
GS(列满秩 ⇒ \Rightarrow ⇒ 各步残差非零)给 A = Q 1 R 1 A=Q_1R_1 A = Q 1 R 1 ;基扩充(推论 1.3.1 )后对整组重做 GS——「张成不变」保证前缀的 span \operatorname{span} span 不变,而已标准正交的前 n n n 个向量重走 GS 公式每个减项内积为零 、原样保留;只有新添的向量被正交化。U = [ Q 1 , U 2 ] U=[Q_1,U_2] U = [ Q 1 , U 2 ] 列标准正交的方阵即酉。
A A A 本身正交,其正线 QR 分解为 A = A ⋅ I A=A\cdot I A = A ⋅ I ,故 A 2 = R 1 Q 1 = A A_2=R_1Q_1=A A 2 = R 1 Q 1 = A ,迭代恒为 A A A 不动。缺口:特征值 ± i \pm\mathrm i ± i 等模 ,违反「模值互异」——该条件不可去掉(充分条件的边界)。