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

1、12 雅可比迭代法雅可比迭代法 高斯高斯-塞德尔迭代法塞德尔迭代法 SOR方法方法 迭代法的收敛性及误差估计迭代法的收敛性及误差估计3迭代法：从解的某个近似值出发，通过构造一个无穷序列迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）去逼近精确解的方法。（一般有限步内得不到精确解） 直接法比较适用于中小型方程组。对高阶方程组，直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。因而有存储量大，程序复杂等不足。 迭代法则能保持矩阵

2、的稀疏性，具有计算简单，编制迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。地解一些高阶方程组。4 迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。1(0 )(1)()()() ()(,) , (k=0,1,2,)TijnnnnnkkkkAxbAabbbxM xgMngRxRxM xgxkxAxb对 线 性 方 程 组其 中非 奇 异 矩 阵 ， 构 造 其 形 如的 同 解 方 程

3、 组 ， 其 中为阶 方 阵 ，。任 取 初 始 向 量代 入 迭 代 公 式产 生 向 量 序 列， 当充 分 大 时 ， 以作 为方 程 组的 近 似 解 ， 这 就 是 求 解 线 M性 方 程 组的 单 步 定 常 线 性 迭 代 法 。称 为 迭 代 矩 阵 。5()()()()()( lim0 lim limknnkkkkknknikxRxRxxxxxxRxRxx 定义：设为中的向量序列，如果其中为向量范数，则称序列收敛于 ，记为定理：中的向量序列收敛于中的向量 当且仅当)()()()()1212()()()()()1() (1,2, )(,) ,(,) lim010max lim

4、=0 (1,2, ) kikkkkTTnnkkkkkkiijjjnkiikxinxxxxxxxxxxxxinxxxxxxxxin 其中。证：由定义，收敛于 即而对任意，有由极限存在准则得即() lim (1,2, )kiikxxin 6()()()()()()() lim0 lim () (1, 2,),(kkkkkkkkijijkAnAnAAAAAAAakAanAA 定 义 ： 设为阶 方 阵 序 列 ，为阶 方 阵 ， 如 果其 中为 矩 阵 范 数 ， 则 称 序 列收 敛 于 矩 阵， 记 为定 理 ： 设)均 为阶 方 阵 ，则 矩 阵 序 列收 敛 于 矩 阵的 充()(1)()(

5、)(1)() lim ( ,1, 2,) , limlim kijijkkkkkkkkaaijnxM xgxxxxM xgM xgxA 要 条 件 为证 明 略 。定 理 表 明 ， 向 量 序 列 和 矩 阵 序 列 的 收 敛 可 以 归 结 为 对 应分 量 或 对 应 元 素 序 列 的 收 敛 。若 按产 生 的 向 量 序 列收 敛 于 向 量则 有即是 方 程 组xb的 解 。71111221n12112222n2n11n12nn 0 (1, 2,),nnnniiina xa xa xba xaxaxba xa xaxba 若 系 数 矩 阵 非 奇 异 即则 有11221331

6、1221123322n112233 nnnnnnnngxb xb xb xgxbxbxbxxb xbxbx , (, ,1, 2,),(1, 2,).ijiijiiiiiabbij ijnginaag 其 中812131111212321221231(0)(1)10(1)(2)( )(1)( )00 0 , nnnnnnnnnnkkkbbbbgbbbbgBgbbbbgxBxgxxxBxgxxxxBx（ ）（ ）若记则方程组可简记为选初值向量代入，代入，如此继续下去，就产生一个向量序列满足(0,1,2,)gkJacobi此过程所给出的迭代法称为迭代法，又称简单迭代法。91211212122121

7、2120110001010 01001nnnnnnnnBbbbbbbbbbbbb AD I-aaaaaaaaaaaaInn1nnn2n12n22211n12111122111 1 12 111222(,)(, , , )TTnnnnggggbDbababa同 样101* n0 1 2 B gnnkJacobiBgxxxxxx（）（ ）（ ）迭代，若收敛，则*1*1* () IB xgDAxDbAxb即故如果序列收敛, 则收敛到解。B称迭代矩阵。11123123123110272 10283542 10010100101200.10.210100011020.100.2100011150.20.

8、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精确解为12(0)(0)(0)(0)112(0)1(0)(0)1.(),( ,),(,),.2.1.3.1,2, ()/4.,55.,1,(1,2, ),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xx

