Syntetisk division

Inom algebra är syntetisk division en metod för att manuellt utföra euklidisk division av polynom, med mindre skrivning och färre beräkningar än långdivision .

Det lärs mestadels ut för division med linjära moniska polynom (känd som Ruffinis regel ), men metoden kan generaliseras till division med vilket polynom som helst .

Fördelarna med syntetisk division är att den låter en räkna utan att skriva variabler, den använder få beräkningar och den tar betydligt mindre plats på papper än lång division. Dessutom omvandlas subtraktionerna i långdivision till additioner genom att byta tecken i början, vilket hjälper till att förhindra teckenfel.

Regelbunden syntetdelning

Det första exemplet är syntetisk division med endast en monisk linjär nämnare $xa$ .

${\frac {x^{3}-12x^{2}-42}{x-3}}$

Täljaren kan skrivas som $x)=x^{3}-12x^{2}+0x-42}$ ( .

Nollan för nämnaren $g(x)$ är $3$ .

Koefficienterna för $p(x)$ är ordnade enligt följande, med nollpunkten för $g(x)$ till vänster:

${\begin{array}{cc}{\begin{array}{r}\\3\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\\hline \end{array}}\end{array}}$

Den första koefficienten efter stapeln "släpps" till sista raden.

${\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{| rrrr}\color {blue}1&-12&0&-42\\&&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}$

Det tappade talet multipliceras med talet före stapeln och placeras i nästa kolumn .

${\begin{array}{cc}{\begin{array}{r}\\\color {grå}3\\\\\end{array}}&{\ start{array}{|rrrr}1&-12&0&-42\\&\color {brown}3&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}$

En tillägg görs i nästa kolumn.

${\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array }{|rrrr}1&\color {green}-12&0&-42\\&\color {green}3&&\\\hline 1&\color {green}-9&&\\\end{array}}\end{array}}$

De två föregående stegen upprepas och följande erhålls:

${\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array }}&{\begin{array}{|rrrr}1&-12&0&-42\\&3&-27&-81\\\hline 1&-9&-27&-123\end{array}}\end{array}}$

Här är den sista termen (-123) resten medan resten motsvarar kvotens koefficienter.

Termerna skrivs med ökande grad från höger till vänster med början på grad noll för resten och resultatet.

${\begin{array}{rrr|r}1x^{2}&-9x&-27&-123\end{array}}$

Därför är kvoten och resten:

$q(x)=x^{2}-9x-27$

$r(x)=-123$

Utvärdera polynom genom restsatsen

Ovanstående form av syntetisk division är användbar i sammanhanget med polynomrestsatsen för att utvärdera univariata polynom. För att sammanfatta, värdet av $p(x)$ vid $a$ är lika med resten av divisionen av $p(x)$ med $xa.$

Fördelen med att beräkna värdet på detta sätt är att det krävs drygt hälften så många multiplikationssteg som naiv utvärdering. En alternativ utvärderingsstrategi är Horners metod .

Utökad syntetisk division

Denna metod generaliserar till division med vilket moniskt polynom som helst med endast en liten modifiering med ändringar i fetstil . Använd samma steg som tidigare och utför följande uppdelning:

${\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}$

Vi sysslar endast med koefficienterna. Skriv koefficienterna för polynomet som ska delas överst.

${\begin{array}{|rrrr}\ 1&-12&0&-42\end{array}}$

Negera koefficienterna för divisorn.

${\begin{array}{rrr}-1x^{2}&-1x&+3\end{array}}$

Skriv in varje koefficient men den första till vänster i en uppåtriktad höger diagonal (se nästa diagram).

${\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\end{array}}&{\begin{array }{|rrrr}\ 1&-12&0&-42\\&&&\\&&&\\\hline \end{array}}\end{array}}$

Notera ändringen av tecken från 1 till −1 och från −3 till 3 . "Släpp" den första koefficienten efter stapeln till den sista raden.

${\begin{array}{cc}{\begin{array}{rr}\\&3\\\-1&\\\\\end{array}}&{\ start{array}{|rrrr}1&-12&0&-42\\&&&\\&&&\\\hline 1&&&\\\end{array}}\end{array}}$

Multiplicera det tappade talet med diagonalen före stapeln och placera de resulterande posterna diagonalt till höger från den tappade posten.

${\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}} &{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&&&\\\end{array}}\end{array}}$

Gör ett tillägg i nästa kolumn.

