線性方程組求解的數(shù)值方法.ppt

1、1、第二章是求解線性方程組的數(shù)值方法，第二章是求解線性方程組的數(shù)值方法，1。高斯消去法2。矩陣分解方法3。向量范數(shù)和矩陣范數(shù)4。迭代解法5。方程的病態(tài)問題和誤差分析，主要內(nèi)容：第二章是求解線性方程的數(shù)值方法，了解各種線性方程的數(shù)值解法；掌握解法和解法的誤差分析方法；該算法可以通過編程實現(xiàn)。特別強調(diào)的是：培養(yǎng)用計算機編程解決問題的習慣，而不是用筆計算，這是國內(nèi)外學生之間的一個主要差距。教學要求：在自然科學和工程技術(shù)中，許多問題需要通過解線性方程來解決。因此，求解線性方程組是科學技術(shù)中的一個普遍問題。求解線性方程組有兩種數(shù)值方法：直接法和迭代法。直接法：計算過程中沒有舍入誤差，方程組的精確解可以通

2、過有限的四次運算得到。(實際計算中存在舍入誤差)高斯消去法、矩陣分解法和迭代法：核心是迭代解的收斂條件和收斂速度。雅可比迭代，高斯-塞德爾迭代，基本思想和方法：通過行初等變換將系數(shù)矩陣化為三角矩陣；用逆向生成法求解方程。(1)利用消去法(高斯消去法)求解方程，高斯消去法是求解方程的經(jīng)典方法。高斯消去法，(2.1)，3.1結(jié)論：整個計算過程可分為兩個部分：(1)消去法：將原始方程轉(zhuǎn)化為以系數(shù)矩陣為上三角矩陣的方程；(2)回歸：求解系數(shù)矩陣為上三角矩陣的方程，(2)得到：解：(1)消去法：對于一般情況：n階線性方程的高斯消去法，記住，增廣矩陣，(2.2)，(1)步驟1 (k=1)，一般形式的高斯消

