第二章 迭代法和二分法

1、非線性方程非線性方程就是因變量與自變量之間的關(guān)就是因變量與自變量之間的關(guān)系不是線性的關(guān)系，這類方程很多，例如平方系不是線性的關(guān)系，這類方程很多，例如平方關(guān)系、對(duì)數(shù)關(guān)系、指數(shù)關(guān)系、三角函數(shù)關(guān)系等關(guān)系、對(duì)數(shù)關(guān)系、指數(shù)關(guān)系、三角函數(shù)關(guān)系等等。求解此類方程往往很難得到精確解，經(jīng)常等。求解此類方程往往很難得到精確解，經(jīng)常需要求近似解問(wèn)題。需要求近似解問(wèn)題。解決此問(wèn)題的最主要的兩種方法是解決此問(wèn)題的最主要的兩種方法是迭代法迭代法和和二分法二分法。1、定義、定義迭代法迭代法逐次逼近的方法，在工程技術(shù)上也逐次逼近的方法，在工程技術(shù)上也叫做試算法。從隔根區(qū)間（叫做試算法。從隔根區(qū)間（a0，b0）中的任一）中的任

2、一個(gè)初始近似值個(gè)初始近似值x0出發(fā)，按照某種格式構(gòu)造一個(gè)出發(fā)，按照某種格式構(gòu)造一個(gè)序列序列x0，x1，x2，使得這個(gè)序列的極限就是使得這個(gè)序列的極限就是f(x)=0的跟的跟x*，即，即另一種方法是把方程另一種方法是把方程f(x)=0寫成等價(jià)形式寫成等價(jià)形式x=(x)，然后令然后令xk+1=(xk) k=0,1,2，lim*,( *)0kkxxf x2、算法核心、算法核心參數(shù)說(shuō)明：參數(shù)說(shuō)明：x0開始存放初始值，迭代中存放第開始存放初始值，迭代中存放第k次近次近似值（實(shí)型變量，輸入?yún)?shù)）；似值（實(shí)型變量，輸入?yún)?shù)）；x迭代中存放第迭代中存放第k+1次近似值，最終存放方次近似值，最終存放方程的跟（實(shí)

3、型變量，輸出參數(shù)）；程的跟（實(shí)型變量，輸出參數(shù)）；eps根的精度控制量（實(shí)型變量，輸出參根的精度控制量（實(shí)型變量，輸出參數(shù)）。數(shù)）。 時(shí)，認(rèn)為時(shí)，認(rèn)為xk+1是方程的跟。是方程的跟。1kkxx3、迭代法的收斂性、迭代法的收斂性如果從初值如果從初值x0出發(fā)，按照迭代公式進(jìn)行迭代計(jì)出發(fā)，按照迭代公式進(jìn)行迭代計(jì)算的過(guò)程中，算的過(guò)程中，xk逐次接近于方程的跟，則稱迭逐次接近于方程的跟，則稱迭代公式是收斂的，否則是發(fā)散的。迭代法可行代公式是收斂的，否則是發(fā)散的。迭代法可行的必要條件是迭代過(guò)程必須收斂，收斂越快，的必要條件是迭代過(guò)程必須收斂，收斂越快，則其收斂性越好。則其收斂性越好。判別條件判別條件迭代函

4、數(shù)的一階導(dǎo)數(shù)在其定義區(qū)迭代函數(shù)的一階導(dǎo)數(shù)在其定義區(qū)間間a,b內(nèi)的絕對(duì)值小于內(nèi)的絕對(duì)值小于1，迭代過(guò)程收斂，否，迭代過(guò)程收斂，否則，則發(fā)散。則，則發(fā)散。加速迭代過(guò)程的加速迭代過(guò)程的3個(gè)因素：個(gè)因素：（1）選擇的迭代初值應(yīng)盡量接近于方程的根；）選擇的迭代初值應(yīng)盡量接近于方程的根；（2）迭代函數(shù)一階導(dǎo)數(shù)在迭代區(qū)間的絕對(duì)值）迭代函數(shù)一階導(dǎo)數(shù)在迭代區(qū)間的絕對(duì)值越小，收斂速度越快；越小，收斂速度越快；（3）所求解方程的原函數(shù)）所求解方程的原函數(shù)f(x)的泰勒展開式中的泰勒展開式中的二階及二階以上的高階導(dǎo)數(shù)的值盡可能小，的二階及二階以上的高階導(dǎo)數(shù)的值盡可能小，以致可以略去不計(jì)時(shí)，收斂速度越快。以致可以略去不

