Dzielenie wielomianów

Dzielenie wielomianów, pisemne dzielnie wielomianów – algorytm dzielenia jednego wielomianu przez drugi niezerowy o tym samym lub niższym stopniu. Algorytm ten jest odpowiednikiem algorytmu dzielenia pisemnego liczb naturalnych z tą różnicą, że kolejne potęgi liczby ${\displaystyle 10}$ (dla systemu dziesiętnego) tu są zastąpione kolejnymi potęgami zmiennej; inaczej mówiąc tutaj rolę cyfr pełnią kolejne jednomiany dzielonych wielomianów.

Jeśli mamy wielomiany ${\displaystyle A,B}$ oraz ${\displaystyle B}$ jest niezerowy, to rezultatem dzielenia ${\displaystyle A}$ przez ${\displaystyle B}$ jest iloraz ${\displaystyle Q}$ i reszta ${\displaystyle R.}$ Stąd

${\displaystyle A=BQ+R.}$

Reszta jest wielomianem stopnia niższego niż wielomian ${\displaystyle B,}$ w szczególności może być wielomianem zerowym.

Opis algorytmu

Podczas procesu dzielenia wielomiany są uporządkowane wg malejących potęg zmiennej, jednomiany mające współczynnik ${\displaystyle 0}$ muszą być wyszczególnione w ciągu jednomianów (pełnią one analogiczną rolę jak cyfry ${\displaystyle 0}$ w ciągu cyfr zapisu pozycyjnego liczb).

Należy podzielić wielomian ${\displaystyle A}$ przez ${\displaystyle B.}$ Celem jest znalezienie wielomianów ${\displaystyle Q}$ i ${\displaystyle R.}$

Algorytm rozpoczyna się od przyjęcia ${\displaystyle R_{0}:=A,}$ tzn. jako resztę ${\displaystyle R_{0}}$ przyjmuje się dzielną ${\displaystyle A,}$ oraz ${\displaystyle Q:=0.}$

Następnie algorytm wykonuje się w cyklu:

1. Bieżącą resztę ${\displaystyle R_{i}}$ dzieli się przez dzielną ${\displaystyle B.}$ Dzielenie to polega na podzieleniu „najstarszego” jednomianu reszty ${\displaystyle R_{i}}$ przez „najstarszy” jednomian dzielnej ${\displaystyle B.}$ Wynik tego dzielenia jest kolejnym jednomianem ${\displaystyle q_{i}}$ powstającego ilorazu ${\displaystyle Q,}$ tzn. ${\displaystyle Q:=Q+q_{i}.}$
2. Dzielną ${\displaystyle B}$ mnoży się przez jednomian ${\displaystyle q_{i}}$ i otrzymany iloczyn ${\displaystyle q_{i}\cdot B}$ odejmuje się od bieżącej reszty ${\displaystyle R_{i}.}$ Przyjmujemy ${\displaystyle R_{i+1}=R_{i}-q_{i}\cdot B.}$
3. Algorytm jest zakończony, gdy reszta ${\displaystyle R_{i+1}}$ zerowa bądź ma stopień niższy od stopnia wielomianu ${\displaystyle B,}$ w przeciwnym razie wracamy do punktu 1. przyjmując ${\displaystyle R_{i+1}}$ jako bieżącą resztę.

Jeśli ostatnia reszta jest zerowa, to wielomian ${\displaystyle B}$ jest dzielnikiem wielomianu ${\displaystyle A.}$ Jeśli ostatnia reszta jest niezerowa, to jest to reszta ${\displaystyle R}$ z dzielenia ${\displaystyle A}$ przez ${\displaystyle B.}$

Iloraz ${\displaystyle Q}$ jest sumą jednomianów ${\displaystyle q_{i}}$ powstających przy każdym przebiegu cyklu.

Przykład

Znaleźć iloraz oraz resztę dzielenia ${\displaystyle x^{3}-2x^{2}-4,}$ przez ${\displaystyle x-3.}$

Dzielna jest na początek przepisana jako:

${\displaystyle x^{3}-2x^{2}+0x-4.}$

Iloraz oraz reszta mogą być określone następująco:

Dzielimy pierwszy człon dzielnej przez najwyższy człon dzielnika. Wpisujemy rezultat nad kreskę ${\displaystyle (x^{3}\div x=x^{2}).}$

${\displaystyle {\begin{array}{l}{\color {White}x^{3}-2}x^{2}\\{\overline {x^{3}-2x^{2}+0x-4}}\quad :\quad x-3\end{array}}}$

