最优化方法(三)——矩阵QR分解

这篇具有很好参考价值的文章主要介绍了最优化方法(三)——矩阵QR分解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、 实验目的与要求

1.熟练掌握QR分解Gram–Schmidt方法;

2.掌握Householder

3.能够判断矩阵是否可逆,并求出其逆矩阵

二、 问题

读取附件MatrixA.mat文件中的矩阵A利用Gram–Schmidt(GS)算法对A进行QR分解

(1) 验证GS是否能稳定进行QR分解矩阵A,其Q矩阵是否正交?

(2) 实现Householder方法QR分解代码验证其对矩阵A分解是否稳定

(3) 读取附件MatrixB.mat文件的方矩阵B,判断其是否可逆如果可逆,求其逆矩阵。

三、模型建立及求解

解决问题思路,模型建立,分析不同QR分解方法的稳定如何应用求解判断矩阵是否可逆及其逆矩阵问题方面进行阐述;注意由于计算机用浮点数格式存储数,当其绝对值很时,可认为值为0;代码不要在报告里面,可以作为附件提交

1.理论概念

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

2. QR分解

        QR分解法是将原矩阵A(M*N)分解成一个正交矩阵Q(M*N)和一个上三角矩阵R(N*N)(对角线下面的元素全为0)的乘积。QR分解主要有三种方法:Gram-Schmid正交化法、Household变换法、Givens变换法。

 2.1 Gram–Schmidt正交化算法

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

                                

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

 

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

        2.1.4 Modified Gram-Schmidt QR

        使用Gran-Schmidt QR进行QR分解由于数值计算的精度问题,其计算的误差累积较快,当矩阵维数较高的时候具有较差的稳定性。

        问题分析:矩阵的正交性使得其逆矩阵可以直接通过矩阵的转置得到,如果正交性被破坏,那么会造成计算的错误;矩阵R元素的精度也会导致越往后面计算所得的元素误差越大。

        针对如上问题,在Gran-Schmidt QR进行优化,提出了Modified Gram-Schmidt QR。

      (1)算法优化思路

        Gran-Schmidt QR的算法进行QR分解是逐列分解,某一步中的向量只与当前向量的前一个向量有关,其他之后的向量不可见。而计算过程中不可避免地引入误差,而后面的向量只有在其被计算的时候才可见,这时误差可能已经积累到一定程度,所以导致其稳定性较差。

        故,首先选定一个向量作为第一个基准,然后将其余所有向量都投影到该基准的正交空间中。在该正交空间中,对剩下的向量重复前面的工作。

        如此,Modified Gram-Schmidt QR使得从一开始所有的向量都是可见的,这样大部分的计算都在误差尚未积累到较大程度的时候就已经被执行,计算量越往后是逐步减少的,因此前面计算积累的误差的影响就不会剧烈地扩散开,所以MGS可以使求得的矩阵Q的正交性更好,同时矩阵R的误差也被控制在计算机精度的水平。

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

        通过两个图像对比,发现,Modified Gram–Schmidt QR稳定性明显高于Gram–Schmidt QR。修正前Gram-Schmidt QR分解在k>35后正交性偏差开始逐渐增大,由0逐渐增大到近1。而在修正后仅从0逐渐增大到近1.2*10^-7。由此,验证了修正后算法有更好的数值计算性能,能有效减少计算机浮点数存储的误差,大大提高稳定性。

2.2 Householder方法

2.2.1 Householder介绍

Householder是基于迭代镜面反射的方法,通过构造反射算子,利用映射不断对原矩阵A进行Householder三角化,实现QR分解

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

 

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

 

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

 

3.矩阵求逆

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

提示: 老师说没有必要用3.2方法求逆(复杂度很高),直接从QR分解过程中是否报错跳出分解来判断是否可逆。

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

最优化方法(三)——矩阵QR分解,最优化方法,矩阵,人工智能,线性代数

这部分(Givens变换)的实现我略过了,但是大家做实验的时候还是要实现一下 。

四、小结(可含个人心得体会)

QR分解常用方法有四种,分别是Gram-Schmidt、Modified Gram-Schmidt、Householder、Givens。下面是三种方法的优缺点总结。

*Gram-Schmidt

优点:

1.适合小矩阵计算;

2.每次迭代都生成一个正交基,可以随时停止计算

缺点:

1.不适合稀疏矩阵;

2.积累大量舍入误差;

3.循环中必须保存整个矩阵,内存开销大

*Householder

优点:

1.不显式计算Q,只保存若干反射矩阵H,适合仅需要R的任务;

2.最适合稠密矩阵;

缺点:

1.迭代过程不产生可用正交基,必须等到全部迭代完成,无法中断。

2.对于稀疏矩阵会产生大量无效计算。

*Givens

优点:

1.最适合稀疏矩阵,仅影响向量的两个分量,不会对零元素做无效操作;

