方程求根計(jì)算方法

方程求根計(jì)算方法第1頁，共128頁，2023年，2月20日，星期五§2.1問題的提出

第二章方程求根第2頁，共128頁，2023年，2月20日，星期五§2.1問題的提出實(shí)際問題f(x)=0,f:R→R定義：如存在x*使得f(x*)=0則稱x*為方程的根或函數(shù)f(x)的零點(diǎn)。特別地，如果m=1x*為f(x)=0的單根或f(x)的單零點(diǎn)m>1x*為f(x)=0的m重根或f(x)的m重零點(diǎn)第3頁，共128頁，2023年，2月20日，星期五§2.1問題的提出f(x)是n次代數(shù)多項(xiàng)式f(x)=0是n次代數(shù)方程f(x)是超越函數(shù)f(x)=0是超越方程第4頁，共128頁，2023年，2月20日，星期五§2.1問題的提出例如:1.n次代數(shù)方程:2.超越方程:第5頁，共128頁，2023年，2月20日，星期五§2.1問題的提出Remarks:1.非線性方程的根可為實(shí)根或復(fù)根；復(fù)根總是共軛出現(xiàn)。2.Galois(伽羅瓦)在1830年就已經(jīng)從理論上證明對(duì)于次數(shù)高于4次的代數(shù)方程，其根不能用方程系數(shù)的解析式表示；一般的超越方程更沒有解析的求根公式?。。。。。。?。第6頁，共128頁，2023年，2月20日，星期五§2.1問題的提出3.根的個(gè)數(shù)。n次代數(shù)方程有?個(gè)根(包括實(shí)根和復(fù)根)n為奇數(shù)時(shí),至少有一個(gè)根是實(shí)根

對(duì)于超越方程,根可能0~無窮個(gè)第7頁，共128頁，2023年，2月20日，星期五§2.1問題的提出

方程求根步驟(1)對(duì)給定區(qū)間進(jìn)行掃描,確定僅存在單根的區(qū)間,此區(qū)間內(nèi)的任意一點(diǎn)可視為根的近似值。(2)用迭代方法使根精確到所要求精度。第8頁，共128頁，2023年，2月20日，星期五§2.1問題的提出

掃描流程第9頁，共128頁，2023年，2月20日，星期五§2.1問題的提出【歷史注記】人們很早就探索了高次方程的數(shù)值解的求法。巴比倫泥板中有平方表和立方表，利用它們可以解某些特殊的二次和三次方程。中國古人相當(dāng)系統(tǒng)地解決了求高次方程數(shù)值解的問題，《九章算術(shù)》以算法形式給出了二次方程及正系數(shù)三次方程正根的具體計(jì)算程序；7世紀(jì)王孝通也給出了求三次方程正根的數(shù)值解法；11世紀(jì)賈憲在《黃帝九章算法細(xì)草》中創(chuàng)“開方作法本源圖”,用“立成釋鎖法”解三次和三次以上高次方程,同時(shí)他又提出一種更為簡便的“增乘開方法”；13世紀(jì)秦九韶在《數(shù)書九章》中的“正負(fù)開方術(shù)”最后完成，提供了一個(gè)用算籌布列解任何次數(shù)字方程的可行算法。第10頁，共128頁，2023年，2月20日，星期五§2.1問題的提出阿拉伯人對(duì)高次代數(shù)方程的數(shù)值解法亦有研究，花拉子米(9世紀(jì))第一個(gè)給出了二次方程的一般解法,奧馬海亞姆(1100年)給出了一些特殊三次方程的解法。1541年塔爾塔利亞得到三次方程的一般解法。1545年卡爾達(dá)諾在其名著《大術(shù)》一書中發(fā)展了塔爾塔利亞的這一成果，并記載了費(fèi)拉里得到的四次方程的一般解法。牛頓在1736年出版的《流數(shù)法》一書中，給出了著名的高次代數(shù)方程的一種數(shù)值解法,1690年Raphson

