平方根法和改进的平方根法在线视频

这小节我们来介绍

求解系数矩阵是对称正定的线性方程组的 

平方根法与改进的平方根法 

如果线性方程组Ax=b 

它的系数矩阵a是对称正定的

我们就说这个线性方根组是

对称正定线性方根组 

基于它系数矩阵对称的特点

在利用Gauss消去法

求解线性方程组的时候 

计算量就会减小近一半

我们下面先来看一下

对称正定矩阵它的一些性质 

我们先来介绍对称正定矩阵的

Cholesky分解

Cholesky分解指的是什么

就是对于对称正定矩阵 

存在唯一的非奇异下三角矩阵L 

使得A可以表示成L乘上L的转置 

其中L的对角线的元素都是正数 

这个结论很容易证明 

因为A是对称正定的 

它就一定可以进行三角分解 

我们把它的三角分解记成L~

其中L~是单位下三角矩阵 

U是上三角矩阵  

因为A是对称正定的

所以这个上三角矩阵

对角线上的元素都是大于0的 

我们再进一步的把上三角矩阵

分解成一个对角矩阵

和一个单位上三角矩阵的乘积 

对角矩阵就是上三角矩阵对角线上的元素 

相应的单位上三角矩阵 

我们把它记成 U ~

根据A的对称性 

我们容易证明U~ 实际上 是L~的转置

又因为A是正定的 

那么对角矩阵D对角线上的元素 

就都是大于0的 

我们可以取它对角线上元素的平方根 

形成新的对角矩阵 D~

所以 A可以分解为L~ 乘上D~ D~转置

当然D~的转置就是D~

再乘上L~上的转置 

那我们另L~和D~的乘积就是L 

正好得到了我们要的分解形式 

L乘上L的转置 

所以这个结论

我们很容易根据三角分解

去把它证明出来 

那么它的这个三角分解怎么去求

也就是说我们怎样去求L里面的元素

我们可以采用比较元素的方法 

也就是说我们把L的一般形式给它写出来 

因为它是下三角矩阵 

我们只需要写出对角线和

对角线下面的元素 

L成上L的转置就等于a 

我们用最简单的一个例子来看 

比方说对于一个三乘三的矩阵a 

那么它的Cholesky分解是怎么样去求的 

我们把L的一般形式设出来 

我们把L和L转置的乘积元素写出来 

它和a的矩阵的元素对应相等 

很容易看出来L1的平方等于a1 

L11乘上L21是等于a21 

L21平方加上L2平方等于a22 

以此类推

那么我们通过对应关系

就很容易把L矩阵里边的元素求出来 

可以先根据L11的平方等于a11 

先把L11求出来 

然后再根据L11乘上L21=a21 

因为L11已经算出来了 

所以我们可以给出L21 

实际上就是a21除上L11 

同样的道理去算L31 

L21的平方加上L22平方等于a22 

所以L22就等于

a22减去L21的平方再开根号  

L21我们前一步已经算出来了 

所以说很容易也可以把L22也算出来 

同样的道理 

我们再去根据a 

我们再去根据a32

跟L矩阵里面元素的关系 

可以给出L32的计算表达式

这个就是我们计算L矩阵里面

元素的基本过程

按照刚才的顺序

大家可以练习着把下面这个三乘三矩阵 

把他的Cholesky分解求出来

也就是去求矩阵L里边的元素 

大家可以模仿我们刚刚介绍的过程去求 

实际上 里边有现成的

做Cholesky分解的 

就是 CHOL

大家可以试一下 

那么对于N阶的对称正定矩阵 

我们也是按照这样的顺序

去求他的Cholesky分解的

先去求第一行第一列的这个元素 

L11的然后根据它

去求L21 L31 Ln1 

也就是说依次的先去求第一列第一个元素 

然后接着

依次去求第一列里面的其他元素 

接着去求第二列里的 

对角线的元素L22 

然后接下来去求第二列里边其他的元素 

接着再依次往下求 

按照这个顺序去求解 

就能保证我们每次用到的数 

都是前边已经求出来的数 

这就是求Cholesky分解里边的

L矩阵元素的计算方法 

在这里 

我们主要是利用了a矩阵的对称性质 

设计出这样的计算方法 

大家可以根据我刚才说的算法

来算一个阶数更加高的

比方说这个四乘四这个矩阵的

它的Cholesky分解

那么大概的运算顺序就是

先求第一行第一列的元素 

然后再去求第一列其他位置的元素 

第二我们把第一列求出来以后 

接着去求第二列 

先去求对角线上这个元素 

然后依次去求对角线以下的这些元素 

求完第二列以后再接着去求第三列 

第四列

做法就和我们刚才

对于一般矩阵的做法是一样的 

主要就是根据元素比较法 

然后呢 

找出L矩阵里面的元素

跟原来a矩阵里面的元素之间的对应关系  

这样就可以通过a矩阵

和已经求出来的L矩阵里的元素 

把L矩阵里面下面的元素算出来

但是需要注意的是

这个次序问题

就一定要按照这个按列计算的这个次序去做 

这个算法才能实现