${\begin{array}{cc}{\begin{array}{rr}\\&3\\\-1&\\\\\end{array }}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&-13&&\\\end{array}}\end{array}}$

Upprepa de två föregående stegen tills du skulle gå förbi posterna överst med nästa diagonal .

${\begin{array}{cc}{\begin{array}{rr}\\&3\\\-1&\\\\ \end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&\\\end{array}}\end{ array}}$

Lägg sedan helt enkelt ihop eventuella återstående kolumner.

${\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\ \\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&-81\\\end{array} }\end{array}}$

Räkna termerna till vänster om stapeln. Eftersom det finns två har resten grad ett och detta är de två termerna längst till höger under stapeln. Markera separationen med en vertikal stapel.

${\begin{array}{rr|rr}1&-13&16&-81\end{array}}$

Termerna skrivs med ökande grad från höger till vänster med början på grad noll för både resten och resultatet.

${\begin{array}{rr|rr}1x&-13&16x&-81\end{array}}$

Resultatet av vår division är:

${\frac {x^{3}-12x^{2}-42} {x^{2}+x-3}}=x-13+{\frac {16x-81}{x^{2}+x-3}}$

För icke-moniska divisorer

Med lite påtryckningar kan den utökade tekniken generaliseras ytterligare för att fungera för vilket polynom som helst, inte bara för moniker . Det vanliga sättet att göra detta skulle vara att dividera divisorn $g(x)$ med dess ledande koefficient (kalla det a ):

$h(x)={\frac {g(x)}{a}}$

använd sedan syntetisk division med $h(x)$ som divisor, och dividera sedan kvoten med a för att få kvoten av den ursprungliga divisionen (resten förblir densamma). Men detta producerar ofta fula fraktioner som tas bort senare och är därför mer benägna att fel. Det är möjligt att göra det utan att först reducera koefficienterna för $g(x)$ .

$) {\displaystyle g(x) }$ , divideras koefficienterna för ${\displaystyle f(x)} med den ledande koefficienten för$ efter "släpp" och innan multiplicering.

Låt oss illustrera genom att utföra följande uppdelning:

${\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}$

En något modifierad tabell används:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}} {\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline &&&\\&&&\\\end{array}}\end{array}}$

Notera den extra raden längst ner. Detta används för att skriva värden som hittats genom att dividera de "bortfallna" värdena med den inledande koefficienten för $g(x)$ (i det här fallet indikeras av /3 ; observera att, till skillnad från resten av koefficienter för ${\displaystyle g(x)} ,$ tecknet för detta tal ändras inte).

tas den första koefficienten av ${\displaystyle f(x)} bort som vanligt:$

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array} }{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\&&&\\\end{array}}\end{array}}$

och sedan divideras det tappade värdet med 3 och placeras i raden nedan:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array }}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}$

Därefter används det nya (delade) värdet för att fylla de översta raderna med multiplar av 2 och 1, som i den utökade tekniken:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end {array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}$

5:an tas bort härnäst, med obligatoriskt tillägg av 4:an under, och svaret delas igen:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\ \end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}$

Sedan används 3:an för att fylla de översta raderna:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&/3 \\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}$

Vid denna tidpunkt, om vi, efter att ha fått den tredje summan, skulle försöka använda den för att fylla de översta raderna, skulle vi "falla av" den högra sidan, så den tredje summan är den första koefficienten av resten, som i vanlig syntetisk uppdelning. Men värdena på resten inte med den ledande koefficienten för divisorn:

${\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\ &&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&8&-4\\2&3&&\\\end{array}}\end {array}}$

Nu kan vi läsa av koefficienterna för svaret. Som i utökad syntetisk division är de två sista värdena (2 är graden av divisor) koefficienterna för resten, och de återstående värdena är koefficienterna för kvoten:

${\begin{array}{rr|rr}2x&+3&8x&-4\end{array}}$

och resultatet är

${\frac {6x^{3}+5x^ {2}-7}{3x^{2}-2x-1}}=2x+3+{\frac {8x-4}{3x^{2}-2x-1}}$

Compact Expanded Synthetic Division

Diagonalformatet ovan blir dock mindre utrymmeseffektivt när divisorgraden överstiger hälften av utdelningsgraden. Tänk på följande uppdelning:

${\dfrac {a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^{4 }+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}{b_{4}x^{4}-b_{3}x^ {3}-b_{2}x^{2}-b_{1}x-b_{0}}}$

