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 $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 $A,B$ oraz $B$ jest niezerowy, to rezultatem dzielenia $A$ przez $B$ jest iloraz $Q$ i reszta $R.$ Stąd

$A=BQ+R.$

Reszta jest wielomianem stopnia niższego niż wielomian $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 $0$ muszą być wyszczególnione w ciągu jednomianów (pełnią one analogiczną rolę jak cyfry $0$ w ciągu cyfr zapisu pozycyjnego liczb).

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

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

Następnie algorytm wykonuje się w cyklu:

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

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

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

Przykład

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

Dzielna jest na początek przepisana jako:

$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ę $(x^{3}\div x=x^{2}).$

${\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.

${\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.

${\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.

${\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.

${\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 $q(x),$ a liczba, która pozostała, czyli 5, jest resztą $r(x).$

$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;
}