第八章 解线性方程组迭代法

1、8 解线性方程组数值的迭代法解线性方程组数值的迭代法直接法直接法: 高斯消元法高斯消元法 列主消法列主消法 迭代法迭代法: 雅可比雅可比 (Jacobi) 高斯高斯-赛德尔赛德尔(Gauss-Seidel)线性方程组的矩阵形式：线性方程组的矩阵形式：AX = b (1) 预备知识预备知识当当b=0时，为齐次方程组：时，为齐次方程组：AX = 0 (2)若若|A|0，方程组，方程组(1)有唯一解。有唯一解。齐次方程组齐次方程组(2)有非零解的充要条件是：有非零解的充要条件是： |A| = 0对矩阵对矩阵A，若存在向量，若存在向量x和和，满足满足Ax = x预备知识预备知识则则x为为A的特征向量，

2、的特征向量，为为A的特征值。的特征值。迭代法？迭代法？ AX = b 1112111212222212nnnnnnnnaaaxbaaaxbAXbxbaaa线性方程组线性方程组X = BX + f X (k+1) = B X (k) + f 给定初值给定初值 X(0)，可以得到向量序列，可以得到向量序列 X(k) 迭代法举例迭代法举例 12120.50.50.50.5xxxx 12210.50.50.50.5xxxx (1)( )12(1)( )210.50.50.50.5kkkkxxxx 12120.50.50.50.5xxxx 12212121xxxx (1)( )12(1)( )21212

3、1kkkkxxxx (1)( )12(1)( )210.50.50.50.5kkkkxxxx (1)( )12(1)( )212121kkkkxxxx 100.50.50B20220B？为何？为何, ,迭代矩阵性质，范数迭代矩阵性质，范数X = BX+f (1)X(k+1) = B X(k) +f (2)定理定理8.3(充分条件充分条件)给定方程组给定方程组 (1)，如果，如果| B | 1，则，则 方程组有唯一解方程组有唯一解X* 对任意初始向量对任意初始向量X(0) Rn，迭代格式收敛于，迭代格式收敛于X*，且有，且有 3. 4. (1)*( )*kkXXBXX( )*( )(1)1kkk

4、BXXXXB( )*(1)(0)1kkBXXXXB迭代法迭代法 12120.50.50.50.5xxxx 12210.50.50.50.5xxxx (1)( )12(1)( )210.50.50.50.5kkkkxxxx 100.50.50B| B1 |1 =0.5，格式收敛。，格式收敛。迭代法迭代法 12120.50.50.50.5xxxx 12212121xxxx 20220B| B2 |1 = | B2 |2 =2, | B2 | = 4，格式不收敛？，格式不收敛？(1)( )12(1)( )212121kkkkxxxx 8.1 雅可比雅可比(Jacobi)迭代法迭代法 12312312

5、31023210152510 xxxxxxxxx123213312(23)/10(215)/10(210)/5xxxxxxxxx(1)( )( )123(1)( )( )213(1)( )( )312(23)/10(215)/10(210)/5kkkkkkkkkxxxxxxxxx例子例子11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb 111221331112222123322111 122,11111nnnnnnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa(1)( )( )

6、( )11122133111(1)( )( )( )2121 1233222(1)( )( )( )1122,11111kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa矩阵形式矩阵形式 2112300.0nnnaLaaa 1122.nnaaDa121,112,120.0.0nnnnaaaaaU 11121312122232123.nnnnnnnaaaaaaaaAaaaaA= -L+D-UA= -L+D-UAX = bX = D-1(L+U)X+ D-1bX(k+1) = D-1(L+U) X(k)+ D-1b迭代矩阵：迭

7、代矩阵：BJ = D-1 (L+U) fJ = D-1 b还与矩阵BJ和常数向量fJ有关。如对于任意X(0)，均有成立，则称雅可比迭代收敛转换成转换成令令迭代收敛迭代收敛，则对任意初始向量X(0)都成立8.2 向量和矩阵的范数向量和矩阵的范数 引子：绝对值函数引子：绝对值函数 2xx三个性质：三个性质：（1） x 0 , x = 0当且仅当当且仅当x = 0 （2）ax = a x a为常数为常数 （3） x+ y x + y 二维欧氏空间的长度二维欧氏空间的长度 一、范数的概念一、范数的概念12(,)Txxx2212|xxx三个性质：三个性质：（1） x 0 , x = 0当且仅当当且仅当x

8、 = 0 （2）ax = a x a为常数为常数 （3） x+ y x + y 非负性非负性齐次性齐次性三角不三角不等式等式1. 1. 向量范数向量范数 设设 X = (x1, x2 , , xn)T，记为，记为 X Rn定义定义8.1设设X Rn，f(X)= X 表示定义在表示定义在Rn 上的一个实值函上的一个实值函数，如果它满足下列条件：数，如果它满足下列条件： 1）非负性：）非负性：即对任意即对任意X Rn，| 0， | = 0当当且仅当且仅当X = 0 XaaX3）三角不等式：）三角不等式：即对任意两个向量即对任意两个向量X、Y Rn ，满足，满足 XYXY2）齐次性：）齐次性：即对任

9、意实数即对任意实数a R，X Rn ，满足，满足 aXaX称之为称之为 X 的范数的范数 三个常用的向量范数三个常用的向量范数 1211|nniiXxxxx22221221nniiXxxxx1maxiinXx 补充一个定义补充一个定义设向量设向量X ,Y Rn，则称，则称 X-Y 为为 X 和和 Y 之间的距离。之间的距离。近似解与准确解之间的距离（的大小）近似解与准确解之间的距离（的大小）向量范数向量范数-度量误差向量的大小度量误差向量的大小。对于给定的允许误。对于给定的允许误差界差界e e，当，当k充分大时，如果误差向量的范数满足充分大时，如果误差向量的范数满足已经达到了所要求的已经达到了

10、所要求的例例8.2 二维向量的三种范数二维向量的三种范数与图与图8-2的对应的对应2. 矩阵矩阵范数范数 11121312122232123.nnnnnnnaaaaaaaaAaaaa定义定义8.2设设A为为n阶方阵，阶方阵， 满足满足4个条件个条件 为矩阵为矩阵 A 的范数。的范数。( )N AA2. 矩阵矩阵范数范数 ( )N A0AcAc AABABABA B三个常用的范数三个常用的范数 矩阵矩阵范数范数 1111maxmaxnijjniAAa 22max()( )BTAAA ABmax为矩阵 的谱半径,11maxmaxnijinjAAa 1-范数范数(列和范数列和范数)2-范数范数(也称

11、谱范数也称谱范数)范数范数(行和范数行和范数)矩阵范数有下列基本性质：矩阵范数有下列基本性质：矩阵矩阵范数范数 1) 对任意对任意A Rnxn，|A 0， |A = 0当且仅当当且仅当A = 0 2) 对任意实数对任意实数c和任意和任意A Rnxn，有，有 |cA|=|c| |A| 3) 对任意两个对任意两个n阶矩阵阶矩阵A、B有有 | A+B | A + | B 4) 对任意两个对任意两个n阶矩阵阶矩阵A、B，有，有 | AB | A | B 相容性条件相容性条件2) 对任意实数对任意实数c和任意和任意A Rnxn，有，有 |cA|=|c| |A| 3) 对任意两个对任意两个n阶矩阵阶矩阵A

12、、B有有 | A+B | A + | B 4) 对任意两个对任意两个n阶矩阵阶矩阵A、B，有，有 | AB | A | B 相容性条件相容性条件2) 对任意实数对任意实数c和任意和任意A Rnxn，有，有 |cA|=|c| |A| 3) 对任意两个对任意两个n阶矩阵阶矩阵A、B有有 | A+B | A + | B 4) 对任意两个对任意两个n阶矩阵阶矩阵A、B，有，有 | AB | A | B 相容性条件相容性条件雅可比雅可比(Jacobi)迭代法的收敛性迭代法的收敛性 ( )(1)*( )*(1)*111kkJJJJkkJkJkkJkJkXB XfXB XfXXBXXeB eeB eBe01

13、lim0kkJJkkeBeBe即收敛。得雅可比迭代收敛的一个充分条件：得雅可比迭代收敛的一个充分条件：BJ的无穷范的无穷范数小于数小于1 1二、赛德尔二、赛德尔(Seidel)迭代法迭代法(1)( )( )( )11122133111(1)( )( )( )2121 1233222(1)( )( )( )1122,11111kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa(1)(1)(1)( )( )( )11122133111(1)( )( )2121 12332221)(1)1122,111)111kkkknnkkk

14、nnknnnnn nnkkknnkxba xa xa xaxba xa xa xaxba xa xaxa(i=1,2, ,n)与雅可比迭代法不同的是，上式右端有第(k+1)次近似解的部分数据X(k+1) = D-1 (LX(k+1) + UX(k) ) + D-1bX(k+1) = (D - L)-1 U X(k) + (D-L)-1 b迭代矩阵：迭代矩阵：BS= (D-L)-1U(D-L)X(k+1) = UX(k) + b方程组方程组AX=b系数矩阵系数矩阵分解成分解成A=D-L-U，其，其中中D为对角矩阵，为对角矩阵，U为为严格右上角矩阵，严格右上角矩阵，L为为严格左下角矩阵严格左下角矩

15、阵考卷试题类型(初定)u 填空题 5u 选择题 5u 简答题 2u 计算题 6复习复习1. 引论引论u 误差与有效数字误差与有效数字2. 解线性方程组的直接法解线性方程组的直接法u 高斯消元法、列主消元法、三对角高斯消元法、列主消元法、三对角方程组的追赶法方程组的追赶法 (满足的满足的3个条件、算法个条件、算法实施过程、乘除法次数实施过程、乘除法次数)4. 数据拟和数据拟和3. 插值法插值法u 定理定理3.1(节点互异节点互异-插值多项式存在且唯一插值多项式存在且唯一)，拉格，拉格朗日线性插值公式，抛物插值公式、插值误差公式朗日线性插值公式，抛物插值公式、插值误差公式u 最小二乘法，超定方程组

16、，掌握最小二乘法最小二乘法，超定方程组，掌握最小二乘法求解数据拟合曲线求解数据拟合曲线(n次多项式次多项式)建立建立u 注意其它函数向线性或二次拟合函数的转化再求解注意其它函数向线性或二次拟合函数的转化再求解uBezier曲线的三个性质曲线的三个性质(公式表示或言语表达公式表示或言语表达)5. 数值积分方法数值积分方法u 梯形公式及其积分误差梯形公式及其积分误差(梯形与曲边梯形面积比较梯形与曲边梯形面积比较)u 辛普生公式、复合梯形公式辛普生公式、复合梯形公式u 数值积分的代数精度与高斯求积公式数值积分的代数精度与高斯求积公式6. 常微分方程数值解常微分方程数值解u Euler方法方法 (差分、数值积分差分、数值积分)及其精度问题及其精度问题u 改进改进Euler方法