草庐IT

【矩阵计算】QR分解-基于Householder变换

Sarielllll 2023-12-02 原文

一、QR分解

QR分解是将一个矩阵分解为正交矩阵三角矩阵乘积

QR分解被广泛应用于线性最小二乘问题的求解矩阵特征值的计算

定义2.4.1 如果实矩阵A∈R^(m×n)能化成正交矩阵Q∈R^(m×m)与上三角矩阵R∈R^(m×n)的乘积,即A=QR,则称其为AQR分解。

二、QR分解存在性证明:基于Householder变化实现

已知,通过Householder变换,我们可以将任何一个非零向量x∈R^n转化为‖x‖2*e1,即除第一个元素外,其它元素均为零。

下面通过Householder变化来实现矩阵的QR分解。

仅考虑m=n时的情形。设矩阵A∈R^(n×n),令H1∈R^(n×n)为一个Householder变化,满足

 于是,利用分块矩阵的运算,得到对矩阵左乘一次Householder变换的结果(使该矩阵第一列变成只有第一个元素非零的向量)

 其中,A2阶数为n-1。

类似地,继续对A2左乘Householder矩阵,直到最后整个矩阵变成一个n阶的下三角阵。

 不断重复上述过程,这样,我们得到一系列Householder矩阵

 最终得到一个下三角阵

 回看QR分解的主要目的:将矩阵分解成正交阵与三角阵相乘。

我们现在已经得到三角阵,即QR分解中的R,那么Q是什么呢?

已知A=QR,  Hn-1...H2H1A=R,并且Hi正交且正交,得到A=H1H2...Hn-1R于是记Q=H1H2...Hn-1,并且可知Q是正交矩阵,即A=QR

于是得到利用Householder变换进行QR分解的思路:逐一左乘上Householder矩阵,Householder矩阵的阶数从一开始与A一致的n递减,矩阵规模逐步缩小至1阶,结束循环,得到三角阵R。

那么,Q要怎么返回呢?

已知Q是n个Householder矩阵的乘积,即Q=Q1Q2Q3...Qn,其中

Qj=Im-βj*v^(j)*[v^(j)]^T

其中,v^(j)是[0,...,0,vj+1^(j),...,vm(j)]T

假设有矩阵A,在A(j+1:m,j)中存储了第j个Householder向量的基本部分v^(j)(j+1:m)

为了算Q(Householder矩阵乘积),有两种做法:向前累积、向后累积。一般会使用向后累积。

三、矩阵Q的向后累积算法

结合Qj的计算公式

Qj=Im-βj*v^(j)*[v^(j)]^T

求解QR分解中矩阵Q的算法如下

给定矩阵A∈R^(m×n),假设m≥n

Q=Im

for j=n:-1:1  %因为Q是若干个从1阶到n阶的Householder矩阵的乘积,所以Qj的下标j也从n开始,步长-1,到1

    Q=QjQ(左乘Househloder矩阵,改变行)

    Q(j:m,j:m)=Q(j:m,j:m)-(βj*v(j:m))(v(j:m)^T*Q(j:m,j:m))(β*v)(v^T*β)

%从上面推导过程的图可以看到,第j个Householder矩阵,是与Q的每一行从第j列开始相乘,直到m,所以是j:m;同样,是与Q的每一列从第j行开始相乘直到m,所以是j:m。其他变量的范围也与这个对应。

 四、矩阵R的算法

注意,此处的v与β都是使用之前博文中的Householder变换得到的返回值。

 五、算法不足

上述算法适用情况是m≥n,即行数≥列数的情况,对于m<n的情况,matlab会报错,需要进一步完善算法讨论。

