- 相關推薦
二分法求解單變量非線性方程及其應用與實現
論文關鍵詞：二分法 單變量 非線性方程 收斂性 誤差
論文摘要：本文主要通過一個實例來研究單變量非線性方程f（x）=0的二分法求解及此方法的收斂性，根據誤差估計確定二分次數并進行求解。同時實現matlab和C語言程序編寫。從而掌握過程的基本形式和二分法的基本思想，在以后的學習過程中得以應用。
1. 引 言
在科學研究與工程技術中常會遇到求解非線性方程f(x)=0的問題。而方程f(x)是多項式或超越函數又分為代數方程或超越方程。對于不高于四次的代數方程已有求根公式，而高于四次的代數方程則無精確的求根公式，至于超越方程就更無法求其精確解了。因此，如何求得滿足一定精度要求的方程的近似根也就成為了我們迫切需要解決的問題。近年來，隨著數學科學研究的不斷進展，又更新了許多方程求解的方法。我們知道，對于單變量非線性方程f（x）=0，一般都可采用迭代法求根，由此產生了二分法。
2. 二分法
一般地，對于函數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<b
①如果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.
由于計算過程的具體運算復雜，但每一步的方式相同，所以可通過編寫程序來運算。
3. 實例引入
二分法求解單變量非線性方程的例子很多，僅以此例進行分析：
求方程f（x）=x³-x-1=0在區間[1.0，1.5]內的一個實根，要求準確到小數點后第2位。
4. 問題分析
對于以上單變量非線性方程，已知a=1.0，b=1.5，采用二分法求解。首先我們根據二分法所允許的誤差范圍求得應迭代次數。
二分法允許的誤差公式：|x*- | ( - )/2=（b-a）/ 0.005，
其中k為二分次數。
所以求得本題應二分6次達到預定的精度。
5. 解題過程
這里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( )的符號
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實現與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
end
k, c = (a + b)/2, err = abs(b - a), yc = feval(‘f’, c)
6.2 %基本二分法的C語言實現
方程式為：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]端點處的值f（a），f（b）。
2）計算f(x)的區間中點的值f（（a+b）/2）。
3）進行函數值的符號比較。
4）根據誤差估計二分到一定次數達到精度，從而求得近似值。
7.2二分法的優缺點：
優點：算法簡單，容易理解，且總是收斂的
缺點：收斂速度太慢，浪費時間
所以，在以后的學習過程中，我們將根據方程的形式和二分法的優缺點不單獨將其用于求根，只用其為根求得一個較好的近似值，方便其他方法的運算。
8. 結 論
(1)針對現實中的許多剖面設計、軌道設計等關鍵參數方程中三角函數多、計算工作量較大、迭代收斂條件強等問題，采取數學變化的方法將該方程轉化成一個只包含對數函數和多項式函數的新方程，并提出了尋找求解區間的步長搜索算法和自適應步長搜索算法，進而使用二分法求新方程的數值解。
(2)數學分析和數值實踐表明，該算法不僅能夠正確判斷設計方程是否有解，而且在有解的情況下能夠正確求出該解，計算量小，計算過程穩定。
參考文獻
【1】曾毅; 改進的遺傳算法在非線性方程組求解中的應用[J]; 華東交通大學學報; 2004 年04期; 136-138
【2】許小勇,宋昔芳; 一種求解非線性方程全部實根的算法與實現 [J];科技廣場;2007年01期; 15-17
【3】王興華,郭學萍; 二分法及其各種變形收斂性的統一判定法則 [J];高等學校計算數學學報; 1999年04期
【4】苗慧; 解非線性方程的若干算法的收斂性分析 [D];浙江大學; 2006年
【5】李曉霞; 關于若干迭代算法的收斂性分析 [D];浙江大學; 2002年
【6】李慶揚,王能超,易大義;數值分析第4版 TUP 清華大學; 2001年5月
【二分法求解單變量非線性方程及其應用與實現】相關文章：
遺傳算法及其在求解TSP中的應用03-07
單時鐘完成多點分別計時的實現和應用03-18
定態薛定諤方程的MATLAB求解(一)03-07
利用有限元法求解Laplace方程03-07
矩陣的分解及其應用03-07
EDA技術及其應用03-19
V-BLAST的實現及其檢測03-07
鈦合金的特性及其應用03-01
矩陣函數的性質及其應用03-07