線性方程組的迭代和最速下降法

劉盎然

（內(nèi)蒙古大學(xué) 數(shù)學(xué)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010010）

線性方程組的迭代和最速下降法

劉盎然

（內(nèi)蒙古大學(xué) 數(shù)學(xué)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010010）

本文在第一部分對(duì)迭代法進(jìn)行了較為詳細(xì)的描述.當(dāng)遇到復(fù)雜問題時(shí)，特別是在未知量很多，方程為非線性時(shí)，我們無法找到直接解法，這時(shí)候或可以通過迭代法尋求方程的近似解.在可以用迭代算法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量.所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）.迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，可以用遞推或倒推的方法來完成.在什么時(shí)候結(jié)束迭代過程，不能讓迭代過程無休止地重復(fù)執(zhí)行下去.迭代過程的控制可分為兩種情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；另一種是所需的迭代次數(shù)無法確定，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件.第二部分是基于最速下降法在解決無約束非線性規(guī)劃問題中的重要性，對(duì)其原理與算法予以討論.

線性方程組；迭代法；最速下降法；最優(yōu)解

1 基本定義與迭代法

1.1 向量序列與矩陣序列的收斂性

定義1.1.1設(shè){x{k}}為Rn中的向量序列，x∈Rn，

其中||x(k)-x||為Rn中的向量范數(shù)，則稱序列{x{k}}收斂于x，記為

其中x(k)=(x1(k),x2(k),…,xn(k)),x=(x1,x2,…xn)

定義1.1.3設(shè){A{k}}為n階方陣序列，A為n階方陣，

其中||A(k)-A||為矩陣范數(shù)，則稱序列{A{k}}收斂于A，記為

1.2 迭代法的一般形式

Ax=b?x=Mx+g其中A，M為n階方陣，x，g∈Rn

迭代公式：xk+1=Mxk+g k=0,1,2，…，M為迭代矩陣，{x(k)}為迭代序列.

結(jié)論：若迭代公式x(k+1)=Mx(k)+g產(chǎn)生的迭代序收斂于x，則必有x=Mx+g，即為方租組Ax=b的解.

1.3 雅可比（Jacobi）迭代法

選取初始向量x(0)，按以上公式產(chǎn)生的迭代序列成為Jacohi迭代（簡單迭代法）Jacobi迭代法的矩陣形式：x(k+1)=Bx(k)+g

1.4 高斯－賽德爾（Gauss－Seidel）迭代法

2 迭代法基本收斂判別

2.1 迭代法收斂性理論

2.1.1 收斂性問題

2.1.2 收斂性基本定理

迭代法收斂性基本定理：設(shè)方程組為x=Bx+f對(duì)任意的初始向量x(0)，解此方程組的迭代法x(k+1)=Bx(k)+f(k=0,1,2,…)收斂的充分必要條件是迭代矩陣B的譜半徑ρ(B)<1

注意：此定理為判斷迭代法的斂散性提供了一個(gè)強(qiáng)有力的手段（充分必要條件）.然而，定理的條件往往不容易驗(yàn)證.因此，利用特征值上界性質(zhì)ρ(B)≤||B||,可以給出另一個(gè)條件較弱的結(jié)果.

迭代法收斂性充分條件：如果迭代法x(k+1)=Bx(k)+f(k=0, 1,2,…)的迭代矩陣B的某一種算子范數(shù)||B||≤1，則

（1）對(duì)任意的初始向量x(0),迭代法收斂；

（2）迭代序列與方程組的解x*存在誤差估計(jì)式

2.2 迭代法的收斂條件

2.2.1 矩陣的譜半徑

定義3.2.1設(shè)A為方陣，λi(i=1,2,…,n)為A的特征值，稱特征值模的最大值為矩陣的譜半徑，記為：

結(jié)論

1、ρ（Ak）=[ρ（A）]k

2、ρ（A）≤||A||,

其中||·||為任意由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)；

3、?ε>0，存在一種矩陣范數(shù)，使得||A||≤ρ（A）+ε，

2.2.2 迭代法的收斂條件定理與結(jié)論

定理 對(duì)任意初始向量x(0)

產(chǎn)生的向量序列{x(k)}收斂的充要條件是：ρ(M)<1

推論1在定理的條件下，若||M||<1，則對(duì)任意初始向量x(0),{x(k)}收斂.

定義1若n階方陣A=(aij）滿足

且至少有一個(gè)i值，使上式不等號(hào)嚴(yán)格成立，則稱A為紡對(duì)角占優(yōu)陣.若對(duì)所有i，上式中不等號(hào)均嚴(yán)格成立，則稱A為嚴(yán)格對(duì)角占優(yōu)陣.不可約矩陣.

其中A11、A22為方陣，則稱矩陣A不可約.

如下列矩陣

結(jié)論：設(shè)A=(aij)為n階矩陣（n≥2），若存在非空集合I?{1,2,…,n}，使得當(dāng)i∈I，而i?I時(shí)，有aij=0，則A是可約陣.

若A沒有零元素，則A不可約.n=3時(shí)，A只有一個(gè)零元素，A不可約.

判別收斂的條件：

若A為嚴(yán)格對(duì)角占優(yōu)陣或不可約弱對(duì)角占優(yōu)陣，則Jacobi迭代法與G-S迭代法收斂.

注：常用條件直接對(duì)系數(shù)矩陣A判別.

1、先觀察系數(shù)矩陣A是否對(duì)稱正定或?qū)钦純?yōu).