也提出了類似的方法，它們的結(jié)合就是現(xiàn)代常用的方法－牛頓法(也叫Newton-Raphson方法)。它是一種廣泛用于高次代數(shù)方程求解的迭代法，亦稱為切線法，并不斷產(chǎn)生新的變形,第11頁，共128頁，2023年，2月20日，星期五§2.1問題的提出如修正牛頓法，擬牛頓法等。1797年，高斯給出“代數(shù)基本定理”，指出高次代數(shù)方程根的存在性。1819年，霍納提出求高次代數(shù)方程數(shù)值解的另一種方法－－霍納法，其思想及計(jì)算程序與秦九韶的方法近似，類似的方法魯非尼在1804年也提出過，霍納法也有廣泛的應(yīng)用，它的現(xiàn)代改進(jìn)形式叫劈因子法。現(xiàn)在常用的代數(shù)方程數(shù)值解法還有伯努利法和勞斯表格法。第12頁，共128頁，2023年，2月20日，星期五§2.1問題的提出

有多種數(shù)值算法可以求解非線性方程，我們?cè)诒菊聦W(xué)習(xí)其中得幾種，它們是：

二分法(bisectionmethod)迭代法(iterationmethod)牛頓法(Newtonmethod)牛頓下山法(Newtondownhillmethod)。第13頁，共128頁，2023年，2月20日，星期五牛頓(1)牛頓(NewtonIsaac1643.1.4-1727.3.31)：英國數(shù)學(xué)家、物理學(xué)家、天文學(xué)家、自然哲學(xué)家。生于林肯郡伍爾索普，卒于倫敦。早年在格蘭瑟姆讀書，1661年以優(yōu)異成績考入劍橋大學(xué)三一學(xué)院，數(shù)學(xué)上受教于巴羅。1664年畢業(yè)后曾為躲避鼠疫回鄉(xiāng)，1665－1666年做出流數(shù)法、萬有引力和光的分析三大發(fā)明，年僅23歲。1667年回劍橋在三一學(xué)院執(zhí)教。1669年繼巴羅之后任盧卡斯數(shù)學(xué)教授職位。晚年致力于哲學(xué)和公務(wù)，1696年任造幣廠監(jiān)督，3年后任廠長。1703年當(dāng)選為英國皇家學(xué)會(huì)主席。他在數(shù)學(xué)上以創(chuàng)建微積分學(xué)而著名，其流數(shù)法始于1665年，系統(tǒng)敘述于《流數(shù)法和無窮級(jí)數(shù)》(1671年完第14頁，共128頁，2023年，2月20日，星期五成，1736年出版)，首先發(fā)表在《自然哲學(xué)的數(shù)學(xué)原理》(1687)中。其中借助運(yùn)動(dòng)學(xué)中描述的連續(xù)量及其變化率闡述他的流數(shù)理論，并創(chuàng)用字母上加一點(diǎn)表示流動(dòng)變化率。討論的基本問題是：已知流量間的關(guān)系，求它們的流數(shù)的關(guān)系以及逆運(yùn)算，確定了微分與積分這兩類運(yùn)算的互逆關(guān)系，即微積分學(xué)基本定理。此外，他還論述了有理指數(shù)的二項(xiàng)式定理(1664年)，n次代數(shù)方程根的m次冪和的公式(1707年)，數(shù)論、解析幾何學(xué)、曲線分類、變分法等問題。在物理學(xué)上發(fā)現(xiàn)了萬有引力定律(1666-1684)，并據(jù)此指出行星運(yùn)行成橢圓軌道的原因。1666年用三棱鏡實(shí)驗(yàn)光的色散現(xiàn)象，1668年發(fā)明并牛頓(2)第15頁，共128頁，2023年，2月20日，星期五親手制作了第一具反射望遠(yuǎn)鏡。在哲學(xué)上深信物質(zhì)、運(yùn)動(dòng)、空間和時(shí)間的客觀存在性，堅(jiān)持用觀察和實(shí)驗(yàn)方法發(fā)現(xiàn)自然界的規(guī)律，力求用數(shù)學(xué)定量方法表述的定律說明自然現(xiàn)象，其科學(xué)研究方法支配后世近300年的物理學(xué)研究。牛頓(3)第16頁，共128頁，2023年，2月20日，星期五牛頓像(1)第17頁，共128頁，2023年，2月20日，星期五牛頓像(2)第18頁，共128頁，2023年，2月20日，星期五牛頓像(3)第19頁，共128頁，2023年，2月20日，星期五牛頓像(4)第20頁，共128頁，2023年，2月20日，星期五牛頓像(5)第21頁，共128頁，2023年，2月20日，星期五牛頓像(6)第22頁，共128頁，2023年，2月20日，星期五牛頓像(7)第23頁，共128頁，2023年，2月20日，星期五牛頓像(8)第24頁，共128頁，2023年，2月20日，星期五高斯(1)高斯(Gauss,CarlFriedrich1777.4.30-1855.2.23)：德國數(shù)學(xué)家、物理學(xué)家、天文學(xué)家。生于不倫瑞克，卒于格丁根。高斯是近代數(shù)學(xué)奠基者之一，在歷史上影響之大，可以和阿基米德、牛頓、歐拉并列。他幼年時(shí)就表現(xiàn)出超人的數(shù)學(xué)天才。1795年進(jìn)入格丁根大學(xué)學(xué)習(xí)。第二年他發(fā)現(xiàn)正十七邊形的尺規(guī)作圖法，并給出可用尺規(guī)作出的正多邊形的條件，解決了歐幾里得以來懸而未決的問題。1798年轉(zhuǎn)入黑爾姆施泰特大學(xué)，1799年獲博士學(xué)位。1807年以后一直在格丁根大學(xué)任教授。高斯的數(shù)學(xué)研究幾乎遍及所有領(lǐng)域，在數(shù)論、代數(shù)學(xué)、非歐幾何、復(fù)變函數(shù)和微分幾何等方面都第25頁，共128頁，2023年，2月20日，星期五做出了開創(chuàng)性貢獻(xiàn)。他還把數(shù)學(xué)應(yīng)用于天文學(xué)。大地測(cè)量學(xué)和磁學(xué)的研究，發(fā)明了最小二乘法原理。高斯的數(shù)論研究總結(jié)在《算術(shù)研究》(1801)中，這本書奠定了近代數(shù)論的基礎(chǔ)，它不僅是數(shù)論方面劃時(shí)代之作，也是數(shù)學(xué)史上不可多得的經(jīng)典著作之一。高斯對(duì)代數(shù)學(xué)的重要貢獻(xiàn)是證明了代數(shù)基本定理，他的存在性證明開創(chuàng)了數(shù)學(xué)研究的新途徑。高斯在1816年左右就得到非歐幾何的原理，發(fā)現(xiàn)橢圓函數(shù)的雙周期性，但這些工作在他生前都沒有發(fā)表出來。他還深入研究復(fù)變函數(shù)，建立了一些基本概念并發(fā)現(xiàn)了著名的柯西積分定理。1828年高斯出版了《關(guān)于曲面的一般研究》，全面系統(tǒng)闡述了空間高斯(2)第26頁，共128頁，2023年，2月20日，星期五曲面的微分幾何學(xué)，并提出了內(nèi)蘊(yùn)曲面理論。高斯的曲面理論后來由黎曼進(jìn)一步發(fā)展。高斯一生共發(fā)表155篇學(xué)術(shù)論文，他對(duì)待學(xué)問十分嚴(yán)謹(jǐn)，只是把他自己認(rèn)為是十分成熟的作品發(fā)表出來。其著作還有《地磁概論》(1839)和《論與距離平方成反比的引力和斥力的普遍定律》(1840)等。高斯(3)第27頁，共128頁，2023年，2月20日，星期五高斯像(1)第28頁，共128頁，2023年，2月20日，星期五高斯像(2)第29頁，共128頁，2023年，2月20日，星期五高斯像(3)第30頁，共128頁，2023年，2月20日，星期五高斯像(4)第31頁，共128頁，2023年，2月20日，星期五§2.2二分法第二章方程求根第32頁，共128頁，2023年，2月20日，星期五§2.2二分法