9、in 输入维数最大容许迭代次数置对若输出停机；否则转 。若置转 ；否则，输出失败信息，停机。( )(1,kkMxx ）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。13(1)( )(1)( )( )( )112213311(1)( )( )( )221123322 (0,1,2,) kkkkkknnkkkknnxBxg kgxb xb xb xgxb xb xb x迭代公式用方程组表示为(1)( )( )( )1122,11( )(1) kkkknnnn nnnkkJacobixxgxb xb xbx因此，在迭代法的计算过程中，需同时保留两个近似解

10、向量和。若把迭代公式改写成14(1)( )( )( )112213311(1)(1)( )( )221123322(1)(1)112 kkkknnkkkknnkknnngxb xb xb xgxb xb xb xxb x(1)(1)2,11(0)( ) ,kkn nnnknxxGaussSeidelJacobigb xbx这样，在整个计算过程中，只需用 个单元存储近似解分量。而且通常认为，近似解可能比老近似解更接近精确解，因此，可望这种迭代会更有效。选取初始向量用上式迭代产生近似解序列这种方法叫迭代法。评价：与相比，只需一组工作单元存放近似解。15(1)()1212,2112(1)()1(1)

11、1()1 0000 U00 ()1,() ()()kknnnnkkkkLxU xgLIL xU xgILILxILU xILgbbbbbb(k+1)用矩阵表示为x其中，移项可得因为故存在，上式可改写为1612131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 如果用矩阵 来表示，记则由)1(1)1( )11()()() () kkILgxDLUxDLbMDLUGaussSeidel式中矩阵为迭代法的迭代矩阵0)1(0)(0)12311

12、(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) .Txxbxx（如此继续下去，精确解为18 GauseseidelJacobiGauseseidelJacobiGauseseidelJacobiJacobiGauses

