问小白 wenxiaobai
资讯
历史
科技
环境与自然
成长
游戏
财经
文学与艺术
美食
健康
家居
文化
情感
汽车
三农
军事
旅行
运动
教育
生活
星座命理

漫步线性代数七——特殊矩阵和应用

创作时间:
作者:
@小白创作中心

漫步线性代数七——特殊矩阵和应用

引用
CSDN
1.
https://blog.csdn.net/u010182633/article/details/52294348

本文将探讨线性代数中特殊矩阵的应用,特别是三对角矩阵在解决实际问题中的应用。文章从一个具体的微分方程问题出发,详细解释了如何将其转化为线性代数问题,并讨论了三对角矩阵的性质及其在高斯消元过程中的优势。此外,文章还讨论了数值计算中的舍入误差问题,并给出了具体的例子来说明小主元带来的不稳定性和行变换的必要性。

本篇文章有两个目标。第一是解释实际问题中大型线性方程组的一种解法,事实是,工程或经济学中大型和现实的问题能够引导我们更深入理解这些知识。但是有一个很重要应用却不需要大量的准备工作。
另一个目标是说明系数矩阵具有的一些特殊性质,为了方便我们用同一个应用进行讲解。大型矩阵几乎总是有一个清晰的模式-对称和很多零元素。因为一个稀疏矩阵包含的信息远小于个,所以计算应该更快。我们将观察带状矩阵,看看集中在对角线附近是如何加快消元的,为此我们将看到一个特殊的三对角矩阵。
看方程(6)中的矩阵,它是通过将微分方程变化为矩阵方程得到的。这是对每个求的连续问题,很明显计算机不能解决它,所以它必须近似为一个离散的问题-我们保留更多的未知变量,结果的精度就越好,当然计算代价也就越高。作为一个简单但仍然具有代表性的连续问题,我们选择微分方程
这是关于位置函数的线性方程,可以在解中加上任何组合依然满足要求,因为的二阶导为零,不影响结果。对于两个任意常数的不确定性,通过在区间的两端添加一个边界条件就能够移除:
这个结果是一个两点边值问题,描述的不是瞬变而是稳态现象-例如一根棒的温度分布,它的一端固定为并且热源为。
记住,我们的目标是产生一个离散的问题-换句话说,一个线性代数中的问题。为此我们只可以接受有限的信息,描述在个相等的区间点上的值,对于同样位置处的真是解我们计算近似解,在端点处处,边界值是。
第一个问题是:我们如何替换导数?一阶导数可以近似表示为有限步长内停止的并且不允许趋近于零,可以是前面的,后面的或中间的:
最后一个关于对称,它是最精确的。对于二阶导数,只是利用处数值的一个组合:
它也有关于对称的优点。重复一遍:当时右边接近的真实值,但是我们必须让停在某个正数上。
对每个点,方程可以用它的离散模拟(5)代替,我们通过乘以来得出个方程:
第一个和最后一个()包含,他们是已知的边界条件,如果这些值非零的话,他们就转化成右边的值。这个方程(5)的结构可以更矩阵形式来更好的可视化,我们选择,从而得到的矩阵:
现在,我们将求解方程(6),它的系数矩阵非常有规律,有许多特殊的性质,其中有三个是非常基本的:

  1. 矩阵是三对角的。所有非零元素位于主对角线以及附近的两条对角线上,这条窄带以外的,这些零大大简化了高斯消元过程。
  2. 矩阵是对称的。每个元素等于它的镜像,使得。上三角矩阵将是下三角矩阵的转置,。的对称性反映了的对称性,奇导数像将破坏对称性。
  3. 矩阵是正定的。这个额外的性质说明主元是正的,在理论和实践中不需要行变换。这和本文末尾要将的矩阵(非正定的)正好相反,在没有行变换的情况下,它将对舍入非常敏感。另外关于正定的概念我会在以后的文章中详细介绍!
    我们返回到是三对角矩阵这个事实,它对消元会有什么影响呢?消元过程的第一步是在第一个主元下面产生零:
    跟一般的矩阵相比,这一步主要有两个简化:
  4. 在主元下面只有一个非零元素
  5. 主元所在的行非常短
    乘数因子是,新的主元是。更进一步,三对角模式保留着:每步消元都允许这两个简化。
    最终结果是,注意主元!
    三对角矩阵的分解因子是二对角矩阵,三个因子和矩阵一样对角线有同样的带状结构,注意互相之间存在转置关系,我们从对称就预期到会如此,主元都是正的,他们的乘积就是的行列式。当不断变大时,这些主元明显收敛到1,这样的矩阵计算起来非常方便。
    稀疏因子完全改变了通常的操作次数,每列的消元只需要两步,对于列来说,次数从降到了,三对角方程组几乎能很快解决,求解它的代价和成正比。
    带状矩阵就是在内(图1),对角矩阵的半个带宽,三对角矩阵的为,,当时就是就是一般的矩阵了。对每一列,消元法需要次操作:长为的行对下面的行进行操作,对于列的带状矩阵大约需要次操作。
    当趋近时,矩阵变成一般矩阵,次数变成。产生的除法和乘-减(不考虑为对称这个假设)精确次数是,对于一般矩阵即,,这是一个整数,因为是连贯的,所以他们之中有一个能被3整除。

    图1:带状矩阵和它的因子
    这是我们最终得到的操作次数,我们强调一点,像那样的有限差分矩阵有逆,在求解时,知道比知道要糟糕,因为乘需要步,而前向消元和回代(产生)步就足够了。
    我们希望本例增强读者对消元的理解,它是实践中遇到的一个大型线性方程实例,接下来对于个未知量的个方程,我们将转向讨论的存在性和唯一性。

