Wykład 9
Interpolacja wielomianowa
Niech K będzie pewnym ciałem i niech a1 , a2 , . . . , an , b1 , b2 , . . . , bn będą
pewnymi elementami ciała K (ai = aj dla i = j). Zadanie jest następujące.
Chcemy znaleźć wielomian f (x) ∈ K[x], taki że
f (a1 ) = b1 , f (a2 ) = b2 , . . . , f (an ) = bn
Podamy teraz dwa sposoby konstrukcji takich wielomianów.
I. Interpolacja Lagrange’a.
Budujemy wyrażenia:
fi (x) =
(x − a1 )(x − a2 ) . . . (x − ai−1 )(x − ai+1 ) . . . (x − an )
(ai − a1 )(ai − a2 ) . . . (ai − ai−1 )(ai − ai+1 ) . . . (ai − an )
Można zauważyć, że fi (ai ) = 1 i dla i = j, fi (aj ) = 0. Wtedy naszym
poszukiwanym wielomianem będzie:
f (x) = b1 f1 (x) + b2 f2 (x) + . . . + bn fn (x)
Przykład Wyznaczyć wielomian f (x) ∈ R[x], taki że
f (1) = 2, f (2) = −1, f (3) = 3
Korzystając z interpolacji Lagrange’a otrzymujemy:
f (x) = 2 (x−2)(x−3) − (x−1)(x−3) + 3 (x−1)(x−2) =
(−1)(−2)
1(−1)
2·1
(x − 2)(x − 3) + (x − 1)(x − 3) + 3 (x − 1)(x − 2)
2
II. Interpolacja Newtona.
Wielomian w tym przypadku budujemy następująco:
f (x) = c0 + c1 (x − a1 ) + c2 (x − a1 )(x − a2 ) + . . . + cn−1 (x − a1 ) . . . (x − an−1 )
Wstawianie kolejno za x wartości a1 , . . . , an i przyrównanie ich do b1 , . . . , bn
pozwoli nam jednoznacznie wyznaczyć wartości c0 , . . . , cn−1 .
Przykład Wyznaczymy tą metodą wielomian f (x), który spełnia te same
własności co wielomian z poprzedniego przykładu. Nasz wielomian ma teraz
postać:
f (x) = c0 + c1 (x − 1) + c2 (x − 1)(x − 2)
Wstawiamy kolejno za x: 1, 2, 3 i otrzymujemy:
f (1) = c0 = 2
f (2) = c0 + c1 = −1
f (3) = c0 + 2c1 + 2c2 = 3
7
Rozwiązaniem tego układu jest c0 = 2, c1 = −3, c2 = 2 . To nam daje nasz
wielomian.
1
Wniosek 1 Jeśli K jest ciałem skończonym to każda funkcja K → K może
być zapisana jako wielomian.
Kongruencje w pierścieniach wielomianów
Niech K będzie dowolnym ciałem i niech K[x] oznacza pierścień wielomianów nad K. Niech f (x) ∈ K[x]. Rozważmy następującą relację. Jeśli
g(x), h(x) ∈ K[x] to:
g(x) ∼f h(x) ⇐⇒ f (x)|(g(x) − h(x))
Relacja ∼f jest relacją równoważności w K[x]. Ponadto spełnia ona następujące własności:
g(x) ∼f h(x)
g1 (x) ∼f h1 (x)
⇒
(g(x) + g1 (x)) ∼f (h(x) + h1 (x))
g(x)g1 (x) ∼f h(x)h1 (x)
Relację tą nazywać będziemy relacją przystawania modulo f (x) lub kongruencją w pierścieniu K[x]. Podobnie jak dla analogicznych relacji w pierścieniu
liczb całkowitych, relacja przystawania pozwala nam wprowadzić działania
w zbiorze klas abstrakcji:
[g(x)] + [h(x)] = [g(x) + h(x)]
[g(x)] · [h(x)] = [g(x)h(x)]
Zbiór klas abstrakcji oznaczać będziemy w tym przypadku przez K[x]/(f (x)).
Twierdzenie 1 Struktura (K[x]/(f (x)), +, ·) jest pierścieniem przemiennym
z jedynką. Zerem jest klasa [0], a jedynką [1].
Jak można opisywać klasy abstrakcji tej relacji? Okazuje się, że istnieje
prosty sposób takiego opisu.
Załóżmy, że wielomian f (x) który definiuje naszą relacje ma stopień n. Wtedy
w każdej klasie abstrakcji istnieje dokładnie jeden wielomian stopnia mniejszego niż n. Rzeczywiście jeśli wielomian g(x)
(…)
… przez wielomian stopnia mniejszego
niż stopień wielomianu f (x).
Twierdzenie 2 Struktura K[x]/(f (x)) jest ciałem wtedy i tylko wtedy gdy
f (x) jest wielomianem nierozkładalnym nad K.
2
Przykład Niech K = Z2 i niech f (x) = x3 + x + 1. Wtedy f (x) jest wielomianem nierozkładalnym na Z2 . Relacja ∼f wyznacza podział na następujące
klasy abstrakcji:
[0], [1], [x], [x + 1], [x2 ], [x2 + 1], [x2 + x], [x2 + x + 1…
... zobacz całą notatkę
Komentarze użytkowników (0)