Varför fungerar polynomdivision?

Söker du en förklaring av varför själva metoden fungerar eller en förklaring till varför det ibland går jämnt ut, dvs varför det ibland gäller att $\frac{S(x)}{P(x)}=Q(x)$, där S, P och Q är polynom?

Menar du metoden med liggande stolen?

Jag har inget formellt bevis, men varje steg utgör en omskrivning av täljaren och i varje steg sjunker gradtalet för mellanresultaten, så det tar garanterat slut.

Man borde kunna hitta likheter med samma sak för heltal.

Yngve skrev:

Söker du en förklaring av varför själva metoden fungerar eller en förklaring till varför det ibland går jämnt ut, dvs varför det ibland gäller att $\frac{S(x)}{P(x)}=Q(x)$, där S, P och Q är polynom?

Varför själva metoden fungerar.

Ett sätt att se på divisionsalgoritmer, för polynom och för vanliga tal, är att de delar upp en helhet i mindre bitar, som är lättare att beräkna.

Tänk på kort division av 960/8. Först tittar vi på hur många gånger 8 går i 9, vilket egentligen är hur många gånger åtta går i 900,. Vi ser att det fungerar en gång. Då har vi kvar 100+60. Då tittar vi på hur många gånger åtta går först i ett (vilket egentligen är 10, eftersom det är tiotal), vilket inte går, och då vänder vi oss till 16 (totalt 160) istället. Åtta går två gånger i 16. Vi har därmed två kvoter - 100 och 20. Summan av dem är 120. 

Polynomdivision fungerar på samma sätt - genom att bryta ut en så stor bit (polynom) som är jämnt delbar med nämnaren som möjligt, kommer vi sakta men säkert att ha delat upp polynomet i mindre bitar, som kan beräknas för sig och summeras ihop. 

Jag tänker mig heltal som polynom (med icke-negativa heltalskoefficienter).
Bara det att vi inte skriver ut  10-potenserna.  
980  eller  9·10² + 8·10¹ + 0   eller  9x² + 8x + 0
Därför funkar den vanliga divisionsalgoritmen även för polynom.
Och det även när vissa koefficienter är negativa!

Det slår mig att jag aldrig sett något bevis för att den vanliga divisionsalgoritmen funkar, men den har ju visat sig funka i bra många sekler … 

Detta är själva principen: Om S=P₁+P₂+…P_n så är S/Q = P₁/Q + P₂/Q+….+P_n/Q. Det är alltså distributiva lagen och den gäller såväl tal som polynom.

Trappan eller liggande stolen eller vad för uppställning man än har, så handlar det om att dela upp en ”komplicerad” division i flera enklare.

Tack så mycket för era svar!

Detta är själva principen: Om S=P₁+P₂+…P_n så är S/Q = P₁/Q + P₂/Q+….+P_n/Q. Det är alltså distributiva lagen och den gäller såväl tal som polynom.

Skulle du kunna illustrera detta med polynomdivision? Jag förstår inte hur det du visade hänger ihop med polynomdivision.

Jag kan försöka visa hur jag inte förstår hur det hänger ihop:

Säg att vi har kvoten $\frac{x^3-2x^2+x-1}{x-1}$, den skulle man kunna skriva som $\frac{x^3}{x-1}-\frac{2x^2}{x-1}+\frac{x}{x-1}-\frac{1}{x-1}$

Om man nu skulle utföra polynomdivision skulle man först titta hur många gånger $x$ går i $x^3$. I detta fall är det $x^2$ gånger. Sedan multiplicerar man $x^2(x-1)$ och subtraherar den produkten från ursprungspolynomet i täljaren. Då får man ett nytt polynom och så upprepar man processen. Men jag förstår inte hur det hänger ihop med den distributiva lagen.

