太理水利工程計(jì)算及設(shè)計(jì)線性代數(shù)方程組分解PPT教案

1、太理水利工程計(jì)算及設(shè)計(jì)線性代數(shù)方程太理水利工程計(jì)算及設(shè)計(jì)線性代數(shù)方程組分解組分解nnnnniiibacbacbacbacbA11122211其系數(shù)陣是三對(duì)角其系數(shù)陣是三對(duì)角陣陣將將A陣分解為陣分解為L(zhǎng)陣和陣和U陣陣111112133221nnnLUA三對(duì)角陣的三角分解三對(duì)角陣的三角分解第1頁(yè)/共41頁(yè)11,1 ,/ )(/1 ,11 ,/11111111inxyxyxniyadydyniabnicbiiiinniiiiiiiiiiii解三對(duì)角線方程組的追趕法的步驟解三對(duì)角線方程組的追趕法的步驟 （1）將）將A陣按式（陣按式（2-89）分解，得到）分解，得到L、U陣。陣。 （2）向前回代求解）向

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

3、yyy第4頁(yè)/共41頁(yè) 760. 0346. 34 . 31192. 012 . 01321xxx760. 020. 376. 2321xxx由由UX=Y，得，得第5頁(yè)/共41頁(yè)BAIXBAAXA111BAX （一）方程組的逆矩陣解法（一）方程組的逆矩陣解法對(duì)方程對(duì)方程 的兩端左乘以逆矩陣的兩端左乘以逆矩陣A-1得得解為解為BAX1方程組的逆矩陣解法方程組的逆矩陣解法第6頁(yè)/共41頁(yè)方程組的逆矩陣解法方程組的逆矩陣解法（二）矩陣求逆（二）矩陣求逆 用計(jì)算機(jī)求用計(jì)算機(jī)求nn階非奇異方陣階非奇異方陣A的逆矩陣的逆矩陣A-1。 nnBBBXXXAIAA,2121110000010000121nBBB

4、式中，式中，B1，B2，Bn分別為分別為第7頁(yè)/共41頁(yè) 求求nn階非奇異方陣階非奇異方陣A的逆矩陣的逆矩陣A-1，等價(jià)于求解具有，等價(jià)于求解具有相同系數(shù)陣（被求逆的矩陣）且右端項(xiàng)分別為相同系數(shù)陣（被求逆的矩陣）且右端項(xiàng)分別為的的n個(gè)方程組，即求解下述方程組個(gè)方程組，即求解下述方程組121221121100000100001AXXXBAXBAXBAXBBBnnnn最后求得的最后求得的A-1為為（2-94）方程組的逆矩陣解法方程組的逆矩陣解法第8頁(yè)/共41頁(yè)第二節(jié)第二節(jié) 線性代數(shù)方程組的線性代數(shù)方程組的迭代解法迭代解法第9頁(yè)/共41頁(yè) 迭代法迭代法就是用某種極限過(guò)程去逐步逼近線性方程組就是用某種

5、極限過(guò)程去逐步逼近線性方程組精確解的方法。精確解的方法。迭代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較小，迭代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較小，程序設(shè)計(jì)簡(jiǎn)單，原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等程序設(shè)計(jì)簡(jiǎn)單，原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等優(yōu)點(diǎn)，但存在收斂性和收斂速度問(wèn)題。迭代法在解決問(wèn)優(yōu)點(diǎn)，但存在收斂性和收斂速度問(wèn)題。迭代法在解決問(wèn)題（特別是大型稀疏系數(shù)陣問(wèn)題）時(shí)，是一種有效的方題（特別是大型稀疏系數(shù)陣問(wèn)題）時(shí)，是一種有效的方法。法。第10頁(yè)/共41頁(yè)雅可比迭代法雅可比迭代法高斯高斯賽德?tīng)柕ㄙ惖聽(tīng)柕ㄖ鸫纬沙诜ㄖ鸫纬沙诜ǖ夥ǖ夥ǖ?1頁(yè)/共41頁(yè)（一）迭代算（一）迭代算法法nnnnnnnn

