迭代法和二分法

迭代法和二分法第1頁(yè)，共13頁(yè)，2023年，2月20日，星期四非線性方程——就是因變量與自變量之間的關(guān)系不是線性的關(guān)系，這類方程很多，例如平方關(guān)系、對(duì)數(shù)關(guān)系、指數(shù)關(guān)系、三角函數(shù)關(guān)系等等。求解此類方程往往很難得到精確解，經(jīng)常需要求近似解問(wèn)題。解決此問(wèn)題的最主要的兩種方法是——迭代法和二分法。第2頁(yè)，共13頁(yè)，2023年，2月20日，星期四1、定義迭代法——逐次逼近的方法，在工程技術(shù)上也叫做試算法。從隔根區(qū)間（a0，b0）中的任一個(gè)初始近似值x0出發(fā)，按照某種格式構(gòu)造一個(gè)序列x0，x1，x2，……使得這個(gè)序列的極限就是f(x)=0的跟x*，即另一種方法是把方程f(x)=0寫(xiě)成等價(jià)形式x=φ(x)，然后令xk+1=φ(xk)k=0,1,2，……第3頁(yè)，共13頁(yè)，2023年，2月20日，星期四2、算法核心參數(shù)說(shuō)明：x0——開(kāi)始存放初始值，迭代中存放第k次近似值（實(shí)型變量，輸入?yún)?shù)）；x——迭代中存放第k+1次近似值，最終存放方程的跟（實(shí)型變量，輸出參數(shù)）；eps——根的精度控制量（實(shí)型變量，輸出參數(shù)）。

