二分法求解單變量非線性方程及其應用與實現

戚興龍

【摘要】在科學研究與工程技術中常會遇到求解非線性方程f(x)=0的問題。而方程f(x)是多項式或超越函數又分為代數方程或超越方程。對于不高于四次的代數方程已有求根公式,而高于四次的代數方程則無精確的求根公式,至于超越方程就更無法求其精確解了。因此,如何求得滿足一定精度要求的方程的近似根也就成為了我們迫切需要解決的問題。近年來,隨著數學科學研究的不斷進展,又更新了許多方程求解的方法。我們知道,對于單變量非線性方程f(x)=0,一般都可采用迭代法求根,由此產生了二分法。

【關鍵詞】二分法 單變量 非線性方程收斂性 誤差

一、引言

在科學研究與工程技術中常會遇到求解非線性方程f(x)=0的問題。而方程f(x)是多項式或超越函數又分為代數方程或超越方程。對于不高于四次的代數方程已有求根公式,而高于四次的代數方程則無精確的求根公式,至于超越方程就更無法求其精確解了。因此,如何求得滿足一定精度要求的方程的近似根也就成為了我們迫切需要解決的問題。近年來,隨著數學科學研究的不斷進展,又更新了許多方程求解的方法。我們知道,對于單變量非線性方程f(x)=0,一般都可采用迭代法求根,由此產生了二分法。

二、二分法

一般地,對于函數f(x),如果存在實數c,當x=c時f(c)=0,那么把x=c叫做函數f(x)的零點。

解方程即要求f(x)的所有零點。

先找到a、b,使f(a),f(b)異號,說明在區間(a,b)內一定有零點,然后求f[(a+b)/2],現在假設f(a)<0,f(b)>0,a

①如果f[(a+b)/2]=0,該點就是零點,

如果f[(a+b)/2]<0,則在區間((a+b)/2,b)內有零點,(a+b)/2=>a,從①開始繼續使用中點函數值判斷。

如果f[(a+b)/2]>0,則在區間(a,(a+b)/2)內有零點,(a+b)/2=>b,從①開始繼續使用中點函數值判斷。

這樣就可以不斷接近零點。

通過每次把f(x)的零點所在小區間收縮一半的方法,使區間的兩個端點逐步迫近函數的零點,以求得零點的近似值,這種方法叫做二分法。

給定精確度ξ,用二分法求函數f(x)零點近似值的步驟如下:

1.確定區間[a,b],驗證f(a)?f(b)<0,給定精確度ξ.

2.求區間(a,b)的中點c.

3.計算f(c).

(1)若f(c)=0,則c就是函數的零點;

(2)若f(a)?f(c)<0,則令b=c;

(3)若f(c)?f(b)<0,則令a=c.

4.判斷是否達到精確度ξ:即若┃a-b┃<ξ,則得到零點近似值a(或b),否則重復2-4.

由于計算過程的具體運算復雜,但每一步的方式相同,所以可通過編寫程序來運算。

三、實例引入

二分法求解單變量非線性方程的例子很多,僅以此例進行分析:

求方程f(x)=x3-x-1=0在區間[1.0,1.5]內的一個實根,要求準確到小數點后第2位。

四、問題分析

對于以上單變量非線性方程,已知a=1.0,b=1.5,采用二分法求解。首先我們根據二分法所允許的誤差范圍求得應迭代次數。

二分法允許的誤差公式:|x*- | ( - )/2=(b-a)/0.005,

其中k為二分次數。

所以求得本題應二分6次達到預定的精度。

五、解題過程

這里a=1.0,b=1.5,而f(a)<0,f(b)>0。[a,b]的中點x0=1.25,將區間二等分。由于f(x0)<0,即f(x0)與f(a)同號,故所求根x*必在x0右側,這是應令a1=1.25,b1=1.5,得到新的有根區間[a1,b1].如此反復二分6次,結果如下:

K/二分次數 /區間

左邊界值 /右邊界值 F( )的符號

六、基本二分法的matlab實現與C語言實現

6.1 %二分法的算法及MATLAB實現

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