calcolare cifre di una radice

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
wDan
Messaggi: 12
Iscritto il: 18 mag 2013, 15:18

calcolare cifre di una radice

Messaggio da wDan » 03 giu 2013, 20:47

Salve a tutti! Come posso fare per calcolare le cifre dopo la virgola di una radice?
ad esempio, se io volessi calcolare le prime sette cifre dopo la virgola di √37 ?
Mi ricordo che c'era un problema nelle passate gare che voleva il settimo numero, che era uguale al primo, solo che non sapevo nè qual era il primo nè che la settima e la prima cifra erano uguali :p

LeZ
Messaggi: 284
Iscritto il: 08 mag 2011, 21:28

Re: calcolare cifre di una radice

Messaggio da LeZ » 03 giu 2013, 21:15

Di così banale, non mi viene in mente nulla, nel senso che, la radice di un numero (per esempio un primo) non credo sia calcolabile con estrema precisione in qualche secondo. Esistono dei metodi più o meno veloci e più o meno complessi che ti permetto di calcolare il numero desiderato con una buona stima dell'errore commesso, ma sono metodo che non vengono insegnati (almeno non nel mio caso) escluso il metodo ricorsivo di Newton e i polinomi di Taylor con le loro infinite applicazioni che comunque non fanno parte della matematica elementare.
Se io dovessi calcolare $ \sqrt(37) $ con una buona precisione, userei Pell (sicuramente non è il metodo migliore ma è comunque comodo).
Ti faccio un esempio: Supponiamo che ci sia una frazione della forma $ \frac{a}{b}\simeq\sqrt{37} $, elevando alla seconda entrambi i membri ho che $ \frac{a^2}{b^2}\simeq{37}, a^2-37b^2=-1 $. Ho scelto $ -1 $ perché conosco la soluzione banale relativa all'equazione di Pell e perché $ -1 $ mi "fornisce" un piccolo errore di approssimazione.
Se ti interessa questo metodo devi approfondire Pell, comunque la prima soluzione banale è appunto $ (a,b), (6,1) $, la seconda è (se non erro) $ (882,145) $, e più avanti vai più sono precise. Infatti già la seconda coppia mi da: $ \frac{882}{145}=6,08275862 $.. e $ \sqrt{37}=6,08276253 $.. L'errore è dell'ordine di $ 10^{-5} $.

Avatar utente
wDan
Messaggi: 12
Iscritto il: 18 mag 2013, 15:18

Re: calcolare cifre di una radice

Messaggio da wDan » 03 giu 2013, 21:37

per prima cosa, grazie per la risposta :)
allora, penso di aver sbagliato proprio a scrivere il problema visto che lo avevo provato a fare (senza successo) molto tempo fa, quindi non me lo ricordavo bene ma comunque mi era rimasto questo dubbio sulla radice.
Il problema è questo: Immagine
e la risposta: http://i.imgur.com/yasu4R7.png
se già che ci sei me la spiegheresti.. :)

LeZ
Messaggi: 284
Iscritto il: 08 mag 2011, 21:28

Re: calcolare cifre di una radice

Messaggio da LeZ » 03 giu 2013, 21:55

E' spiegata benissimo la soluzione, comunque provo a rispiegartela. Sei d'accordo che $ \frac{13^7}{10^5} $ è come spostare "la virgola" verso sinistra di $ 5 $ posizioni? Non serve fare i calcoli di $ 13^7 $, ma comunque fa $ \frac{62748517}{10^5}=627,48517 $. Quindi abbiamo cinque cifre dopo la virgola, la sesta ora è $ 0 $.
Quanto fa invece $ \frac{\sqrt{3}}{10^5}? $ fa $ 0,00001732 $... Se sommi questi due numeri hai $ 627,48518732 $... Come puoi vedere non serve a nulla calcolare $ 13^7 $ bensì basta sapere che $ \sqrt{3}\simeq 1,73 $.

Avatar utente
wDan
Messaggi: 12
Iscritto il: 18 mag 2013, 15:18

Re: calcolare cifre di una radice

Messaggio da wDan » 03 giu 2013, 21:58

ecco, così l'ho capita! :)
quindi per calcolarmi quella radice di 3 come potrei fare? domani mi guardo subito quel Pell di cui parlavi :)

LeZ
Messaggi: 284
Iscritto il: 08 mag 2011, 21:28

Re: calcolare cifre di una radice

Messaggio da LeZ » 03 giu 2013, 22:05

Pell è un argomento olimpico di alto livello (IMO?), quindi ti consiglio di vedere prima bene un po' di dispense sulla teoria dei numeri e poi affrontare Pell.
Diciamo che $ \sqrt{3} $ è un numero irrazionale di cui si "dovrebbero" conoscere almeno le prime tre cifre significative, un po' come $ \pi $ o $ \sqrt{2} $. Non ci vuole comunque molto per capire che la prima cifra dopo la virgola è $ 7 $. Supponi che sia $ 6 $, eleva alla seconda $ 16 $, e ti viene $ 256 $, che è minore di $ 300 $. Eleva alla seconda $ 18 $ e ti viene $ 324 $ che è maggiore di $ 300 $ quindi $ 6<x<8 $.

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: calcolare cifre di una radice