定義：如果函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，且f(a)f(b)<0，則方程在區(qū)間[a,b]上一定有實(shí)根，[a,b]叫方程的有根區(qū)間。【注記】f(a)f(b)<0只保證有實(shí)根,但并不保證根是唯一,即不保證是單根,也不排斥f(a)f(b)>0時(shí)在[a,b]上有根的情形。即，f(a)f(b)<0對(duì)于在[a,b]上有實(shí)根是充分的,但不必要；f(a)f(b)<0對(duì)于在[a,b]上有唯一單實(shí)根不充分也不必要。如圖所示：第33頁，共128頁，2023年，2月20日，星期五b僅有一個(gè)實(shí)根af(x)x有多個(gè)實(shí)根abxf(x)f(a)f(b)>0但有實(shí)根abxf(x)§2.2二分法第34頁，共128頁，2023年，2月20日，星期五

二分法實(shí)際上是一種簡單的區(qū)間求根方法(Bracketingmethod)，區(qū)間法的基本思想是把方程的根限定在一個(gè)區(qū)間中，區(qū)間長度不斷縮小，當(dāng)區(qū)間長度充分小時(shí)就得到了近似解。二分法就是簡單地每次把區(qū)間從中間一分為二，區(qū)間長度每次減半。§2.2二分法第35頁，共128頁，2023年，2月20日，星期五二分法具體作法：