舍入误差

理论上非奇异情况有完整的主元(考虑行变换),实践中,需要更多的行交换否则计算的解可能变得毫无价值。接下来我们重点来讲如何使消元更加稳定-为什么需要它以及如何做。
对于中等大小的系统,比如说,消元可能涉及一百万的三分之一次(),对于每步操作,我们必须预期舍入误差。通常情况下,我们固定有效位数,然后将两个大小不同的数相加给出一个误差:
那么所有这些误差是如何影响的最终误差的呢?
这不是一个简单的问题。而这个问题被约翰冯诺依曼碰到了,在计算机使得100万步操作成为可能的时候,是他引领了数学。事实上高斯和冯诺依曼的结合给出了简单的消元算法,虽然冯诺依曼高估了最后的舍入误差。威尔金森(Wilkinson)找到这个问题的正确方法,并且他的书到现在依然是经典。
我们将给出两个简单的例子来说明舍入误差的重要性:
几乎是奇异的而离奇异很远,如果我们稍微将中的元素改一下,它既是奇异的。考虑两个非常接近的向量:
第一个解是,而第二个解是。中第五位数的改变放大到解中第一位数的改变,没有任何数值方法可以避免它对小扰动这种敏感,病态条件能够从一个地方转到另一个地方,但是无法移除。真实解都如此敏感更别说计算解了。
第二点如下:
15、即便是一个矩阵也可能别差的算法个毁掉
我们很遗憾的说:对于矩阵,直接使用高斯消元就是一种差的算法。假设.0001作为第一个主元,那么第二行需要减去第一行的10000倍,右下角就变成了-9999,但是第三位四舍五入将变为-10000,为1的元素将会消失:
四舍五入将得到或者。首先我们用正确值(保留三位小数)回代将得到:
但是如果接受,我们将得到:
计算结果完全不对,是well-conditioned但是消元明显不稳定,也明显是比大许多:
小主元.0001带来了不稳定,补救方法很明显-换行
16、一个小主元迫使消元中发生变化。通常我们比较同一列所有可能的主元,将最大主元换到当前的位置
对于来讲,.0001将和下面的1比较,立马进行行交换,从矩阵的角度来讲就是乘以一个置换矩阵,新矩阵就有好的因子:
的主元是1和.9999,比的.0001和-9999要好。
还有一种策略就是与其余所有列中最大主元进行交换,这时候可能不仅是行,也会有列交换。(这时候置换矩阵乘在右边)这么做的代价太高,上面的方法其实已经够了。
我们说完了数值线性代数的基本算法:带有行变换的消元法。一些进一步的完善,比如看整行或列,都是有可能的,但本质上读者现在知道了一台电脑如何解线性方程组,相比“理论”描述-找到并相乘-我们的描述已花费了大量时间和耐心,我希望能够用更简单的方法来解释是如何发现的,但是我认为我还没有找到。(博主心声:期待大家能有更好的方法提出来)

© 2023 北京元石科技有限公司 ◎ 京公网安备 11010802042949号