sơ đồ khối biểu diễn thuật toán và chương trình viết bằng ngôn ngữ c

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

Lêi nãi ®Çu

To¸n häc lµ mét m«n khoa häc chiÕm vÞ trÝ quan träng kh«ng thÓ thiÕu

trong cuéc sèng con nguêi.

Cïng víi sù ph¸t triÓn néi t¹i cña to¸n häc vµ c¸c ngµnh khoa häc kh¸c,

to¸n häc chia thµnh to¸n lý thuyÕt vµ to¸n øng dông.

Gi¶i tÝch sè hay cßn gäi lµ ph¬ng ph¸p sè lµ m«n khoa häc thuéc lÜnh

vùc to¸n øng dông nghiªn cøu c¸ch gi¶i gÇn ®óng c¸c ph¬ng tr×nh, c¸c bµi

to¸n xÊp xØ hµm sè vµ c¸c bµi to¸n tèi u.

ViÖc gi¶i mét bµi to¸n xÊp xØ hµm sè nh»m môc ®Ých thay mét hµm sè

díi d¹ng phøc t¹p nh d¹ng biÓu thøc hoÆc mét hµm sè díi d¹ng b¶ng b»ng

nh÷ng hµm sè ®¬n gi¶n h¬n. Trong lý thuyÕt xÊp xØ hµm ngêi ta thêng

nghiªn cøu c¸c bµi to¸n néi suy, bµi to¸n xÊp xØ ®Òu vµ bµi to¸n xÊp xØ trung

b×nh ph¬ng.

Trong ®å ¸n nµy em ®Ò cËp ®Õn bµi to¸n dïng ph¬ng ph¸p xÊp xØ trung

b×nh ph¬ng hay cßn gäi lµ ph¬ng ph¸p b×nh ph¬ng tèi thiÓu ®Ó xÊp xØ hµm

trong thùc nghiÖm.

§Ó hoµn thµnh ®å ¸n nµy em xin ch©n thµnh c¶m ¬n c¸c thÇy c« trong

khoa To¸n tin øng dông- Trêng ®¹i häc B¸ch Khoa Hµ Néi ®· quan t©m gióp

®ì em vµ t¹o mäi ®iÒu kiÖn cho em trong suèt qu¸ tr×nh lµm ®å ¸n. §Æc biÖt

em xin ch©n thµnh göi lêi c¶m ¬n ®Õn PGS-TS Lª Träng Vinh, ngêi ®·

trùc tiÕp tËn t×nh híng dÉn, chØ b¶o vÒ kinh nghiÖm vµ tµi liÖu trong suèt qu¸

tr×nh em lµm ®å ¸n tèt nghiÖp.

Em xin ch©n thµnh c¶m ¬n!

Hµ Néi, th¸ng 5 n¨m 2008

Bïi V¨n B»ng

-------------------------------------------------------------------------------------------------------

- 1 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

Ch¬ng I

PH¦¥NG PH¸P B×NH PH¦¥NG TèI THIÓU

LËP C¤NG THøC Tõ THùC NGHIÖM

1.1 Giíi thiÖu chung

1.1.1 §Æt vÊn ®Ò

Cã rÊt nhiÒu ph¬ng ph¸p kh¸c nhau ®Ó lËp nh÷ng ®a thøc tõ thùc nghiÖm

mµ ta ®· biÕt ®Õn nh phÐp néi suy ®Ó lËp ®a thøc cÊp n: ϕ( ) x (®¹i sè hoÆc l￾îng gi¸c) xÊp xØ hµm sè y f x = ( ) mµ ta ®· biÕt c¸c gi¸ trÞ cña hµm nµy lµ

i

y y = t¹i c¸c ®iÓm i

x x = . Ph¬ng ph¸p néi suy nãi trªn khi sö dông trong

thùc tiÔn th× cã nh÷ng ®iÒu cÇn c©n nh¾c lµ:

1. Trong c¸c ®a thøc néi suy ϕ( ) x ta ®ßi hái i ϕ(x ) = i

y . Tuy nhiªn sù ®ßi

hái nµy kh«ng cã ý nghÜa nhiÒu trong thùc tÕ. Bëi v× c¸c sè i

y lµ gi¸ trÞ

cña hµm y f x = ( ) t¹i c¸c ®iÓm i

x x = , trong thùc tÕ chóng ta cho díi

