數(shù)值方法課件

第三章線性代數(shù)方程組的解法§3.3矩陣三角分解法§3.4迭代法§3.1引言§3.2Gauss消去法大量的科學(xué)與工程實際問題常?？梢詺w結(jié)為求解含有多個未知量x1，x2，…，xn的線性代數(shù)方程組求解?！?.1引言即求：(3.1)其矩陣表示形式為：AX

=b當(dāng)線性方程組的階數(shù)較高時，用我們熟悉的克萊姆法則并不實際，例如對于一個20階的線性方程組，如果用克萊姆法則求解，采用每秒十億次的個人計算機，大約需要3萬年。因此，需要采用實用的數(shù)值計算方法來求解。一．三角形方程組的解法對于（3.2）所示的下三角方程組當(dāng)時，有如下解法上述方法稱為前推算法(3.2)(3.3)§3.2Gauss消去法對于（3.3）所示的下三角方程組(3.4)當(dāng)時，有如下解法(3.5)上述方法稱為回代算法二、Gauss消去法由于三角形方程組的求解過程很簡單，因此只要能將方程組化為等價的三角形方程組，則很容易求解。Gauss消去法的基本思想就是通過逐步消元將線性方程組(3.1)化為系數(shù)矩陣為上三角形矩陣的同解方程組，然后用回代算法解此三角形方程組，并得到原方程組的解。設(shè)系數(shù)矩陣A非奇異，則Gauss消去法的具體過程描述如下：Gauss消去法具體過程：其中將改為按上述做法，做完n-1步消元，原方程可化為同解的上三角方程組：其中(i,j=k+1,…,n)（i=k+1,…,n）上面的方程記為記為Remark2：在消去過程中，也可以采用Gauss-Jordan消去法，將方程組化為對角形方程組，進(jìn)而化為單位陣，則右端列向量就化為方程組的解向量。該方法不需回代過程，但總的計算量比Gauss順序消去法略有增加。Remark1：在Gauss順序消去法的消去過程中，可以將右端列向量視為方程組A的第n＋1列，直接對矩陣A（指現(xiàn)在的n行，n＋1列的增廣矩陣）進(jìn)行行初等變換，將其變換為上三角形矩陣，從而回代求解得到方程組的解。

此時高斯順序消去法能進(jìn)行下去，但不能求出唯一解。②當(dāng)

detA=0,說明：①當(dāng)

高斯順序消去法能進(jìn)行下去，但當(dāng)或相對于（k=1,2,…，n)均不為零時

（i=k+1,k+2…，n）比較小時，計算時產(chǎn)生的舍入誤差將導(dǎo)致計算結(jié)果誤差增大。③由于舍入誤差的原因，Gauss順序消去法不是一個實用的方法，實用中應(yīng)該采用選主元的Gauss消去法。

在計算過程中舍入誤差增大迅速，造成計算解與真解相差甚遠(yuǎn)，這一方法就是不穩(wěn)定的方法，反之，在計算過程中的舍入誤差增大能得到控制，該方法就是穩(wěn)定的。小主元是不穩(wěn)定的根源，這就需要采用“選主元素”技術(shù)，即選取絕對值最大的元素作為主元。三、主元素消去法B=

1)列主元消去法一種常用的方法是列主元消去法。設(shè)增廣矩陣為在第一列中選取絕對值最大的元素,如若=調(diào)換第一行與第i行，這時的就是原來的,再進(jìn)行消去法的第一步，即再考慮右下角矩陣，選取絕對值最大的元素作為主元素,經(jīng)過行的對換把主元素移到，

再按消元公式計算（i,j=3,…n）。直至將方程組化成上三角方程組，再進(jìn)行回代就可求得解。然后每一步類似的都在右下角方陣中的第一列中選主元，再經(jīng)行對調(diào),將主元素?fù)Q到右下腳方陣中左上角的位置。再按下一步計算（i,j=k…n)例題：用列主元消去法解線性方程組

解：2)全主元消去法B=

列在A中選取絕對值最大的元素作為主元素，如

,然后交換B

的第一行與第

行，第一列，這時的

就是元素的

元法的第一步，即與第，然后進(jìn)行消都

換把主元素移到再按消元公式計算

（i,j=3,…n）,然后每一步對再考慮右下角矩陣，選取絕對值最大的元素作為主元素,經(jīng)過行的對換和列的對

在右下角方陣中進(jìn)行完全選主元，經(jīng)過行的位置,類似的調(diào)列對調(diào)將主元換到右下角方陣中左上角的位置，再按下一步計算

（i,j=k…n）直至將方程組化成上三角方程組，再進(jìn)行回代就可得解。一.Gauss順序消去法的矩陣形式

設(shè)方程組A=中A的各階順序主子式均不為零，令§3.3矩陣的三角分解法即

（1）

由

得：容易驗證：每個可逆，且

k=1,2,…，n-1

令L=

則

L=

又令

U=

,且

U=

則A=LU，

其中，L為單位下三角矩陣，它的對角元素皆為1。即

U為陣，