有关【矩阵计算】QR分解-基于Householder变换的更多相关文章

  1. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间,其中100是最大分数。计算平均分并将字母等级作为字符串返回,即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join,

  2. 叮咚买菜基于 Apache Doris 统一 OLAP 引擎的应用实践 - 2

    导读:随着叮咚买菜业务的发展,不同的业务场景对数据分析提出了不同的需求,他们希望引入一款实时OLAP数据库,构建一个灵活的多维实时查询和分析的平台,统一数据的接入和查询方案,解决各业务线对数据高效实时查询和精细化运营的需求。经过调研选型,最终引入ApacheDoris作为最终的OLAP分析引擎,Doris作为核心的OLAP引擎支持复杂地分析操作、提供多维的数据视图,在叮咚买菜数十个业务场景中广泛应用。作者|叮咚买菜资深数据工程师韩青叮咚买菜创立于2017年5月,是一家专注美好食物的创业公司。叮咚买菜专注吃的事业,为满足更多人“想吃什么”而努力,通过美好食材的供应、美好滋味的开发以及美食品牌的孵

  3. 旋转矩阵的几何意义 - 2

    点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前,先介绍一下点向量坐标矩阵的几何含义点:在一维空间下就是一个标量,如同一条直线上,以任意某一个位置为0点,以一定的尺度间隔为1,2,3...,相反方向为-1,-2,-3...;如此就形成了一维坐标系,这时候任何一个点都可以用一个数值表示,如点p1=5,即即从原点出发沿着x轴正方向移动5个尺度;点p2=-3,负方向移动3个尺度;     在一维坐标系上过原点做垂直于一维坐标系的直线,则形成了二维坐标系,此时描述一个点需要两个数值来表示点p3=(3,2),即从原点出发沿着x轴正方向移动3个尺度,在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。

  4. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  5. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明:前端使用微信微信小程序开发工具:后端使用ssm:VU

  6. kvm虚拟机安装centos7基于ubuntu20.04系统 - 2

    需求:要创建虚拟机,就需要给他提供一个虚拟的磁盘,我们就在/opt目录下创建一个10G大小的raw格式的虚拟磁盘CentOS-7-x86_64.raw命令格式:qemu-imgcreate-f磁盘格式磁盘名称磁盘大小qemu-imgcreate-f磁盘格式-o?1.创建磁盘qemu-imgcreate-fraw/opt/CentOS-7-x86_64.raw10G执行效果#ls/opt/CentOS-7-x86_64.raw2.安装虚拟机使用virt-install命令,基于我们提供的系统镜像和虚拟磁盘来创建一个虚拟机,另外在创建虚拟机之前,提前打开vnc客户端,在创建虚拟机的时候,通过vnc

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止,这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量,我

  8. ruby - 使用 Ruby,计算 n x m 数组的每一列中有多少个 true 的简单方法是什么? - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true?”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组,其中每个子数组代表一列,然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本,应该在1.8.6上运行,没有任何依赖:arr.transpose.map{|subarr|subarr.in

  9. arrays - 计算数组中的匹配元素 - 2

    给定两个大小相等的数组,如何找到不考虑位置的匹配元素的数量?例如:[0,0,5]和[0,5,5]将返回2的匹配项,因为有一个0和一个5共同;[1,0,0,3]和[0,0,1,4]将返回3的匹配项,因为0有两场,1有一场;[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法,但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法,或者可能是一个正则表达式,可以很好地回答这个解决方案。 最佳答案 您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at

  10. ruby-on-rails - (Ruby,Rails) 基于角色的身份验证和用户管理...? - 2

    我正在寻找用于Rails的优质管理插件。似乎大多数现有的插件/gem(例如“restful_authentication”、“acts_as_authenticated”)都围绕着self注册等展开。但是,我正在寻找一种功能齐全的基于管理/管理角色的解决方案——但不是简单地附加到另一个非基于角色的解决方案。如果我找不到,我想我会自己动手......只是不想重新发明轮子。 最佳答案 RyanBates最近做了两个关于授权的railscast(注意身份验证和授权之间的区别;身份验证检查用户是否如她所说的那样,授权检查用户是否有权访问资源

随机推荐