线性方程组AX=b几种解法的比较研究
赵慎行
(湖南商学院信息系 湖南长沙 410205)
摘 要:随着各个领域在近期以迅猛的速度发展,线性代数作为一门基础学科,在近期的发展也特别快,它的代表之一就是线性方程组。为了能更深入地了解它的特性,有必要先对它的几种解法研究一下。解可能出现三种情况:无解、有唯一解和有无穷多组解。求解方法大概可以划分为两类:直接消去方法、迭代数值解法。关键词:线性方程组 解法 比较中图分类号:G4文献标识码:A文章编号:0673-0534(2007)05(a)-0099-02
1 方程组的解法概要
对于线性方程组a11x1+...+a1nxn=b1…
am1x1+...+amnxn=bm可以写成矩阵的形式AX=b
其中Amn,bm1,Xn1均为矩阵,由线性代数知识可知。关于其解的理论如下:解可能出现三种情形:无解、有唯一解和有无穷多组解。这主要取决于系数矩阵A的秩与增广矩阵(A|b)的秩是否相等、秩与变量个数是否相等,具体地:
(1)若R(A)≠R(A|b),则AX=b无解;(2)若R(A)=R(A|b)=n(n为变量个数),则AX=b有唯一组解;
(3)若R(A)=R(A|b)<n,则AX=b有无穷多组解。求解方法大概可以划分为两类:直接消去方法(这主要是指高斯消去法)、迭代数值解法。
,i=1,...,
n;k=0,1,...
2.2 高斯-塞德尔迭代法
类似的方法可以得到高斯-塞德尔迭代公式X=BX+f,其中B=-(D+L)-1U,f=(D+L)

-

1b。
迭代公式的分量形式如下:
,i
=1,……,n;k=0,1,……
加速收敛方法--SOR方法:如果迭代算法产生的数列{X(k)}收敛,极限记为X,则由此产生迭代算法X(k+1)=X(k)+wR(k)。基于如上

高斯

-塞德尔迭代法的加速收敛法如下:
y[a,b]
|j(x)-j(y)| £ L|x-y|
则对任意初值x0[a,b],迭代过程xn +1= j(xn)产生的序列{xn}收敛到j(x)在[a,b]上的不动点.下面几个迭代方法是根据f(x)的几何性质与解析性质,从不同角度构造出迭代公式:xn+1=j(xn)
(2)单点割线法:给定初值x0(点P0)及当前值xn(点Pn),将曲线y=f(x)上当前点和初始点构成的割线(代替曲线)与x轴的交点的横坐标,作为本次迭代的输出xn+1,也为下次迭代的输入。其迭代公式为

x

n+1=xn-
(3)两点割线法:给定初值x0及x1(两个点),将曲线上最新的相邻(按迭代先后为序)两点的割线(代替曲线)与x轴的交点的横坐标,作为迭代输出。其迭代公式如下:
2 解法比较
(1)直接消去法:理论上,经过有限次算术运算能够求出方程组的精确解;实际上由于计算存在舍入误差,因此,可能得到的只是近似解。高斯消去法可以用LU分解来表示.如果方程组的系数矩阵A满足一定条件,则A可以分解为一个下三角阵L与一个上三角阵U的乘积: A=LU
于是由AX=b得到:
X=A-1b=(LU)-1b =U-1L-1b。用消元法解线性方程组。
(2)迭代法:常用的有雅可比迭代法和高斯-塞德尔迭代法等。其一般形式如下:
将AX=b等价变形为(形式不唯一):X = BX + f
由此构造迭代公式:
X(n+1)=BX(n)+f,n=0,1,...
可以证明:在B满足谱半径r(B)<1时,当n¥ 时,X(n)收敛,其极限X*就是原方程组的解。
2.1 雅可比迭代法
设A=L+D+U(矩阵分解:D为对角矩阵,L下三角矩阵,U为上三角矩阵),由AX=b得到:
(L+D+U)X=b,X=D-1[-(L+U)X+b]=BX+f
得到以上(矩阵)形式的迭代公式,其中:B=-D-1(L+U),f =D-1b。并且可以证明
||X(n+1)-X*||£||B||n+1||X(0)

X

*

