基于区间计算的高斯消去法

论文总字数：15492字

目 录

中文摘要 1

英文摘要 2

1.背景介绍 3

2.误差分析和区间计算 3

2.1浮点舍入误差分析方法 3

2.2区间计算 3

3.基于区间计算的高斯消去法 4

3.1区间计算 4

3.1.1区间计算的定义和四则运算 4

3.1.2区间矩阵 5

3.2任意精度的加法和乘法的算法 5

3.2.1加法 5

3.2.2乘法 6

4.分析基于区间计算的高斯消去法 7

4.1预备知识 7

4.2基于区间计算的高斯消去法 8

4.2.1消元过程 8

4.2.2回代过程 10

4.3分析算法 10

4.3.1分析算法的正确性 10

4.3.2误差分析 10

5.验证基于区间计算的高斯消去法的收敛速度 11

5.1INTLAB 11

5.2验证算法 12

5.2.1设计算法 12

5.2.2例子 13

6.总结 14

7.参考文献 14

致谢 16

附件 17

精度可控的高斯消去法

陈旻忆

，China

Absract:Gaussian Elimination Method is a classical direct solution method for calculating sparse large matrices or small dense matrices. In the era of rapid development of the computer, we not omly seek the solution of the matrix,but also the accuracy of the solution has a higher demand. Therefore, a control error problem is introduced. Many researchers have made outstanding contributions in this field and found a lot of effective ways, such as probabilistic method, determination of theory and so on. In practice, also play their own advantages.In this paper,interval analysis is used to control the rounding error in Gaussian elimination. In addition,the definition of the new interval addition and subtraction is given to obtain a better algorithm, which proves that the algorithm can achieve the goal of precision control.

Key words: interval analysis;Gaussian Elimination Method ;precision;intlab;rounding errror

1.背景介绍

在科学研究和生产实践中，许多实际问题往往涉及到解线性方程组。因此,对线性方程组的研究具有十分重要的意义。线性方程组的数值解法一般有两类： 1、直接法：就是经过有限步算术运算，可求得方程组精确解的方法（假设计算过程中没有舍入误差），高斯消去法就是直接法中具有代表性的算法[1]。2、迭代法:  就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。

高斯消去法是解决大型稀疏矩阵的有力工具。在用高斯消去法解线性方程组的时候，我们发现了很多问题，比如当系数矩阵中主元素比较小，就存着大数吃小数的问题。还有相加相消等之类的问题[2]。但是其中比较突出的问题就是舍入误差的问题。

舍入误差在矩阵计算过程中出现。由于计算机只能用某一精度的二进制浮点数来表示实数，所以在一定精度范围内，会舍去若干位有效数字，从而导致误差的出现。

由于科学技术和工程问题对计算提出越来越高的要求以及高速计算工程—电子计算的迅速发展，误差问题变得非常突出。而在进行大规模复杂运算时，舍入误差会随着一步步运算不断地产生，累积扩大，使得开始的误差经过若干次运算后得到的结果可能偏离正确结果，导致计算的数值结果不精确，甚至不正确。因此，舍入误差是一个非常严重的问题。

2.误差分析和区间计算

2.1浮点舍入误差分析方法

分析误差的方法由很多种，按照采用方法不同可以分为两类：第一类是概率方法，第二类是确定性理论方法[3]。

概率方法是把计算过程中每步引入的局部浮点误差看成是有概率密度的独立随机变量，采用计算不确定原理来估算概率意义下的误差范围。

确定性理论方法有很多种，比如区间分析，Wilkinson移动误差分析方法（Wilkinson’s running error analysis）和CENA[3]。这些方法为浮点舍入误差的分析提供了强有力的自动分析结果，能够自动衡量计算结果的有效性；另外也为概率论方法的研究提供了强有力的理论支持。

2.2区间计算

区间计算最早的起源可以追溯到亚里士多德用内接多边形和外接多边形来逼近圆形，从而获得一个圆的周长区间[4]。

把区间算术用作数值计算的第一本书是1951出版的俄语教材，其中区间计算是被陈述并应用于有理数表达式。例如：，其中a,b,c是由指定区间给出，从而得出x的区间范围。