二分初始選取區(qū)間[a0,b0]，使得f(a0)f(b0)<0，然后把區(qū)間二等分，等分點(diǎn)為(a0+b0)/2，如果f((a0+b0)/2)=0，則得到了方程的根，如果f(a0)f((a0+b0)/2)<0，則說明根在區(qū)間[a0,(a0+b0)/2],令a1=a0，及b1=(a0+b0)/2,得到更新的區(qū)間[a1,b1]；否則，f(b0)f((a0+b0)/2)>0，說明根在區(qū)間[(a0+b0)/2,b0]，令a1=(a0+b0)/2,b1=b0則得到更新區(qū)間[a1,b1]。§2.2二分法第36頁，共128頁，2023年，2月20日，星期五不斷重復(fù)這個(gè)過程直到，為給定精度，于是得到方程根。

新區(qū)間長度總是舊區(qū)間長度的一半，二分k次后區(qū)間假設(shè)為[ak,bk]，其長度為，§2.2二分法第37頁，共128頁，2023年，2月20日，星期五所以對(duì)于精度，由11111得到循環(huán)次數(shù)為nnn§2.2二分法第38頁，共128頁，2023年，2月20日，星期五二分法的特點(diǎn)：§2.2二分法2)實(shí)施簡單，僅需函數(shù)值1)收斂總能得到保證3)收斂速度慢第39頁，共128頁，2023年，2月20日，星期五二分法算法:

f1=f(a0),f2=f(b0)(3)ifthenstop.ifthenstop.(4)ifthenstop.§2.2二分法(2)iff1f2>0,初始區(qū)間選擇不合適,stop

給定f(x),[a0,b0],第40頁，共128頁，2023年，2月20日，星期五(5)x=(a0+b0)/2,f=f(x)ifthenstop.(6)Iff1f<0,thenb0=x,f2=felsea0=x,f1=f,endif(7)Goto(3)§2.2二分法第41頁，共128頁，2023年，2月20日，星期五定理2.1：如果區(qū)間[a,b]上的連續(xù)函數(shù)f應(yīng)用二分算法,f(a)f(b)<0，則n步后將算出一個(gè)近似根，其誤差至多為§2.2二分法第42頁，共128頁，2023年，2月20日，星期五

例2.1用二分法求方程f(x)=x3+4x2-10=0在區(qū)間[1,1.5]上的根，使得根誤差不大于0.005，需要作幾次二分？§2.2二分法解：由f(1)=-5,f(1.5)=2.375,且當(dāng)時(shí)，知方程在所給區(qū)間內(nèi)有唯一根。第43頁，共128頁，2023年，2月20日，星期五§2.2二分法

由

得到

所以n=6就可以得到誤差不大于0.005的近似根。作業(yè)：證明1-x-sinx=0在[0,1](x單位為弧度)內(nèi)有唯一根，使用二分法求誤差不大于5e-5的根要迭代多少次？第44頁，共128頁，2023年，2月20日，星期五§2.2二分法【思考題2.1】如何編程用二分法計(jì)算區(qū)間內(nèi)的N個(gè)實(shí)根(假設(shè)至少有N個(gè)實(shí)根)。第45頁，共128頁，2023年，2月20日，星期五§2.3迭代法(iterationmethods)

