Qual è il metodo Newton-Rapson per trovare una radice quadrata di un numero intero? Come si usa?

L’idea di base con il metodo Newton-Raphson è che inizi con un’approssimazione ragionevolmente buona della radice desiderata di qualsiasi funzione di cui stiamo parlando (in questo caso, [matematica] f (x) = x ^ 2 – n [/ matematica] se [matematica] \ sqrt {n} [/ matematica] è quello che stiamo cercando) e usa l’approssimazione lineare della funzione (cioè la linea tangente) a quel valore di [matematica] x [/ matematica] per trovare un migliore approssimazione; quindi ripetere se necessario. Fintanto che la tua prima approssimazione è abbastanza vicina, la radice dell’approssimazione lineare (cioè l’interpretazione [matematica] x [/ matematica] della linea tangente) sarà ancora più vicina alla radice effettiva di [matematica] f (x) [/ matematica], quindi quella sarà la tua prossima approssimazione.

È abbastanza facile trovare il numero intero più vicino alla radice quadrata desiderata e che dovrebbe essere abbastanza vicino. Ad esempio, se stai cercando [matematica] \ sqrt {35} [/ matematica], è ragionevole iniziare con [matematica] x_0 = 6 [/ matematica] poiché [matematica] 36 [/ matematica], cioè [matematica ] 6 ^ 2 [/ math], è il numero quadrato più vicino a 35. Se stai cercando qualcosa come [math] \ sqrt {123.456.789} [/ math] (e non imbrogliare!) Puoi generare quadrati abbastanza rapidamente aggiunta di numeri dispari successivi (ad esempio,

[matematica] 1 = 1 ^ 2 [/ matematica]
aggiungi 3: [matematica] 4 = 2 ^ 2 [/ matematica]
aggiungi 5: [matematica] 9 = 3 ^ 2 [/ matematica]
aggiungi 7: [matematica] 16 = 4 ^ 2 [/ matematica]
e così via…)

finché non trovi che [matematica] 123.454.321 = 11.111 ^ 2 [/ matematica] e [matematica] 123.476.544 = 11.112 ^ 2 [/ matematica]. (Ho tradito.)

Torniamo a [matematica] \ sqrt {35} [/ matematica], quindi non devo scrivere così tanto. Abbiamo già determinato che [matematica] x_0 = 6 [/ matematica] è una buona approssimazione iniziale. Sappiamo dal calcolo che [matematica] f ‘(6) [/ matematica] è la pendenza della linea che è tangente al grafico di [matematica] f (x) [/ matematica] nel punto [matematica] (6, f (6)) [/ matematica], quindi un’equazione per l’approssimazione lineare è [matematica] y – f (6) = f ‘(6) (x – 6) [/ matematica]. In questo caso [matematica] f (x) = x ^ 2 – 35 [/ matematica] e quindi [matematica] f ‘(x) = 2x [/ matematica]; quindi usiamo l’equazione [matematica] y – 1 = 12 (x – 6) [/ matematica], inserisci 0 per [matematica] y [/ matematica] e [matematica] x_1 [/ matematica] per [matematica] x [ / math] e risolvi per [math] x_1 [/ math]. In questo caso otteniamo [matematica] x_1 = 71/12 [/ matematica]. Diciamo che approssimiamo questo come 5.91666666667. Quindi impostiamo l’equazione [matematica] 0 – (5.91666666667 ^ 2 – 35) = 2 (5.91666666667) (x_2 – 5.91666666667) [/ matematica] e risolviamo per [matematica] x_2 [/ matematica]. O davvero, usiamo semplicemente la formula che sarebbe derivata dalla risoluzione di [matematica] 0 – (x_1 ^ 2 – 35) = 2 x_1 (x_2 – x_1) [/ matematica] per [matematica] x_2 [/ matematica]. Ripeti fino a quando le tue risposte successive sono così vicine tra loro da avere un’approssimazione che sia accurata come desideri.

È un metodo numerico iterativo. Questo tipo di metodi crea una successione [matematica] (x_0, x_1 \ cdots x_n) [/ math]. Con alcune condizioni iniziali data una radice della fucntion f, [math] \ alpha [/ math]
[matematica] f (\ alpha) = 0 [/ matematica]

[matematica] \ lim_ {n-> inf} {\ alpha-x_n} = 0 [/ math]

Più esattamente newton-rapson segue il seguente schema:

[matematica] x_ {n + 1} = x_n – \ dfrac {f (x)} {f ‘(x_n)} [/ math]

Per trovare una radice quadrata di un numero intero (t) puoi fare questo trucco.
[matematica]
f (x) = x ^ 2 – t [/ matematica]
quindi nel nostro caso:
[matematica]
x_ {n + 1} = x_n – \ dfrac {(x_n) ^ 2-t} {2x_n}
[/matematica]

dove f ‘(x) = 2x.

Il metodo Newton-Raphson è una formula di iterazione per approssimare le radici dell’equazione [matematica] f (x) = 0 [/ matematica] per una funzione sufficientemente ben condotta [matematica] f (x) [/ matematica] che è almeno una volta -differentabile, data un’ipotesi iniziale che è “abbastanza buona”.

L’idea dell’iterazione NR è di “seguire la pendenza” della funzione nel punto [matematica] (x_n, f (x_n)) [/ matematica] indietro nel punto in cui la tangente della funzione in quel punto attraversa l’asse x. Fallo abbastanza volte e alla fine sarai “abbastanza vicino” alla radice per tutti gli scopi pratici.

