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 znalez
ć 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:
(x - a1)(x - a2) . . . (x - ai-1)(x - ai+1) . . . (x - an)
fi(x) =
(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) = b1f1(x) + b2f2(x) + . . . + bnfn(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:
(x-1)(x-3)
f(x) = 2(x-2)(x-3) - + 3(x-1)(x-2) =
(-1)(-2) 1(-1) 2·1
3
(x - 2)(x - 3) + (x - 1)(x - 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 = . To nam daje nasz
2
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ń wielo-
mianó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) (g(x) + g1(x)) <"f (h(x) + h1(x))
Ò!
g1(x) <"f h1(x) g(x)g1(x) <"f h(x)h1(x)
Relację tą nazywać będziemy relacją przystawania modulo f(x) lub kongru-
encją 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 mniej-
szego niż n. Rzeczywiście jeśli wielomian g(x) ma stopień większy od n to
możemy podzielić g(x) przez f(x) z resztą:
g(x) = q(x)f(x) + r(x), r(x) = 0 lub st(r(x)) < st(f(x))
i wtedy wielomiany g(x) i r(x) są ze sobą w relacji. A więc każda klasa
abstrakcji jest jednoznacznie wyznaczona 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 wielo-
mianem 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].
Pokażemy kilka przykładów dodawania i mnożenia:
[x2 + x] + [x + 1] = [x2 + 1]
[x2 + x] · [x + 1] = [(x2 + x)(x + 1)] = [x3 + 1] = [(x3 + x + 1) + x] = [x]
[x2 + x + 1]2 = [(x2 + x + 1)2] = [x4 + x2 + 1] = [x(x + 1) + x2 + 1] =
[x2 + x + x2 + 1] = [x + 1]
3