Att dividera med (x-1) är detsamma som att multiplicera med a= 1/(x-1). Därför är din division ovan lika med a•(x³-2x²+x-1)=ax³-2ax²+ax-1 som motsvarar precis den uppdelning du själv gjort ovan som exempel, och där har vi använt distributiva lagen när vi multiplicerade in a i parentesen.

Ja, så långt är jag med dig. Men det jag inte förstår är vad detta har att göra med själva "divisionsalgoritmen". Exempelvis tittar man hur många gånger $x$ går i $x^3$, inte hur många gånger $x-1$ går i $x^3$, så som det ser ut i uppdelningen. Och sedan gångrar man resultatet med $x-1$ för att erhålla $x^2(x-1)$. Varför gör man det? Jag ursäktar om jag verkar lite trög men jag ser verkligen inte kopplingen mellan hur man utför polymdivisionen och den distributiva lagen.

Frågan ”Varför gör man det?

• Svar: Det är första delen av divisionen. Du sätter den ”preliminära” kvoten till x², väl medveten om att du bara gör en bit av hela divisionen. Nu måste du titta efter vad som återstår att dividera. Därför tar du bort det redan dividerats genom att subtrahera kvoten•nämnaren dvs x²(x-1)

Målet med polynomdivision är följande:

Givet ett täljarpolynom $f(x)$ och ett nämnarpolynom $g(x)\neq 0$ med $\operatorname{deg}(g)\leq\operatorname{deg}(f)$, så vill vi hitta en kvot $q(x)$ sådan att produkten $q(x)\cdot g(x)$ är "så lik $f(x)$ som möjligt", i bemärkelsen att produkten $q(x)g(x)$ och $f(x)$ ska ha identiska termer från och med gradtalet $\operatorname{deg}(g)$ och uppåt.

Ekvivalent så vill vi välja $q(x)$ så att differensen $f(x)-q(x)g(x)$ har gradtal lägre än $\operatorname{deg}(g)$.

Idén i liggande-stolen-algoritmen är att vi bygger upp kvotpolynomet $q(x)$ termvis:

   $q(x)=q_1(x)+q_2(x)+q_3(x)+\cdots$

(med start på högstagradstermen) enligt följande lilla "livsmotto":

Börja alltid med att lösa det mest akuta problemet, och hantera resten sen!

där vi kan låtsas att "akut" betyder "av högst gradtal".

Låt oss titta på hur detta går till på ett konkret exempel, där täljaren är $f(x)=2x^4-4x^3-8x^2+18$, och nämnaren är $g(x)=x-3$.

Jag kommer precis följa liggande-stolen-algoritmen, men jag kommer beskriva vad som händer med annan notation, på ett sätt som förhoppningsvis gör det mer transparent vad som händer, och varför det fungerar.

---

Steg 1a: Vad måste $q_1(x)$ vara?

Det mest "akuta" problemet för oss är högstagradstermen i $f(x)$, så den första frågan vi ställer oss är vad högstagradstermen i kvoten måste vara för att vi ska få samma högstagradsterm som när vi multiplicerar kvoten med $g(x)$. Det kommer bara finnas en enda möjlighet!

I vårt exempel ser vi att högstagradstermen i $f(x)$ är $2x^4$. Alltså måste högtagradstermen i kvoten vara $2x^3$ för att vi ska få till termen $2x^4$ när vi multiplicerar med $(x-3)$. Vi sätter därför $q_1(x)=2x^3$.

Steg 1b: Vad blir kvar? Är vi färdiga, eller behöver vi fler termer i $q(x)$?

Kolla vad den preliminära resten

   $r_1(x):=f(x)-q_1(x)g(x)$

blir. Om alla termerna har gradtal mindre än $\operatorname{deg}(g)$ så är vi färdiga, och kan sätta $q(x):=q_1(x)$ och $r(x):=r_1(x)$. Annars fortsätter vi med att lägga till en ny term i vår kvot $q(x)$ enligt steg 2a nedan.