由（1）式，上三角矩Gauss消去法的實質(zhì)就是用一連串的初等變換把系數(shù)方陣A化成上三角方陣U，同時把右端向量化為,

若矩陣A=LU，則LU叫做矩陣A的LU分解

.Remark：實際中對A進(jìn)行三角分解，不是利用初等變換矩陣，而是直接使用矩陣乘法得到。（若不加說明，后面我們講到的三角分解一律指Doolittle型分解。）的求解過程為:可推導(dǎo)求解單位下三角形方程組的遞歸公式為

:

求解上三角形方程組的遞歸公式為:

三.直接三角分解法

設(shè)A=LU即Step1：

比較第一行元素：比較第一列元素：解出Step2：

比較第二行元素：

算出：

比較第二列的元素：

得出：一般地，設(shè)U的前k-1行以及L的前k-1列已求出，則比較第k行元素Stepk：

可以算出：

比較第k列元素(i>k即行指標(biāo)>列指標(biāo)，為算,i>k)

算出:這組公式可用下圖記憶（緊湊格式）:的求解過程為:可推導(dǎo)求解單位下三角形方程組的遞歸公式為

:求解上三角形方程組的遞歸公式為:對比計算和公式，

發(fā)現(xiàn)計算的規(guī)律與計算的規(guī)律類似,因此計算的求方程組的過程可用三角分解的緊湊格式取代。事實上,這只要把做為A的第n＋1列進(jìn)行直接三角分解即可。Reamrk：上述直接三角分解法所對應(yīng)的是Gauss順序消去法，二者的乘除運算次數(shù)是相當(dāng)?shù)?。實際中對階數(shù)較高的線性方程組，應(yīng)采用選主元的三角分解法求解，以保證計算結(jié)果的可靠性。四.平方根法（Cholesky分解）

設(shè)A為n階對稱正定矩陣，L是非奇異下三角矩陣，稱為矩陣A的Cholesky分解。n階對稱正定矩陣A，一定存在如下的分解式，其中L為單位下三角陣，D是對角元全為正的對角陣，且這種分解式唯一;，其中L為下三角陣，當(dāng)限定L的對角元為正時，（Cholesky分解）的分解式唯一。定義：

定理：

平方根法的計算公式（為簡單起見設(shè)，L為下三角矩陣）

令

我們可以通過矩陣乘法比較來求L的下三角部分元素。具體計算公式如下:Remark1:由于在上式分解過程中有n次開方運算，故Choledsky分解法也稱為平方根法。

Remark3:可以證明，若用Gauss順序消去法求解對稱正定的方程組Ax＝b，則有Remark2:因為，這說明放大受到控制，故用平方根法解對稱正定的方程組時，不必考慮選主元的問題，算法本身數(shù)值穩(wěn)定。的平方不會超過A的最大對角元，因而舍入誤差的其中是第k步Gauss順序消去過程所得元素。這說明用Gauss順序消去法求解對稱正定方程組也不用選主元。Remark4：為避免開方運算，也可對A做分解。(其中L為單位下三角陣,D為對角陣)五、解三對角方程組的追趕法1.矩陣對角占優(yōu)的概念設(shè)

類似地，也有按列對角占優(yōu)和按列嚴(yán)格對角占優(yōu)的概念。若對于，均有,則對稱矩陣A按行嚴(yán)格對角占優(yōu)。

若對于，不等式均成立，且至少對某個有，則稱矩陣A按行對角占優(yōu)。2.追趕法解三對角方程組設(shè)并滿足嚴(yán)格對角占優(yōu)條件

當(dāng)A嚴(yán)格對角占優(yōu)時，可以證明各階順序主子式非零。

當(dāng)A為上述三對角陣時，A有更特殊的三角分解形式A=LU

即：事實上，比較第i行的第i＋1列，立刻可得U的次上三角線元素為，由矩陣相乘可得，一般地比較第i行第i－1列,比較第i行第i列

即

等價于令即由得

由得

Remark：只要三對角矩陣按行嚴(yán)格對角占優(yōu)，則追趕法定能進(jìn)行下去，且計算過程是穩(wěn)定的（不必選主元素），其乘除法運算次數(shù)為5n－4。上述方法稱為解三對角方程組的追趕法，又稱為Thomas方法。1．向量的范數(shù)一、向量和矩陣的范數(shù)

(1)正定性：.當(dāng)且僅當(dāng)時，(2)齊次性：(3)三角不等式：則稱實值函數(shù)為向量空間上的一種向量范數(shù)．定義3：設(shè)定義在維向量空間上的非負(fù)實值函數(shù)滿足：§3.4解線性方程組的迭代法（1）（2）（3）三個常用的向量范數(shù)：對任意向量，有： 2．矩陣的范數(shù)定義4:設(shè)是中的向量序列，若有向量使則稱向量序列收斂于，記為向量定義5：設(shè)定義在階實矩陣空間上的非負(fù)實值函數(shù)滿足：(1)正定性：.當(dāng)且僅當(dāng)時，(2)齊次性：(3)三角不等式：(4)自相容性：則稱為上的矩陣范數(shù)．常用的矩陣范數(shù)：（1）列范數(shù)（2）行范數(shù)（3）譜范數(shù)（4）F范數(shù)定義6：設(shè)階矩陣在復(fù)數(shù)范圍內(nèi)的諸特征值為則稱為矩陣的譜半徑。迭代法的一般格式為

