第6章线性方程组的迭代解法..ppt

第六章线性方程组的迭代解法
§1 向量和矩阵的范数
向量的范数
矩阵的范数
§2 迭代解法与收敛性 
迭代法的构造
迭代法的收敛性条件
§3 常用的三种迭代解法
Jacobi迭代法
Gauss-Seidel迭代法
超松弛(SOR)迭代法
6/20/2018
1
第六章线性方程组的迭代解法
§1 向量和矩阵的范数
一、向量的范数
为了对线性方程组数值解的精确程度,以及方程组本身的性态进行分析,需要对向量和矩阵的“大小”引进某种度量,范数就是一种度量尺度,向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。
||·||是向量空间Rn上的实值函数,且满足条件
求解线性方程组的数值解除了使用直接解法,迭代解法也是经常采用的一种方法,这种方法更有利于编程计算,本章将介绍这种方法。
6/20/2018
2
第六章线性方程组的迭代解法
则称||·|| 为 Rn 空间上的范数,|| x ||为向量 x 的范数。
理论上存在多种多样的向量范数,但最常用的是如下三种。
(2)齐次性:对任何实数和向量x
|| α x||=| α| || x ||
(3)三角不等式:对任何向量x和y,都有
|| x+y ||≤|| x ||+|| y ||
设向量x=(x1,x2,…,xn)T,定义
(1)非负性:对任何向量 x,
|| x ||≥0,且|| x ||=0当且仅当x=0
可引进极限
6/20/2018
3
第六章线性方程组的迭代解法
向量1-范数:
向量2-范数:
向量∞-范数:
容易验证,以上三种范数都满足向量范数的三个条件。
设x=(1,-3,2,0)T,求向量范数|| x ||p,P=1,2,∞。
欧氏范数
最大范数
6/20/2018
4
第六章线性方程组的迭代解法
解:对于向量 x=(1,-3,2,0)T ,根据定义可以计算出:
|| x||1=| 1 |+|-3 |+| 2 |+| 0 |=6
由此例可见,向量不同范数的值不一定相同,但这并不影响对向量大小做定性的描述,因为不同范数之间存在如下等价关系。
6/20/2018
5
第六章线性方程组的迭代解法
定义(范数的等价性) Rn上两种范数||·||α和||·||β称为等价的,如果存在着正数 m,M,使得:
范数的等价性表明,一个向量若按某种范数是一个小量,则它按任何一种范数也将是一个小量。(等价有传递性)容易证明,常用的三种向量范数满足下述等价关系。
|| x ||∞≤|| x ||1 ≤ n|| x ||∞
|| x ||∞≤|| x ||2 ≤|| x ||∞
|| x || 2≤|| x ||1 ≤n|| x ||2
例如:
n维向量x的一切范数都等价
6/20/2018
6
第六章线性方程组的迭代解法
对于向量序列
向量序列{x(k)} 收敛于向量 x*,当且仅当它的每一个分量序列收敛于xi*的对应分量,即
及向量
如果
则称向量序列 x(k) 收敛于向量 x* 。记作
或
收敛与取哪种范数无关
6/20/2018
7
第六章线性方程组的迭代解法
二、矩阵的范数
矩阵范数是反映矩阵“大小”的一种度量,具体定义如下。
设||·||是以n阶矩阵为变量的实值函数,且满足条件:
(1)|| A ||≥0,且|| A ||=0时,当且仅当A=0
(2)||αA||=|α| || A||,α∈R
(3)||A+B|| ≤|| A ||+|| B ||
(4)|| AB ||≤|| A || || B ||
则称|| A ||为矩阵A的范数。
可定义矩阵极限
6/20/2018
8
第六章线性方程组的迭代解法
设 n 阶矩阵 A=(aij),常用的矩阵范数有:
矩阵1-范数:
矩阵2-范数:
矩阵∞-范数:
以上三种范数都满足矩阵范数的条件,通常将这三种矩阵范数统一表示为|| A ||p,P=1,2,∞。
列和
行和
谱范数. 不好
算理论上重要
6/20/2018
9
第六章线性方程组的迭代解法
设矩阵
求矩阵A的范数|| A ||p,P=1,2,∞。
解根据定义
由于
则它的特征方程为:
6/20/2018
10
第六章线性方程组的迭代解法