Dzielenie wielomianów

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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 (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 oraz jest niezerowy, to rezultatem dzielenia przez jest iloraz i reszta Stąd

Reszta jest wielomianem stopnia niższego niż wielomian w szczególności może być wielomianem zerowym.

Opis algorytmu[edytuj | edytuj kod]

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

Należy podzielić wielomian przez Celem jest znalezienie wielomianów i

Algorytm rozpoczyna się od przyjęcia tzn. jako resztę przyjmuje się dzielną oraz

Następnie algorytm wykonuje się w cyklu:

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

Jeśli ostatnia reszta jest zerowa, to wielomian jest dzielnikiem wielomianu Jeśli ostatnia reszta jest niezerowa, to jest to reszta z dzielenia przez

Iloraz jest sumą jednomianów powstających przy każdym przebiegu cyklu.

Przykład[edytuj | edytuj kod]

Znaleźć iloraz oraz resztę dzielenia przez

Dzielna jest na początek przepisana jako:

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ę

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

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.

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

Powtarzamy 4. Tym razem nie ma nic do sprowadzenia.

Wielomian powyżej kreski jest ilorazem a liczba, która pozostała, czyli 5, jest resztą

Kod[edytuj | edytuj 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;
}