【正文】 牛頓法的迭代公式為 擬牛頓法 ( 1 ) ( ) ( ) ( 1 0 .4 .1 )k k kkx x d?? ?=( ) ( )kkdx 其 中 是 在 處 的 牛 頓 方 向( ) 2 ( ) 1 ( )( ) ( ) 1 0 2k k kd f x f x?? ? ?= ( . 4 . )()k .kx? 是 從 出 發(fā) 沿 牛 頓 方 向 搜 索 的 最 優(yōu) 步 長2 ( ) 1 2 ( ) 1( ) , ( )kkkf x H f x????為 構 造 的 近 似 矩 陣 先 分 析與 一 階 導 數(shù) 的 關 系 . ( 1 ) ( 1 ) ( 1 )( 1 ) 2 ( 1 ) ( 1 )( ) ( ) ( ) (( ( ) (k k T kk T k kf x f x f x x xx x f x x x? ? ?? ? ?? ? ? ?? ? ?)+1 ) )2( 1 ) ( 1 ), ( ) Ta y l o rkkk x f x x??設 在 第 次 迭 代 后 , 得 點 將 在 點 展 開( 1 ) 2 ( 1 ) ( 1 )( ) ( ) ( ) ( ) ( ( 1 0 . 4 . 3 )k k kg x f x f x f x x x? ? ?? ? ? ? ?+ ) ( 1 )kx ?于 是 在 附 近()kxx?令 ,則( ) ( 1 ) 2 ( 1 ) ( ) ( 1 )( ) ( ) ( ) (k k k k kf x f x f x x x? ? ?? ? ? ? ?+)記 擬牛頓法 ( ) ( 1 ) ( )( ) ( 1 ) ( )( 10 .4 .4)( ) ( ) ( .5)k k kk k kp x xq f x f x????? ? ? ? 則 ( ) 2 ( 1 ) ( )( ) ( 1 0 . 4 . 6 )k k kq f x p???2 ( 1 )H e s s ia n ( ) ,kfx ??設 矩 陣 可 逆 則( ) 2 ( 1 ) 1 ( )( ) ( 1 0 . 4 . 7 )k k kp f x q????( ) ( ) ( 1 )12 ( 1 ) 11, , ( 10 .4 .7 )He ss i a n . He ss i a n( ) ,k k kkkkp q xHf x H??????于 是 計 算 出 和 可 根 據(jù) 估 計 在 處 的矩 陣 的 逆 令 取 代 牛 頓 法 中 的 陣的 逆 則 滿 足()稱為 擬牛頓條件 (方程 )， 也稱為 割線方程 . 怎樣確定滿足這個條件的 H k+1 ? 擬牛頓法 ( ) ( )1= ( 1 0 . 4 . 8 )kk kp H q?算法 擬牛頓法 000011 ( ) , ( 0 , 1 )( ) , 0.2( ) , , ,3 ( ) , ( , ) { | , 0 }, ??? ? ?? ? ????? ? ? ???n n nkkkkk k k kk k kkkx R H Rg f x kgd H gR x d x x x dx x d??????初 始 化 給 定 初 始 點 , 正 定 矩 陣 ,。st e p3 3 , ( ) , , 0) ,( ) ( )4 , ,k k k kkk k k kkkkkkkkSt e p x kSt e p g f x f x xSt e p G f x B G EEGd B f xSt e p x d?????? ? ?? ? ? ?? ? ?給 定 初 始 點 允 許 誤 差 置計 算 梯 度 = 若 停 止 得 解否 則 轉計 算 Hesse 矩 陣 置 矩 陣 其中 為 修 正 矩 陣 ( 當 正 定 時 它 取 計 算 修 正 牛 頓 方 向 從 出 發(fā) 沿 方 向 作 ( 精 確 或( ) ( ) ( ) ( )( 1 ) ( ) ( ): m i n ( ) ( ) , : 1 , 2k k k kkk k kkf x d f x dx x d k k?????? ? ?? ? ? ?非 精 確 ) 一 維 搜 索 令 置 轉 牛頓法 000() : R D D{ | ( ) ( )l im ( )( ) 0.????? ? ???nfxkxfRxf S x D f x f xfx設 在 某 開 集上 二 階 連 續(xù) 可 微 , 且 修 正 牛 頓 法 的 初 始 點 使 得的 水 平 集 是 緊 集 . 若 矩 陣序 列定 理 全 局 收 斂 定滿 足 有 界 分 性理解 特 , 則 1 共軛方向與擴張子空間定理 定義 設 A是 n n對稱矩陣 ,若 Rn 中的兩個方向 d 1 和 d2滿足 (d 1)T Ad 2 =0 （ ） 則稱這兩個方向關于 A共軛 ,或稱它們關于 A正交 . ( 1 ) ( 2 ) ( )( ) ( ), , ..., A0 , , , 1 , 2 , .. . ()? ? ?ki T jd d d kd Ad i j i j kn 若 是 E 中 個 方 向 , 它 們 兩 兩 關 于共 軛 , 即 則稱這組方向是 A共軛 ,或稱它們?yōu)?A的 k個共軛方向 共軛梯度法 幾何意義 設有二次函數(shù) 1( ) ( ) ( ) ( 1 0 .3 .3 )2? ? ?Tf x x x A x x其中 A是 n n對稱正定矩陣 , x是一個定點 . 1 ( ) ( )2Tx x A x x c? ? ?是以 x為中心的橢球面 , ( ) ( ) 0 f x A x x? ? ? ?A正定 ,故 x是 f(x)的極小值點 . f(x)的等值面 由于 設 x(1)是在某等值面上一點 ,此面在點 x(1)處的法向量 ( 1 ) ( 1 )( ) ( )f x A x x? ? ?又設 d (1)是在該等值面在點 x (1)處的一切向量 . d (2) = x x (1) ( 1 ) ( 1 ) ( 1 ) ( 1 ), ( ) . ( ) 0 ,Td f x d f x? ? ?顯 然 與 正 交 即 于 是( 1 ) ( 2 ) 0Td A d ? 即等值面上一點 x(1)處的切向量與由這點指向極小點的向量關于 A共軛 . x 1x 2(1)d(2)d(1)xx 000 0 011111 ( ) , , ( ) ,( ) 02( ) , ( ) 。 ,( ) ( ) , : 1 , 2kkk k k kSte p x kSte p f x xx x f x f x k k????????? ? ? ? ? ?算 法 ( 法給 定 初 始 點 允 許 誤 差 置若 停 止 得 解 否 則 令 轉 牛頓法 ?? (x)=0 為求 ? (x)的駐點 ,令 注意 :牛頓法的迭代格式也可以從最速下降方向的角度來理解 . m i n ( ). 1 (10 .2 .3 )??TTf x ds t d Ad下求 A度量下的最速下降方向 ,為此 ,考慮 牛頓法 TAd d Ad?下面介紹一下 A度量及其意義下的最速下降方向 .設 A為對稱正定矩陣 ,向量 d的 A范數(shù)定義為 由 A, A1對稱正定 ,故存在對稱平方根 A1/2 , A1/2,使得 1 1 1 112 2 2 2, A A A A A A???? －于是 1 1 1 12 2 2 211221122()( ) ( ) ( ( ) )T T TTTTd Ad d A A d A d A df x d f x A A dA f x A d????? ? ??? 牛頓法 12 , ( 10 .2 .3 )?y A d令 則 可 寫 成12m in ( ( ) ). 1 ( 10 .2. 4)???TTA f x ys t y y去掉絕對值符號 ,有 1122 ( ( ) ) ( )TA f x y A f x??? ? ? ?1 1 12 2 2 ( ( ) ) ( ) ( )TA f x y A f x y A f x? ? ?? ? ? ? ?根據(jù) Schwartz不等式 ,得到 牛頓法 即 1 1 12 2 2 ( ) ( )Tf x A A d A f x??? ? ? ?12( ) ( ) Tf x d A f x?? ? ? ? ?為得到在點 x處下降最快的方向 ,按下式選取 d 111 2() ( )( ( ) ( ) )??????? TA f xdf x A f x這時上式等號成立 ,由此確定的方向即 度量 A意義下的最速下降方向 牛頓法 若取 2 () kkA G f x? ? ?, ( ) .k kkG Gfx?的 最 速 下 降 方 向 其 步 長 為則牛頓法的搜索方向實際上是關于向量橢球范數(shù) 牛頓法 牛頓法 例 用牛頓法求解下列問題 4212( 1 ) m in ( 1 )( 0 , 1 )xxx????取 初 點3 221 120 4( 1 ) 12( 1 )( ) , ( ) 22 0x xf x f xx?? ??? ?? ? ? ??? ??????第 1次迭代 ( 1 ) 2 ( 1 ) 4 12 0 ( ) , ( ) 2 0 2f x f x? ? ? ?? ? ? ?? ? ? ?? ? ? ? ( 2 ) ( 1 ) 2 ( 1 ) 1 ( 1 )1( ) ( )0 12 0 4 1 / 3 1 0 2 2 0x x f x f x??? ? ? ?? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?( 3 ) ( 2 ) 2 ( 2 ) 1 ( 2 )1( ) ( )1 / 3 48/ 9 0 32 / 27 5 / 9 0 0 2 0 0x x f x f x??? ? ? ??? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?第 2次迭代 ( 2 ) 2 ( 2 ) 32 / 27 48/9 0 ( ) , ( ) 0 0 2f x f x?? ? ? ?? ? ? ?? ? ? ?? ? ? ? 牛頓法 ( 4 ) ( 3 ) 2 ( 3 ) 1 ( 4 )1( ) ( )5 / 9 64/ 27 0 256 / 729 19 / 27 0 0 2 0 0x x f x f x??? ? ? ??? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?第 3次迭代 ( 3 ) 2 ( 2 ) 256 / 729 64/27 0 ( ) , ( ) 0 0 2f x f x?? ? ? ?? ? ? ?? ? ? ?? ? ? ?繼續(xù)下去 ,第 4次迭代 ,… 得到點列收斂于 (1,0),此為 最優(yōu)解 . 牛頓法 ? ?2 ( ) 1 ( 1 )1 2 1 2( 1 )2 ( ) 112 ( ) , . ( ) 0 ,( ) ,( ) , (10 .2 .) ( ) ( ) (( 2 )1??? ? ??? ? ? ? ???? ? ? ? ? ?nkkf x x E x f xf x x xk k k kx X x x x x x