张瑞
中国科学技术大学数学科学学院
rui@ustc.edu.cn |
线性方程组可以写成一般矩阵形式形式
简记为
根据线性代数的知识,当且仅当时,方程组存在唯一的解。
Gramer法则给出了解的表达式
其中是把的第列换成后得到的方阵。
注.
但这个公式不能用于计算机求解,因为计算量太大。
直接法:
- 经过若干次等价变换后再求解,因而该类方法没有截断误差。
- 需要分析方法的计算量有多大。
迭代法:
- 构造一个收敛到解的迭代序列。产生的截断误差取决于迭代的步数,
- 因而也没有截断误差的分析,但需要分析迭代格式收敛的条件。
先从直接法开始介绍。
在线性方程组中,若为对角阵
则可以直接得到解
可以看到,计算得到解需要的计算量是: 个乘除法。
在线性方程组中,若为下三角阵
则可以顺序得到解
解需要运算量是: 个加减,个乘除。因此,总的计算量是
在线性方程组中,若为上三角阵
则可以倒序得到解
总计算量与下三角阵的情形一样,也是次运算。
定义 1.
消元法就是把矩阵变为对角阵、上三角阵或下三角阵,然后进行求解的方法
Gauss 消元
Gauss消元法把矩阵
变为上三角阵
第1步,第1行加到第行,,可以把第1列下三角部分变成。
这一步的运算量: 次乘除,次加减,
共次运算。
第2步,第2行加到第行,,可以把第2列下三角部分变成。
这一步的运算量: 次乘除,次加减,
共次运算。
在第步后,
第k步,第k行加到第行,,可以把第k列下三角部分变成。
这一步的运算量:
经过步后,可以得到上三角阵
加上一个解上三角矩阵的回代过程,即可得解。
整个消元过程的计算量为
加上反代过程的计算量为,可以得到全部的运算量为
- 可以看到,整个Gauss消元过程都是对方程组作的初等变换,它不会改变方程组的根,
也不会改变的值。因此,不存在截断误差。
- Gauss消元法可以进行,需要保证
定理 1.
方程可以使用Gauss消元法求解的充要条件是的所有顺序主子式不为0,即
Gauss消元法的问题:
- 可以保证方程组存在唯一的解,但还不能保证Gauss消元法可以运行。
- 当接近0时,舍入误差会被放大,从而有可能导致计算失败。
例 1. 解方程
解. 方程有真解
由Gauss消元
在单精度数值计算下,
则有
列主元(Partial Pivot)
Gauss消元法的问题集中在上,
- 若它为0,则算法不可用;
- 若它太接近0,则可能导致不稳定: 舍入误差会导致结果误差太大。
在消元前,调换行的次序。这就可以得到列主元消元法。
在第步后,
若是中最大的,则交换行与行。
然后进行第k步消元。
例 2. 解方程
解.
由列主元消元
在单精度数值计算下,(同样存在大数吞小数)
则有
例 3. 解方程
解.
由列主元消元
在单精度数值计算下,
则有
进一步得到
- 若,则中
一定有一个非0元。(否则,)
- 列主元消元的适用范围是,与线性方程组存在唯一解的条件是一致的。
- 列主元在一定程序上克服了Gauss消元中的不稳定现象。
- 相较于Gauss消元,列主元没有增加任何的运算量,但增加了次的比较操作。
- 还存在一些情形,用列主元消元法仍然有较大的误差。
改进的方法可以有 Scaled Pivot 或 全选主元消元 。
Scaled Pivot
在第步后,
在中,比较
若是中最大的,则交换行与行,然后进行消元。
整个算法,在第步,增加了个查找最大值的过程,以及次除法。
因此,整个算法的运算量增加了次。
例 4. 解方程
解.
由Scaled Pivot
在单精度数值计算下,
则有
全选主元 Full Pivot
在第步后,
若在, 中最大,则交换行与行,列与列。
然后进行第k步消元。
问题. 列交换并不是等价的变换,还有可能得到真正的解吗?
比较如下两个线性方程组
可以看出,
这样,对增广矩阵的一次列交换,需要对结果做相应的一次行交换。
全选主元消元法的运算量与Gauss消元和列主元消元的运算量是一样的。
相对于Gauss消元,全选主元消元法增加了
次的比较操作。
例 5. 解方程
解.
由全选主元消元
在单精度数值计算下,
则有
消元过程中,交换了1列与2列,因此,最后的解需要交换1行与2行。
得到解是
Gauss-Jordan消元
消元过程中,把矩阵的上三角部分也变成0元,最后得到一个对角阵。
第k步:
第k行加到第行,
,
可以把第k列上三角部分与下三角部分变成。
- 具体实现时,可以先做Gauss消元,变成上三角阵,然后从第列开始,逐步将上三角部分也变成0。
- 解形问题,在反代过程中,可以节省运算量。
- 当时,得到的。
程序作业
编写列主元消元法,并且计算
输出消元后的上三角阵,及解
输出:
消元后的矩阵为
31,-13,0,0,0,-10,0,0,0
0, *,
...
解为:
0.218304
1.29484
...