5、計(jì)時(shí)，收斂速度越快。迭代法缺點(diǎn)迭代法缺點(diǎn)一是存在迭代過(guò)程不收斂的可一是存在迭代過(guò)程不收斂的可能性，這將無(wú)法求解；二是存在收斂速度極緩能性，這將無(wú)法求解；二是存在收斂速度極緩慢的問(wèn)題，這將導(dǎo)致大大降低效率甚至難于計(jì)慢的問(wèn)題，這將導(dǎo)致大大降低效率甚至難于計(jì)算。算。1、定義、定義二分法二分法也稱對(duì)分法，是另一種簡(jiǎn)單易行的也稱對(duì)分法，是另一種簡(jiǎn)單易行的求非線性方程數(shù)值解的方法。不僅克服了迭代求非線性方程數(shù)值解的方法。不僅克服了迭代法可能不收斂的缺欠，即在有根區(qū)間用二分法法可能不收斂的缺欠，即在有根區(qū)間用二分法肯定收斂于極值，而且其收斂速度也很快。肯定收斂于極值，而且其收斂速度也很快。假設(shè)有一個(gè)非線性方

6、程假設(shè)有一個(gè)非線性方程f(x)=0，x在在a0, b0區(qū)間區(qū)間內(nèi)，當(dāng)內(nèi)，當(dāng)f(x)在區(qū)間在區(qū)間a0, b0上單調(diào)連續(xù)，且上單調(diào)連續(xù)，且f(x)在在其區(qū)間其區(qū)間a0, b0的兩個(gè)端點(diǎn)處的值異號(hào)，即的兩個(gè)端點(diǎn)處的值異號(hào)，即f(a0)f(b0)0時(shí)，則方程在時(shí)，則方程在a0, b0區(qū)間內(nèi)有根，區(qū)間內(nèi)有根，且只有一個(gè)根且只有一個(gè)根x*。2、求單根算法核心、求單根算法核心基本思想基本思想將方程有根區(qū)間將方程有根區(qū)間a0, b0分為兩個(gè)分為兩個(gè)小 區(qū) 間 （ 稱 二 分 ） ， 取小 區(qū) 間 （ 稱 二 分 ） ， 取 a0， b0的 中 點(diǎn)的 中 點(diǎn)x1=(a0+b0)/2，并計(jì)算，并計(jì)算f(x1)的值

7、；如果的值；如果f(x1)與與f(a0)同號(hào)，則方程的根必在同號(hào)，則方程的根必在x1, b0區(qū)間，反之，區(qū)間，反之，f(x1)與與f(a0)異號(hào)，則根在異號(hào)，則根在a0, x1區(qū)間。通過(guò)這區(qū)間。通過(guò)這樣的方法找出并確定新的有根區(qū)間樣的方法找出并確定新的有根區(qū)間a1, b1，然，然后再將新的有根區(qū)間二分為兩個(gè)小區(qū)間，如此后再將新的有根區(qū)間二分為兩個(gè)小區(qū)間，如此繼續(xù)下去，就可得到一個(gè)有根區(qū)間套繼續(xù)下去，就可得到一個(gè)有根區(qū)間套001122,.,.kkaba babab（1）直至某一小區(qū)間端點(diǎn)處的函數(shù)）直至某一小區(qū)間端點(diǎn)處的函數(shù)f(xk)的絕的絕對(duì)值小于給定精度對(duì)值小于給定精度1，即，即f(xk) 1

8、式中式中k為尋找中點(diǎn)或二分有根區(qū)間的次數(shù)，為尋找中點(diǎn)或二分有根區(qū)間的次數(shù)，xk為第為第k次二分時(shí)的中點(diǎn)值，則有次二分時(shí)的中點(diǎn)值，則有xk=ak；或；或xk= bk；（2）或者直至某區(qū)間）或者直至某區(qū)間ak, bk的長(zhǎng)度小于給定的長(zhǎng)度小于給定的精度的精度2，即跟的絕對(duì)誤差限小于，即跟的絕對(duì)誤差限小于2， 便可以便可以得到一個(gè)滿意的近似值。得到一個(gè)滿意的近似值。200*12kkkkkkxxbababa參數(shù)說(shuō)明：參數(shù)說(shuō)明：a0，b0求根區(qū)間的下限與上限（實(shí)型變量，求根區(qū)間的下限與上限（實(shí)型變量，輸入?yún)?shù)）；輸入?yún)?shù)）；eps根的精度控制量，即根的精度控制量，即2（實(shí)型變量，（實(shí)型變量，輸入?yún)?shù)）；輸

