[洛穀日報第53期]淺談一些求近似值的方法

2021-01-10 洛谷科技

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

相關焦點

  • [洛穀日報第70期]NOIP2018初賽解析
    一些解釋性語言也有了也能在一定程度上編譯，或者使用虛擬機。3.今年是第35屆NOI，因此第一屆NOI是1984年。每次都有這種沒啥實際意義的題目。4.考慮一個等比數列求和。=T_0+(1+2+3+…+n)=\frac{n*(n+1)}{2} 這題是2015年提高組初賽原題，如果有在洛谷有題上寫過這個題應該不會寫錯。6.建出表達式樹，然後先序遍歷即可。
  • [洛穀日報第79期]二進位與位運算
    其他進位也可以用類似的方法進行轉換，例題P1143 進位轉換（https://www.luogu.org/problemnew/show/P1143）原碼、反碼和補碼原碼，指一個二進位數左邊加上符號位後所得到的碼，且當二進位數大於0時，符號位為0；二進位數小於0時，符號位為1；二進位數等於0時，符號位可以為0或1。
  • 三個步驟,助你抓住高中數學「二分法求方程根近似值」問題的本質
    因此，在所學知識和方法基礎上，能結合實際應用，熟練地應用近似求解的意識、方法與能力去解決問題，具有重要的實用意義。本文將講述高中階段要求掌握的二分法求方程式根的近似值的方法與技巧。1. 基本問題說明二分法，又稱分半法，是一種方程式根的近似值求法。
  • [洛穀日報第58期]初賽備考乾貨:P、NP、NP-hard、NPC問題
    這個時候，圖靈跳了出來，丟了一個停機問題，人們吃驚地發現，這個問題甚至沒有正確的解決方法，於是上面的flag就這樣子GG了。 所以又有人來說了：「那能解的問題是不是一定有多項式解法呢？」 於是又來了一個問題：請解決3-SAT問題。 然後不用想了，又GG了。
  • 兩種方法看看0.91^2.91的近似值計算
    本文主要內容：介紹用極限和全微分方法，計算0.91^2.91的近似值。※.極限方法原理：當x→0時，有lim(x→0)(1+x)^a/(1+ax)=1，即此時有(1+x)^a～(1+ax)。此方法計算近似值實質是等價無窮小替換。
  • 計算0.91^1.91近似值的方法
    2020-11-24 13:38:16　來源: 楚鄂新阿 舉報 ※.極限方法
  • 解析二分法求方程f(x)=0在區間「a,b」內近似值的解題步驟
    取[a，b]的中點x=1/2 (a+b)，將區間一分為二用二分法求方程的近似解時會給出近似值與精確值的差的絕對值的範圍，即給出精確度的大小；在使用二分法求方程的近似解時還要找到這個方程的解存在的區間，因為並不是所有的題都給出區間；找到該方程的區間後，求出這個區間的中點，將區間分為兩個區間，方程的解只能在這個區間中的一個區間上，這樣就縮小了區間的範圍
  • 蒙特卡羅方法及應用
    (6)這就是早期的用頻率值作為概率近似值的方法的應用實例, 表1是在歷史上一些有名的用投針試驗計算π值的結果，其中針長以a為單位。
  • 高考數學原創試題—用牛頓迭代法求方程近似解
    牛頓-拉弗森迭代法（簡稱牛頓迭代法）是求方程解的重要方法，該方法是牛頓在17世紀提出的一種在實數域和複數域上近似求解方程的方法。我們知道，很多方程不存在求公式，因此求精確根非常困難，甚至不可能，從而尋求方程的近似根就顯得特別重要。
  • 第52期:軸對稱的妙用之對稱點坐標求法(第5集)
    步：利用A』在拋物線上，求出m，進而求出A『坐標       解法二：（解析法）第1步：求直線AA『的解析式            易知直線BC的解析式為y=-2x+4            設A（0，n），則直線AA』的解析式為y=0.5x+
  • 如何使用java語言求一個正整數的平方根?(不使用庫函數)
    今天的這篇文章是我在刷算法題的時候遇到的，最簡單的方法是直接調用java裡面的Sqrt函數，不過有時候題目中會要求我們不能使用庫函數，所以在這裡我們自己定義Sqrt方法。最常見的思路有兩種，第一種是二分法，第二種是牛頓的微積分思想。
  • 偽·從零開始學算法 - 2.3 求圓周率
    據說遠古時期的人們根據經驗以3作為圓周率的值（「徑一周三」），這個值至今也能夠用於一些對精度要求不高的場合（如手工做木桶）。但是，對於天體運行和面積測量等方面，3這個值未免太粗略。人們對於它的計算絕不僅限於此。古埃及、古巴比倫、古印度、古代中國的遺蹟中都能夠找到關於圓周率的較精確的值，它們都能夠達到3.1這個值。
  • 除了用「正多邊形逼近圓」的「割圓術」，還有哪些計算π的方法？
    其中中國古人，用圓內接正多邊形逼近圓求圓周率；西方則通過內接與外切正多邊形兩面「夾攻」，用算術平均近似圓周率；有的通過周長，有的通過面積。1976年，歐仁·沙拉明在《計算的數學》第30卷上，發表了重要論文《利用算術平均數與幾何平均數計算π值的新方法》。理察·波倫特於同年獨立發現了類似的新方法。該算法是基於算術一幾何平均值，和某些在19世紀原屬於高斯的思想，但高斯沒有將其與π的計算相聯繫。算法產生的近似值收斂速度，比任何經典公式都快得多。
  • 第51期:軸對稱的妙用之對稱點坐標求法(第4集)
    本文將此類問題歸結為對稱點坐標求法，並介紹兩種解決此類問題的通法。【例1】(自編)（難度係數☆☆☆) 如圖，在平面直角坐標系中，已知A（-1，2），B（2，0），C（0，4），求點A關於直線BC的對稱點A'的坐標.【解法一】（構造K字型）    第1步：過點A分別作x軸，y軸的平行線，交對稱軸於點F, E，連接A'E,A'F。
  • 近似值——霧裡看花數花瓣,水中望月找嫦娥
    近似值為0.5的兩位小數中，最小的是0.45，最大的是0.54，這裡面當然包括0.50。●首先，從數學概念的本質來分析，部分老師混淆了精確值和近似值兩個概念，認為：0.50=0.5,因此0.50是精確值，不是0.5的近似值。
  • 圓周率的7大類計算方法:割圓術、連分數、分析法、概率法
    其中中國古人，用圓內接正多邊形逼近圓求圓周率；西方則通過內接於外切正多邊形兩面「夾攻」，用算術平均近似圓周率；有的通過周長，有的通過面積。1976年，歐仁·沙拉明在《計算的數學》第30卷上，發表了重要論文《利用算術平均數與幾何平均數計算π值的新方法》。理察·波倫特於同年獨立發現了類似的新方法。該算法是基於算術一幾何平均值，和某些在19世紀原屬於高斯的思想，但高斯沒有將其與π的計算相聯繫。算法產生的近似值收斂速度，比任何經典公式都快得多。之後又以此派生出其他的一些算法，都極大地提高了運算速度。
  • 梅雅博論第53期:探索生命科學奧秘——走進神奇的光遺傳學研究領域
    為解開這些疑惑，藥學院特聘副研究員陳顯軍於11月20日中午做客梅雅博論第53期，在隴上書店黨建服務中心與同學們分享探索生命科學奧秘——走進神奇的光遺傳學研究領域。他指出，目前化學誘導物控制基因的表達的方法只能在時間上調節基因的表達，空間上則存在局限性。而光誘導物避開了化學誘導物的缺陷，具有易於時空操作、無毒性和易獲取的優點，因此非常適用於基於基因精準醫療方面的研究，如控制糖尿病血糖值、抑制腫瘤的生長等。講座最後，他談到，儘管光遺傳學研究領域已經取得了諸多顯著進展，但其仍然處於初期發展階段，存在大量的未知領域值得進一步探究。
  • 你會求方程的近似解嗎?
    內容章節：函數的應用 - 函數與方程 - 用二分法求方程的近似解基礎知識3.1.2 用二分法求方程的近似解（1）二分法原理：對於在區間[a,b]上連續不斷且f(a).f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間一分為二
  • 號稱研究生都做不出來的「小學」數學題:求陰影部分面積
    頭條上很多人叫囂著說自己十幾年前就做過這道題，信誓旦旦說確實是小學奧數題，但卻沒有一個人能用小學方法給出解答。除了大部分譁眾取寵之徒外，也有一部分人給出了正確解答，有用三角函數的，有用微積分的，也有直接用軟體計算的，近似值為1.25.分析解答下面對這道題作簡要分析，並給出幾何畫板的解法。
  • EV3 雙光感比例算法巡線 ——李老師大講堂第22期 (更新scratch模式)
    我們先要看的是這個，a為100，B為探測的結果乘以2的數值，也就是 情況1 雙白  B接近於0，好了 abs的意思是 絕對值，abs（b）的意思是求b具體的講解可以看看，我以前發過的一篇關於pid的文章，其實比例就是pid裡的p淺談PID巡線——李老師積木大講堂 第75期