線性方程組的定常迭代法簡(jiǎn)析——by? Tangwei

? ? ? ?在采用有限元或有限體積進(jìn)行力學(xué)的數(shù)值計(jì)算時(shí)，會(huì)涉及到大型的線性方程組，因?yàn)槲覀儗⒈热缌黧w離散為一個(gè)個(gè)小的有限體積，通過(guò)這種離散的方式把大自然中原本連續(xù)的物質(zhì)給分割成一小塊一小塊，進(jìn)而可以利用計(jì)算機(jī)進(jìn)行計(jì)算，避免了對(duì)現(xiàn)實(shí)世界中物體的解析解有時(shí)求解太過(guò)復(fù)雜，甚至解不出來(lái)。

? ? ? ?那么在計(jì)算離散值時(shí)，會(huì)涉及到大量的數(shù)據(jù)，因?yàn)槟Ｐ蜁?huì)被分割成成千上萬(wàn)、甚至百萬(wàn)千萬(wàn)個(gè)元素。它們將組成一套線性方程組通過(guò)計(jì)算機(jī)來(lái)進(jìn)行計(jì)算。我們將現(xiàn)實(shí)中的數(shù)據(jù)抽象成一個(gè)線性方程組，如下：

A=（）∈R^(n×n)是非奇異矩陣，x∈R^n是n維向量，b∈R^n是n維向量。若b不全為0向量時(shí)，這是一個(gè)典型的非齊次方組。

? ? ? ?那么當(dāng)未知數(shù)的系數(shù)矩陣A是低階稠密矩陣的時(shí)候（n比較?。覀兛梢杂肔U分解、高斯消元法等，一個(gè)一個(gè)去算把它解出來(lái)。但是當(dāng)A是大型的稀疏矩陣的時(shí)候，就是說(shuō)n很大，而0比較多的時(shí)候，一個(gè)個(gè)地去求解就不現(xiàn)實(shí)了，這就要用迭代法去求解。

? ? ? ?我們把含矩陣A的（1）式變化成

的形式，這種方式是怎么得到的呢，B和f?又是啥東西？來(lái)看：

? ? ? ?將A分裂成

M是供你選擇的一個(gè)非奇異矩陣，而且對(duì)于Mx=d這種形式的方程組是容易求解的（這個(gè)d只是一種形式，就是說(shuō)式子容易求解就行），我們就把M叫做分裂矩陣。那么這個(gè)時(shí)候

所以上面我們講到的B和f?是啥東東，就是這個(gè)：

? ? ? ?所以我們叫B為迭代法的迭代矩陣。那么不同的M選取，就產(chǎn)生了不同的迭代矩陣，導(dǎo)致迭代方法也不一樣。以后會(huì)講到具體的迭代方法：雅克比迭代、高斯-賽德?tīng)柕椭鸫纬沙诘鶶OR。本次僅對(duì)基礎(chǔ)概念進(jìn)行初步分析。

好了，話(huà)又回來(lái)了，變成x=Bx+f干嘛？

? ? ? 干嘛？擎好了您嘞！我們?cè)谟糜?jì)算機(jī)算的時(shí)候，計(jì)算機(jī)用的都是一個(gè)個(gè)離散的數(shù)據(jù)，它也不會(huì)像我們?nèi)四菢佑兴枷氲厝ニ伎荚趺唇忸}，只能根據(jù)代碼的指令去機(jī)械的計(jì)算。那怎么辦，用迭代法，這種體力活計(jì)算機(jī)最適合。

? ? ? ? 我們先給定方程組x=Bx+f的解，設(shè)為唯一的解x*，那么

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?x*=Bx*+f? ? ? ? ? ?（6）

這個(gè)“=”是兩邊相等時(shí)的等號(hào)，因?yàn)?b>x*是真解.

? ? ? ? 我們先給定x一個(gè)初始向量，通常為x^(0)=(0,0…,0)^T，x的上標(biāo)(0)是迭代的初始值，帶入到方程組x=Bx+f就解得一個(gè)x^(1)解向量。這樣就得到：

k表示迭代的次數(shù)

注意到，這里不管迭代多少次，B和f?始終不變的。

? ? ? ?那么問(wèn)題來(lái)了，這樣迭代下去，x^(k)會(huì)向真值x*靠攏，而收斂于它嗎？這個(gè)問(wèn)題的答案是：不一定！

我們把

這個(gè)極限若存在，就稱(chēng)此迭代法收斂，收斂的值就是x*，否則就是發(fā)散。

? ? ? ? 那么進(jìn)一步地，就要研究{ x^(k)}的收斂性了，我們這是要引出一個(gè)量：誤差向量。

它的意思就是第k+1步時(shí)，x向量與真值向量的差值。

由（9）式減去（6）式，得到

? ? ? 我們要確定{ x^(k)}是否收斂，B滿(mǎn)足什么樣的條件，可以使得

也就是需要：

