线性方程组数值求解

《数值分析》课程设计

线性方程组数值求解算法研究

院（系）名称专 业 班 级 学 号学 生 姓 名 指 导 教 师

摘 要

本课程设计用matlab就线性方程组数值方法，Jacobi迭代法，Gauss-Seidel迭代法，超松弛法对所设计的问题进行求解，并编写程序在Matlab中实现，在文章中对各种迭代法进行了收敛性分析。接着用几种不同方法对线性方程组进行求解及结果分析，最后对此次课程设计进行了总结。

关键词：线性方程组，迭代，

Matlab，结果分析

一、 提出问题

直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n<1000 ），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是系数矩阵就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。

迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根,如何建立迭代格式，向量序列{Xk}是否收敛条件等。

二、 算法的基本思想 线性方程组的数值法

a) 直接法——直接法是指在无舍入误差存在的情况下，经过有限 步运算即可求得方程组解的算法，因此，又称为精确法。这种方法是通过矩阵约化将原方程组化为与之等价的三角形方程组或其他形式的可直接求解的方程组而实现的。由于实际中存在舍入误差的影响，这种方法只能求得线性方程组的近似解。

通常用来解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组 比较著名的方法有：Gauss消去法，主元消去法，LU分解法，QR分解法，Cholesky分解法等。

b) 迭代法——迭代法是用某种极限过程去逐步逼近线性方程组 精确解的方法。迭代法具有需要计算机的存储单元较少，程序设计简单和原始系数矩阵在计算过程中始终不变等优点，但存在收敛性与收敛速度问题。迭代法是解大型稀疏矩阵方程组，尤其是由微分方程离散后得到的大型方程组的重用方法。比较著名的方法有：jacobi迭代法，Gauss-seidel迭代法，超松弛迭代法，梯度法，理查森迭代法。

与解f(x)=0 的不动点迭代相类似,将AX=b改写为X=BX+f 的形 式,建立雅可比方法的迭代格式： k+1=BX(k)+f ,其中，B称为迭代矩阵.其计算精度可控,特别适用于求解系数为大型稀疏矩阵

(sparse matrices)的方程组.

三、 算法的推导及步骤

对方程组 Ax b做等价变换 x Gx g 则，我们可以构造序列 x( k 1) G x (k) g

若 x(k) x* x* G x* g Ax* b

(k 1)(k)(k)

x* Gx Gx* G(x x*)同时： x

G

k 1

(x

(0)

x*)

所以，序列收敛 Gk 0与初值的选取无关

k

定义：（收敛矩阵） G 0定理： kG

0 (G) 1

矩阵G为收敛矩阵，当且仅当G的谱半径<1

由 ( G) G 知，若有某种范数 G 1 则，迭代收敛

p1. Jacobi迭代

a11x1 a1nxn b1

an1x1 annxn bn

x1

x2

xn

1a11

1a22 1ann 1a11 1a22 1ann

(a12x2 a1nxn b1)(a21x1 a23x3 a1nxn b2)

(an1x1 an n 1xn 1 bn)

(k 1) x1

(k 1) x2

(k 1)

xn

(a12x2(a21x1

(k)

a1nxn a23x3

(k)

(k)

b1)

(k)

(k)

a1nxn b2)

(an1x1

(k)

an n 1xn 1

(k)

bn)

格式很简单： i 1

1(k 1)(k)

x (ax ijj i

a

ii

j 1

n

aijxj

(k)

bi)

j i 1

2. Gauss－Seidel迭代

在Jacobi迭代中，使用最新计算出的分量值

(k 1) x1

(k 1) x2

(k 1) xn

1ann

(an1x1

i 1

(k 1)

1a11

1a22

(a12x2(a21x1

(k)

a1nxn a23x3

(k)

(k)

b1)

(k)

(k 1)

a1nxn b2)

an n 1xn 1

n

(k 1)

bn)

xi

(k 1)

1aii

( aijxj

j 1

(k 1)

a

j i 1

ij

xj

(k)

bi)

3. 松弛迭代(SOR)

(k)(k 1)(k)(k 1)(k)(k)

记 x x x 则 x x x可以看作在前一步上加一个修正量。

若在修正量前乘以一个因子 有 x(k 1) x(k) x(k) x(k 1) x(k) (x(k 1) x(k))对Gauss-Seidel迭代格式 x

(k 1)

D

1

(Lx

(k 1)

Ux

(k)

b)

x(k 1) x(k) (D 1Lx(k 1) D 1Ux(k) D 1b x(k))

(k 1)(k) 1(k 1) 1(k) 1x (1 )x (DLx DUx Db)

写成分量形式，有

(k 1) x1

(k 1)

x2

(k 1)

xn

(1 )x1

(k)

1a11

(a12x2

(k)

a1nxn

(k)

(k)

b1)

(k)

(1 )x2

(1 )xn

(k)

a22

(a21x1

(k)

a23x3 a1nxn b2)

(k)

1ann

(an1x1

(k)

an n 1xn 1

(k)

bn)

四、 算法分析（稳定.收敛.误差） 1. 算法及收敛性： 1.1. Jacobi迭代矩阵 记 A D L U

a11

D

0

0

0 ann

0

0

0 U

0

a12

a1n

an 1n

0

0

a21L

an1

ann 1

易知，Jacobi迭代有 (D L U)x b Dx (L U)x b x D(L U)x Db

G D

1

1 1

(L U) I D

1

A , g D

1

b

收敛条件：迭代格式收敛的充要条件是G的谱半径<1。对于Jacobi迭代，我们有一些保证收敛的充分条件 若A满足下列条件之一，则Jacobi迭代收敛。 ① A为行对角占优阵 aii

j i

aij

② A为列对角占优阵 a

③ A满足

i j

jj

i j

aij

aij

aii

1

1.2. Gauss－Seidel迭代矩阵 x(k 1) D 1(Lx(k 1) Ux

(k)

b)

(k)

1(k 1) 1

DUx (I DL)x

D

1

1

b

x x

(k 1)

(I DL)DUx

1 1 1(k)

(I DL)

1

1

Db

1

(k 1)

(D L)Ux

1

1(k)

(D L)b

1

G

(D L)U , g (D L)b

Gauss－Seidel收敛条件：迭代格式收敛的充要条件是G的谱半径<1。我们看一些充分条件

若A …… 此处隐藏：2485字，全部文档内容请下载后查看。喜欢就下载吧 ……