Somma pitagorica

In matematica la somma di Pitagora di due numeri $a$ e $b$ è il numero $\sqrt un 2 + b 2$ , che può essere visto come la lunghezza della dell'ipotenusa di un triangolo rettangolo di lati di lunghezza $a$ e $b$ dal teorema di Pitagora . L'operazione associata, l'aggiunta pitagorica, è commutativa e associativa . La somma pitagorica può essere calcolata in modo efficiente su una macchina da un algoritmo fornito da Moler e Morisson, che risulta essere un'applicazione del metodo di Halley .

Definizione e proprietà

Se indichiamo con $a \oplus b = \sqrt a 2 + b 2$ , l'operazione così definita è commutativa e associativa, e:

a 1 \oplus a 2 \oplus\dots \oplus a n = \sqrt a 1 2 + a 2 2 +\dots + a n 2

Calcolo numerico

La somma delle lunghezze di Pitagora un e b su entrambi i lati del angolo retto di un triangolo rettangolo è la lunghezza dell'ipotenusa secondo il teorema di Pitagora . Il calcolo di questo dà la norma euclidea nella dimensione 2, e più in generale in uno spazio di qualsiasi dimensione . Permette così di calcolare il modulo di un numero complesso , o di passare da una rappresentazione cartesiana a una polare .

Il calcolo può procedere squadratura un e b allora la radice quadrata della somma, ma se una o b assumono valori molto grandi, il calcolo intermedio di un 2 o b 2 su un computer può creare un errore di overflow o cedimenti .

Tipicamente, il numero più grande rappresentabile in singola precisione è dell'ordine di 3 × 10 38 ; quindi, se una o b è maggiore di 2 × 10 19 , il software dichiarare il risultato (overflow) "infinito", anche se il risultato finale è rappresentabile (per esempio se l'altro tratto è piccola in valore assoluto); per esempio ,. Con doppia precisione la rappresentanza , il più grande numero rappresentabile è pari a circa 1,8 × 10.308 , quindi il risultato sarà dichiarato "infinito", se una o b è maggiore di 1.3 × 10.154 . ${\ displaystyle {\ sqrt {(2 \ times 10 ^ {19}) ^ {2} + 1 ^ {2}}} \ simeq 2 \ times 10 ^ {19}}$

Al contrario, il valore assoluto più piccolo rappresentabile è circa 1,1 × 10 −38 in precisione singola e 2,2 × 10 −308 in doppia precisione. Pertanto, in precisione singola, il calcolo per a = b = 2 × 10 −38 darà 0 (errore di underflow), mentre il valore atteso è rappresentabile e vale circa 1,4 × 10 −38 .

Il metodo di Moler e Morrison, un metodo cubico iterativo (otteniamo circa 3 cifre significative ad ogni iterazione), derivato dal metodo di Halley, evita questo problema.

Questo metodo consiste nel ridurre primo a $un \geq b$ , quindi sostituendo $un$ e $b$ , da due positivi numeri p e q con $p > un \geq b > q$ avente la stessa somma di Pitagora, vale a dire che $\sqrt a 2 + b 2 = \sqrt p 2 + q 2$ . Ad ogni passo, l'algoritmo diminuisce il valore di q e aumenta il valore di p mantenendo la somma pitagorica. Quando il valore di q diventa molto piccolo, abbiamo quindi $\sqrt a 2 + b 2 \approx p$ . In concreto, l'algoritmo è scritto in pseudo-codice:

fonction [résultat] = somme_pythagoricienne(a, b) // initialisation p ← max(|a|, |b|) q ← min(|a|, |b|) // Calcul tant que (q a une valeur significative) faire r ← (q/p)^2 s ← r/(4 + r) p ← p + 2*s*p q ← s*q fin de boucle résultat ← p fin de fonction

Per un calcolo della norma euclidea in uno spazio di dimensione maggiore di 2, è sufficiente calcolare successivamente la somma pitagorica. Per un vettore X di dimensione n :

fonction [résultat] = norme2(X) // initialisation n ← dimension(X) s ← 0 // Calcul pour i allant de 1 à n s ← somme_pythagoricienne(s, X(i)) fin de boucle résultat ← s fin de fonction

Bibliografia

(en) Cleve Moler e Donald Morrison , " Sostituire radici quadrate con somme pitagoriche " , IBM Journal of Research and Development , vol. 27, n o 6,1983, p. 577–581 ( DOI 10.1147 / rd.276.0577 , leggi online ).
(en) Augustin A. Dubrulle , " Una classe di metodi numerici per il calcolo delle somme pitagoriche " , IBM Journal of Research and Development , vol. 27, n o 6,1983, p. 582–589 ( DOI 10.1147 / rd.276.0582 , leggi online ).