线性方程组迭代法的收敛速度

系部 学号 实验题目

数计系

专 业 姓 名

计算机科学与技术

日期 成绩

2010 年 12 月

实验三： 实验三：解线性方程组的迭代法

一.实验目的 1.熟练运用已学过的迭代法求解线性方程组， 包括雅克比迭代法、 迭代法和 SOR 迭代法。 G-S 2.加深对计算方法技巧，选择正确的计算方法来求解各种线性方程组。 3.培养使用电子计算机进行科学计算和解决问题的能力。 二.实验环境 VC++6.0 实验语言：c++ 三.实验内容 1.试用雅克比迭代法和高斯塞德尔迭代法求解如下的线性方程组，设置精度为 1.0e-6:

10 1 1 x1 6.2 1 10 2 x2 = 8.5 2 1 5 x 3.2 3 2. 用 w=1 及 w=1.25 的 SOR 方法求解如下的线性方程组， 设置精度为 0.5e-7(初值为(1,1,1))

4 3 0 x1 24 3 4 1 x2 = 30 0 1 4 x 24 3 四.实验公

第6章

解线性方程组的迭代方法

6.1 迭代法的基本概念 6.2 雅可比迭代法与高斯-赛德尔迭代法

6.3 超松弛迭代法 6.4* 共轭迭代法

上页

下页

6.1 迭代法的基本概念6.1.1 引 言 对线性方程组 Ax=b, (1.1) 其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 第5章 讨论的选主元消去法是有效的. 但对于大型稀疏矩 阵方程组(A的阶数n很大 104,但零元素较多), 利 用迭代法求解是合适的. 本章将介绍迭代法的一些基本理论及雅可比 迭代法，高斯-赛德尔迭代法，超松弛迭代法，而 超松弛迭代法应用很广泛。 下面举简例，以便了解迭代法的思想.上页 下页

例1 求解方程组

8 x1 3 x2 2 x3 20, 4 x1 11 x2 x3 33, 6 x 3 x 12 x 36. 2 3 1记为Ax=b,其中

(1.2)

x1 8 3 2 30 A 4 11 1 , x x2 , b 33 . x 6 3 12 36 3 此方程组的精确解是x*=(3,2,1)T

实验一 线性方程组迭代法实验

一、

实验目的

1．掌握用迭代法求解线性方程组的基本思想和计算步骤；

2．能熟练地写出Jacobi迭代法的迭代格式的分量形式，并能比较它们各自的特点及误差估计；

3.理解迭代法的基本原理及特点，并掌握Jacobi迭代Gauss-Seidel迭代和SOR迭代格式的分量形式、矩阵形式及其各自的特点；

4.掌握Jacobi迭代Gauss-Seidel迭代和SOR迭代算法的MATLAB程序实现方法,及了解松弛因子对SOR迭代的影响；

5.用SOR迭代法求解线性方程组时，超松弛因子?的取值大小会对方程组的解造成影响，目的就是能够探索超松弛因子?怎样对解造成影响，通过这个实验我们可以了解?的大致取值范围。

二、

实验题目

1、迭代法的收敛速度

用迭代法分别对n=20，n=200解方程组Ax=b,其中

?4??????A?????????1315131513??134???...15134?15?15??15134?13?15???????11?3?5??4?13?1?34??n?n

（1）选取不同的初值x0和不同的右端向量b，给定迭代误差，用两种迭代法计算，观测得到的迭代向量并分析计算结果给出结论；

（2）取定初值x0

hao

第3章 解线性方程组的迭代法

清华大学工程硕士数学课程--数值分析 数值方法

§1 Jacobi迭代法和Gauss-Seidel迭代法

（I）迭代概念

（1） Ax b ， A Rn n， b R

A M N ， M R

n n

n

， N R

n n

，

M非奇异

Mx Nx

b

Mx Nx b

x M

1

Nx M

1

1

b

如果令 B M

1

N,f Mb，那么上式写成

（2） x Bxf 此方程组等价于Ax b

任给x

(0)

R，

(1)

n

x x

Bx

(0)

f f

(2)

Bx

(1)

（3） x

(k 1)

Bx

(k)

k(

f

(k)

)

由（3）可以确定 x

x

(k)

，当x

x R，即

*n

x

*

0 时，有

*

*

x Bx f

x同样满足 Ax b

*

*

定义 式（3） x

(k 1)

Bx

k(

f称为求解 （1）

)

Ax b 的简单形式迭代法，B称为迭代矩阵。

（II）Jacobi迭代法

hao

Ax b

写成分量形式有

n

a

j 1

ij

xj bi,

i 1,2, ,n

i 1n

ij

aiixi

a

j 1

xj

j i 1

aijxj bi,i 1,2, ,n

假定 aii 0 ，那么有 xi

1aii

i 1

n

ij

(bi

3.4 向量和矩阵的范数

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维

向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范 数。

向量和矩阵的范数

在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1,

x2之间距离用| x1-x2 |表示。

向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用 x 2 y 2 | OP 表示。而平面上 | 任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。

| P1 P2 | ( x1 x 2 ) ( y1 y 2 )2

2

向量范数定义3.4.1 设任一向量x R n , 按某一确定的

x ||, 且满足 : 1)非负性： || x || 0,当且仅当x 0时， || x || 0; 2)奇次性： || kx || | k ||| x ||, k R; 3)三角不等式：对任意 x, y R , 都有 || x y || || x || || y || ,法则对应于一非负实数 ||n

