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

1、太理水利工程计算及设计线性代数方程太理水利工程计算及设计线性代数方程组分解组分解nnnnniiibacbacbacbacbA11122211其系数阵是三对角其系数阵是三对角阵阵将将A阵分解为阵分解为L阵和阵和U阵阵111112133221nnnLUA三对角阵的三角分解三对角阵的三角分解第1页/共41页11,1 ,/ )(/1 ,11 ,/11111111inxyxyxniyadydyniabnicbiiiinniiiiiiiiiiii解三对角线方程组的追赶法的步骤解三对角线方程组的追赶法的步骤 （1）将）将A阵按式（阵按式（2-89）分解，得到）分解，得到L、U阵。阵。 （2）向前回代求解）向

2、前回代求解LY=D，得，得（3）向后回代求解）向后回代求解UX=Y，得到，得到（2-89）追追赶赶第2页/共41页题题7用追赶法解三对角方程组用追赶法解三对角方程组751451753232121xxxxxxx510151015A解解808. 4192. 015192. 02 . 5/1/2 . 5)2 . 0(152 . 0)5/(1/, 512333222122211111abcabcbaii第3页/共41页71417808. 412 . 515321yyy1192. 012 . 01808. 412 . 515510151015A由由LY=D，得，得760. 0346. 34 . 3321

3、yyy第4页/共41页 760. 0346. 34 . 31192. 012 . 01321xxx760. 020. 376. 2321xxx由由UX=Y，得，得第5页/共41页BAIXBAAXA111BAX （一）方程组的逆矩阵解法（一）方程组的逆矩阵解法对方程对方程 的两端左乘以逆矩阵的两端左乘以逆矩阵A-1得得解为解为BAX1方程组的逆矩阵解法方程组的逆矩阵解法第6页/共41页方程组的逆矩阵解法方程组的逆矩阵解法（二）矩阵求逆（二）矩阵求逆 用计算机求用计算机求nn阶非奇异方阵阶非奇异方阵A的逆矩阵的逆矩阵A-1。 nnBBBXXXAIAA,2121110000010000121nBBB

4、式中，式中，B1，B2，Bn分别为分别为第7页/共41页 求求nn阶非奇异方阵阶非奇异方阵A的逆矩阵的逆矩阵A-1，等价于求解具有，等价于求解具有相同系数阵（被求逆的矩阵）且右端项分别为相同系数阵（被求逆的矩阵）且右端项分别为的的n个方程组，即求解下述方程组个方程组，即求解下述方程组121221121100000100001AXXXBAXBAXBAXBBBnnnn最后求得的最后求得的A-1为为（2-94）方程组的逆矩阵解法方程组的逆矩阵解法第8页/共41页第二节第二节 线性代数方程组的线性代数方程组的迭代解法迭代解法第9页/共41页 迭代法迭代法就是用某种极限过程去逐步逼近线性方程组就是用某种

5、极限过程去逐步逼近线性方程组精确解的方法。精确解的方法。迭代法具有需要计算机的存储单元较小，迭代法具有需要计算机的存储单元较小，程序设计简单，原始系数矩阵在计算过程中始终不变等程序设计简单，原始系数矩阵在计算过程中始终不变等优点，但存在收敛性和收敛速度问题。迭代法在解决问优点，但存在收敛性和收敛速度问题。迭代法在解决问题（特别是大型稀疏系数阵问题）时，是一种有效的方题（特别是大型稀疏系数阵问题）时，是一种有效的方法。法。第10页/共41页雅可比迭代法雅可比迭代法高斯高斯赛德尔迭代法赛德尔迭代法逐次超松弛法逐次超松弛法迭代解法迭代解法第11页/共41页（一）迭代算（一）迭代算法法nnnnnnnn

6、nnbxaxaxabxaxaxabxaxaxa2211222221211121211111,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax设有设有n阶方程组阶方程组可改写为可改写为即即AX=B雅可比迭代法雅可比迭代法第12页/共41页任一方程可写为任一方程可写为111), 2 , 1()(1ijnijjijjijiiiinixaxabax进而写成如下的迭代格式进而写成如下的迭代格式（2-97）式（式（2-97）就是雅可比迭代算法。）就是雅可比迭代算法。), 2 , 1 , 0;, 2 , 1()(111

7、1)()()1(mnixaxabaxijnijmjijmjijiiimi雅可比迭代法雅可比迭代法第13页/共41页)(11,)(22)(11)1()(2)(323)(121222)1(2)(1)(313)(212111)1(1111mnnnmnmnnnnmnmnnmmmmnnmmmxaxaxabaxxaxaxabaxxaxaxabax雅可比迭代法雅可比迭代法式（式（2-97）展开为）展开为第14页/共41页0002121nnaaaL0002112nnaaaUBDXULDXBXULDXBXULDBAX11)()()( 方程组方程组AX = B中的系数矩阵可表示为三个矩阵的代数和中的系数矩阵可表示

8、为三个矩阵的代数和矩阵，即矩阵，即A = D L-U其中其中 nnaaaD2211雅可比迭代法雅可比迭代法第15页/共41页BDXULDXBXULDXBXULDBAX11)()()(故式（故式（2-97）即为）即为BDGULDKGKXBDXULDXmmm11)(1)(1)1(),()(（2-99）式（式（2-99）就是雅可比迭代的矩阵形式。）就是雅可比迭代的矩阵形式。其中其中雅可比迭代法雅可比迭代法第16页/共41页题题8用雅可比迭代法求解下列方程组用雅可比迭代法求解下列方程组2 . 453 . 82102 . 7210321321321xxxxxxxxx0)0(3)0(2)0(1xxx取初值

9、解解 按式（按式（2-97）形式的雅可比算法，有）形式的雅可比算法，有84. 02 . 02 . 083. 03 . 01 . 072. 02 . 01 . 0)(2)(1)1()()()1()()()1(3312321mmmmmmmmmxxxxxxxxx第17页/共41页计算结果见下表：计算结果见下表： k01234567 X100.720.9711.0571.08531.09511.0983 X200.831.0701.15711.18531.19511.1983 X300.841.1501.24821.28281.29411.2980原线性代数方程组的精确解为原线性代数方程组的精确解为3

10、 . 1 , 2 . 1 , 1 . 1,321xxx第18页/共41页 高斯高斯赛德尔迭代是对雅可比迭代的赛德尔迭代是对雅可比迭代的一个简单改进一个简单改进，从而提高了迭代收敛的速度从而提高了迭代收敛的速度（一）迭代算法（一）迭代算法11,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabaxN阶方程组可改写为如下形式阶方程组可改写为如下形式高斯高斯赛德尔迭代法赛德尔迭代法第19页/共41页), 2 , 1 , 0;, 2 , 1()(1111)()1()1(mnixaxabaxijnijmjijmjijii

11、imi（2-100）)1(11,)1(22)1(11)1()(2)(323)1(121222)1(2)(1)(313)(212111)1(1111mnnnmnmnnnnmnmnnmmmmnnmmmxaxaxabaxxaxaxabaxxaxaxabax可写成如下的迭代形式可写成如下的迭代形式可简写成可简写成式（式（2-100）就是高斯）就是高斯赛德尔迭代算法赛德尔迭代算法高斯高斯赛德尔迭代法赛德尔迭代法第20页/共41页 ， （二）迭代的矩阵形式（二）迭代的矩阵形式BLDGULDK11)(,)(其中其中式（式（2-101）是高斯）是高斯赛德尔迭代的矩阵形式。赛德尔迭代的矩阵形式。GKXXBLDU

12、XLDXBUXXLDBXULDBAXmmmmmm)()1(1)(1)1()()1()()()()(（2-101）高斯高斯赛德尔迭代法赛德尔迭代法第21页/共41页 ， （二）迭代的矩阵形式（书上）（二）迭代的矩阵形式（书上）BLDGULDKGKXXBUXXLDUXLXBDXULDAmmmmmmm11)()1()()1()()1(1)1()(,)()()(式（式（2-100）可写成）可写成亦即亦即故故其中其中（2-101）式（式（2-101）是高斯）是高斯赛德尔迭代的矩阵形式。赛德尔迭代的矩阵形式。高斯高斯赛德尔迭代法赛德尔迭代法第22页/共41页题题9用高斯用高斯-赛德尔迭代法求解下列方程组赛

13、德尔迭代法求解下列方程组2 . 453 . 82102 . 7210321321321xxxxxxxxx0)0(3)0(2)0(1xxx取初值解解 按式（按式（2-100）得到的高斯）得到的高斯赛德尔迭代算法，有赛德尔迭代算法，有84. 02 . 02 . 083. 02 . 01 . 072. 02 . 01 . 0)1(2)1(1)1()()1()1()()()1(3312321mmmmmmmmmxxxxxxxxx第23页/共41页计算结果见下表：计算结果见下表： k01234567 X100.721.043081.093131.099131.099891.099991.1 X200.90

14、21.167191.195721.199471.199931.199991.2 X300.16441.282051.297771.299721.299961.31.3第24页/共41页（一）迭代算法（一）迭代算法imiijnijmjijmjijiiimiijnijmiiimjijmjijiiiijnijmjijmjijiiimixxxaxabaxxaxaxabaxaxabax)(11)()1()(11)()()1(111)()1()1()(1)(1)(1逐次超松弛法又是对高斯逐次超松弛法又是对高斯赛德尔法的赛德尔法的一个改进一个改进。高斯高斯赛德尔迭代算法赛德尔迭代算法逐次超松弛法逐次超松弛法

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

16、mimimimi式（式（2-102）还可等价地表示为）还可等价地表示为（2-103） 式（式（2102）和（）和（2-103）就是逐次超松弛迭代算法）就是逐次超松弛迭代算法（r1）。）。逐次超松弛法逐次超松弛法第27页/共41页 ， （二）迭代的矩阵形式（二）迭代的矩阵形式BrLDrGrUDrrLDKGKXXrBXrUIrDXrLDmmmm11)()1()()1()()1()()1 ()()()1 ()()1()()1(mmmmUXLXBrXrDDX（2-104）式（式（2-104）是逐次超松弛法的矩阵形式。）是逐次超松弛法的矩阵形式。直接根据式（直接根据式（2-103）写）写整理得整理得逐次

17、超松弛法逐次超松弛法111)()1()()1()()1 (ijnijmjijmjijiiimimixaxabarxrx（2-103）第28页/共41页 超松弛因子通常在超松弛因子通常在1.4到到1.9 之间。松驰因子的选之间。松驰因子的选取对迭代格式的收敛速度影响极大。实际计算时，可取对迭代格式的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。定松驰因子。使收敛最快的松弛因子称为最佳松弛因子（使收敛最快的松弛因子称为最佳松弛因子（ ）。）。optr逐次超松弛法逐次超松弛法第29页/共41页举例举例用用SOR

18、方法解线性方程组方法解线性方程组111141111411114111144321xxxx方程精确解为方程精确解为X=（-1，-1，-1，-1）T 解解 : 取取x(0) =(0,0,0,0)T , 取不同的松弛因子，得取不同的松弛因子，得到的满足误差到的满足误差10-5的迭代次数如下表所示。的迭代次数如下表所示。逐次超松弛法逐次超松弛法第30页/共41页松弛因子松弛因子迭代次数迭代次数松弛因子松弛因子迭代次数迭代次数1.01.11.21.31.422171211141.51.61.71.81.917233353109 本例说明，松弛因子选择的好，会使本例说明，松弛因子选择的好，会使SOR迭代法

19、的迭代法的收敛大大加速。本例中收敛大大加速。本例中1.3 是最佳松弛因子。是最佳松弛因子。逐次超松弛法逐次超松弛法第31页/共41页。，有对任何的向量三角不等式。有对任何实数齐次性。时当非负性YXYXYXXCCXXOXO,)3(,C)2(0, 0) 1 (四、四、 向量和矩阵的范数的概念向量和矩阵的范数的概念向量向量X的范数的范数 是满足下列条件的是满足下列条件的实数实数。X迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第32页/共41页nxxxX211222212nTxxxXXX),max(max211ninixxxxX三个常用的向量范数：三个常用的向量范数：设设X = (x1, x2

20、, xn)T，则有，则有列范数列范数谱范数谱范数行范数行范数迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第33页/共41页)00(01AAA非负性）（为实数齐次性）（cAccA,2BABA三角不等式）（3 4BAAB 相容性）（ 矩阵的范数矩阵的范数 是定义在是定义在Rnn上的上的非负的实值函数非负的实值函数，它它满足下列条件的实数。满足下列条件的实数。A迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第34页/共41页njijniaAA11max:的行范数矩阵niijnjaAA111max:的列范数矩阵)(:max2AAAAT的谱范数矩阵的最大特征值表示其中AAAATT)(max

21、三个常用的矩阵范数：三个常用的矩阵范数：迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则矩阵每一列元素绝对值之和取最大值矩阵每一列元素绝对值之和取最大值矩阵每一行元素绝对值之和取最大值矩阵每一行元素绝对值之和取最大值第35页/共41页（一）一般迭代法的收敛准则与收敛条件（一）一般迭代法的收敛准则与收敛条件 对方程组对方程组AX=B，一般（线性）迭代法是按公式，一般（线性）迭代法是按公式以任意初始向量以任意初始向量X（0）开始，反复进行计算。当开始，反复进行计算。当m时，时，迭代向量序列迭代向量序列 有时收敛于方程组的精确解，有时则有时收敛于方程组的精确解，有时则不然。如向量序列不然。如向量

22、序列 收敛于方程组的精确解，就称该收敛于方程组的精确解，就称该迭代法收敛迭代法收敛；反之，则谓；反之，则谓不收敛或发散不收敛或发散。GKXXmm)()1()(mX)(mX（2-112）定义定义迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第36页/共41页收敛准则收敛准则 收敛准则是指使迭代终止的条件。收敛准则是指使迭代终止的条件。通常使用的收敛准通常使用的收敛准则有绝对准则和相对准则两种。则有绝对准则和相对准则两种。BRXXXRXXmmmmmmm/)()1()()1()()()1(绝对准则绝对准则相对准则相对准则或或或或)()(mmAXBR这里这里 是方程的余差向量，是方程的余差向量，是给定的控制是给定的控制误差。误差。迭代法的收敛条件与收敛准则迭代法的收敛条件与收敛准则第37页/共41页 定理定理2 迭代格式（迭代格式（2-112）收敛的充分必要条件是迭代）收敛的充分必要条件是迭代矩阵矩阵K的谱半径的谱