求解線性方程組的迭代解法.ppt

第四章,線性方程組 迭代解法,第四章目錄,1 向量序列與矩陣序列的極限 2 Jacobi迭代法 3 GaussSeidel迭代法 4 松馳法 5 迭代法的收斂條件及誤差估計 5.1 矩陣的譜半徑 5.2 迭代法的收斂條件 5.3 誤差估計 6 非線性方程組迭代法 6.1 Newton法 6.2 最速下降法,第四章 方程組的迭代解法概述,這一章討論線性方程組的另一類解法迭代法，由于迭代法能充分避免系數(shù)矩陣中零元的存貯與計算，因此特別適用于求解系數(shù)矩陣階數(shù)很高而零元素又很多（即大型稀疏）的線性方程組。 解線性方程組的迭代法的基本思想與解方程的迭代法相似，首先將方程組Ax = b化為等價方程組x = Mx + g，其中M為n 階方陣，b = (b1,b2,bn)T，g Rn，任取初始向量x(0) Rn，代入迭代公式：,迭代解法概述(續(xù)）,產(chǎn)生向量序列x(k)，若此序列收斂于x*，則有x* = Mx*+g，即x*為原方程組的解。因此，可根據(jù)精度要求選擇一個合適的x(k)（k充分大時）作為近似解，這就是解線性方程組的迭代法， 上式稱為迭代格式，M 稱為迭代矩陣，若序列x(k)極限存在，稱此迭代過程收斂，否則稱為發(fā)散。,1 向量序列與矩陣序列的極限,與求解方程類似，需要討論的問題是：如何建 立迭代公式，向量序列的收斂條件是什么，若向量 序列x(k)收斂，如何進(jìn)行誤差估計？,1 向量序列與矩陣序列的極限,由于Rn中的向量可與Rn的點建立一一對應(yīng)關(guān)系， 因此由點列的收斂概念及向量范數(shù)的等價性，可得 到向量序列的收斂概念。,定義1,向量序列與矩陣序列的極限（續(xù)）,n維點列收斂的一種等價描述是其對應(yīng)坐標(biāo)序列均 收斂，向量序列也有類似的結(jié)論。,定理1,矩陣序列的收斂概念及定理,定義2,完全類似地，可以定義矩陣序列的收斂：,與向量序列類似，也有：,定理2,2 雅可比（Jacobi）迭代法,設(shè)有n階線性方程組：,簡記為：,其系數(shù)矩陣A非奇異，不妨設(shè)aii 0 (1,2,n)可將上式 改寫為等價方程組：,雅可比（Jacobi）迭代法（續(xù)）,也可寫作為：,可簡記為：,由此可建立迭代格式：,Jacobi迭代法定義,選取初始向量x(0)代入（4-4）右端，可得x(1) = Bx(0) + g， 再將x (1)代入（4-4）右端，可得x(2) = Bx(1) + g，如此繼續(xù)下去， 就產(chǎn)生一個向量序列x(k)，按（4-2）或（4-3）格式迭代求解 的方法稱為雅可比（Jacobi）迭代法，又叫簡單迭代法。 迭代式（3-4）中的B 稱為迭代矩陣，它可直接由（4-2） 或（4-3）得到，也可用系數(shù)矩陣A來表示：,若將系數(shù)矩陣A分解為A = DLU，其中：,Jacobi迭代法定義（續(xù)）,式（4-5）為簡單迭代法的矩陣形式。,Jacobi迭代法舉例,用Jacobi迭代法求解線性方程組：,例1,解：由第一個方程解x1，第二個方程解x2，第三 個方程解x3得Joacbi迭代格式為：,繼續(xù)迭代下去，迭代結(jié)果見表4-1：,取x(0) = (0,0,0)T代入迭代式 （4-6）或（4-7）得：,Jacobi迭代法舉例,迭代9次，得近似解x(9) = (10.9994,11.9994,12,9992)T，此方程組的準(zhǔn)確解為x =(11,12,13)T，從表4-1可以看出，隨著迭代次數(shù)的增加，迭代結(jié)果越來越接近精確解。,3 高斯塞德爾(Gauss-Seidel)迭代法,Jacobi迭代法的優(yōu)點是公式簡單，迭代矩陣容易得到， 它又稱為同時替換法：在每一步迭代計算過程中，計算 x(k+1)時是用x(k)的全部分量代入求x (k+1)的全部分量。因此 需同時保留兩個近似解向量x(k)和x(k+1)。,高斯塞德爾(Gauss-Seidel)迭代法續(xù)1,Gauss-Seidel迭代法求解,例2 用Gauss-Seidel迭代法求解例1,解：Gauss-Seidel迭代格式為：,仍取x (0) = (0,0,0)T， 計算結(jié)果見下表：,顯然，用Gauss-Seidel 迭代法比Jacobi迭代法收斂快，這個結(jié)論 在多數(shù)情況下是成立的，但也有Gauss-Seidel迭代比Jacuobi迭代收 斂慢，甚至還有Jacobi迭代收斂，Gauss-Seidel迭代發(fā)散的情形。,求例2中的Gauss-Seidel法的迭代陣M的兩種方法,求例2中的Gauss-Seidel法的迭代陣M的兩種方法續(xù)1,方法2：可按代入法求M，以避免計算逆矩陣，在Gauss- Seidel迭代式（4-10）中，第 二個式子中的以第一個式子 代替?？蓪⒌诙接叶松蠘?biāo)都化為k（可以不管常數(shù)）：,求例2中的Gauss-Seidel法的迭代陣M的兩種方法續(xù)2,由于（4-10）第一式及（4-11）， （4-12）的右端上標(biāo)均為k ，即 為同時替換迭代式，類似于 Jacobi迭代法可直接由它們得 迭代陣為：,4 松馳法,通過引入?yún)?shù)，在Gauss-Seidel法的基礎(chǔ)上作適當(dāng)修改， 在不增加過多的計算量的條件下，可得到一種新的，收斂 更快的迭代法。 將Gauss-Seidel迭代格式（4-9）改寫為：,松馳法（續(xù)）,通過選擇適當(dāng)?shù)膮?shù)使此迭代格式收斂更快。 稱為松馳因子，1時稱 為超松馳法， = 1是Gauss-Seidel迭代，簡稱為 SOR法（Successive Over-Relaxation）。,SOR法的迭代矩陣,將（4-13） 代入（4-14） 可得：,其矩陣 形式為：,所以SOR法的迭代矩陣為：,用SOR法解線性方程組（例3）,例3 取 =1.4,x (0) = (1,1,1)T， 用SOR法解線性方程組,例 3 （續(xù)1）,繼續(xù)下去，計算結(jié)果如下：,例 3 （續(xù)2）,所以，方程組近似解為:,松馳因子的選取對收斂速度影響極大，如何選取使收斂速度加快，或達(dá)到最快？這是非常重要的，但又很困難，目前尚無可供實用的計算最佳松馳因子的辦法，通常的作法是采用試算法：即從同一初值出發(fā)，選不同的松馳因子進(jìn)行試算，迭代相同的次數(shù)，來比較殘量r (k) = b Ax(k) 的大小，選取使r(k) 最?。ǜ鞣至靠傮w相差最?。┑乃神Y因子。這樣做較簡單，但比較有效。,小結(jié)如下：,5 迭代法的收斂條件及誤差估計,5.1 矩陣的譜半徑,迭代法的收斂性與迭代矩陣的特征值有關(guān)：,設(shè)A為n階方陣，i (i = 1,2,，n)為A的特征值， 稱特征值模的最大值為矩陣A的譜半徑，記為：,定義3,矩陣的譜半徑（續(xù)）,矩陣的譜半徑與范數(shù)之間有如下關(guān)系： 設(shè)x為對應(yīng)于特征值的A的特征向量，則由：,這個不等式對A的任何范數(shù)、任意特征值都成立， 因此，可得矩陣A的譜半徑與A的范數(shù)之間的一個重要 關(guān)系：A的譜半徑不超過A的任一種范數(shù)。即：,公式 的重要性說明,它之所以重要是因為：(A)難計算，而|A|、 |A|1 計算容易，并且對于任意正數(shù) ，存在一種矩陣范數(shù) 很接近(A)，使得成立：,對任意n 階方陣A，一般不存在矩陣范數(shù)使 (A) =|A| ，但若A為對稱矩陣，則有：,下面的結(jié)論對建立迭代法的收斂條件十分重要 ：,定理3,定理3（續(xù)）,證明：,5.2 迭代法的收斂條件,證明：,定理4,由5.1 的結(jié)果，可以得到如下收斂定理 ：,迭代法的收斂條件（續(xù)1）,推論1,迭代法的收斂條件（續(xù)2）,定理4表明，迭代法收斂與否只決定于迭代矩陣 的譜半徑，與初始向量及方程組的右端項無關(guān)。 對同一方程組，由于不同的迭代法其迭代矩陣不同，因此可能出現(xiàn)有的方法收斂，有的方法發(fā)散的情形。,兩種迭代法舉例,例4,討論Jacobi迭代法與Gauss-Seidel迭代法的收斂性。,解：首先要求出迭代矩陣，然后利用推論1（充分條件）及定理4（充分必要條件）進(jìn)行討論。,對Jacobi迭代法：,例4（ Jacobi迭代法續(xù)）,例4（ G-S迭代法續(xù)）,對G-S迭代法：,兩種迭代法說明,注1：對G-S法，為避免求逆陣可按下面兩個方法：,兩種迭代法說明（續(xù)）,注2：例4也說明0 2確實只是松馳法的必要條件， 而非充分條件，因為G-S法即為 = 1的情形。,定理4雖然給出了判別迭代法收斂的充要條件，但實際 使用時很不方便，因為求逆矩陣和特征值的難度并不亞于 用直接法求解線性方程組。而推論1僅為充分條件。很多 情況下如例3，由推論1無法判別收斂性。下面對一些特殊 的方程組，從方程組本身出發(fā)給出幾個常用的判別條件， 而不必求迭代陣的特征值或范數(shù)。,直接用矩陣A判定斂散性,定義4,直接用矩陣A判定斂散性（續(xù)）,為嚴(yán)格對角占優(yōu)陣，Jacobi迭代法與 G-S迭代法均收斂。,又如例3中，系數(shù)矩陣：,為非嚴(yán)格對角占優(yōu)，但A 為對稱正定矩陣，且 = 1.4 松馳法收斂。,如例1中，線性方程組的系數(shù)矩陣：,設(shè)有線性方程組Ax= b，下列結(jié)論成立： 1. 若A為嚴(yán)格對角占優(yōu)陣，則Jacobi迭代法與G-S法均收斂； 2. 若A為嚴(yán)格對角占優(yōu)陣，0 1，則松馳法收斂； 3. 若A為對稱正定矩陣， 0 2，則松馳法收斂； 若A為對稱正定陣，松馳法收斂 0 2。,三種迭代法判定斂散性舉例,解：可以總結(jié)，討論迭代法的收斂性，應(yīng)首先從A出發(fā)討 論其是否具有主對角占優(yōu)或?qū)ΨQ正定性；其次對迭代法的 迭代陣討論其是否有范數(shù)小于1；最后利用迭代陣的譜 半徑討論（這是充分必要條件）。,例5,例 5 (續(xù)）,對Jacobi迭代法，其迭代陣容易由A直接得到：,例6,解,Jacobi迭代陣為：,例6,G-S迭代陣為：,兩點注釋,兩點注釋（續(xù)）,注2：在利用迭代陣的范數(shù)判定收斂時（推論1），只要 迭代陣的范數(shù)小于1，即可判 定其收斂性，但當(dāng)| |1時 ，則無法判定，還需利用譜半徑作最后判定，并且，由 于不同的范數(shù)其值不同，可能會出現(xiàn)某一種范數(shù)小于1 但很接近于1（收斂）， 這時另一種范數(shù)可能會大于1 （無法判定）的情況，如設(shè)Ax = b，其中（見下）:,5.3 誤差估計,定理5,定理5（續(xù)）,利用定理5 對例1，若給出=104，即要求各分量 的誤差絕對值不超過104，則由于：,式（4-20） 常用于事后估計誤差，即在實際計算時，利用相鄰兩次迭代值之差是否達(dá)到精度要求作為停機(jī)標(biāo)準(zhǔn)。,這表明需要迭代13次才能保證各分量絕對誤差不超過10-4。,迭代改善法,無論是用直接法還是用迭代法求得病態(tài)方程組的計算解,當(dāng)精度不理想時，,可以使用迭代改善的辦法進(jìn)行處理，即,使用迭代改善法,此法常用于解不十分嚴(yán)重病態(tài)的方程組。,迭代改善法：,（2）也可與直接法結(jié)合進(jìn)行直接求解。,（1）可用于改善已求得的近似爭的精度，,1. 對Ax=b 用列主元消元法，分解法均可，分解法（選主元）最好。,即：,具體步驟為：,迭代改善法（續(xù)1）,2. 求x(1)的修正量z(1) ：先求,然后由,即可,的解。,而,就是近似解x(1)的改進(jìn)解.,這是因為有：,3. 可繼續(xù)下去：再求,迭代改善法（續(xù)2）,例1：,與準(zhǔn)確解,若用Gauss消元法求解（取五位有效數(shù)字）,比較，相差太遠(yuǎn)。,迭代改善法（續(xù)3）,若用迭代改善法：,K,迭代改善法（續(xù)4）,例2 Hilbert 陣,較準(zhǔn)確的解為,若用列主元法求得近似解：,對x(1)用迭代改善法進(jìn)行改進(jìn)：先求,迭代改善法（續(xù)5）,用Doolittle分解法求解,x(3)顯然已具有四位有效數(shù)字,可計算,可繼續(xù)求：,并由Dolittle分解法解,可得,6 非線性方程組的解法,非線性方程組的一般形式為：,這一節(jié)討論它的求解方法，主要是迭代解法（因為 除了極為特殊的非線性方程組以外，類似于線性方程組 的直接解法幾乎是不可能的），并且這里介紹的迭代解 法都采用線性化的方法構(gòu)成各種形式的迭代格式，只介 紹方法，不討論收斂性。,其中：xi是實變量，fi 是xi 的非 線性實函數(shù)(i=1，2，n)可 記為x=(x1，x2，xn)T， F(x)=(f1(x)，f2(x)，fn(x)T，上述方程組 又可記為：F(x)=0,非線性方程組的解法（續(xù)）,選取一組初值x1(0)，x2(0)，xn(0)代入迭代 格式，可得向量序列x(k)，并且一般有，若 x(k)收斂，只要gi連續(xù)，則收斂到原方程組的 解（向量形式： x = g(x)，x(k+1) = g(x(k) ）。,一般方法：將上述方程組改寫等價形式：,下面主要介紹Newton法 ，只介紹基本方法。,此式可展為：,6.1 Newton法,按上述過程求F(x) = 0的近似解的方法稱為Newton法 。,Newton法的具體做法,用Newton法具體做時：,每迭代一次，即要解一個線性方程組（即Newton 方程組）,并且每次的系數(shù)矩陣F(x(k)不一樣。 可以證明：Newton法具有二階收斂速度。 控制結(jié)束：對預(yù)先給定的精度：,兩個方程情況下的Newton法,兩個方程的情況，加深理解Newton法：,兩個方程情況下的Newton法舉例,Newton方程組 F(x)在x(0)處取值，F(xiàn) (x)在x(0)取值得：,同單個方程的Nweton法一樣：解非線性方程組的Newton法： 收斂快，形式簡單，格式固定。 但同時也：1. 對初值要求高； 2. 迭代一次，需計算n+n2個函數(shù)值及導(dǎo)數(shù)值； 3. 求解一個n階非線性方程組，計算量較大。,6.2 最速下降法,這一小節(jié)只介紹大概算法，因為要用別的知識較多。,最速下降法（續(xù)）,因此 ，非線性方程組的求解可轉(zhuǎn)化為求解最優(yōu)化問題 （求(x)的最小值） 并且沒有任何約束條件，稱為無條件約束最優(yōu)化問題。,求解此類問題的一種基本方法是最速下降法。 最速下降法的基本思想是： 從最優(yōu)化問題的近似解x(k)出發(fā)，沿使函數(shù)(x)下 降最快的方向，尋找新的近似解x(k+1)