I vårt exempel får vi

   $r_1(x)=f(x)-2x^3(x-3)=2x^3-8x^2+18$,

som har högre gradtal än nämnaren. Så vi är inte klara ännu...

---

Steg 2a: Vad måste $q_2(x)$ vara?

Kolla vad som det nuvarande mest akuta problemet, dvs. vad högstagradstermen i resten $r_1(x)$ från Steg 1b är. Vad måste vår kvot innehålla för term $q_2(x)$ för att vi ska ta ut högstagradstermen när vi multiplicerar med nämnaren $g(x)$? Det kommer bara finnas en enda möjlighet.

I vårt exempel är högstagradstermen i resten $2x^3$, så vi måste ha en term $q_2(x)=2x^2$ i kvoten.

Steg 2b: Vad blir kvar? Är vi färdiga, eller behöver vi fler termer i $q(x)$?

Beräkna en ny preliminär rest

   $r_2(x):=r_1(x)-q_2(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)=f(x)-(q_1(x)+q_2(x))g(x)$.

Om alla termerna i $r_2(x)$ har gradtal mindre än $\operatorname{deg}(g)$ så är vi färdiga, och kan sätta $q(x):=q_1(x)+q_2(x)$ och $r(x):=r_2(x)$. Annars går vi vidare med ytterligare en term.

I vårt exempel får vi

   $r_2(x)=2x^3-8x^2+18-2x^2(x-3)=-2x^2+18$.

Gradtalet är fortfarande inte lägre än nämnarens gradtal, så vi fortsätter...

---

Steg 3a: Vad måste $q_3(x)$ vara?

Vi kollar på högstagradstermen i $r_2(x)$ och bestämmer vilken term $q_3(x)$ som kvoten måste innehålla härnäst för att vi ska få samma term när vi multiplicerar med $g(x)$. Återigen: det finns bara en möjlighet.

I vårt exempel är den kvarvarande högstagradstermen $-2x^2$, så vi måste ha en term $q_3(x)=-2x$ i kvoten.

Steg 3b: Vad blir kvar? Är vi färdiga, eller behöver vi fler termer i $q(x)$?

Beräkna en ny preliminär rest 

  $r_3(x):=r_2(x)-q_3(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)-q_3(x)g(x)=f(x)-(q_1(x)+q_2(x)+q_3(x))g(x)$.

Om alla termerna i $r_3(x)$ har gradtal mindre än $\operatorname{deg}(g)$ så är vi färdiga, och kan sätta $q(x):=q_1(x)+q_2(x)+q_3(x)$ och $r(x):=r_3(x)$. Annars går vi vidare med ytterligare en term.

I vårt exempel får vi

  $r_3(x)=-2x^2+18-(-2x)(x-3)=-6x+18$.

Gradtalet är fortfarande inte lägre än nämnarens gradtal, så vi fortsätter.

---

Steg 4a: Vad måste $q_4(x)$ vara?

Vi kollar på högstagradstermen i $r_3(x)$ och bestämmer vilken term $q_4(x)$ som kvoten måste innehålla härnäst för att vi ska få samma term när vi multiplicerar med $g(x)$. Återigen: det finns bara en möjlighet.

I vårt exempel är den kvarvarande högstagradstermen $-6x$, så vi sätter $q_4(x)=-6(x-3)$.

Steg 4b: Vad blir kvar? Är vi färdiga, eller behöver vi fler termer i $q(x)$?

Beräkna en ny preliminär rest 

  $r_4(x):=r_3(x)-q_4(x)g(x)=f(x)-(q_1(x)+q_2(x)+q_3(x)+q_4(x))g(x)$.

Om alla termerna i $r_4(x)$ har gradtal mindre än $\operatorname{deg}(g)$ så är vi färdiga, och kan sätta $q(x):=q_1(x)+q_2(x)+q_3(x)+q_4(x)$ och $r(x):=r_4(x)$. Annars går vi vidare med ytterligare en term.

