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