Algoritmo della divisione

[galles90]

Buongiorno,

Sto leggendo la proposizione riguardante l'algoritmo della divisione. Vi riporto solo la parte che non mi è chiara cioè quella inerente all'unicità.

Enunciato

Siano $P_1$ un polinomio di grado $n$ e $P_2$ di grado $m$. Allora esistono e sono unici due polinomi $Q$ e $R$ tali che:

$P_1=Q circdot P_2+R$ e $deg(R).
Inoltre, se $ m le n $ si ha $deg(Q)=n-m$ , mentre se $n

Come detto tralasciando la parte dell'esistenza vi riporto solo quella riguardante l'unicità.
Siano $Q_1$ e $R_1$ altri due polinomi tali che $P_1=Q_1 circ P_2+R_1$ e $deg(R_1) Poiché $R-R_1=P_1-Q circ P_2-(P_1-Q_1 circ P_2)=(Q-Q_1) circ P_2 $ il grado di $R-R_1$ è $p+m$ ma d'altra parte $R$ ed $R_1$ hanno entrambi grado minore di $m$ e quindi deve essere $deg(R-R_1) Si conclude che $R-R_1$ coincide con il polinomio nullo e quindi $R=R_1$

La parte che non mi è chiara è quella in grassetto, i passaggi che ha fatto in precedenza mi sono chiari, l'unico che non mi chiaro è questo.

Grazie in anticipo per eventuali risposte.

Ciao

Cita

Segnala

---

Risposte

otta96

29 mar 2018, 15:11

Questa dimostrazione ha alcune cose che non vanno, le correggo: innanzitutto suppongo che tu stia lavorando in $RR[x]$, ovvero nell'anello dei polinomi a coefficienti reali (o in $K[x]$ con $K$ campo va bene ugualmente)

"galles90":Siano $Q_1$ e $R_1$ altri due polinomi tali che $P_1=Q_1 circ P_2+R_1$ e $deg(R_1)$R_1$, non $R$). Sia $m$ il grado di $Q-Q_1$. (non puoi usare di nuovo $n$, lo hai già usato, semmai usa $p$)
Poiché $R-R_1=P_1-Q circ P_2-(P_1-Q_1 circ P_2)=-(Q-Q_1) circ P_2 $, supponendo per assurdo che $Q!=Q_1$ il grado di $R-R_1$ è $p+m$

$p$? chi è $p$? non si capisce bene, avrebbe senso se $p$ fosse il grado di $Q-Q_1$ per questo prima l'ho chiamato p.

ma d'altra parte $R$ ed $R_1$ hanno entrambi grado minore di $m$ e quindi deve essere $deg(R-R_1) Si conclude che $R-R_1$ coincide con il polinomio nullo e quindi $R=R_1$

La conclusione si ha perchè il grado di $R-R_1$ dovrebbe essere sia $=m$ (in quanto $=m+p,p>=0$), assurdo, allora $Q=Q_1$ e $R=R_1$.
P.S. A voler essere precisi il punto in cui ho scritto "supponendo per assurdo che $Q!=Q_1$" andava scritto prima di considerare il grado di $Q-Q_1$, perché sennò non si sa nemmeno se è ben definito.

Cita

Segnala

---

galles90

29 mar 2018, 16:03

Ciao ho corretto gli errori che mi hai fatto notare, grazie.

"otta96":suppongo che tu stia lavorando $ RR[x] $

Si.

"otta96": P.S. A voler essere precisi il punto in cui ho scritto "supponendo per assurdo che $ Q!=Q_1 $" andava scritto prima di considerare il grado di $ Q-Q_1 $, perché sennò non si sa nemmeno se è ben definito.

Questo non l'ho scritto.

Cita

Segnala

---

otta96

29 mar 2018, 17:36

Ma non ho capito se hai capito.

Cita

Segnala

---

galles90

29 mar 2018, 18:18

Non del tutto, cioè quando dici:

"otta96":La conclusione si ha perchè il grado di $ R-R_1 $ dovrebbe essere sia$=m $ (in quanto $ =m+p,p>=0 $), assurdo, allora $ Q=Q_1 $ e $ R=R_1 $.
.

