Algebra 2-09 interpolacja wielomianowa.pdf

Wykład9

Interpolacjawielomianowa

Niech K b¦dziepewnymciałeminiech a 1 ,a 2 ,...,a n ,b 1 ,b 2 ,...,b n b¦d¡

pewnymielementamiciała K ( a i 6 = a j dla i 6 = j ).Zadaniejestnast¦puj¡ce.

Chcemyznale¹¢wielomian f ( x ) 2 K [ x ],taki»e

f ( a 1 )= b 1 ,f ( a 2 )= b 2 ,...,f ( a n )= b n

Podamyterazdwasposobykonstrukcjitakichwielomianów.

I. InterpolacjaLagrange’a.

Budujemywyra»enia:

f i ( x )= ( x − a 1 )( x − a 2 ) ... ( x − a i − 1 )( x − a i +1 ) ... ( x − a n )

( a i − a 1 )( a i − a 2 ) ... ( a i − a i − 1 )( a i − a i +1 ) ... ( a i − a n )

Mo»nazauwa»y¢,»e f i ( a i )=1idla i 6 = j , f i ( a j )=0.Wtedynaszym

poszukiwanymwielomianemb¦dzie:

f ( x )= b 1 f 1 ( x )+ b 2 f 2 ( x )+ ... + b n f n ( x )

Przykład Wyznaczy¢wielomian f ( x ) 2 R [ x ],taki»e

f (1)=2 ,f (2)= − 1 ,f (3)=3

2 · 1 =

( x − 2)( x − 3)+( x − 1)( x − 3)+ 3 2 ( x − 1)( x − 2)

II. InterpolacjaNewtona.

Wielomianwtymprzypadkubudujemynast¦puj¡co:

f ( x )= c 0 + c 1 ( x − a 1 )+ c 2 ( x − a 1 )( x − a 2 )+ ... + c n − 1 ( x − a 1 ) ... ( x − a n − 1 )

Wstawianiekolejnoza x warto±ci a 1 ,...,a n iprzyrównanieichdo b 1 ,...,b n

pozwolinamjednoznaczniewyznaczy¢warto±ci c 0 ,...,c n − 1 .

Przykład Wyznaczymyt¡metod¡wielomian f ( x ),któryspełniatesame

własno±cicowielomianzpoprzedniegoprzykładu.Naszwielomianmateraz

posta¢:

f ( x )= c 0 + c 1 ( x − 1)+ c 2 ( x − 1)( x − 2)

Wstawiamykolejnoza x :1 , 2 , 3iotrzymujemy:

f (1)= c 0 =2

f (2)= c 0 + c 1 = − 1

f (3)= c 0 +2 c 1 +2 c 2 =3

Rozwi¡zaniemtegoukładujest c 0 =2 ,c 1 = − 3 ,c 2 = 7 2 .Tonamdajenasz

wielomian.

( − 1)( − 2) − ( x − 1)( x − 3)

1( − 1) +3 ( x − 1)( x − 2)

Korzystaj¡czinterpolacjiLagrange’aotrzymujemy:

f ( x )=2 ( x − 2)( x − 3)

Wniosek1 Je±liKjestciałemsko«czonymtoka»dafunkcjaK ! Kmo»e

by¢zapisanajakowielomian.

Kongruencjewpier±cieniachwielomianów

Niech K b¦dziedowolnymciałeminiech K [ x ]oznaczapier±cie«wielo-

mianównad K .Niech f ( x ) 2 K [ x ].Rozwa»mynast¦puj¡c¡relacj¦.Je±li

g ( x ) ,h ( x ) 2 K [ x ]to:

g ( x ) f h ( x ) () f ( x ) | ( g ( x ) − h ( x ))

Relacja f jestrelacj¡równowa»no±ciw K [ x ].Ponadtospełniaonanast¦-

puj¡cewłasno±ci:

g ( x ) f h ( x )

g 1 ( x ) f h 1 ( x )

)

) ( g ( x )+ g 1 ( x )) f ( h ( x )+ h 1 ( x ))

g ( x ) g 1 ( x ) f h ( x ) h 1 ( x )

Relacj¦t¡nazywa¢b¦dziemyrelacj¡przystawaniamodulo f ( x )lubkongru-

encj¡wpier±cieniu K [ x ].Podobniejakdlaanalogicznychrelacjiwpier±cieniu

liczbcałkowitych,relacjaprzystawaniapozwalanamwprowadzi¢działania

wzbiorzeklasabstrakcji:

[ g ( x )]+[ h ( x )]=[ g ( x )+ h ( x )]

[ g ( x )] · [ h ( x )]=[ g ( x ) h ( x )]

Zbiórklasabstrakcjioznacza¢b¦dziemywtymprzypadkuprzez K [ x ] / ( f ( x )).

Twierdzenie1 Struktura ( K [ x ] / ( f ( x )) , + , · ) jestpier±cieniemprzemiennym

zjedynk¡.Zeremjestklasa [0] ,ajedynk¡ [1] .

Jakmo»naopisywa¢klasyabstrakcjitejrelacji?Okazujesi¦,»eistnieje

prostysposóbtakiegoopisu.

Załó»my,»ewielomian f ( x )którydeﬁniujenasz¡relacjemastopie« n .Wtedy

wka»dejklasieabstrakcjiistniejedokładniejedenwielomianstopniamniej-

szegoni» n .Rzeczywi±cieje±liwielomian g ( x )mastopie«wi¦kszyod n to

mo»emypodzieli¢ g ( x )przez f ( x )zreszt¡:

g ( x )= q ( x ) f ( x )+ r ( x ) ,r ( x )=0lubst( r ( x )) < st( f ( x ))

iwtedywielomiany g ( x )i r ( x )s¡zesob¡wrelacji.Awi¦cka»daklasa

abstrakcjijestjednoznaczniewyznaczonaprzezwielomianstopniamniejszego

ni»stopie«wielomianu f ( x ).

Twierdzenie2 StrukturaK [ x ] / ( f ( x )) jestciałemwtedyitylkowtedygdy

f ( x ) jestwielomianemnierozkładalnymnadK.

Przykład Niech K = Z 2 iniech f ( x )= x 3 + x +1.Wtedy f ( x )jestwielo-

mianemnierozkładalnymna Z 2 .Relacja f wyznaczapodziałnanast¦puj¡ce

klasyabstrakcji:

[0] , [1] , [ x ] , [ x +1] , [ x 2 ] , [ x 2 +1] , [ x 2 + x ] , [ x 2 + x +1] .

Poka»emykilkaprzykładówdodawaniaimno»enia:

[ x 2 + x ]+[ x +1]=[ x 2 +1]

[ x 2 + x ] · [ x +1]=[( x 2 + x )( x +1)]=[ x 3 +1]=[( x 3 + x +1)+ x ]=[ x ]

[ x 2 + x +1] 2 =[( x 2 + x +1) 2 ]=[ x 4 + x 2 +1]=[ x ( x +1)+ x 2 +1]=

[ x 2 + x + x 2 +1]=[ x +1]

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: