• / 91
  • 下载费用:10 下载币  

数值分析(08)解线性方程组的迭代法

关 键 词:
数值分析课件
资源描述:
数值分析数值分析迭代法适用于求解大型稀疏的线性方程组,其基本思想是通过构造迭代格式产生迭代序列,由迭代序列来逼近原方程组的解,因此,要解决的基本问题是: 1. 如何构造迭代格式 型稀疏方程组的迭代法一 、 基本迭代法及其收敛性二 、 几种基本迭代法三 、 应用实例数值分析数值分析一 、基本迭代法及其收敛性设有线性代数方程组A=M+N , 要求 b (M+N)x=Nx+b x=用矩阵表示: 系数矩阵,非奇异且设 ; A x b x B x g B M N g M b      1 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2n n n n na x a x a x ba x a x a x ba x a x a x b              数值分析数值分析1(11 ) ( ),,( 0, 1 , 2, )x b x B M N g M g        基其 中 称 为 迭 代 矩本 迭 代 法 的阵 , 是 已 知迭 格 式的代维 向 量 ,( 0 ) ( 1 ) ( )(), , ( 0 , 1 , 2 , ){}x B x g    给 定 由 迭 代 格 式即 可 产 生 迭 代 序 列 。()( 1 ) ( )x x g Ax b   当 时 ,对 取 极 限得注:如何分裂 值分析数值分析20, 3336,A x b A M N M N                              例 :解 :8 - 3 2对 线 性 方 程 组 , 其 中 = 4 1 1 - 16 3 1 28 0 0 0 - 3 2将 分 裂 为 , 其 中 = 0 1 1 0 = 4 0 - 10 0 1 2 6 3 0231312()20 3 233 436 6 3A x b x M N x M b M b N        - 1 - 1 - 11 0081001110012231312( 20 3 2 ) / 8( 33 4 ) / 11( 36 6 3 ) / 12x x xx x xx x x        123数值分析数值分析( ) ( )23( ) ( )13( ) ( )12( 20 3 2 ) / 8( 33 4 ) / 11( 36 6 3 ) / 12 0, 1 , 2, ... x xx x xx x x k         (k+1)1(k+1)2(k+1)3迭 代 格 式 的 分 量 形 式 为( ( 3, 2, 1 )(10)迭 代 到 第 10 次 , 得 到已 知 精 确 解 为( 1 ) ( )0, 1 , 2, ...., x g                       迭 代 格 式 的 矩 阵 形 式 ,3 2 2 00 84 1 3 3迭 代 矩 阵 = - 01 1 1 1 1 16 3 3 6- - 01 2 1 2 1 2数值分析数值分析( 1 ) ( )( ) ( 0 )(), ( 0 , 1 , 2 , ){}x g    迭 代 法产 生 的 迭 代 序 列 , 如 果 对 任 取 初 始 向 量 都 有 则 称 此 迭 代 法 是 收 敛 的 , 否 则定 义是 发 散 的 。( ) ( ) ( ) ( )1212( ) ( )( , , , ) ,( , , , ) , ( 1 , 2 , , )k k k k x x xx x x x Rx x x x i n         对则在 列的收敛等价于每个分量的收敛。 即 ()( ) ( )( ) ( )( ) , ( ) ,l i m l i m , ( , 1 , 2, , )j i j i a A a a i j n       同 理 , 的 收 敛 与 所 选 择 的 范 数 无 关 。若则l i m 0 数值分析数值分析( ) ( 1 )( ) ( ) ( 1 ) ( 1 )( 0 )( 0 ) ( 0 )()( 1 , 2, )k k x b x B x x gx x B x x          是 精 确 解迭 代 格 式 为误 差 向 量其 中 是 初 始 误 差 向 量 , 是 一 个 确 定 的 值 ( 0 )() 0 ( ) k   k=0由 此 , 得 到 结 论 : 对 任 意 初 值 ,迭 代 序 列 收 敛数值分析数值分析:1112212J o rd a  例 形 矩 阵()J o r d a 的 约 当 标 准 形  1, n P P A P JJ o r d a n J 存 在 阶 可 逆 矩 阵 , 使形 矩 阵 的 对 角 线 元 素 是 的 全 部 特 征 值 。21111 2 1232的 代 数 重 数 为 , 几 何 重 数 为 ;的 代 数 重 数 为 , 几 何 重 数 为 ;数值分析数值分析1111 222J ()1112123的代数重数为 ,几何重数为 ;的代数重数为 ,几何重数为3 ;112 21212J () 111223的代数重数为 ,几何重数为2 ;的代数重数为 ,几何重数为1 ;数值分析数值分析11 1 0,: 4 3 2P P A P o r d a n 求 可例逆 矩 阵 使设为 标 准 形解 ,)1()2(2010340112  321  的特征值为所以 0)2(,21  0000100010010140132 ~ p 0 ,1属 于 特 征 值的 一 个 特征 向 量 取 为数值分析数值分析由解方程时当 ,132  ,000210101101024012~ 21,,1231,2)(不可相似对角化故数的几何重数小于代数重特征值因此的几何重数是特征值2211 11112,,由   221321321 1,,,,.,, 3222211  数值分析数值分析   于是有232 )(  1210)( 2解方程011)( 32 解方程 1 1 2 30 1 1, , 0 2 11 1 0P p p p  数值分析数值分析121 P 由 矩 阵 的 标 准 型 知 存 在 非 奇 异 阵 使( 1 ) ( )( 0 )(), ( 0 , 1 , 2 , )( ) 1 x g    迭 代 法 收 敛 的 充 要 条 件迭 代 格 式 对 任 意 初 始向 量 都 收 敛 的 充 分定 理 3 条 件 是( ) ( 0 ): 0 ( ) ) ( ) 1 .k k kB k B       由 知 迭 代 法 收 敛以 下 证 明 的 充 分 必 要 条 件 是证 明数值分析数值分析(),11( 1 , 2, , )1i r 为 若 当 块 且1111 1 1 1,n B P J B B P P B P P B P P B P   于 是数值分析数值分析11 2, ( 1 , 2, ) P J   1, , 0 0 J J    故显 然 当 时120 0 ( 1 , 2, , )( ) ( ) m , , , ), 0 1 , ( 1 , 2, , ) i i r          为 此 只 需 证 明数值分析数值分析22221211 0 2 10 1 , 0 2 ,0 0 0 0( 1 )2000k k kk k       例 :数值分析数值分析0 1 ( )0 ( ) 1 ( 1 , 2 , , )0 ( ) ( ) 1j k k i rB k B              由 极 限 运 算 知 :所 以即 证 明 了 结 论 结 论1 ( 1 )112 ( 2 )1111()! ( 1 ) ( 1 ),! ( ) ! !k k i k in k k i k k k k k j j              其中数值分析数值分析21 , 2d e t ( ) 6 0 , 6 ,( ) 2 . 4 4 9 1 . 3 7         特 征 多 项 式 为 得由 定 理 迭 代 格 式 不 收 敛( 1 ) ( )12( 1 ) ( )2152( 1 , 2 , )33511 讨 论 如 下 迭 代 格,例 式 的 收 敛 性02 ,30B  : 迭 代 格 式 的解 迭 代 矩 阵 为数值分析数值分析( ) ( 1 )(), ( 0,381 , 2, )1 , x g 迭 代 法 收 敛 的 充 分 条 件如 果 迭 代 格 式 的 迭 代矩 阵 的 某 一 种 范 数 则 此 迭 代理格 式 收 敛定, . , ( 12- 1, 2, )()   ( 特 征 值 上 界 定 理 )设 对 于 有定 理数值分析数值分析( ) ( 1 ) ( ) ( )( ) ( ) ( 1 )1k k k kk k kx x B x x B x x x        从 而( ) ( 1 )( ) ( ) ( 1 )( ) ( 1 ) ( 0 ), ( 0 , 1 , 2 , )1 , 911k x g x x x x       如 果 迭 代 格 式的 迭 代 矩 阵 满 足 则 有 如 下 的 误 差 估 计 式定 理( ) ( 1 )( ) ( 1 )( 1 ) ( ) ( ):()( ) ( )k x g x Bx gx x B x xB x x B x x        由 和证 明 有数值分析数值分析: ( 1 ) , .( 2) 1 , 小 收敛越快接近 时 收敛慢( ) ( 1 ) ( 1 ) ( 2 )1( 1 ) ( 2 ) ( 1 ) ( 0 )()( ) ( )k k k x B x xB x x B x x        ( ) ( ) ( 1 ) ( 1 ) ( 0 )11kk k x x x x    ( ) ( 1 ) ( 1 ) ( 2 )( ) ( 1 ) ( 1 ) ( 2 )()k k k kk k k x g x B x gx x B x x          又 因 为 ,数值分析数值分析m a xm a x( 3) 给 出 最 大 迭 代 次 数当 迭 代 终 止 , 给 出 失 败 信 息 。( ) ( 1 )()( ) ( 1 ) ( ) ( 1 )|| || ( 1 , 2, ).,|( 1 )| || m |k k x x x x       绝 对 误 差 标 准 。 给 出 容 许 误 差 界当 时 , 终 止 迭 代 ,解 取 为常 取( ) ( 1 )()| | | || | | |( 2 )相 对 误 差 标 准 。 给 出 容 许 误 差 界迭 代 终 止 标 准数值分析数值分析( ) ( 1 ) ( 0 )1x x x  由误差估计式 估计迭代次数( ) ( 1 ) ( 0 )( 1 ) ( 0 )1x x     估 计 迭 代 次 数数值分析数值分析( ) ( 0 )( ) ( 0 )| | | | | | | | | | | | |由得收 敛 速 度l n ( ( ) ) 为 迭 代 格 式 的 渐定 义 近 收 敛 速 度 。()()| | | | 0 , ( )( ) | | | | ( ) 0 , ( ) B k        越 小 , 越 快 。, 越 小 , 越 快 。数值分析数值分析( 1 ) ( ) ( )3 2 31 2 1( ) , ( 0 , 1 , . . . )k k x A x b kA x b            已 知 , , 用 迭 代 公 式求 解 。 问 取 什 么 实 数 可 使 迭 代 收 敛 , 且 为 何值 时 ,例 :收 敛 最 快 。232 5 4 ( 1 ) ( 4 )12           1 , 1 4 ,B I A         12迭 代 矩 阵 的 特 征 值 为1 1 1 1 1 2 0,11 4 1 1 1 4 1 0,2                        1 , 4 ,A 12的 特 征 值 为B I A(1) 迭 代 矩 阵解 :数值分析数值分析( 2 ) 1 1 4 ( 1 ) 1 425 2 ,525                当 时 , 收 敛 最 快 。1 02   当 时 , 迭 代 格 式 收 敛 。思考: A为 如何处理 411 12251数值分析数值分析()()x B x g I B x    实际计算中,存在舍入误差当 呈病态时,迭代舍入误差分析解会失真。数值分析数值分析二、几种基本迭代法1、 松弛迭代法( 、对称超松弛迭代法( 、块超松弛迭代法( 值分析数值分析1、 代法(同步迭代法) 12 121211 , 12,112 4221 4 21 1 44 0 0 0 0 0 0 2 20 4 0 , 1 0 0 , 0 0 20 0 4 1 1 0 0 0 0A D L U                                例:数值分析数值分析1111()( ) ,b x D L U x D bB x L U g D b      于是其中( 1 ) ( ) 迭 代 法 的 矩 阵 迭 代 格 式()()A x b D L U x bD x L U x L U x D b          数值分析数值分析推导其分量形式1 1 1 1 2 2 1 3 3 1 12 2 2 2 1 1 2 3 3 2 21 1 2 2 1 1n n n nn n na x a x a x a x ba x a x a x a x ba x a x a x a x b                第 i =1,2,… ,n),得( ) ( )A x b D L U x b D x L U x b        由 得13 112 11 2 311 11 11 1123 221 22 1 322 22 22 221 2 11 2 1n nn nn nn x x xa a a x x xa a a aa a a bx x x xa a a a                数值分析数值分析13 112 11 2 311 11 11 1123 221 22 1 322 22 22 221 2 11 2 1n nn nn nn x x xa a a x x xa a a aa a a bx x x xa a a a                1 ) ( ) ( ) ( )13 112 121311 11 11 11( 1 ) ( ) ( ) ( )23 221 213222 22 22 22( 1 ) ( ) ( ) ( )1 2 11 2 1k k k k k k k kn n n n n n n n n n x x xa a a x x xa a a aa a a bx x x xa a a a                 数值分析数值分析112 111 11 11()12221 ()() 22222 22()1200,0n n a x            令 : ,则 x(k+1)=k)+g ,这里 +U) , g=1 ) ( )1( ) / ,1 , 2 , ,i i j j i b a x  ( 1 ) ( )a c o b iB x g 迭 代 法 的 矩 阵 格 式x(0), 即可得到向量序列:x(1),x(2),…,x (k),…若 x(k) → x*, 则 x*是解。数值分析数值分析例 1: 设方程组为3103220241225321321321并求解 。10310351)323(10152141)220(415125152)212(51)(2)(1)(2)(1)1(3)(3)(1)(3)(1)1(2)(3)(2)(3)(2)1(110551104231 05 10取 x(0)=(0,0,0)t, e=10止准则: ‖x(k)-x(<4)=: 设方程组为1 2 31 2 31 2 35 2 1 24 2 2 02 3 1 0 3x x xx x xx x x         解: ( 1 ) ( ) ( ) ( ) ( )1 2 3 2 3( 1 ) ( 1 ) ( ) ( 1 ) ( )2 1 3 1 3( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )3 1 2 1 21 2 1 12( 12 2 )5 5 5 51 1 1( 20 2 ) 54 4 23311( 3 2 3 )10 5 10 10k k k k kk k k k kk k k k kx x x x xx x x x xx x x x x                         2、 异步迭代法)数值分析数值分析( 1 ) ( ) ( ) ( )13 112 121311 11 11 11( 1 ) ( 1 ) ( ) ( )23 221 213222 22 22 22( 1 ) ( 1 ) ( 1 ) ( 1 )1 2 11 2 1k k k k k k k kn n n n n n n n n n x x xa a a x x xa a a aa a a bx x x xa a a a                  量形式1( 1 ) ( 1 ) ( )11( ) / ,1 , 2 , ,k ki i i j j i j j i ij j ix b a x a x     数值分析数值分析( 1 ) ( ) ( )1312 121311 11 11( 1 ) ( 1 ) ( )2321 213222 22 22( 1 ) ( 1 ) ( 1 )31 32 33 1 233 33 33k k kk k kk k x xa a x xa a aa a bx x xa a a           由( 1 ) ( ) ( )1 1 1 1 2 2 1 3 3 1( 1 ) ( 1 ) ( )2 2 2 2 1 1 2 3 3 2( 1 ) ( 1 ) ( 1 )3 3 3 3 1 1 3 2 2 3k k kk k kk k ka x a x a x ba x a x a x ba x a x a x b            得( 1 ) ( 1 ) ( )k k kD x b L x U x  2131 3212 13230 0 00000000 0 0推导 阵形式数值分析数值分析( 1 ) ( ) ( ) ( )13 112 121311 11 11 11( 1 ) ( 1 ) ( ) ( )23 221 213222 22 22 22( 1 ) ( 1 ) ( 1 ) ( 1 )1 2 11 2 1k k k k k k k kn n n n n n n n n n x x xa a a x x xa a a aa a a bx x x xa a a a                   由( 1 ) ( ) ( ) ( )11 1 12 2 13 3 1 1( 1 ) ( 1 ) ( ) ( )22 2 21 1 23 3 2 2( 1 ) ( 1 ) ( 1 ) ( 1 )1 1 2 2 1 1k k k k k k k n n n nn n na x a x a x a x ba x a x a x a x ba x a x a x a x b                   得( 1 ) ( 1 ) ( )k k kD x b L x U x  数值分析数值分析()A x b D L x b U x    ( 1 ) ( 1 ) ( )( 1 ) ( )( 1 ) 1 ( ) 1()( ) ( )k k x b x b U L U x D L b           ( 1 ) ( ) x g  代 法 的 矩 阵 格 式) , ( ) L U g D L b   其 中数值分析数值分析1( 1 ) ( 1 ) ( )11( ) / , 1 , 2 , ,k ki i i j j i j j i ij j ix b a x a x a       ( 1 ) ( )11( ) , ( ) x L U g D L b    代 法 的 矩 式中阵其格x(0), 即可得到向量序列:x(1),x(2),…,x (k),…若 x(k) → x*, 则 x*是解。数值分析数值分析m a xm a x, , ,:( ) 0, ( 1 , 2, , )1 , ,0A b s Se 给 出 , 允 许 误 差 界 最 大 迭 代 次 数计 算 步迭 代 法 求 解 线 性 方骤 如 下① 置② 对 循 环 执 行 到 第 ⑨ 步③程 组 的 计 算步 骤 如置下 :( ) ( 1 )()( , , ) , ,( , , ) ,a c o b i k i j x xk i j x程 序 实 现 : 法 : 三 套 循 环 , 两 套 数 组 代 法 : 三 套 循 环 , 一 套 数 组 2, ,()0( , ) ( ) ,( 1 , 2, , ; )( ) ( ( ) ) / ( , )(),,,, x m su m a i j x jj n j ix i b i su m a i x i S R E R R k  对 循 环 执 行 到 第 ⑧ 步④⑤⑥⑦⑧ 如 果 则⑨ 如 果 停 机 。⑩ 输 出 结 果数值分析数值分析算法 3 x = x,k]=,b)[n n]=);x=,n);k=1:1000;i=1:;xb=x(i);j=1:i~=j,s=s+A(i,j)*x(j);i)=(b(i)A(i,i);x(i)n<%n',k,值分析数值分析3- 123- 132 对 称 正 定 代 法 收 敛若 是 对 称 正 定 的定 理 :,则 是 对定称 正 定 迭理 :代 法 收 敛( ) 1,|| || 1( ) 1|| || 1a c o b 收 敛 敛 原 则 敛3 - 1 03 - 1 1,| | | | 1 , a c o b a c o b i( 充 分 准 则 )严 格 对 角 占 优 迭 代 法严 格 对 角 占 优 代 法 收 敛 。迭 代 法 准 则 :定 理 :定 理 : 代 法 收 敛 值分析数值分析1 1m a   10,:, i D A B a c o b    且 的 元 素 为证 明 ① 迭 代 法11 1,ma x j a a c o b i      严 格 对 角 占 优即所 以 迭 代 法 收 敛定理 3 - 10 如果  是严格对角占优阵,则对任意的初值 )0(x , 代法和 代法都是收敛的。 数值分析数值分析111de t ( ) de t ( ( ) ) 0,,1de t ( ) 0 de t ( ( ) ) 0D L D L D L U        上 式 可 改 写 为已 知 严 格 对 角 占 优 的 对 角 元 非 零故 , 只 有1( ) a u s s S e id e l B D L UG a u s s S e id e l迭 代 法 的 迭 代 矩 阵 为② 迭 代 法11,, ( ) 0 ,d e t ( ) d e t [ ( ) ] 0, x x I B I D L U       设 有 特 征 值由 方 程 组 有 非 零 解 于 是 有反 证1( ( ) ) ,A D L U由 严格对角占优可推出 也严格对角占优数值分析数值分析1( ( ) )A D L U由 严 格 对 角 占 优 可 推 出 也 严 格 对 角 占 优5221 5 21 1 5225121 ( ) 1 51 1 5A D L U     = 严 格 对 角 占 优当 时 , 也 严例 :格 对 角 占 优1, d e t ( ( ) ) 0 ,1 , ( ) 1 , G S    是 非 奇 异 阵 应 有 , 矛 盾故 的 特 征 值 即 收 敛 证 毕 。数值分析数值分析0, 9410 100033, 9 15004230 15( ) , ( )22A x b au e i de                   改 变 方 程 组 中 方 程 的 次 序 , 即 将 系 数 矩 阵 作 行交 换 , 会 改 变 迭 代 法 的 收 敛 性 。例 :与 迭 代 的 迭 代 矩 阵 分 别 为谱 半 径 分 别 是 。 均 不 收 敛 。数值分析数值分析'''' ' ',3 10 9 494 3 10Ax bA x x au e l           若 交 换 方 程 的 次 序 , 得 的 同 解 方 程 组为 严 格 对 角 占 优 阵 , 因 而 对 方 程 组 用与 迭 代 求 解 均 收 敛 。数值分析数值分析定理 3 - 12 如果 A 是对称正定矩阵,则对任意的初值 )0(x , e l 迭代是收敛的。
展开阅读全文
  石油文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:数值分析(08)解线性方程组的迭代法
链接地址:http://www.oilwenku.com/p-10797.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
copyright@ 2016-2020 石油文库网站版权所有
经营许可证编号:川B2-20120048,ICP备案号:蜀ICP备11026253号-10号
收起
展开