太理水利工程计算及设计线性代数方程组分解学习教案

《太理水利工程计算及设计线性代数方程组分解学习教案》由会员分享，可在线阅读，更多相关《太理水利工程计算及设计线性代数方程组分解学习教案（42页珍藏版）》请在装配图网上搜索。

1、太理水利工程计算及设计线性代数太理水利工程计算及设计线性代数(xin xn di sh)方程组分解方程组分解第一页，共42页。nnnnniiibacbacbacbacbA11122211其系数其系数(xsh)阵是三阵是三对角阵对角阵将将A阵分解阵分解(fnji)为为L阵和阵和U阵阵111112133221nnnLUA三对角三对角(du jio)(du jio)阵的三角分解阵的三角分解第1页/共41页第二页，共42页。11,1 ,/ )(/1 ,11 ,/11111111inxyxyxniyadydyniabnicbiiiinniiiiiiiiiiii解三对角线方程组的追赶法的步骤解三对角线方程

2、组的追赶法的步骤 （1）将）将A阵按式（阵按式（2-89）分解，得到）分解，得到(d do)L、U阵。阵。 （2）向前回代求解）向前回代求解LY=D，得，得（3）向后回代求解）向后回代求解(qi ji)UX=Y，得到，得到（2-89）追追赶赶第2页/共41页第三页，共42页。题题7用追赶用追赶(zhugn)(zhugn)法解三对角方程组法解三对角方程组751451753232121xxxxxxx510151015A解解808. 4192. 015192. 02 . 5/1/2 . 5)2 . 0(152 . 0)5/(1/, 512333222122211111abcabcbaii第3页/共4

3、1页第四页，共42页。71417808. 412 . 515321yyy1192. 012 . 01808. 412 . 515510151015A由由LY=D，得，得760. 0346. 34 . 3321yyy第4页/共41页第五页，共42页。 760. 0346. 34 . 31192. 012 . 01321xxx760. 020. 376. 2321xxx由由UX=Y，得，得第5页/共41页第六页，共42页。BAIXBAAXA111BAX （一）方程组的逆矩阵（一）方程组的逆矩阵(j zhn)解法解法对方程对方程(fngchng) 的两端左乘以逆矩阵的两端左乘以逆矩阵A-1得得解为解

4、为BAX1方程组的逆矩阵解法方程组的逆矩阵解法第6页/共41页第七页，共42页。方程组的逆矩阵方程组的逆矩阵(j zhn)(j zhn)解法解法（二）矩阵（二）矩阵(j zhn)求逆求逆 用计算机求用计算机求nn阶非奇异方阵阶非奇异方阵(fn zhn)A的逆矩阵的逆矩阵A-1。 nnBBBXXXAIAA,2121110000010000121nBBB式中，式中，B1，B2，Bn分别为分别为第7页/共41页第八页，共42页。 求求nn阶非奇异方阵阶非奇异方阵A的逆矩阵的逆矩阵A-1，等价于求解具，等价于求解具有有(jyu)相同系数阵（被求逆的矩阵）且右端项分别为相同系数阵（被求逆的矩阵）且右端项

5、分别为的的n个方程组，即求解个方程组，即求解(qi ji)下述方程组下述方程组121221121100000100001AXXXBAXBAXBAXBBBnnnn最后最后(zuhu)求得的求得的A-1为为（2-94）方程组的逆矩阵解法方程组的逆矩阵解法第8页/共41页第九页，共42页。第二节第二节 线性代数线性代数(xin xn (xin xn di sh)di sh)方程组的方程组的迭代解法迭代解法第9页/共41页第十页，共42页。 迭代法就是用某种极限过程去逐步逼近线性方程组精迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法。迭代法具有需要计算机的存储单元较小，程确解的方法。迭代法具

6、有需要计算机的存储单元较小，程序设计简单，原始系数矩阵在计算过程中始终不变等优点，序设计简单，原始系数矩阵在计算过程中始终不变等优点，但存在收敛性和收敛速度问题。迭代法在解决问题（特别但存在收敛性和收敛速度问题。迭代法在解决问题（特别是大型是大型(dxng)稀疏系数阵问题）时，是一种有效的方法。稀疏系数阵问题）时，是一种有效的方法。第10页/共41页第十一页，共42页。雅可比迭代法雅可比迭代法高斯高斯(o s)赛德尔迭代法赛德尔迭代法逐次超松弛法逐次超松弛法迭代迭代(di di)解解法法第11页/共41页第十二页，共42页。（一）迭代（一）迭代(di di)算法算法nnnnnnnnnnbxax

7、axabxaxaxabxaxaxa2211222221211121211111,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax设有设有n阶方程组阶方程组可改写可改写(gixi)为为即即AX=B雅可比迭代法雅可比迭代法第12页/共41页第十三页，共42页。任一方程任一方程(fngchng)可可写为写为111), 2 , 1()(1ijnijjijjijiiiinixaxabax进而写成如下进而写成如下(rxi)的迭代格式的迭代格式（2-97）式（式（2-97）就是）就是(jish)雅可比迭代算法。雅可比迭

8、代算法。), 2 , 1 , 0;, 2 , 1()(1111)()()1(mnixaxabaxijnijmjijmjijiiimi雅可比迭代法雅可比迭代法第13页/共41页第十四页，共42页。)(11,)(22)(11)1()(2)(323)(121222)1(2)(1)(313)(212111)1(1111mnnnmnmnnnnmnmnnmmmmnnmmmxaxaxabaxxaxaxabaxxaxaxabax雅可比迭代法雅可比迭代法式（式（2-97）展开）展开(zhn ki)为为第14页/共41页第十五页，共42页。0002121nnaaaL0002112nnaaaUBDXULDXBXUL

9、DXBXULDBAX11)()()( 方程组方程组AX = B中的系数中的系数(xsh)矩阵可表示为三个矩阵的代数和矩阵可表示为三个矩阵的代数和矩阵，即矩阵，即A = D L-U其中其中 nnaaaD2211雅可比迭代法雅可比迭代法第15页/共41页第十六页，共42页。BDXULDXBXULDXBXULDBAX11)()()(故式（故式（2-97）即为）即为BDGULDKGKXBDXULDXmmm11)(1)(1)1(),()(（2-99）式（式（2-99）就是雅可比迭代的矩阵）就是雅可比迭代的矩阵(j zhn)形式。形式。其中其中(qzhng)雅可比迭代法雅可比迭代法第16页/共41页第十七

10、页，共42页。题题8用雅可比迭代法求解用雅可比迭代法求解(qi ji)下列方程组下列方程组2 . 453 . 82102 . 7210321321321xxxxxxxxx0)0(3)0(2)0(1xxx取初值解解 按式（按式（2-97）形式）形式(xngsh)的雅可比算法，有的雅可比算法，有84. 02 . 02 . 083. 03 . 01 . 072. 02 . 01 . 0)(2)(1)1()()()1()()()1(3312321mmmmmmmmmxxxxxxxxx第17页/共41页第十八页，共42页。计算结果见下表：计算结果见下表： k01234567 X100.720.9711.0

11、571.08531.09511.0983 X200.831.0701.15711.18531.19511.1983 X300.841.1501.24821.28281.29411.2980原线性代数原线性代数(xin xn di sh)方程组的精确解为方程组的精确解为3 . 1 , 2 . 1 , 1 . 1,321xxx第18页/共41页第十九页，共42页。 高斯高斯(o s)赛德尔迭代是对雅可比迭代的一个简单改进，赛德尔迭代是对雅可比迭代的一个简单改进，从而提高了迭代收敛的速度从而提高了迭代收敛的速度（一）迭代（一）迭代(di di)算法算法11,221123231212222131321

12、21111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabaxN阶方程组可改写为如下形式阶方程组可改写为如下形式高斯高斯赛德尔迭代法赛德尔迭代法第19页/共41页第二十页，共42页。), 2 , 1 , 0;, 2 , 1()(1111)()1()1(mnixaxabaxijnijmjijmjijiiimi（2-100）)1(11,)1(22)1(11)1()(2)(323)1(121222)1(2)(1)(313)(212111)1(1111mnnnmnmnnnnmnmnnmmmmnnmmmxaxaxabaxxaxaxabaxxaxaxabax可写成如下可写

13、成如下(rxi)的迭代形式的迭代形式可简写可简写(jinxi)成成式（式（2-100）就是）就是(jish)高斯高斯赛德尔迭代算法赛德尔迭代算法高斯高斯赛德尔迭代法赛德尔迭代法第20页/共41页第二十一页，共42页。 ， （二）迭代的矩阵（二）迭代的矩阵(j zhn)形式形式BLDGULDK11)(,)(其中其中(qzhng)式（式（2-101）是高斯）是高斯赛德尔迭代的矩阵赛德尔迭代的矩阵(j zhn)形式。形式。GKXXBLDUXLDXBUXXLDBXULDBAXmmmmmm)()1(1)(1)1()()1()()()()(（2-101）高斯高斯赛德尔迭代法赛德尔迭代法第21页/共41页第

14、二十二页，共42页。 ， （二）迭代的矩阵（二）迭代的矩阵(j zhn)形式（书上）形式（书上）BLDGULDKGKXXBUXXLDUXLXBDXULDAmmmmmmm11)()1()()1()()1(1)1()(,)()()(式（式（2-100）可写成）可写成亦即亦即故故其中其中(qzhng)（2-101）式（式（2-101）是高斯）是高斯赛德尔迭代的矩阵赛德尔迭代的矩阵(j zhn)形式。形式。高斯高斯赛德尔迭代法赛德尔迭代法第22页/共41页第二十三页，共42页。题题9用高斯用高斯(o s)-赛德尔迭代法求解下列方程组赛德尔迭代法求解下列方程组2 . 453 . 82102 . 7210

15、321321321xxxxxxxxx0)0(3)0(2)0(1xxx取初值解解 按式（按式（2-100）得到）得到(d do)的高斯的高斯赛德尔迭代算法，有赛德尔迭代算法，有84. 02 . 02 . 083. 02 . 01 . 072. 02 . 01 . 0)1(2)1(1)1()()1()1()()()1(3312321mmmmmmmmmxxxxxxxxx第23页/共41页第二十四页，共42页。计算结果见下表：计算结果见下表： k01234567 X100.721.043081.093131.099131.099891.099991.1 X200.9021.167191.195721.

16、199471.199931.199991.2 X300.16441.282051.297771.299721.299961.31.3第24页/共41页第二十五页，共42页。（一）迭代（一）迭代(di di)算法算法imiijnijmjijmjijiiimiijnijmiiimjijmjijiiiijnijmjijmjijiiimixxxaxabaxxaxaxabaxaxabax)(11)()1()(11)()()1(111)()1()1()(1)(1)(1逐次超松弛法又是对高斯逐次超松弛法又是对高斯(o s)赛德尔法的一个改赛德尔法的一个改进。进。高斯高斯赛德尔迭代算法赛德尔迭代算法逐次超松弛

17、法逐次超松弛法第25页/共41页第二十六页，共42页。 这里这里r是用来加速收敛的权因子是用来加速收敛的权因子(ynz)，称为松弛因子，称为松弛因子(ynz)，r=1时，即为赛德尔迭代公式。式（时，即为赛德尔迭代公式。式（2-102）在）在r1时为超松弛迭代（简称时为超松弛迭代（简称SOR），在），在r1时为松弛迭代。通常时为松弛迭代。通常取取1r2。 修改修改(xigi)为为（2-102）imimixrxx)()1(逐次逐次(zh c)(zh c)超松弛法超松弛法第26页/共41页第二十七页，共42页。), 2 , 1 , 0;, 2 , 1()()1 ()1 ()(111)()1()()1