第二章方程求根第46頁，共128頁，2023年，2月20日，星期五§2.3迭代法基本思想:設(shè)欲求方程f(x)=0的根,變成形式,或,于是方程f(x)=0的根是直線y=x與曲線的交點(diǎn)。用數(shù)學(xué)式表示迭代公式為：如果迭代序列{xk}極限存在，則迭代收斂，并且；如果迭代序列{xk}極限不存在，則稱迭代過程發(fā)散。第47頁，共128頁，2023年，2月20日，星期五解法1：將原方程寫成x=x3-1。取迭代函數(shù)構(gòu)造迭代格式例2.2用迭代法求x3-x-1=0在x0=1.5附近的根?！?.3迭代法以初值x0=1.5代入計(jì)算，得到如下結(jié)果第48頁，共128頁，2023年，2月20日，星期五§2.3迭代法k0123…xk1.52.37512.3961903.78…很明顯，xk發(fā)散，方法失敗。第49頁，共128頁，2023年，2月20日，星期五§2.3迭代法解法2：將原方程寫成。取迭代函數(shù)構(gòu)造迭代格式取初值x0=1.5，計(jì)算得到第50頁，共128頁，2023年，2月20日，星期五§2.3迭代法k0123…78xk1.51.3571.3301.325…1.32471.3247可見迭代8次，近似解已收斂于1.3247。第51頁，共128頁，2023年，2月20日，星期五§2.3迭代法解法1和解法2的情況可用下面兩個(gè)圖示意：

解法1解法2第52頁，共128頁，2023年，2月20日，星期五

定理2.2假設(shè)迭代函數(shù)在[a,b]上存在一階連續(xù)導(dǎo)數(shù),且滿足下列兩個(gè)條件§2.3迭代法(1)

對(duì)于任意有(2)存在正數(shù)L<1，使對(duì)于任意有第53頁，共128頁，2023年，2月20日，星期五§2.3迭代法(a)方程在[a,b]上有唯一根(b)對(duì)于[a,b]內(nèi)任意初始值,迭代均收斂于方程根(c)且有誤差估計(jì)則：第54頁，共128頁，2023年，2月20日，星期五§2.3迭代法條件(2)意味著斜率小于1,即曲線比直線y=x更平。

幾何解釋：

條件(1)意味著初始及后續(xù)每次迭代函數(shù)值仍在初始區(qū)間[a,b]內(nèi)；第55頁，共128頁，2023年，2月20日，星期五§2.3迭代法(a)作函數(shù)。所以必有使

定理證明：即第56頁，共128頁，2023年，2月20日，星期五§2.3迭代法再證根的唯一性。假設(shè)在區(qū)間[a,b]上存在兩個(gè)根，則由微分中值定理及條件(2)知存在由于L>0，必有，即根唯一。第57頁，共128頁，2023年，2月20日，星期五§2.3迭代法(b)由微分中值定理知，存在使

反復(fù)利用上式，有

因?yàn)長<1，所以時(shí)

即第58頁，共128頁，2023年，2月20日，星期五§2.3迭代法(c)誤差。注意到于是所以第59頁，共128頁，2023年，2月20日，星期五§2.3迭代法把代入上式得于是第60頁，共128頁，2023年，2月20日，星期五§2.3迭代法

可以看出，L越小收斂越快，當(dāng)L接近1時(shí)，收斂很慢。因?yàn)長為常數(shù)，所以一般用來判斷迭代收斂。第61頁，共128頁，2023年，2月20日，星期五§2.3迭代法第62頁，共128頁，2023年，2月20日，星期五§2.3迭代法第63頁，共128頁，2023年，2月20日，星期五§2.3迭代法第64頁，共128頁，2023年，2月20日，星期五§2.3迭代法第65頁，共128頁，2023年，2月20日，星期五§2.3迭代法

定義如果存在鄰域，迭代過程對(duì)于任意初始值收斂，則稱迭代過程在根附近具有局部收斂性。第66頁，共128頁，2023年，2月20日，星期五§2.3迭代法