若，即，，稱為單步迭代法。若為線性的，即，，稱為單步線性迭代法，稱為迭代矩陣。因為計算

一般要用到前面多步的值故稱為多步迭代法。二、迭代法的基本思想及簡單迭代法1.簡單迭代法的構(gòu)造將該方程組等價變形為構(gòu)造簡單迭代格式，。若收斂于確定的向量，則就是方程組的解。此時稱簡單迭代法，關(guān)于初始向量收斂。設(shè)要求解的線性方程組為，其中為非奇異矩陣，為向量。若，與k無關(guān)，即,k=0,1,…，稱為單步定常線性迭代法，或者叫簡單迭代法。③

變形為的方式不唯一。④當(dāng)收斂時,只要充分大，則可用作為的近似值。②同一個簡單迭代法可以關(guān)于某一個收斂，而關(guān)于另外不收斂。對任意，均有.代法關(guān)于初始向量收斂。一般談及收斂，是指①如果對初始向量，，則稱此簡單迭2.簡單迭代法的收斂性迭代矩陣的譜半徑(1)

收斂的充要條件

定理:簡單迭代法，，對任意初始向量都收斂的充要條件是：①是判定收斂的根本法則。（判定較繁）

時，有可能存在某個初始向量使簡單迭代法收斂。（該向量不好找）Remark：(2)收斂的充分條件

證明：僅以為例。設(shè)是n階非奇次線性方程組的解向量， 是其等價形式。記

由k=0,1,…的分量形式則簡單迭代格式關(guān)于任意初始向量和收斂。

若或

定理：設(shè)簡單迭代公式為相減有

由于上式對于i=1,2,…,n都成立，故有

由此遞推可得

因為，所以即Remark：由此定理可以知道，在將方程組作等價變形時，若使矩陣B的元素bij的絕對值盡可能的小，就有可能使簡單迭代法收斂。3.Jacobi迭代法(1)迭代格式設(shè)有n

階方程組

其中系數(shù)矩陣非奇異，且，i=1,2，……，n將上式變形為建立迭代格式上面的迭代式稱為雅可比（Jacobi）迭代格式。用矩陣形式來表示方程組的迭代格式

設(shè)det(A)，且雅可比迭代式成為：則令則得記A=D+L+U

(2)Jacobi迭代法的收斂條件b.充分條件：

（j=1,2,…,n）(按列)（按行）,（i=1,2,…,n）（II）設(shè)系數(shù)矩陣

嚴(yán)格對角占優(yōu)，或則Jacobi迭代法關(guān)于任意初始向量收斂。（I）若則Jacobi方法關(guān)于任意初始向量都收斂。即

a.充要條件：Jacobi方法關(guān)于任意初始向量都收斂的充要條件是證明參見教材二、Seidel迭代法將B分解為

設(shè)有簡單迭代法

,k=0,1,…則將其修改為

k=0，1，…i=1,2,……，n上式稱為由簡單迭代法導(dǎo)出的Seidel迭代法。它的分量形式為1.迭代格式與簡單迭代法相應(yīng)的Seidel迭代可化為故Seidel迭代的迭代矩陣為：2.Seidel迭代法的收斂條件(1)Seidel迭代收斂的充要條件(2)迭代收斂的充分條件

若或，

，則Seidel迭代法關(guān)于任意的初始向量收斂。證明（了解）的分量形式相減有

記

證明：

由k=0,1,…僅以為例。有

上式對i=1,2,……，n都成立，故有

使

有即注意：

即所以。當(dāng)k

則即當(dāng)k

時，則即Remark：當(dāng)或時，簡單迭代法與相應(yīng)的Seidel迭代法同時關(guān)于任意初始向量收斂。證畢3.與Jacobi方法對應(yīng)的Seidel迭代格式（1）迭代格式其迭代式為

矩陣形式為因,故存在，于是Seidel迭代式為稱為Gauss-Seidel迭代法的迭代矩陣。則得令Remark1:今后若無特殊說明，凡談到Gauss-Seidel迭代法（簡稱G-S迭代法），均指與Jacobi迭代法相應(yīng)的Seidel迭代法。Remark2:并不是任何時候Gauss-Seidel迭代法都比Jacobi迭代法收斂快。甚至也有Jacobi法收斂而Gauss-Seidel迭代法不收斂的例子。

（2）收斂條件a.充要條件：收斂的充要條件是：G-S法關(guān)于任意初始向量都

b.充分條件：①若則G-S方法關(guān)于任意初始向量都收斂。關(guān)于任意初始向量收斂。②設(shè)系數(shù)矩陣嚴(yán)格對角占優(yōu)，則G-S方法

三、逐次超松弛迭代法（SOR法-SuccessiveOverRelaxation）1.迭代公式將G-S迭代格式改寫為：

并記

一般地，殘量(余量)

。這就是逐次超松馳迭代法（SOR方法