Det är lätt att se att vi har fullständig frihet att skriva varje produkt i vilken rad som helst så länge den är i rätt kolumn, så algoritmen kan kompakteras med en girig strategi , som illustreras i indelningen nedan:

${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0} \\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_ {1}b_{2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1} &q_{0}b_{1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0 }&q_{1}b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0 }\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&r_{2}&r_{1}&r_{0}\\q_{3}&q_{2} &q_{1}&q_{0}&&&&\\\end{array}}\end{array}}$

Följande beskriver hur man utför algoritmen; den här algoritmen innehåller steg för att dividera icke-moniska divisorer:

1. Skriv utdelningskoefficienterna på en stapel.

   $\displaystyle {\begin{array}{cc}{\begin{array}{|rrrrrrrr}\ a_{7}&a_{6}&a_{5} &a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline \end{array}}\end{array}}}$

2. Ignorera den första (ledande) koefficienten för divisorn, negera varje koefficient och placera dem på den vänstra sidan av stapeln.

   ${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_{2 }&b_{1}&b_{0}\\\end{array}}&{\begin{array}{|rrrrrrrr}\ a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_ {2}&a_{1}&a_{0}\\\hline \end{array}}\end{array}}$

3. Från antalet koefficienter placerade på den vänstra sidan av stapeln, räkna antalet utdelningskoefficienter ovanför stapeln, med början från kolumnen längst till höger. Placera sedan en vertikal stapel till vänster, samt raden nedanför, om den kolumnen. Denna vertikala stapel markerar separationen mellan kvoten och resten.

   ${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_{2 }&b_{1}&b_{0}\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a_{7}&a_{6}&a_{5}&a_{4}&a_{ 3}&a_{2}&a_{1}&a_{0}\\\hline &&&&&&&\\\end{array}}\end{array}}$

4. Släpp den första koefficienten av utdelningen under ribban.

   ${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_ {2}&b_{1}&b_{0}\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a_{7}&a_{6}&a_{5}&a_{4} &a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&&&&&&&\\\end{array}}\end{array}}$