時(shí)，認(rèn)為xk+1是方程的跟。第4頁(yè)，共13頁(yè)，2023年，2月20日，星期四3、迭代法的收斂性如果從初值x0出發(fā)，按照迭代公式進(jìn)行迭代計(jì)算的過(guò)程中，xk逐次接近于方程的跟，則稱迭代公式是收斂的，否則是發(fā)散的。迭代法可行的必要條件是迭代過(guò)程必須收斂，收斂越快，則其收斂性越好。判別條件——迭代函數(shù)的一階導(dǎo)數(shù)在其定義區(qū)間[a,b]內(nèi)的絕對(duì)值小于1，迭代過(guò)程收斂，否則，則發(fā)散。第5頁(yè)，共13頁(yè)，2023年，2月20日，星期四加速迭代過(guò)程的3個(gè)因素：（1）選擇的迭代初值應(yīng)盡量接近于方程的根；（2）迭代函數(shù)一階導(dǎo)數(shù)在迭代區(qū)間的絕對(duì)值越小，收斂速度越快；（3）所求解方程的原函數(shù)f(x)的泰勒展開(kāi)式中的二階及二階以上的高階導(dǎo)數(shù)的值盡可能小，以致可以略去不計(jì)時(shí)，收斂速度越快。迭代法缺點(diǎn)——一是存在迭代過(guò)程不收斂的可能性，這將無(wú)法求解；二是存在收斂速度極緩慢的問(wèn)題，這將導(dǎo)致大大降低效率甚至難于計(jì)算。第6頁(yè)，共13頁(yè)，2023年，2月20日，星期四1、定義二分法——也稱對(duì)分法，是另一種簡(jiǎn)單易行的求非線性方程數(shù)值解的方法。不僅克服了迭代法可能不收斂的缺欠，即在有根區(qū)間用二分法肯定收斂于極值，而且其收斂速度也很快。假設(shè)有一個(gè)非線性方程f(x)=0，x在[a0,b0]區(qū)間內(nèi)，當(dāng)f(x)在區(qū)間[a0,b0]上單調(diào)連續(xù)，且f(x)在其區(qū)間[a0,b0]的兩個(gè)端點(diǎn)處的值異號(hào)，即f(a0)·f(b0)<0時(shí)，則方程在[a0,b0]區(qū)間內(nèi)有根，且只有一個(gè)根x*。第7頁(yè)，共13頁(yè)，2023年，2月20日，星期四2、求單根算法核心基本思想——將方程有根區(qū)間[a0,b0]分為兩個(gè)小區(qū)間（稱二分），取a0，b0的中點(diǎn)x1=(a0+b0)/2，并計(jì)算f(x1)的值；如果f(x1)與f(a0)同號(hào)，則方程的根必在[x1,b0]區(qū)間，反之，f(x1)與f(a0)異號(hào)，則根在[a0,x1]區(qū)間。通過(guò)這樣的方法找出并確定新的有根區(qū)間[a1,b1]，然后再將新的有根區(qū)間二分為兩個(gè)小區(qū)間，如此繼續(xù)下去，就可得到一個(gè)有根區(qū)間套第8頁(yè)，共13頁(yè)，2023年，2月20日，星期四（1）直至某一小區(qū)間端點(diǎn)處的函數(shù)f(xk)的絕對(duì)值小于給定精度ε1，即f(xk)<ε1式中k為尋找中點(diǎn)或二分有根區(qū)間的次數(shù)，xk為第k次二分時(shí)的中點(diǎn)值，則有xk=ak；或xk=bk；（2）或者直至某區(qū)間[ak,bk]的長(zhǎng)度小于給定的精度ε2，即跟的絕對(duì)誤差限小于ε2，便可以得到一個(gè)滿意的近似值。第9頁(yè)，共13頁(yè)，2023年，2月20日，星期四參數(shù)說(shuō)明：a0，b0——求根區(qū)間的下限與上限（實(shí)型變量，輸入?yún)?shù)）；eps——根的精度控制量，即ε2（實(shí)型變量，輸入?yún)?shù)）；x，y——分別存放近似根及其相應(yīng)的函數(shù)值（實(shí)型變量，輸出參數(shù)）；f——函數(shù)子程序名，表示被求解的方程。第10頁(yè)，共13頁(yè)，2023年，2月20日，星期四函數(shù)特點(diǎn)——始終通過(guò)判斷某一有根區(qū)間二分后的中點(diǎn)函數(shù)值f(xk)與求根初始區(qū)間的左端點(diǎn)處函數(shù)值f(a0)的乘積f(xk)·f(a0)是否大于零，來(lái)確定下一個(gè)有根區(qū)間。這里并沒(méi)有考慮精度ε1的影響，即沒(méi)有考慮某一小區(qū)間內(nèi)端點(diǎn)處的函數(shù)的絕對(duì)值是否小于精度。缺點(diǎn)——不能判斷某一區(qū)間是否有根或有幾個(gè)根。第11頁(yè)，共13頁(yè)，2023年，2月20日，星期四3、求所有單重實(shí)根的算法核心基本思想——需求出區(qū)間[a,b]上所有的單重實(shí)根，滿足兩個(gè)求根精度控制量ε1或ε2。自a點(diǎn)開(kāi)始，以一個(gè)基本步長(zhǎng)h，向右逐次分割出寬度為h的小區(qū)間[a0,b0]。若小區(qū)間兩端點(diǎn)處的函數(shù)值f(a0)與f(b0)異號(hào)，則用二分法找出其中存在的一個(gè)根；若同號(hào)，則繼續(xù)向右分割，重復(fù)上述操作，直至分割的小區(qū)間已超過(guò)定義或求根區(qū)間[a,b]為止。步長(zhǎng)h可以選的小些，以便每個(gè)小區(qū)間內(nèi)最多只有一個(gè)根，這樣并不浪費(fèi)很多機(jī)時(shí)，根據(jù)問(wèn)題的性質(zhì)h也沒(méi)有必要太小。第12頁(yè)，共13頁(yè)，2023年，2月20日，星期四參數(shù)說(shuō)明：a，b——求根區(qū)間[a,b]（實(shí)型變量，輸入?yún)?shù)）；h——步長(zhǎng)（實(shí)型變量，輸入?yún)?shù)）；n——估計(jì)根的最多個(gè)數(shù)（與x方次數(shù)有關(guān)，整型變量，輸入?yún)?shù)）；ep1——函數(shù)值精度控制量ε1（實(shí)型變量，輸入?yún)?shù)）；ep2——根的精度