d¹ng b¶ng vµ thêng thu ®îc tõ nh÷ng kÕt qu¶ ®o ®¹c hoÆc tÝnh to¸n

trong thùc hµnh. Nh÷ng sè y i

nµy nãi chung chØ xÊp xØ víi c¸c gi¸ trÞ

®óng ( )i

f x cña hµm y f x = ( )t¹i i

x x = . Sai sè m¾c ph¶i ( ) i i i ε = − y f x

nãi chung kh¸c kh«ng. NÕu buéc ( )i i ϕ x y = th× thùc chÊt ®· ®em vµo

bµi to¸n c¸c sai sè i

ε cña c¸c sè liÖu ban ®Çu nãi trªn (chø kh«ng ph¶i

lµ lµm cho gi¸ trÞ cña hµm néi suy ϕ(x) vµ hµm f x( ) trïng nhau t¹i c¸c

®iÓm i

x x = ).

2. §Ó cho ®a thøc néi suy ϕ(x) biÓu diÔn xÊp xØ hµm f x( ) mét c¸ch s¸t

thùc ®¬ng nhiªn cÇn t¨ng sè mèc néi suy i

x (nghÜa lµ lµm gi¶m sai sè

cña c«ng thøc néi suy). Nhng ®iÒu nµy l¹i kÐo theo cÊp cña ®a thøc néi

suy t¨ng lªn do ®ã nh÷ng ®a thøc néi suy thu ®îc kh¸ cång kÒnh g©y

khã kh¨n cho viÖc thiÕt lËp còng nh dùa vµo ®ã ®Ó tÝnh gi¸ trÞ gÇn ®óng

hoÆc kh¶o s¸t hµm f x( ).

-------------------------------------------------------------------------------------------------------

- 2 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

1.1.2 Bµi to¸n ®Æt ra

ChÝnh v× nh÷ng lý trªn nªn ph¬ng ph¸p t×m hµm xÊp xØ cã thÓ sÏ s¸t thùc

h¬n th«ng qua hai bµi to¸n:

Bµi to¸n 1(t×m hµm xÊp xØ).

Gi¶ sö ®· biÕt gi¸ trÞ i

y ( 1,2,..., ) i n = cña hµm y f x = ( ) t¹i c¸c ®iÓm

t¬ng øng i

x x = . T×m hµm ( ) m φ x xÊp xØ víi hµm f(x) trong ®ã

0

φ ϕ ( ) ( ).

=

= ∑

m

m i i

i

x a x (1 - 1)

víi (x) ϕi

lµ nh÷ng hµm ®· biÕt, i

a lµ nh÷ng hÖ sè h»ng sè.

Trong khi gi¶i quyÕt bµi to¸n nµy cÇn chän hµm (x) φ m

sao cho qu¸ tr×nh tÝnh

to¸n ®¬n gi¶n ®ång thêi nhng sai sè i

ε cã tÝnh chÊt ngÉu nhiªn (xuÊt hiÖn khi

thu ®îc c¸c sè liÖu i

y ) cÇn ph¶i ®îc chØnh lý trong qu¸ tr×nh tÝnh to¸n. Trong

bµi to¸n t×m hµm xÊp xØ trªn viÖc chän d¹ng cña hµm xÊp xØ (x) φ m

lµ tïy

thuéc ý nghÜa thùc tiÔn cña hµm f(x).

Bµi to¸n 2 (t×m c¸c tham sè cña mét hµm cã d¹ng ®· biÕt).

Gi¶ sö ®· biÕt d¹ng tæng qu¸t cña hµm

0 1 ( , , ,..., ) Y f x a a a = m

(1 –

2)

Trong ®ã: i

a ( 1,2,..., ) i m = lµ nh÷ng h»ng sè.

Gi¶ sö qua thùc nghiÖm ta thu ®îc n gi¸ trÞ cña hµm = i

y y ( 1,2,..., ) i m =

øng víi c¸c gi¸ trÞ i

x x = cña ®èi. VÊn ®Ò lµ tõ nh÷ng sè liÖu thùc nghiÖm

thu ®îc cÇn x¸c ®Þnh c¸c gi¸ trÞ cña tham sè 0 1 , ,..., m

a a a ®Ó t×m ®îc d¹ng cô

thÓ cña biÓu thøc (1 – 2): y f x = ( ) vÒ sù phô thuéc hµm sè gi÷a y vµ x .

