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

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

$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 с 4x³, тогава най-високата степен на 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}}$

Алгоритъм

Следния код на 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) съдържа коефициента на степента xⁱ. Съответно Nenner() е друг масив, който съдържа коефициентите на знаменателя. Резултата е полином, който се записва в Quotient() и Rest(). Променливите GradN и GradZ съдържат съответните степени на полиномите в числителя и знаменателя.

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