打字猴:1.700536596e+09

1700536596

1700536597

1700536598

1700536599 （7.24）

1700536600

1700536601 二阶法也称为牛顿法，Hessian矩阵就是目标函数的二阶信息。二阶法的收敛速度一般要远快于一阶法，但是在高维情况下，Hessian矩阵求逆的计算复杂度很大，而且当目标函数非凸时，二阶法有可能会收敛到鞍点（Saddle Point）。

1700536602

1700536603 ·总结与扩展·

1700536604

1700536605 俄罗斯著名数学家Yurii Nesterov于1983年提出了一阶法的加速算法[10]，该算法的收敛速率能够达到一阶法收敛速率的理论界。针对二阶法矩阵求逆的计算复杂度过高的问题，Charles George Broyden，Roger Fletcher，Donald Goldfarb和David Shanno于1970年独立提出了后来被称为BFGS的算法 [11—14]，1989年扩展为低存储的L-BFGS算法 [15]。

1700536606

1700536607 逸闻趣事

1700536608

1700536609 　

1700536610

1700536611 平方根倒数速算法

1700536612

1700536613 20世纪90年代曾出现过一款不可思议的游戏——雷神之锤（Quake series）。除了优秀的情节设定和精美的画面外，这个游戏最让人称道的莫过于它的运行效率。在计算机配置低下的年代，一段小动画都是一个奇迹，但雷神之锤却能流畅运行于各种配置的电脑上。直到2005年Quake Engine开源时，雷神之锤系列游戏的秘密才被揭开。在代码库中，人们发现了许多堪称神来之笔的算法。它们以极其变态的高效率，压榨着计算机的性能，进而支撑起了20世纪90年代3D游戏的传奇。其中的某些算法，甚至比系统原生的实现还要快！今天的主角—— 快速平方根倒数算法（Fast Inverse Square Root）就是其中一个。

1700536614

1700536615

1700536616 在3D 绘图中，计算平方根倒数是一步重要的运算，因为计算机需要大量求解一个矢量的方向矢量，即

1700536617

1700536618

1700536619

1700536620

1700536621 （7.25）

1700536622

1700536623 其中就涉及平方根倒数的计算，这也是最麻烦的一步。如果能在此做一些优化，渲染效率无疑会得到极大提高。先来看雷神之锤中平方根倒数速算法的代码。

1700536624

1700536625 float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y　= number; i　= * ( long * ) &y;　　　　　　　　　 // evil floating point bit level hacking i　= 0x5f3759df - ( i >> 1 );　　　　　　 // what the fuck? y　= * ( float * ) &i; y　= y * ( threehalfs - ( x2 * y * y ) );　 // 1st iteration // y　= y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y;}

1700536626

1700536627 从代码中可以看出，算法最后有两步相同的操作，像是在对一个数进行某种迭代。而其中的第二步被注释掉了，似乎是因为和性能损耗相比，对结果的二次迭代意义不大，这也说明一次迭代的结果在误差允许范围内。这些特性让人想到了牛顿法。

1700536628

1700536629