對于“算”一詞給精確的定不是一件易事，有些意義相的同義語就是一些他的名詞它們（有）會給出不多同樣東西，例 "法則"" 技巧”“程序”有“方法等等都是種同義語也可以給一些例子如長乘法就是小學學的把兩正整數(shù)相的豎式乘。然而，然非形式解釋和恰的例子對什么是算給出了很的感覺，算法一詞所深藏的想卻經歷一個很長演化歷程直得到 20 世紀才得到了令滿意的形定義，而于算法的念，直到今還在演。算盤家算法家回關于乘法例子，有點是顯然：怎樣把個數(shù)相乘表示這些的方法極地影響了法的具體法。為了明白這點試著把兩羅馬數(shù)字 CXLVII 和 XXIX 相乘，但不先把它們成等價的進數(shù)字 147 和 29。這件事既難弄白，明白以后進行算也極其時間，而就可以解何以留存今的羅馬國關于乘的材料極零散。記制可以是 " 累加的 "，如羅馬記數(shù)法C 表示 100。X 表示 10。L 表示 50，但是 X 放在 L 左方表示從 L 中減去 X，所以就是 40，V 表示 5，I 表示 1，兩個 I 放在 V 的右方，表示要它們加到 V 上，所以是 7。把所有以的解釋“加”起來就是羅馬學的 147。記數(shù)制度也可以進位的，我們今天用的那樣如果是進的，可以用一個或個基底。很長的時中，進行算可以使一種計算具 "算盤（abacus）"。這些計算具可以表一定基底的進位制數(shù)。例如如果以 10 為基底、則一個記物可以表 1 個單位、或 10?；蛘?100 等等，視它是放在一橫行或列而定。照精確的則移動這標記物，可以進行術四則運。中國的盤就是 abacus 的一種。到 12 世紀，阿伯數(shù)學著被翻譯為丁文以后十進制就歐洲流行來了。這進位制特適合于算運算，并引導到許新的計算法。這些法就通稱算法（algoritmus），而與在算上用標記進行計算區(qū)別。雖數(shù)字符號就是數(shù)碼來自印度的實踐，后來才為拉伯人所，現(xiàn)在這數(shù)碼卻叫阿拉伯數(shù)．算法（algorithm）的字源卻是拉伯文，是阿拉伯學家阿爾花拉子米名字的變?；ɡ?是現(xiàn)在已的最古老數(shù)學書的者，這一作名為 《通過補全還原做計的綱要》al-Kitab al-mukhtasar f hisib al-jabr wod ll-mugi balo），其中的 al-jabr 后來就變成了代數(shù)”（algebra）一詞。有限性我已經看到算法”一在中世紀指以整數(shù)十進制表為基礎的算程序。是到了 17 世紀，在達朗貝主編的《科全書》，算法一被賦予了廣泛的意，不只用算術，還于關于代方法以及他的計算序，諸如 "積分學的算法"" 正弦的算 " 等等。算法這詞又逐漸被用來表任意的具精確規(guī)則系統(tǒng)的計程序。最，隨著計機的作用來越大，限性的重性被充分識到了，本質的要是，這個程在有限間以后就停止，而出結果。以就得到下面的樸的定義：個算法就有限多個則的集合用以對數(shù)有限的數(shù)進行操作而在有限步以后產結果。注，在這里直強調有性，在寫算法時的限性，以在執(zhí)行算時的有限。上面的述算不上在經典意下的數(shù)學義。我們會看到，它進一步式化是重的。但是們現(xiàn)在暫也就滿足這個 "定義" 了，而且來看下數(shù)學中算法的一經典例子三個歷史的例子算具有一種們尚未提的特性：代，也就簡單程序反復執(zhí)行為了看清代的重要，我們再次來看一長乘法這例子，這一個對任大小的正數(shù)都適用方法。數(shù)變得越大程序也就長。但是關緊要的，方法是同樣的”如果會把個三位數(shù)乘，也就把兩個 137 位的數(shù)字相乘而不必再學什么新原理，理在于長乘的方法里包含了大的仔細構好的小得的任務的復執(zhí)行，如把兩個位數(shù)相乘九九表。們將會看，迭代在們所要討的算法中了重要作。歐幾里算法：迭歐幾里得法是說明法本質的好也是最用的例子這個算法以追溯到元前 3 世紀。歐里得用它計算兩個整數(shù)的最公約數(shù)（gcd）。當我們最開遇到兩個整數(shù) a 和 b 的最大公約時，它是義為一個整數(shù)，而同為 a 和 b 的因數(shù)。然，為了很目的，定它為具有下兩個性的唯一的數(shù) d 更好。這兩性質就是首先，d 是 a 和 b 的一個因數(shù)；次，如果 c 是 a 和 b 的另一個數(shù)，則 d 可以被 c 所整除。歐幾里的《幾何本》卷 VII 的前兩個命題出了求 d 的方法，其中第一命題如下"給定了兩個不相等數(shù)、從較的一數(shù)不地減去較的一數(shù)，果余下的位，都不量度前數(shù)直到余下數(shù)為一單為止，這，原來的為互質。" 換句話說，如果輾相減得到數(shù) 1，則 gcd 為 1。這時，就說來的兩個互質（或為素數(shù)）輾轉相減現(xiàn)在我們一般地描歐幾里得法，它是于以下兩觀察的：1）如果 a=b，則 a 和 b 的 gcd 就是 b（或 a）。（2）d 是 a 和 b 的公約數(shù)，當且僅它也是 a-b 和 b 的公約數(shù)。現(xiàn)在要求 a 和 b 的 gcd，而且設 a≥b。如果 a=b，則觀察（1）告訴我，gcd 就是 b。若不然，察（2）告訴我們，果求 a-b 和 b 的 gcd 也會得到同樣的案。現(xiàn)在 a_1 是 a-b 和 b 中較大的個，而 b_1 則為其中較小一個，然再求兩數(shù) gcd。不過，現(xiàn)兩數(shù)中較的一個， a_1，小于原來數(shù)中較大一個，即 a。這樣我們就可以上面的程再重復一：若 a_1=b_1，則 a_1 和 b_1 的 gcd，亦即 a 和 b 的 gcd 是 b_1，若不然，把 a_1 換成 a_1-b_1，再來組織 a_1-b_1 和 b_1，總之，大的一個放在前面然后再繼下去，這叫做 " 輾轉相減 "。為了使這個程序夠進行下，還有一觀察是需的，這就下面的關正整數(shù)的個基本事，有時稱良序原理嚴格下降正整數(shù)序 a_0 > a1 > a2 >… 必為有限序列因為上面迭代程序好產生了個嚴格下序列，這迭代最終定會停止這就意味在某一點必有 a_k=b_k，而這個共值就是 a 和 b 的 gcd。歐幾里得算法的程圖歐幾得除法通對于歐幾得算法的述與此稍不同?？?應用一種復雜的程，稱為歐里得除法也就是帶除法），可以大大少算法的數(shù)，這種法也稱為轉相除法這個程序基本事實：若 a 和 b 是兩個正整，則必存唯一的整 q 和 r，使得數(shù) q 稱為商，而 r 稱為余數(shù)。上面的點說明（1）和（2）現(xiàn)在要代若 r=0，則 a 和 b 的 gcd 就是 b。a 和 b 的 gcd 與 b 和 r 的 gcd 是相同的。這一次在第一步用（b，r）代替（a，b）。如果 r≠0，則還要第二步，用（r，r_1）來代替（b，r），r1 是用 r 去除 b 所得的余，所以 r_1r>m>r1>r2≥0）。再用一次良原理，即這個程序過有限步一定停止而最后一非零的余就是 a 和 b 的 gcd。不難看到這兩種方，就求 gcd 而言是等價的但就算法言則有很區(qū)別。例，設 a=103 438，b=37。如果用輾轉相法，就要 103 438 中累次減去 37，一直到余下的數(shù)小于 37 為止。這個差數(shù) 103438 除以 37 的余數(shù)是一的，而如用第二種法，一次可以得到。這樣，用第二種法的理由在于用累減法來求法的余數(shù)非常低效的。效率的收益在踐上是很要的，第種方法給的是多項時間算法而第一種法所需的是指數(shù)長時間。推歐幾里得法可以推到許多其背景下，要有加法減法和乘的概念就。例如它一個變體可以用于斯整數(shù)環(huán)就是形如 a＋ bi，而其中 a，b 為整數(shù)的復所成的環(huán)它也可以于系數(shù)為數(shù)的多項環(huán)中（就而論，系在任意域也行）。有一個要，就是要夠定義帶除法的類物，有了一點以后算法就與整數(shù)情況算法基本相同了。如下面的題：設 A 和 B 是兩個任多項式，且 B 不是零多項、則必存兩個多項 Q 和 R。使得或者 R=0，或者 R 的次數(shù)小于 B 的次數(shù)。正歐幾里得《幾何原》中提到那樣，也以對于一數(shù)（a，b）當 a 和 b 不一定是整時實行這程序。容驗證，當僅當比 a / b 是有理數(shù)，這個程會停下來這個觀點導到連分的概念。 17 世紀以前，有特別地究過它，是其中的想根源可追溯到阿米德。阿米德計算 π 的方法：逼近和限性圓周和圓的直的比值是個常數(shù)，自從 18 世紀以來就記作 π?，F(xiàn)在我來看一看基米德怎在公元前 3 世紀就得到了這比值的經的近似值 22/7。若在圓內一個內接正多邊形其頂點都圓周上）又作其外的正多邊（其邊都圓周的切），再計這些多邊的周長，會得到 x 的下界與上界，因圓的周長定大于任內接多邊的周長，小于任意切多邊形周長。阿米德從正邊形開始然后，每把多邊形邊數(shù)加倍得到了越越精確的下界。他到九十六形為止，到了π 的逼近這個程中顯然及迭代。是稱它為個算法對對？嚴格說，它不一個算法不論取多邊的多邊，所得到僅是 π 的近似值所以這個程不是有的。然而們確實得了一個可近似計算 π 到任意精確度的法。例如如果想得 π 的一個準確到數(shù)十位的似值，經有限多步后，這個法會給出個我們想的近似值重要的是這個過程收斂的。是說，重的在于由代得出之可以任意接近于 π。這個方的幾何來可以用來明這個收性，而 1609 年德國人作了 202 邊形（基本上用阿米德的方），得到 π 的精確到小數(shù) 35 位的近似值。然，逼近 π 的算法與阿基米德算兩個正數(shù)的 gcd 的算法有一個明的區(qū)別。歐幾里得樣的算法常稱為離算法，而用來計算整數(shù)值的值算法相立。牛頓-拉夫森方：遞推公1670 年前后、頓提出了個求方程根的方法而且就方 x^3-2x-5=0 解釋了他的方法他的解釋下面的一觀察開始根 x 近似地等于 2。于是他寫出 x=2+p，并用 2＋p 代替原方程的 x，而得到了個關于 p 的方程。這個新方算出來是為 x 接近于 2，所以 p 很小，而就略去了 p^3 和 6p^2 來估計 p。這就給了他 p 的方程 10p-1=0，即 p=1/10。這當然是一個準解，但是給了牛頓于根的新更好的近值：x=2.1。然后牛頓就重這個過程令 x=2.1＋q，代入原方以后又給了一個關 q 的方程，近似解這個方，又把他近似解精化了，于得到 q 的估計為-0.0054，所以 x 的下一個近似值 2.0946。盡管如此，我怎么能確這個過程收斂于 x 呢？讓我們更仔細考察這個法。切線收斂性牛的方法可從幾何上函數(shù) f 的圖像來釋，雖然頓本人并有這樣做f（x）=0 的每一個根 x 都對應于數(shù) y=f（x）的曲線和 x 軸的一個點。如果根 x 的一個近似 a 開始，而且和面做的一，設 p=x- a，于是可以 a+p 代替 x 而得到一新的函數(shù) g（p），也就是說原點（0，0）有效地移到了（a，0）處。然后把 p 的所有高次冪都略，只留下數(shù)項和線項，這樣得到了函 g 的最佳的線性近 —— 從幾何上，這就是 g 在點（0，g（0））處的線。這樣對于 p 所得到的似值就是數(shù) y 在點（0，g（0））處的切線與 x 軸的交點。再在坐標上加個 a，也就是讓原回到原來（0，0）處，這樣 a＋p 就給出了 f 的根的新近似值。就是牛頓方法稱為線法的原。牛頓方從上圖可看到，再一次切線逼近，如曲線 y=f（x）與 x 軸的交點在 a 點以及 f 在點（a，f（a））處的線與 x 軸的交點即上圖中橫坐標為 a+p 的點，即根近似值）間，則第次的近似（即 a＋p＋q）肯定比第一的近似值 a＋p 好（這里稱 a 為根的零次近似。回到牛的例子，以看到牛選取 a=2 并不是上面所說情況。但從下一個似值 2.1 開始，以下所有近似值就是這個情了。從幾上看，如點（a，f（a））位于 x 軸的上方，且 y=f（x）的曲線在凸部 x 軸相交，或者（a，f（a））在 x 軸的下方，而且 y=f（x）曲線在部與 x 軸相交，會出現(xiàn)這有利的情。初始的近（即零近似）的擇顯然是重要的，且提出了妙的未曾到的問題如果我們慮復多項的復根，就更加清了。牛頓方法很容適應這個廣泛的背。設 z 是一個復項式的復，而 z_0 是初始的逼近，是牛頓方將給出一序列 z_0，z_1，z_2…… 它可能收斂于 z，也可能收斂。我定義根 z 的吸引區(qū)域為這樣初始逼近 z_0 的集合，使所得到的列確實收于 z，并且記這個域為 A（z）。怎樣來決定 A（z）呢？第一個問個問題的是凱萊，間是 1879 年。他注意到對于二次項式，這問題是很易的，但次數(shù)為 3 或者更大時，問題很困難了例如多項 z^2-1 的根 ±1 的吸引區(qū)域分是復平面以鉛直軸界的兩個平面，但 z^3-1 的三個根 1，w，w^2 的相應的引區(qū)域就極復雜的合。這些合是由儒亞在 1918 年描述的，而在稱為分集合。遞公式牛頓法的每一段都會產一個新方。但是拉森指出實上并無必。他就特的例子給在每一步可以使用單一一個式。但是的基本的察可以一地適用，出可以用每一個情的一般公，而這個式用切線解釋就可容易得出事實上，線 y=f（x）在 x 坐標為 a 處的切線方程它與 x 軸的交點橫坐標是 a-f（a）/f'（a）。我們現(xiàn)在所說牛頓-拉夫森方法就指的這個式。我們一個初始近 a_0=a 開始再用這個推公式得這樣就得一個逼近序列，在情況下，就是前面的 z_0，z_1，z_2，…。作為一例子，考函數(shù) f（x）=x^2-c。這時，牛頓法就給出 c 的平方根根號 c 的一串近似值，遞公式現(xiàn)在了在上面一般公式把 f 換成 x^2-c 即得。這個近平方根的法，公元 1 世紀的亞歷山大亞的海倫已經知道本文來自信公眾號老胡說科 （ID：LaohuSci），作者：我是老?
