文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 线性方程组AX_b几种解法的比较研究
侵权投诉

线性方程组AX_b几种解法的比较研究

线性方程组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)

线性方程组AX_b几种解法的比较研究

-

线性方程组AX_b几种解法的比较研究

1b。

迭代公式的分量形式如下:

,i

=1,……,n;k=0,1,……

加速收敛方法--SOR方法:如果迭代算法产生的数列{X(k)}收敛,极限记为X,则由此产生迭代算法X(k+1)=X(k)+wR(k)。基于如上

线性方程组AX_b几种解法的比较研究

高斯

线性方程组AX_b几种解法的比较研究

-塞德尔迭代法的加速收敛法如下:

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,也为下次迭代的输入。其迭代公式为

线性方程组AX_b几种解法的比较研究

x

线性方程组AX_b几种解法的比较研究

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)

线性方程组AX_b几种解法的比较研究

X

线性方程组AX_b几种解法的比较研究

*

线性方程组AX_b几种解法的比较研究

||迭代公式的分量形式如下:

,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)对分法:对分法是重复应用零点存在性定理,每次将区间压缩一半且其中至少包含一个根,直至最终区间长度(根的精度)满足要求为止。

线性方程组AX_b几种解法的比较研究

(2)黄金分割法:黄金分割法与对分法本质上一致,只不过每次压缩区间的比例不是一半,而是压缩比为0.618=

。(黄金分割

(4)三点抛物线法:给定初值x0,x1及x2

(三个点),过曲线上最新三个点的抛物线(代替曲线f(x))与x

线性方程组AX_b几种解法的比较研究

轴的交点的横坐标xn+1就是迭代的输出。其迭代公式如下:

其中:±符号的选取以使分母绝对值最大为原则;

(5)牛顿法:给定初值x0(点P0),将过曲线上当前点的切线(代替曲线f(x))与x轴的交点

线性方程组AX_b几种解法的比较研究

的横坐标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页)

第1页

你可能喜欢

  • 线性方程组的应用
  • 线性方程组求解方法
  • 线性方程组的直接解法
  • 线性代数方程组的解法
  • 线性方程组的消元解法
  • 解线性方程组的迭代法

热门文档

相关文档

  • 实习线性方程组AX_B的数值解法

    实习线性方程组AX_B的数值解法_计算机软件及应用_...线性代数方面的计算方法就是研究求解线性方程 组的...S迭代的比较一般来说,用J-迭代、G-S迭代都收敛的...

  • 【论文】关于非齐次线性方程组Ax=b两类解法的对比

    关于非齐次线性方程组Ax=b两类解法的对比_专业资料。给出相容的非齐次线性方程组的两种不同的解法,即矩阵的初等变换法及广义逆矩阵法,并证明了两种方法通解的...

  • 几种线性方程组的解法研究

    本文分析比较了解线性方程组中直接接法和迭 代解法,涉及到的内容有:算法的优化...? 雅可比迭代法是将一个线性方程组 Ax=b 等价 写成 x=Bx+g,选取初始向量 ...

  • 关于线性方程组Ax=b的解的注记

    线性方程组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几种解法的... ...二分法一般常用于为方程提 供初始近似值当计算出的近似根比较准确时,再用其他方法...

  • 在LabVIEW编程平台下求解线性方程组Ax_b

    ( 广东工业大学, 广州 510643) 摘要: 先引入关于线性方程组 Ax = b 解法的...3 实验结果两种算法的比较实验结果表 算法 TPID PVPID 时间 ( s) 2 534 1 ...

  • 线性方程组Ax=b的反问题的一般解

    在研究直接控制系统绝对稳定充要条件时, 92II 提出了一个关于线性方程 Ax—b ... 齐次线性方程组基础解系... 3页 免费 线性方程组AX_b几种解法... 2页 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email