算法构造 问题:如何从xk→>xk 设f(x)二阶连续可微x∈Ry,k=V(x) 海色阵G=V2f(x)正定 f(x)=f(x,+x-xk)=(x)=f+gk 因为G正定则q(x)有唯一极小点用这个 极小点作为x
算法构造 问题： 设 f (x) 二阶连续可微， , n xk R ( ), k k g = f x 海色阵 ( ) k k G f x 2 = 正定． 如何从 ? k → k+1 x x ( ) ( ) ( ) ( ) k T k k k k k f x = f x + x − x q x = f + g x − x ( ) ( ) k k T k + x − x G x − x 2 1 因为 Gk 正定，则 q (x) k 有唯一极小点，用这个 极小点作为 . k+1 x
所以要求:Vqn(x21)=0 即:G(x1-x)+8=0 因此:xk1=x4-G8 这就是牛顿法迭代公式 注:这里a=1,dk=-G8k
所以要求： ( ) 0 qk xk+1 = 即： ( ) 0 Gk xk+1 − xk + gk = k k k k x x G g 1 1 − 因此： + = − 这就是牛顿法迭代公式． 注：这里 1, . 1 k k k k d G g − = = −
牛顿法算法 Step1:给出xo∈Rn,0≤E<<1,k:=0 step2:计算ⅴf(x),如果(xk)≤E,停 step3:否则计算G,并且求解方程 GAdk=-k,得出ak Step4:令xk+1 X,-+ k k 转步2
牛顿法算法 Step1: 给出 x0 R ,0 1, k := 0 n Step2: 计算 ( ), k f x 如果 ( ) , k f x 停． Step3: 否则计算 , Gk Step4: 令 , xk+1 = xk + dk 转步２. 并且求解方程 , Gk dk = −gk 得出 . dk
例1:用牛顿法求解 m/(x)=1x2+9x2 (9,1) 解:g(x)= G(x)= x=(00) 9 09 00 1)(09)(9)(0
例1：用牛顿法求解： ( ) ( ) T f x x x x 9,1 2 9 2 1 min 0 2 2 2 = 1 + = 解： ( ) ( ) ( ) T G x x x x g x 0,0 0 9 1 0 9 * 2 1 = = = * 1 0 1 1 0 0 0 0 9 9 0 9 1 0 1 9 x x G g = x = − = − = − −
牛顿法收敛定理 定理:设f(x)二次连续可微,x是f(x)的局 部极小点,V/(x)正定假定/(x)的海色阵 Gk=V2f(xk)满足 Lipschitz条件,即存在 β>0,使得对于所有1≤i,j≤n有 G(x)-G()≤川x-y,yx,y∈R”() 其中G(x)是海色阵G的(元素则当x 充分靠近x“时对于—切k,牛顿迭代有意义 迭代序列{收敛到x并目具有二阶收敛速度
牛顿法收敛定理 定理1: 设 f (x) 二次连续可微， * x 是 f (x) 的局 部极小点， ( ) * f x 正定．假定 f (x) 的海色阵 ( ) k xk G f 2 = 满足Lipschitz条件，即存在 0, 使得对于所有 1 i, j n 有： ( ) ( ) , , (1) n Gi j x −Gi j y x − y x y R 其中 G (x) ij 是海色阵 Gk 的 (i, j) 元素．则当 x0 充分靠近 * x 时，对于一切 k, 牛顿迭代有意义， 迭代序列xk 收敛到 , * x 并且具有二阶收敛速度．