第七章解线性方程组的迭代法课件.ppt

《第七章解线性方程组的迭代法课件.ppt》由会员分享，可在线阅读，更多相关《第七章解线性方程组的迭代法课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 雅可比迭代法雅可比迭代法 高斯高斯-塞德尔迭代法塞德尔迭代法 SOR方法方法 迭代法的收敛性及误差估计迭代法的收敛性及误差估计2解线性方程组的迭代法解线性方程组的迭代法直接法直接法: : 经过有限次运算后可求得方程组精确解的经过有限次运算后可求得方程组精确解的方法方法( (不计舍入误差不计舍入误差!)!)迭代法：从解的某个近似值出发，通过构造一个无穷序列迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）去逼近精确解的方法。（一般有限步内得不到精确解） 直接法比较适用于中小型方程组。对高阶方程组，直接法比较适用于中小型方程组。对高阶方程组，既使

2、系数矩阵是稀疏的，但在运算中很难保持稀疏性，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。因而有存储量大，程序复杂等不足。 迭代法则能保持矩阵的稀疏性，具有计算简单，编制迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。地解一些高阶方程组。3 迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。1(0 )(1)()()() ()(,) , (k=0,1,2

3、,)TijnnnnnkkkkAxbAabbbxM xgMngRxRxM xgxkxAxb对 线 性 方 程 组其 中非 奇 异 矩 阵 ， 构 造 其 形 如的 同 解 方 程 组 ， 其 中为阶 方 阵 ，。任 取 初 始 向 量代 入 迭 代 公 式产 生 向 量 序 列， 当充 分 大 时 ， 以作 为方 程 组的 近 似 解 ， 这 就 是 求 解 线 M性 方 程 组的 单 步 定 常 线 性 迭 代 法 。称 为 迭 代 矩 阵 。4()()()()()( lim0 lim limknnkkkkknknikxRxRxxxxxxRxRxx 定义：设为中的向量序列，如果其中为向量范数，

4、则称序列收敛于 ，记为定理：中的向量序列收敛于中的向量 当且仅当)()()()()1212()()()()()1() (1,2, )(,) ,(,) lim010max lim=0 (1,2, ) kikkkkTTnnkkkkkkiijjjnkiikxinxxxxxxxxxxxxinxxxxxxxxin 其中。证：由定义，收敛于 即而对任意，有由极限存在准则得即() lim (1,2, )kiikxxin 5()()()()()()() lim0 lim () (1, 2,),(kkkkkkkkijijkAnAnAAAAAAAakAanAA 定 义 ： 设为阶 方 阵 序 列 ，为阶 方 阵

5、， 如 果其 中为 矩 阵 范 数 ， 则 称 序 列收 敛 于 矩 阵， 记 为定 理 ： 设)均 为阶 方 阵 ，则 矩 阵 序 列收 敛 于 矩 阵的 充()(1)()()(1)() lim ( ,1, 2,) , limlimkijijkkkkkkkkaaijnxM xgxxxxM xgM xgxA 要 条 件 为证 明 略 。定 理 表 明 ， 向 量 序 列 和 矩 阵 序 列 的 收 敛 可 以 归 结 为 对 应分 量 或 对 应 元 素 序 列 的 收 敛 。若 按产 生 的 向 量 序 列收 敛 于 向 量则 有即是 方 程 组xb的 解 。61111221n1211222

6、2n2n11n12nn 0 (1, 2,),nnnniiina xa xa xba xaxaxba xa xaxba 若 系 数 矩 阵 非 奇 异 即则 有112213311221123322n112233 nnnnnnnngxb xb xb xgxbxbxbxxb xbxbx , (, ,1, 2,),(1, 2,).ijiijiiiiiabbij ijnginaag 其 中712131111212321221231(0)(1)10(1)(2)( )(1)( )00 0 , nnnnnnnnnnkkkbbbbgbbbbgBgbbbbgxBxgxxxBxgxxxxBx（ ）（ ）若记则方程组

