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÷x=x^2).$

$\begin{array}{c}{x}^3-2x^2\\ \overline{x^3-2x^2+0x-4}: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}{c}{x}^3-2x^2\\ \overline{x^3-2x^2+0x-4}:x-3\\ 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}{c}{x}^3-2x^2\\ \overline{x^3-2x^2+0x-4}:x-3\\ \underset{\_}{x^3-3x^2+0x}\\ x^3+0x^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}{c}{x}^3-2x^2+1x+3\\ \overline{x^3-2x^2+0x-4}:x-3\\ \underset{\_}{x^3-3x^2+0x}\\ x^3+2x^2+0x-4\\ x^3\underset{\_}{+2x^2-3x-4}\\ x^3-2x^2+3x-4\end{array}$

Powtarzamy 4. Tym razem nie ma nic do sprowadzenia.

$\begin{array}{c}{x}^3-2x^2+1x+3\\ \overline{x^3-2x^2+0x-4}:x-3\\ \underset{\_}{x^3-3x^2+0x}\\ x^3+2x^2+0x-4\\ x^3\underset{\_}{+2x^2-3x-4}\\ x^3-2x^2+3x-4\\ x^3-2x^2\underset{\_}{+3x-9}\\ 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)\underset{q(x)}{\underbrace{(x^2+x+3)}}+\underset{r(x)}{\underbrace{5}}$

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

Polskojęzyczne

• Szablon:Otwarty dostęp 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.
• Szablon:Otwarty dostęp 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].
• Szablon:Otwarty dostęp Algebra – dzielenie wielomianów, kanał Khan Academy na YouTube [dostęp 2024-05-23].

Anglojęzyczne

• Szablon:MathWorld [dostęp 2024-05-22].
• Szablon:MathWorld [dostęp 2024-05-22].