牛頓迭代法的作用是使用迭代法來求解函數(shù)方程的根，簡單的說就是不斷地求取切線的過程．對(duì)于形如f(x)=0的方程，首先任意的估算一個(gè)解x0哄芜，再把該估計(jì)值代入原方程中．由于一般不會(huì)正好選擇到正確的解，所以有f(x0)=a.這時(shí)計(jì)算函數(shù)在x0處的斜率，和這條斜率與ｘ軸的交點(diǎn)x1. f(x)=0中精確解的意義是族阅，當(dāng)取得解的時(shí)候，函數(shù)值為零(即f(x)的精確解是函數(shù)的零點(diǎn))．因此膝捞，x1比x0更加的接近精確地解．只要以此方法不分段的更新ｘ坦刀，就可以取得無線接近的精確地解．但是也有可能會(huì)遇到牛頓迭代法無法收斂的情況．比如函數(shù)有多個(gè)零點(diǎn)，或者是函數(shù)不連續(xù)的時(shí)候．
設(shè)x的ｍ次方根為a
const float EPS = 0.00001;
double sqrt(double x) {
if(x == 0) return 0;
double result = x; /*Use double to avoid possible overflow*/
double lastValue;
do{
lastValue = result;
result = result / 2.0f + x / 2.0f / result;
}while(abs(result - lastValue) > EPS);
return (double)result;
}
更快的方法
在游戲雷神之錘III中有一段求平方根的代碼如下：
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此處迭代次數(shù)越多绑警，精度越高．
#ifndef Q3_VM #
ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
這段代碼的作用就是求數(shù)number的平方根求泰，并返回它的倒數(shù)．經(jīng)過測試，它的效率比牛頓法要快幾十倍计盒，也比C++標(biāo)準(zhǔn)的sqrt()函數(shù)要快好幾倍．