定理2.3：設(shè)在方程根x*附近有連續(xù)一階導(dǎo)數(shù)，且，則迭代過程具有局部收斂性。使得利用微分中值定理有證明：取x*附近的一個(gè)鄰域第67頁，共128頁，2023年，2月20日，星期五§2.3迭代法由于即于是取滿足(1)對(duì)任意，；(2)對(duì)任意

所以，迭代過程具有局部收斂性。第68頁，共128頁，2023年，2月20日，星期五迭代法的收斂速度§2.3迭代法

定義：當(dāng)時(shí)，有，(且為常數(shù))，則稱迭代過程是p階收斂。特別地，當(dāng)p=1,0<c<1時(shí)，稱作線性收斂；當(dāng)p>1時(shí)，稱作超線性收斂；

p=2時(shí)稱作平方收斂。其中稱作迭代誤差。第69頁，共128頁，2023年，2月20日，星期五§2.3迭代法由微分中值定理有簡單迭代法收斂速度一般是線性的。簡單迭代法的收斂速度。第70頁，共128頁，2023年，2月20日，星期五§2.3迭代法例2.3設(shè)兩個(gè)迭代格式分別是線性收斂和平方收斂的，且若取精度，試估計(jì)這兩個(gè)迭代格式各所需的迭代次數(shù)。解：第71頁，共128頁，2023年，2月20日，星期五§2.3迭代法得

由所以線性迭代格式需迭代54次。第72頁，共128頁，2023年，2月20日，星期五§2.3迭代法于是所以故平方收斂的迭代格式只需迭代6次。第73頁，共128頁，2023年，2月20日，星期五§2.3迭代法定理2.4：若在的根附近有連續(xù)

階導(dǎo)數(shù)且p-1階導(dǎo)數(shù)全為零，,則p階局部收斂，且有如果p=1，要求第74頁，共128頁，2023年，2月20日，星期五§2.3迭代法證明：由定理2.3知，迭代格式局部收斂。應(yīng)用泰勒級(jí)數(shù)展開并注意到p-1導(dǎo)數(shù)全為零，有第75頁，共128頁，2023年，2月20日，星期五§2.3迭代法于是或第76頁，共128頁，2023年，2月20日，星期五§2.3迭代法于是第77頁，共128頁，2023年，2月20日，星期五§2.3迭代法例2.4判斷能不能直接用簡單迭代法求解下列的方程？解：判斷方程能否用簡單迭代法求根，要看在根的鄰域是否有第78頁，共128頁，2023年，2月20日，星期五§2.3迭代法對(duì)于(1)，所以(1)可以用簡單迭代法求解。對(duì)于(2)，可知f(1)>0,f(3)<0,所以[1,3]為有根區(qū)間。所以(2)不能用簡單迭代法求解。第79頁，共128頁，2023年，2月20日，星期五§2.3迭代法例2.5證明對(duì)于任何初始值,由迭代公式所產(chǎn)生的序列都收斂于的根.證明:記則(1)當(dāng),故序列收斂于的根.第80頁，共128頁，2023年，2月20日，星期五§2.3迭代法(2)當(dāng)對(duì)于任意,

把看作新的迭代初值,由(1)知命題得證.第81頁，共128頁，2023年，2月20日，星期五§2.3迭代法例2.6利用迭代格式證明證明:考慮迭代格式第82頁，共128頁，2023年，2月20日，星期五§2.3迭代法

則

記第83頁，共128頁，2023年，2月20日，星期五§2.3迭代法

當(dāng)時(shí),1.

所以迭代格式產(chǎn)生的序列收斂于方程

在[0,2]內(nèi)的唯一根x=2,即第84頁，共128頁，2023年，2月20日，星期五§2.3迭代法作業(yè)：證明用迭代格式

產(chǎn)生的序列，對(duì)于均收斂于作業(yè)：為求方程在附近的一個(gè)根，將方程改寫成為下列各式,試分析各格式收斂性.第85頁，共128頁，2023年，2月20日，星期五§2.4牛頓法(Newtonmethod)