Messaggio da Gottinger95 » 04 lug 2013, 02:02

Ehi! Io lo conosco un metodino carino carino per le radici! Le frazioni continue :D
Piccola intro sui razionali, per poi tuffarci sugli irrazionali :D
Si definisce frazione continua di \(a/b\) la seguente espressione:
\( \displaystyle \frac{a}{b} = q_0 + \frac{1}{q_1+\frac{1}{q_2 + \ldots \frac{1}{q_n}} } \)
I numeri \(q_0, \ldots, q_n\) si chiamano quozienti parziali. La frazione continua relativa ad \(a/b\) si indica con \([q_0, \ldots,q_n]\).

E uno potrebbe dire: eh va là, ma come faccio io a calcolarmi i quozienti parziali? Straafacile:
Passo 1. Prendo la parte intera di \(a/b\) ed è \(q_0\) (di fatto quello che sta dopo è un 1 fratto roba, perciò più piccolo di 1).
Passo 2. Sottraggo \(q_0\) ad \(a/b\) e prendo l'inverso: ottengo una frazione \(a'/b'\) che sottopongo nuovamente al passo 1.
Con questo si ottengono tutti i quozienti parziali, che, per i razionali, sono in numero finito.

Convergenti. Data una frazione continua \([q_0, \ldots, q_n]\), si definisce \(k\)-esimo convergente la frazione che vien fuori sviluppando la frazione continua \([q_0, \ldots, q_k]\). Per esempio, ho che \(\displaystyle 13/7 = 1 + \frac{1}{1+\frac{1}{6}} = [1,1,6]\). Lo 0-esimo convergente è [1], ossia 1, mentre il primo convergente è [1,1], ossia \(\displaystyle 1+\frac{1}{1} = 2\).
In particolare, chiamiamo rispettivamente \(A_k\) e \(B_k\) il numeratore e il denominatore del \(k\)-esimo convergente. Vale la seguente relazione di ricorrenza (prova a dimostrarla giochicchiando un pochino con le frazioni continue):
(1) \(A_{k+1} = q_{k+1} A_k + A_{k-1}, \ \ \ \ \ B_{k+1} = q_{k+1} B_k + B_{k-1} \)
Questo significa che, per ogni \(x \in \mathbb{R}\):
(2) \( \displaystyle [q_0, \ldots, q_n, x] = \frac{xA_n + A_{n-1}}{x B_n +B_{n-1} } \)
Questo servirà per dimostrare (a te :) ) che effettivamente le frazioni continue servono per approssimare gli irrazionali. Mi spiegherò meglio.
Seconda proprietà carina dei convergenti (e utile per le famose equazioni di Pell, che però adesso non ci importano):
(3) \(A_n B_{n-1} - B_n A_{n-1} = (-1)^n\)
Puoi provare a dimostrare anche questo con questo hint:
Testo nascosto:
Poniamo \(\Delta_n = A_n B_{n-1} - B_n A_{n-1}\). Prova a dimostrare che \(\Delta_n = - \Delta_{n-1}\), dunque se riesci a far vedere che \(\Delta_1 = -1\) hai vinto per induzione.
Irrazionali. In particolare, se ti interessano gli irrazionali quadratici, questi hanno uno sviluppo periodico in frazioni continue, e se non sbaglio sono della forma \([q_0; \overline{q_1, q_2, \ldots, q_2, q_1, 2q_0}]\). Puoi dimostrare che, detto \(\frac{A_n}{B_n}\) l'\(n\)-esimo convergente della frazione continua di un numero irrazionale \(\alpha\), vale
(4)\( \displaystyle |\alpha - \frac{A_n}{B_n} | < \frac{1}{B_n B_{n+1} } < \frac{1}{B_n^2}\)
Visto che i \(B_n\) sono crescenti (guarda la (1) per convincertene), significa che al crescere di \(n\) l'errore diminuisce, e in particolare tende a 0.
Per dimostrarlo, devi usare la (2) e la (3). Se non ci riesci, posto alcuni hint:
Testo nascosto:
Innanzitutto scrivi la frazione continua come \(\alpha = q_0 + \frac{1}{q_1+} \frac{1}{q_2+} \ldots \frac{1}{q_n+} \frac{1}{\alpha_{n+1} } \), e diciamo che \(q_n\) è l'ultimo quoziente parziale che ti andava di calcolare. Usa la (2) per correlare \(\alpha\) ad \(\alpha_{n+1}\), perciò sostituisci nella (4) e vedi che succede.
Testo nascosto:
Se non riesci, guarda che a un certo punto devi usare la (3) , poi considerare il fatto che \(\alpha_{n+1} > q_{n+1}\) (se ricordi il procedimento, \(q_{n+1}\) è la parte intera di \(\alpha_{n+1}\)). Infine dovrai usare anche la (1) .
La pratica. Facciamo un esempio di come si usano queste frazioni parziali per approssimare \(\sqrt{3}\):
Iniziamo a calcolarci i quozienti parziali finchè non vediamo che diventano periodici:
\(\displaystyle \sqrt{3} = 1+ (\sqrt{3}-1) = 1+ (\sqrt{3}-1)\frac{(\sqrt{3}+1)}{(\sqrt{3}+1)} = 1 + \frac{2}{\sqrt{3}+1} = 1+ \frac{1}{ \frac{\sqrt{3}+1}{2} } \)
Come vedi, basta razionalizzare la parte rimanente e poi prendere l'inverso. Continuiamo:
\(\displaystyle \frac{\sqrt{3}+1}{2} = 1 + \frac{\sqrt{3}-1}{2} = 1+ \frac{2}{2(\sqrt{3}+1)} = 1+ \frac{1}{ \sqrt{3}+1} \)
\(\displaystyle \sqrt{3}+1 = 2 + (\sqrt{3}-1) = 1+ \frac{1}{\frac{(\sqrt{3}+1)}{2} } \)
e qui siamo felici, perchè ci è ricapitato lo stesso calcolo iniziale. Perciò abbiamo \(\sqrt{3} = [1;\overline{1,2}]\). Calcoliamo a mano i primi due convergenti:
\(A_0 = q_0 = 1, \ B_0 = 1; \ \ \ \ A_1 = q_0q_1 + 1 = 2, B_1 = q_1 = 1\)
Adesso con la relazione di ricorrenza (1) te ne puoi calcolare finchè non ti stanchi; andando un po' avanti si ottiene:
\(A_2 = 2*2 + 1 = 5, \ A_3 = 5*1 + 2 = 7, \ A_4 = 7*2 + 5 = 19,\ A_5 = 19*1 + 7 = 26\)
\(B_2 = 2*1+1=3, \ B_3 = 3*1 + 1 = 4, \ B_4 = 4*2 + 3 = 11, \ B_5 = 11*1 + 4 = 15\)
Perciò \(26/15\) può essere una buona approssimazione; precisamente, ha un errore di \(1/15^2\) (vedi la (4)), ossia ha le prime due cifre dopo la virgola giuste. Andando un po' avanti puoi ottenere in fretta buone approssimazioni :D

