數(shù)值分析課件 第5章 解線性方程組的直接法

1、第五章線性代數(shù)方程的數(shù)值解法解線性方程問(wèn)題是科學(xué)研究和工程計(jì)算中最常見(jiàn)的問(wèn)題。包括理解線性方程問(wèn)題的方法，如電的網(wǎng)絡(luò)問(wèn)題、工程力學(xué)中解決連續(xù)力學(xué)(微分方程)問(wèn)題的差分方法、有限元方法、邊界元方法和函數(shù)的樣條插值、最小二乘法擬合等。因此，線性方程的解法在數(shù)值計(jì)算中占有非常重要的位置。對(duì)于階線性方程式，方程式有唯一的解決方案。解釋為Cramer法則。其中是使用向量而不是的熱向量獲得的矩陣。每個(gè)階行列式的公共項(xiàng)，每個(gè)項(xiàng)都有系數(shù)，所以在計(jì)算階行列式的時(shí)候，我們都要計(jì)算一個(gè)決定因素，計(jì)算，還要進(jìn)行子劃分，所以用Cramer法則解決階分離法(除了加減法)，計(jì)算是很驚人的。那么要進(jìn)行約乘?？梢钥闯?，克雷默定

2、律在理論上是絕對(duì)正確的，但在實(shí)際計(jì)算中卻是不可能的。因此，尋找有效的數(shù)值計(jì)算方法是非常必要的課題。線性方程可以分為兩大類：系數(shù)矩陣序列的高、低或零元素。也就是說(shuō)，系數(shù)矩陣角度不高，幾乎沒(méi)有零元素的低階稠密線性方程的類。另一類是系數(shù)矩陣角度高、零元素為絕對(duì)優(yōu)勢(shì)(例如上面)的高階稀疏線性方程。線性方程的數(shù)值解法也可以分為直接法和迭代法兩類。直接法是通過(guò)有限步長(zhǎng)運(yùn)算獲得方程精確解的一種方法，沒(méi)有舍入誤差。但是，實(shí)際計(jì)算時(shí)，由于初始數(shù)據(jù)成為機(jī)器數(shù)而產(chǎn)生的誤差和計(jì)算過(guò)程中產(chǎn)生的舍入誤差等影響了解決方案的精度，因此直接方法實(shí)際上只能計(jì)算方程實(shí)際解的近似值。常用的有效算法是高斯消元法和矩陣的三角分解法。迭代

3、方法是使用極限過(guò)程逼近精確解的方法。通過(guò)幾種方法逐步生成近似解序列，使極限成為方程的解，例如給定的初始近似解向量。實(shí)際計(jì)算時(shí)只能執(zhí)行有限的步驟，所以得到的也是近似解決方案。常用的迭代法是Jacobi迭代法、高斯-Seidel迭代法、連續(xù)超松弛法和共軛梯度法。直接法的優(yōu)點(diǎn)是計(jì)算次數(shù)固定，可以提前估計(jì)。通常需要存儲(chǔ)系數(shù)矩陣和常量的所有元素，因此需要更多的存儲(chǔ)單位，編寫過(guò)程復(fù)雜，通常適合求解低階線性方程組。迭代方法的優(yōu)點(diǎn)在于原始系數(shù)矩陣不變，只存儲(chǔ)原始方程系數(shù)矩陣的非零元素，因此算法簡(jiǎn)單，程序容易編寫，所需存儲(chǔ)單元少，廣泛用于求解高階稀疏線性方程。缺點(diǎn)是存在收斂和收斂速度問(wèn)題，僅適用于具有特定性質(zhì)的

4、方程式。1消化法1.1三角方程的解形狀(1.1)的方程式稱為向上三角形方程式。以矩陣格式編寫簡(jiǎn)潔地寫如下。如果是(1.1)，則存在唯一的解決方案求解上三角方程(1.1)的過(guò)程稱為迭代過(guò)程。此外，求解這樣的方程也很容易，所以對(duì)于一般方程體系，必須用(1.1)表達(dá)式的形式進(jìn)行構(gòu)造和求解。1.2高斯消元法考慮方程(1.2)其矩陣形式如下其中有多種方法可以使線性方程(1.2)成為等效三角形方程，其中高斯消去法是最基本的方法。高斯消元法分為消元計(jì)算和替代解兩個(gè)過(guò)程。為了后面符號(hào)的統(tǒng)一，記憶方程式(1.2)是其中。消費(fèi)源計(jì)算第一步：使第一列中主要對(duì)角元素下的所有元素約為零。設(shè)定，計(jì)算使用乘法(1.2)的第

