0 前置知識&&寫在前面
學習牛頓迭代法需要能熟練地掌握求導QwQ
學習泰勒公式需要能熟練地掌握求導並對無窮級數有一定了解QwQ
要想看懂牛頓迭代法的二次收斂證明需要一定的高數基礎QwQ（看不懂也無所謂，會用就行）
學習泰勒公式需要能熟練地掌握求導並對無窮級數有一定了解QwQ
一點都不會怎麼辦？沒有問題，會用就行NOIP不考QwQ
求零點、不動點、函數近似值、極值、最值……基本可以認為是一類問題，所以本文以討論如何** 求零點的近似值為主**
因為筆者太弱所以沒有遺傳算法、模擬退火之類的玄學算法
筆者是∑狂魔，要是有式子不理解請展開QwQ
對於低於5次的多項式方程，我們有通用的公式解法求零點的精確值對於一些特殊高次多項式方程（例如可以因式分解的或者滿足一些特定形式的方程）的和一些特殊的超越方程，我們也有方法求零點的精確值但是其餘的情況呢？目前來說我們只能求近似值QwQ（而且在實際應用中，精確值往往也會被轉換成近似值）1 二分法 (int\long long\etc.)這個方法可以說相當常見了（括號裡是此法經常被應用於的數據類型）QwQ對於在區間[l,r]內單調、連續且有f(l)*f(r)<0成立的f(x)，做如下操作：計算mid=(l+r)/2若f(l)*f(mid)<0，則令r=mid，否則令l=mid如果達到預定精度，跳轉到4，否則跳轉到1結束循環次數：附程序：
2 0.618法\優選法 (float\double\long double)可能有的讀者沒聽說過，不過這個方法其實還是很常用的QwQ這個方法更常用於求單峰函數最值，所以這裡以求單峰函數最值為例講解先證明一下它的優越性（過程摘自人教版高中數學選修4-7 優選法與試驗設計初步）（沒錯真的有這本選修QwQ）
一句話概括就是在縮小區間後可以只計算一個試點坐標，從而保證最優操作流程如下（和二分法類似）
附程序：
讀者們可以在洛谷P3382（https://www.luogu.org/problemnew/show/P3382）中測試一下(～o￣3￣)～（雖然是三分法模板但也可以用優選法\二分法做哦）關於這個還有一個類似方法：斐波那契法。有興趣的讀者可以查閱相關資料才不是筆者不想寫_(:3」∠)_3 泰勒公式先講這個是為了為下文牛頓迭代法二次收斂的證明做鋪墊，不想看證明的可以略過QwQ（不過還是推薦了解一下，挺有趣的）這裡假定函數f(x)在x_0處有任意階導數我們可以很容易地求出多項式和類指數函數的近似值，但是像三角函數、對數函數這樣的我們又該如何求近似值呢對了，就是用泰勒公式QwQ泰勒公式的想法很簡單，就是構造一個多項式函數，使得它與函數在處的原函數值和各階導數均相等，即
因為
於是我們就得到了（解n元一次方程組，很簡單的）
當n→∞時，我們可以認為f(x)=g(x)而當n有一個確定的值時，f(x)就可以寫成g(x)+R_n(x)了其中R_n(x)是餘項，它有好幾種不同的寫法，這裡選用拉格朗日餘項。因為它不僅在下文中牛頓迭代法的二次收斂證明中出現了，而且形式和前面的幾項非常相近
其中ξ_L在x和x_0之間要是了解過拉格朗日中值定理的讀者應該很快就能領會當n→∞時，有（泰勒級數）
特別地，當x_0=0時，有（麥克勞林級數）
另外注意應用麥克勞林級數並且x在某個範圍之外時，得到的結果可能是發散的（就是，這個不展開講，有興趣的讀者可以去學習無窮級數相關知識）附上Wikipedia的動圖
對證明感興趣的讀者可以自行查閱相關資料不能理解無所謂反正NOIP不考，下面給出幾個常見的泰勒級數
程序略QwQ4 牛頓迭代法先說說這個方法的過程
稍加計算便得到了
既然是迭代，那麼自然就有
其中x_n代表第n次迭代附上Wikipedia的動圖（https://en.wikipedia.org/wiki/Newton's_method）
二次收斂證明（Wikipedia上的，筆者翻譯QwQ）（還是那句話：看不懂無所謂，會用就行QwQ）：
程序：
當然，上述各方法的應用範圍遠不止於此，有興趣的讀者可以自行查閱相關資料QwQ5 贈品5.1 cos(x)=x的解析解對於PhOer來說，cos(x)=x這個方程應該是相當熟悉了QwQ筆者在這裡放上解析解（近似值x=0.739），詳情見參考文獻[2]（文獻裡講的是t sin( x)=x-m的解法，不過筆者太弱了，實在是看不懂QwQ）
5.2 快速求1/sqrt{x}關於這個有一個相當有名的故事為了節約篇幅，筆者把文章放在這裡了（https://www.luogu.org/paste/04z8pvrb）6 後記這篇文章偏數學一些，如果不能理解的話請多讀幾遍QwQ其實可寫的還有很多，限於篇幅就到此為止了（現在在後臺打個字都要卡兩秒QwQ）因為筆者是個蒟蒻，所以如果有錯誤，煩請各位dalao不吝賜教7 主要參考資料[1] 人教版高中數學選修4-7 優選法與試驗設計初步[2] Siewert C E, Burniston E E. An exact analytical solution of Kepler's equation[J]. Celestial Mechanics, 1972, 6(3):294-304.[3] Newton's method - Wikipedia（https://en.wikipedia.org/wiki/Newton's_method）[4] Taylor's theorem - Wikipedia（https://en.wikipedia.org/wiki/Taylor%27s_theorem）[5] 一個Sqrt函數引發的血案（）（這個是筆者能找到的最早的一篇了QwQ）本文發布於洛穀日報，特約作者：khong原文地址：https://khong-biet.blog.luogu.org/methods-of-GetApproxNumber