8線性方程組的迭代解法

1、1.8線性方程組的迭代解法線性方程組的迭代解法在階數(shù)較大、系數(shù)陣為稀疏陣的情況下，可以采用迭代法求解線性方程組。用迭代法迭代法(IterativeMethod)求解線性方程組的優(yōu)點(diǎn)是方法簡單，便于編制計(jì)算機(jī)程序，但必須選取合適的迭代格式及初始向量，以使迭代過程盡快地收斂。迭代法根據(jù)迭代格式的不同分成雅可比可比(Jacobi)迭代、高斯高斯塞德爾塞德爾(GaussSeidel)迭代和松弛松弛(Relaxation)法等幾種。在本節(jié)中，我們

2、假設(shè)系數(shù)矩陣A的主對角線元素，且按行嚴(yán)格對角占優(yōu)對角占優(yōu)(DiagonalDonimant)，0?iia即：)...21(1niaanjijijii?????1.1雅可比迭代雅可比迭代1.1.1雅可比迭代及其串行算法雅可比迭代及其串行算法雅可比迭代的原理是：對于求解n階線性方程組Ax=b，將原方程組的每一個(gè)方程ai1x1ai2x2…ainxn=bi改寫為未知向量x的分量的形式：)1()(1niaxabxiinijjjijii??????

3、?然后使用第k1步所計(jì)算的變量xi(k1)來計(jì)算第k步的xi(k)的值：)1()(1)1()(nkiaxabxiinijjkijikji????????這里，xi(k)為第k次迭代得到的近似解向量x(k)=(x1(k)x2(k)…xn(k))T的第i個(gè)分量。取適當(dāng)初始解向量x(0)代入上述迭代格式中，可得到x(1)，再由x(1)得到x(2)，依次迭代下去得到近似解向量序列x(k)。若原方程組的系數(shù)矩陣按行嚴(yán)格對角占優(yōu)，則x(k)收斂于原

4、方程組的解x。實(shí)際計(jì)算中，一般認(rèn)為，當(dāng)相鄰兩次的迭代值xi(k1)與xi(k)i=(12…n)很接近時(shí)，xi(k1)與準(zhǔn)確解x中的分量xi也很接近。因此，一般用判斷迭代是否(k)i)(kixx1ni1max???收斂。如果取一次乘法和加法運(yùn)算時(shí)間或一次比較運(yùn)算時(shí)間為一個(gè)單位時(shí)間，則下述雅可比迭代算法20.1的一輪計(jì)算時(shí)間為n2n=O(n2)。算法算法20.1單處理器上求解線性方程組雅可比迭代算法單處理器上求解線性方程組雅可比迭代算法輸入

5、：輸入：系數(shù)矩陣Ann，常數(shù)向量bn1，ε，初始解向量xn1輸出：輸出：解向量xn1Begin(1)fi=1tondoendifendf(1.3)x1[i]=(b[i]sum)a[imy_rankmi]endf(2)求出本處理器計(jì)算的x的相應(yīng)的分量的新值與原值的差的最大值localmaxlocalmax=│x1[0]x[0]│(3)fi=1tom1doif(│x1[i]x[i]│localmax)thenlocalmax=│x1[i]x

6、[i]│endifendf(4)用Allgather操作將x的所有分量的新值廣播到所有處理器中(5)用Allreduce操作求出所有處理器中l(wèi)ocalmax值的最大值max并廣播到所有處理器中endwhileEnd若取一次乘法和加法運(yùn)算時(shí)間或一次比較運(yùn)算時(shí)間為一個(gè)單位時(shí)間，則一輪迭代的計(jì)算時(shí)間為mnm；另外，各處理器在迭代中做一次歸約操作，通信量為1，一次擴(kuò)展收集操作，通信量為m，需要的通信時(shí)間為，因此算法20.2的一輪)1()1()1

7、(4????ptmptws并行計(jì)算時(shí)間為。mmnptmptTwsp???????)1()1()1(4MPI源程序請參見所附光盤。1.2高斯高斯塞德爾迭代塞德爾迭代1.2.1高斯高斯塞德爾迭代及其串行算法塞德爾迭代及其串行算法高斯塞德爾迭代的基本思想與雅可比迭代相似。它們的區(qū)別在于，在雅可比迭代中，每次迭代時(shí)只用到前一次的迭代值，而在高斯塞德爾迭代中，每次迭代時(shí)充分利用最新的迭代值。一旦一個(gè)分量的新值被求出，就立即用于后續(xù)分量的迭代計(jì)算，

8、而不必等到所有分量的新值被求出以后。設(shè)方程組Ax=b的第i個(gè)方程為：=??nj1ijajxib)21(ni??高斯塞德爾迭代公式為：)(11)(11)1()1(???????????nijkjijijkjijiiikixaxabax)21(ni??取適當(dāng)?shù)膞(0)作為初始向量，由上述迭代格式可得出近似解向量x(k)。若原方程組的系數(shù)矩陣是按行嚴(yán)格對角占優(yōu)的，則x(k)收斂于方程組的解x，若取一次乘法和加法運(yùn)算時(shí)間或一次比較運(yùn)算時(shí)間為一個(gè)