Mnożymy dzielnik przez właśnie otrzymany rezultat (pierwszy człon ilorazu). Wpisujemy rezultat poniżej pierwszych dwu członów dzielnej.

${\displaystyle {\begin{array}{l}{\color {White}x^{3}-2}x^{2}\\{\overline {x^{3}-2x^{2}+0x-4}}\quad :\quad x-3\\{\color {White}}x^{3}-3x^{2}\end{array}}}$

Odejmujemy otrzymany iloraz od odpowiednich członów oryginalnej dzielnej (należy pamiętać, że odejmowanie czegoś mającego znak minus odpowiada dodaniu czegoś ze znakiem plus), i zapisujemy rezultat pod spodem. Następnie „sprowadzamy” następny człon dzielnej.

${\displaystyle {\begin{array}{l}{\color {White}x^{3}-2}x^{2}\\{\overline {x^{3}-2x^{2}+0x-4}}\quad :\quad x-3\\{\color {White}}{\underline {x^{3}-3x^{2}{\color {White}{}+0x}}}\\{\color {White}x^{3}}+{\color {White}0}x^{2}+0x\end{array}}}$

Powtarzamy poprzednie trzy kroki, tylko tym razem używamy dwóch członów, które zostały zapisane jako dzielna.

${\displaystyle {\begin{array}{l}{\color {White}x^{3}-2}x^{2}+{\color {White}1}x{\color {White}{}+3}\\{\overline {x^{3}-2x^{2}+0x-4}}\quad :\quad x-3\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x}}}\\{\color {White}x^{3}}+{\color {White}2}x^{2}+0x{\color {White}{}-4}\\{\color {White}x^{3}\,}{\underline {+{\color {White}2\;}x^{2}-3x{\color {White}{}-4}}}\\{\color {White}x^{3}-2x^{2}}+3x-4\end{array}}}$

Powtarzamy 4. Tym razem nie ma nic do sprowadzenia.

${\displaystyle {\begin{array}{l}{\color {White}x^{3}-2}x^{2}+{\color {White}1}x+3\\{\overline {x^{3}-2x^{2}+0x-4}}\quad :\quad x-3\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x}}}\\{\color {White}x^{3}}+{\color {White}2}x^{2}+0x{\color {White}{}-4}\\{\color {White}x^{3}\,}{\underline {+{\color {White}2\;}x^{2}-3x{\color {White}{}-4}}}\\{\color {White}x^{3}-2x^{2}}+3x-4\\{\color {White}x^{3}-2x^{2}\,}{\underline {+\,3x-9}}\\{\color {White}x^{3}-2x^{2}+0x}+5\end{array}}}$

Wielomian powyżej kreski jest ilorazem ${\displaystyle q(x),}$ a liczba, która pozostała, czyli 5, jest resztą ${\displaystyle r(x).}$

${\displaystyle x^{3}-2x^{2}-4=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}}$

Kod

void divPoly(double *Q, double *R, const double *A, const double *B, int &degQ, int &degR, const int degA, const int degB)
{
        const double Eps = 1e-14;
        for (int i = 0; i <= degA; i++)
                R[i] = A[i];
        degQ = degA - degB;
        degR = degB - 1;
        for (int j = 0; j <= degQ; j++)
        {
                Q[degQ - j]  = R[degA - j] / B[degB];
                for (int i = degA - j; i >= degQ - j; i--)
                        R[i] -= Q[degQ - j] * B[i - degQ + j];
        }
        for (int i = degR - 1; i>=0; i--)
                if (fabs(R[i])<Eps) R[i] = 0;
}

Linki zewnętrzne

Zobacz publikację Matematyka dla liceum/Wielomiany/Dzielenie wielomianów w Wikibooks

Polskojęzyczne

• Artykuły na Zintegrowanej Platformie Edukacyjnej, zpe.gov.pl [dostęp 2024-05-23]:
  • Michał Niedźwiedź, Dzielenie wielomianów;
  • Adam Jackowski, Działania na wielomianach – powtórzenie wiadomości.
• Dzielenie wielomianów, twierdzenie Bézouta, serwis „Uczę się”, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW), smurf.mimuw.edu.pl, 9 października 2010 [dostęp 2024-05-23].
• Algebra – dzielenie wielomianów, kanał Khan Academy na YouTube [dostęp 2024-05-23].

Anglojęzyczne

• Eric W.E.W. Weisstein Eric W.E.W., Long Division, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-05-22].
• Eric W.E.W. Weisstein Eric W.E.W., Synthetic Division, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-05-22].