基于Givens旋转完成QR分解进而求解实矩阵的逆矩阵

基于Givens旋转完成QR分解进而求解实矩阵的逆矩阵

前言

一、Givens旋转简介

二、Givens旋转解释

三、Givens旋转进行QR分解

四、Givens旋转进行QR分解数值计算例子

五、求逆矩阵

六、MATLAB仿真

七、参考资料

总结

前言

在进行QR分解时，HouseHolder变换一次将一个向量除第一个元素以外都转化成零。而有一种方法，可以每次将向量的一个元素转化成0，也可以最终达到正交化的目的，它就是Givens旋转。Givens旋转矩阵是正交矩阵，使用Givens旋转很容易就可以将一个向量的某个分量的某个指定分量化为0。本文会通过列举例子说明如何将一个矩阵通过Givens旋转分解为Q矩阵和R矩阵，最后，会用MATLAB进行仿真，当然，代码也会分享出来。

提示：以下是本篇文章正文内容，希望能帮助到各位，转载请附上链接。

一、Givens旋转简介

Givens旋转矩阵是正交矩阵，使用Givens旋转很容易就可以将一个向量的某个分量的某个指定分量化为0。

本文中主要考虑实数的情况。

2×2的Givens旋转矩阵如下:

$\mathbf{G}=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}$

其中

$\cos\theta=\frac{x}{\sqrt{x^2+y^2}},\quad\sin\theta=\frac{y}{\sqrt{x^2+y^2}}$

那么就可以将向量 $\textbf{v}=[x \ y]^T$ 旋转到x轴上面去，如下图所示。当然改变正余弦函数也能旋转到y轴上面去。

即

$\textbf{w}=\textbf{Gv}=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix}=\begin{bmatrix} x\cos\theta+y\sin\theta\\ -x\sin\theta+y\cos\theta \end{bmatrix}= \begin{bmatrix} \sqrt{x^2+y^2}\\ 0 \end{bmatrix}$

可以把简写三角函数，如下所示

$\begin{bmatrix}c&s\\-s&c\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}\sqrt{x^2+y^2}\\0\end{bmatrix}$

二、Givens旋转解释

我们将向量 $\textbf{v}=[x \ y]^T$ 看成一个复数，即

$z_1=x+iy=re^{i\varphi}=r\cos\varphi+ir\sin\varphi$

则

$\left.\textbf{G}\cdot\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}\cos\theta&\sin\theta\\-\sin\theta&\cos\theta\end{bmatrix}\left[\begin{array}{c}x\\y\end{array}\right.\right]=\left[\begin{array}{c}x\cos\theta+y\sin\theta\\\\-x\sin\theta+y\cos\theta\end{array}\right]$

将其也看成一个复数

$z_2=(x\cos\theta+y\sin\theta)+i(-x\sin\theta+y\cos\theta)\\ \\=r[(\cos\varphi\cos\theta+\sin\varphi\sin\theta)+i(\sin\varphi\cos\theta-\sin\theta\cos\varphi)]\\ \\ =r(\cos(\varphi-\theta)+i\sin(\varphi-\theta))\\ \\=re^{i(\varphi-\theta)}$

对比 $z_1=re^{i\varphi}$ 和 $z_2=re^{i(\varphi-\theta)}$ ，学过复数的话，显然就能看出这是顺时针旋转了 $\theta$ 的角度。

三、Givens旋转进行QR分解

下面我们来说明如何通过Givens旋转来实现QR分解。其实原理很简单，就是通过将原矩阵A的主对角线下方的元素都通过Givens旋转置换成0，形成上三角矩阵R，同时左乘的一系列Givens矩阵相乘得到一个正交阵Q。
如下图所示，G(m,n)是Givens旋转矩阵，相当于用某一列的第m个元素去将第n个元素清零。

也可以通过下图来理解，其中×表示没有发生变化的元素，m表示值改变的元素，每一个向右的箭头表示原矩阵左乘了1次Givens矩阵。