Quindi l’iterazione NR inizia con una linea retta attraverso il punto [matematica] (x_n, f (x_n)) [/ matematica] con pendenza [matematica] f ^ \ prime (x_n) [/ matematica]. Questo è [matematica] \ frac {yf (x_n)} {x-x_n} = f ^ \ prime (x_n) [/ math]. Questo può essere riorganizzato nell’equazione di una linea, ma non è necessario farlo; ciò che vogliamo è il punto su questa linea che soddisfa [matematica] (x_ {n + 1}, 0) [/ matematica], quindi sostituiamo quelli in per [matematica] (x, y) [/ matematica]:

[matematica] \ frac {-f (x_n)} {x_ {n + 1} – x_n} = f ^ \ prime (x_n) [/ math]

che risolviamo per ottenere [math] x_ {n + 1} [/ math]

[matematica] x_ {n + 1} = x_n – \ frac {f (x_n)} {f ^ \ prime (x_n)} [/ math].

Quindi, per trovare la radice quadrata di un numero, vuoi costruire la giusta funzione [matematica] f (x) [/ matematica]. Il numero che stai cercando soddisfa l’equazione [matematica] x ^ 2 = a [/ matematica], dove [matematica] a [/ matematica] è il numero di cui desideri trovare la radice quadrata. Cioè, formalmente, sappiamo che [matematica] x = \ pm \ sqrt {a} [/ matematica], anche se non ne conosciamo il valore.

Possiamo riorganizzare l’equazione sopra in modo che il lato destro sia zero, e quindi il lato sinistro è la funzione che vogliamo: [matematica] f (x) = x ^ 2 – a = 0 [/ matematica]. Ta-daa!

Ora troviamo [matematica] f ^ \ prime (x) = 2x [/ matematica] e abbiamo tutto ciò di cui abbiamo bisogno per usare l’iterazione NR per approssimare [matematica] \ pm \ sqrt {a} [/ matematica]. Se ottieni la radice positiva o negativa dipende dalla tua ipotesi iniziale [matematica] x_0 [/ matematica]: un numero positivo o negativo. L’unico problema è se si sceglie il punto iniziale come [matematica] x_0 = 0 [/ matematica], perché la linea tangente ha una pendenza pari a zero e la formula NR ha una divisione per zero. Non è una buona cosa!

Una cosa bella di questo è che non devi scegliere [math] a [/ math] per essere un numero intero; può essere qualsiasi numero reale non negativo (anche se se vai abbastanza in matematica imparerai anche a gestire le radici quadrate di numeri reali negativi!).

Se sei interessato, vedi se riesci a capire quale funzione [matematica] f (x) [/ matematica] ti serve per approssimare il cubo (o qualsiasi altra) radice di numeri reali, e quindi come apparirà la formula NR in quei casi particolari.

Se hai funzioni più complicate e ipotesi iniziali non così buone, NR può darti alcuni risultati strani, come risposte che non convergono (oscillando attraverso due o più valori nel limite) o che convergono in punti molto lontani da dove iniziato, o che portano a “punti fermi” della tua funzione e quindi si fermano a causa di una divisione per zero (o di un numero così piccolo che i tuoi risultati potrebbero essere scartati se lo stai facendo su un computer). Queste sono cose con cui dobbiamo convivere, perché per quanto riguarda le radici approssimative delle funzioni, NR è uno dei metodi più veloci che abbiamo. È possibile trovare schemi simili che utilizzano derivati ​​più elevati, ma di solito sono molto più costosi (in termini di tempo di calcolo) che il piccolo guadagno in precisione con ogni passaggio non ne vale la pena. Altri metodi che non soffrono delle insidie ​​di NR saranno in genere più lenti, quindi nel mondo reale devi scegliere qualcosa che sia appropriato per il tuo problema.

Puoi anche usare NR per funzioni di più di una variabile, ma è un esercizio che è meglio lasciare fino a dopo. 😉

More Interesting

Se [matematica] p> 3 [/ matematica] è un numero primo, come si può dimostrare che se [matematica] p ^ k + p ^ l + p ^ m = n ^ 2 [/ matematica] ha soluzioni naturali [matematica] k , l, m, n [/ math], [math] p + 1 [/ math] è divisibile per [math] 8 [/ math]?

Quale sarà il resto quando 185185 scritto 100 volte è diviso per 99?

C'è qualche relazione tra equazioni differenziali e teoria dei numeri?

Come dimostreresti che esistono infiniti numeri interi [matematica] n [/ matematica] tale che [matematica] n ^ 2 [/ matematica] divide [matematica] 2 ^ n + 3 ^ n [/ matematica]?

Come mostrare che [matematica] b (n) [/ matematica] converge semplicemente sapendo che [matematica] b_1 = 0 [/ matematica] e [matematica] b (n + 1) = \ dfrac {3b (n) +1 } {b (n) 3} [/ math]

Qualche semplice spiegazione alla prova di Eulero degli infiniti numeri primi mostrati di seguito?

Come dimostrare che ci sono infiniti numeri interi [matematica] x, y [/ matematica] tale che [matematica] x + y = 100 [/ matematica] e [matematica] \ gcd (x, y) = 5 [/ matematica]

Teoria dei numeri: in che modo i matematici trovano approssimazioni / limiti asintotici per le funzioni aritmetiche?

In che modo a + ba quadrato perfetto se GCD (a, b, c) e a, b, c sono numeri interi positivi dato che 1 / a + 1 / b = 1 / c?

Teoria dei numeri: perché funzionano le regole di divisibilità?

È una buona prova aritmetica modulare?

Qual è il teorema del resto cinese e come viene utilizzato nella programmazione competitiva?

Quali sono i numeri primi p per i quali p + 3 è un quadrato perfetto?

Qual è la probabilità che un dato numero intero sia un multiplo di 2, 3 o 5, ma non due o tre?

Qual è il resto quando 128 ^ 1000 è diviso per 153?