18、()()()1()()1(mnixaxabarxrrxxrxxrxxijnijmjijmjijiiimimimimimimimi式（式（2-102）还可等价）还可等价(dngji)地表示为地表示为（2-103） 式（式（2102）和（）和（2-103）就是逐次超松弛）就是逐次超松弛(sn ch)迭代算法迭代算法（r1）。）。逐次逐次(zh c)(zh c)超松弛法超松弛法第27页/共41页第二十八页，共42页。 ， （二）迭代（二）迭代(di di)的矩阵形式的矩阵形式BrLDrGrUDrrLDKGKXXrBXrUIrDXrLDmmmm11)()1()()1()()1()()1 ()()()1

19、 ()()1()()1(mmmmUXLXBrXrDDX（2-104）式（式（2-104）是逐次超松弛法的矩阵）是逐次超松弛法的矩阵(j zhn)形式。形式。直接直接(zhji)根据式（根据式（2-103）写）写整理得整理得逐次超松弛法逐次超松弛法111)()1()()1()()1 (ijnijmjijmjijiiimimixaxabarxrx（2-103）第28页/共41页第二十九页，共42页。 超松弛因子通常在超松弛因子通常在1.4到到1.9 之间。松驰因子的选取之间。松驰因子的选取对迭代格式的收敛速度影响极大。实际计算时，可以根对迭代格式的收敛速度影响极大。实际计算时，可以根据据(gnj)

20、系数矩阵的性质，结合经验通过反复计算来确系数矩阵的性质，结合经验通过反复计算来确定松驰因子。定松驰因子。使收敛最快的松弛因子使收敛最快的松弛因子(ynz)称为最佳松弛因子称为最佳松弛因子(ynz)（ ）。）。optr逐次逐次(zh c)(zh c)超松弛法超松弛法第29页/共41页第三十页，共42页。举例举例(j l)用用SOR方法方法(fngf)解线性方程解线性方程组组111141111411114111144321xxxx方程方程(fngchng)精确解为精确解为X=（-1，-1，-1，-1）T 解解 : 取取x(0) =(0,0,0,0)T , 取不同的松弛因子，得到取不同的松弛因子，得

21、到的满足误差的满足误差10-5的迭代次数如下表所示。的迭代次数如下表所示。逐次超松弛法逐次超松弛法第30页/共41页第三十一页，共42页。松弛因子松弛因子迭代次数迭代次数松弛因子松弛因子迭代次数迭代次数1.01.11.21.31.422171211141.51.61.71.81.917233353109 本例说明本例说明(shumng)，松弛因子选择的好，会使，松弛因子选择的好，会使SOR迭代法的收敛大大加速。本例中迭代法的收敛大大加速。本例中1.3 是最佳松弛因子。是最佳松弛因子。逐次逐次(zh c)(zh c)超松弛法超松弛法第31页/共41页第三十二页，共42页。，有对任何的向量三角不等

22、式。有对任何实数齐次性。时当非负性YXYXYXXCCXXOXO,) 3(,C)2(0, 0) 1 (四、四、 向量和矩阵向量和矩阵(j zhn)的范数的概念的范数的概念向量向量X X的范数的范数 是满足下列是满足下列(xili)(xili)条件的实数。条件的实数。X迭代法的收敛迭代法的收敛(shulin)条件与条件与收敛收敛(shulin)准则准则第32页/共41页第三十三页，共42页。nxxxX211222212nTxxxXXX),max(max211ninixxxxX三个常用三个常用(chn yn)的向量范数：的向量范数：设设X = (x1, x2, xn)T，则有，则有列范数列范数谱范数

23、谱范数行范数行范数迭代法的收敛条件迭代法的收敛条件(tiojin)与收与收敛准则敛准则第33页/共41页第三十四页，共42页。)00(01AAA非负性）（为实数齐次性）（cAccA,2BABA三角不等式）（3 4BAAB 相容性）（ 矩阵的范数矩阵的范数 是定义在是定义在Rnn上的非负的实值函数，它上的非负的实值函数，它满足满足(mnz)下列条件的实数。下列条件的实数。A迭代法的收敛迭代法的收敛(shulin)条件与收敛条件与收敛(shulin)准则准则第34页/共41页第三十五页，共42页。njijniaAA11max:的行范数矩阵niijnjaAA111max:的列范数矩阵)(:max2A

24、AAAT的谱范数矩阵的最大特征值表示其中AAAATT)(max三个常用三个常用(chn yn)的矩阵范数：的矩阵范数：迭代法的收敛迭代法的收敛(shulin)条件与收条件与收敛敛(shulin)准则准则矩阵矩阵(j zhn)每一列元素绝对值之和取最大值每一列元素绝对值之和取最大值矩阵每一行元素绝对值之和取最大值矩阵每一行元素绝对值之和取最大值第35页/共41页第三十六页，共42页。（一）一般（一）一般(ybn)迭代法的收敛准则与收敛条件迭代法的收敛准则与收敛条件 对方程组对方程组AX=B，一般（线性）迭代法是按公式，一般（线性）迭代法是按公式以任意初始向量以任意初始向量X（0）开始，反复进行）

25、开始，反复进行(jnxng)计算。当计算。当m时，迭代向量序列时，迭代向量序列 有时收敛于方程组的精确解，有时收敛于方程组的精确解，有时则不然。如向量序列有时则不然。如向量序列 收敛于方程组的精确解，就收敛于方程组的精确解，就称该迭代法收敛；反之，则谓不收敛或发散。称该迭代法收敛；反之，则谓不收敛或发散。GKXXmm)()1()(mX)(mX（2-112）定义定义(dngy)迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第36页/共41页第三十七页，共42页。收敛收敛(shulin)准准则则 收敛准则是指使迭代终止收敛准则是指使迭代终止(zhngzh)的条件。通常使用的收的条件。通常使用

26、的收敛准则有绝对准则和相对准则两种。敛准则有绝对准则和相对准则两种。BRXXXRXXmmmmmmm/)()1()()1()()()1(绝对绝对(judu)准则准则相对准则相对准则或或或或)()(mmAXBR这里这里 是方程的余差向量，是方程的余差向量，是给定的控制是给定的控制误差。误差。迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第37页/共41页第三十八页，共42页。 定理定理2 迭代迭代(di di)格式（格式（2-112）收敛的充分必要条件）收敛的充分必要条件是迭代是迭代(di di)矩阵矩阵K的谱半径的谱半径(K) 1。 定理1 若迭代格式（2-112）的迭代矩阵(j zhn)

27、K的范数小于1（即 ），则该格式求出的向量序列 将收敛于方程组的唯一解a，且有误差估计式1K迭代法收敛迭代法收敛(shulin)定理定理)(mXaXKaXmm)0()( 以上两定理有较大的理论意义，但实际用起来不甚方便，以上两定理有较大的理论意义，但实际用起来不甚方便，为为此后面引入更为实用的判别迭代格式收敛的充分条件。此后面引入更为实用的判别迭代格式收敛的充分条件。的特征值。是的谱半径，为KKmax)(i1niiK迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第38页/共41页第三十九页，共42页。 定理定理1 若线性代数方程组若线性代数方程组AX=B的系数阵的系数阵A按行（或列）严按

28、行（或列）严格对角占优，即格对角占优，即则雅可比迭代和赛德尔迭代收敛则雅可比迭代和赛德尔迭代收敛(shulin)。 定理定理2 若线性代数方程组若线性代数方程组AX=B的系数阵的系数阵A是实对称正定是实对称正定阵，则赛德尔迭代收敛阵，则赛德尔迭代收敛(shulin)。 定理定理3 对任何系数阵对任何系数阵A，要使逐次超松弛法收敛，要使逐次超松弛法收敛(shulin)，必须选取松弛因子必须选取松弛因子r为（为（0，2）内的正数，则）内的正数，则SOR法收敛法收敛(shulin)的必要条件是的必要条件是 (2-117)当当A是对称正定阵时，满足（是对称正定阵时，满足（2-117）的）的r必使必使SOR法收敛法收敛(shulin)。), 2 , 1(111niaaaiinijijijij20 r迭代法的收敛条件迭代法的收敛条件(tiojin)与收敛准与收敛准则则第39页/共41页第四十页，共42页。第40页/共41页第四十一页，共42页。感谢您的观看感谢您的观看(gunkn)。第41页/共41页第四十二页，共42页。