Estrazione radice quadrata

Negli algoritmi e nell'analisi numerica , l' estrazione della radice quadrata è il processo con cui, dato un numero, si calcola la sua radice quadrata . Esistono molti metodi per eseguire questo calcolo. Si tratta di un caso particolare della ricerca del calcolo della radice n-esima .

Contesto

Poiché la radice quadrata di un numero può essere un numero irrazionale , l'estrazione della radice quadrata è generalmente approssimativa.

Definizioni

Estrarre la radice quadrata di a equivale a risolvere l'equazione . Si applicano quindi i metodi generali di risoluzione delle equazioni polinomiali, e più in generale gli algoritmi per la ricerca dello zero di una funzione . Gli stessi strumenti vengono utilizzati per misurare le prestazioni dei metodi.

Quando non viene fornita alcuna precisione aggiuntiva, l'estrazione della radice quadrata viene eseguita nell'insieme dei numeri reali . Possiamo tuttavia essere interessati ad altri insiemi di numeri come numeri complessi o anelli come ℤ / nℤ .

Metodi per numeri reali positivi

Metodo di Airone

Il metodo Heron è un metodo storico sviluppato dai Babilonesi . In termini più moderni, questo è un caso speciale del metodo di Newton .

Per determinare la radice quadrata del numero (positivo) a , è quindi necessario considerare la sequenza definita per induzione come segue: primo termine scelto se possibile "abbastanza vicino" per una , in generale la parte intera di un .

La velocità di convergenza di approssimazioni successive verso il valore esatto è quadratica .

Metodo del manoscritto Bakshali

Si trova in un manoscritto indiano, detto scrittura Bakshali, forse risalente al VII °  secolo, una diversa correzione del metodo di Erone, il nuovo valore essendo approssimato . È equivalente ad applicare il metodo di Erone due volte di seguito. L'iterazione di quest'ultimo metodo fornisce una velocità di convergenza biquadratica:

Ravvicinamento delle un utilizzando sequenze adiacenti

Consideriamo le successioni u e v definite da:

Le successioni u e v sono adiacenti e convergono verso lo stesso limite: a . L'errore è aumentato dalla differenza . La sequenza v non è altro che la sequenza ottenuta iterando il metodo di Erone dal valore 1 .

Si noti l'originalità di questa presentazione che combina mezzi armonici, geometrici e aritmetici. Infatti a non è altro che la media geometrica di 1 e di a , e se sostituiamo con un qualsiasi numero reale strettamente positivo b , le successioni u e v convergono verso la media geometrica ab di a e b .

Algoritmi che utilizzano la notazione decimale

Algoritmo dello stelo

L'introduzione della notazione decimale dei numeri per posizione ha permesso di sviluppare un algoritmo sfruttando questa notazione. È menzionato in un'opera del matematico indiano Âryabhata , intorno al 499 d.C. DC E 'stato utilizzato per diversi secoli fino alla metà del XX °  secolo, prima dell'invenzione dei calcolatori elettronici. Âryabhata fornisce anche un algoritmo comparabile per il calcolo delle radici cubiche .

Separare le cifre del numero a coppie partendo dalla virgola. Mettiamo in alto il numero da cui vogliamo estrarre la radice, allo stesso modo di quando eseguiamo una divisione secondo il metodo classico; la radice quadrata sarà inscritta nel posto normalmente riservato al divisore in una divisione in posa convenzionale.

Ad ogni passo:

Notiamo che la ricerca di x trascurando il termine in x 2 non è altro che il metodo di Erone.

Esempio: 152,2756 = 12,34 con il metodo del patibolo

(Nota: la sequenza di cifre che costituisce la radice si iscrive come e quando il posto devoluto al divisore in una divisione classica, e dà il risultato: 12.34. Il posto della virgola è significativo ma non ha bisogno di essere preso in considerazione durante i calcoli, annotalo alla fine)

