雅克比高斯賽德爾迭代法

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