计算方法3_线性方程组迭代解法.ppt

第3章线性方程组迭代解法 Iterative Techniques for Solving Linear Systems ??????????????????? nn nn 22n11n 2nn22 22 1 21 1nn12 12 1 11bxaxaxa bxaxaxa bxaxaxa????() ?直接法是通过有限步运算后得到线性方程组的解, 解线性方程组还有另一种解法,称为迭代法?迭代法:不是用有限步运算求精确解,通过迭代产生近似解逼近精确解?基本思想是将线性方程组 AX =B化为 X= BX+F , 再由此构造一个向量序列{X (k)}X (k+1) =BX (k) +F ?若{X (k)}收敛在某个极限向量 X *,则可得 X *就是() 式的准确解?线性方程组的迭代法主要有 Jocobi 迭代法、 Gauss Seidel 迭代法和超松弛(SOR) 迭代法?Jacobi 迭代和 Seidel 迭代由于收敛速度较慢,已经越来越不适应当前信息时代人们对计算速度和精度的要求,所以在实际应用中使用的并不多。但是, 他们体现了迭代法的最基本的思想,是学习其它迭代法的基础?如何构造迭代序列{X (n) }? ? {X (n)}在什么条件下收敛? ?收敛速率如何??误差估计. 若在求解过程中 X (k)?X*(k ??),由X (k+1) =?(X (k)) 产生的迭代 X (k)向X*的逼近,在数次迭代求解之后, 由于机器跳动产生的 X (k)值误差或是有效数字产生的舍入误差,都会在第 k+1 次迭代计算中自动弥补过来或逐步纠正过来。因此,在迭代求解过程中产生的各种误差是可以忽略的,即迭代求解无累积误差,实际上, X (k)只是解的一个近似,机器的舍入误差并不改变它的性质。迭代过程中经常要遇到向量范数,矩阵范数以及序列极限的概念。 向量和矩阵的范数 Norms of Vectors and Matrices 数值分析中,经常要用向量和矩阵,为了应用的需要(误差分析), 引入衡量向量和矩阵大小的度量——范数. 对于实数 x∈ R,我们定义了绝对值,满足?| x|≥0非负性? |α x|=| α|· |x| 齐次性? | x+y| ≤|x|+|y| 三角不等式类似地,定义向量范数 在实 n维线性空间 R n中定义一个映射,它使任意X∈R n有一个非负实数与之对应,记为||X ||,且该映射满足: ?正定性任意 X∈R n ,||X|| ≥ 0,if and only if X=0 时, || X|| =0 ?齐次性任意 X∈R n , λ∈ R,有||λX ||=|λ|· ||X || ?三角不等式任意 X,Y ∈R n,有|| X+Y|| ≤||X|| + ||Y|| 则称该映射在 R n中定义了一个向量范数. 注:R n中的范数不唯一. 常用的向量范数有三种: 设 X=(x 1 , x 2,…, x n) T∈R ??????? ni inxxxxX:—1 1 211?范数 2 11 2222 212)x(xxxX:—2 ni in????????范数 inix max X:—????? 1 范数注: (1) 用范数的定义可验证上述皆为向量范数(2) p=1,2, ||X|| p即为|| X|| 1 ,||X|| 2. (3) 任意 x∈R n: p 1n1i pip)x(X:—p???范数????XX lim pp????????????3 2 1X ][例3X 14 941X 6321X 2 1??????????定理 设||?|| α和||?|| β是R n上任意两种范数,则存在正常数 C1 和 C2 ,使得对一切 X∈R n有 C1 ||X || α?||X || β? C2 ||X || α??????????XnXX XnXX XnXX 1 2 212有对于常用的三种范数, 注: R n中范数的等价性表明,虽范数值不同,但考虑到向量序列收敛性时,却有明显的一致性. R n中X= (x 1 , x 2,…, x n) T和Y= (y 1 , y 2,…, y n) T则有|yx| max ||YX|| )yx(||YX|| iini1 2 1 n1i 2ii2??????????????????????????????? 4254 .8x 6852 .1x 1791 .5x 5611 .1 544 . 28 x 6120 .9x 710 . 16 x 2220 .2 15913 x 333 . 10 x 15920 x 3330 .3 ][ 3 2 1 3 2 1 3 2 1 线性方程组例有解(x 1 , x