1 52 , 27 56 1 2 , 3 4   Costituzione progressiva della radice r . Abbassiamo la prima fetta.
1 ? ×? Cerchiamo la x più grande tale che x ² non superi 1. È 1 . Completiamo r .
-1 1 × 1 = 1 che togliamo dall'attuale residuo e abbassiamo la tranche successiva.
0 52 2?×? r = 1, cerchiamo il più grande x tale che (20+ x ) x non superi 52. È 2 . Completiamo r .
- 44 2 2 × 2 = 44 che si toglie dal resto corrente e si abbassa la fetta successiva. Mettiamo la virgola in r .
8 27 24? ×? r = 12, stiamo cercando il più grande x tale che (240+ x ) x non superi 827. È 3 . Completiamo r .
-7 29 24 3 × 3 = 729 che togliamo dall'attuale residuo e abbassiamo la tranche successiva.
  98 56 246? ×? r = 123, stiamo cercando il più grande x tale che (2460+ x ) x non superi 9856. Questo è 4 . Completiamo r .
- 98 56 246 4 × 4 = 9856 che togliamo dal riposo attuale
0   Fine

Fino al XX °  secolo era comunemente usato questo algoritmo velocizzando i calcoli con un abaco formato una serie di strisce: i bastoni Napier .

Sebbene qui descritta per i numeri scritti in base 10, la procedura funziona in qualsiasi base numerica, ad esempio base 2 .

Metodo Ruffini-Horner

Trovare la radice quadrata di A è trovare la radice positiva del polinomio P (X) = X² - ​​​​A. Sia a l'intero più grande tale che P (a) sia negativo o zero. La radice di A è un numero intero compreso tra a e a + 1. Poniamo quindi X = a + Y / 10. P (X) = P (a + Y / 10) = P 1 (Y). La radice quadrata di A è quindi uguale a a + r / 10 dove r è la radice del polinomio P 1 . Se b è l'intero più grande tale che P 1 (b) è negativo, allora la radice di A è compresa tra a + b / 10 e a + b / 10 + 1/10. Poniamo quindi Y = b + Z / 10, P 1 (Y) = P 2 (Z). Cerchiamo quindi una radice di P 2 , ecc.

Il metodo Ruffini-Horner rende facile cambiare le variabili

Esempio: 152,2756 = 12,34 con il metodo di Horner

P (X) = X² - ​​152,2756

a = 12 perché P (12) <0 e P (13)> 0

Il cambio della variabile X = 12 + Y / 10 nel polinomio P si effettua secondo il metodo di Horner:

Coefficienti di P 1 0 - 153.2756
1 12 144 -152,2756 = -8,2756
1 12 + 12 = 24
1

pertanto

Il più grande intero b tale P 1 (b) è negativo è 3 (stiamo cercando un valore vicino a 827/240). La radice cercata è quindi compresa tra 12.3 e 12.4

Eseguiamo il cambio di variabile Y = 3 + Z / 10 nel polinomio P 1

Coefficienti di P 1 1 240 - 827,56
1 3 × 1 + 240 = 243 3 × 243 -827,56 = -98,56
1 3 × 1 + 243 = 246
1

pertanto

4 è una radice di P 2 . Quindi la radice quadrata di 152,2756 è 12,34

Estrazione per somme dispari successive

Questo metodo insegnato volte il XIX °  secolo a vantaggio di essere ridotta ad una serie di aggiunte (fino 9 per decimale ricercato) di dispari consecutivi

Consiste nell'utilizzare la tabella dei quadrati successivi e la loro differenza, osservando che . La scansione della tavola dei quadrati consiste quindi nell'addizione di numeri dispari successivi. Dopo aver tagliato il numero in fette di due cifre partendo da destra, troviamo il quadratino subito sotto il gruppo più a sinistra. Sia la radice quadrata di questo quadrato immediatamente inferiore. Moltiplichiamo l'intero trovato per e spazziamo la tavola dei quadrati a partire da (e ) per avvicinarci al numero formato dai due gruppi più a sinistra. Trovato questo numero , lo moltiplichiamo per sfogliare la tabella dei quadrati a partire da , ecc.

