Cristian Consonni bio photo

Cristian Consonni

Computer science PhD student, free software activist, physicist and storyteller

Email Twitter Facebook Google+ LinkedIn Github keybase

Riassunto: per errore, le slides relative al metodo di Newton riportavano che la serie convergeva al valore \(\lim_{n \to \infty} x_{n} = \sqrt{z}\), invece la successione converge a \(\dfrac{1}{\sqrt{z}}\) ovvero \(\lim_{n \to \infty} x_{n} = \dfrac{1}{\sqrt{z}}\).

Mi sono state fatte alcune domande e mi è stato segnalato un errore rispetto all’esercizio per il calcolo della radice quadrata di un numero con il metodo di Newton presentato a lezione il 30/09/2015. Condivido qui le risposte:

  • per errore le slide relative al metodo di Newton riportavano che la serie convergeva erroneamente al valore \(\lim_{n \to \infty} x_{n} = \sqrt{z}\) invece la successione converge a \(\dfrac{1}{\sqrt{z}}\) ovvero \(\lim_{n \to \infty} x_{n} = \dfrac{1}{\sqrt{z}}\). Mi scuso per la svista, ora le slides sono corrette.

  • Per alcuni valori di del quale calcolare la radice quadrata, partendo dal valore si ottiene un comportamento oscillatorio, ovvero la successione continua a “saltare” tra due valori. In particolare, per esempio, quando si ha . Questo tipo di problemi è tipico dei processi iterativi. Nello specifico, partendo dal sistema di equazioni iniziale:

si deve descrivere la situazione in cui si forma un ciclo. Se la successione assume il valore e da questo , ed inoltre da si ha allora la successione diventa \({ x_n = \dots, a, b, a, b, a, \dots }\). In situazione si è formato un ciclo di lunghezza due. I possibili cicli di lunghezza due per il caso possono essere trovati risolvendo il seguente sistema di equazioni (in generale si può trattare come un parametro):

  • Si ottengono le seguenti soluzioni (notate \([a=\frac{1}{2},b=-\frac{1}{2}]\))
    • \([a=-\frac{1}{2\cdot \sqrt{5}},b=-\frac{1}{2\cdot \sqrt{5}}]\)
    • \([a=\frac{1}{2\cdot \sqrt{5}},b=\frac{1}{2\cdot \sqrt{5}}]\)
    • \([a=-\frac{1}{2},b=\frac{1}{2}]\)
    • \([a=\frac{1}{2},b=-\frac{1}{2}]\)
    • \([a=\frac{\sqrt{\sqrt{7}\cdot i+3}\cdot \left( \sqrt{2}\cdot \sqrt{5}\cdot \sqrt{7}\cdot i-3\cdot \sqrt{2}\cdot \sqrt{5}\right) }{80},b=-\frac{\sqrt{\sqrt{7}\cdot i+3}}{2\cdot \sqrt{10}}]\)
    • \([a=-\frac{\sqrt{\sqrt{7}\cdot i+3}\cdot \left( \sqrt{2}\cdot \sqrt{5}\cdot \sqrt{7}\cdot i-3\cdot \sqrt{2}\cdot \sqrt{5}\right) }{80},b=\frac{\sqrt{\sqrt{7}\cdot i+3}}{2\cdot \sqrt{10}}]\)
    • \([a=-\frac{\sqrt{3-\sqrt{7}\cdot i}\cdot \left( \sqrt{2}\cdot \sqrt{5}\cdot \sqrt{7}\cdot i+3\cdot \sqrt{2}\cdot \sqrt{5}\right) }{80},b=-\frac{\sqrt{3-\sqrt{7}\cdot i}}{2\cdot \sqrt{10}}]\)
    • \([a=\frac{\sqrt{3-\sqrt{7}\cdot i}\cdot \left( \sqrt{2}\cdot \sqrt{5}\cdot \sqrt{7}\cdot i+3\cdot \sqrt{2}\cdot \sqrt{5}\right) }{80},b=\frac{\sqrt{3-\sqrt{7}\cdot i}}{2\cdot \sqrt{10}}]\)
    • \([a=0,b=0]\)
  • Le soluzioni sono i valori per cui la serie oscilla (e per quanto riguarda le prime due coppie di risultati, come sottocaso, si trovano anche le soluzioni che sono punto fisso ovvero \(z = - 1/\sqrt{20}\) e \(z = 1/\sqrt{20}\)).

  • in generale, utilizzando per \(x_0\) un valore più vicino al risultato riduce i tempi di convergenza e da evitare questi problemi. Nello specifico è semplice calcolare la parte intera di una radice quadrata (ovvero l’intero \(x\) più grande tale che \(x^2 < z\)). In particolare in questo caso \(\sqrt{20} > 4\), quindi è bene partire da \(1/4 = 0.25\). Quindi, quando scegliete il valore iniziale calcolate (a mente) l’intero più grande \(x\) tale per cui \(x^2 < z\) e inizializzate la successione, ovvero usate come valore di \(x_0\) il reciproco di quel numero. (\({\lfloor x \rfloor}\) indica il \(\texttt{floor}\) di \(x\) ovvero il valore di \(x\) arrotondato all’intero più piccolo).
  • Rispetto all’errore compiuto dal metodo, ovvero su come interpretare il valore di \(\varepsilon\) si può notare che definendo \(r_{n} = \dfrac{1}{x_{n}}\) la condizione di terminazione si può scrivere come ovvero nella peggiore delle ipotesi \(r^{2}_{n} = z \pm \varepsilon\) e . Utilizzando gli sviluppi in serie di McLaurin e supponendo \(\varepsilon\) sufficientemente piccolo si ha che:
  • Quindi la differenze in valore assoluto tra \( r_{n} \) e \( \sqrt{z} \) è al primo ordine (con \(z>1\)):