數值分析中的迭代法解線性方程組

摘 要:對于實際生活中的不少問題來說，一個十分重要的解決方案就是求解線性方程組，求解線性方程組的方法有很多，最為重要的就是數值分析中的迭代法。本文將主要介紹一種全新的求解線性方程組的迭代方法。

關鍵詞:數值分析 迭代法 線性方程組

中圖分類號:O241文獻標識碼:A文章編號:1673-9795(2011)07(b)-0112-01

現實生活中許多數學模型都可以歸結為解線性方程組，線性方程組的解法有很多種，其中數值分析中迭代法是比較重要的一種。本文利用系數矩陣A的對角線上元素的和給出了線性方程組Ax=b的一種新的迭代格式。

1 數值分析中的迭代法解線性方程組的理論

1.1 迭代法概述

迭代法是指在數值分析的過程中，從一個初始估計出發尋求一系列的近似解，已達到解決問題的目的的一個過程，而為了實現這個過程，所運用的方法就是迭代法。在數值分析中，與迭代法相對應的就是一次解法，也有人將之稱為直接法。如果有可能，運用一次解法會相對簡單，而且得出的結果比較的準確，但是，一次解法并不是什么時候都能夠使用的，我們在對一系列的復雜問題求解的時候，一般都沒有辦法直接求解，而需要通過迭代法對方程或者方程組求近似解。

在我們通常的數值分析過程中，較為常用的迭代法是牛頓迭代法，除此之外，還可以根據具體的情況運用諸如線性規劃、最速下降、斜率投影等方法對復雜方程求解。這種那個應用常常在工程技術、自然科學和社會科學中發現，可以解決許多問題最終都可歸結為解線性方程組，因此，線性方程組的求解對于解決實際問題是極其重要的。線性方程組的解法有很多種，其中數值分析中的迭代法是比較重要的一種。

1.2 迭代法求解的基本步驟

我們在利用迭代算法解線性方程的時候，一般需要從如下三個方面著手。

(1)確定迭代變量。

在我們運用迭代算法解線性方程時，至少要確定一個變量，即迭代變量，通過這個變量我們可以直接或間接地不斷由舊值遞推出新值。

迭代法的基本思想是將線性方程組:

Ax=b(其中A∈R，b∈R)

經過變換構造出一個等價同解方程組:x=Mx+c，然后改寫成Jacobi迭代式:

x=Mx+c(k=0，1，2，…)

(2)建立迭代關系式。

在確定了迭代變量之后，需要建立起迭代關系是，通過該關系式直接或間接地不斷由舊值遞推出新值。而所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式。它的建立是解決迭代問題的關鍵，在實踐中，該關系式的確立一般可以采用遞推或倒推的方法來完成。

(3)對迭代過程進行控制。

如果不對迭代的過程進行控制，那么按照迭代關系式，則永遠能夠從變量的前一個值推出下一個值來，這個過程會永無休止的繼續下去。因此，在這種情況下，需要對迭代過程進行控制，確保在得出了自己需要的數值之后，可以結束迭代過程。

2 迭代法解線性方程組的實踐

在現實生活當中，經常會遇到自然以及社會科學領域中的諸多問題，這些問題中所包含的數學模型都可以與一定的線性方程組所對應起來，換句話說，求解線性方程組的過程就是就是解決實際遇到的自然及社會科學問題的過程，線性方程組的求解的重要性可見一斑。然而，對于線性方程組來說，求解的方法不止一種，其中最為重要的一種就是數值分析中的迭代法。

數值分析中的迭代法的基本思路是:對線性方程組進行結構變換，從新組建一個等價的同解方程組，并對其進行迭代式的改寫，用公式進行解釋就是:

線性方程組:Ax=b(其中A∈R，b∈R)，(1)變換之后的等價方程組:x=Mx+c，對其進行迭代式改寫，得到Jacobi迭代式:x=Mx+c(k=0，1，2，…);(2)或Gauss-Seidel迭代式:x=Bx+Bx+c(k=0，1，2，…)(其中B+B=M)。

將x=(x，x，…，x)指定為初始向量，并利用迭代式構建出一個{x}(k=0，1，2，…)序列，當利用迭代式所構建出的數列是收斂的，那么此方程組的近似解序列就是數列{x}(k=0，1，2，…);但如果該數列不是收斂的，那么就意味著利用迭代法所組建起的數列不具有任何實用性。筆者選定方程組Ax=b，并且該方程組的系數特性是對稱正定矩陣，并在屬于系數矩陣A對角線的各個元素之和的基礎上，為方程組提供一種全新的迭代格式。當系數矩陣A是具備可逆特性的非正定矩陣時，對其進行預處理，將原本的非正定矩陣變換成正定矩陣，與此同時，還要對計算速度進行全面衡量。

2.1 收斂定理及證明

2.1.1 引理

假定M是一個n×n矩陣，對任意的n維向量c迭代格式(2)收斂的充分必要條件是ρ(M)<1，其中ρ(M)為M譜半徑。

2.1.2 定理1

若阿α為對稱正定n×n矩陣，則線形方程組αx=b的迭代格式x=[I-α]x+(3)是收斂的。在迭代格式(3)中可以通過引入一個特定的因子改進收斂速度。

構造迭代格式:

{y=[I-α]x+b(4)

或者與(4)等價的迭代格式:

x=[I-α]x+b(5)

2.1.3 定理2

若α為對稱正定n×n矩陣，則線性方程組αx=b的迭代格式(5)是收斂的。

證明:假設λ(i=1，2，…，n)是α的n個特征值，α是對稱正定矩陣，λ>0(i=1，2，…，n)，λ+λ+…+λ=a+a+…+a。

得出I-α的n個特征值為1-(i=1，2，…，n)，很明顯-1<1-<1(i=1，2，…，n)，在這種情況下ρ[I-α]<1，由引理可以得知迭代格式(5)是收斂的。

2.1.4 定理3

迭代格式(7)收斂的充分必要條件是:

<，i=1，2，…，n(8)

證明:(7)收斂的充分必要條件是其I-α的譜半徑小于1，而譜半徑小于1的充分必要條件是<2，即<，i=1，2，…，n。

2.1.5 推論1

迭代格式(7)收斂的充分條件是λ≤2λ。

證:因為λ≤2λ，所以得到:<，i=1，2，…，n，

即迭代格式(7)是收斂的。

3 結果

一般的，在矩陣的特征值分布較為均衡，并且比較集中的時候，通過采用迭代格式(7)的對應算法Gauss_seidel迭代算法以及Cholesky分解算法對有關的矩陣進行計算，該矩陣的階數J=100，200，500，1000，對其4個線性方程組進行計算，最后計算所耗的時間。我們發現，一般而言，還是迭代格式(7)所耗的時間少。雖然Gauss-seidel算法以及Cholesky分解算法的迭代次數相對而言較少，但是，由于它們在求逆的過程中浪費了大量的時間，迭代格式(7)的算法就比較占優勢了。

參考文獻

[1]袁媛，楊建偉.求解非線性方程重根的二階迭代法[J].南京信息工程大學學報(自然科學版)，2010(1).

[2]欒世超，王云誠.求解非線性方程的一個全局收斂算法[J].魯東大學學報(自然科學版)，2010(1).

[3]倪健，馬昌鳳.解非線性方程牛頓迭代法的一種新的加速技巧[J].廣西科學院學報，2010(1).