Деление на полиноми

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Делението на полиноми е математически алгоритъм за решаване на уравнение от вида:


p(x) = s(x) q(x) + r(x)
\!

за дадени полиноми p и q, т.е. търсят се s и r. To e аналогично на делението с остатък при целите числа.


Приложение[редактиране | edit source]

Делението на полиноми се използва и за:

  • намаляване на степента и съответно приблизително изчисляване на уравнения от висока степен
  • изчисляване асимптоти на рационални функции
  • изчисляване на контролна сума при кодиране на информация
  • интегриране на рационални функции

Изчисление[редактиране | edit source]

На ръка[редактиране | edit source]

Процедира се точно както при писменото деление на цели числа и се изчислява по същата схема. Ето и етапите един по един:

  • Нека решим следната задача
 \frac{p(x)}{q(x)} = \frac{4 \cdot x^5 - x^4 + 2 \cdot x^3 + x^2 - 1} {x^2 + 1}
  • Първо трябва да се погрижим за елиминирането на най-голямата степен на полинома. За тази цел трябва да умножим q с 4x3, тогава най-високата степен на q е x^2 и е в сила 4x^5 = x^2 \cdot 4x^3 .
 \begin{matrix} ( 4x^5 & -x^4 & +2x^3 & + x^2 & -1 ) & : & ( x^2 & +1 ) & = & 4x^3 \dots \\
\underline{-4x^5} &    & \underline{-4x^3} &       &    &   &     &    &   & \\
& -x^4 & -2x^3 &       &    &   &     &    &   & \end{matrix}
  • Продължава се по същия начин с елиминирането на съответната най-висока степен, докато получим остатък, който не може да бъде елиминиран, понеже степента му става по-малка от тази на q.
\begin{matrix} (4x^5 & -x^4 & +2x^3 & + x^2 & -1) & : & (x^2 &  +1) & = & 4x^3 - x^2 -2x +2 + \frac{2x - 3}{x^2 + 1}\\
\underline{-4x^5} &        & \underline{-4x^3} &       &    &   &   &      &   & \\
& -x^4 & -2x^3 &       &    &   &     &    &   & \\
& \underline{+x^4} &       & \underline{+x^2}  &    &   &     &    &   & \\
&      & -2x^3 & +2x^2 &    &   &     &    &   & \\
&      & \underline{+2x^3} &       & \underline{+2x} &  &     &   &   & \\
&      &       & 2x^2  & +2x & -1 &     &    &   & \\
&      &       & \underline{-2x^2} &     & \underline{- 2}    &  &     & \\
&      &       &       & 2x  & - 3    & &   &   &
\end{matrix}

Алгоритъм[редактиране | edit source]

Следния код на BASIC показва същността на изчислението:

   For i = GradZ - GradN To 0 Step -1
       Quotient(i) = Zähler(i + GradN) / Nenner(GradN)
       For j = GradN To 0 Step -1
           Zähler(i + j) = Zähler(i + j) - Nenner(j) * Quotient(i)
       Next j
   Next i
   For j = GradN - 1 To 0 Step -1
       Rest(j) = Zähler(j)
   Next j

Променливата Zähler() е масив, който съдържа коефициентите на полинома в числителя, тоест Zähler(i) съдържа коефициента на степента xi. Съответно Nenner() е друг масив, който съдържа коефициентите на знаменателя. Резултата е полином, който се записва в Quotient() и Rest(). Променливите GradN и GradZ съдържат съответните степени на полиномите в числителя и знаменателя.

Алгоритъмът може да се оптимизира, като вътрешният цикъл се върти от 0 до (GradN-1) и резултатът се записва обратно в Zähler() и така променливите Quotient() и Rest() могат да отпаднат.