5、一個(gè)方程添加到第一個(gè)方程中，并完成第一步刪除后的結(jié)果(1.2)的相同解方程(1.3)簡(jiǎn)略地記住其中，零件的方程式如下假設(shè)上一步驟移除完成，則(1.2)的相同解決方案方程式為(1.4)簡(jiǎn)略地記住。步驟：使第一列中主要對(duì)角元素下的所有元素都等于0左右。設(shè)定，計(jì)算使用乘積(1.4)的第一個(gè)方程式，將其加入至第一個(gè)方程式，并完成第一步的移除。一起解方程式其中元素的計(jì)算公式為繼續(xù)以上過(guò)程，完成步驟移除(1.2)，然后使用相同解決方案的父三角表達(dá)式(1.5)簡(jiǎn)略地記住。逆向代解決方案因此，所以(1.6)高斯消元階段能夠成功進(jìn)行的條件是，現(xiàn)在的問(wèn)題是矩陣必須具有什么樣的特性才能成立這個(gè)條件。使用顯示的順序主

6、樣式時(shí)有以下整理定理1降的主要元素的充要條件是矩陣的序主。證明必要性。由于主要元素，您可以執(zhí)行步驟刪除，并且每個(gè)步驟刪除過(guò)程不會(huì)更改順序主要子樣式的值需要得到證明。用歸納法證明適當(dāng)性。命題肯定成立。假設(shè)的命題是對(duì)的。安裝。根據(jù)歸納法，高斯消元法可以：其中是對(duì)角元素為的上方三角形陣列。由于是通過(guò)步驟刪除方法獲得的，因此每個(gè)步驟刪除過(guò)程不會(huì)更改順序主樣式的值，因此順序主樣式為知道，充分證明。計(jì)算1.3高斯消元法1)卸載過(guò)程的工作量剔除過(guò)程的第一步：計(jì)算乘法需要子分割運(yùn)算。行乘法將添加到行中，需要分別進(jìn)行乘法和減法(無(wú)需計(jì)算列元素)，需要進(jìn)行乘法()，因此在刪除時(shí)，乘法、除法和減法運(yùn)算量為乘法除法計(jì)

7、數(shù)：加法和減法計(jì)數(shù)：2)迭代過(guò)程的工作量計(jì)算需要二次乘法和二次加法減法運(yùn)算，整個(gè)迭代過(guò)程的計(jì)算量為：乘法和除法：減去：所以高斯消元法的總計(jì)算乘法和除法：(在大的情況下)加法和減法： (較大時(shí))當(dāng)時(shí)高斯消元法需要約430次乘法和除法法則約2次乘法。1.4高斯消元法的矩陣形式對(duì)于矩陣形式，高斯消元法的消元過(guò)程與將方程(1.2)的增量矩陣轉(zhuǎn)換為一系列基本轉(zhuǎn)換、將系數(shù)矩陣轉(zhuǎn)換為三角形矩陣或使用一系列基本矩陣消除左乘矩陣的過(guò)程相同，因此消元過(guò)程可以用矩陣運(yùn)算來(lái)表示。第一次消耗相當(dāng)于使用預(yù)設(shè)矩陣左邊的乘法矩陣通常，第一次消耗相當(dāng)于使用預(yù)設(shè)矩陣左邊的乘法矩陣消費(fèi)一次后得出ITZY記錄頂部三角形矩陣，如下所示

8、其中單位下的三角形陣列。表明，消除過(guò)程實(shí)際上是將系數(shù)矩陣分解為單位下三角矩陣和上三角矩陣的乘積的過(guò)程。這種分解稱為杜氏分解，也稱為分解。定理2(矩陣因數(shù)分解)設(shè)置為階方形，因?yàn)槿绻嬖陧樞蛑黜?xiàng)，則具有唯一單位下和上三角陣列。上面的分析證明了它是可以分解的。以下證明了分解的唯一性。如果不特別的話，有兩個(gè)分解。其中是單位下的三角形陣列，是上方三角形陣列。因?yàn)椴黄婀?，都是可逆的。所以左邊是單位下的三角形陣列，右邊是上方三角形陣列是，唯一性證明。對(duì)于單個(gè)陣列，可以記住順序主樣式不等于0其中，由階比奇異陣、階單元下三角陣、被證明的結(jié)果所知道的分解是唯一的。所以唯一確定的。而且是唯一確定的。定理2的逆命題