则称 || x || 为向量x的范数。

常见的向量范数设向

3.4 向量和矩阵的范数

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维

向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范 数。

向量和矩阵的范数

在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1,

x2之间距离用| x1-x2 |表示。

向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用 x 2 y 2 | OP 表示。而平面上 | 任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。

| P1 P2 | ( x1 x 2 ) ( y1 y 2 )2

2

向量范数定义3.4.1 设任一向量x R n , 按某一确定的

x ||, 且满足 : 1)非负性： || x || 0,当且仅当x 0时， || x || 0; 2)奇次性： || kx || | k ||| x ||, k R; 3)三角不等式：对任意 x, y R , 都有 || x y || || x || || y || ,法则对应于一非负实数 ||n

则称 || x || 为向量x的范数。

常见的向量范数设向

解线性方程组的迭代方法 1 引言 2 基本迭代法

3 迭代法的收敛性

上页

下页

1 引对线性方程组

言

Ax=b, (1.1) 其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 用前面讨 论的选主元消去法是有效的. 但对于大型稀疏矩阵方 程组(A的阶数n很大，但零元素较多), 利用迭代法求解 是合适的. 迭代法的基本思想就是用逐次逼近的方法去求线 性方程组的解。 本章将介绍迭代法的一些基本理论及雅可比迭代 法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭 代法应用很广泛。 下面举简例，以便了解迭代法的思想. 上页 下页

例1 求解方程组

8 x1 3 x2 2 x3 20, 4 x1 11 x2 x3 33, 6 x 3 x 12 x 36. 2 3 1记为Ax=b,其中

(1.2)

x1 8 3 2 30 A 4 11 1 , x x2 , b 33 . x 6 3 12 36 3 方程组的精确解是x*=(3,2,1)T. 现将改写为上页 下页

1 3 x 2 2 x 3

第四章 解线性方程组的迭代法

对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、节约内存，使用迭代法更有利。本章介绍迭代法的初步内容。

§1 雅克比法、赛得尔法、超松驰法

1．雅克比（Jacobi ）迭代法

设有n 阶方程组

???????=+++=+++=+++n n nn n n n n n n b x a x a x a b x a x a x a b x a x a x a 22112222212111212111 （4.1）

若系数矩阵非奇异，且0≠ii a (i = 1, 2,…, n )，将方程组（4.1）改写成 ()()()

?????

??????----=----=----=--11,221112323122221213132121111111n n n n n n nn n n n n n x a x a x a b a x x a x a x a b a x x a x a x a b a x 然后写成迭代格式 ()()()???????????----=----=

浙江丝绸工学院学报,,

,

第

卷

,

第

期

,

年

月

关于解非线性方程组的迭代法的若干研究卢兴江浙江大学,

型

杭州

摘本文给出了求解非线性方程组的

要型迭代法的几何实质同时提出了新的研究方向并,。

设计了对一般非线性方程组运用的灵活而有效的算法关键词非线性方程组型迭代法

几何实质

。

中图分类号

引

言

对非线性方程组其中,

任

,

,

一

,

,

…人,,

」求解的方法甚多有迭代法同伦延拓算法,,

、

、

单纯形算法和区间迭代法等

。

在文献

中系统地介绍了。

阶非线性方程组,

的基本理

论完整地分析了该类方程组数值解的几种主要迭代法在众多的迭代法中以著名的法奋‘丢

一〔

‘

丢

〕

一‘

去

,

,

,

…,

最为引人注目它的最大优点是平方收敛且是强有力的有自校正性阵及其逆矩阵的代价很高,,,

。

但缺点是求。

矩阵

对初始点的要求较高。

,

不具有大范围收敛性、

另外

,

当

奇异或病态时计算不能顺利进行针对以上问题许多工作者对定型方程比较好的方法。

法作了种种改进修正

,

得到了一些对一般或某特

这类方法的迭代格式是去‘奋

一

去

汤

,

,

…

我们称这类方法为法、

型迭代法

。

常见的有修正,

法

、

下降法

、

带参数的为此针对

一

和

一

法等

。‘〕

对于解非线性方程组迭代法的研究虽有较长的历史本文收到日期一一

但问题远没有完全解决

,

浙江丝绸工学院学报

年、

第

卷

这一老问题种处理方法

,

解线性方程组的几种迭代算法

内容摘要:

本文首先总结了分裂法解线性方程组的一些迭代算法,在此基础上分别通过改变系数矩阵A的分裂形式和对SSOR算法的改进提出了两种新的算法,并证明了这两种算法的收敛性.与其它方法相比,通过改变系数矩阵A的分裂形式得到的新算法具有更好的收敛性,改进的SSOR算法有了更快的收敛速度.最后通过数值实例验证了这两种算法在有些情况下确实可以更有效的解决问题.

关键词:

线性方程组 迭代法 算法 收敛速度

Several kinds of solving linear equations

iterative algorithm

Abstract:

In this paper, we firstly summarize some Iterative algorithms of Anti-secession law solution of linear equations. Based on these, two new algorithms are put forward by changing the fission form of coefficient matrix A and improving the alg