13、eidelJacobi上例计算结果表明，迭代法比迭代法效果好。事实上，对有些问题迭代法确实比迭代法收敛得快，但也有迭代比迭代收敛得慢，甚至还有迭代收敛，迭代发散的情形。评价：与相比，只需一组工作单元存放近似解。19( 0 )( 0 )( 0 )( 0 )112( 0 )1111121( 0 )111.(),(,),(,),.2.1.3. () / () /(2,1) (ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxbaxaxba xa xainxba 输 入维 数最 大 容 许 迭 代 次 数置计 算11( 0 )( 0 ) /4.,55.,1,(1, 2,),

14、3nnjjnnjiixaxxxkNkkxxin若输 出停 机 ； 否 则 转。若置转；否 则 ， 输 出 失 败 信 息 ， 停 机 。20(1)( )(1)121(1)( )( )111(1)( )( )11 (,), 1 ()Tkkkninkkkiijjijjiijj iinkkkiijjijjijj iiiGaussSeidelxxxxxxxGaussSeidelxb xb xgxba xa xxa 为迭代法加速。记其中由迭代公式得到。于是有( )(1)( )(1,2, )kkkinxGaussSeidelkxxxx 可以把看作迭代的修正项，即第 次近似解以此项修正后得到新的近似解 21

15、(1)( )(1)1(1)( )11 (1)() (kkkkiiiinkkkiiijjijjjj iiixxxxxxxxba xa xai 松弛法是将乘上一个参数因子作为修正项而得到新的近似解，具体公式为即1,2, ) 111nAxbGaussSeidel按上式计算的近似解序列的方法称为松弛法，称为松弛因子。当时称为低松弛；是迭代；时称为超松弛法。22(1)( )( )1(1)1( )1( )( )1(1)1( )11111(1)1 () (1)1,() () (1kkkkkkkkkkxxxxDLxD UxD bxxDLxD UxD bIDLIDLDLxDL松弛法迭代公式的矩阵表示：因为故（）

16、 与存在，有( )11)() () (1) ,kDU xDLbMDLDU松弛法的迭代矩阵为松弛因子的选取对收敛速度影响极大 但目前尚无可供实用的计算最佳松弛因子的方法。通常是根据系数矩阵的性质及实际经验，通过试算来确定松弛因子。23(0)12123231(1)(1)( )11(1)( )( )112(1)( )22 1.4,(1,1,1) ,21 2021.8 (1)()0.40.7(1)0.4Tinkkkkiiiijjijjjj iiikkkkkxxxxxxxxxxba xa xaxxxxx 例：取用超松弛法解方程组解：由(1)( )13(1)( )(1)332(0)(9)0.7()(0,1

17、,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6001) (1.2,1.4,1.6)kkkkkTTTxxkxxxxxx 将代入上式开始迭代，精确解24(0 )(0 )(0 )(0 )112(0 )(0 )11111121(0 )(0 )111.(),(,),(,),.2.1.3. (1)() / (1)() / ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 输 入维 数最 大 容 许 迭 代 次 数， 参 数置计 算1(0 )1(0 )(0 ) (2,1) (1)() /4.,55.,1,(1, 2,)

18、,3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若输 出停 机 ； 否 则 转。若置转；否 则 ， 输 出 失 败 信 息 ， 停 机 。2511212 (1,2, ) ( )max(,) (,)(1,2,), () (iii nnkkkkknAninAAAAAAAAkA 迭代法的收敛与迭代矩阵的特征值有关。定义：设 为 阶方阵，为 的特征值，称特征值的最大值为矩阵 的谱半径，记为称为矩阵 的谱。由特征值的定义知，矩阵的谱是因而)kA26 :, ():, , () . :,iiiiiiiiiiiAnAAAuuuAuAuuAAAAn定理 设 为任意 阶方阵为任意由向量范数诱导

19、出的矩阵范数 则证 对 的任一特征值及相应的特征向量都有因为为非零向量 于是有由的任意性即得证毕定理 设 为任意 阶方阵 则对任意正数存在一种矩阵2, () , ()()AAnAAAAA范数使得证明略。对任意 阶方阵 一般不存在矩阵范数使得。但若 为对成矩阵，则有。27 lim0()1 lim0 lim0 () 0()() lim()0 ()11 ()1kkkkkkkkkkkAnAAAAAAAAAAAA定理：设 为阶方阵，则的充要条件为。证：必要性：若由矩阵收敛的定义知又因由极限存在的准则，有所以。充分性。若，取()0,21() ()12,limlim0lim0.kkkkkkkkAAAAAAA

20、AA由上一定理知，存在一种矩阵范数，使得而28(0)(1)( )( )*( )*( ) (0,1,2,)()1. : , lim kkkkkkxgxMxgkxMnxxxxxMxgx定理：对任意初始向量和右端项 ，由迭代格式产生的向量序列收敛的充要条件是证 必要性 设存在 维向量使得则满足由迭代公式有*(1)*(1)*2(2)*(0)*(0)*( )*(0) ()()() lim()lim()0, lim0 ()1.kkkkkkkkkkxMxgMxgM xxMxxMxxMxxxxxnMM于是有因为为任意 维向量 因此上式成立必须由上一定理29*()*(1)*(0 )*(0 )()* :()1,1

21、,0, lim0 ()(), lim ()limkkkkkkkkMMIMngIMxgxxM xgMxxMxxMxxxxxM 充 分 性 若则不 是的 特 征 值 因 而 有于 是 对 任 意维 向 量方 程 组有 唯 一 解 记 为即并 且又 因 为所 以 对 任 意 初 始 向 量都 有(0 )*(1)()()(0 )(1)()()()=0.1 1, (0,1, 2,).kkkkkkkxxxM xgxxgMxM xgkx即 由 迭 代 公 式产 生 的 向 量 序 列收 敛推 论对 任 意 初 始 向 量和 右 端 项， 若由 迭 代格 式产 生 的 向 量 序 列收 敛3012121111

22、22 2 02 , det()() det()1 det()()(1)1 () (1nnnnnMMMMMDLDUDLa aa 推论松弛法收敛的必要条件是。证：设松弛法的迭代矩阵由特征值。因为由定理，松弛法收敛必有又因为1122)(1)det()(1)102 nnnnDUa aaM。迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及右端项无关。对同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的方法发散的情形。31123123123221 2223 1122100 111 010221001000 100220 xxxxxxxxxADL例：对方程组讨论Jacobi迭代法与Ga

23、uss-Seidel迭代法的收敛性。解：求迭代矩阵判别其谱半径是否小于 。022 001000U3213123 Jacobi022 10122022 110220,()01,JacobiBIDAIBB迭代法的迭代矩阵为其特征方程为因此有于是所以迭代法收敛。331121 Gauss-Seidel100100 110 ()110221021100022022()11000102302100000222 023(2)00020,DLDLMDLUIM 迭代，由特征方程特征值为232,()21,M故所以迭代发散。34 021 121,1,1 BM上例说明了确实只是松弛法收敛的必要条件，而非充要条件，因为

24、Gauss-Seidel迭代记为的情形。判断定理虽然给出了判别迭代收敛的充要条件，但要求逆矩阵和特征值。推论 与 仅分别给出了收敛的充分与必要条件，许多情形下不能起作用。如上例，两个方法均有由推论 无法判别收敛性。对一些特殊的系数矩阵可给出几个常用的判别收敛条件3511112112222 ()(1,2, ) ,0110 11nijiiijjj inAaaainiAiAAAAAAAAAA定义：若 阶方阵满足且至少有一个 值，使上式中不等号严格成立，则称 为弱对角占优阵。若对所有 ，上式不等号均严格成立，则称为严格对角占优阵。定义：如果矩阵 不能通过行的互换和相应的列互换成为形式其中，为方阵，则称

25、 为不可约。 例：132100011012011PITP AP 36 ,1.JacobiG auss-S eidel2.01,3.021012210 1102121115012A xbAAAABA设 有 线 性 方 程 组下 列 结 论 成 立 ：若为 严 格 对 角 占 优 阵 或 不 可 约 弱 对 角 占 优 阵 ， 则迭 代 法 和迭 代 法 均 收 敛 。若为 严 格 对 角 占 优 阵 ，则 松 弛 法 收 敛 。若为 对 称 正 定 阵 ， 则 松 弛 法 收 敛 的 充 要 条 件 为。上 两 例 中 ：为 严 格 对 角 占 优B阵 ， 故 Jacobi与 Gauss-Sei

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

27、阵 为383212311221131 224411221 ()(1 )021,1 , ()12 IBBJ a c o b i其特征方程得因而迭代法不收敛。39 310 , 9410100033 , 91500423015(),()22AxbAJacobiGaussSeidelBMBM改 变 方 程 组 中 方 程 的 次 序 ， 即 将 系 数 矩 阵 作 行交 换 ， 会 改 变 迭 代 法 的 收 敛 性 。例 ：与迭 代 的 迭 代 矩 阵 分 别 为谱 半 径 分 别 是。 均 不 收 敛 。40 ,31094 94310AxbAxbAAAAxbJacobiGaussSeidel若交换

28、方程的次序，得的同解方程组为严格对角占优阵，因而对方程组用与迭代求解均收敛。41(1 )()()*()*(1 )( 0 )1*1()*(1 )*( 0 )* ,1, 1 ()1,0 ,) ()() kkkkkkkkxM xgMxxMxxxxMMMIMIMxM xgxxIMgxxMxxMxx定 理 ： 设 有 迭 代 格 式若收 敛 于则 有 误 差 估 计 式证 ： 因故于 是(存 在 ， 方 程 组有 唯 一 解，且(。 从 而 有( 0 )11( 0 )1( 0 )1 ) ) )kkkMxIMgMIMIMxgMIMxx（）(42()*1( 0 )11111111()* ) ) ) ) )1

