设72f(x)可逆，有(10.2.1)得到牛顿法的迭代公式 x()=x()-v2f(x()Vf(x()) (10.2.2) 其中V2f(x)1是esse矩阵V2f(x)的逆矩阵.这样，知道 xk)后，算出在这一点处目标函数的梯度和Hsse矩阵的逆，代人 (10.2.2), 得到后继点x+),用k+1代替k,再用(10.2.2)计算，得 到x+的后继点依此类推，产生序列{x}.在适当的条件下， 这个序列收敛 定理10.2.1 设f(x)为二次连续可微函数，x∈R”,元满 足Vf(x)=0,且V2f(x)存在.又设初点x)充分接近x,使得存 在k,k2>0,满足kk2<1,且对每一个 x∈X={xlx-利≤x0-x 成立
设 2 f (x (k ) ) 可逆,有(10.2.1)得到牛顿法的迭代公式 ( ) ( ) (k 1) (k ) 2 (k ) 1 (k ) x = x − f x f x + − (10.2.2) 其中 是Hesse矩阵 的逆矩阵. 这样, 知道 后,算出在这一点处目标函数的梯度和Hesse矩阵的逆,代人 (10.2.2), 得到后继点 ,用 代替 ,再用(10.2.2)计算,得 到 的后继点.依此类推,产生序列 .在适当的条件下, 这个序列收敛. 2 ( ) 1 ( ) − k f x ( ) 2 (k ) f x (k ) x (k +1) x k +1 k (k +1) x { } (k ) x 定理10.2.1 设 为二次连续可微函数, , 满 足 ,且 存在.又设初点 充分接近 ,使得存 在 ,满足 ,且对每一个 f (x) n x R x f (x) = 0 2 1 ( ) − f x (1) x x , 0 k1 k2 1 k1 k2 { | } (1) x X = x x − x x − x 成立
1.2fx)≤ (10.2.3) 2. f)-fx)-f版-≤k (10.2.4) 版-州 则牛顿法产生的序列收敛于x. 例10.2.1用牛顿法解下列问题： min (x-1)4+x2 我们取初点x=(0,1)T. 实际上，当牛顿法收敛时，有下列关系： x+w-≤crw- (6.2.8) 其中C是某个常数.因此，牛顿法至少2级收敛，参看文献24].可见 牛顿法的收敛速率是很快的
( ) 2 2 1 2 1 ( ) ( ) ( ) 2. 1. ( ) k x x f x f x f x x x f x k − − − − − (10.2.3) (10.2.4) 则牛顿法产生的序列收敛于 x . 例10.2.1 用牛顿法解下列问题: 2 2 4 1 min (x −1) + x 我们取初点 (0,1) . (1) T x = 实际上,当牛顿法收敛时,有下列关系: 2 ( 1) ( ) x x c x x k k − − + (6.2.8) 其中 是某个常数.因此,牛顿法至少2级收敛,参看文献[24].可见 牛顿法的收敛速率是很快的. c
特别地，对于二次凸函数，用牛顿法求解，经1次迭代即达极小 点. 设有二次凸函数 f(x)=-xAx+bx+c (10.2.9 其中A是对称正定矩阵 我们先用极值条件求解.令 Vf(x)=Ax+b=0 得到最优解 x=-A-b 下面用牛顿法求解.任取初始点x四，根据牛顿法的迭代公 式(10.2.2)，则有
特别地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小 点. 设有二次凸函数 f x x Ax b x c T T = + + 2 1 ( ) (10.2.9) 其中 是对称正定矩阵. 我们先用极值条件求解.令 A f (x) = Ax + b = 0 得到最优解 x A b −1 = − 下面用牛顿法求解. 任取初始点 , 根据牛顿法的迭代公 式(10.2.2),则有 (1) x
x2)=x0-A17f(x0) =x四-A(AxD+b) =-Ab 显然，x2=元，即1次迭代达到极小点 以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛 顿法，经有限次迭代必达到极小点这种性质称为二次终止性 值得注意，当初始点远离极小点时，牛顿法可能不收敛.原因 之一，牛顿方向 d=-V2f(x)-17f(x) 不一定是下降方向，经迭代，目标函数值可能上升此外，即使目标 函数值下降，得到的点xk+也不一定是沿牛顿方向的最好点或 极小点.因此，人们对牛顿法进行修正，提出了阻尼牛顿法」
(2) (1) 1 (1) (1) 1 (1) 1 ( ) ( ) x x A f x x A Ax b A b − − − = − = − + = − 显然, .即1次迭代达到极小点. x = x (2) ( ) ( ) 2 1 d = − f x f x − 不一定是下降方向,经迭代,目标函数值可能上升.此外,即使目标 函数值下降,得到的点 也不一定是沿牛顿方向的最好点或 极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法. 值得注意,当初始点远离极小点时,牛顿法可能不收敛.原因 之一,牛顿方向 以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛 顿法,经有限次迭代必达到极小点.这种性质称为二次终止性. (k +1) x
10.2.2 阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的 一维搜索，其迭代公式是 xk+=xk)+元d (10.2.6) 其中d)=-Vf(x)1口f(x)为牛顿方向，九k是由一维搜索得 到的步长，即满足 f(xd()=min f(x+d) 阻尼牛顿法的计算步骤如下： 1.给定初始点xD,允许误差δ>0，置k=1· 2.计算f(xk),V2f(x)
10.2.2 阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的 一维搜索,其迭代公式是 ( 1) ( ) (k ) k k k x = x + d + (10.2.6) 其中 为牛顿方向, 是由一维搜索得 到的步长,即满足 ( ) min ( ) ( ) (k ) (k ) (k) k k f x d f x d + = + k ( ) ( ) (k ) 2 (k ) 1 (k ) d = − f x f x − 阻尼牛顿法的计算步骤如下: 1.给定初始点 ,允许误差 ,置 . 2.计算 (1) x 0 k =1 ( ) 2 ( ) 1 ( ), ( ) − k k f x f x