household变换

1、3.2正交变换正交变换为了给出求解最小二乘问题的更实用的算法， 这一节我们来介绍两个最基本的初等正交变换，它们是数值线性代数中许多算法的基础。3.2.1 Householde改换改换使用 Gauss 变换将一个矩阵约化为上三角形式是基于一个简单的事实：对于任一个给定的向量 x,可构造一个初等下三角阵工,使%=*这里或是/的第一列，立七 R.R.这一节我们来讨论如何求一个初等正交矩阵,使其具有矩阵的功能。这样，对一个矩阵的上三角化任务，便可以由一系列的初等正交变换来完成。定义 3.2.13.2.1 设 WEWERR满足=1,定义在宅 RMRM 为豆豆= =1-2 何丁，何丁，(3.2.1)贝口称

2、欢为 HouseholderHouseholder 变换。Householder 变换也叫做初等反射矩阵或镜像变换，它是著名的数值分析专家Householder 在 1958 年为讨论矩阵特征值问题而提出来的。下面的定理给出了Householder 变换的一些简单而又十分重要的性质。定理 3.2.13.2.1 设刘是由(3.2.1)定义的 Householder 变换，那么五满足：对合性：一二；反射性：对任意的,ER,ER，如下图所示，.是无关于卬的垂直超平面的镜像反射。证明（1）显然。（2）和（3）可由（1）导出。事实上，我们有=（”2KM）Q2ww）-I-+MM-1（4）设.ER,则工可表

3、示为K=$十以死其中蕈 w 尔驮伸广已 wR 利用/”=0 和 3”=1 可得丹工=Zww1）（n 十四）=即：+32H 伸,骷Zctwvyf-u-gu这就说明了.为 X 关于“kP3n可，的镜像反射。Householder 变换除了具有定理 3.2.1 所述的良好性质外，它的主要用途在于，它能如 Gauss 变换一样，可能通过适当选取单位向量 W，把一个给定向量的若干个指定的分量变为零。引理 i i 设工,为两个不相等的向量，且凡二 ML*3,则存在一个HouseholderHouseholder 变换用满足引理证毕定理 3.2.2 设口HER则可构造单位向量 WER”,使由（3.2.1）定

4、义的Householder 变换日满足其中.：-I-证明由于田三(1-2wwr)x=x-2(v/j)wn故欲使野三维，则 W 应为对度=IM,直接验证可知这样定义的 H 满足定理的要求。定理 3.2.2 告诉我们，对任意的 xR1 工善口）都可以构造出 Householder 矩阵W证明令,构造 Householder 变换阵丹=1-2 州*-2以卜理卜一 Jt 二。一处C2b才7晨）从而=7-笈，使出的后咫 T 个分量为零；而且其证明亦告诉我们，可按如下的步骤来构造确定H的单位向量 w:构造算法程序时，以注意以下几个问题：计算以必时，为避免溢出，可以考虑先将无规范化为卜 L=1的向量。事实上

5、，若工工。，假定 Householder 变换阵区使由川现叫那么H工=ZHx，二引吐.=网.1=也就是说，对于向量集合能.口）中的任一个非零向量，由 Th3.2.2 构造出的Householder 变换阵都是一样的，或许最多只相差一个符号。在实际计算时，卜 1 前的符号如何选取最好。即，二工-口即产在计算向量炉的第一个分量巳=瓦 TkL 时，为了避免两相近数相减，而导致计算结果损失有效数字，可适当做变形处理，即1）如果勺三。时，2）直接计算：wM；+器）3）如果口时，4）五十桃事实上，5）vT_|J_-皿_（君+十尺）IM矶考虑到实际计算的需要， 在最后构造 Householder 变换阵时，

6、 常规定 H 具有如下形式一，.,其中：的第一个分量为 1;二24算法 3.2.13.2.1(计算 Householder 变换)function.v,j?=house(x)?s=length(i)向量工的长度)MLCT=z(2：界)Tx(2:龙)丫(1)=1;v(2,n)=x(2:)ifct=0仆二。ekea-J.+仃ififA(1)十n(l)T=v为 3end对应的 C 程序函数如下：voidHouseholder(double*x,intn,double&bet,double*v)(inti;doublealph,norm;norm=fabs(x0);for(i=1;in;i+)

7、if(normfabs(xi)norm=fabs(xi);if(norm=0)printf(Fail,becausexiszero.n);exit(0);for(i=0;in;i+)xi/=norm;norm=0.0;for(i=1;in;i+)norm+=xi*xi;v0=1.0;for(i=1;in;i+)vi=xi;if(norm=0)bet=0.0;else(alph=sqrt(x0*x0+norm);if(x0=0)v0=x0-alph;elsev0=-norm/(x0+alph);bet=2.0*v0*v0/(norm+v0*v0);alph=v0;for(i=0;ir二1了6;看二Ifjl十广，二二/els?产二乡/&C=+s=crendend如果用一个 Givens 变换左（或右）乘一个矩阵 R