最速下降法與共軛梯度法

《最速下降法與共軛梯度法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、最速下降法與共軛梯度法1.最速下降法當(dāng)方程組????Ax=b(1)中的A為對(duì)稱正定矩陣時(shí)，方程組Ax=b的解正好是二次函數(shù)????(2)的唯一極小值點(diǎn)。求解方程組(1)的問題等價(jià)與求??????(3)問題。求解問題(3)的最簡(jiǎn)單的方法是所謂最速下降法，即從某個(gè)初始點(diǎn)x(0)出發(fā)，沿φ(x)在點(diǎn)x(0)處的負(fù)梯度方向??????(4)(稱為搜索方向)求得φ(x)的極小值點(diǎn)x(1),即??????(5)然后從x(1)出發(fā)，重復(fù)上面的過程得到x(2)。如此下去,得到序列{x(k)}??????(6)可以證明，從任一初

2、始點(diǎn)x(0)出發(fā)，用最速下降法所得到的序列{x(k)}均收斂于問題(3)的解，也就是方程組(1)的解。其收斂速度取決于?????其中λ1,λn分別為A的最小,最大特征值。最速下降法迭代格式：給定初值x(0),x(k)按如下方法決定??例8用最速下降法求解對(duì)稱正定方程組??解：過程如圖所示。??1.共軛梯度法共軛梯度法簡(jiǎn)稱CG(ConjugateGradient),其基本步驟是在點(diǎn)x(k)處選取搜索方向d(k),使其與前一次的搜索方向d(k-1)關(guān)于A共軛，即??????????=0k

3、=1,2,…(7)?然后從點(diǎn)x(k)出發(fā)，沿方向d(k)求得φ(x)的極小值點(diǎn)x(k+1),即?????????(8)如此下去,得到序列{x(k)}。不難求得(7)的解為?????????注意到d(k)的選取不唯一，我們可取d(k)=-▽?duì)?x(k))+βk-1d(k-1),?由共軛的定義(7)可得???????共軛梯度法的計(jì)算過程如下：第一步：去初始向量x(0),計(jì)算????????第k+1步(k=1,2,…)：計(jì)算????????例8用共軛梯度法求解對(duì)稱正定方程組????????解?????迭代過程如圖所示

4、??故x2=(1,1)T就是φ(x)的最小點(diǎn)，也就是索求方程的解。