先求第一列再求第二列

依次往下做 

把这种矩阵分解的方法用来求解线性方程组

这种方法就叫解线性方程组的平方根法

也叫Cholesky分解方法

也就是说

如果我们要求的这个线性方程组是Ax=b 

A是对称正定的

我们可以先对a做一个分解

把A分解成一个下三角矩阵和它的转置乘积

也就是L乘L的转置

然后我们把L的转制成X

设成是y

利用L的转置Ly=b

先去求Ly=b 

把y求出以后 

再带入到 L 的转置乘 x等于y里面

接着把X再求出来

这样的利用Cholesky分解 

来求解这样的对称正定线性方程组的方法

我们就把他叫平方根法

也叫Cholesky分解方法

实际上

我们还可以给出对称正定矩阵的另外一种分解

也就是说

对于对称正定矩阵A

一定存在一个单位下三角矩阵L和对角矩阵D  

使得A是等于L乘上D乘上L的转置

B的对角元都是正数 

实际上这个结论在我们刚才说明

A可以进行Cholesky分解的过程中  

就有这个结果

所以这个结论很容易说明

同样的方法也是把A作三角分解

当A=LU然后U再把它分解成一个

对角矩阵乘上一个单位上三角矩阵 

然后利用A的对称性

我们就可以知道L

和这个单位上三角矩阵是互为转置的

所以就是我们要的这种分解的形式

L乘上D的L的转置

这里头需要说明的是 

对称正定矩阵的LD LT分解

本质上其实就是对A作LU分解

那个从刚才我们这种分解的存在性

大家可以看出来

那么LD LT分解中的L实际上就是

LU分解中的L

LD LT分解中的D

实际上就是LU分解中U的对角部分

也就是把u的对角线拿出来就是D

那么LD LT分解中的L和D怎么去计算 

我们就采用对一般的矩阵做LU分解的方法

就可以把LD LT分解

把它求出来

这里我们充分利用对称性

还可以减少一半的计算量

它大概的实现方法就是U的第一行 

就是A的第一行

L的第一列就是用刚求出来的U的第一行 

去除上对角线上的元素就是U11 

这样就求出来L的一列

如果我把U的第K行求出来

那再求L的第K列的时候 

就比一般的LU分解更加简单

直接用U的第K行

去除以U的第K行第K列的这个元素 

得到的就是相应的L的第I行第K列的元素

这样就节省了一半的计算量

这里实际上就是

充分的利用了原来矩阵的对称性质 

也就是你把它的行求出来以后

一转置就是它的列

无非行和列之间差了一个系数

这个系数就是对角线上的元素

所以把它除过去就对了

对角线上的元素拿出来放到对角线上

得到的对角矩阵就是我们要的D 

我们下面可以拿一个简单的例子说明一下

比方对这个四乘四的对称正定矩阵 

我们就用普通的LU分解的紧凑格式来说明它

第一行 那么就是U的第一行

所以U的第一行

直接把A的第一行抄下来就对了 

再求L的第一列的时候就看着第一行

然后用第一行的元素分别去除以对角线上的元素

在这里边再求L的第一列的时候 

就应该是-2 6 -2  

分别去除以四得到L的第一列 

然后再去求U的第二行 

U的第二行求法就是一般的LU分解的这种方法

把U的第二行求出来以后 

直接除以对角线上的元素就是4

也就是把2和-4分别除以4 

摆到相应的第二列的位置上

得到的就是L的第二列

在求U的第三行 

L的第三列的都是这样去做的

那么在求L矩阵里面元素的时候

实际上直接用了U矩阵计算结果

而且只做一次除法 

这个计算量就节省下来了

我们把这个分解过程就叫做

对矩阵的LD LT分析

如果是把这种矩阵分解的方法

用在求解线性方程组上面

那么也是把这个线性方程组

分解成两个三角形的线性方程组

我们把D乘上LT乘X设成是y 

我们先去求三角形方程组Ly=b 

把这个三角形方程组求出以后 

我们得出y 

然后再带入到L的转置

乘X等于B的幂乘y 

再去解决个三角形的方程组

就可以把x解出来

利用矩阵的LD 

LT分解来解线性方程组过程

我们把这种算法叫做改进的平方根法

我们从平方根法和改进的平方根法

的系数矩阵三角分解的过程

大家可以看出来 

平方根法里边有根号的计算

所以会增加计算量 

改进的平方根法 

避免的这个操作

所以在实际问题当中改进的平方根法

用的是更多的 

我们可以总结一下平方根法和改进平方根法

他们的优点

这两种方法都不需要选主元

由于系数矩阵的正定性

所以计算过程也都是稳定的

他们的计算量都是Gauss消去法的一半 

但这里的一半 

应该是比一半多的

因为平方根法需要有根号的计算

是额外消耗了一部分计算量 

改进的平方根法里边也有额外消耗的一部分

计算量

但是他们根据对称性 

计算时存储可以减少一半

实际上

平方根法和改进的平方根法

是求解小型稠密

对称正定线性方程组的最好的算法 

这一小结的内容我们就到这