Cài đặt bài toán: Khớp đường cong bằng phương pháp bình phương nhỏ nhất
LỜI NÓI ĐẦU
Ngày nay thế giới chúng ta đã và đang là kỷ nguyên của sự bùng nổ thông tin. Trong thời đại ngày nay khoa học kỹ thuật ngày một được ứng dụng rộng rãi khắp mọi nơi trong mọi lĩnh vực, mọi nghành nghề và tin học phát triển không ngừng từng giây, từng phút.Máy tính điện tử đươc sử dụng ,khai thác triệt để trong mọi công việc , như trong hàng không , quân sự , ngân hàng ,đo lường , tính toán , và nó cũng được sử dụng để giải quyết các bài toán từ đơn giản đến phức tạp.Đề tài thực tập tốt nghiệp này cũng đựơc áp dụng để thực hiện , tên đề tài: Cài đặt bài toán:"Khớp đường cong" bằng phương pháp bình phương nhỏ nhất.
Để hoàn thành đề tài tốt nghiệp này, bên cạnh nỗ lực của bản thân em còn nhận được sự giúp quý báu của các thầy, cô và các bạn.
Em xin chân thành cảm ơn thầy Dương Thăng Long đã tận tình hướng dẫn em trong suốt quá trình thực hiện đề tài.
Cảm ơn khoa Công nghệ tin học đã tạo mọi điều kiện giúp đỡ em trong suốt quá trình học tập ở trường và các thầy cô đã hết lòng truyền đạt cho em những kiến thức và kinh nghiệm quý giá. Cũng như tất cả các bạn đã cùng trao đổi giúp đỡ nhau trong quá trình học tập.
15 trang |
Chia sẻ: maiphuongtl | Lượt xem: 2035 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Đề tài Cài đặt bài toán: Khớp đường cong bằng phương pháp bình phương nhỏ nhất, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Lêi nãi ®Çu
Ngµy nay thÕ giíi chóng ta ®· vµ ®ang lµ kû nguyªn cña sù bïng næ th«ng tin. Trong thêi ®¹i ngµy nay khoa häc kü thuËt ngµy mét ®îc øng dông réng r·i kh¾p mäi n¬i trong mäi lÜnh vùc, mäi nghµnh nghÒ vµ tin häc ph¸t triÓn kh«ng ngõng tõng gi©y, tõng phót.M¸y tÝnh ®iÖn tö ®¬c sö dông ,khai th¸c triÖt ®Ó trong mäi c«ng viÖc , nh trong hµng kh«ng , qu©n sù , ng©n hµng ,®o lêng , tÝnh to¸n , vµ nã còng ®îc sö dông ®Ó gi¶i quyÕt c¸c bµi to¸n tõ ®¬n gi¶n ®Õn phøc t¹p.§Ò tµi thùc tËp tèt nghiÖp nµy còng ®ù¬c ¸p dông ®Ó thùc hiÖn , tªn ®Ò tµi: Cµi ®Æt bµi to¸n:"Khíp ®êng cong" b»ng ph¬ng ph¸p b×nh ph¬ng nhá nhÊt.
§Ó hoµn thµnh ®Ò tµi tèt nghiÖp nµy, bªn c¹nh nç lùc cña b¶n th©n em cßn nhËn ®îc sù gióp quý b¸u cña c¸c thÇy, c« vµ c¸c b¹n.
Em xin ch©n thµnh c¶m ¬n thÇy D¬ng Th¨ng Long ®· tËn t×nh híng dÉn em trong suèt qu¸ tr×nh thùc hiÖn ®Ò tµi.
C¶m ¬n khoa C«ng nghÖ tin häc ®· t¹o mäi ®iÒu kiÖn gióp ®ì em trong suèt qu¸ tr×nh häc tËp ë trêng vµ c¸c thÇy c« ®· hÕt lßng truyÒn ®¹t cho em nh÷ng kiÕn thøc vµ kinh nghiÖm quý gi¸. Còng nh tÊt c¶ c¸c b¹n ®· cïng trao ®æi gióp ®ì nhau trong qu¸ tr×nh häc tËp.
C¬ së vµ c¸c thuËt to¸n trong ®Ò tµi "Khíp ®êng cong" b»ng ph¬ng ph¸p b×nh ph¬ng nhá nhÊt
1. C¬ së:
Khi nh÷ng gi¸ trÞ d÷ liÖu kh«ng chÝnh x¸c, thêng ta cÇn ph¶i tëng tîng ra h×nh d¹ng cña hµm khíp vµ d÷ liÖu. Hµm nµy cã thÓ phô thuéc mét tham sè.
f(x) = f(c1,c2...., cM, x)
vµ thñ tôc ®iÒu chØnh ®êng cong lµ t×m c¸ch chän c¸c tham sè nµo khíp nhÊt víi c¸c gi¸ trÞ quan s¸t ®îc ë c¸c ®iÓm ®· cho. NÕu hµm lµ mét ®a thøc (víi tham sè lµ nh÷ng hÖ sè) vµ c¸c gi¸ trÞ lµ chÝnh x¸c th× ®©y chÝnh lµ phÐp néi suy. Nhng ta ®ang xÐt nh÷ng hµm tæng qu¸t h¬n vµ d÷ liÖu kh«ng ®óng. §Ó gi¶n ®¬n ho¸ vÊn ®Ò, ta tËp trung vµo viÖc nèi nh÷ng hµm lµ tæ hîp tuyÕn tÝnh cña hµm ®¬n gi¶n h¬n, víi c¸c tham sè Èn lµ c¸c hÖ sè:
f(x) = c1f1(x) + c2f2(x) + ........ +cMfM(x)
Hµm nµy bao hµm hÇu hÕt c¸c hµm mµ ta quan t©m. Sau khi nghiªn cøu xong trêng hîp nµy, ta sÏ xÐt ®Õn nh÷ng hµm tæng qu¸t h¬n.
Mét c¸c phæ th«ng ®Ó ®o møc ®é tèt cña hµm nèi lµ tiªu chuÈn b×nh ph¬ng tæng qu¸t. ë ®©y sai sè ®îc tÝnh b»ng c¸ch thªm vµo b×nh ph¬ng sai sè ë mçi ®iÓm quan s¸t ®îc.
1£ j £N
E = Z (f(xj) - þ)2
§©y lµ mét phÐp ®o rÊt tù nhiªn: b×nh ph¬ng ®îc thùc hiÖn ®Ó lµm khö c¸c íc lîc gi÷a c¸c sai sè víi c¸c sè hiÖu kh¸c nhau. HiÓn nhiªn, ®iÒu ngêi ta mong muèn nhÊt lµ t×m ra mét phÐp chän c¸c tham sè sao cho tèi thiÓu ho¸ E. §iÒu nµy khiÕn phÐp chän cã thÓ ®îc tÝnh cã hiÖu qña; ®©y lµ ph¬ng ph¸p b×nh ph¬ng nhá nhÊt, ph¬ng ph¸p nµy ®óng nh ®Þnh nghÜa cña nã. §Ó ®¬n gi¶n ho¸ ®¹o hµm, xÐt trêng hîp M=2, N=3. Gi¶ sö cã ba ®iÓm x1, x2,x3 vµ c¸c gi¸ trÞ t¬ng øng y1,y2,y3 tho¶ hµm cã d¹ng:
f(x) = (c1f1(x1) + c2f2(x1) - y1)2
+ (c1f1(x2) + c2f2(x2) - y2)2
+ (c1f1(x3) + c2f2(x3) - y3)2
§Ó t×m c¸c phÐp chän cña c1 vµ c2 sao chá tèi tiÓu ho¸ sao sè nµy, ®¬n gian chØ cÇn g¸n zero c¸c ®¹o hµm dE/dc1 vµ dE/dc2 Víi c1 ta cã :
dE/dc1 = 2(c1f1(x1) + c2f2(x1) - y1)2 f1(x1)
+ (c1f1(x2) + c2f2(x2) - y2)2 f2(x2)
+ (c1f1(x3) + c2f2(x3) - y3)2 f3(x3)
ViÖc g¸n ®¹o hµm b»ng zero cho ra ph¬ng tr×nh cã biÕn lµ c1 vµ c2 ph¶i tho¶ (f1(x1), lµ c¸c "h»ng sè" cã trÞ biÕt tríc).
c1(f1(x1)f1(x1) + f1(x2)f1(x2) + (f1(x3)f1(x3)
+ c2(f2(x1)f1(x1) + (f2(x2)f1(x2) + (f2(x3)f1(x3))
= y1f1 (x1) + y2f1 (x2) + y3f1 (x3)
Ta cã ph¬ng tr×nh t¬ng tù, khi g¸n ®¹o hµm dE/dc2 vÒ zero
Gi¶ sö ®a thøc xÊp xØ bËc m cña f lµ P(x) = Sj=0 Cjx
víi Cj (j = O1m) x¸c ®Þnh tõ hÖ D0C0 +D1C1 + ...... + DmCm = t0
D1C0 +D2C1 + ...... + Dm+1Cm = t1
..............
DmC0 +Dm+1C1 + ...... + D2mCm = tm
Trong ®ã Dk = S xg (k= 0,2m)
ti = S xg f (xg) (i = o1m)
víi Cj (j = 0,m) x¸c ®Þnh tõ hÖ ph¬ng tr×nh trªn trong ®ã.
2. C¸c thuËt to¸n dïng trong ch¬ng tr×nh Cµi ®Æt bµi to¸n: "Khíp ®êng cong" b»ng ph¬ng ph¸p b×nh ph¬ng nhá nhÊt
2.1. NhËp d÷ liÖu
+ nhËp tõ file:
NhËp c¸c to¹ ®é xi , yi vµo m¸y to¹ ®é, sè ®iÓm n, bËc m cña ®a thøc.
- hái xem cã ghi vµo file kh«ng nÕu hái nhËp tªn tªn file ghi d÷ liÖu vµo file ®ã.
+ nhËp tõ file:
yªu cÇu nhËp vµo tªn file, ®äc file Read (f,n,m) n¹p c¸c qt tõ file vµo hai m¶ng to¹ ®é do x, to¹ ®é y
For i = 1-> n
Read (f, to¹ ®é x[i], to¹ ®é y[i])
2.2. TÝnh m¶ng
-TÝnh to¸n c¸c hÖ sè cña m¶ng
a[i] [j], b[i] theo hÖ pt (1)
2.3.Dïng ph¬ng ph¸p gauss vµ thuËt to¸n sytru gi¶i hÖ pt (1)
Gauss
Input n, (¹i)1n; (bi)1n
IER = 0
akk ¹ 0
Pi=aik/akk
k= 1, 2,...,n
i= k + 1, ..., n
j= k + 1, ..., n
aþj = piakj
bi = bi - pibk
Call Sytru
IER = 1
Print (xi)1n
End
ThuËt to¸n gauss (§a ma trËn vÒ d¹ng tam gi¸c )
no
yesthuËt to¸n Sytru (gi¶i hÖ ph¬ng tr×nh d¹ng tam gi¸c)
IRE = 1
Procedure
Input n, {bi}1n, aij (1£ i £ j £ n)
IER = 0
ann ¹ 0
xn = bn / ann
i = n-1, n-2,...,1
S = bi
j = i + 1, ..., n
S = S - aijxij
aij ¹ 0
xi = S/aij
Return
Procedure
Input n, {bi}1n, aij (1£ i £ j £ n)
IER = 0
ann ¹ 0
xn = bn / ann
i = n-1, n-2,...,1
S = bi
j = i + 1, ..., n
S = S - aijxij
aij ¹ 0
xi = S/aij
Return
no
yes
no
yes
2.4. X©y dùng hµm tÝnh gi¸ trÞ
2.4.1. Hµm tÝnh luü thõa
Fuction luü thõa (x: Real; n: integer): real.
S : Real
i : integer
S = 1
For i = 1 ® n
S = S*x
Return S.;
2.4.2. X©y dùng hµm tÝnh f(x)
For i = m ® 0
S = S + C (i + 1) + luü thõa (x, i)
3. VÏ ®å thÞ
3.1. T×m xmin , xmax , ymin , ymax ,trong toµn ®å thÞ vµ c¸c ®iÓm nhËp vµo x¸c ®Þnh kx , xy
Kx = (Lmax - Lmin)/ (xmax - xmin)
(Hmax - H min)
(ymax - ymin)
Ky =
vÏ ®å thÞ tõ ®iÓm
x1-> x2 , x = x1,
i = 0
while x<x2
i = i + 1
Begin
x = x1 + x2 i/ kx
yvÏ = H max- (f(x) - ymin)*xy
if'i = 1 -> move to (i + lmin, yvÏ)
ESC line to (i + lmin, yvÏ)
+ vÏ trôc, to¹ ®é
+ vÏ c¸c ®iÓm nhËp vµo
For i = 1 -> n
Begin
x = kx + (to¹ ®é x[i]) - ymin)
y vÏ = Hmax - (Toado y[i]) - ymin)*ky
vÏ ®iÓm (x+lmin, yvÏ, to¹ ®é x[i], to¹ ®é y[i]);
4. Ch¬ng tr×nh b»ng ph¬ng ph¸p b×nh ph¬ng
M· nguån
uses crt,graph;
const Hmin=150;
Lmin=200;
Hmax=480-Hmin;
Lmax=640-Lmin;
Type mang2=array[1..20,1..20] of real;
mang1=array[1..20] of real;
mang_diem=array[1..20] of real;
var
a:mang2;
b:mang1;
n,m:integer;
toadox,toadoy:mang_diem;
c:mang1;
ok:boolean;
r:real;
(*----------------------------*)
procedure hien_mang(so:integer;a:mang2;b:mang1);
var i,j:integer;
Begin
{for i:=1 to so do
begin
for j:=1 to so do
write(a[i,j]:0:2,' ');
write(' | ',b[i]:0:2);
writeln;
end; }
End;
(*----------------------------*)
function luythua(x:real;n:integer):real;
var
i:integer;
s:real;
Begin
s:=1;
if n>0 then
for i:=1 to n do
s:=s*x;
luythua:=s;
End;
(*----------------------------*)
procedure nhap_tu_ban_fim(var n,m:integer;var toadox,toadoy:mang_diem);
var
i:integer;
x,y:real;
ch:char;
tenfile:string;
f:text;
Begin
textcolor(14);
textbackground(1);
window(1,1,80,24);
clrscr;
write('Nhap vao so diem:');readln(n);
writeln('Nhap vao cac diem:');
for i:=1 to n do
begin
write('vao toa do cua diem ',i,' x=');readln(toadox[i]);
write('vao toa do cua diem ',i,' y=');readln(toadoy[i]);
end;
write('Nhap vao so bac:');readln(m);
Writeln('Nhap Du Lieu OK !');
repeat
Write('Ban CO Muon Ghi Du Lieu Vao File Khong (C/K)?:');
ch:=readkey;
until upcase(ch) in['C','K'];
writeln;
if upcase(ch)='C' then
Begin
write('Moi nhap vao ten file:');
readln(tenfile);
assign(f,tenfile);
{$I-}
rewrite(f);
if IOResult 0 then
begin
gotoxy(30,10);
Writeln('File not found');
readln;
exit;
end;
{$I+}
writeln(f,n,' ',m);
for i:=1 to n do
write(f,toadox[i],' ',toadoy[i],' ');
close(f);
Writeln('Nhap File OK !');
readkey;
end;
end;
(*----------------------------------*)
procedure nhap_tu_file(var n,m:integer;
var toadox,toadoy:mang_diem);
var f:text;
tenfile:string;
i:integer;
Begin
n:=0;
m:=0;
write('Moi nhap vao ten file:');
readln(tenfile);
assign(f,tenfile);
{$I-}
reset(f);
if IOResult 0 then
begin
gotoxy(30,10);
Writeln('File not found');
readln;
exit;
end;
{$I+}
readln(f,n,m);
for i:=1 to n do
read(f,toadox[i],toadoy[i]);
close(f);
Writeln(' Nhap Tu File Ok !');
readkey;
End;
(*----------------------------------*)
procedure tinh_mang;
var i,j,dem:integer;
so:array[0..200] of real;
Begin
dem:=0;
for i:=0 to 2*m do
begin
so[i]:=0;
for j:=1 to n do
so[i]:=so[i]+luythua(toadox[j],i);
end;
for i:=0 to m do
begin
dem:=i*2-1;
for j:=i to m do
begin
dem:=dem+1;
a[i+1,j+1]:=so[dem];
a[j+1,i+1]:=so[dem];
end;
end;
for i:=0 to m do
begin
b[i+1]:=0;
for j:=1 to n do
b[i+1]:=b[i+1]+toadoy[j]*luythua(toadox[j],i);
end;
End;
(*--------------- Giai Phuong Trinh --------------*)
procedure gauss(m:integer;a:mang2;b:mang1;
var nghiem:mang1;var ok:boolean);
var
k,i,j:integer;
s:real;
mi:mang1;
Begin
ok:=true;
for i:=1 to m+1 do
Begin
if a[i,i]=0 then begin ok:=false;exit;end;
for j:=i+1 to m+1 do
mi[j]:=a[j,i]/a[i,i];
for j:=i+1 to m+1 do
begin
for k:=1 to m+1 do
a[j,k]:=a[j,k]-a[i,k]*mi[j];
b[j]:=b[j]-b[i]*mi[j];
end;
End;
(*----------------Sytru-------------*)
nghiem[m+1]:=b[m+1]/a[m+1,m+1];
for i:=m downto 1 do
Begin
s:=b[i];
for j:=i+1 to m+1 do
s:=s-a[i,j]*nghiem[j];
nghiem[i]:=s/a[i,i];
end;
End;
(*----------------------------------*)
function f(x:real;n,m:integer;c:mang1):real;
var s:real;
i:integer;
Begin
s:=0;
for i:=m downto 0 do
s:=s+c[i+1]*luythua(x,i);
f:=s;
End;
(*----------------------------------*)
Procedure Tinh_Min_Max_X_Y_(n,m:integer;c:mang1;
var kx:real;var xmin,xmax,ymin,ymax:real);
var i,j:integer;
x:real;
Begin
xmin:=toadox[1];
xmax:=toadox[1];
ymin:=toadoy[1];
ymax:=toadoy[1];
for i:=1 to n do
begin
if xmin>toadox[i] then xmin:=toadox[i];
if xmax<toadox[i] then xmax:=toadox[i];
if ymin>toadoy[i] then ymin:=toadoy[i];
if ymax<toadoy[i] then ymax:=toadoy[i];
end;
i:=0;
if xmaxxmin then
begin
kx:=abs((lmax-lmin)/(xmax-xmin));
while x<xmax do
begin
i:=i+1;
x:=xmin+(i/kx);
if ymin>f(x,n,m,c) then ymin:=f(x,n,m,c);
if ymax<f(x,n,m,c) then ymax:=f(x,n,m,c);
end;
end;
End;
(*----------------------------------*)
procedure draw_point(x,y:integer;x1,y1:real);
var i:integer;
s1,s2:string;
Begin
setcolor(13);
line(x-2,y-2,x+2,y+2);
line(x+2,y-2,x-2,y+2);
if(x>320) then i:=10 else i:=-100;
Str(x1:0:1,s1);
Str(y1:0:1,s2);
s1:='('+s1+','+s2+')';
outtextxy(x+i,y,s1);
End;
(*----------------------------------*)
Procedure Ve_do_thi(n,m:integer;c:mang1);
Var
kx,ky:real;
x,yve,xmin,xmax,ymin,ymax:real;
i,j:integer;
gd,gm:integer;
s1,s2:string;
Begin
Tinh_Min_Max_X_Y_(n,m,c,kx,xmin,xmax,ymin,ymax);
gd:=detect;
initgraph(gd,gm,'');
setfillstyle(1,0);
bar(0,0,getmaxx,getmaxy);
if yminymax then
begin
i:=0;
ky:=abs((hmax-hmin)/(ymax-ymin));
setcolor(13);
x:=xmin;
if xminxmax then
begin
(* Ve do Thi *)
x:=xmin;
setcolor(14);
i:=0;
while x<xmax do
Begin
x:=xmin+i/kx;
yve:=hmax-(f(x,n,m,c)-ymin)*ky;
if i=0 then
moveto(lmin,round(yve));
lineto(lmin+i,round(yve));
inc(i);
end;
for i:=1 to n do
Begin
x:=kx*(toadox[i]-xmin);
yve:=hmax-(toadoy[i]-ymin)*ky;
draw_point(round(x+lmin),round(yve),toadox[i],toadoy[i]);
end;
if round((-xmin)*kx)+lmin<640 then
if round((-xmin)*kx)+lmin>=0 then
begin
setcolor(15);
yve:=hmax-(ymax-ymin)*ky;
line(round((-xmin)*kx)+lmin,5,round((-xmin)*kx+lmin),480);
line(round((-xmin)*kx)+lmin,5,round((-xmin)*kx)+lmin-3,5+3);
line(round((-xmin)*kx)+lmin,5,round((-xmin)*kx)+lmin+3,5+3);
setcolor(13);
outtextxy(round((-xmin)*kx)+lmin+10,20,'Y');
end;
yve:=hmax+(ymin)*ky;
(* Ve truc Hoanh *)
if (yve>0)and(yve<480) then
begin
setcolor(15);
line(5,round(yve),639,round(yve));
line(639,round(yve),639-3,round(yve)+3);
line(639,round(yve),639-3,round(yve)-3);
setcolor(13);
outtextxy(600,round(yve)-20,'X');
end;
End
else line(320,hmin,320,hmax);
end
else
Begin
if xminxmax then
line(lmin+10,240,lmax-10,240)
else putpixel(320,240,14);
End;
readkey;
closegraph;
End;
(*----------------------------------*)
procedure Menu;
var
ch:char;
i:integer;
Begin
gotoxy(10,3);
Writeln('Chuong Trinh Khop Ham so Bang Phuong Phap Binh Phuong Nho Nhat');
gotoxy(10,4);
Writeln('---------------------------- =o0o= ----------------------------');
gotoxy(30,5);
Writeln(' 1. Nhap Du Lieu Tu Ban Phim ');
gotoxy(30,6);
Writeln(' 2. Nhap Tu File ');
gotoxy(30,7);
Writeln(' 3. Xem Cac He So ');
gotoxy(30,8);
Writeln(' 4. Ve Do Thi ');
gotoxy(30,9);
Writeln(' 5. Thoat Khoi Chuong Trinh ');
gotoxy(25,11);
Write('Ban Hay Chon Mot Trong Cac So:');
repeat
ch:=readkey;
case ch of
'1':begin
clrscr;
nhap_tu_ban_fim(n,m,toadox,toadoy);
Writeln('Nap Du Lieu Ok !');
tinh_mang;
gauss(m,a,b,c,ok);
Readln;
exit;
end;
'2':begin
clrscr;
nhap_tu_file(n,m,toadox,toadoy);
Writeln('Nap Du Lieu Ok !');
tinh_mang;
gauss(m,a,b,c,ok);
Readln;
exit;
end;
'3':begin
clrscr;
if n>0 then
begin
hien_mang(m+1,a,b);
for i:=m+1 downto 1 do
writeln('c[',i,']:',c[i]:0:4);
end
else
Writeln('Ban Chua Vao Du Lieu !');
readkey;
exit;
end;
'4':begin
clrscr;
if (n>0)then
begin
if ok then
ve_do_thi(n,m,c)
else Writeln('Khong the khop ham');
end
else Writeln('Ban Chua Nap Du Lieu');
readkey;
exit;
end;
'5':halt(1);
end;
until false;
End;
(*------------ Chuong Trinh Chinh------------*)
Begin
n:=0;
m:=0;
repeat
textcolor(14);
textbackground(1);
clrscr;
menu;
until false;
End.
Các file đính kèm theo tài liệu này:
- 80746.DOC