9、如下。定理三次矩陣非奇點(diǎn)，有唯一分解(單位下三角陣列，上三角陣列)的情況下，試驗(yàn)證據(jù)的順序注記。(證據(jù)留給讀者)2主要元素方法前面指出，Gauss刪除方法必須在每個(gè)縮減主元素下進(jìn)行。這里要指出的是，即使時(shí)間很長(zhǎng)，元素也不能隨心所欲。當(dāng)成為第一個(gè)析構(gòu)函數(shù)時(shí)，乘以第一個(gè)方程，因?yàn)闀r(shí)間很長(zhǎng)的時(shí)候乘數(shù)很大，乘以第一行的因子，結(jié)果數(shù)量急劇增加，剔除計(jì)算中出現(xiàn)了大量吃小數(shù)的現(xiàn)象，最后計(jì)算結(jié)果的精度可能會(huì)很低或失真。范例1求解方程式(1)找到正確的解決方案。(2)浮點(diǎn)機(jī)采用高斯消去法。解(1)方程的精確解很容易得到。(2)給定浮點(diǎn)機(jī)的原始方程如下因?yàn)橐瞥诙€(gè)型式。大量的小數(shù)被“吃掉”了第一式，第一式。與精

10、確的解決方案相比，不再有精度。主要元素太小，大小太大，所以不準(zhǔn)確。變更此條件的方法是變更方程式的一個(gè)或兩個(gè)。然后使用高斯消元法。所以要好好解決。這個(gè)例子說(shuō)明，用高斯消元法求解方程時(shí)，小主元素可能會(huì)導(dǎo)致嚴(yán)重的結(jié)果，因此，應(yīng)盡量避免小主元素的出現(xiàn)。另一方面，通過(guò)改變方程的順序或改變變量的順序，可以選擇絕對(duì)值大的元素的主要元素，從而減少舍入誤差并提高計(jì)算精度。2.1列關(guān)鍵元素和所有關(guān)鍵元素的刪除方法1.刪除熱關(guān)鍵元素的方法。刪除元素時(shí)，在的行元素中選擇絕對(duì)值最大的元素作為主元素，將該值替換為位置，然后執(zhí)行刪除計(jì)算。使用方程式(1.2)的延伸矩陣(2.1)表達(dá)它，在擴(kuò)展矩陣中直接計(jì)算。具體步驟如下：第

11、一步：首先，在上述矩陣的第一行中選擇絕對(duì)值最大的那個(gè)。例如：將(2.1)的第一行與第一行交換。為方便起見(jiàn)，行交換后將增量矩陣記為，并進(jìn)行第一析構(gòu)子以獲得矩陣假設(shè)如何移除已完成階段的主要元素，如下所示步驟：在矩陣的第一列中，選擇關(guān)鍵元素，如所示。的第一行與第二行交換，消耗第一行。經(jīng)過(guò)階段，增廣矩陣(1.7)變成了上三角形算法1(高斯列關(guān)鍵元素消除方法)說(shuō)明：剔除結(jié)果、行乘數(shù)、det存儲(chǔ)決定因素值。輸入、設(shè)置、1.卸載過(guò)程沒(méi)錯(cuò)(1)選擇關(guān)鍵元素：(a)按列選擇關(guān)鍵元素。也就是說(shuō)，確定(b)可能的話停機(jī)；(c)如果(線路交換)對(duì)。(2)（）沒(méi)錯(cuò)(3)5.替代進(jìn)程(a)輸出失敗消息，停機(jī)時(shí)間(b)(c

12、)沒(méi)錯(cuò)備注：計(jì)算程式的判斷可以使用或(預(yù)先選取的極小正數(shù))。完整的主要因素方法。第一步，在的右下順序矩陣的所有元素中，選擇絕對(duì)值最大的元素作為主元素，將該值替換為位置，然后執(zhí)行刪除計(jì)算。與“刪除整個(gè)周”和“刪除列周”方法相比，每個(gè)步驟刪除流程中選定的主要元素范圍更大，因此控制舍入誤差更有效，解決結(jié)果更可靠。但是，整個(gè)主方法需要在計(jì)算過(guò)程中交換行和列，因此過(guò)程更復(fù)雜，計(jì)算時(shí)間更長(zhǎng)。熱主元法的準(zhǔn)確度比整個(gè)主元法略低，但計(jì)算簡(jiǎn)單，工作量大大減少，在計(jì)算經(jīng)驗(yàn)和理論分析中，數(shù)值穩(wěn)定性和整個(gè)主方法一樣好，因此熱主元法是求解中小型高密度線性方程組的最佳方法之一。2.2列主成分消除法的矩陣形式在移除的第一階段

13、交換的行和行與執(zhí)行以下矩陣計(jì)算相同：(1)基本陣列矩陣左乘法，即其中，是由交換單位矩陣的第一行和第二行獲得的。很明顯。(2)基本矩陣乘以左邊，也就是因此，具有行交換的步驟移除過(guò)程可以用矩陣表示所以有因此，常識(shí)可以用以下方法代替其中如果指針是位于的單位下的三角形數(shù)組，則可以證明一個(gè)指針是位于的單位下的三角形數(shù)組。趙令排列。所以也就是說(shuō)我注意到它仍是單位下的三角形陣列都有常識(shí)是指具有線交換的高斯消元過(guò)程中生成的矩陣分解。這相當(dāng)于系數(shù)矩陣先執(zhí)行每一步剔除，然后分解生成的矩陣。上述討論可以敘述如下定理4(列主成分三角分解定理)為非奇異矩陣時(shí)，數(shù)組矩陣存在，并且其中是單位下的三角形矩陣，是上三角形矩陣。

14、3矩陣三角分解法3.1直接三角分解法1.不選擇主元素的直接三角分解方法設(shè)置為以下格式(3.1)通過(guò)矩陣的乘法規(guī)則由此可以計(jì)算總和的公式(3.2)具體步驟如下：1)計(jì)算的第1行，的第1列2)計(jì)算中的行、列范例2尋找矩陣三角分解。解決方案標(biāo)準(zhǔn)(3.2)所以小型格式：.在示例2中，矩陣的三角分解以緊湊形式計(jì)算，結(jié)果如下表所示如果線性方程的系數(shù)矩陣三角分解，那么求解方程就等于求解兩個(gè)三角形方程。第一步：先解下一個(gè)三角形方程式海得島州第二步：求解上三角方程。海得島州2.選擇主元素的直角三角形分解方法不選擇主元的直接三角分解過(guò)程可以進(jìn)行到最后的條件是，即使實(shí)際上不是恒星，也可能發(fā)生任何情況，此時(shí)分解過(guò)程不

15、會(huì)進(jìn)行。此外，小而小的情況下，在計(jì)算過(guò)程中舍入誤差會(huì)急劇增加，解決方案的精度會(huì)非常低。但是，如果不是單數(shù)，則可以通過(guò)交換的行執(zhí)行矩陣分解。實(shí)際上，使用與列主移除方法等效的選擇主元素的三角分解。也就是說(shuō)，在直接三角剖分的每個(gè)階段，只需引入主元素選擇技術(shù)。步驟分解完成?？紤]步驟分解(4)(1)計(jì)算輔助量并下降(2)選擇主要原因。確定行號(hào)而且，記錄主行號(hào)： (一維數(shù)組)(3)交換的行和行元素(4)計(jì)算的行和列元素(這里)上述計(jì)算過(guò)程完成后，可以使用的分解、的上三角形部分保存、的嚴(yán)格下三角形部分保存、陣列陣列的最后記錄。例如，如果設(shè)置所以方程的解法等于可以通過(guò)和完成的解法。示例3使用主元素的直接三角分

16、解方法求解方程。在這里而且，解決方案(1)分解選定主體，刪除中間結(jié)果對(duì)應(yīng)的位置元素，陣列記錄主行號(hào)。第一步分解：因?yàn)榈诙A段分解：因?yàn)樗杂蛇x擇主圖元的過(guò)程.而且，(2)解決方法；好的，好的求解3.2三重方程的追趕法數(shù)值計(jì)算(例如使用三次樣條插值或差分方法的常微分方程的邊值問(wèn)題)經(jīng)常會(huì)求解以下方程其中系數(shù)矩陣(3.3)是具有非零元素的特殊稀疏矩陣，集中在主對(duì)角線及其旁邊的兩個(gè)輔助對(duì)角線(稱為tridiagonal矩陣)上。方程式稱為tridiagonal方程式。在tridiagonal方程式中使用高斯移除方法時(shí)，程序可能會(huì)大大簡(jiǎn)化。第一次剔除時(shí)只剔除，所以剔除過(guò)程是使用單位下的對(duì)角矩陣左邊乘法矩陣。上面的每個(gè)列元素都是0，因此很容易看出它有格式定理5矩陣(3.3)滿足以下條件(3.4)可以分解(3.5)其中，在矩陣(3.3)中給出，分解是唯一的。證明將樣式(3.5)的右端擴(kuò)展到乘法法則，并與中的元素進(jìn)行比