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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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