迭代法和二分法

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

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