1.2 Sai sè trung b×nh ph¬ng vµ ph¬ng ph¸p b×nh ph¬ng tèi thiÓu t×m xÊp

xØ tèt nhÊt víi mét hµm

1.2.1 Sai sè trung b×nh ph¬ng

-------------------------------------------------------------------------------------------------------

- 3 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

Nh÷ng hµm trong thùc nghiÖm thu ®îc thêng m¾c ph¶i nh÷ng sai sè cã

tÝnh chÊt ngÉu nhiªn. Nh÷ng sai sè nµy xuÊt hiÖn do sù t¸c ®éng cña nh÷ng

yÕu tè ngÉu nhiªn vµo kÕt qu¶ thùc nghiÖm ®Ó thu ®îc c¸c gi¸ trÞ cña hµm.

ChÝnh v× lý do trªn, ®Ó ®¸nh gi¸ sù sai kh¸c gi÷a hai hµm trong thùc

nghiÖm ta cÇn ®a ra kh¸i niÖm vÒ sai sè (hoÆc ®é lÖch) sao cho mét mÆt nã

chÊp nhËn ®îc trong thùc tÕ, mét mÆt l¹i san b»ng nh÷ng sai sè ngÉu nhiªn

(nghÜa lµ g¹t bá ®îc nh÷ng yÕu tè ngÉu nhiªn t¸c ®éng vµo kÕt qu¶ cña thùc

nghiÖm). Cô thÓ nÕu hai hµm thùc chÊt kh¸ gÇn nhau th× sai sè chóng ta ®a ra

ph¶i kh¸ bÐ trªn miÒn ®ang xÐt.

Kh¸i niÖm vÒ sai sè nãi trªn cã nghÜa lµ kh«ng chó ý tíi nh÷ng kÕt qu¶

cã tÝnh chÊt c¸ biÖt mµ xÐt trªn mét miÒn nªn ®îc gäi lµ sai sè trung b×nh ph-

¬ng.

1.2.2 §Þnh nghÜa

Theo ®Þnh nghÜa ta sÏ gäi σ n

lµ sai sè (hoÆc ®é lÖch) trung b×nh ph¬ng cña

hai hµm f x( ) vµ ϕ( ) x trªn tËp 1 2 = ( , ,..., ) X x x xn

, nÕu

σ n

= ∑=

−

n

i

i i

f x x

n 1

2

[ ( ) ( )] 1

ϕ . (2 –

1)

1.2.3 ý nghÜa cña sai sè trung b×nh ph¬ng

§Ó t×m hiÓu ý nghÜa cña sai sè trung b×nh ph¬ng ta gi¶ thiÕt f x( ) , ϕ (x) lµ

nh÷ng hµm liªn tôc trªn ®o¹n [ a b, ] vµ 1 2 = ( , ,..., ) X x x xn

lµ tËp hîp c¸c ®iÓm

c¸ch ®Òu trªn [ a b, ]

1 2 = < < < = ...

n

a x x x b

Theo ®Þnh nghÜa fÝch ph©n x¸c ®Þnh ta cã

lim n

n

σ σ

→∞

= (2 –

2)

Trong ®ã:

-------------------------------------------------------------------------------------------------------

- 4 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

2 σ =

b − a

1

f x x dx

b

a

∫

−

2

[ ( ) ϕ( )] . (2 –

3)

Gi¶ sö f x x ( ) ( ) −ϕ cã trªn [ a b, ] mét sè h÷u h¹n cùc trÞ vµ α lµ mét sè d-

¬ng nµo ®ã cho tríc. Khi ®ã trªn [ a b, ] sÏ cã k ®o¹n riªng biÖt [ , ] i i a b

( 1,2,..., ) i k = sao cho

f x x ( ) ( ) − ≥ ϕ α (víi ∈[ , ] i i x a b , ( 1,2,..., ) i k = )

Gäi ω lµ tæng c¸c ®é dµi cña k ®o¹n nãi trªn.

Víi n ®ñ lín vµ σ n ®ñ bÐ, tõ (2 – 2) ta suy ra σ <ε (ε bÐ tïy ý). Tõ (2 – 3)

suy ra

( )

2

ε b − a > ∫

−

b

a

f x x dx 2

[ ( ) ϕ( )] ≥ ∑∫

=

−

k

i

b

a

i

i

f x x dx

1

2

[ ( ) ϕ( )] ≥ α ω