缺点:

1.迭代的过程不产生可用的正交基,无法中断

2.不适合稠密矩阵计算,稠密矩阵下的计算量大且需要更多空间;

        本次实验学习研究了QR分解及几种方法,深入学习了矩阵的知识,掌握并实践了正交化方法及其他QR分解的方法,学会了如何表达算法的稳定性。文章来源地址https://www.toymoban.com/news/detail-820474.html

到了这里,关于最优化方法(三)——矩阵QR分解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 张益唐:数学的浪漫 —— 人工智能的很多东西实际上就是一种最优化问题

    张益唐,美国加州大学圣塔芭芭拉分校数学系终身教授。张益唐的研究方向是数论。2013年4月17日,他在《数学年刊》发表 《质数间的有界间隔》 ,在 孪生素数猜想 这一数论重大难题上取得重要突破。2022年,张益唐表示,在本质上,他已经证明了朗道-西格尔零点猜想,引发

    2024年02月07日
    浏览(51)
  • 【人工智能的数学基础】多目标优化的帕累托最优(Pareto Optimality)

    寻找多目标优化问题的帕累托最优解. paper:

    2024年02月07日
    浏览(38)
  • 机器学习笔记之最优化理论与方法(一)最优化问题概述

    从本节开始,将对 最优化理论与方法 进行简单认识。 无论是 最优化理论 还是 最优化方法 ,讨论的 对象 都是 最优化问题 。 关于 最优化问题 的一种简单描述:最优化问题本质上属于 决策问题 。 例如 路径选择 问题:确定达到目的地最佳路径的计量标准 。其中问题的 目

    2024年02月11日
    浏览(45)
  • 无约束最优化方法

    求解无约束最优化的基本思路 给定初始点 x 0 ∈ R n , k = 0 x_0in mathbb{R}^n,k=0 x 0 ​ ∈ R n , k = 0 判断当前解是否满足终止准则,若满足则停止迭代,若不满足则转3. 确定 f ( x ) f(x) f ( x ) 在 x k x_k x k ​ 点的下降方向 确定步长 λ k lambda_k λ k ​ ,使 f ( x k + λ k d k ) f(x_k+lambda_

    2023年04月08日
    浏览(96)
  • 最优化方法

    1.最小生成树 图的生成树是它的一颗含有其所有顶点的无环连通子图,一 幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和) 最小的生成树 • 适用场景:道路规划、通讯网络规划、管道铺设、电线布设等 题目数据 kruskal算法 稀疏图,按边大小排序 prim 稠密图

    2024年02月15日
    浏览(37)
  • 最优化方法与数学建模

    目录 1. 梯度下降法 2. 牛顿法 3. 遗传算法 4. 数学建模案例

    2024年02月08日
    浏览(40)
  • 最优化方法-牛顿法一维搜索

    导言: 在最优化问题中,找到函数的最小值或最大值是一个重要的任务。牛顿法是一种经典的迭代方法,常用于优化问题的求解。本文将详细介绍最优化方法中的牛顿法一维搜索,包括其基本原理、算法步骤以及应用场景。 牛顿法,也称为牛顿-拉夫逊方法,是一种迭代的优

    2024年02月06日
    浏览(38)
  • 机器学习笔记之最优化理论与方法(五)凸优化问题(上)

    本节将介绍 凸优化问题 ,主要介绍 凸优化问题的基本定义 、 凸优化与非凸优化问题的区分 。 关于最优化问题 P mathcal P P 描述如下: P ⇒ { min ⁡ f ( x 1 , x 2 , ⋯   , x n ) s.t.  { G i ( x 1 , x 2 , ⋯   , x n ) ≤ 0 i = 1 , 2 , ⋯   , m H j ( x 1 , x 2 , ⋯   , x n ) = 0 j = 1 , 2 , ⋯   ,

    2024年02月09日
    浏览(42)
  • 机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)

    上一节介绍了 牛顿法、拟牛顿法 。本节将继续以 拟牛顿法 为基础,介绍 DFP , BFGS text{DFP},text{BFGS} DFP , BFGS 方法 。 经典牛顿法缺陷与修正牛顿法 关于 经典牛顿法 中关于 下降方向 D k ( k = 1 , 2 , ⋯   , ∞ ) mathcal D_k(k=1,2,cdots,infty) D k ​ ( k = 1 , 2 , ⋯ , ∞ ) 的 数学符号 表

    2024年02月09日
    浏览(51)
  • 机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)

    本节将介绍 无约束优化问题 的常用求解方法,包括 坐标轴交替下降法、最速下降法 。 本节是对优化算法(十~十七)最速下降法(梯度下降法)的理论补充,其中可能出现一些定理的 证明过程 这里不再赘述,并在相应位置 附加链接 。 从本节开始,将介绍 四大类 无约束优化问

    2024年02月10日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包