6、nnbxaxaxabxaxaxabxaxaxa2211222221211121211111,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax設(shè)有設(shè)有n階方程組階方程組可改寫(xiě)為可改寫(xiě)為即即AX=B雅可比迭代法雅可比迭代法第12頁(yè)/共41頁(yè)任一方程可寫(xiě)為任一方程可寫(xiě)為111), 2 , 1()(1ijnijjijjijiiiinixaxabax進(jìn)而寫(xiě)成如下的迭代格式進(jìn)而寫(xiě)成如下的迭代格式（2-97）式（式（2-97）就是雅可比迭代算法。）就是雅可比迭代算法。), 2 , 1 , 0;, 2 , 1()(111

7、1)()()1(mnixaxabaxijnijmjijmjijiiimi雅可比迭代法雅可比迭代法第13頁(yè)/共41頁(yè))(11,)(22)(11)1()(2)(323)(121222)1(2)(1)(313)(212111)1(1111mnnnmnmnnnnmnmnnmmmmnnmmmxaxaxabaxxaxaxabaxxaxaxabax雅可比迭代法雅可比迭代法式（式（2-97）展開(kāi)為）展開(kāi)為第14頁(yè)/共41頁(yè)0002121nnaaaL0002112nnaaaUBDXULDXBXULDXBXULDBAX11)()()( 方程組方程組AX = B中的系數(shù)矩陣可表示為三個(gè)矩陣的代數(shù)和中的系數(shù)矩陣可表示

8、為三個(gè)矩陣的代數(shù)和矩陣，即矩陣，即A = D L-U其中其中 nnaaaD2211雅可比迭代法雅可比迭代法第15頁(yè)/共41頁(yè)BDXULDXBXULDXBXULDBAX11)()()(故式（故式（2-97）即為）即為BDGULDKGKXBDXULDXmmm11)(1)(1)1(),()(（2-99）式（式（2-99）就是雅可比迭代的矩陣形式。）就是雅可比迭代的矩陣形式。其中其中雅可比迭代法雅可比迭代法第16頁(yè)/共41頁(yè)題題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頁(yè)/共41頁(yè)計(jì)算結(jié)果見(jiàn)下表：計(jì)算結(jié)果見(jiàn)下表： k01234567 X100.720.9711.0571.08531.09511.0983 X200.831.0701.15711.18531.19511.1983 X300.841.1501.24821.28281.29411.2980原線性代數(shù)方程組的精確解為原線性代數(shù)方程組的精確解為3

10、 . 1 , 2 . 1 , 1 . 1,321xxx第18頁(yè)/共41頁(yè) 高斯高斯賽德?tīng)柕菍?duì)雅可比迭代的賽德?tīng)柕菍?duì)雅可比迭代的一個(gè)簡(jiǎn)單改進(jìn)一個(gè)簡(jiǎn)單改進(jìn)，從而提高了迭代收斂的速度從而提高了迭代收斂的速度（一）迭代算法（一）迭代算法11,22112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabaxN階方程組可改寫(xiě)為如下形式階方程組可改寫(xiě)為如下形式高斯高斯賽德?tīng)柕ㄙ惖聽(tīng)柕ǖ?9頁(yè)/共41頁(yè)), 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可寫(xiě)成如下的迭代形式可寫(xiě)成如下的迭代形式可簡(jiǎn)寫(xiě)成可簡(jiǎn)寫(xiě)成式（式（2-100）就是高斯）就是高斯賽德?tīng)柕惴ㄙ惖聽(tīng)柕惴ǜ咚垢咚官惖聽(tīng)柕ㄙ惖聽(tīng)柕ǖ?0頁(yè)/共41頁(yè) ， （二）迭代的矩陣形式（二）迭代的矩陣形式BLDGULDK11)(,)(其中其中式（式（2-101）是高斯）是高斯賽德?tīng)柕木仃囆问?。賽德?tīng)柕木仃囆问健KXXBLDU

12、XLDXBUXXLDBXULDBAXmmmmmm)()1(1)(1)1()()1()()()()(（2-101）高斯高斯賽德?tīng)柕ㄙ惖聽(tīng)柕ǖ?1頁(yè)/共41頁(yè) ， （二）迭代的矩陣形式（書(shū)上）（二）迭代的矩陣形式（書(shū)上）BLDGULDKGKXXBUXXLDUXLXBDXULDAmmmmmmm11)()1()()1()()1(1)1()(,)()()(式（式（2-100）可寫(xiě)成）可寫(xiě)成亦即亦即故故其中其中（2-101）式（式（2-101）是高斯）是高斯賽德?tīng)柕木仃囆问?。賽德?tīng)柕木仃囆问?。高斯高斯賽德?tīng)柕ㄙ惖聽(tīng)柕ǖ?2頁(yè)/共41頁(yè)題題9用高斯用高斯-賽德?tīng)柕ㄇ蠼庀铝蟹匠探M賽

13、德?tīng)柕ㄇ蠼庀铝蟹匠探M2 . 453 . 82102 . 7210321321321xxxxxxxxx0)0(3)0(2)0(1xxx取初值解解 按式（按式（2-100）得到的高斯）得到的高斯賽德?tīng)柕惴?，有賽德?tīng)柕惴ǎ?4. 02 . 02 . 083. 02 . 01 . 072. 02 . 01 . 0)1(2)1(1)1()()1()1()()()1(3312321mmmmmmmmmxxxxxxxxx第23頁(yè)/共41頁(yè)計(jì)算結(jié)果見(jiàn)下表：計(jì)算結(jié)果見(jiàn)下表： 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頁(yè)/共41頁(yè)（一）迭代算法（一）迭代算法imiijnijmjijmjijiiimiijnijmiiimjijmjijiiiijnijmjijmjijiiimixxxaxabaxxaxaxabaxaxabax)(11)()1()(11)()()1(111)()1()1()(1)(1)(1逐次超松弛法又是對(duì)高斯逐次超松弛法又是對(duì)高斯賽德?tīng)柗ǖ馁惖聽(tīng)柗ǖ囊粋€(gè)改進(jìn)一個(gè)改進(jìn)。高斯高斯賽德?tīng)柕惴ㄙ惖聽(tīng)柕惴ㄖ鸫纬沙诜ㄖ鸫纬沙诜?/p>

