計算方法 (力學系本科生),第二章 方程求根 (Roots finding ),2.1 問題的提出,第二章 方程求根,2.1 問題的提出,實際問題,f(x)=0, f: R R,定義：如存在x*使得f(x*)=0,則稱x*為方程的根或函數(shù)f(x)的零點。,特別地，如果,m=1,x*為f(x)=0的單根或f(x)的單零點,m1,x*為f(x)=0的m重根或f(x)的m重零點,2.1 問題的提出,f(x)是n次代數(shù)多項式,f(x)=0是n次代數(shù)方程,f(x)是超越函數(shù),f(x)=0是超越方程,2.1 問題的提出,例如:,1. n次代數(shù)方程:,2. 超越方程:,2.1 問題的提出,Remarks:,1. 非線性方程的根可為實根或復根；復根總是共軛出現(xiàn)。,2. Galois(伽羅瓦)在1830年就已經(jīng)從理論上證明對于次數(shù)高于4次的代數(shù)方程，其根不能用方程系數(shù)的解析式表示；一般的超越方程更沒有解析的求根公式！1。,2.1 問題的提出,3. 根的個數(shù)。,n次代數(shù)方程有?個根(包括實根和復根),n為奇數(shù)時, 至少有一個根是實根,對于超越方程,根可能0無窮個,2.1 問題的提出,方程求根步驟,(1) 對給定區(qū)間進行掃描,確定僅存在單根的區(qū)間,此區(qū)間內(nèi)的任意一點可視為根的近似值。,(2) 用迭代方法使根精確到所要求精度。,2.1 問題的提出,掃描流程,2.1 問題的提出,【歷史注記】人們很早就探索了高次方程的數(shù)值解的求法。巴比倫泥板中有平方表和立方表，利用它們可以解某些特殊的二次和三次方程。中國古人相當系統(tǒng)地解決了求高次方程數(shù)值解的問題，九章算術以算法形式給出了二次方程及正系數(shù)三次方程正根的具體計算程序；7世紀王孝通也給出了求三次方程正根的數(shù)值解法；11世紀賈憲在黃帝九章算法細草中創(chuàng)“開方作法本源圖”,用“立成釋鎖法”解三次和三次以上高次方程, 同時他又提出一種更為簡便的“增乘開方法”；13世紀秦九韶在數(shù)書九章中的“正負開方術”最后完成，提供了一個用算籌布列解任何次數(shù)字方程的可行算法。,2.1 問題的提出,阿拉伯人對高次代數(shù)方程的數(shù)值解法亦有研究，花拉子米(9世紀)第一個給出了二次方程的一般解法,奧馬海亞姆(1100年)給出了一些特殊三次方程的解法。1541年塔爾塔利亞得到三次方程的一般解法。1545年卡爾達諾在其名著大術一書中發(fā)展了塔爾塔利亞的這一成果，并記載了費拉里得到的四次方程的一般解法。牛頓在1736年出版的流數(shù)法一書中，給出了著名的高次代數(shù)方程的一種數(shù)值解法,1690年Raphson 也提出了類似的方法，它們的結(jié)合就是現(xiàn)代常用的方法牛頓法(也叫Newton-Raphson方法)。它是一種廣泛用于高次代數(shù)方程求解的迭代法，亦稱為切線法，并不斷產(chǎn)生新的變形,2.1 問題的提出,如修正牛頓法，擬牛頓法等。1797年，高斯給出“代數(shù)基本定理”，指出高次代數(shù)方程根的存在性。1819年，霍納提出求高次代數(shù)方程數(shù)值解的另一種方法霍納法，其思想及計算程序與秦九韶的方法近似，類似的方法魯非尼在1804年也提出過，霍納法也有廣泛的應用，它的現(xiàn)代改進形式叫劈因子法。現(xiàn)在常用的代數(shù)方程數(shù)值解法還有伯努利法和勞斯表格法。,2.1 問題的提出,有多種數(shù)值算法可以求解非線性方程，我們在本章將學習其中得幾種，它們是：,二分法(bisection method),迭代法(iteration method),牛頓法(Newton method),牛頓下山法(Newton downhill method)。,牛頓(1),牛頓(Newton Isaac 1643.1.4-1727.3.31)：英國數(shù)學家、物理學家、天文學家、自然哲學家。生于林肯郡伍爾索普，卒于倫敦。早年在格蘭瑟姆讀書，1661年以優(yōu)異成績考入劍橋大學三一學院，數(shù)學上受教于巴羅。1664年畢業(yè)后曾為躲避鼠疫回鄉(xiāng)，16651666年做出流數(shù)法、萬有引力和光的分析三大發(fā)明，年僅23歲。1667年回劍橋在三一學院執(zhí)教。1669年繼巴羅之后任盧卡斯數(shù)學教授職位。晚年致力于哲學和公務，1696年任造幣廠監(jiān)督，3年后任廠長。1703年當選為英國皇家學會主席。他在數(shù)學上以創(chuàng)建微積分學而著名，其流數(shù)法始于1665年，系統(tǒng)敘述于流數(shù)法和無窮級數(shù)(1671年完,成，1736年出版)，首先發(fā)表在自然哲學的數(shù)學原理(1687)中。其中借助運動學中描述的連續(xù)量及其變化率闡述他的流數(shù)理論，并創(chuàng)用字母上加一點表示流動變化率。討論的基本問題是：已知流量間的關系，求它們的流數(shù)的關系以及逆運算，確定了微分與積分這兩類運算的互逆關系，即微積分學基本定理。此外，他還論述了有理指數(shù)的二項式定理(1664年)，n次代數(shù)方程根的m次冪和的公式(1707年)，數(shù)論、解析幾何學、曲線分類、變分法等問題。在物理學上發(fā)現(xiàn)了萬有引力定律(1666-1684)，并據(jù)此指出行星運行成橢圓軌道的原因。1666年用三棱鏡實驗光的色散現(xiàn)象，1668年發(fā)明并,牛頓(2),親手制作了第一具反射望遠鏡。在哲學上深信物質(zhì)、運動、空間和時間的客觀存在性，堅持用觀察和實驗方法發(fā)現(xiàn)自然界的規(guī)律，力求用數(shù)學定量方法表述的定律說明自然現(xiàn)象，其科學研究方法支配后世近300年的物理學研究。,牛頓(3),牛頓像(1),牛頓像(2),牛頓像(3),牛頓像(4),牛頓像(5),牛頓像(6),牛頓像(7),牛頓像(8),高斯(1),高斯(Gauss, Carl Friedrich 1777.4.30-1855.2.23)：德國數(shù)學家、物理學家、天文學家。生于不倫瑞克，卒于格丁根。高斯是近代數(shù)學奠基者之一，在歷史上影響之大，可以和阿基米德、牛頓、歐拉并列。他幼年時就表現(xiàn)出超人的數(shù)學天才。1795年進入格丁根大學學習。第二年他發(fā)現(xiàn)正十七邊形的尺規(guī)作圖法，并給出可用尺規(guī)作出的正多邊形的條件，解決了歐幾里得以來懸而未決的問題。1798年轉(zhuǎn)入黑爾姆施泰特大學，1799年獲博士學位。1807年以后一直在格丁根大學任教授。 高斯的數(shù)學研究幾乎遍及所有領域，在數(shù)論、代數(shù)學、非歐幾何、復變函數(shù)和微分幾何等方面都,做出了開創(chuàng)性貢獻。他還把數(shù)學應用于天文學。大地測量學和磁學的研究，發(fā)明了最小二乘法原理。高斯的數(shù)論研究總結(jié)在算術研究(1801)中，這本書奠定了近代數(shù)論的基礎，它不僅是數(shù)論方面劃時代之作，也是數(shù)學史上不可多得的經(jīng)典著作之一。高斯對代數(shù)學的重要貢獻是證明了代數(shù)基本定理，他的存在性證明開創(chuàng)了數(shù)學研究的新途徑。高斯在1816年左右就得到非歐幾何的原理，發(fā)現(xiàn)橢圓函數(shù)的雙周期性，但這些工作在他生前都沒有發(fā)表出來。他還深入研究復變函數(shù)，建立了一些基本概念并發(fā)現(xiàn)了著名的柯西積分定理。1828年高斯出版了關于曲面的一般研究，全面系統(tǒng)闡述了空間,高斯(2),曲面的微分幾何學，并提出了內(nèi)蘊曲面理論。高斯的曲面理論后來由黎曼進一步發(fā)展。高斯一生共發(fā)表155篇學術論文，他對待學問十分嚴謹，只是把他自己認為是十分成熟的作品發(fā)表出來。其著作還有地磁概論(1839)和論與距離平方成反比的引力和斥力的普遍定律(1840)等。,高斯(3),高斯像(1),高斯像(2),高斯像(3),高斯像(4),2.2 二分法,第二章 方程求根,2.2 二分法,定義：如果函數(shù)f(x)在區(qū)間a,b上連續(xù)，且f(a)f(b)0，則方程在區(qū)間a,b上一定有實根，a,b叫方程的有根區(qū)間。,【注記】f(a)f(b)0時在a,b上有根的情形。即，f(a)f(b)0對于在a,b上有實根是充分的, 但不必要；f(a)f(b)0對于在a,b上有唯一單實根不充分也不必要。如圖所示：,2.2 二分法,二分法實際上是一種簡單的區(qū)間求根方法(Bracketing method)，區(qū)間法的基本思想是把方程的根限定在一個區(qū)間中，區(qū)間長度不斷縮小，當區(qū)間長度充分小時就得到了近似解。二分法就是簡單地每次把區(qū)間從中間一分為二，區(qū)間長度每次減半。,2.2 二分法,二分法具體作法：,二分初始選取區(qū)間a0,b0，使得f(a0)f(b0)0 ，說明根在區(qū)間 (a0+b0)/2, b0 ，令a1= (a0+b0)/2, b1=b0則得到更新區(qū)間a1,b1 。,2.2 二分法,不斷重復這個過程直到 ， 為給定精度，于是得到方程根 。,新區(qū)間長度總是舊區(qū)間長度的一半，二分k次后區(qū)間假設為ak,bk，其長度為，,2.2 二分法,所以對于精度 ，由11111,得到循環(huán)次數(shù)為nnn,2.2 二分法,二分法的特點：,2.2 二分法,2)實施簡單，僅需函數(shù)值,1)收斂總能得到保證,3) 收斂速度慢,二分法算法:,f1=f(a0), f2=f(b0),(3) if then stop.,if then stop.,(4) if then stop.,2.2 二分法,(2) if f1f20, 初始區(qū)間選擇不合適, stop,給定f(x), a0, b0,(5) x=(a0+b0)/2, f=f(x) if then stop.,(6) If f1f0, then b0=x, f2=f else a0=x, f1=f, endif,(7) Goto (3),2.2 二分法,定理2.1：如果區(qū)間a,b上的連續(xù)函數(shù)f應用二分算法, f(a)f(b)0，則n步后將算出一個近似根，其誤差至多為,2.2 二分法,例2.1 用二分法求方程f(x)=x3+4x2-10=0在區(qū)間1,1.5上的根，使得根誤差不大于0.005，需要作幾次二分？,2.2 二分法,解：由f(1)=-5, f(1.5)=2.375,且當 時， 知方程在所給區(qū)間內(nèi)有唯一根。,2.2 二分法,由,得到,所以n=6就可以得到誤差不大于0.005的近似根。,作業(yè)：證明1-x-sinx=0在0,1(x單位為弧度)內(nèi)有唯一根，使用二分法求誤差不大于5e-5的根要迭代多少次？,2.2 二分法,【思考題 2.1】如何編程用二分法計算區(qū)間內(nèi)的N個實根(假設至少有N個實根)。,2.3 迭代法(iteration methods),第二章 方程求根,2.3 迭代法,基本思想: 設欲求方程f(x)=0的根, 變成形式 ,或 , 于是方程f(x)=0 的根是直線y=x與曲線 的交點。,用數(shù)學式表示迭代公式為：,如果迭代序列xk極限存在，則迭代收斂，并且 ；如果迭代序列xk極限不存在，則稱迭代過程發(fā)散。,解法1：將原方程寫成x=x3-1。取迭代函數(shù) 構(gòu)造迭代格式,例2.2 用迭代法求x3-x-1=0在x0=1.5附近的根。,2.3 迭代法,以初值x0=1.5代入計算，得到如下結(jié)果,2.3 迭代法,很明顯，xk發(fā)散，方法失敗。,2.3 迭代法,解法2：將原方程寫成 。取迭代函數(shù) 構(gòu)造迭代格式,取初值x0=1.5，計算得到,2.3 迭代法,可見迭代8次，近似解已收斂于1.3247。,2.3 迭代法,解法1和解法2的情況可用下面兩個圖示意：,定理2.2 假設迭代函數(shù) 在a,b上存在一階連續(xù)導數(shù),且滿足下列兩個條件,2.3 迭代法,(1) 對于任意 有,(2) 存在正數(shù)L1，使對于任意 有,2.3 迭代法,(a)方程 在a,b上有唯一根,(b)對于 a,b內(nèi)任意初始值,迭代 均收斂于方程根,(c)且有誤差估計,則：,2.3 迭代法,條件(2)意味著 斜率小于1, 即曲線 比直線y=x更平。,幾何解釋：,條件(1)意味著初始及后續(xù)每次迭代函數(shù)值仍在初始區(qū)間a,b內(nèi)；,2.3 迭代法,(a)作函數(shù) 。,所以必有 使,定理證明：,即,2.3 迭代法,再證根的唯一性。假設在區(qū)間a,b上存在兩個根 ，則,由微分中值定理及條件(2)知存在,由于L0，必有 ，即根唯一。,2.3 迭代法,(b)由微分中值定理知，存在 使,反復利用上式，有,因為L1，所以 時,即,2.3 迭代法,(c)誤差。注意到,于是,所以,2.3 迭代法,把,代入上式得,于是,2.3 迭代法,可以看出，L越小收斂越快，當L接近1時，收斂很慢。因為L為常數(shù)，所以一般用 來判斷迭代收斂。,2.3 迭代法,2.3 迭代法,2.3 迭代法,2.3 迭代法,2.3 迭代法,定義 如果存在鄰域 ，迭代過程 對于任意初始值 收斂，則稱迭代過程在根 附近具有局部收斂性。,2.3 迭代法,定理2.3：設在方程 根x*附近有 連續(xù)一階導數(shù)，且 ， 則迭代過程 具有局部收斂性。,使得,利用微分中值定理有,證明：取x*附近的一個 鄰域,2.3 迭代法,由于,即,于是取 滿足(1)對任意 ， ；(2)對任意,所以，迭代過程具有局部收斂性。,迭代法的收斂速度,2.3 迭代法,定義： 當 時，有 ，( 且為常數(shù))，則稱迭代過程是p階收斂。特別地，當 p=1, 01時，稱作超線性收斂； p=2時稱作平方收斂。其中 稱作迭代誤差。,2.3 迭代法,由微分中值定理有,簡單迭代法收斂速度一般是線性的。,簡單迭代法的收斂速度。,2.3 迭代法,例2.3 設兩個迭代格式分別是線性收斂和平方收斂的，且,若取精度 ，試估計這兩個迭代格式各所需的迭代次數(shù)。,解：,2.3 迭代法,得,由,所以線性迭代格式需迭代54次。,2.3 迭代法,于是,所以,故平方收斂的迭代格式只需迭代6次。,2.3 迭代法,定理2.4：若 在 的根 附近有連續(xù) 階導數(shù)且p-1階導數(shù)全為零， , 則 p階局部收斂，且有,如果p=1，要求,2.3 迭代法,證明：由定理2.3知，迭代格式局部收斂。應用泰勒級數(shù)展開并注意到p-1導數(shù)全為零，有,2.3 迭代法,于是,或,2.3 迭代法,于是,2.3 迭代法,例2.4 判斷能不能直接用簡單迭代法求解下列的方程？,解：判斷方程 能否用簡單迭代法求根，要看在根的鄰域是否有,2.3 迭代法,對于(1)，,所以(1)可以用簡單迭代法求解。,對于(2)，可知f(1)0, f(3)0,所以1,3為有根區(qū)間。,所以(2)不能用簡單迭代法求解。,2.3 迭代法,例2.5 證明對于任何初始值 ,由迭代公式 所產(chǎn)生的序列 都收斂于 的根.,證明: 記 則,(1)當 ,故序列 收斂于 的根.,2.3 迭代法,(2)當對于任意 ,把 看作新的迭代初值,由(1)知命題得證.,2.3 迭代法,例2.6 利用迭代格式證明,證明: 考慮迭代格式,2.3 迭代法,則,記,2.3 迭代法,當 時,1.,所以迭代格式產(chǎn)生的序列 收斂于方程,在0,2內(nèi)的唯一根x=2, 即,2.3 迭代法,作業(yè)：證明用迭代格式,產(chǎn)生的序列，對于 均收斂于,作業(yè)：為求方程 在,附近的一個根，將方程改寫成為下列各式, 試分析各格式收斂性.,2.4 牛頓法(Newton method),第二章 方程求根,【歷史注記】1685年Wallis出版了一本名為代數(shù)的書，描述了由牛頓發(fā)明的一種求解方程的方法。1690年Raphson也發(fā)表了這個方法，但略有修改。于是現(xiàn)在通常把這個方法叫牛頓法或Newton-Raphson法。事實上，牛頓本人在1669年就討論了這個方法，并以方程x3-2x-5=0 為例作了說明，Wallis在其著作中也使用了這個例子，此后每一個學數(shù)值分析的學生都認識這個歷史悠久的方程。,2.4 牛頓法,牛頓法的解釋：使用牛頓法時總假設函數(shù)f(x)是一階可微的，這在幾何上 f(x)表示的圖形(曲線)在每個點上都有確定的斜率，因而有唯一切線。現(xiàn)在我們利用線性化的思想，設曲線 f(x)上某一點(x0,f(x0)有一條切線，該切線在該點的近旁是f(x)曲線的一個很好近似(以直代曲)。,2.4 牛頓法,2.4 牛頓法,從分析觀點來講，這種以直線代曲線就意味著切線線性函數(shù),在x0的近旁接近于函數(shù)f(x)，并且在x0處l(x)和f(x)值相等。因此，可取l(x)的零點為f(x)零點的一個近似。,2.4 牛頓法,l(x)的零點為x1=x0-f(x0)/f(x0)。這樣，從初始點x0出發(fā)，由上式就得到了一個新點，重復這個過程(迭代)，就能產(chǎn)生一系列點,2.4 牛頓法,如果收斂的話，這個點列將趨向于f(x)的一個零點。,還可以用另外的方式說明牛頓法。假設x0是對于f(x)的一個根的近似，可以想象，如果給x0加上一個修正值h就可以成為f(x)的精確根，即f(x+h)=0。如果f(x)的各階導數(shù)在x0處存在，則f(x)在x0處泰勒展開為,2.4 牛頓法,用上式很難求出h，于是考慮線性化，對于上式進行截斷,于是,2.4 牛頓法,得到一個新的近似根，,重復這個過程就是牛頓法。,回顧前面過程，可以發(fā)現(xiàn)，實際上并不需要有二階導數(shù)，因為我們只使用了泰勒展開的前兩項，僅要求在根的一個鄰域中導數(shù)連續(xù)即可。,2.4 牛頓法,牛頓法是方程求根十分重要和有效的方法，其基本思想是將非線性方程線性化構(gòu)造迭代公式。,設方程f(x)=0有近似根xk，將函數(shù)f(x)在xk處一階泰勒展開,2.4 牛頓法,于是方程線性化為,這個線性化方程的根為,按照迭代法，其迭代函數(shù)為,2.4 牛頓法,牛頓法的收斂速度,牛頓法可以看成迭代公式,如果x*是f(x)=0的一個單根，則f(x*)=0，,于是由上節(jié)定理知牛頓法有二階收斂速度。,2.4 牛頓法,【注記】可以證明對于重根情形，牛頓法是1階局部收斂。,迭代收斂判據(jù)有：,2.5 牛頓法下山法,第k次迭代xk充分接近于方程根x*，|f(xk)|充分小，接近于零。這兩個判據(jù)不等價，第一個能嚴格保證收斂，第二個并不能。雖然第一個判據(jù)很嚴格，但是實現(xiàn)起來有困難，因為x*未知，第二個判據(jù)盡管不嚴格，但易于實現(xiàn)。 后兩個判據(jù)在實際中采用較多。,2.5 牛頓法下山法,牛頓法算法,2.4 牛頓法,以及最大迭代次數(shù)N。,已知函數(shù)f(x)及f(x),給定x0,2.4 牛頓法,2.4 牛頓法,例2.7 用牛頓法求方程 在x=0.5附近的根。,2.4 牛頓法,解：把方程寫成 于是,取x0=0.5，得到,2.4 牛頓法,用簡單迭代法 得,2.4 牛頓法,例2.8 用牛頓法求Leonardo方程,的根,設x0=2，要求,解：,2.4 牛頓法,故,【注】Leonardo在1225年研究了該方程，并得到x=1.368808107的結(jié)果，此時f(x)=-0.000000009，這在當時是非常重要的結(jié)果，但無人知道他是如何得到的。,例2.9 用牛頓法求 的近似值，精度 。,2.4 牛頓法,解：化為求x2-115=0的正根，牛頓迭代公式為,取初值x0=10，經(jīng)過4次迭代，得x*=10.723805,【思考題 】對于牛頓迭代公式，證明,2.4 牛頓法,2.5 牛頓下山法,第二章 方程求根,牛頓法的收斂性和初始迭代值有關，如果初始迭代值離方程根較近，則迭代收斂性可以保證；如果初始值距離方程根較遠，則收斂過程可能發(fā)散。但是通常情況下很難給出一個離根較近的初始值，因為根無法預先知道。,2.5 牛頓法下山法,我們發(fā)現(xiàn)這樣一個事實：通常在根附近|f(x)|是單調(diào)下降的，即越接近根， |f(x)|越小，所以|f(xk)|f(xk+1)| 。于是我們把這個條件作為一個約束引入到迭代方程。滿足這個約束條件的算法叫下山法。,2.5 牛頓法下山法,具體作法：先得到牛頓法結(jié)果,把 與xk作加權(quán)平均得到：,叫下山因子, 時即為牛頓法。,2.5 牛頓法下山法,可以通過選取 值使得|f(xk)|f(xk+1)|。通常先令 開始，若上式不成立則 減半，直到上式成立,如果 已經(jīng)很小，上式仍不成立，則下山失敗。,意味著新的 若不滿足下山條件，則加大上一步結(jié)果的權(quán)重。,2.5 牛頓法下山法,例2.10 用牛頓下山法求方程f(x)=x3-x-1=0在1.5附近的根，精確到7位有效數(shù)