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

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

2、過有限的四次運(yùn)算得到。(實(shí)際計算中存在舍入誤差)高斯消去法、矩陣分解法和迭代法：核心是迭代解的收斂條件和收斂速度。雅可比迭代，高斯-塞德爾迭代，基本思想和方法：通過行初等變換將系數(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ù)量級，然后將它們四舍五入。然而，計算機(jī)的有效位數(shù)是有限的，這使得消去后的三角方程不準(zhǔn)確。結(jié)論：在消去過程中，主元素可能為零，則消去法不會執(zhí)行，即使不為零，當(dāng)主元素很小時，將其作為除數(shù)會導(dǎo)致其他元素的嚴(yán)重增加和舍入誤差的擴(kuò)散，最終使計算解不可靠。解決方法：對于一般矩陣，最好選擇系數(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īng)進(jìn)行記錄：完整主元素之間的優(yōu)缺點(diǎn)比較缺點(diǎn)：計算量大；在矩陣A上實(shí)現(xiàn)初等行變換相當(dāng)于將A乘以左初等矩陣，因此在第一次消去(2.2)之后，它被變換成，即3.1矩陣的三角分解LU分解，步驟k的

6、初等矩陣是，并且，重復(fù)這個過程，最終得到上三角矩陣被表示為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的各階主子公式大于零。摘要：指出當(dāng)A是A(2.4)，uii 0 (i=1，n)的L

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

8、c具有(3)時，范數(shù)也稱為2-范數(shù)或歐氏函數(shù)；規(guī)范也稱為-規(guī)范或統(tǒng)一規(guī)范。該函數(shù)用于在Matlab中計算向量x的范數(shù)。從性質(zhì)(3)，很容易得到矩陣范數(shù)的定義。矩陣范數(shù)可以在向量范數(shù)的基礎(chǔ)上進(jìn)一步定義。如果上述公式中的向量范數(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)如果是，則；此外，只有當(dāng)(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ù)點(diǎn)后兩位的近似解，高斯-塞德爾迭代法只需迭代三次。雅可比迭代法

11、需要迭代七次。為了進(jìn)一步研究，從矩陣的角度討論了上述迭代方法。對于方程Ax=b的線性系統(tǒng)，記住，D=diag(a11，a22，ann)，有A=D-L-U，所以方程Ax=b的線性系統(tǒng)可以寫成(D-L-U)x=b，這相當(dāng)于，因此，迭代公式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的任意特征值是對應(yīng)的特征向量，即假設(shè)它是任意向量范數(shù)及其相容的矩陣范數(shù)，有：首先，引入幾個定

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

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

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