Mi chiaro che è assurdo, però il collegamento tra i due concetti non li riesco a vedere.

Cita

Segnala

---

otta96

29 mar 2018, 18:27

Quindi se ho capito bene hai capito perché è assurdo ma non perché questo implichi quello che ho scritto dopo, in tal caso il motivo è questo: l'assurdo era nato dal fatto che avevamo supposto che $Q!=Q_1$ quindi abbiamo $Q=Q_1$ e allora $R-R_1=-(Q-Q_1)*P_2=0=>R=R_1$.
Spero che così sia chiaro, ma se non lo è non esitare a dirmelo, magari cerca di spiegare meglio possibile cosa di preciso non ti è chiaro.

Cita

Segnala

---

galles90

30 mar 2018, 14:59

Si si ora mi è tutto chiaro, non avevo afferrato il concetto $ Q ne Q_1$ che avevi scritto .

Comunque ci sarebbe un altro punto che non mi è chiaro, riguarda la prima parte:

Si supponga ora che la tesi sia vera per i numeri naturali minori o uguali di un fissato numero naturale $n$ e si supponga che il grado di $P_1$ sia $n+1$.
Siano quindi :

$P_1(z)=a_{n+1}z^{n+1}+...+a_0, P_2(z)=b_mz^m+...+b_0 .

Si ponga $c=a_{n+1}/b_m$ e si consideri il polinomio $P_0=c circ z^{n+1-m}$
Il polinomio \(\displaystyle P_1 - P_0 \circ P_2 \) ha grado \(\displaystyle p \le n \) ; se \(\displaystyle p < m \) si ha $Q=P_0$ e $R=P_1 - P_0 circ P_2$. Invece se $ m le p$ si ha anche $ m le n$ in quanto $p le n+1$ e quindi per l'ipotesi di induzione applicata ai polinomi $(P_1 - P_0 circ P_2, P_2)$ , esistono un polinomio $Q_0$ di grado $p-m$ ed un polinomio $R$ di grado minore di $m$, tali che

$P_1 - P_0 circ P_2=Q_0 circ P_2 +R$

La parte che non mi è chiara sarebbe quella messa in grassetto. Cioè l'autore vuol dire che ha applicato più volte l'algoritmo di divisione ?

Cita

Segnala

---

otta96

30 mar 2018, 15:50

Non è che applica più volte l'algoritmo di divisione, ma l'algoritmo ha un ciclo lui sta facendo vedere come funziona il primo passaggio perché quello è sufficiente per ricondursi a un caso più semplice (ovvero il grado del polinomio che devi dividere è diminuito) che sa già fare (è l'ipotesi induttiva). In altre parole, se sai un minimo di programmazione lui ti sta spiegando come funziona una routine di un ciclo while ricorsivo.

Cita

Segnala

---

galles90

30 mar 2018, 16:30

Ok ci sono, mi è tutto chiaro. Sei stato super chiaro
A presto.

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[otta96]

Questa dimostrazione ha alcune cose che non vanno, le correggo: innanzitutto suppongo che tu stia lavorando in $RR[x]$, ovvero nell'anello dei polinomi a coefficienti reali (o in $K[x]$ con $K$ campo va bene ugualmente)

"galles90":Siano $Q_1$ e $R_1$ altri due polinomi tali che $P_1=Q_1 circ P_2+R_1$ e $deg(R_1)$R_1$, non $R$). Sia $m$ il grado di $Q-Q_1$. (non puoi usare di nuovo $n$, lo hai già usato, semmai usa $p$)
Poiché $R-R_1=P_1-Q circ P_2-(P_1-Q_1 circ P_2)=-(Q-Q_1) circ P_2 $, supponendo per assurdo che $Q!=Q_1$ il grado di $R-R_1$ è $p+m$

$p$? chi è $p$? non si capisce bene, avrebbe senso se $p$ fosse il grado di $Q-Q_1$ per questo prima l'ho chiamato p.