2

.

Do ®ã

2

( ) ε

ω

α

 

< −  ÷   b a .

NghÜa lµ tæng ®é dµi ω cña c¸c ®o¹n [ , ] i i a b sÏ bÐ tïy ý.

Tãm l¹i: víi σ n

®ñ bÐ (n kh¸ lín) th× trªn ®o¹n [ a b, ] (trõ t¹i nh÷ng ®iÓm cña

nh÷ng ®o¹n [ , ] i i a b mµ cã tæng ®é dµi ω bÐ tïy ý), ta cã

f x x ( ) ( ) − < ϕ α .

Trong ®ã α lµ mét sè d¬ng tïy ý cho tríc.

Tõ nhËn xÐt trªn ta rót ra nh÷ng ý nghÜa thùc tiÔn cña sai sè trung b×nh

ph¬ng nh sau:

NÕu sai sè trung b×nh ph¬ng σ n

cña hai hµm f(x) vµ ϕ(x) trªn tËp hîp n

®iÓm [ a b X , ] ⊂ (n ®ñ lín) mµ kh¸ bÐ th× víi tuyÖt ®¹i ®a sè gi¸ trÞ cña x trªn

[a, b] cho sai sè tuyÖt ®èi gi÷a f(x) vµ ϕ(x) kh¸ bÐ.

1.2.4 XÊp xØ hµm theo nghÜa trung b×nh ph¬ng

-------------------------------------------------------------------------------------------------------

- 5 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48

§å ¸n tèt nghiÖp

--------------------------------------------------------------------------------------------

Tõ ý nghÜa cña sai sè trung b×nh ph¬ng nãi trªn

Ta nhËn thÊy nÕu c¸c gi¸ trÞ i

y ( 1,2,..., ) i n = cña hµm f x( ) t¹i c¸c ®iÓm i

x

vµ nÕu sai sè trung b×nh ph¬ng

σ n

= ∑=

−

n

i

i i

y x

n 1

2

[ ( )] 1

ϕ

kh¸ bÐ th× hµm ϕ(x) sÏ xÊp xØ kh¸ tèt víi hµm f x( ) .

C¸ch xÊp xØ mét hµm sè lÊy sai sè trung b×nh ph¬ng lµm tiªu chuÈn ®¸nh

gi¸ nh trªn gäi lµ xÊp xØ hµm theo nghÜa trung b×nh ph¬ng.

Râ rµng: NÕu hµm f x( ) thu ®îc b»ng thùc nghiÖm (nghÜa lµ ≈ ( ) i i y f x )

th× c¸ch xÊp xØ nãi trªn ®· san b»ng nh÷ng sai l¹c t¹i tõng ®iÓm (n¶y sinh do

nh÷ng sai sè ngÉu nhiªn cña thùc nghiÖm). §ã lµ lý do gi¶i thÝch lý do v× sao

ph¬ng ph¸p xÊp xØ theo nghÜa trung b×nh ph¬ng ®îc sö dông réng r·i trong

thùc tiÔn.

Ta xÐt trêng hîp ϕ( ) x lµ phô thuéc c¸c tham sè 0 1 , ,..., m

a a a

0 1 ϕ( ) ( ; , ,..., ) = m

x x a a a . (2 –

4)

Trong sè nh÷ng hµm ϕ( ) x cã d¹ng (2 – 4) ta sÏ gäi hµm

ϕ( ) ( ; , ,..., ) x x a a a = 0 1 m (2 –

5)

lµ xÊp xØ tèt nhÊt theo nghÜa trung b×nh ph¬ng víi hµm f x( ) nÕu sai sè trung

b×nh ph¬ng ϕ( ) x víi f x( ) lµ bÐ nhÊt. Cô thÓ lµ

0 1 0 1 σ σ n n m

( , ,..., ) min ( , ,..., ) a a a a a a m =

trong ®ã

[ ]

2

0 1 0 1

1

1

σ ϕ ( , ,..., ) ( ; , ,..., )

=

= − ∑

n

n m i m

i

a a a y x a a a

n

. (2 –

6)

Tõ (2 – 6) ta nhËn thÊy (2 – 5) t¬ng ®¬ng víi ®¼ng thøc:

-------------------------------------------------------------------------------------------------------

- 6 - Sinh viên thực hiện: Bùi Văn Bằng

Lớp: Toán Tin_2 – K48