? ? ? ?上面我們講到，B滿(mǎn)足（13）式時(shí)迭代收斂，那么什么樣的條件下能得出這樣的B矩陣，以及有這樣的B矩陣會(huì)得到什么樣的結(jié)果？（3）式講到把矩陣A分裂為A=M-N的形式，就得到（2）式來(lái)求解線性方程組。這樣一來(lái)我們就可以構(gòu)造一個(gè)一階定常的迭代法了：

? ? ? ?下面我們有這樣幾個(gè)結(jié)論（定理）：

結(jié)論（1）：對(duì)于任意選取的初始向量x^(0),迭代方程組（14）收斂的充要條件為矩陣B的譜半徑:

在給出其證明之前，我們先給出另外幾個(gè)結(jié)論，

結(jié)論（2）：

結(jié)論（3）：

對(duì)于矩陣序列,

結(jié)論（4）：

下面我們稍證明一下結(jié)論（1）：

? ? ? ?1）先證明收斂的充分性。

已知譜半徑，由（2）式得到(I-B)x=f，即Ax=f，

∴?I-B為非奇異矩陣，因此(I-B)x=f，即Ax=f有唯一解，設(shè)為x*，得到：

那么誤差向量

由(B)<1可知，根據(jù)上述結(jié)論（2）得出

那么對(duì)于任意的x^(0),

? ? ? ?2）證明必要性

已知迭代法（14）收斂，所以可以設(shè)對(duì)任意x^(0)都有：

所以x*是方程組的解，并且對(duì)任意x^(0)都有：

那么對(duì)于任意的x^(0)其實(shí)就是任意的^(0)，都有上式成立，那么根據(jù)結(jié)論（3）可知：

再由結(jié)論（2）知道：

? ? ? ?以上結(jié)論（1）給出了線性方程組迭代法的收斂性的充要條件以及證明，那么不同的B，雖然都收斂，但是收斂的速度卻是不一樣的，對(duì)于計(jì)算機(jī)計(jì)算來(lái)說(shuō)，收斂的快，就可以在較短的時(shí)間步得到結(jié)果，也節(jié)省計(jì)算資源。

? ? ? ? 我們來(lái)看迭代法的收斂速度：

假設(shè)（14）是收斂的，那么

得到：

根據(jù)算子范數(shù)的定義：

? ? ? 我們來(lái)看一下平均每次迭代后的誤差向量的壓縮率：

令第一次迭代，前后步向量誤差的比率：

那么第二次為：

直至第k次為：

令P為平均壓縮率，將，，…，相乘：

這里的每個(gè)P1，...Pk，不是把每個(gè)項(xiàng)的分子分母相消得到總的壓縮率的，這里因?yàn)槿ax，所以不能相消，此處只是為了展示平均壓縮率的數(shù)值得到的路徑。平均值P的k次方就是等于每個(gè)壓縮率的總積，進(jìn)而等于總壓縮率的，從而得到了下面（15）式。

所以平均每次迭代的壓縮率P為：

我們希望迭代k次后，誤差向量^(k)小于初始誤差向量的倍，即

根據(jù)算子范數(shù)和上式，就可以得到：

其中設(shè)σ<<1,我們可以用10的冪來(lái)表示，比較容易理解，取=10^(-s).

又因?yàn)榫仃嘊的譜半徑(B)<1,所以根據(jù)上述結(jié)論（2）得：

由此可以看出，迭代次數(shù)k與如下參數(shù)：

有關(guān)。分母就可以看成是迭代速度，在s一定的情況下，k取決于分母的迭代速度。

? ? ? ? 我們?cè)賮?lái)看看兩個(gè)收斂速度：平均收斂速度和漸進(jìn)收斂速度。

? ? ? ?平均收斂速度的定義為：

因?yàn)檫@個(gè)收斂速度和k及范數(shù)有關(guān)，為了方便計(jì)算和分析，我們把(B)進(jìn)行變換，有結(jié)論（4）可知

而對(duì)數(shù)是連續(xù)函數(shù)，所以

它的意思就是在迭代次數(shù)趨向于∞時(shí)的迭代速度，這樣就與k無(wú)關(guān)了。

? ? ? ?漸進(jìn)收斂速度的定義為：

? ? ? ?這個(gè)收斂速度就與k及范數(shù)無(wú)關(guān)了，它反應(yīng)的是迭代次數(shù)趨向于∞時(shí)迭代法的漸進(jìn)性質(zhì)的速度。由（18）式可知，當(dāng)矩陣B的譜半徑(B)越小時(shí)R(B)越大，收斂的就越快。此時(shí)我們可以用（19）式來(lái)估計(jì)所需的迭代次數(shù)：

? ? ? ?所以，在s選定后，k的次數(shù)，也就是收斂的快慢由漸進(jìn)收斂速度確定，即由B的譜半徑?jīng)Q定，那么選取什么樣的B對(duì)迭代的收斂速度來(lái)說(shuō)，就是一個(gè)很重要的問(wèn)題了。