而第一本关于区间计算的书是由日本科学家Teruo Sunaga[5]出版的。在这本书中，不仅可以查找区间计算的基本定义和运算规则，而且还证明了这些运算规则。不仅如此，这本书还讨论了通过区间端点来估计有界区间上的有理函数的范围。此外，还引入了区间向量（作为多维的区间运算），并且讨论了相应的操作。Sunaga还改进了求实函数零点的迭代公式，也就是今天的区间牛顿法。最后，通过区间计算界定剩余项来确定一个有限积分的值，并讨论了解决初始值问题的逐点围绕剩余项的解决方案。

遗憾的是，这些著作并没有得到广泛的关注，直到Moore[4]写的第一本关于区间计算的书出现。

这本书是Moore[6]为了博士论文写的书。尽管它包含一大堆的研究成果，但是主要是集中在解决常微分方程初始值的边界解问题。

Moore的书[7]问世后，很多学者开始研究区间算术的理论与应用。关于Moore这本书第一份研究报告是由Kulisch[8]写的，由1983年被翻译成英文。U.Kulisch和他的团队全方面地研究了区间算法与计算机的应用联系。在20 世纪60年代，ALGOL实施了运算的拓展，提供区间计算相应的算法和相关的运算符。

在过去三十年中，在验证或分析各种各样数学问题的解决方案时，或证明在特定或者给定区域中是否有解决方案时，区间算术作为独立研究对象在数值分析中的作用不断增加。通过引入区间函数和区间算法以及应用适当的不动点定理，将区间视为实数或者复数的延伸变成可能。此外，在计算机上丰富的算术和复杂的应用以及诸如舍入可控，可变精度，运算符超载或者机器数的部分新概念，使理论在实践中成果丰硕，并且影响了许多领域的解决方法可以由计算机自行验证[4]。

3.基于区间计算的高斯消去法

3.1区间计算

3.1.1区间计算的定义和四则运算

令实区间[X]表示非空有界闭实数集，定义

[X]=[,，其中是下界，是上界。

[X]的中点公式为： (3.1)

[X]的半径（误差）公式为： (3.2)

[X]的宽度公式为：widX= (3.3)

若，则=，即，此时就称为区间[X]为点区间或称为区间[X]是退化的。

如果X=[,，Y=[，如上定义，则由以下的

X Y=[；

X-Y=[；

X*Y=[],S={,,,}；

X/Y=X*1/Y,1/Y=[1/,1/]。 (3.4)

3.1.2区间矩阵

设，其中 (i=1,2,…,n)满足3.1.1的区间定义，即。

区间向量的中点：

区间向量的宽度： (i=1,2,…,n) (3.5)

区间向量的范数：， (3.6)

其中}.

设A=，则

区间矩阵范数与普通范数定义相似： (3.7)

区间矩阵宽度：

区间矩阵中点： (3.8)

区间矩阵乘法：

(3.9)

3.2任意精度的加法和乘法的算法

将精度为n的非零实数在p进制计数中被规范化地唯一表示[9]为

.

同理也有唯一的表示

. (3.10)

3.2.1加法

我们不妨求和[]两区间的加法，其他以此类推。我们将和[]的上，下界分别规范化地表示:

. (3.11)

类似地，可以将和按上述定义表示。由于过程相同，就不一一赘述。受徐国良[9]的《任意高精度四则运算算法与实现》一文的启发,为了保证运算结果具有n位有效数字，在运算结果增加附加位，先设置成0。

1. 对阶。不妨设 。将的阶增加到。同时，将尾数右移位，即.

其中= (i=1,2,,)

1. 尾数相加。令　(i=1,2,,)
2. 进位。记E[x]为不超过x的最大整数，并记为进位后的结果，则 (3.12)

若存在连续进位的情况，不妨设进i位(i=1,2,,n l)，则

(i=1,2,,)

1. 规范化。若，则此时无需向右移动小数点，直接取。若，则取

,(i=1,2,,n l)

1. 舍入。若，则最终结果为

(.

剩余内容已隐藏，请支付后下载全文，论文总字数：15492字