15、第25頁(yè)/共41頁(yè) 這里這里r是用來(lái)加速收斂的權(quán)因子，稱(chēng)為松弛因子，是用來(lái)加速收斂的權(quán)因子，稱(chēng)為松弛因子，r=1時(shí)，時(shí)，即為賽德?tīng)柕?。式（即為賽德?tīng)柕?。式?-102）在）在r1時(shí)為超松弛迭代時(shí)為超松弛迭代（簡(jiǎn)稱(chēng)（簡(jiǎn)稱(chēng)SOR），在），在r1時(shí)為松弛迭代。通常取時(shí)為松弛迭代。通常取1r2。 修改為修改為（2-102）imimixrxx)()1(逐次超松弛法逐次超松弛法第26頁(yè)/共41頁(yè)), 2 , 1 , 0;, 2 , 1()()1 ()1 ()(111)()1()()1()()()1()()1(mnixaxabarxrrxxrxxrxxijnijmjijmjijiiimimimi

16、mimimimi式（式（2-102）還可等價(jià)地表示為）還可等價(jià)地表示為（2-103） 式（式（2102）和（）和（2-103）就是逐次超松弛迭代算法）就是逐次超松弛迭代算法（r1）。）。逐次超松弛法逐次超松弛法第27頁(yè)/共41頁(yè) ， （二）迭代的矩陣形式（二）迭代的矩陣形式BrLDrGrUDrrLDKGKXXrBXrUIrDXrLDmmmm11)()1()()1()()1()()1 ()()()1 ()()1()()1(mmmmUXLXBrXrDDX（2-104）式（式（2-104）是逐次超松弛法的矩陣形式。）是逐次超松弛法的矩陣形式。直接根據(jù)式（直接根據(jù)式（2-103）寫(xiě)）寫(xiě)整理得整理得逐次

17、超松弛法逐次超松弛法111)()1()()1()()1 (ijnijmjijmjijiiimimixaxabarxrx（2-103）第28頁(yè)/共41頁(yè) 超松弛因子通常在超松弛因子通常在1.4到到1.9 之間。松馳因子的選之間。松馳因子的選取對(duì)迭代格式的收斂速度影響極大。實(shí)際計(jì)算時(shí)，可取對(duì)迭代格式的收斂速度影響極大。實(shí)際計(jì)算時(shí)，可以根據(jù)系數(shù)矩陣的性質(zhì)，結(jié)合經(jīng)驗(yàn)通過(guò)反復(fù)計(jì)算來(lái)確以根據(jù)系數(shù)矩陣的性質(zhì)，結(jié)合經(jīng)驗(yàn)通過(guò)反復(fù)計(jì)算來(lái)確定松馳因子。定松馳因子。使收斂最快的松弛因子稱(chēng)為最佳松弛因子（使收斂最快的松弛因子稱(chēng)為最佳松弛因子（ ）。）。optr逐次超松弛法逐次超松弛法第29頁(yè)/共41頁(yè)舉例舉例用用SOR

18、方法解線性方程組方法解線性方程組111141111411114111144321xxxx方程精確解為方程精確解為X=（-1，-1，-1，-1）T 解解 : 取取x(0) =(0,0,0,0)T , 取不同的松弛因子，得取不同的松弛因子，得到的滿(mǎn)足誤差到的滿(mǎn)足誤差10-5的迭代次數(shù)如下表所示。的迭代次數(shù)如下表所示。逐次超松弛法逐次超松弛法第30頁(yè)/共41頁(yè)松弛因子松弛因子迭代次數(shù)迭代次數(shù)松弛因子松弛因子迭代次數(shù)迭代次數(shù)1.01.11.21.31.422171211141.51.61.71.81.917233353109 本例說(shuō)明，松弛因子選擇的好，會(huì)使本例說(shuō)明，松弛因子選擇的好，會(huì)使SOR迭代法

19、的迭代法的收斂大大加速。本例中收斂大大加速。本例中1.3 是最佳松弛因子。是最佳松弛因子。逐次超松弛法逐次超松弛法第31頁(yè)/共41頁(yè)。，有對(duì)任何的向量三角不等式。有對(duì)任何實(shí)數(shù)齊次性。時(shí)當(dāng)非負(fù)性YXYXYXXCCXXOXO,)3(,C)2(0, 0) 1 (四、四、 向量和矩陣的范數(shù)的概念向量和矩陣的范數(shù)的概念向量向量X的范數(shù)的范數(shù) 是滿(mǎn)足下列條件的是滿(mǎn)足下列條件的實(shí)數(shù)實(shí)數(shù)。X迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則第32頁(yè)/共41頁(yè)nxxxX211222212nTxxxXXX),max(max211ninixxxxX三個(gè)常用的向量范數(shù)：三個(gè)常用的向量范數(shù)：設(shè)設(shè)X = (x1, x2

20、, xn)T，則有，則有列范數(shù)列范數(shù)譜范數(shù)譜范數(shù)行范數(shù)行范數(shù)迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則第33頁(yè)/共41頁(yè))00(01AAA非負(fù)性）（為實(shí)數(shù)齊次性）（cAccA,2BABA三角不等式）（3 4BAAB 相容性）（ 矩陣的范數(shù)矩陣的范數(shù) 是定義在是定義在Rnn上的上的非負(fù)的實(shí)值函數(shù)非負(fù)的實(shí)值函數(shù)，它它滿(mǎn)足下列條件的實(shí)數(shù)。滿(mǎn)足下列條件的實(shí)數(shù)。A迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則第34頁(yè)/共41頁(yè)njijniaAA11max:的行范數(shù)矩陣niijnjaAA111max:的列范數(shù)矩陣)(:max2AAAAT的譜范數(shù)矩陣的最大特征值表示其中AAAATT)(max

21、三個(gè)常用的矩陣范數(shù)：三個(gè)常用的矩陣范數(shù)：迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則矩陣每一列元素絕對(duì)值之和取最大值矩陣每一列元素絕對(duì)值之和取最大值矩陣每一行元素絕對(duì)值之和取最大值矩陣每一行元素絕對(duì)值之和取最大值第35頁(yè)/共41頁(yè)（一）一般迭代法的收斂準(zhǔn)則與收斂條件（一）一般迭代法的收斂準(zhǔn)則與收斂條件 對(duì)方程組對(duì)方程組AX=B，一般（線性）迭代法是按公式，一般（線性）迭代法是按公式以任意初始向量以任意初始向量X（0）開(kāi)始，反復(fù)進(jìn)行計(jì)算。當(dāng)開(kāi)始，反復(fù)進(jìn)行計(jì)算。當(dāng)m時(shí)，時(shí)，迭代向量序列迭代向量序列 有時(shí)收斂于方程組的精確解，有時(shí)則有時(shí)收斂于方程組的精確解，有時(shí)則不然。如向量序列不然。如向量

22、序列 收斂于方程組的精確解，就稱(chēng)該收斂于方程組的精確解，就稱(chēng)該迭代法收斂迭代法收斂；反之，則謂；反之，則謂不收斂或發(fā)散不收斂或發(fā)散。GKXXmm)()1()(mX)(mX（2-112）定義定義迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則第36頁(yè)/共41頁(yè)收斂準(zhǔn)則收斂準(zhǔn)則 收斂準(zhǔn)則是指使迭代終止的條件。收斂準(zhǔn)則是指使迭代終止的條件。通常使用的收斂準(zhǔn)通常使用的收斂準(zhǔn)則有絕對(duì)準(zhǔn)則和相對(duì)準(zhǔn)則兩種。則有絕對(duì)準(zhǔn)則和相對(duì)準(zhǔn)則兩種。BRXXXRXXmmmmmmm/)()1()()1()()()1(絕對(duì)準(zhǔn)則絕對(duì)準(zhǔn)則相對(duì)準(zhǔn)則相對(duì)準(zhǔn)則或或或或)()(mmAXBR這里這里 是方程的余差向量，是方程的余差向量，是給定的控制是給定的控制誤差。誤差。迭代法的收斂條件與收斂準(zhǔn)則迭代法的收斂條件與收斂準(zhǔn)則第37頁(yè)/共41頁(yè) 定理定理2 迭代格式（迭代格式（2-112）收斂的充分必要條件是迭代）收斂的充分必要條件是迭代矩陣矩陣K的譜半徑的譜