3、去法：把它加到第I個方程中，去掉第二個方程2.2，直到第n個方程中的未知數(shù)，(代表第I行)，得到等價于原始方程的方程。記為(2)一般的第k個消去法()，讓我們假設(shè)上述消去過程的第一步、第二步和第k-1步已經(jīng)完成，并且，其中：讓我們計算乘數(shù)，(也就是說，將乘以2.2的第k個方程加到第I個方程，并且消去2.2的第k-1個方程，直到第n個方程。直到第(n-1)次消去完成，我們最終得到與原始方程等價的三角形方程。(2.3)消去過程結(jié)束后，我們求解三角形方程2.3，得到解的公式。這一過程被稱為反向生成過程。例如：考慮到方程，在高斯消去法的每一步中用來消去其他元素的主要元素稱為該步。高斯消去法作為一種數(shù)值

4、方法，主成分的選擇會影響計算結(jié)果嗎？則方程的精確解為，而以(1)為主要元素的高斯消去法得到的解為，顯然結(jié)果是錯誤的。錯誤在哪里？原因是我們在消去法中使用了小的主成分，這大大增加了簡化方程元素的數(shù)量級，然后將它們四舍五入。然而，計算機的有效位數(shù)是有限的，這使得消去后的三角方程不準確。結(jié)論：在消去過程中，主元素可能為零，則消去法不會執(zhí)行，即使不為零，當主元素很小時，將其作為除數(shù)會導致其他元素的嚴重增加和舍入誤差的擴散，最終使計算解不可靠。解決方法：對于一般矩陣，最好選擇系數(shù)矩陣(或消去后的低階矩陣)列中絕對值最大的元素作為每一步的主元素，這樣高斯消去法具有更好的數(shù)字穩(wěn)定性。(高斯列主元消去法)，1

5、。列主元法，第一列最大絕對值為10，取10作為主元。在n階方程的第k輪消去中，選擇第k列最后(n-k-1)個元素中絕對值最大的主元素。，x3=6.2/6.2=1，x2=(2.5-5x3)/2.5=-1，x1=(7 7x2-0x3)/10=0，x1=0x2=-1x3=1，第二列中的最后兩個數(shù)字選擇主元素2.5，2作為完全主元素X1=0 x2=-1 x3=1，6是框中最大的，在交換行和列(即x3和x2交換位置)時應進行記錄：完整主元素之間的優(yōu)缺點比較缺點：計算量大；在矩陣A上實現(xiàn)初等行變換相當于將A乘以左初等矩陣，因此在第一次消去(2.2)之后，它被變換成，即3.1矩陣的三角分解LU分解，步驟k的

6、初等矩陣是，并且，重復這個過程，最終得到上三角矩陣被表示為u，然后上三角矩陣被表示為u，然后本質(zhì)上，高斯消去產(chǎn)生分解成兩個三角矩陣并相乘的因式分解。如果A是非奇異矩陣，則邏輯單元分解是唯一的；否則，分解不是唯一的。消元法：消元法與三角分解法的關(guān)系：三角分解法：用直接三角分解法求解線性方程組的具體過程：1。2。計算U的R行和L的R列，元素r=2，3，n，3。(1) LU分解，然后，求解： (1)矩陣LU分解，(1)，所以，(2)，經(jīng)過計算，(2)求解x:因此，喬萊斯基分解，3.2矩陣，對稱正定矩陣A: AT=A，A的各階主子公式大于零。摘要：指出當A是A(2.4)，uii 0 (i=1，n)的L

7、U分解時，非奇異矩陣可以有三角分解，因為A是對稱的正定矩陣，那么u進一步分解：根據(jù)A:so:的對稱性，由分解的唯一性可知，其中p是上三角矩陣，這個對稱正定矩陣的分解稱為Cholesky分解。對稱正定矩陣的喬萊斯基分解由Matlab中的函數(shù)“chol”給出。在n個步驟之后，可以直接獲得。思路： (1)分解對稱正定矩陣，讓n階對稱正定矩陣a被分解，首先用待定系數(shù)法求出l的元素，膽斯基分解的具體步驟(膽斯基分解):(2)分解并求解方程，膽斯基法計算公式：分解計算：解：，1。向量范數(shù)的定義，其中范數(shù)是，最常用的范數(shù)是，并且很容易證明向量范數(shù)滿足以下性質(zhì)：(1)如果，那么；此外，當且僅當(2)對于任何數(shù)

8、c具有(3)時，范數(shù)也稱為2-范數(shù)或歐氏函數(shù)；規(guī)范也稱為-規(guī)范或統(tǒng)一規(guī)范。該函數(shù)用于在Matlab中計算向量x的范數(shù)。從性質(zhì)(3)，很容易得到矩陣范數(shù)的定義。矩陣范數(shù)可以在向量范數(shù)的基礎(chǔ)上進一步定義。如果上述公式中的向量范數(shù)作為范數(shù)，可以證明定義的矩陣范數(shù)(稱為矩陣范數(shù)或列范數(shù))是，如果向量范數(shù)作為2-范數(shù)，那么，其中(模)稱為矩陣B的譜半徑(是B的任意特征值.)，類似地，Matlab函數(shù)范數(shù)(，)給出矩陣p=1，2或范數(shù)。如果向量范數(shù)為0，則可以證明定義的矩陣范數(shù)(稱為矩陣的范數(shù)或行范數(shù))為0，并且很容易證明矩陣范數(shù)滿足以下性質(zhì)：(1)如果是，則；此外，只有當(2)與任何數(shù)(3)和(4)相容

9、，并由矩陣范數(shù)定義時，它也稱為矩陣范數(shù)。39，3.4經(jīng)典迭代法的構(gòu)造，求解線性代數(shù)方程的方法，中小問題，直接法，迭代法，大規(guī)模和超大規(guī)模問題，經(jīng)典方法，現(xiàn)代方法，40。線性方程的一般形式是：如果它是非奇異的，上面的公式有唯一的解。我們將用一個特定線性方程組的例子來解釋迭代方法。取：即線性方程組為：方程的精確解(用直接法計算)，41。如果方程組是變形的，變量分別從三個方程中分離出來：初始值是，所以公式(1)可以表示為迭代形式：所以我們可以得到一個向量序列，只要序列有一個極限，那么這個極限就是。上述求解線性方程組的迭代法稱為雅可比迭代法。考慮到線性方程的一般形式：其中矩陣A是nn階的平方矩陣，方程

10、的分量形式是：重寫為：從而得到迭代公式：上述公式是一般的雅可比迭代法，也可以記為：充分利用雅可比迭代法中的新值，可以得到以下迭代：上述迭代方法也稱為高斯-塞德爾迭代法，也可以記為： 方程組的精確解是x *=(1，1，1) t，雅可比迭代公式的解是，取初始向量x(0)=(0，0，0)T，可以通過迭代得到。 例1:利用雅可比法和高斯-塞德爾法求解線性方程組，可以看出迭代序列逐一收斂到方程組的解，計算結(jié)果列表如下：高斯-塞德爾迭代法的公式為：并取初始向量x(0)=(0，0，0)T。計算結(jié)果表明，高斯-塞德爾迭代法收斂速度快。對于精確到小數(shù)點后兩位的近似解，高斯-塞德爾迭代法只需迭代三次。雅可比迭代法

11、需要迭代七次。為了進一步研究，從矩陣的角度討論了上述迭代方法。對于方程Ax=b的線性系統(tǒng)，記住，D=diag(a11，a22，ann)，有A=D-L-U，所以方程Ax=b的線性系統(tǒng)可以寫成(D-L-U)x=b，這相當于，因此，迭代公式x(k 1)=D-1(L U)x(k) D-1b k=0，1，2，或者寫成x(k 1)=Bx(k) f k=0，1，2，其中高斯-塞德爾迭代例如，它的精確解是：可以看出，不是所有的方程都收斂，即使不同的方法(如雅可比法和高斯-塞德爾法)收斂速度不同，計算結(jié)果如下：假設(shè)矩陣B的任意特征值是對應的特征向量，即假設(shè)它是任意向量范數(shù)及其相容的矩陣范數(shù)，有：首先，引入幾個定

12、義和引理： 記住并稱它為矩陣b的譜半徑。然后，首先，引入兩個引理(詳細證明見附錄):引理3.1矩陣，那么充要條件是引理3.2矩陣，如果是，它是非奇異的。 定理3.1對于任意初始向量，迭代收斂的充要條件是證明由迭代法生成的序列收斂是必要的，這是序列的極限點。因此，滿足迭代關(guān)系，我們可以得到任意性，已知：已知：通過引理3.1已知，和通過引理2充分(即，有一個唯一的解決方案，這類似于必要性。眾所周知，只要存在某個相容的矩陣范數(shù)，那么當然，這在實踐中往往是一個有效的收斂準則。嚴格對角占優(yōu)矩陣：考慮，假設(shè)，當矩陣。定理3.2如果A是嚴格對角占優(yōu)的矩陣，它必須是非奇異的。因為a是對角占優(yōu)矩陣，所以矩陣是可

13、逆的?？紤]到矩陣的范數(shù)是，因為A是對角占優(yōu)矩陣，從引理3.2可知它是非奇異的，并且因為它是非奇異的，所以A是非奇異的。去拿證書！引理3.2矩陣，如果，是非奇異的。定理3.3系數(shù)矩陣是嚴格對角占優(yōu)的線性代數(shù)方程組，其雅可比迭代和高斯-塞德爾迭代是收斂的。證明了雅可比方法的迭代矩陣為。根據(jù)定理3.2的證明，嚴格對角占優(yōu)矩陣滿足：然后通過定理3.1，雅可比迭代法收斂。(a)證明a)Jocobi，1 .再次考慮高斯-塞德爾方法。它的迭代矩陣，通過反證的方法，假設(shè)高斯-塞德爾迭代不收斂，那么從定理3.1可知，存在一個模大于1的特征值。有一個行列式：(b)高斯-塞德爾的證明，因此，只有它才能成立。因為A是

14、對角占優(yōu)的，所以矩陣是對角占優(yōu)的，那么矩陣必須是非奇異的，這與上面矩陣等于0的行列式相矛盾。因為可逆，所以，得到證書！定理3.4如果滿足迭代矩陣B，由迭代產(chǎn)生的序列滿足收斂速度問題，其中精確解被表達。證明：首先證明(b)，然后證明(a)，因此，這一頁上的第一個公式可以寫成，因為，因此，(b)被證明，顯然對于任何正整數(shù)p，那么(a)和(a)可以通過在這一頁上的第一個公式中重復使用上述公式來證明也就是說，只要和足夠接近，就意味著和足夠接近。定理3.4 (a)給出了迭代收斂速度的估計。顯然，越接近0，生成的序列收斂得越快。定理3.14 (b)，定理3.4、3.6的討論過松弛迭代和塊迭代法。對于給定的迭代方法，每次迭代所需的工作量是確定的。如果迭代方法收斂速度慢，需要更多的迭代，導致算法工作量大，失去使用價值。因此，各種迭