由上图我们会发现清一个0时只影响两行，所以对一个高阶矩阵，在清某一列的几个0时可以同时执行，加快计算速度。比如对于4×4阶矩阵，可以在选第1列的第1个元素去将第一列的第2个元素清零的同时，也选择第1列的第3个元素去将第一列的第4个元素清零。

四、Givens旋转进行QR分解数值计算例子

设矩阵 $\textbf{A}=\begin{bmatrix}0&&4&&2\\0&&3&&1\\2&&1&&-2\end{bmatrix}$ ，用Givens旋转的方法对其进行QR分解。

解：由于其第1列的第2个元素已经为0了，不用对它进行消0操作，我们首先用第1列的第1个元素对第1列的第3个元素清0。

易求

$c=\frac{0}{\sqrt{0^2+2^2}}=0,\:\: s=\frac{2}{\sqrt{0^2+2^2}}=1$

则Givens矩阵可写为

$\textbf{G}_1=\begin{bmatrix} 0 &0 &1 \\ 0&1 &0 \\ -1& 0 &0 \end{bmatrix}$

所以

$\textbf{G}_1\textbf{A}=\begin{bmatrix} 0 &0 &1 \\ 0&1 &0 \\ -1& 0 &0 \end{bmatrix}\begin{bmatrix}0&&4&&2\\0&&3&&1\\2&&1&&-2\end{bmatrix}=\begin{bmatrix}2&&1&&-2\\0&&3&&1\\0&&-4&&-2\end{bmatrix}$

接下来对上面结果右下角的四个元素进行Givens旋转，用3去将-4消为0。

易求

$c=\frac{3}{\sqrt{3^2+(-4))^2}}=\frac{3}{5},\:\: s=\frac{-4}{\sqrt{3^2+(-4))^2}}=-\frac{4}{5}$

则Givens矩阵可写为

$\textbf{G}_2=\begin{bmatrix} 1 &0 &0 \\ 0&\frac{3}{5}&-\frac{4}{5}\\ 0& \frac{4}{5} &\frac{3}{5} \end{bmatrix}$

所以

$\textbf{G}_2\textbf{G}_1\textbf{A}=\begin{bmatrix} 1 &0 &0 \\ 0&\frac{3}{5}&-\frac{4}{5}\\ 0& \frac{4}{5} &\frac{3}{5} \end{bmatrix}\begin{bmatrix}2&&1&&-2\\0&&3&&1\\0&&-4&&-2\end{bmatrix}=\begin{bmatrix} 2 &1 &-2 \\ 0&5&\frac{11}{5}\\ 0& 0 &-\frac{2}{5} \end{bmatrix}$

所以

$\textbf{R}=\begin{bmatrix} 2 &1 &-2 \\ 0&5&\frac{11}{5}\\ 0& 0 &-\frac{2}{5} \end{bmatrix}$

所以

$\textbf{Q}=(\textbf{G}_2\textbf{G}_1)^T=\textbf{G}_1^T\textbf{G}_2^T\\\\=\begin{bmatrix} 0 &0 &-1 \\ 0&1 &0 \\ 1& 0 &0 \end{bmatrix}\begin{bmatrix} 1 &0 &0 \\ 0&\frac{3}{5}&\frac{4}{5}\\ 0& -\frac{4}{5} &\frac{3}{5} \end{bmatrix}\\ \\ \\=\begin{bmatrix} 0 &\frac{4}{5} &-\frac{3}{5} \\ 0&\frac{3}{5}&\frac{4}{5}\\ 1& 0 &0\end{bmatrix}$

故

$\textbf{A}=\textbf{QR}=\begin{bmatrix} 0 & \frac{4}{5} & \frac{-3}{5} \\ 0& \frac{3}{5}& \frac{4}{5} \\ 1 &0&0 \end{bmatrix} \begin{bmatrix}2&1&-2\\0&5&\frac{11}{5}\\0&0&\frac{-2}{5}\end{bmatrix}=\begin{bmatrix}0&4&2\\0&3&1\\2&1&-2\end{bmatrix}$