Piccole altre cose. Puoi dimostrare, grazie alla (1) e al fatto che \(B_0 = 1\), che numeratore e denominatore \(A_k, B_k\) del \(k\)-esimo convergente sono sempre primi fra loro. Inoltre il convergente \(A_k / B_k\) della frazione continua di un irrazionale \(\alpha\) rappresenta la migliore approssimazione razionale possibile con denominatore minore o uguale a \(B_k\).

Spero di esserti stato utile!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: calcolare cifre di una radice

Messaggio da ma_go » 04 lug 2013, 08:08

LeZ ha scritto: [...] Non ci vuole comunque molto per capire che la prima cifra dopo la virgola (di $\sqrt3$, NdA) è $ 7 $. Supponi che sia $ 6 $, eleva alla seconda $ 16 $, e ti viene $ 256 $, che è minore di $ 300 $. Eleva alla seconda $ 18 $ e ti viene $ 324 $ che è maggiore di $ 300 $ quindi $ 6<x<8 $.
in realtà devi osservare che $17^2 = 289 \le 300 < 324 = 18^2$, non ti basta osservar che $16^2 < 300 < 18^2$. è un dettaglio, lo so, ma preferisco correggerlo subito -- non tanto per te, quanto per i lettori meno esperti.

LeZ
Messaggi: 284
Iscritto il: 08 mag 2011, 21:28

Re: calcolare cifre di una radice

Messaggio da LeZ » 17 lug 2013, 12:35

Sì. Dalle frazioni parziali deriva poi Pell..
Un metodo veloce che si lega con quanto abbiamo detto prima è anche questo. Faccio direttamente un esempio.
Voglio calcolarmi $ \sqrt2 $. Prendo $ (\sqrt2-1)^n $. Sviluppo per esempio per $ n=4 $ (ovviamente maggiore sarà $ n $ maggiore sarà la precisione). Ottengo $ 17-12\sqrt2 $. A questo punto divido i coefficienti interi tra di loro (in questo caso $ \frac{17}{12} $) che viene $ 1,4166 $.. Insomma è già buona. Anche la spiegazione di questo metodo è semplice perché elevando alla $ n $, quella differenza tende a $ 0 $.

Rispondi