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

от Уикипедия, свободната енциклопедия

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

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

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


Съдържание

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

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

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


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

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

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

  • Нека решим следната задача
\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 е x2 и е в сила 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}

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

Следния код на 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() могат да отпаднат.

На други езици