第二章方程求根第86頁，共128頁，2023年，2月20日，星期五【歷史注記】1685年Wallis出版了一本名為《代數(shù)》的書，描述了由牛頓發(fā)明的一種求解方程的方法。1690年Raphson也發(fā)表了這個(gè)方法，但略有修改。于是現(xiàn)在通常把這個(gè)方法叫牛頓法或Newton-Raphson法。事實(shí)上，牛頓本人在1669年就討論了這個(gè)方法，并以方程x3-2x-5=0為例作了說明，Wallis在其著作中也使用了這個(gè)例子，此后每一個(gè)學(xué)數(shù)值分析的學(xué)生都認(rèn)識(shí)這個(gè)歷史悠久的方程?！?.4牛頓法第87頁，共128頁，2023年，2月20日，星期五

牛頓法的解釋：使用牛頓法時(shí)總假設(shè)函數(shù)f(x)是一階可微的，這在幾何上f(x)表示的圖形(曲線)在每個(gè)點(diǎn)上都有確定的斜率，因而有唯一切線?，F(xiàn)在我們利用線性化的思想，設(shè)曲線f(x)上某一點(diǎn)(x0,f(x0))有一條切線，該切線在該點(diǎn)的近旁是f(x)曲線的一個(gè)很好近似(以直代曲)。§2.4牛頓法第88頁，共128頁，2023年，2月20日，星期五§2.4牛頓法第89頁，共128頁，2023年，2月20日，星期五

從分析觀點(diǎn)來講，這種以直線代曲線就意味著切線線性函數(shù)在x0的近旁接近于函數(shù)f(x)，并且在x0處l(x)和f(x)值相等。因此，可取l(x)的零點(diǎn)為f(x)零點(diǎn)的一個(gè)近似。§2.4牛頓法第90頁，共128頁，2023年，2月20日，星期五l(x)的零點(diǎn)為x1=x0-f(x0)/f’(x0)。這樣，從初始點(diǎn)x0出發(fā)，由上式就得到了一個(gè)新點(diǎn)，重復(fù)這個(gè)過程(迭代)，就能產(chǎn)生一系列點(diǎn)§2.4牛頓法如果收斂的話，這個(gè)點(diǎn)列將趨向于f(x)的一個(gè)零點(diǎn)。第91頁，共128頁，2023年，2月20日，星期五還可以用另外的方式說明牛頓法。假設(shè)x0是對(duì)于f(x)的一個(gè)根的近似，可以想象，如果給x0加上一個(gè)修正值h就可以成為f(x)的精確根，即f(x+h)=0。如果f(x)的各階導(dǎo)數(shù)在x0處存在，則f(x)在x0處泰勒展開為§2.4牛頓法用上式很難求出h，于是考慮線性化，對(duì)于上式進(jìn)行截?cái)嗟?2頁，共128頁，2023年，2月20日，星期五于是§2.4牛頓法得到一個(gè)新的近似根，重復(fù)這個(gè)過程就是牛頓法。第93頁，共128頁，2023年，2月20日，星期五回顧前面過程，可以發(fā)現(xiàn)，實(shí)際上并不需要有二階導(dǎo)數(shù)，因?yàn)槲覀冎皇褂昧颂├照归_的前兩項(xiàng)，僅要求在根的一個(gè)鄰域中導(dǎo)數(shù)連續(xù)即可?！?.4牛頓法牛頓法是方程求根十分重要和有效的方法，其基本思想是將非線性方程線性化構(gòu)造迭代公式。第94頁，共128頁，2023年，2月20日，星期五設(shè)方程f(x)=0有近似根xk，將函數(shù)f(x)在xk處一階泰勒展開§2.4牛頓法于是方程線性化為這個(gè)線性化方程的根為第95頁，共128頁，2023年，2月20日，星期五按照迭代法，其迭代函數(shù)為§2.4牛頓法牛頓法的收斂速度牛頓法可以看成迭代公式如果x*是f(x)=0的一個(gè)單根，則f(x*)=0，第96頁，共128頁，2023年，2月20日，星期五于是由上節(jié)定理知牛頓法有二階收斂速度。§2.4牛頓法【注記】可以證明對(duì)于重根情形，牛頓法是1階局部收斂。第97頁，共128頁，2023年，2月20日，星期五迭代收斂判據(jù)有：

