總體思路，一步步逼近赃承。
如何逼近呢？三個方法：
- 基本二分法：折半悴侵。 線性逼近
- Newton's 逼近瞧剖；
一次導(dǎo)數(shù)逼近： - 泰勒級數(shù)；（啊可免，回憶起了被高數(shù)支配的大學(xué)時光@_@）
泰勒級數(shù)
泰勒(Taylor)中值定理 如果函數(shù)f(x)在定義在a附近的平滑函數(shù)f最近似的多項式被稱為關(guān)于x =a的N階泰勒多項式, 即
該公式稱為f(x)按(x-a)的冪展開的n階泰勒公式捉撮。余項Rn(x)有多種形式。
在泰勒公式中逮刨，如果取a=0呕缭，則可得到所謂的麥克勞林(Maclaurin)公式：
我們要求開平方根堵泽，那么把f(x)設(shè)為√x是不是就可以了呢修己？讓我們試試看求它的導(dǎo)數(shù)恢总。
f(x)=√x
f'(x)=(√x)'
根據(jù)導(dǎo)數(shù)公式
- (x^u)' =u·x^(u-1)
- f'(x)=(x^(1/2))'=1/(2√x)
然后把0帶入，發(fā)現(xiàn)0在分母位置睬愤。所以把f(x)設(shè)為√x無法運用麥克勞林公式片仿。比如把f(x)設(shè)為√(x+1)
- f(x)=√(x+1)則f'(x)=1/(2√(x+1))
我們可以繼續(xù)計算得到2階，3階導(dǎo)數(shù)尤辱。
“函數(shù)展開成冪級數(shù)”就是指砂豌，是否能找到這樣一個冪級數(shù)，它在某個區(qū)間內(nèi)收斂光督，且其和恰好就是給定的函數(shù)f(x)阳距，如果能找到這樣的冪級數(shù)，我們就說结借，函數(shù)f(x)在該區(qū)間內(nèi)能展開成冪級數(shù)筐摘，或簡單地說函數(shù)f(x)能展開成冪級數(shù)，而該級數(shù)在收斂區(qū)間內(nèi)就表達(dá)了函數(shù)f(x)船老。
有這樣一個定理 設(shè)函數(shù)f(x)在點x0的某個領(lǐng)域U(x0)內(nèi)具有各階導(dǎo)數(shù)咖熟，則f(x)在該領(lǐng)域內(nèi)能展開成泰勒級數(shù)的充分必要條件是f(x)的泰勒公式中的余項Rn(x)當(dāng)n->∞時的極限為零。
所以函數(shù)展開成冪級數(shù)是有條件的柳畔。對于√(x+1)=1+(1/2)x-(1/8)x2+(1/16)x3+... 條件是-1<=x<=1馍管。具體計算過程請看《高等數(shù)學(xué)》下冊第十一章第四節(jié)例6。
對于x的特殊要求 所以 我們求√(17) = √(16+1) = 4 * √(1+1/16). -1<= 1/16 <= 1.
所以√(17) = 4(1+1/21/16-1/8(1/16)^2+1/16(1/16)^3+...)
所以誤差 取決于我們省略號省略了什么薪韩。
- 二分法
int sqrt(int x) {
long long i = 0;
long long j = x / 2 + 1;// 為了防止溢出
while (i <= j)//起初直接思路是：用x與mid * mid比較确沸，但是用區(qū)間夾，誤差更小
{
long long mid = (i + j) / 2;
long long sq = mid * mid;
if (sq == x) return mid;
else if (sq < x) i = mid + 1;
else j = mid - 1;
}
return j;
}
- 迭代逼近 （相當(dāng)于二分法的優(yōu)化俘陷，區(qū)間單端調(diào)整）
double sqrt(double x) {
if (x == 0) return 0;
double last = 0.0;
double res = 1.0;
while (res != last)
{
last = res;
res = (res + x / res) / 2;
}
return res;
}
- 泰勒級數(shù)
double Tsqrt(double x)//計算[0,2)范圍內(nèi)數(shù)的平方根
{
double sum,coffe,factorial,xpower,term;
int i;
sum=0;
coffe=1;
factorial=1;
xpower=1;
term=1;
i=0;
while(ABS(term)>0.000001)//假設(shè)誤差為0.000001
{
sum+=term;
coffe*=(0.5-i);
factorial*=(i+1);
xpower*=(x-1);
term=coffe*xpower/factorial;
i++;
}
return sum;
}
double sqrt2(double x)//讓括號整體的值,相當(dāng)于之前提的(1+x),在區(qū)間[0,2)张惹；
{
double correction=1;
while(x>=2)
{
x/=4;
correction*=2;
}
return Tsqrt(x)*correction;
}