Prima di scansionare la tavola dei quadrati da , la facile calcolabilità dei quadrati degli interi che terminano con 5 può consentire, in alcuni casi, di eliminare cinque addizioni verificando se , o , rimane anche inferiore (o meno) al numero di cui stanno cercando la radice. In tal caso, è meglio continuare l'algoritmo da che da .

Ad esempio, vogliamo arrotondare vicino alla radice quadrata di . Per rispettare questa precisione, dobbiamo cercare la radice di . Sarà quindi sufficiente dividere la radice finale per .

Come dire , abbiamo: . Ma essere più vicino a che a , sarà più vicino a che a .

Invece di iniziare a spazzare via e possiamo, in questo caso, avviare il processo  : . Era buono, come previsto .

L'algoritmo (dettagliato nell'esempio seguente) ci porta, a poco a poco, a cui aggiungiamo , quindi che è più vicino a di . Si deduce: a chiudere.

Esempio: 152,2756 = 12,34 con il metodo dei numeri dispari successivi

La radice quadrata 1.522.756 darà a un fattore di 100 la radice quadrata desiderata. Questo numero viene tagliato in fette di 2 cifre 1 52 27 56. Il quadrato più vicino al primo gruppo è 1.

Eseguiamo quindi la scansione della tabella dei quadrati da 10 per avvicinarci a 152

non 2n + 1 = (n + 1)² - n²
10 100 21
11 100 + 21 = 121 23
12 121 + 23 = 144 25

Sommare 25 porterebbe a superare 152. Passiamo quindi ai successivi dieci ripercorrendo la tavola dei quadrati da 120 per avvicinarci a 15227.

non 2n + 1 = (n + 1)² - n²
120 14400 241
121 14400 + 241 = 14641 243
122 14641 + 243 = 14884 245
123 14884 + 245 = 15129 247

Sommare 247 porterebbe a superare 15227. Passiamo quindi ai successivi dieci sfogliando la tabella delle piazze da 1230 ad avvicinarci a 1522756.

non 2n + 1 = (n + 1)² - n²
1230 1512900 2461
1231 1512900 + 2461 = 1515361 2463
1232 1515361 + 2463 = 1517824 2465
1233 1517824 + 2465 = 1520289 2467
1234 1520289 + 2467 = 1522756

1522756 è quindi il quadrato di 1234 e 152.2756 è quello di 12.34


Questo stesso principio viene utilizzato nell'estrazione della radice quadrata con il metodo a goccia .

Estrazione per addizione e sottrazione

Questo metodo molto semplice ha la particolarità di utilizzare solo operazioni molto semplici: addizione, sottrazione e addizione di 0. Si considerino le successioni a e b definite da:

  • ,
  • Se poi e
  • Altrimenti, (che equivale ad aggiungere due zeri alla fine di ) e (che equivale a inserire uno zero appena prima dell'ultima cifra di perché quest'ultima finisce sempre con un 5)

Pertanto, i numeri di si avvicinano sempre di più ai numeri di . Nota che rimane un intero (sempre più grande) quindi non è quello che tende ma solo le sue cifre nella sua rappresentazione decimale.

Esempio: 3 ≈ 1.732 per addizione e sottrazione

,

Commenti
0 15 5 possiamo sottrarre
1 10 1 5 Non possiamo più sottrarre
2 1000 105 possiamo sottrarre
3 895 115 possiamo sottrarre
4 780 125 possiamo sottrarre
5 655 135 possiamo sottrarre
6 520 145 possiamo sottrarre
7 375 155 possiamo sottrarre
8 220 165 possiamo sottrarre
9 55 17 5 Non possiamo più sottrarre
10 5500 1705 possiamo sottrarre
11 3795 1715 possiamo sottrarre
12 2080 1725 possiamo sottrarre
13 355 173 5 Non possiamo più sottrarre
14 35500 17305 possiamo sottrarre
15 18195 17315 possiamo sottrarre
16 880 1732 5 non possiamo più sottrarre
...