9、入?yún)?shù)）；x，y分別存放近似根及其相應(yīng)的函數(shù)值分別存放近似根及其相應(yīng)的函數(shù)值（實(shí)型變量，輸出參數(shù)）；（實(shí)型變量，輸出參數(shù)）；f函數(shù)子程序函數(shù)子程序名，表示被求解的方程。名，表示被求解的方程。函數(shù)特點(diǎn)函數(shù)特點(diǎn)始終通過(guò)判斷某一有根區(qū)間二分始終通過(guò)判斷某一有根區(qū)間二分后的中點(diǎn)函數(shù)值后的中點(diǎn)函數(shù)值f(xk)與求根初始區(qū)間的與求根初始區(qū)間的左端點(diǎn)左端點(diǎn)處函數(shù)值處函數(shù)值f(a0)的乘積的乘積f(xk)f(a0)是否大于零，來(lái)是否大于零，來(lái)確定下一個(gè)有根區(qū)間。確定下一個(gè)有根區(qū)間。這里并沒(méi)有考慮精度這里并沒(méi)有考慮精度1的影響，即沒(méi)有考慮某的影響，即沒(méi)有考慮某一小區(qū)間內(nèi)端點(diǎn)處的函數(shù)的絕對(duì)值是否小于精一小區(qū)間內(nèi)端

10、點(diǎn)處的函數(shù)的絕對(duì)值是否小于精度。度。缺點(diǎn)缺點(diǎn)不能判斷某一區(qū)間是否有根或有幾個(gè)不能判斷某一區(qū)間是否有根或有幾個(gè)根。根。3、求所有單重實(shí)根的算法核心、求所有單重實(shí)根的算法核心基本思想基本思想需求出區(qū)間需求出區(qū)間a, b上所有的單重上所有的單重實(shí)根，滿足兩個(gè)求根精度控制量實(shí)根，滿足兩個(gè)求根精度控制量1或或2。自。自a點(diǎn)點(diǎn)開始，以一個(gè)基本步長(zhǎng)開始，以一個(gè)基本步長(zhǎng)h，向右逐次分割出寬，向右逐次分割出寬度為度為h的小區(qū)間的小區(qū)間a0, b0。若小區(qū)間兩端點(diǎn)處的。若小區(qū)間兩端點(diǎn)處的函數(shù)值函數(shù)值f(a0)與與f(b0)異號(hào)，則用二分法找出其中異號(hào)，則用二分法找出其中存在的一個(gè)根；若同號(hào)，則繼續(xù)向右分割，重存在

11、的一個(gè)根；若同號(hào)，則繼續(xù)向右分割，重復(fù)上述操作，直至分割的小區(qū)間已超過(guò)定義或復(fù)上述操作，直至分割的小區(qū)間已超過(guò)定義或求根區(qū)間求根區(qū)間a, b為止。為止。步長(zhǎng)步長(zhǎng)h可以選的小些，以便每個(gè)小區(qū)間內(nèi)最多可以選的小些，以便每個(gè)小區(qū)間內(nèi)最多只有一個(gè)根，這樣并不浪費(fèi)很多機(jī)時(shí)，根據(jù)問(wèn)只有一個(gè)根，這樣并不浪費(fèi)很多機(jī)時(shí)，根據(jù)問(wèn)題的性質(zhì)題的性質(zhì)h也沒(méi)有必要太小也沒(méi)有必要太小。參數(shù)說(shuō)明：參數(shù)說(shuō)明：a，b求根區(qū)間求根區(qū)間a, b（實(shí)型變量，輸入?yún)?shù)）；（實(shí)型變量，輸入?yún)?shù)）；h步長(zhǎng)（實(shí)型變量，輸入?yún)?shù)）；步長(zhǎng)（實(shí)型變量，輸入?yún)?shù)）；n估計(jì)根的最多個(gè)數(shù)（與估計(jì)根的最多個(gè)數(shù)（與x方次數(shù)有關(guān)，整型變方次數(shù)有關(guān)，整型變量，輸入?yún)?shù)）；量，輸入?yún)?shù)）；ep1函數(shù)值精度控制量函數(shù)值精度控制量1（實(shí)型變量，輸入?yún)ⅲ▽?shí)型變量，輸入?yún)?shù)）；數(shù)）；ep2根的精度控制量根