Chapt-4 线性代数方程组的数值解法.ppt

第四章线性代数方程组的数值解法
§ 概述
线性代数方程组(System of Linear Algebra Equations)的求解是数值计算方法中的一个重要课题。现代工程技术或科研过程中所遇到的一些实际问题,常常直接或间接地归结为求解一个线性代数方程组。例如有分支水流的流速分布、建筑结构中的设计计算和应力分析、仪器分析中的质谱分析、光谱分析、色谱分析、电力系统中的电网分析等等;另外有些数值计算方法本身也是以线性代数方程组的数值解、有限元法和边界元等等,其中间过程或者最后都会导致求解线性代数方程组。这些线性代数方程组的解法是十分必要的,有着十分重要的意义。
§ 概述
本章介绍求解n阶线性代数方程组的一般形式是:
或简写成矩阵形式:
其中A称为方程组()式的系数矩阵;B称为方程组的右端列向量;x称谓方程组解的列向量。它们分别为
()
()
§ 概述
求解线性代数方程组的数值计算方法很多,大致可分为两大类:消去(元)法和迭代法。消去法是直接从方程组的系数矩阵入手,经过有限步运算求出方程组的精确解(假如没有舍入误差的话)。迭代法则是将求方程组的问题化为构造一组递推计算结构,从一组近似解出发,用这组递推结构逐步算出精度更高的近似解。上述这两类算法各有其优点和缺点,消去法的计算量小,但程序复杂;迭代法计算量大,精度不高,但程序结构简单。
本章将主要介绍求解线性代数方程组的简单高斯消去法和三角分解法,迭代法将在以后相关章节中介绍。
§ 高斯消去法
§
我们以三元线性代数方程组为例,叙述简单高斯消去法(以下简称为消去法)的基本步骤,这各方法是理解其它方法的基础,消去法分为消元和回代两个过程。
例4-1:
消去过程实际上是对增广矩阵作行初等变换。上例可表示为
§ 高斯消去法
这是上三角方程组,它极容易求解:由第三个方程得,
代入第二个方程得,再代入第一方程。此一过程称为回代过程。
从上述消元过程可以看出,三元议程组要经过两次消元(因为不用消)才能把增广矩阵化为拟上三角矩阵。对于一般的n元线性代数方程组,经经过(n-1)次消元才能把相应的增广矩阵变换为拟上三角矩阵。n元线性代数方程组的增广矩阵的一般形式如()式。
§ 高斯消去法
以下是消元步骤(共分n-1部):
第一步(k=1):从第一列中消去第2~n行中x1的系数,即消去a11下方元素;
第二步(k=2):从第一列中消去第3~n行中x2的系数,即消去a22下方元素;
()
§ 高斯消去法
第j步(k=j):从第j列中消去第j+1~n行中xj的系数;即消去ajj下方元素;
第n-1步(k=n-1):从第n-1列中消去第n行中xn-1的系数;即消去an-1n-1下方元素
因此,高斯消元步骤的计算通式可写为:
()
§ 高斯消去法
经过n-1步消元后,增广矩阵()式变为:
()
§ 高斯消去法
高斯回代过程的通用递推计算公式可写为:
()
§ 高斯消去法
§
我们从(4-4)式可以看出,高斯消去法消去过程共分n-1步,第k步变换n-k行:对这些行先乘系数,再从n+1-k元素减去第k行相对应列的元素;因此共需乘、除次数为
回代过程求xn需1次除法,求xn-1需1次乘法、1次除法,…,求x1需n-1次乘法、1次除法,因此共需乘除次数
两过程共需要乘除次数为。当n=20时,N=3060.