ma d'altra parte $R$ ed $R_1$ hanno entrambi grado minore di $m$ e quindi deve essere $deg(R-R_1) Si conclude che $R-R_1$ coincide con il polinomio nullo e quindi $R=R_1$

La conclusione si ha perchè il grado di $R-R_1$ dovrebbe essere sia $=m$ (in quanto $=m+p,p>=0$), assurdo, allora $Q=Q_1$ e $R=R_1$.
P.S. A voler essere precisi il punto in cui ho scritto "supponendo per assurdo che $Q!=Q_1$" andava scritto prima di considerare il grado di $Q-Q_1$, perché sennò non si sa nemmeno se è ben definito.

[galles90]

Ciao ho corretto gli errori che mi hai fatto notare, grazie.

"otta96":suppongo che tu stia lavorando $ RR[x] $

Si.

"otta96": P.S. A voler essere precisi il punto in cui ho scritto "supponendo per assurdo che $ Q!=Q_1 $" andava scritto prima di considerare il grado di $ Q-Q_1 $, perché sennò non si sa nemmeno se è ben definito.

Questo non l'ho scritto.

[otta96]

Ma non ho capito se hai capito.

[galles90]

Non del tutto, cioè quando dici:

"otta96":La conclusione si ha perchè il grado di $ R-R_1 $ dovrebbe essere sia$=m $ (in quanto $ =m+p,p>=0 $), assurdo, allora $ Q=Q_1 $ e $ R=R_1 $.
.

Mi chiaro che è assurdo, però il collegamento tra i due concetti non li riesco a vedere.

[otta96]

Quindi se ho capito bene hai capito perché è assurdo ma non perché questo implichi quello che ho scritto dopo, in tal caso il motivo è questo: l'assurdo era nato dal fatto che avevamo supposto che $Q!=Q_1$ quindi abbiamo $Q=Q_1$ e allora $R-R_1=-(Q-Q_1)*P_2=0=>R=R_1$.
Spero che così sia chiaro, ma se non lo è non esitare a dirmelo, magari cerca di spiegare meglio possibile cosa di preciso non ti è chiaro.

[galles90]

Si si ora mi è tutto chiaro, non avevo afferrato il concetto $ Q ne Q_1$ che avevi scritto .

Comunque ci sarebbe un altro punto che non mi è chiaro, riguarda la prima parte:

Si supponga ora che la tesi sia vera per i numeri naturali minori o uguali di un fissato numero naturale $n$ e si supponga che il grado di $P_1$ sia $n+1$.
Siano quindi :

$P_1(z)=a_{n+1}z^{n+1}+...+a_0, P_2(z)=b_mz^m+...+b_0 .

Si ponga $c=a_{n+1}/b_m$ e si consideri il polinomio $P_0=c circ z^{n+1-m}$
Il polinomio \(\displaystyle P_1 - P_0 \circ P_2 \) ha grado \(\displaystyle p \le n \) ; se \(\displaystyle p < m \) si ha $Q=P_0$ e $R=P_1 - P_0 circ P_2$. Invece se $ m le p$ si ha anche $ m le n$ in quanto $p le n+1$ e quindi per l'ipotesi di induzione applicata ai polinomi $(P_1 - P_0 circ P_2, P_2)$ , esistono un polinomio $Q_0$ di grado $p-m$ ed un polinomio $R$ di grado minore di $m$, tali che

$P_1 - P_0 circ P_2=Q_0 circ P_2 +R$

La parte che non mi è chiara sarebbe quella messa in grassetto. Cioè l'autore vuol dire che ha applicato più volte l'algoritmo di divisione ?

[otta96]

Non è che applica più volte l'algoritmo di divisione, ma l'algoritmo ha un ciclo lui sta facendo vedere come funziona il primo passaggio perché quello è sufficiente per ricondursi a un caso più semplice (ovvero il grado del polinomio che devi dividere è diminuito) che sa già fare (è l'ipotesi induttiva). In altre parole, se sai un minimo di programmazione lui ti sta spiegando come funziona una routine di un ciclo while ricorsivo.

[galles90]

Ok ci sono, mi è tutto chiaro. Sei stato super chiaro
A presto.