||迭代公式的分量形式如下:
,i=1,……,n;k=0,1,……
矩阵形式为:X(k+1)=(D+wL)-1{[(1-w)D-wU]X(k)+wb}
比较:如果w=1,就是标准的高斯-塞德尔迭代法;如果w>1,就称为SOR(SuccessiveOver-Relaxation)方法。2.3 数值方法-迭代逼近
利用图形的方法或连续函数的零点存在性定理,可以推知f(x)在某一区间内有根,下面就基于此来讨论求根的数值方法。
a.区间迭代
(1)对分法:对分法是重复应用零点存在性定理,每次将区间压缩一半且其中至少包含一个根,直至最终区间长度(根的精度)满足要求为止。

(2)黄金分割法:黄金分割法与对分法本质上一致,只不过每次压缩区间的比例不是一半,而是压缩比为0.618=
。(黄金分割
(4)三点抛物线法:给定初值x0,x1及x2
(三个点),过曲线上最新三个点的抛物线(代替曲线f(x))与x

轴的交点的横坐标xn+1就是迭代的输出。其迭代公式如下:
其中:±符号的选取以使分母绝对值最大为原则;
(5)牛顿法:给定初值x0(点P0),将过曲线上当前点的切线(代替曲线f(x))与x轴的交点

的横坐标xn+1作为本次迭代的输出。其迭代公式如下:
比例)
b.点迭代
(1)简单迭代法:基于构造与方程f(x)=0等价的方程j(x)=x,得到迭代函数j(x),然后求迭代函数j(x)的不动点。注意到j(x)形式不唯一,可能其迭代差异很大。剩下来的工夫花在j(x)的构造上,即保证迭代算法的收敛性。对此,有如下结论:
定理:设j(x)在[a,b]上连续,且满足(1)对任意的x[a,b],j(x)[a,b]
(2)存在常数L[0,1],使得对于任意的x,
比较:对分法是重复应用零点存在性定理,每次将区间压缩一半且其中至少包含一个根,直至最终区间长度(根的精度)满足要求为止.黄金分割法与对分法本质上一致,只不过每次压缩区间的比例不是一半,而是压缩比例为0.618=
,(黄金分割比例)和简单跌代
法、单点割线法、两点割线法、三点抛物线法比较对于正定二次函数,牛顿法一步即可达到最优解。
(1)如果系数矩阵A的行数m等于列数n,
(下转101页)
实习线性方程组AX_B的数值解法_计算机软件及应用_...线性代数方面的计算方法就是研究求解线性方程 组的...S迭代的比较一般来说,用J-迭代、G-S迭代都收敛的...
关于非齐次线性方程组Ax=b两类解法的对比_专业资料。给出相容的非齐次线性方程组的两种不同的解法,即矩阵的初等变换法及广义逆矩阵法,并证明了两种方法通解的...
本文分析比较了解线性方程组中直接接法和迭 代解法,涉及到的内容有:算法的优化...? 雅可比迭代法是将一个线性方程组 Ax=b 等价 写成 x=Bx+g,选取初始向量 ...
线性方程组AX_b几种解法... 2页 免费 解线性方程组的ABS方法的... 5页...上对线性 方程组 Ax=6其中A∈( ,∈6 ) 了进 一步 的研究 ,作 是线性...
线性方程组解的研究 对线性方程组的几种解法的比较对线性方程组的几种解法的...代数作为一门基础学科,在近期的发展也特别快,它的代表之一就是线性方程组Ax=b...
解法研究是代数学中经典且重要的 研究课题.下面将综述几种不同类型的线性方程组...求解线性方程组 Ax ? k 等价于解两个三角方程组 Ly ? k 与 Ux ? y ,...
线性方程组AX_b几种解法... 2页 免费 第九章 有限元线性方程... 29页 ...? ? ? ? ? 3 3 2 2 3 2 6 与Grammer法则相比较,Gauss消去法的计算量...
齐次和非齐次线性方程组的... 6页 免费 线性方程组AX_b几种解法的... ...二分法一般常用于为方程提 供初始近似值当计算出的近似根比较准确时,再用其他方法...
( 广东工业大学, 广州 510643) 摘要: 先引入关于线性方程组 Ax = b 解法的...3 实验结果两种算法的比较实验结果表 算法 TPID PVPID 时间 ( s) 2 534 1 ...
在研究直接控制系统绝对稳定充要条件时, 92II 提出了一个关于线性方程 Ax—b ... 齐次线性方程组基础解系... 3页 免费 线性方程组AX_b几种解法... 2页 ...
热门文档