特征值与特征向量的计算

QR分解

张瑞
中国科学技术大学数学科学学院

QR分解

Givens旋转矩阵

一个$n\times n$的旋转矩阵为 \[G(i,j,\theta)=\begin{pmatrix} 1 & & & & & & \\ & \cdots & & & & & \\ & & \cos\theta & & \sin\theta & & \\ & & & \cdots & & & \\ & & -\sin\theta & & \cos\theta & & \\ & & & & & \cdots & \\ & & & & & & 1 \end{pmatrix} \] 则$G(i,j,\theta)$为正交阵。

若$x\in\mathbb{R}^n$， $y=G(i,j,\theta)x$，则$y$的分量为 \[\left\{ \begin{array}{l} y_i=c x_i+s x_j \\ y_j=-s x_i+c x_j \\ y_k=x_k, k\neq i, k\neq j \end{array} \right. \] 若要使$y_j=0$，只要取$\theta$满足 \[\left\{ \begin{array}{l} c=\cos\theta=\frac{x_i}{\sqrt{x_i^2+x_j^2}}, \\ s=\sin\theta=\frac{x_j}{\sqrt{x_i^2+x_j^2}}, \\ \end{array} \right. \]

Householder反射变换

设$\omega\in\mathbb{R}^n$，且$\|\omega\|_2=1$，则 \[P=I-2\omega\omega^T \] 称为Householder变换，或者Householder矩阵。易得，$P$是一个对称的正交阵。

对$v\in\mathbb R^n$，将$v$分解为$v=v_1+v_2$，其中$v_2//\omega$， $v_1\perp \omega$，则 \[Pv=v_1-v_2 \] 即，$v$与$Pv$关于与$\omega$垂直的平面$S$是镜面对称的。

对$x,y\in\mathbb{R}^n$，则取$\omega=\frac{x-y}{\|x-y\|_2}$，则有 \[y=Px \]

注. \[\begin{array}{ll} Pv&=(I-2\omega\omega^T)(v_1+v_2) \\ &=(v_1+v_2)-2\omega\omega^Tv_1-2\omega\omega^Tv_2 \end{array} \] 由$v_1\perp\omega$，则$\omega\cdot v_1=0$，即$\omega^Tv_1=0$

由$v_2//\omega$，则$v_2=\lambda\omega$， \[\omega\omega^Tv_2=\omega\omega^T\lambda\omega =\omega\lambda\omega^T\omega \\ =\lambda\omega\|\omega\|_2 =\lambda\omega=v_2 \]

所以， \[Pv=v_1+v_2-0-2v_2=v_1-v_2 \]

对$x=(x_1,\cdots,x_n)^T\neq 0$，求Householder变换P，使得 \[Px=k e_1 \] 其中$e_1=(1,0,\cdots,0)^T$。

取$k=-\mbox{sign}(x_1)\|x\|_2$，令 \[u=x-ke_1, \omega=\frac{u}{\|u\|_2} \] 则 \[u=(x_1+\mbox{sign}(x_1)\|x\|_2,x_2,\cdots,x_n)^T \] 从而 \[P=I-\beta u u^T \] 其中 \[\beta=2(\|u\|_2^2)^{-1}=(\|x\|_2(\|x\|_2+|x_1|))^{-1} \]

QR分解

定理 1.
设$A\in\mathbb R^{n\times n}$，则存在正交阵$P$，使得$PA=R$，其中$R$是上三角阵

定理 2.
设$A\in\mathbb R^{n\times n}$，且$A$非奇异，则存在正交阵$Q$，上三角阵$R$，使得$A$有如下分解 \[A=QR \] 且当$R$的对角元均为正时，分解是唯一的。

例 1. 做矩阵$A$的QR分解 \[A=\begin{pmatrix} 2 & -2 & 3 \\ 1 & 1 & 1 \\ 1 & 3 & -1 \end{pmatrix} \]

例 2. 做矩阵$A$的QR分解 \[A=\begin{pmatrix} 0 & 3 & 1 \\ 0 & 4 & -2 \\ 2 & 1 & 1 \end{pmatrix} \]

找$P_1\in\mathbb R^{n\times n}$，使 \[P_1\begin{pmatrix}2 \\ 1 \\ 1 \end{pmatrix}=\begin{pmatrix}* \\ 0 \\ 0 \end{pmatrix} \] 则有 \[P_1=\begin{pmatrix} -0.816497 & -0.408248 & -0.408248 \\ -0.408248 & 0.908248 & -0.091751 \\ -0.408248 & -0.091751 & 0.908248 \end{pmatrix} \]

\[P_1A=\begin{pmatrix} -2.44949 & 0 & 2.44949 \\ 0 & 1.44949 & -0.224745 \\ 0 & 3.44949 & -2.22474 \end{pmatrix} \]

找$\bar P_2\in\mathbb R^{2\times 2}$，使$\bar P_2(1.44949, 3.44949)^T=(*,0)^T$，得 \[P_2=\begin{pmatrix} 1 & 0 \\ 0 & \bar P_2 \end{pmatrix} =\begin{pmatrix} 1 & 0 & 0 \\ 0 & -0.387392 & -0.921915 \\ 0 & -0.921915 & 0.387392 \end{pmatrix} \]

\[P_2(P_1A)=\begin{pmatrix} -2.44949 & 0 & -2.44949 \\ 0 & -3.74166 & 2.13809 \\ 0 & 0 & -0.654654 \end{pmatrix} \]

解： \[A=\begin{pmatrix} 0 & 3 & 1 \\ 0 & 4 & -2 \\ 2 & 1 & 1 \end{pmatrix} \] 由$x_1=(0,0,2)^T$，记$a_1=\|x_1\|_2=2$，令 \[w_1=\frac{x_1-a_1e_1}{\|x_1-a_1e_1\|_2}=\frac1{\sqrt{2}}(-1,0,1)^T \] 则 \[H_1=I-2w_1 w_1^T=\begin{pmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{pmatrix} \]

\[H_1 A=\begin{pmatrix} 2 & 1 & 2 \\ 0 & 4 & -2 \\ 0 & 3 & 1 \end{pmatrix} \] 记$x_2=(4,3)^T$，则$b_2=\|x_2\|_2=5$，令 \[w_2=\frac{x_2-b_2e_2}{\|x_2-b_2e_2\|_2}=\frac1{\sqrt{10}}(-1,3)^T \] 则 \[\tilde H_2=I-2 w_2 w_2^T=\frac15\begin{pmatrix} 4 & 3 \\ 3 & -4 \end{pmatrix} \] 记 \[H_2=\begin{pmatrix} 1 & 0^T \\ 0 & \tilde H_2\end{pmatrix} \]

\[H_2(H_1 A)=\begin{pmatrix} 2 & 1 & 2 \\ 0 & 5 & -1 \\ 0 & 0 & -2 \end{pmatrix}=R \] \[Q=H_1H_2=\frac15\begin{pmatrix} 0 & 3 & -4 \\ 0 & 4 & 3 \\ 5 & 0 & 0 \end{pmatrix} \]

vertical slide1

vertical slide 2

目录

本节读完

例 3.

[#ex9-1-0].