《雅克比高斯賽德爾迭代法》由會員分享,可在線閱讀,更多相關(guān)《雅克比高斯賽德爾迭代法(6頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、第八節(jié) 雅可比迭代法與高斯塞德爾迭代法一 雅可比迭代法設(shè)線性方程組 (1)的系數(shù)矩陣A可逆且主對角元素均不為零,令 并將A分解成 (2)從而(1)可寫成 令 其中. (3)以為迭代矩陣的迭代法(公式) (4)稱為雅可比(Jacobi)迭代法(公式),用向量的分量來表示,(4)為 (5)其中為初始向量.由此看出,雅可比迭代法公式簡單,每迭代一次只需計算一次矩陣和向量的乘法.在電算時需要兩組存儲單元,以存放及.例1 例1 用雅可比迭代法求解下列方程組解 將方程組按雅可比方法寫成取初始值按迭代公式進行迭代,其計算結(jié)果如表1所示 表1 0 1 2 3 4 5 6 700.720.9711.0571.0
2、8531.09511.0983 00.831.0701.15711.18531.19511.1983 00.841.1501.24821.28281.29411.2980 二 高斯塞德爾迭代法由雅可比迭代公式可知,在迭代的每一步計算過程中是用的全部分量來計算的所有分量,顯然在計算第i個分量時,已經(jīng)計算出的最新分量沒有被利用,從直觀上看,最新計算出的分量可能比舊的分量要好些.因此,對這些最新計算出來的第次近似的分量加以利用,就得到所謂解方程組的高斯塞德(Gauss-Seidel)迭代法.把矩陣A分解成 (6) 其中,分別為的主對角元除外的下三角和上三角部分,于是,方程組(1)便可以寫成 即其中
3、(7)以為迭代矩陣構(gòu)成的迭代法(公式) (8)稱為高斯塞德爾迭代法(公式),用 量表示的形式為 (9)由此看出,高斯塞德爾迭代法的一個明顯的優(yōu)點是,在電算時,只需一組存儲單元(計算出后不再使用,所以用沖掉,以便存放近似解.例2 例2 用高斯塞德爾迭代法求解例1.解 取初始值,按迭代公式進行迭代,其計算結(jié)果如下表2 表2 0 1 2 3 4 5 6 700.721.043081.093131.099131.099891.09999 1.100.9021.167191.195721.199471.199931.19999 1.201.16441.282051.297771.299721.29996
4、1.3 1.3從此例看出,高斯塞德爾迭代法比雅可比迭代法收斂快(達到同樣的精度所需迭代次數(shù)少),但這個結(jié)論,在一定條件下才是對的,甚至有這樣的方程組,雅可比方法收斂,而高斯塞德爾迭代法卻是發(fā)散的.三 迭代收斂的充分條件定理1 在下列任一條件下,雅可比迭代法(5)收斂. ; ; 定理2 設(shè)分別為雅可比迭代矩陣與高斯塞德爾迭代矩陣,則 (10)從而,當時,高斯塞德爾迭代法(8)收斂.證明 由的定義,它們可表示成用表示維向量,則有不等式這里,記號表示其中矩陣的元素都取絕對值,而不等式是對相應元素來考慮的,于是容易驗證所以,及可逆,且從而有因此必有因為已知所以.即高斯塞德爾迭代法收斂.若矩陣為對稱,我
5、們有定理3 若矩陣正定,則高斯塞德爾迭代法收斂.證明 把實正定對稱矩陣A分解為 ,則為正定的,迭代矩陣設(shè)是的任一特征值,為相應的特征向量,則以左乘上式兩端,并由有用向量的共軛轉(zhuǎn)置左乘上式兩端,得 (11)求上式左右兩端的共軛轉(zhuǎn)置,得以和分別乘以上二式然后相加,得由,得即 (12)因為A和D都是正定的,且x不是零向量,所以由(11)式得,而由(12)式得, 即,從而,因而高斯塞德爾迭代法收斂.定義1 設(shè)為n階矩陣. 如果 (13)即A的每一行對角元素的絕對值都嚴格大于同行其他元素絕對值之和,則稱A為嚴格對角優(yōu)勢矩陣. 如果且至少有一個不等式嚴格成立,則稱A為弱對角優(yōu)勢矩陣.例如是嚴格對角優(yōu)勢矩陣
6、,是弱對角優(yōu)勢矩陣.定義2 設(shè)是n階矩陣,如果經(jīng)過行的互換及相應列的互換可化為, 即存在n階排列矩陣P,使 其中為方陣,則稱A是可約的,否則稱A為不可約的.是可約矩陣,意味著可經(jīng)過若干次行列重排,化為兩個低階方程組,事實上, 可化為 ,記于是,求解化為求解可以證明,如果A為嚴格對角優(yōu)勢矩陣或為不可約弱對角優(yōu)勢矩陣,則A是非奇異的.定理4 如果A為嚴格對角優(yōu)勢矩陣或為不可約弱對角優(yōu)勢矩陣,則對任意,雅可比迭代法(4)與高斯塞德爾迭代法(8)均為收斂的.證明 下面我們以A為不可約弱對角優(yōu)勢矩陣為例,證明雅可比迭代法收斂,其他證明留給讀者.要證明雅可比迭代法收斂,只要證,是迭代矩陣.用反證法,設(shè)矩陣有某個特征值,使得,則,由于A不可約,且具有弱對角優(yōu)勢,所以存在,且從而 另一方面,矩陣與矩陣A的非零元素的位置是完全相同的,所以也是不可約的,又由于,且A弱對角優(yōu)勢,所以并且至少有一個i使不等號嚴格成立.因此,矩陣弱對角優(yōu)勢,故為不可約弱對角優(yōu)勢矩陣.從而 矛盾,故的特征值不能大于等于1,定理得證.