29、 )1 1kkkkxxMIMxxIMIMIIMIMIMIMIMIMIMIMIMMMxx（）取 范 数(又 因 为(取 范 数(移 项 得(代 入 得(1)( 0 )xxM。43()*(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由 误 差 估 计 式根 据 事 先 给 定 的 精 度， 可 估 计 出 迭 代 的 次 数例 ： 若则 有1)(0 )8.4 12.932,13xk即 需 要 迭 代次 才 能 满 足 精 度 。44(1)()()*()

30、*()(1)()*(1)*(1)11(1)(1)1(1)()()*1(1) ,1, 1() )()kkkkkkkkkkkkkkkxMxgMxxMxxxxMxxM xxM xIMgM IMxMxgM IMxxxxMIMx定理：设有迭代格式若收敛于则有误差估计式证：因 ()()(1)()(1) .11kkkkkxMxxMMxx当不太接近 时，可用作为停机准则。4511112211211222221122 nnnnnnnnnnna x a xa xba x a xa xba x a xa xb阶线性方程组： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩阵表示记

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

32、222;0(2,3,)(3,)jkkiillinllin 这里规定。计算顺序是按列进行，即。4821114 2 ,; 2.()/(1,2, ).()/(,1,1).Tiiiikkiikniikikiik ibbacAAxbaLybyL xyxybl ylinxyl xlin n 当矩阵 完成平方根分解后，求解，即求解两个三角形方程组(1)求（ ），求3 /6, AnGaussAbLAy xbLn由于 的对称性，平方根法的乘除运算量为数量级，约是消去法的一半。上机计算时，所需存储单元也少，只要存储 的下三角部分和右端项 ，计算中 存放在 的存储单元，存储在 的存储单元。但这种方法在求 时需作 次

33、开方运算，这样又增加了计算量.为了避免开方，可使用改进的平方根方法。49123412413412342312552141635158xxxxxxxxxxxxxx例例 用用平方根法平方根法求解方程组求解方程组解解1213112131250522121010141161232535115831211A11210,11 3531221TALLLy ,1, 1, 1, 1 .TTL xy x 解毕故知故知解得解得50121212211211 111 11,0 (),TnnnnnjjjkdldALDLlldllllljk 其中由比较法得5112111111 1,2, ,;()/(1, ). 1,2, ,

34、;()/(1, ).iiiiikkkijijijkk ikikikikkiiiiik ikkijijiik jkikindal dlal d ldjintl dindat llat ldjin 对于上式虽避免了开方运算，但增加了相乘因子，引进变量对于有15211111 ,;(2, )./;/(1,2,1).TTTTiiiikkknnnniiikikk iALDLLLLDLLyb DL xyybybl yinxydxydl xin 对称正定矩阵 按分解和按分解计算量差不多，但分解不需要开方计算。求解计算公式5311112222211111 .iiiiinnnnnnnnnxdbcxdabcxdab

35、cAxdabcxdabxd 在数值计算中，如三次样条插值或用差分方法解常微分方程边值问题，常常会遇到求解以下形式的方程组简记 此系数矩阵的非零元素集中分布在主对角线及其相邻两次对角线上，称为三对角矩阵。方程组称为三对角方程组。54111122231 0 0(2,3,1)01111(1,2,1)iiiiinnnnnibcbaca cinbauclucALUlcluc in 定理：设三对角方程组系数矩阵满足下列条件：则它可分解为其中为已给出的，且分解是唯一的5511111111 , (2,3,) 0(1 2,) /(2,3,)iiiiiiiiiiiiiiiAbualuimbc luuimublau

36、imubc l将上式右端按乘法规则展开 并与 进行比较 得如果，则由上式可得5611( )111111111/(2,3, )kkkkkknnnnnkkkkkGausekucucAabcabcabubcaukn按消去法步骤易得，经次消元后，三对角方程的系数矩阵变为其中。5711112221 2121 2121 21 2121 2121 2122221111(2)2 0., 00(1,2, )iAubbcbacbbbabcc abcbbc abbc abcc aubcubbbuAuinLU由于 满足定理所给条件，显然有又因为于是从而有故且矩阵仍满足定理条件。依此类推可得出。因此由上面公式唯一确定了

37、 和 。5811111111 /(2,3, ) (2,3, )/: ()/(1,2,1) ,iiiiiiikkkknnnkkkkkubALUla uimubc lydLydydl yknxyuUxyxyc xuknnGause分解公式：解得：再解得追赶法的基本思想与消去法及三角分解法相同只是由于系数中出现了,大量的零可使计算公式简化减少了计算量。可证当系数矩阵为严格对角占优时此方法具有良好的数值稳定性。59A事实上，追赶法的求解过程就是将系数矩阵事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两分解两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。个简单方

38、程组的过程。上述定理也表明，追赶法的原理和高斯消去上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。量零元素撇开，从而大大节省计算量。60例例 用追赶法解下面三对角方程组用追赶法解下面三对角方程组12343 1 0 0101 4 1 0110 1 6 1300 0 2 848xxxx61解解：先把系数矩阵分解成如下形式：先把系数矩阵分解成如下形式11223341 3 1 0 0 1 1 1 4 1 0 1 0 1 6 1 1 0 0 2 8 1 1pqpqpqp由递推公式可知由递推公式可知

39、1111113, 3pbqcp2221222113, 113pba qqcp33323336311, 1163pba qqcp62444348263pba q又由递推公式（又由递推公式（4.274.27）可得：）可得：111103ydp2221223()11yda yp33323307()63yda yp44434()5yda yp63再由递推公式（再由递推公式（4.284.28）可得：）可得：445xy33344xyq x22231xyq x11123xyq x故所求的解向量为故所求的解向量为3,1,4,5Tx 6460年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法

40、。实矩阵、非奇异。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。()(1)(1)(1)1(2)1(2)1111111 QRQR (1,2,). , kkkkkkAQ RkAR QAAAAAQ RQARAR QQAQAA基本方法的基本思想是利用矩阵的分解通过迭代格式将化成相似的上三角阵（或分块上三角阵），从而求出矩阵 的全部特征值与特征向量。由即。于是即与相似。同理可()(2,3,)kAAk 得，。故它们有相同的特征值。65可证，在一定条件下，基本可证，在一定条件下，基本QR方法产生的矩阵序列方法产生的矩阵序列A(k) “基本基本”收敛于一个上三角阵（或分块上三角阵）。收敛于一个上三角阵（或分块上三角阵）。即主对