Thứ Năm, 20 tháng 2, 2014
Tài liệu CHƯƠNG 5: CÁC PHƯƠNG TRÌNH PHI TUYẾN docx
245
tol=eps;
fa=feval(f,a);
fb=feval(f,b);
iffa*fb>0
error(ʹNghiemkhongotrongdoannayʹ);
end
fork=1:maxiter
xx(k)=(a+b)/2;
fx=feval(f,xx(k));
err=(b‐a)/2;
ifabs(fx)<tol|abs(err)<
tolx
break;
elseiffx*fa>0
a=xx(k);
fa=fx;
elseb=xx(k);
end
end
x=xx(k);
ifk==maxiter
fprintf(ʹKhonghoitusau%dlanlap\nʹ,maxiter),
else
fprintf(ʹHoitusau%dlanlap\nʹ,k),
end
Đểtìmnghiệmcủahàmf(x)=tg(π‐)‐xtadùngchươngtrình
ctbisection.m
clearall,clc
f=inline(ʹtan(pi‐x)‐xʹ);
[x,ss,xx]=bisection(f,1.6,3,1e‐4,50)
§4.PHƯƠNGPHÁPDÂYCUNG
Giảsửf(x)liêntụctrêntrênđoạn[a,b]vàf(a).f(b)<0.Cầntìmnghiệm
củaf(x)= 0.Đểxácđịnhtaxemf(a)<0vàf(b)>0.Khiđóthayvìchiađôi
đoạn[a,b]tachia[a,b]
theotỉlệ‐f(a)/f(b).Điềuđóchotanghiệmgầnđúng:
x
1=a+h1
246
Trongđó
1
f(a)
(b a)
h
f(a) f(b)
=
−
−
−+
Tiếptheodùngcáchđóvớiđoạn[a,x
1]
hay[x
1,b]màhaiđầuhàmnhậngiátrịtrái
dấutađượcnghiệmgầnđúngx
2v.v.
Vềmặthìnhhọc,phươngphápnàycó
nghĩalàkẻdâycungcủađườngcongf(x)
quahaiđiểmA[a,f(a)]vàB[b,f(b)]haynóicáchkháclàtuyếntínhhoáhàm
f(x)trongđoạn[a,b].
Thật
vậyphươngtrìnhdâycungABcódạng:
f(a) f(b) af(b) bf(a)
yx
ab ab
−−
=+
−−
Chox=x
1,y=0tacó
1
af(b) bf(a)
x
f( b) f(a)
−
=
−
(1)
Taxâydựnghàm
chord()đểthựchiệnthuậttoántrên
function[x,err,xx]=chord(f,a,b,tolx,maxiter)
%giaiptf(x)=0bgphuongphapdaycung.
%vao:f‐hamcantimnghiem
%a/b‐khoangtimnghiem
%tolx‐saisomongmuoncuanghiem
%maxiterlanlapmax
%ra:x‐nghiem
%err‐sai
so
%xx‐cacgiatritrunggian
tolfun=eps;
fa=feval(f,a);
fb=feval(f,b);
iffa*fb>0
error(ʹNghiemkhongotrongdoannay!ʹ);
end
fork=1:maxiter
xx(k)=(a*fb‐b*fa)/(fb‐fa);%pt.(1)
fx=feval(f,xx(k));
err=min(abs(xx(k)‐a),abs(b‐xx(k)));
a
b
x
y
x1
ξ
247
ifabs(fx)<tolfun|err<tolx
break;
elseiffx*fa>0
a=xx(k);
fa=fx;
else
b=xx(k);
fb=fx;
end
end
x=xx(k);
ifk==maxiter
fprintf(ʹKhonghoitusau%dlanlap\nʹ,maxiter)
else
fprintf(ʹ
Hoitusau%dlanlap\nʹ,k)
end
Đểtìmnghiệmcủahàmf(x)=tg(π‐x)‐xtadùngchươngtrình
ctchord.m
clearall,clc
f=inline(ʹtan(pi‐x)‐xʹ);
[x,ss,xx]=falsp(f,1.7,3,1e‐4,50)
§5.PHƯƠNGPHÁPNEWTON‐RAPHSON
Phương pháp lặp Newton(còn gọi là ph ương pháp tiếp tuyến)được
dùngnhiềuvìnóhộitụnhanh.Tuynhiênphươngphápnàyđòihỏitínhfʹ(x).
CôngthứcNewton‐RaphsonđượcsuytừkhaitriểnTaylorc
ủaf(x)lâncậnx:
2
i1 i i i1 i i1 i
f(x ) f(x) f(x)(x x) O(x x)
+++
′
=+ −+ −(1)
Nếux
i+1lànghiệmcủaphươngtrìnhf(x)=0thì(1)trởthành:
2
iii1i i1i
0 f(x ) f (x )(x x ) O(x x )
++
′
=+ −+ −(2)
Giảsửrằngx
igầnvớixi+1,tacóthểbỏquasốhạngcuốitrong(2)vàcócông
thứcNewton‐Raphson:
i
i1 i
i
f(x )
xx
f(x)
+
=−
′
(3)
Nếux
i+1lànghiệmđúngcủaphươngtrìnhthìsaisốlàei=x‐xi.Khinghiệm
đượctínhtheo(3)thìsaisốlà:
248
2
i
i1 i
i
f(x)
ee
2f (x )
+
′′
=−
′
Minh hoạ hình học của thuật toán
Newton‐Raphsonnhưhìnhbên.
Thuậttoánđượctómlượcnhưsau:
‐chox
o
‐tính
f(x)
x
fʹ(x)
∆=−
‐chox=x+∆x
‐lặplạibước2và3chođếnkhi|∆x|≤ε
Taxâydựnghàm
newtonraphson()đểthựchiệnthuậttoántrên.
function[x,fx,xx]=newtonraphson(f,df,x0,tolx,maxiter)
%giaiptf(x)=0bangppNewton‐Raphson.
%vao:f=ftntobegivenasastring’f’ifdefinedinanM‐file
%df=df(x)/dx(neukhongchosedungdaohamso.)
%x0
=giatribandau
%tolx=saisomongmuon
%maxiter=solanlapmax
%ra:x=nghiem
%fx=f(x(last)),xx=cacgiatritrunggian
h=1e‐4;
h2=2*h;
tolf=eps;
ifnargin==4&isnumeric(df)
maxiter=tolx;
tolx=x0;
x0=df;
end
xx(1)=x0;
fx=feval(f,x0);
fork=1:maxiter
if~isnumeric(df)
dfdx=feval(df,xx(k));%daohamcuaham
else
dfdx=(feval(f,xx(k)+h)‐feval(f,xx(k)‐h))/h2;%daohamso
a
b
=xo
x1
y
x
249
end
dx=‐fx/dfdx;
xx(k+1)=xx(k)+dx;%pt.(3)
fx=feval(f,xx(k+1));
ifabs(fx)<tolf|abs(dx)<tolx,
break;
end
end
x=xx(k+1);
ifk==maxiter
fprintf(ʹKhonghoitusau%dlanlap\nʹ,maxiter)
else
fprintf(ʹ
Hoitusau%dlanlap\nʹ,k)
end
Để tính lại nghiệm của hàm cho trong ví dụ trên ta dùng chương trình
ctnewraph.m
clearall,clc
f=inline(ʹx.^3‐10*x.^2+5ʹ);
[x,ss,xx]=newtonraphson(f,0.7,1e‐4,50)
§6.PHƯƠNGPHÁPCÁTTUYẾN
Phươngphápcáttuy ếncóthểcoilàbiếnthểcủaphươngphápNewton
‐Raphsontheonghĩađạohàmđượcthaybằngxấpxỉ:
kk1
kk1
f( x ) f(x )
f(x)
xx
−
−
−
′
≈
−
(1)
vàtốnítthờigiantínhhơnkhidùngđạohàmgiảitíchhayđạohàmsố.
Bằngcáchxấpxỉ,biểuthức:
k
k1 k
k
f(x )
xx
f(x )
+
=−
′
trởthành:
−
+
−
⎡⎤
−
=− =−
⎢⎥
−
⎣⎦
kk1 k
k1 k k k
kk1 k
xx f(x)
xxf(x) x
f(x ) f(x ) dfdx
(2)
với
kk1
k
kk1
f( x ) f(x )
dfdx
xx
−
−
−
=
−
250
Phươngtrình(2)chínhlàbiểuthứctổngquátcủaphéplặp.Haigiátrịđầu
tiênx
1vàx2cầnđểkhởiđộngphépl ặp.Quátrìnhlặpđượcminhhoạbằng
hìnha
Phéplặpcóthểkhônghộitụ(hìnhb).Tuynhiênkhihộitụ,nóhộirấtnhanh.
Taxâydựnghàm
secant()đểthựchiệnthuậttoántrên.
function[x,fx,xx]=secant(f,x0,x1,tolx,maxiter)
%giaiptf(x)=0bgphuongphapdaycung
%vao:f‐hamcantimnghiem
%x0,x1‐giatrikhoidongpheplap
%tolx‐saisomongmuon
%maxiter‐solanlapmax
%ra:x
=nghiem
%fx=f(x(last)),xx=cacgiatritrunggian
h=(x1‐x0)/100;
h2=2*h;
tolfun=eps;
xx(1)=x0;
fx=feval(f,x0);
fork=1:maxiter
ifk<=1
dfdx=(feval(f,xx(k)+h)‐feval(f,xx(k)‐h))/h2;
else
dfdx
=(fx‐fx0)/dx;
x0
x1
x2
f(x)
x
y
a
x0
x1
f(x)
x
y
b
251
end
dx=‐fx/dfdx;
xx(k+1)=xx(k)+dx;%pt.(2)
fx0=fx;
fx=feval(f,xx(k+1));
ifabs(fx)<tolfun|abs(dx)<tolx,
break;
end
end
x=xx(k+1);
ifk==maxiter
fprintf(ʹKhonghoitusau%dlan
lap\nʹ,maxiter)
else
fprintf(ʹHoitusau%dlanlap\nʹ,k)
end
Đểtính nghiệm của hàm f(x) = x
3
‐10x
2
+ 5 ta dùng chương trình
ctsecant.m
clearall,clc
f=inline(ʹx.^3‐10*x.^2+5ʹ);
[x,ss,xx]=secant(f,0.5,1,1e‐4,50)
§7.PHƯƠNGPHÁPBRENT
Phương pháp Brent kêt hợp phương pháp chiađôi cung và phương
phápnộisuybậchaiđểtạo ra mộtphươngpháptìmnghiệm của phương
trìnhf(x) =0rấthiệuquả.Phương
phápnàydùngkhiđạohàmcủaf(x)khó
tínhhaykhôngthểtínhđược.Giảsửtacầntìmnghiêmtrong đoạn[x
1,x2].
Quátrìnhtìmnghiệmbắtđầubằngviệcchiađôiđoạn[x
1,x2]bằngđiểmx3.
x2
x
x3
x
x1
x
x3
x
x2
x1
252
Trongquátrìnhnàytatínhđượcf(x1),f(x2)vàf(x3).Qua 3điểm nàytacómột
đườngcongbậc2vàtìmđượcnghiệmxcủađườngcongbậc2này.Nếux
nằmtrongđoạn[x
1,x2]nhưhìnhtrên thìgiátrịnàyđượcchấpnhận. Tiếp
theotatìmnghiệmtrongđoạn[x
1,x3]hay[x3,x2]tuỳtheovịtrícủax.
ĐathứcnộisuyLagrangequa3điểmlà:
23 13 12
123
1213 2123 3132
(f f )(f f ) (f f )(f f ) (f f )(f f )
x(y) x x x
(f f )(f f ) (f f )(f f ) (f f )(f f )
−− −− −−
=++
−− −− −−
Choy=0tacó:
2312 3 1323 1 1231 2
122331
ffx(f f) ffx(f f) ffx(f f)
x
(f f )(f f )(f f )
−+ −+ −
=−
−−−
(1)
Độthayđổicủanghiệmlà:
31 2 2 3 1 212 3 123 1
33
122331
x (f f )( f f f ) f x (f f ) f x (f f )
xxx f
(f f )(f f )(f f )
−−++ −+ −
∆= − =
−−−
(2)
Taxâydựnghàm
brent()đểthựchiệnthuậttoántrên
functionroot=brent(f,a,b,tol)
%giaiptf(x)=0bangthuattoanBrent.
%Cuphap:root=brent(f,a,b,tol)
%vao:f=hamcantimnghiem
%a,b=doanchuanghiem
%tol=saisochotruoc
ifnargin<
4;
tol=1.0e6*eps;
end
%lanchiadoidautien
x1=a;
f1=feval(f,x1);
iff1==0;
root=x1;
return;
end
x2=b;
f2=feval(f,x2);
iff2==0;
root=x2;
return;
253
end
iff1*f2>0.0
error(ʹNghiemkhongnamtrongdoannayʹ)
end
x3=0.5*(a+b);
%batdaulap.
fori=1:30
f3=feval(f,x3);
ifabs(f3)<tol
root=x3;
return
end
%xacdinhdoanchuanghiem.
if
f1*f3<0.0;
b=x3;
else
a=x3;
end
if(b‐a)<tol*max(abs(b),1.0)
root=0.5*(a+b);
return
end
%noisuybac2.
denom=(f2‐f1)*(f3‐f1)*(f2‐f3);
numer=x3*(f1‐f2)*(f2‐f3+f1)
+f2*x1*(f2‐f3)+
f1*x2*(f3‐f1);
ifdenom==0;
dx=b‐a;
else
dx=f3*numer/denom;
end
x=x3+dx;
%neulaprangoaidoan(a,b),dungcachchiadoicung
if(b‐x)*(x‐a)<0.0
dx=0.5*(b‐a);
x=a+dx;
254
end
%chox=x3&chonx1,x2moisaochox1<x3<x2.
ifx<x3
x2=x3;
f2=f3;
else
x1=x3;
f1=f3;
end
x3=x;
end
root=NaN;
Để tìm nghiệm của phương trìnhx|cos(x)|‐1 = 0 ta dùng chương trình
ctbrent.m
clearall,clc
f=inline(ʹx.*abs(cos(x))‐1ʹ);
x=brent(f,0.0,4,1e‐4)
§8.PHƯƠNGPHÁPNGOẠISUYAITKEN
Xétphươngpháplặp:
x=f(x)(1)
vớif(x)thoảmãnđiềukiệnhộitụcủaphéplặp,nghĩalàvớimọix∈[a,b]ta
có:
|f’(x)|≤q<1(2)
Nhưvậ
y:
x
n+1=f(xn)(3)
x
n=f(xn‐1)(4)
Trừ(3)cho(4)vàápdụngđịnhlíLagrangechovếphảivớic∈[a,b]tacó:
x
n+1‐xn=f(xn)‐f(xn‐1)=(xn‐xn‐1)f’(c)(5)
Vìphéplặp(1)nên:
|x
n+1‐xn|≤q|xn‐xn‐1|(6)
Do(6)đúngvớimọinnênchon=1,2,3,...tacó:
|x
2‐x1|≤q|x1‐xo|
|x
3‐x2|≤q|x2‐x1|
Đăng ký:
Đăng Nhận xét (Atom)
Không có nhận xét nào:
Đăng nhận xét