Python實(shí)現(xiàn)所有算法：拉夫遜方法

emmmmm,好長(zhǎng)時(shí)間沒有用matplotlib，都不會(huì)畫圖了。先繪制一個(gè)x**3-1的函數(shù)，然后考慮在a,b之間找他的根。

-10，10

-5，5

那么這個(gè)函數(shù)被起名為intersection

連續(xù)函數(shù)與x相交時(shí)就是根，是不是很形象。

def intersection(function: Callable[[float], float], x0: float, x1: float) -> float:

因?yàn)槲覀冎?，這個(gè)函數(shù)應(yīng)該是我們給出要求解的區(qū)間和函數(shù)給出一個(gè)根。那么這里function的Callable就是可以當(dāng)匿名函數(shù)傳遞。

為了函數(shù)的靈活性，這里使用float

主函數(shù)，因?yàn)槲覀兒瘮?shù)其實(shí)不知道具體的函數(shù)的循環(huán)次數(shù)，那么就可以使用while的循環(huán)。

一開始要判斷參數(shù)的情況，如果都相等，你這算啥？？？以及都帶進(jìn)去，再算一下，雙保險(xiǎn)，雙重?fù)浣帧?/p>

接下來就是這個(gè)公式，我是個(gè)罪人，用了一張A4紙就寫一個(gè)這

計(jì)算的X看看符合要求嗎？不符合就繼續(xù)將值域縮小。直到很小。

這個(gè)不是二分法，但是差不多的意思，不過這個(gè)是牛頓法，也叫牛頓-拉夫遜（拉弗森）方法，就我的題目。

這篇文章的下面就講講這個(gè)東西：

它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。

多數(shù)方程不存在求根公式，因此求精確根非常困難，甚至不可解，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù) f(x) 的泰勒級(jí)數(shù)的前面幾項(xiàng)來尋找方程 f(x)=0 的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點(diǎn)是在方程 f(x)=0 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時(shí)線性收斂，但是可通過一些方法變成超線性收斂。

牛！

迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代算法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。

利用迭代算法解決問題，需要做好以下三個(gè)方面的工作：

一、確定迭代變量

在可以用迭代算法解決的問題中，至少存在一個(gè)可直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。

二、建立迭代關(guān)系式

所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。

三、對(duì)迭代過程進(jìn)行控制

在什么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地執(zhí)行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析得出可用來結(jié)束迭代過程的條件。

然后，自己的函數(shù)也可以這樣定義

intersection(f, 3, 3.5)

精度ok

再說說數(shù)值求法：

大多數(shù)的數(shù)值求根算法都使用迭代法，生成一個(gè)以方程的根為極限的收斂數(shù)列。它們需要一個(gè)或多個(gè)根作為迭代的初期值，之后每次迭代都生成一個(gè)逐步逼近根的值。

由于迭代法必須在有限步內(nèi)終止于某個(gè)點(diǎn)，這些方法都只能提供一個(gè)根的近似值，而不能提供一個(gè)精確解。許多方法是通過代入上一個(gè)迭代值來計(jì)算一個(gè)輔助方程，從而得出下一個(gè)迭代值的。此處所指的輔助方程是指為了使原方程的根是一個(gè)定點(diǎn)并使迭代值能更快地收斂到這些定點(diǎn)而設(shè)計(jì)的一個(gè)方程，因此迭代值的極限是這個(gè)輔助方程的一個(gè)定點(diǎn)。

求根算法的性能是數(shù)值分析的研究范疇。一種算法的效率可能大幅度取決于已知點(diǎn)的性質(zhì)。

例如，一部分算法都使用輸入函數(shù)的導(dǎo)數(shù)（此要求函數(shù)不但連續(xù)，而且可導(dǎo)），而其他算法則能用于任何一個(gè)連續(xù)函數(shù)。在一般情況下，數(shù)值算法不能保證找到一個(gè)函數(shù)的所有根，因此算法未能找到根并不能證明方程無根。然而，對(duì)于多項(xiàng)式，存在特定的使用代數(shù)學(xué)性質(zhì)以定位根的所在區(qū)間（或復(fù)根所在的圓盤）的算法，這個(gè)區(qū)間（或圓盤）足夠小以能保證數(shù)值算法（例如牛頓法）能收斂到唯一被定位的根。