Cum aflu câtul împărțirii la X − a cu Horner?

Lecția pe scurt · clasa a XII-a · Împărțirea și Horner

Teorema. Pentru orice $f$ și orice $g$ nenul din $K[X]$ se găsesc, într-un singur fel, un cât $q$ și un rest $r$ legate prin $f=gq+r$, restul fiind nul ori de grad strict sub cel al împărțitorului. Marginea aceasta dă sens întrebării „care este restul?”: fără ea, aceeași egalitate ar admite o grămadă de scrieri.

Unde se sprijină algoritmul pe corp. Într-un singur loc: la fiecare rundă trebuie să afli cu ce se înmulțește împărțitorul ca să dispară termenul dominant, adică să folosești inversul coeficientului dominant al împărțitorului. Într-un corp el există mereu, deci în ${\mathbb{Z}}_p$ împărțirea se face înmulțind cu inversul; în ${\mathbb{Z}}_3$ fiecare clasă nenulă este propria ei inversă.

Schema lui Horner merge neschimbată în orice $K[X]$, fiindcă folosește numai adunări și înmulțiri. Rândul de sus are exact $\mathrm{grad}f+1$ celule, cu zerourile scrise; prima celulă de jos copiază coeficientul dominant, apoi orice celulă nouă iese adăugând, peste numărul de deasupra, produsul lui $a$ cu vecina ei din stânga. La capăt stă restul, adică valoarea $f(a)$.

Două greșeli scumpe. Pe $a$ îl iei din scrierea $X-a$, după ce ai socotit opusul chiar în corpul de lucru; iar proba prin înmulțire înapoi nu se sare niciodată.

De reținut

• Horner: fiecare număr nou = $a\cdot$(numărul anterior) + coeficientul următor
• ultimul număr este restul, adică $f(a)$
• coeficienții puterilor lipsă se scriu cu $0$

Greșeala tipică

La Horner se sare peste coeficientul unei puteri lipsă; la $X^4-2X^3+X-7$ rândul coeficienților este $1$, $-2$, $0$, $1$, $-7$, cu zero pentru $X^2$.

Exerciții din această mini-lecție

1. În $\mathbb{Q}[X]$, restul împărțirii polinomului $f=X^3-4X^2+6X-5$ la $X-3$ este:

   • a) $0$
   • b) $4$
   • c) $-4$
   • d) $13$
   Vezi răspunsul

   Răspuns corect: b) $4$

   Împărțitorul are gradul întâi, deci restul e o constantă, iar teorema restului spune că ea este $f(3)$. Calculăm: $27-36+18-5=4$. Control cu schema lui Horner, pe coeficienții $1$, $-4$, $6$, $-5$ și $a=3$: se coboară $1$; $-4+3=-1$; $6-3=3$; $-5+9=4$ — ultima celulă confirmă.

2. În $\mathbb{Q}[X]$, câtul împărțirii polinomului $f=2X^3+5X^2-4X+6$ la $X+3$ este:

   • a) $2X^2-X-1$
   • b) $2X^2+11X+29$
   • c) $2X^2-X+5$
   • d) $2X^2-6X+14$
   Vezi răspunsul

   Răspuns corect: a) $2X^2-X-1$

   Rescriem împărțitorul ca $X-(-3)$, deci $a=-3$. Rândul lui Horner, pe coeficienții $2$, $5$, $-4$, $6$: se coboară $2$; $5+(-3)\cdot 2=-1$; $-4+(-3)\cdot (-1)=-1$; $6+(-3)\cdot (-1)=9$. Câtul este $2X^2-X-1$, iar restul $9$. Varianta b) ar ieși intrând în schemă cu $a=3$, adică citind greșit semnul.

3. În ${\mathbb{Z}}_3[X]$, restul împărțirii polinomului $f=X^4+\hat{2}{X}^2+\hat{2}$ la $X+\hat{2}$ este:

   • a) $\hat{0}$
   • b) $\hat{1}$
   • c) $\hat{2}$
   • d) $\hat{2}X$
   Vezi răspunsul

   Răspuns corect: c) $\hat{2}$

   Rescriem împărțitorul: $-\hat{2}=\hat{1}$ în ${\mathbb{Z}}_3$, deci $X+\hat{2}=X-\hat{1}$ și evaluarea se face în $\hat{1}$. Avem $f(\hat{1})=\hat{1}+\hat{2}+\hat{2}=\hat{5}=\hat{2}$. Varianta a) ar însemna că împărțirea e exactă, ceea ce ar cere $f(\hat{1})=\hat{0}$; varianta b) iese dacă se evaluează greșit în $\hat{2}$; varianta d) e imposibilă, fiindcă la un împărțitor de gradul întâi restul e o constantă.

Întrebări conexe

Oamenii mai întreabă și: schema lui Horner cât și rest · împărțirea la X minus a cu Horner · cum aplic schema lui Horner · câtul împărțirii cu schema lui Horner