5. • 
     Dividera det tidigare tappade/summerade talet med divisorns ledande koefficient och placera den på raden nedanför (detta behöver inte göras om den ledande koefficienten är 1). I detta fall ${\displaystyle q_{3}={\dfrac {a_{7}}{b_{4}}}} ,$ där indexet $3=7 -4$ har valts genom att subtrahera divisorns index från utdelningen.
     
   • Multiplicera det tidigare tappade/summerade talet (eller det dividerade tappade/summerade talet) till varje negerad divisorkoefficient till vänster (börjar med den längst till vänster); hoppa över om det tappade/summerade talet är noll. Placera varje produkt ovanpå de efterföljande kolumnerna.

     ${\begin {array}{cc}{\begin{array}{rrrr}\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&&/b_{4}\\\end{array} }{\begin{array}{|rrrr|rrrr}&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&&&\\\a_{ 7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&&&&&&&\\q_{3}&&&&&&&\\\end {array}}\end{array}}$

6. Utför ett kolumnvis tillägg på nästa kolumn. I det här fallet är $q_{2}'=q_{3}b_{3}+a_{6}$ .

   ${\begin{array}{cc}{\begin{array}{rrrr}\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&&/b_{4}\\\end {array}}{\begin{array}{|rrrr|rrrr}&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&&&\ \a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&&&&&&\\q_ {3}&&&&&&&\\\end{array}}\end{array}}$

7. Upprepa de två föregående stegen. Stopp när du utförde de två föregående stegen på numret precis före den vertikala stapeln.
   1. Låt $q_{2}={\dfrac {q_{2}'}{b_{4}}}$ .

      ${\begin{array}{cc}{\begin{array}{rrrr}\\\\b_{3}&b_{2} &b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&q_{2}b_{3}&q_{2} b_{2}&q_{2}b_{1}&&&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2 }b_{0}&&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{ 2}'&q_{1}'&&&&&\\q_{3}&q_{2}&&&&&&\\\end{array}}\end{array}}$

   2. Låt $q_{1}={\dfrac {q_{1}'}{b_{4}}}$ .

      ${\begin{array}{cc}{\ börja{array}{rrrr}\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&&/b_{4}\\\end{array}}{\begin {array}{|rrrr|rrrr}&&&q_{1}b_{3}&q_{1}b_{2}&&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{ 1}&q_{1}b_{1}&&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_ {0}&q_{1}b_{0}&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&&&&\\q_{3}&q_{2}&q_{1}&&&&&\\\end{array}}\end{array}}$

   3. Låt $q_{0}={\dfrac {q_{0}'}{b_{4}}}$ .

      ${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&& /b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_{1}b_{ 2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1}&q_{0}b_ {1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&q_{1} b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&&&\\q_{3}&q_{2}&q_{1}&q_{0}&&&&\\\end{array} }\end{array}}$

8. Utför de återstående kolumnvisa tilläggen på de efterföljande kolumnerna (beräkna resten).

   ${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0} \\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_ {1}b_{2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1} &q_{0}b_{1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0 }&q_{1}b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0 }\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&r_{2}&r_{1}&r_{0}\\q_{3}&q_{2} &q_{1}&q_{0}&&&&\\\end{array}}\end{array}}$

9. De nedersta resultaten under den horisontella stapeln är koefficienterna för polynomen (kvoten och resten), där koefficienterna för kvoten är till vänster om den vertikala stapelseparationen och koefficienterna för resten är till höger. Dessa koefficienter tolkas som att de har ökande grad från höger till vänster, med början på grad noll för både kvoten och resten.
   

   Vi tolkar resultaten för att få:

   ${\dfrac {a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^ {4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}{b_{4}x^{4}-b_{3} x^{3}-b_{2}x^{2}-b_{1}x-b_{0}}}=q_{3}x^{3}+q_{2}x^{2}+q_ {1}x+q_{0}+{\dfrac {r_{3}x^{3}+r_{2}x^{2}+r_{1}x+r_{0}}{b_{4} x^{4}-b_{3}x^{3}-b_{2}x^{2}-b_{1}x-b_{0}}}$

Python implementering

Följande kodavsnitt implementerar Expanded Synthetic Division i Python för godtyckliga univariata polynom:

  
    





        
      0
           
        
        
          

          
           0  
            
            
                
                      

    
    
    
    
    
        
         def  expanded_synthetic_division  (  dividend  ,  divisor  ):  """Snabb polynomdivision med hjälp av expanderad syntetisk division.  Fungerar även med icke-moniska polynom.  Dividend och divisor är båda polynom, som här helt enkelt är listor med koefficienter.  T.ex.: x**2 + 3*x + 5 kommer att representeras som [1, 3, 5]  "  ""  ut  =  lista  (  utdelning  )  # Kopiera utdelningsnormaliseraren  =  divisor  [  ]  för  i  inom  intervallet  (  len  (  dividend  )  -  len  (  divisor  )  +  1  ):  # För allmän polynomdivision (när polynom är icke-moniska),  # måste vi normalisera genom att dividera koefficienten med divisorns första koefficient  ut  [  i  ]  /=  normaliserare  coef  =  ut  [  i  ]  if  coef  !=  :  # Useless för att multiplicera om koefficienten är 0  # I syntetisk division hoppar vi alltid över den första koefficienten för divisorn,  # eftersom den bara används för att normalisera utdelningskoefficienterna  för  j  i  intervallet  (  1  ,  len  (  divisor  )):  ut  [  i  +  j  ]  +=  -  divisor  [  j  ]  *  coef  # Det resulterande resultatet innehåller både kvoten och resten,  # resten är storleken på divisorn (resten  # har nödvändigtvis samma grad som divisorn eftersom det är  # vad vi kunde inte dividera från utdelningen), så vi beräknar index  # där denna separation är, och returnerar kvoten och resten.  separator  =  1  -  len  (  divisor  )  return  out  [:  separator  ],  out  [  separator  :]  # Return quotient, rest. 

Se även

• Euklidisk domän
• Största gemensamma delaren av två polynom
• Gröbner grund
• Horner-schema
• Polynomrestsats
• Ruffinis regel

• Lianghuo Fan (2003). "En generalisering av syntetisk division och en allmän sats för division av polynom" ( PDF) . Matematiskt medley . 30 (1): 30–37.
• Li Zhou (2009). "Kort division av polynom". College Mathematics Journal . 40 (1): 44–46. doi : 10.4169/193113409x469721 .

externa länkar

• Goodman, Len ; Stover, Christopher & Weisstein, Eric W. "Synthetic Division" . MathWorld .
• Stover, Christopher. "Ruffinis regel" . MathWorld .