§2.5牛頓法下山法第98頁，共128頁，2023年，2月20日，星期五①第k次迭代xk充分接近于方程根x*，②|f(xk)|充分小，接近于零。這兩個(gè)判據(jù)不等價(jià)，第一個(gè)能嚴(yán)格保證收斂，第二個(gè)并不能。雖然第一個(gè)判據(jù)很嚴(yán)格，但是實(shí)現(xiàn)起來有困難，因?yàn)閤*未知，第二個(gè)判據(jù)盡管不嚴(yán)格，但易于實(shí)現(xiàn)。后兩個(gè)判據(jù)在實(shí)際中采用較多。

§2.5牛頓法下山法第99頁，共128頁，2023年，2月20日，星期五牛頓法算法§2.4牛頓法以及最大迭代次數(shù)N。已知函數(shù)f(x)及f’(x),給定x0,第100頁，共128頁，2023年，2月20日，星期五§2.4牛頓法第101頁，共128頁，2023年，2月20日，星期五§2.4牛頓法第102頁，共128頁，2023年，2月20日，星期五例2.7用牛頓法求方程在x=0.5附近的根?！?.4牛頓法解：把方程寫成于是

取x0=0.5，得到第103頁，共128頁，2023年，2月20日，星期五§2.4牛頓法k0123xk0.50.571020.567160.56714用簡單迭代法得k0123…18xk0.50.606530.545240.57970…0.56714第104頁，共128頁，2023年，2月20日，星期五§2.4牛頓法例2.8用牛頓法求Leonardo方程的根,設(shè)x0=2，要求解：第105頁，共128頁，2023年，2月20日，星期五§2.4牛頓法k01…45xk21.6…1.3688081091.368808108

故【注】Leonardo在1225年研究了該方程，并得到x=1.368808107的結(jié)果，此時(shí)f(x)=-0.000000009，這在當(dāng)時(shí)是非常重要的結(jié)果，但無人知道他是如何得到的。第106頁，共128頁，2023年，2月20日，星期五例2.9用牛頓法求的近似值，精度?！?.4牛頓法解：化為求x2-115=0的正根，牛頓迭代公式為取初值x0=10，經(jīng)過4次迭代，得x*=10.723805第107頁，共128頁，2023年，2月20日，星期五【思考題】對(duì)于牛頓迭代公式，證明§2.4牛頓法第108頁，共128頁，2023年，2月20日，星期五§2.5牛頓下山法第二章方程求根第109頁，共128頁，2023年，2月20日，星期五

牛頓法的收斂性和初始迭代值有關(guān)，如果初始迭代值離方程根較近，則迭代收斂性可以保證；如果初始值距離方程根較遠(yuǎn)，則收斂過程可能發(fā)散。但是通常情況下很難給出一個(gè)離根較近的初始值，因?yàn)楦鶡o法預(yù)先知道?！?.5牛頓法下山法第110頁，共128頁，2023年，2月20日，星期五

我們發(fā)現(xiàn)這樣一個(gè)事實(shí)：通常在根附近|f(x)|是單調(diào)下降的，即越接近根，|f(x)|越小，所以|f(xk)|>|f(xk+1)|。于是我們把這個(gè)條件作為一個(gè)約束引入到迭代方程。滿足這個(gè)約束條件的算法叫下山法?！?.5牛頓法下山法第111頁，共128頁，2023年，2月20日，星期五

具體作法：先得到牛頓法結(jié)果把與xk作加權(quán)平均得到：

叫下山因子,時(shí)即為牛頓法。§2.5牛頓法下山法第112頁，共128頁，2023年，2月20日，星期五可以通過選取值使得|f(xk)|>|f(xk+1)|。通常先令開始，若上式不成立則減半，直到上式成立

如果已經(jīng)很小，上式仍不成立，則下山失敗。

意味著新的若不滿足下山條件，則加大上一步結(jié)果的權(quán)重?！?.5牛頓法下山法第113頁，共128頁，2023年，2月20日，星期五

例2.10用牛頓下山法求方程f(x)=x3-x-1=0在1.5附近的根，精確到7位有效數(shù)字，取x0=0.6。§2.5牛頓法下山法解：應(yīng)用牛頓下山公式第114頁，共128頁，2023年，2月20日，星期五§2.5牛頓法下山法kxkf(xk)010.6-1.3840001117.8999805716.42101/29.249990781.20070………1/321.140624-0.65