7、可简记为选初值向量代入，代入，如此继续下去，就产生一个向量序列满足(0,1,2,)gkJacobi此过程所给出的迭代法称为迭代法，又称简单迭代法。812112121221212120110001010 01001nnnnnnnnBbbbbbbbbbbbb AD I-aaaaaaaaaaaaInn1nnn2n12n22211n12111122111 1 12 111222(,)(, , , )TTnnnnggggbDbababa同 样91* n0 1 2 B gnnkJacobiBgxxxxxx（）（ ）（ ）迭代，若收敛，则*1*1* () IB xgDAxD bAxb即故如果序列收敛, 则收

8、敛到解。B称迭代矩阵。10123123123110272 10283542 10010100101200.10.210100011020.100.2100011150.20.201005 xxxJacobixxxxxxBIDA例：用迭代法求解解：1(0)(0)(2)(1)(9) (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3,8.4)(9.71,10.70,11.5)(10.9994,11.9994,12.9992)(11,12,13) .TTTTTgDbxBxgxBxgxx(1)取代入迭代式，得x精确解为11(0)(0)(0)(0)112(0)1(0)(0)1.(),( ,),

9、(,),.2.1.3.1,2, ()/4.,55.,1,(1,2, ),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xxin 输入维数最大容许迭代次数置对若输出停机；否则转 。若置转 ；否则，输出失败信息，停机。( )(1,kkMxx ）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。12(1)( )(1)( )( )( )112213311(1)( )( )( )221123322 (0,1,2,) kkkkkknnkkkknnxBxg kgxb xb xb xgxb xb xb x迭代公式用方

10、程组表示为(1)( )( )( )1122,11( )(1) kkkknnnn nnnkkJacobixxgxb xb xbx因此，在迭代法的计算过程中，需同时保留两个近似解向量和。若把迭代公式改写成13(1)( )( )( )112213311(1)(1)( )( )221123322(1)(1)112 kkkknnkkkknnkknnngxb xb xb xgxb xb xb xxb x(1)(1)2,11(0)( ) ,kkn nnnknxxGaussSeidelJacobigb xbx这样，在整个计算过程中，只需用 个单元存储近似解分量。而且通常认为，近似解可能比老近似解更接近精确解，

11、因此，可望这种迭代会更有效。选取初始向量用上式迭代产生近似解序列这种方法叫迭代法。评价：与相比，只需一组工作单元存放近似解。14(1)()1212,2112(1)()1(1)1()1 0000 U00 ()1,() ()()kknnnnkkkkLxU xgLIL xU xgILILxILU xILgbbbbbb(k+1)用矩阵表示为x其中，移项可得因为故存在，上式可改写为1512131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 如果用矩阵 来表示，记则由)1

