- 相關(guān)推薦
二分法求解單變量非線(xiàn)性方程及其應用與實(shí)現
論文關(guān)鍵詞：二分法 單變量 非線(xiàn)性方程 收斂性 誤差
論文摘要：本文主要通過(guò)一個(gè)實(shí)例來(lái)研究單變量非線(xiàn)性方程f（x）=0的二分法求解及此方法的收斂性，根據誤差估計確定二分次數并進(jìn)行求解。同時(shí)實(shí)現matlab和C語(yǔ)言程序編寫(xiě)。從而掌握過(guò)程的基本形式和二分法的基本思想，在以后的學(xué)習過(guò)程中得以應用�！�
1. 引 言
在科學(xué)研究與工程技術(shù)中常會(huì )遇到求解非線(xiàn)性方程f(x)=0的問(wèn)題。而方程f(x)是多項式或超越函數又分為代數方程或超越方程。對于不高于四次的代數方程已有求根公式，而高于四次的代數方程則無(wú)精確的求根公式，至于超越方程就更無(wú)法求其精確解了。因此，如何求得滿(mǎn)足一定精度要求的方程的近似根也就成為了我們迫切需要解決的問(wèn)題。近年來(lái)，隨著(zhù)數學(xué)科學(xué)研究的不斷進(jìn)展，又更新了許多方程求解的方法。我們知道，對于單變量非線(xiàn)性方程f（x）=0，一般都可采用迭代法求根，由此產(chǎn)生了二分法。
2. 二分法
一般地，對于函數f(x),如果存在實(shí)數c,當x=c時(shí)f(c)=0,那么把x=c叫做函數f(x)的零點(diǎn)。
解方程即要求f(x)的所有零點(diǎn)。
先找到a、b，使f(a)，f(b)異號，說(shuō)明在區間(a,b)內一定有零點(diǎn)，然后求f[(a+b)/2], 現在假設f(a)<0,f(b)>0,a<b
�、偃绻鹒[(a+b)/2]=0，該點(diǎn)就是零點(diǎn)，
如果f[(a+b)/2]<0,則在區間（(a+b)/2，b)內有零點(diǎn)，(a+b)/2=>a，從①開(kāi)始繼續使用中點(diǎn)函數值判斷。
如果f[(a+b)/2]>0，則在區間(a,(a+b)/2)內有零點(diǎn)，(a+b)/2=>b，從①開(kāi)始繼續使用中點(diǎn)函數值判斷。
這樣就可以不斷接近零點(diǎn)。
通過(guò)每次把f(x)的零點(diǎn)所在小區間收縮一半的方法，使區間的兩個(gè)端點(diǎn)逐步迫近函數的零點(diǎn)，以求得零點(diǎn)的近似值，這種方法叫做二分法。
給定精確度ξ,用二分法求函數f(x)零點(diǎn)近似值的步驟如下:
1. 確定區間[a,b],驗證f(a)·f(b)<0,給定精確度ξ.
2. 求區間(a,b)的中點(diǎn)c.
3. 計算f(c).
(1) 若f(c)=0,則c就是函數的零點(diǎn);
(2) 若f(a)·f(c)<0,則令b=c;
(3) 若f(c)·f(b)<0,則令a=c.
4. 判斷是否達到精確度ξ:即若┃a-b┃<ξ,則得到零點(diǎn)近似值a(或b),否則重復2-4.
由于計算過(guò)程的具體運算復雜，但每一步的方式相同，所以可通過(guò)編寫(xiě)程序來(lái)運算。
3. 實(shí)例引入
二分法求解單變量非線(xiàn)性方程的例子很多，僅以此例進(jìn)行分析：
求方程f（x）=x³-x-1=0在區間[1.0，1.5]內的一個(gè)實(shí)根，要求準確到小數點(diǎn)后第2位。
4. 問(wèn)題分析
對于以上單變量非線(xiàn)性方程，已知a=1.0，b=1.5，采用二分法求解。首先我們根據二分法所允許的誤差范圍求得應迭代次數。
二分法允許的誤差公式：|x*- | ( - )/2=（b-a）/ 0.005，
其中k為二分次數。
所以求得本題應二分6次達到預定的精度。
5. 解題過(guò)程
這里a=1.0，b=1.5，而f（a）<0，f（b）>0。[a,b]的中點(diǎn)x0=1.25，將區間二等分。由于f（x0）<0,即f（x0）與f（a）同號，故所求根x*必在x0右側，這是應令a1=1.25，b1=1.5，得到新的有根區間[a1，b1].如此反復二分6次，結果如下：
K/二分次數 /區間
左邊界值 /右邊界值 F( )的符號
0
1
2
3
4
5
61.0
1.25
1.3125
1.32031.5
1.375
1.3438
1.32811.25
1.375
1.3125
1.3438
1.3281
1.3203
1.3242－
+
－
+
+
－
－
6. 基本二分法的matlab實(shí)現與C語(yǔ)言實(shí)現
6.1 %二分法的算法及MATLAB實(shí)現
function [c, err, yc] = bisect(f, a, b, delta)
% f 是所要求解的函數
% a 和 b 分別是有根區間的左右限
% delta 是允許的誤差界
% c 為所求的近似解
% yc 為函數 f 在 c 上的值
% err 是 c 的誤差估計
if nargin < 4
delta = 1e -5;
end
ya = feval (’f’, a);
yb = feval (’f’, b);
if yb == 0, c = b, return
end
if ya * yb > 0
disp(’(a, b)不是有根區間’);
return
end
max1 = 1 + round((log(b - a) - log(delta))/log(2));
for k = 1:max1
c = (a + b)/2;
yc = fevel(’f’, c);
if yc == 0 a = c; b = c; break,
elseif yb * yc > 0
b = c; yb = yc;
else
a = c; ya = c;
end
if (b - a) < delta, break
end
end
k, c = (a + b)/2, err = abs(b - a), yc = feval(‘f’, c)
6.2 %基本二分法的C語(yǔ)言實(shí)現
方程式為：f(x) = 0，示例中f(x) = 1+x-x^3
使用示例：
input a b e: 1 2 1e-5
solution: 1.32472
源碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
double f(double x)
{
return 1+x-x*x*x;
}
int main()
{
double a = 0, b = 0, e = 1e-5;
printf("input a b e: ");
scanf("%lf%lf%lf", &a, &b, &e);
e = fabs(e);
if (fabs(f(a)) <= e)
{
printf("solution: %lg\n", a);
}
else if (fabs(f(b)) <= e)
{
printf("solution: %lg\n", b);
}
else if (f(a)*f(b) > 0)
{
printf("f(%lg)*f(%lg) > 0 ! need <= 0 !\n", a, b);
}
else
{
while (fabs(b-a) > e)
{
double c = (a+b)/2.0;
if (f(a)* f ( c ) < 0)
b = c;
else
a = c;
}
printf("solution: %lg\n", (a+b)/2.0);
}
return 0;
}
7.方法總結
7.1二分法解題的基本步驟：
1）計算f（x）的有根區間[a,b]端點(diǎn)處的值f（a），f（b）。
2）計算f(x)的區間中點(diǎn)的值f（（a+b）/2）。
3）進(jìn)行函數值的符號比較。
4）根據誤差估計二分到一定次數達到精度，從而求得近似值。
7.2二分法的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：算法簡(jiǎn)單，容易理解，且總是收斂的
缺點(diǎn)：收斂速度太慢，浪費時(shí)間
所以，在以后的學(xué)習過(guò)程中，我們將根據方程的形式和二分法的優(yōu)缺點(diǎn)不單獨將其用于求根，只用其為根求得一個(gè)較好的近似值，方便其他方法的運算。
8. 結 論
(1)針對現實(shí)中的許多剖面設計、軌道設計等關(guān)鍵參數方程中三角函數多、計算工作量較大、迭代收斂條件強等問(wèn)題，采取數學(xué)變化的方法將該方程轉化成一個(gè)只包含對數函數和多項式函數的新方程，并提出了尋找求解區間的步長(cháng)搜索算法和自適應步長(cháng)搜索算法，進(jìn)而使用二分法求新方程的數值解。
(2)數學(xué)分析和數值實(shí)踐表明，該算法不僅能夠正確判斷設計方程是否有解，而且在有解的情況下能夠正確求出該解，計算量小，計算過(guò)程穩定。
參考文獻
【1】曾毅; 改進(jìn)的遺傳算法在非線(xiàn)性方程組求解中的應用[J]; 華東交通大學(xué)學(xué)報; 2004 年04期; 136-138
【2】許小勇,宋昔芳; 一種求解非線(xiàn)性方程全部實(shí)根的算法與實(shí)現 [J];科技廣場(chǎng);2007年01期; 15-17
【3】王興華,郭學(xué)萍; 二分法及其各種變形收斂性的統一判定法則 [J];高等學(xué)校計算數學(xué)學(xué)報; 1999年04期
【4】苗慧; 解非線(xiàn)性方程的若干算法的收斂性分析 [D];浙江大學(xué); 2006年
【5】李曉霞; 關(guān)于若干迭代算法的收斂性分析 [D];浙江大學(xué); 2002年
【6】李慶揚,王能超,易大義;數值分析第4版 TUP 清華大學(xué); 2001年5月
【二分法求解單變量非線(xiàn)性方程及其應用與實(shí)現】相關(guān)文章：
遺傳算法及其在求解TSP中的應用03-07
單時(shí)鐘完成多點(diǎn)分別計時(shí)的實(shí)現和應用03-18
利用有限元法求解Laplace方程03-07
矩陣的分解及其應用03-07
EDA技術(shù)及其應用03-19
V-BLAST的實(shí)現及其檢測03-07
鈦合金的特性及其應用03-01
矩陣函數的性質(zhì)及其應用03-07