I vårt exempel får vi

   $r_4(x)=-6x+18-(-6)(x-3)=0$,

som har lägre gradtal ($-\infty$) än nämnarens gradtal ($1$). Alltså är vi klara!

Slutresultatet blir att kvoten är $q(x)=2x^3+2x^2-2x-6$, och att resten är $r(x)=0$.

---

Generellt kommer den här processen alltid terminera efter ett ändligt antal steg, säg $m$, eftersom gradtalet i den kvarvarande resten minskar i varje steg, så förr eller senare får vi ett gradtal lägre än $\operatorname{deg}(g)$, och vi kommer då ha ett resultat som ser ut så här:

Steg 1: $r_1(x)=f(x)-q_1(x)g(x)$
Steg 2: $r_2(x)=r_1(x)-q_2(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)$
Steg 3: $r_3(x)=r_2(x)-q_3(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)-q_3(x)g(x)$
Steg m-1: $r_{m-1}(x)=r_{m-2}(x)-q_{m-1}(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)-\cdots-g_{m-1}(x)g(x)$
Steg m: $r_m(x)=r_{m-1}(x)-q_m(x)g(x)=f(x)-q_1(x)g(x)-q_2(x)g(x)-\cdots-g_{m}(x)g(x)$

vilket ger

$\:\:f(x)=q_1(x)g(x)+q_2(x)g(x)+\cdots+q_m(x)g(x)+r_m(x)\\\:\:=(\,q_1(x)+\cdots+q_m(x)\,)g(x)+r_m(x)\,,$

så vi kan sätta kvoten till $q(x):=q_1(x)+\ldots+q_m(x)$ och resten till $r(x):=r_m(x)$.

Anmärkningar:

• Precis som naytte redan har uppmärksammat så är det bara högstagradstermen i nämnaren $g(x)$ som spelar roll i a-stegen, eftersom vi då enbart fokuserar på att matcha ihop just högstagradstermer. Däremot spelar hela nämnaren $g(x)$ roll i b-stegen där vi beräknar resterna.
• Ytterligare en bra poäng som redan har diskuterats i tråden är att den distributiva lagen spelar en avgörande roll i göra det möjligt att konstruera kvoten $q(x)$ termvis!

Exemplet sammanfattat:

Steg 1: $2x^4-4x^3-8x^2+18=2x^3(x-3)+(2x^3-8x+18)$

$q_1(x)=2x^3$
$r_1(x)=2x^3-8x+18$

Steg 2: $2x^3-8x+18=2x^2(x-3)+(-2x^2+18)$

$q_2(x)=2x^2$
$r_2(x)=-2x^2+18$

Steg 3: $-2x^2+18=-2x(x-3)+(-6x+18)$

$q_3(x)=-2x$
$r_3(x)=-6x+18$

Steg 4: $-6x+18=-6(x-3)+0$

$q_4(x)=-6$
$r_4(x)=0$

Exemplet sammanfattat på kvotform:

Steg 1: $\frac{2x^4-4x^3-8x^2+18}{x-3}=\frac{2x^3(x-3)+2x^3-8x+18}{x-3}=2x^3+\frac{2x^3-8x+18}{x-3}$

Steg 2: $=2x^3+\frac{2x^2(x-3)-2x^2+18}{x-3}=2x^3+2x^2+\frac{-2x^2+18}{x-3}$

Steg 3: $=2x^3+2x^2+\frac{-2x(x-3)-6x+18}{x-3}=2x^3+2x^2-2x+\frac{-6x+18}{x-3}$

Steg 4: $=2x^3+2x^2-2x+\frac{-6(x-3)+0}{x-3}=2x^3+2x^2-2x-6+\frac{0}{x-3}$

Länktips: Kolla gärna in den här videon av Olof Dahl, där han går igenom precis samma polynomdivision på ett liknande sätt, men utan att introducera massa extra notation.