12、(1)1( )11()()() () kkILgxDLUxDLbMDLUGaussSeidel式中矩阵为迭代法的迭代矩阵。16123123123(0)1(0)(0)12311(1)(0)21321310272 10283542(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.02001010 TxxxGaussSeidelxxxxxxxxxxbxxxbx（ ）（ ）（ ）例：用迭代法求解解：仍取代入迭代式，得(1)(1)123(5)11()7.20009.020042)11.644055(10.9989,11.9993,12.9996)(11,12,13

13、) .Txxbxx（如此继续下去，精确解为17 GauseseidelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauseseidelJacobi上例计算结果表明，迭代法比迭代法效果好。事实上，对有些问题迭代法确实比迭代法收敛得快，但也有迭代比迭代收敛得慢，甚至还有迭代收敛，迭代发散的情形。评价：与相比，只需一组工作单元存放近似解。18( 0 )( 0 )( 0 )( 0 )112( 0 )1111121( 0 )111.(),(,),(,),.2.1.3. () / () /(2,1) (ijnnnjjjiniiijjijjiijjinnAa

14、bbbn xxxxNkxbaxaxba xa xainxba 输 入维 数最 大 容 许 迭 代 次 数置计 算11( 0 )( 0 ) /4.,55.,1,(1, 2,),3nnjjnnjiixaxxxkNkkxxin若输 出停 机 ； 否 则 转。若置转；否 则 ， 输 出 失 败 信 息 ， 停 机 。19(1)( )(1)121(1)( )( )111(1)( )( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkkiijjijjijj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 为迭代法加速。记

15、其中由迭代公式得到。于是有( )(1)( )(1,2, )kkkinxGaussSeidelkxxxx 可以把看作迭代的修正项，即第 次近似解以此项修正后得到新的近似解 20(1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxba xa xai 松弛法是将乘上一个参数因子作为修正项而得到新的近似解，具体公式为即1,2, ) 111nAxbGaussSeidel按上式计算的近似解序列的方法称为松弛法，称为松弛因子。当时称为低松弛；是迭代；时称为超松弛法。21(1)( )( )1(1)1( )1( )( )1(1)1( )1111

16、1(1)1 () (1)1,() () (1kkkkkkkkkkxxxxDLxD UxD bxxDLxD UxD bIDLIDLDLxDL松弛法迭代公式的矩阵表示：因为故（） 与存在，有( )11)() () (1) ,kDU xDLbMDLDU松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大 但目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确定松弛因子。22(0)12123231(1)(1)( )11(1)( )( )112(1)( )22 1.4,(1,1,1) ,21 2021.8 (1)()0.40.7(1)0.4Tinkkkkiiiijji

17、jjjj iiikkkkkxxxxxxxxxxba xa xaxxxxx 例：取用超松弛法解方程组解：由(1)( )13(1)( )(1)332(0)(9)0.7()(0,1,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6001) (1.2,1.4,1.6)kkkkkTTTxxkxxxxxx 将代入上式开始迭代，精确解23(0 )(0 )(0 )(0 )112(0 )(0 )11111121(0 )(0 )111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxba

18、xaxxba xa xa 输 入维 数最 大 容 许 迭 代 次 数， 参 数置计 算1(0 )1(0 )(0 ) (2,1) (1)() /4.,55.,1,(1, 2,),3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若输 出停 机 ； 否 则 转。若置转；否 则 ， 输 出 失 败 信 息 ， 停 机 。2411212 (1,2, ) ( )max(,) (,)(1,2,), () (iii nnkkkkknAninAAAAAAAAkA 迭代法的收敛与迭代矩阵的特征值有关。定义：设 为 阶方阵，为 的特征值，称特征值的最大值为矩阵 的谱半径，记为称为矩阵 的谱。由特征

19、值的定义知，矩阵的谱是因而)kA25 :, ():, , () . :,iiiiiiiiiiiAnAAAuuuAuAuuAAAAn定理 设 为任意 阶方阵为任意由向量范数诱导出的矩阵范数 则证 对 的任一特征值及相应的特征向量都有因为为非零向量 于是有由的任意性即得证毕定理 设 为任意 阶方阵 则对任意正数存在一种矩阵2, () , ()()AAnAAAAA范数使得证明略。对任意 阶方阵 一般不存在矩阵范数使得。但若 为对成矩阵，则有。26 lim0()1 lim0 lim0 () 0()() lim()0 ()11 ()1kkkkkkkkkkkAnAAAAAAAAAAAA定理：设 为阶方阵，

20、则的充要条件为。证：必要性：若由矩阵收敛的定义知又因由极限存在的准则，有所以。充分性。若，取()0,21() ()12,limlim0lim0.kkkkkkkkAAAAAAAAA由上一定理知，存在一种矩阵范数，使得而27(0)(1)( )( )*( )*( ) (0,1,2,)()1. : , lim kkkkkkxgxMxgkxMnxxxxxMxgx定理：对任意初始向量和右端项 ，由迭代格式产生的向量序列收敛的充要条件是证 必要性 设存在 维向量使得则满足由迭代公式有*(1)*(1)*2(2)*(0)*(0)*( )*(0) ()()() lim()lim()0, lim0 ()1.kkkk

21、kkkkkkxMxgMxgM xxMxxMxxMxxxxxnMM于是有因为为任意 维向量 因此上式成立必须由上一定理28*()*(1)*(0 )*(0 )()* :()1,1,0, lim0 ()(), lim ()limkkkkkkkkMMIMngIMxgxxM xgMxxMxxMxxxxxM 充 分 性 若则不 是的 特 征 值 因 而 有于 是 对 任 意维 向 量方 程 组有 唯 一 解 记 为即并 且又 因 为所 以 对 任 意 初 始 向 量都 有(0 )*(1)()()(0 )(1)()()()=0.1 1, (0,1, 2,).kkkkkkkxxxM xgxxgMxM xgkx

22、即 由 迭 代 公 式产 生 的 向 量 序 列收 敛推 论对 任 意 初 始 向 量和 右 端 项， 若由 迭 代格 式产 生 的 向 量 序 列收 敛291212111122 2 02 , det()() det()1 det()()(1)1 () (1nnnnnMMMMMDLDUDLa aa 推论松弛法收敛的必要条件是。证：设松弛法的迭代矩阵由特征值。因为由定理，松弛法收敛必有又因为1122)(1)det()(1)102 nnnnDUa aaM。迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的

23、情形。30123123123221 2223 1122100 111 010221001000 100220 xxxxxxxxxADL例：对方程组讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性。解：求迭代矩阵判别其谱半径是否小于 。022 001000U3113123 Jacobi022 10122022 110220,()01,JacobiBIDAIBB迭代法的迭代矩阵为其特征方程为因此有于是所以迭代法收敛。321121 Gauss-Seidel100100 110 ()110221021100022022()11000102302100000222 023(2)00020,

24、DLDLMDLUIM 迭代，由特征方程特征值为232,()21,M故所以迭代发散。33 021 121,1,1 BM上例说明了确实只是松弛法收敛的必要条件，而非充要条件，因为Gauss-Seidel迭代记为的情形。判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用。如上例，两个方法均有由推论 无法判别收敛性。对一些特殊的系数矩阵可给出几个常用的判别收敛条件3411112112222 ()(1,2, ) ,0110 11nijiiijjj inAaaainiAiAAAAAAAAAA定义：若 阶方阵满足且至少有一个 值，

25、使上式中不等号严格成立，则称 为弱对角占优阵。若对所有 ，上式不等号均严格成立，则称为严格对角占优阵。定义：如果矩阵 不能通过行的互换和相应的列互换成为形式其中，为方阵，则称 为不可约。 例：132100011012011PITP AP 35 ,1.JacobiG auss-S eidel2.01,3.021012210 1102121115012A xbAAAABA设 有 线 性 方 程 组下 列 结 论 成 立 ：若为 严 格 对 角 占 优 阵 或 不 可 约 弱 对 角 占 优 阵 ， 则迭 代 法 和迭 代 法 均 收 敛 。若为 严 格 对 角 占 优 阵 ，则 松 弛 法 收 敛

26、 。若为 对 称 正 定 阵 ， 则 松 弛 法 收 敛 的 充 要 条 件 为。上 两 例 中 ：为 严 格 对 角 占 优B阵 ， 故 Jacobi与 Gauss-Seidel迭代 均 收 敛 。为 非 严 格 对 角 占 优 阵 ， 但 为 对 称 正 定阵 ，=1.4故 松 弛 法 收 敛 。36-11112211,122111223(02)11102211 -02211022Axb AAAABIDA例 ：讨 论 用 三 种 迭 代 法 求 解 的 收 敛 性 。解 ： 因为 对 称 且 其 各 阶 主 子 式 皆 大 于 零 ， 故为 对 称 正 定 矩阵 。 由 判 别 条 件，

27、Gauss-Seidel迭 代 法 与 松 弛 法均 收 敛 。不 是 弱 对 角 占 优 阵 ， 故 不 能 用 条 件 判 断 。Jacobi迭 代 法 的 迭 代 矩 阵 为373212311221131 224411221 ()(1 )021,1 , ()12 IBBJ a c o b i其特征方程得因而迭代法不收敛。38 310 , 9410100033 , 91500423015(),()22AxbAJacobiGaussSeidelBMBM改 变 方 程 组 中 方 程 的 次 序 ， 即 将 系 数 矩 阵 作 行交 换 ， 会 改 变 迭 代 法 的 收 敛 性 。例 ：与迭

28、 代 的 迭 代 矩 阵 分 别 为谱 半 径 分 别 是。 均 不 收 敛 。39 ,31094 94310AxbAxbAAAAxbJacobiGaussSeidel若交换方程的次序，得的同解方程组为严格对角占优阵，因而对方程组用与迭代求解均收敛。40(1 )()()*()*(1 )( 0 )1*1()*(1 )*( 0 )* ,1, 1 ()1,0 ,) ()() kkkkkkkkxM xgMxxMxxxxMMMIMIMxM xgxxIMgxxMxxMxx定 理 ： 设 有 迭 代 格 式若收 敛 于则 有 误 差 估 计 式证 ： 因故于 是(存 在 ， 方 程 组有 唯 一 解，且(。

29、 从 而 有( 0 )11( 0 )1( 0 )1 ) ) )kkkMxIMgMIMIMxgMIMxx（）(41()*1( 0 )11111111()* ) ) ) ) )1 )1 1kkkkxxMIMxxIMIMIIMIMIMIMIMIMIMIMIMMMxx（）取 范 数(又 因 为(取 范 数(移 项 得(代 入 得(1)( 0 )xxM。42()*(1)(0 )(1)(0 )(0 )(1)4( 1:(1)ln ln00.10.207.20.100.2,0,8.30.20.2008.410, 0.4, kkMxxxxMkMxxkMMxxMx由 误 差 估 计 式根 据 事 先 给 定 的

30、精 度， 可 估 计 出 迭 代 的 次 数例 ： 若则 有1)(0 )8.4 12.932,13xk即 需 要 迭 代次 才 能 满 足 精 度 。43(1)()()*()*()(1)()*(1)*(1)11(1)(1)1(1)()()*1(1) ,1, 1() )()kkkkkkkkkkkkkkkxMxgMxxMxxxxMxxM xxM xIMgM IMxMxgM IMxxxxMIMx定理：设有迭代格式若收敛于则有误差估计式证：因 ()()(1)()(1) .11kkkkkxMxxMMxx当不太接近 时，可用作为停机准则。4411112211211222221122 nnnnnnnnnnn

31、a x a xa xba x a xa xba x a xa xb阶线性方程组： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩阵表示记为这里45 工程实际计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特出的解法，如平方根法与改进的平方根法。 , TALALLL定理：设 是对称正定矩阵，则存在唯一的非奇异下三角阵使得且 的对角元素皆为正。46111112121222221211221000 0000 (1,2,).0 (),()(1,2,), () /(1,

32、)nnTnnnnnniijkjjjjjjkkijijikjkjjllllllllALLlllllinljklaljnlal llijn 由其中由矩阵乘法及当时得1101111222;0(2,3,)(3,)jkkiillinllin 这里规定。计算顺序是按列进行，即。4721114 2 ,; 2.()/(1,2, ).()/(,1,1).Tiiiikkiikniikikiik ibbacAAxbaLybyL xyxybl ylinxyl xlin n 当矩阵 完成平方根分解后，求解，即求解两个三角形方程组(1)求（ ），求3 /6, AnGaussAbLAy xbLn由于 的对称性，平方根法的乘

33、除运算量为数量级，约是消去法的一半。上机计算时，所需存储单元也少，只要存储 的下三角部分和右端项 ，计算中 存放在 的存储单元，存储在 的存储单元。但这种方法在求 时需作 次开方运算，这样又增加了计算量.为了避免开方，可使用改进的平方根方法。48123412413412342312552141635158xxxxxxxxxxxxxx例例 用平方根法求解方程组用平方根法求解方程组解解1213112131250522121010141161232535115831211A11210,11 3531221TALLLy ,1, 1, 1, 1 .TTL xy x 解毕故知故知解得解得491212122

34、11211 111 11,0 (),TnnnnnjjjkdldALDLlldllllljk 其中由比较法得5012111111 1,2, ,;()/(1, ). 1,2, ,;()/(1, ).iiiiikkkijijijkk ikikikikkiiiiik ikkijijiik jkikindal dlal d ldjintl dindat llat ldjin 对于上式虽避免了开方运算，但增加了相乘因子，引进变量对于有15111111 ,;(2, )./;/(1,2,1).TTTTiiiikkknnnniiikikk iALDLLLLDLLyb DL xyybybl yinxydxydl

35、xin 对称正定矩阵 按分解和按分解计算量差不多，但分解不需要开方计算。求解计算公式5211112222211111 .iiiiinnnnnnnnnxdbcxdabcxdabcAxdabcxdabxd 在数值计算中，如三次样条插值或用差分方法解常微分方程边值问题，常常会遇到求解以下形式的方程组简记 此系数矩阵的非零元素集中分布在主对角线及其相邻两次对角线上，称为三对角矩阵。方程组称为三对角方程组。53111122231 0 0(2,3,1)01111(1,2,1)iiiiinnnnnibcbaca cinbauclucALUlcluc in 定理：设三对角方程组系数矩阵满足下列条件：则它可分解

36、为其中为已给出的，且分解是唯一的5411111111 , (2,3,) 0(1 2,) /(2,3,)iiiiiiiiiiiiiiiAbualuimbc luuimublauimubc l将上式右端按乘法规则展开 并与 进行比较 得如果，则由上式可得5511( )111111111/(2,3, )kkkkkknnnnnkkkkkGausekucucAabcabcabubcaukn按消去法步骤易得，经次消元后，三对角方程的系数矩阵变为其中。5611112221 2121 2121 21 2121 2121 2122221111(2)2 0., 00(1,2, )iAubbcbacbbbabcc

37、abcbbc abbc abcc aubcubbbuAuinLU由于 满足定理所给条件，显然有又因为于是从而有故且矩阵仍满足定理条件。依此类推可得出。因此由上面公式唯一确定了 和 。5711111111 /(2,3, ) (2,3, )/: ()/(1,2,1) ,iiiiiiikkkknnnkkkkkubALUla uimubc lydLydydl yknxyuUxyxyc xuknnGause分解公式：解得：再解得追赶法的基本思想与消去法及三角分解法相同只是由于系数中出现了,大量的零可使计算公式简化减少了计算量。可证当系数矩阵为严格对角占优时此方法具有良好的数值稳定性。58A事实上，追赶法

38、的求解过程就是将系数矩阵事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两分解两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。个简单方程组的过程。上述定理也表明，追赶法的原理和高斯消去上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。量零元素撇开，从而大大节省计算量。59例例 用追赶法解下面三对角方程组用追赶法解下面三对角方程组12343 1 0 0101 4 1 0110 1 6 1300 0 2 848xxxx60解解：先把系数矩阵分解成如下形式

39、：先把系数矩阵分解成如下形式11223341 3 1 0 0 1 1 1 4 1 0 1 0 1 6 1 1 0 0 2 8 1 1pqpqpqp由递推公式可知由递推公式可知1111113, 3pbqcp2221222113, 113pba qqcp33323336311, 1163pba qqcp61444348263pba q又由递推公式（又由递推公式（4.274.27）可得：）可得：111103ydp2221223()11yda yp33323307()63yda yp44434()5yda yp62再由递推公式（再由递推公式（4.284.28）可得：）可得：445xy33344xyq

40、x22231xyq x11123xyq x故所求的解向量为故所求的解向量为3,1,4,5Tx 6360年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。实矩阵、非奇异。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。()(1)(1)(1)1(2)1(2)1111111 QRQR (1,2,). , kkkkkkAQ RkAR QAAAAAQ RQARAR QQAQAA基本方法的基本思想是利用矩阵的分解通过迭代格式将化成相似的上三角阵（或分块上三角阵），从而求出矩阵 的全部特征值与特征向量。由即。于是即

41、与相似。同理可()(2,3,)kAAk 得，。故它们有相同的特征值。64可证，在一定条件下，基本可证，在一定条件下，基本QR方法产生的矩阵序列方法产生的矩阵序列A(k) “基本基本”收敛于一个上三角阵（或分块上三角阵）。收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，对角线（或主对角线子块）以上元素可以不收敛。特别的，如果如果A是实对称阵，则是实对称阵，则A(k) “基本基本”收敛于对角矩阵。收敛于对角矩阵。因为上三角阵的主对角元（或分块上三角阵中，主对

42、因为上三角阵的主对角元（或分块上三角阵中，主对角线子块的特征值）即为该矩阵的特征值，故当角线子块的特征值）即为该矩阵的特征值，故当k充分大时，充分大时， A(k)的主对角元（或主对角线子块的特征值）就可以作为的主对角元（或主对角线子块的特征值）就可以作为A的特征值的近似。的特征值的近似。基本的基本的QR方法的主要运算是对矩阵方法的主要运算是对矩阵QR分解，分解的方分解，分解的方法有多种。介绍一种法有多种。介绍一种Schmit正交化方法。正交化方法。651212211112221121212121211121121111111222212 ,(,)(1,2, )., /. , ,0, /,1nT

43、jjjnjAnAaaaaaaajnaabaabaabbaaaaaaaaaaaaab baaaaaabbbbbbb设 为 阶非奇异实矩阵，记其中取取则1211121111, ,0., /(2,3,),1 (1,2,),kkkkiikkkinkkkkkkkkb bbaab bbbbknb bbbknaabbabbbb一般地取则向量组正交，且即661111121212112211, ,Q RkkkkkkknnnnnnnnaabbabbbbAaaabbbaababbabQ RbabbSchm it即于 是这 就 是 用正 交 化 方 法 对 矩 阵 进 行 的分 解 。67基本基本QR方法每次迭代都需

44、作一次方法每次迭代都需作一次QR分解与矩阵乘分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的法，计算量大，而且收敛速度慢。因此实际使用的QR方法是先用一系列相似变换将方法是先用一系列相似变换将A化成拟上三角矩阵（称化成拟上三角矩阵（称为上为上Hessenberg矩阵），然后对此矩阵用基本矩阵），然后对此矩阵用基本QR方法。方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。因为拟上三角矩阵具有较多零元素，故可减少运算量。化化A为相似的拟上三角阵的方法有多种。为相似的拟上三角阵的方法有多种。681231112222112222210 :121.012: (2,1,0) ,( 1,2,1) ,(0,1,2) .21 (,0) ,554213 6,( 1,2,1)(,0)(,1) ,5 5555365(,) ,707070TTTTTTTTSchmitAQRaaaababaabbbbbb 例 用正交化方法对进行分解解因而有3331132233322 4 6,(,) 7 7 7123 (,)141414TTaabbabbbbb69121212112211 , , ,253701145451515670214070516700570314002 40 7nnnnnnnnAa aab bbaa ba bba bba bb 所以