Se, invece di 5 m , prendiamo troncamenti in incrementi di due cifre e, invece di aggiungere due zeri ad un n , si abbassa i seguenti incrementi, si finisce con la variante dal 5 del metodo goccia a goccia.

Metodo della frazione continua

La frazione continua di un irrazionale è la sequenza delle sue approssimazioni "ottimali" per frazioni, vale a dire che se p / q è uno dei valori di questa sequenza, allora nessuna frazione di a / b con b < q no si avvicina più accuratamente alla realtà. Nel caso particolare delle radici quadrate, si calcola in modo relativamente semplice questa successione, nonché una sottosequenza che corrisponde ad un caso particolare del metodo di Erone .

Metodo della dicotomia

È anche possibile procedere per dicotomia, purché vi sia un quadro per la radice quadrata desiderata. Per questo, possiamo usare il numero di cifre del numero di cui stiamo cercando la radice quadrata. Questa radice avrebbe la metà delle cifre. Quindi, se il numero ha 1.024 cifre, la sua radice quadrata sarà compresa tra 511 e 513. Possiamo anche utilizzare prima i metodi precedenti per ottenere un primo valore approssimativo della radice quadrata prima di procedere alla dicotomia.

L'algoritmo della dicotomia è il seguente. Evita di eseguire divisioni (diverse dalla divisione per 2 che è solo uno spostamento di registro se i numeri sono codificati in binario. Questa divisione è indicata sotto shr 1).

function Racine_64(C: int64): int64; var A, B, D, D2: int64; begin A := borne basse; B := borne haute; repeat D := (A + B) shr 1; D2 := D * D; ⇐ on élève au carré avant de tester if D2 > C then A := D - 1 else if C > D2 then B := D + 1 else Result := A; until B > A; end;

Lo stesso metodo si applica alle radici n-esime, sostituendo il calcolo di D2 = D * D con il calcolo di D ^ n.

Il metodo della dicotomia, tuttavia, ha un tasso di convergenza più lento rispetto all'iterazione del metodo di Erone.

In altre serie di numeri

Numeri complessi

Anelli ℤ / nℤ

Proviamo a risolvere l'equazione . Possiamo allora distinguere tre casi:

  • è un numero primo (es. 19);
  • è una potenza di un numero primo (es. 81 = 3 4 );
  • è un numero composto (es. 35 = 5 × 7).

Se esiste una soluzione, cioè se è un residuo modulo quadratico , si hanno algoritmi efficienti per trovarla nei primi due casi. Se è un numero composto, al momento abbiamo un algoritmo efficiente solo se è nota la fattorizzazione di . Inoltre possiamo dimostrare che se esistesse un algoritmo efficiente per calcolare una radice quadrata senza avere la fattorizzazione di , questo algoritmo potrebbe essere utilizzato per ottenere un algoritmo di fattorizzazione efficiente . Non saremo quindi in grado di calcolare in modo efficiente radici quadrate modulo finché non saremo in grado di fattorizzare in modo efficiente qualsiasi numero intero e viceversa.

Note e riferimenti

Appunti

Riferimenti

  1. T. Hayashi, The Bakhshali mauscript, un antico trattato matematico indiano , John Benjamins Publishing Company, Amsterdam (2005).
  2. WE Clarke, The Aryabhatiya of Aryabhata, un'antica opera indiana sulla matematica e l'astronomia , Università di Chicago, Chicago IL (1930).
  3. Joseph Claudel, Introduzione alla scienza degli ingegneri , Dunod, 1863 pagine 86/87
  4. Frazer Jarvis, Radici quadrate per sottrazione [1]
  5. (en) Victor Shoup , Un'introduzione computazionale alla teoria dei numeri e all'algebra , Cambridge University Press,2009, 2 °  ed. , 580  pag. ( ISBN  9780521516440 e 0521516447 , OCLC  277069279 , leggi in linea ) , 12. Reciprocità quadratica e calcolo delle radici quadrate modulari, cap.  5 (“Calcolo delle radici quadrate modulari”) , p.  350-355.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">