2、是否可以通過同解變形使系數(shù)矩陣具有上述特性（例如：交換方程的位置等）

3、給出迭代公式，討論迭代矩陣的譜半徑.

3 最速下降法

3.1 無約束問題的最優(yōu)性條件

無約束問題的最優(yōu)解所要滿足的必要條件和充分條件是我們設(shè)計(jì)算法的依據(jù)，為此我們有以下幾個(gè)定理.

定理4.1設(shè)f：Rn→R1在點(diǎn)∈Rn處可微.若存在p∈Rn，使

定理4.2設(shè)f：Rn→R1在點(diǎn)x*∈Rn處可微.若x*是無約束問題的局部最優(yōu)解，

由數(shù)學(xué)分析中我們已經(jīng)知道，使▽f(x)=0的點(diǎn)x為函數(shù)f的駐點(diǎn)或平穩(wěn)點(diǎn).函數(shù)f的一個(gè)駐點(diǎn)可以是極小點(diǎn)；也可以是極大點(diǎn)；甚至也可能既不是極小點(diǎn)也不是極大點(diǎn)，此時(shí)稱它為函數(shù)f的鞍點(diǎn).以上定理告訴我們，x*是無約束問題的的局部最優(yōu)解的必要條件是：x*是其目標(biāo)函數(shù)f的駐點(diǎn).

定理4.3設(shè)f：Rn→R1在點(diǎn)x*∈Rn處的Hesse矩陣▽2f (x*)存在.若▽f(x*)=0，并且▽2f(x*)正定,則x*是無約束問題的嚴(yán)格局部最優(yōu)解.

一般而言，無約束問題的目標(biāo)函數(shù)的駐點(diǎn)不一定是無約束問題的最優(yōu)解.但對(duì)于其目標(biāo)函數(shù)是凸函數(shù)的無約束凸規(guī)劃，下面定理證明了，它的目標(biāo)函數(shù)的駐點(diǎn)就是它的整體最優(yōu)解.

定理4.4設(shè)f：Rn→R1，x*∈Rn，f是Rn上的可微凸函數(shù).若有

則x*是無約束問題的整體最優(yōu)解.

3.2 最速下降法的基本思想和迭代步驟

最速下降法的基本思想是：從當(dāng)前點(diǎn)xk出發(fā)，取函數(shù)f (x)在點(diǎn)xk處下降最快的方向作為我們的搜索方向pk.由f(x)的Taylor展式知

略去t的高階無窮小項(xiàng)不計(jì)，可見取pk=-▽f(xk)時(shí)，函數(shù)值下降得最多.于是，我們可以構(gòu)造出最速下降法的迭代步驟.

解無約束問題的的最速下降法計(jì)算步驟：

由以上計(jì)算步驟可知，最速下降法迭代終止時(shí)，求得目標(biāo)函數(shù)駐點(diǎn)的一個(gè)近似點(diǎn).

例1 minf(x)=x1-x2+2x12+2x1x2+x22給定初始點(diǎn)X(1)=(0,0)T

3.3 最速下降法的缺點(diǎn)

由于沿負(fù)梯度方向目標(biāo)函數(shù)的最速下降性，很容易使人們誤認(rèn)為負(fù)梯度方向是最理想的搜索方向.必須指出的是，某點(diǎn)的負(fù)梯度方向，通常只是在該點(diǎn)附近才具有這種最速下降的性質(zhì).

在一般情況下，當(dāng)用最速下降法尋找極小點(diǎn)時(shí)，其搜索路徑呈直角鋸齒狀（圖1-3），開始時(shí)目標(biāo)函數(shù)下降較快；但在接近極小點(diǎn)時(shí)，收斂速度就不理想了.特別適當(dāng)目標(biāo)函數(shù)的等值線為比較扁平的橢圓時(shí)，收斂就更慢了.

因此，在實(shí)用中常將最速下降法和其他方法聯(lián)合應(yīng)用.

在接近極小點(diǎn)時(shí)，可改用收斂較快的其他方法.

3.4 最速下降法程序流程圖

接觸最速下降法1847年由著名數(shù)學(xué)家Cauchy給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的.

〔1〕黃明游.數(shù)值分析[M].高等教育出版社，2008.

〔2〕封建湖，車剛明，聶玉峰.數(shù)值分析原理[M].科學(xué)出版社，2005.

〔3〕關(guān)治，陸金甫.數(shù)值分析基礎(chǔ)（第二版）[M].高等教育出版社，2010.

〔4〕Kendall Atkinson，韓謂敏.數(shù)值分析導(dǎo)論（第三版）[M].人民郵電出版社，2009.

〔5〕何漢林，梅家斌.數(shù)值分析[M].科學(xué)出版社，2009.

O241.6

A

1673-260X（2014）01-0010-04