专栏首页MyBlog数值分析读书笔记(2)求解线性代数方程组的直接方法

数值分析读书笔记(2)求解线性代数方程组的直接方法

数值分析读书笔记(2)求解线性代数方程组的直接方法

1.引言

矩阵的数值计算一般可以分为直接法和间接法

本章主要介绍

这类线性方程组求解的直接法,数值求解该方程组的基础思想是Gauss消元法

实质是通过一组满秩的初等行变换,将A保秩变换成一个三角矩阵U,此变换过程称为矩阵A的非奇异上三角化

我们的目的就是寻求一个矩阵P,使得PA=U,其中U是一个三角矩阵,其中

同解(

),有效的生成一个P是我们主要研究的问题

2.初等下三角矩阵--Guass变换矩阵

回顾一下线性代数中的三个初等线性变换

  • 数乘
  • 倍加
  • 互换

我们引入一个一般意义上的初等变换矩阵,它把许多常用的线性变换统一在一个框架里面,在数值线性代数中起着重要的意义

Def: 称

中如下形式的矩阵

初等矩阵:

其中非零向量

是实或者复数,即

选取不同的

,可以得到许多常用的线性变换矩阵

  • 数乘(

  • 倍加(

  • 互换(

下面引出初等变换矩阵的一些重要的数学性质 1.两相同向量u,v组成的初等变换矩阵可交换,其积仍然为一个初等矩阵

证明:

2.若

,则初等矩阵E(u,v;\sigma)可逆,其逆矩阵也是初等矩阵

3.设

表示和

正交的(n-1)维子空间 a.若

,则

有n个线性无关的特征向量,该组特征向量由u和

中任取一组基向量组成 b.若

,则

仅有n-1个线性无关的特征向量,该组特征向量由

中任取一组基向量组成

4.

5.对任意非零向量

,必可适当选取

使得

事实上只需要取

满足

由初等变换矩阵引出Guass变换矩阵,我们选取

得到n-1个Guass变换矩阵

下面给出Guass变换矩阵的一些性质

1.

2.Guass变换矩阵的逆只需要将

从-1变成+1

3.

注意左乘的顺序

3.Gauss消元法

先介绍一下顺序Gauss消元法,大概分两步

  • 消元过程
  • 回代过程

在消元过程中,我们不断去左乘Gauss变换矩阵,不断将原矩阵的下三角部分一列列变成0,从而最终变换成一个上三角矩阵

需要注意的是,在一列列的消元过程中,我们需保证

,所以需要利用行互换来保证此条件

当然这一切消元过程的前提是,矩阵A应该是非奇异的

经过n-1次的Gauss消元,我们可以得到一个上三角矩阵

在回代过程中,由于我们得到了一个上三角矩阵,那么就可以从最底行开始逐步解出x

Gauss消元法的复杂度是

,高阶状态下比起克拉默法则运算量要小得多

Gauss消元法过程中,在对各列进行消元的时候,如果主元比较小的话,运算的结果会产生较大的误差,故引入Gauss列主元消元法,即在每一次利用主元消元的步骤之前,把该列中绝对值最大的数所在的行与主元所在的行进行交换

4.三角分解法

我们利用Gauss变换矩阵对Gauss消元法进行进一步的分析

由此引出矩阵的LU分解,又称Doolittle分解

这里再介绍一下Crout分解,即A=LU中的L是一个下三角矩阵,U是单位上三角矩阵

注意到某些特殊矩阵的三角分解也是比较特殊的,这里引入一类带状对角形矩阵

上半带宽为s,下半带宽为r,存在LU分解,其中L是下半带宽为r的单位下三角矩阵,U是上半带宽为s的上三角矩阵

对于r=s=1的这一类更加特殊的矩阵,称为三对角矩阵,对于此类矩阵的三角分解,介绍一种“追赶法”

首先做Crout分解

然后分两步解决此类问题 追:解

赶:解

注意到正定对称矩阵的三角分解也是特殊的,这里引入Cholesky分解

首先利用Doolittle分解,得

,对U进一步提取对角矩阵

,从而有

故,

,由于A对称正定,

,所以有

由于分解的唯一性,可知

,从而有

我们可以记,

,从而

此种分解手段称为Cholesky分解,限定对角元素为正,此类分解唯一

上述的Cholesky分解中涉及了开方的运算,下面介绍一种改进的平方根法

易知,

,则

先解

,后解

,其中D的逆只需要将对角元素取倒数即可

5.向量和矩阵的范数

范数是比长度更为一般的概念,有了范数就可以更好的去测度误差的大小

关于向量范数

对于非负正定,当仅当x=0,有N(x)=0,否则N(x)> 0;

对于齐次性,有

对于三角不等式,有

这里介绍几种常见的向量范数

向量中的元素的绝对值之和

向量中的元素的绝对值的平方加起来然后开方

向量元素中的最大绝对值(使用Cauchy-Schwarz不等式证明三角不等式)

向量中的元素的绝对值的p次方加起来然后开p次方根(利用赫尔德不等式即可证明三角不等式)

在最优化理论中可能会涉及加权范数,A为对称正定矩阵,

是一种向量范数,记为

在无限维线性空间中,比如在[a,b]区间中,对于所有的实连续函数集合C[a,b],对于其中的一个元素f(x)也是有类似定义的范数

  • 1范数
  • p范数
  • ∞范数

下面介绍一下范数的等价性

对于任意两个定义好的范数,存在两个与向量x无关的非零正常数c1,c2,有

称两个范数等价

不难验证,此处的等价性满足数学定义中的等价性的三个条件,即自反,对称,传递

关于矩阵范数

矩阵范数不仅仅满足非负正定,齐次和三角不等式,而且须满足矩阵相乘的相容性,即

这里给出一类特殊的范数, Frobenius范数

对于

上面的任意一种向量诱导范数,都有

这里给出一种范数的定义,即诱导矩阵范数,诱导矩阵范数和向量范数密切相关

定义:设在两个向量空间

中存在向量范数

, 定义在

空间上的矩阵A的由向量范数

诱导所给出的矩阵范数为(其中x不为零向量)

我们为了解决这个最大值的问题,继续等价定义来优化这个问题

其中第一个max条件为x不为零向量,第二个max条件为

我们利用诱导范数的定义可以从原来的向量范数中诱导出三种范数,分别是

1范数:对矩阵的每一列中的元素取绝对值之后求和,然后选取其中的最大列作为1范数 2范数:矩阵的最大奇异值,也就是矩阵与矩阵的转置的乘积的最大特征值 无穷范数:对于矩阵的每一行的元素取绝对值之后求和,然后选取其中的最大行作为无穷范数

关于矩阵的应用,这里引入一个Banach引理

设矩阵A属于n*m的复矩阵空间,对于该空间上的某种矩阵范数

,有

,则矩阵

非奇异,且有

给出矩阵谱半径的定义

矩阵的谱半径为矩阵的最大特征值,关于矩阵的谱半径,它不超过其任意一种矩阵范数(当矩阵是Hermite矩阵时,矩阵的2范数恰好等于矩阵的谱半径)

继续给出线性方程组中条件数的定义

在某一矩阵空间中,对于某一矩阵范数,矩阵的条件数=矩阵的范数×矩阵的逆的范数,即

对于矩阵的条件数来说,它显然大于等于1,当矩阵恰好是正交矩阵的时候,矩阵的条件数恰好等于1 当矩阵为对称阵,对应的矩阵范数为2范数的时候,此时的条件数称之为谱条件数,其值等于最大特征值除以最小特征值,然后取绝对值

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Effective.Java 读书笔记(12)关于Comparable接口

    对于Comparable接口来说,其主要方法应该是compareTo方法,可是这个方法并没有在Object里面声明,而是Comparable接口中唯一的方法,这...

    Mezereon
  • 关于强化学习(2)

    根据 Simple statistical gradient-following algorithms for connectionist reinforcem...

    Mezereon
  • 图像增强的几个方法以及Matlab代码

    灰度线性变换, 是一种空域的方法, 直接对每一个像素的灰度值进行操作 假设图像为

    Mezereon
  • 【Math for ML】矩阵分解(Matrix Decompositions) (上)

    设\(λ=λ_i\)是矩阵\(A\)的一个特征值,则有方程\((A-λ_iv)x=0\),可求得非零解\(x=p_i\)即为\(λ_i\)对应的特征向量。(若\...

    marsggbo
  • Matlab系列之数组(矩阵)的生成

    从本篇开始,会有一段时间都将用于记录数组、矩阵的操作等等,如果以前没有接触过相关的,可能会觉得要展示的是很复杂的东西,但并不是,这是一个很简单的部分,但也是一个...

    狂人V
  • Python sympy 模块常用功能(三)

    注意,添加行或列是非原位操作(do not operate in place), 不改变原来的矩阵,返回一个新的矩阵。

    用户6021899
  • gauss消元法

    mwangblog
  • matlab矩阵及其运算(五)

    二狗在MATLAB矩阵及其运算(三)篇章中,给大家留下关于自编行列式运算的小程序,本期二狗在此给大家解答一下自编行列式程序思路及代码,再给大家讲一下广逆矩阵的概...

    matlab爱好者
  • 13.高斯消去法(2)——三角矩阵

      对于矩阵有一类特殊的矩阵,叫做三角矩阵。 ?   这种矩阵如果还是按照定义一个二维数组来对数值进行存储的话,无疑将消耗掉不必要的空间,所以我们采用压缩存储的...

    用户1148394
  • SVD奇异值分解的数学涵义及其应用实例

    SVD(Singular Value Decomposition, 奇异值分解)是线性代数中既优雅又强大的工具, 它揭示了矩阵最本质的变换. 使用SVD对矩阵进...

    SIGAI学习与实践平台

扫码关注云+社区

领取腾讯云代金券