Metode de calcul al rădăcinilor pătrate

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 13 ianuarie 2022; verificările necesită 4 modificări .

Metodele rădăcinii pătrate sunt algoritmi de calcul pentru calcularea valorilor aproximative ale rădăcinilor pătrate principale (sau nenegative) (notate de obicei ca , sau ) ale unui număr real. Din punct de vedere aritmetic, aceasta înseamnă că dacă un număr este dat , procedura găsește un număr care, înmulțit cu el însuși, dă . Din punct de vedere algebric, aceasta înseamnă procedura pentru găsirea unei rădăcini nenegative a unei ecuații . Din punct de vedere geometric, aceasta înseamnă construirea unei laturi a unui pătrat cu o zonă dată. ${\sqrt {S})$ ${\sqrt[{2}]{S))$ $S^{1/2}$ $S$ $S$ $x^{2}-S=0$

Orice număr real are două rădăcini [1] . Valoarea principală a rădăcinii pătrate a majorității numerelor este un număr irațional cu o succesiune infinită de cifre zecimale. Ca rezultat, reprezentarea zecimală a oricărei astfel de rădăcini pătrate poate fi calculată doar aproximativ la precizie finită (locuri zecimale). Totuși, chiar dacă luăm rădăcina pătrată a unui număr întreg, astfel încât rezultatul să aibă o reprezentare finită, unele dintre procedurile utilizate pentru calcularea rădăcinii pot returna doar o serie de aproximări cu precizie crescândă.

Reprezentarea fracțională continuă a unui număr real poate fi folosită în locul expansiunii zecimale sau binare, iar această reprezentare are proprietatea că rădăcina pătrată a oricărui număr rațional (care nu este un pătrat perfect) are o perioadă, adică o expansiune periodică similară modului numerele raționale au expansiunea repetitivă a sistemului numeric zecimal.

Cele mai frecvent acceptate metode analitice sunt iterative și constau în doi pași: găsirea unei valori de pornire adecvate și apoi rafinarea iterativă până la atingerea unui anumit criteriu de oprire. Valoarea de început poate fi orice număr, dar dacă este mai aproape de valoarea finală, vor fi necesare mai puține iterații. Cea mai cunoscută astfel de metodă, și chiar mai convenabilă pentru programare, este metoda lui Newton, care se bazează pe calculul derivatei. Mai multe metode, cum ar fi divizarea manuală Horner sau extinderea în serie, nu necesită o valoare inițială. În unele aplicații, este necesar să se găsească rădăcina pătrată întreg , care este rădăcina pătrată rotunjită la cel mai apropiat număr întreg (în acest caz, poate fi utilizată o procedură modificată).

Metoda utilizată depinde de modul în care va fi utilizat rezultatul (adică de cât de precis trebuie să fie rezultatul) și de ce instrumente sunt disponibile. Metodele pot fi împărțite aproximativ în acelea care pot fi realizate mental, care necesită un creion și hârtie, sau cele care sunt implementate ca program și rulează pe computere sau alte dispozitive de calcul. Viteza de convergență (câte iterații vor fi necesare pentru a obține o precizie dată), complexitatea de calcul a operațiilor individuale (cum ar fi diviziunea) sau iterațiile și distribuția erorilor (acuratețea rezultatului) pot fi luate în considerare.

Procedurile pentru găsirea rădăcinilor pătrate (în special, rădăcina lui 2) sunt cunoscute cel puțin încă din timpul Babilonului antic (secolul al XVII-lea î.Hr.). Metoda lui Heron din Egiptul secolului I a fost primul algoritm verificabil pentru calcularea rădăcinii pătrate. Metodele analitice moderne au început să fie dezvoltate după adoptarea cifrelor arabe în Europa de Vest în perioada Renașterii timpurii . În zilele noastre, aproape toate dispozitivele de calcul au o funcție de rădăcină pătrată rapidă și precisă ca un limbaj de programare încorporat, funcție de bibliotecă sau declarație hardware care se bazează pe procedurile descrise mai jos.

Scorul inițial

Mulți algoritmi iterativi de rădăcină pătrată necesită o valoare aleatorie inițială. Această valoare trebuie să fie un număr pozitiv diferit de zero. Trebuie să fie între 1 și , numărul a cărui rădăcină pătrată o căutăm, deoarece rădăcina pătrată trebuie să fie în aceste limite. Dacă valoarea inițială este foarte departe de rădăcină, algoritmul va avea nevoie de mai multe iterații. Dacă începeți cu (sau cu ), se va rezolva despre iterații suplimentare doar pentru a obține ordinea rădăcinii. Prin urmare, este util să aveți o estimare aproximativă a rădăcinii, care poate avea o precizie slabă, dar este ușor de calculat. În general, cu cât estimarea este mai precisă, cu atât convergența este mai rapidă. Pentru metoda lui Newton (numită și metoda babiloniană sau a lui Heron), o valoare inițială puțin mai mare decât rădăcina oferă o convergență mai rapidă decât o valoare inițială mai mică decât rădăcina. $S$ $x_{0}=1$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

În general, estimarea este considerată pe un interval arbitrar în care se știe că conține o rădăcină (cum ar fi ). Obținerea unei estimări mai bune implică fie obținerea unor limite mai înguste pe interval, fie o aproximare funcțională mai bună a . Aceasta din urmă înseamnă, de obicei, utilizarea polinoamelor de ordin superior pentru aproximare, deși nu toate aproximările folosesc polinoame. Metodele comune de estimare sunt scalare, liniare, hiperbolice și logaritmice. Sistemul zecimal este folosit de obicei pentru estimarea mentală sau pe hârtie. Sistemul de numere binare este mai potrivit pentru evaluările computerizate. La evaluare, exponentul și mantisa sunt de obicei tratate separat. $[x_{0},S/x_{0}]$ $f(x).$

Scor zecimal

De obicei, numărul este exprimat în formă exponențială ca , unde , și n este un număr întreg, apoi o estimare a posibilei rădăcini pătrate poate fi , unde . $S$ $a\times 10^{2n)$ $1\leqslant a<100$ ${\sqrt {a}}\times 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Estimări scalare

Metodele scalare împart întreaga gamă în binuri, iar scorul din fiecare bin este reprezentat de un singur număr. Dacă intervalul este tratat ca un singur interval, atunci media aritmetică (5.5) sau media geometrică () sunt estimări acceptabile. Estimările absolute și relative pentru aceste estimări vor diferi. În general, un singur număr va fi foarte inexact. Mai mult estimările precise împart intervalul în două sau mai multe intervale, dar estimarea scalară continuă să fie foarte aproximativă. ${\sqrt {10}}\aprox 3{,}16)\times 10^{n}$

Pentru două intervale împărțite geometric, rădăcina pătrată poate fi estimată ca [2] . ${\sqrt {S}}={\sqrt {a}}\times 10^{n}$

{\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}a<10,\\6\cdot 10^{n}&{ \text{if }}a\geqslant 10.\end{cases}}

Această estimare are o eroare absolută maximă la punctul = 100 și o eroare relativă maximă de 100% la punctul = 1. $4\cdot 10^{n)$

De exemplu, pentru cu o descompunere , scorul va fi . , cu o eroare absolută de 246 și o eroare relativă de aproape 70%. $S=125348$ $12{,}5348\times 10^{4}$ ${\sqrt {S}}\aprox 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Estimare liniară

Cea mai bună estimare și metoda standard este aproximarea liniară a funcției pe un arc mic. Dacă, ca mai sus, exponentul este extras din numărul , iar intervalul este redus la , puteți utiliza o secantă sau o tangentă undeva de-a lungul arcului pentru a aproxima, dar regresia directă a celor mai mici pătrate va fi mai precisă. $y = x^2$ $S$ $[1.100]$

Linia dreaptă, obținută prin metoda celor mai mici pătrate, minimizează distanța medie dintre estimare și valoarea funcției. Ecuația ei este . După transformarea și rotunjirea coeficienților pentru a simplifica calculele, obținem $y=8{,}7x-10$ $x=0{,}115y+1{,}15$

{\sqrt {S}}\aprox (a/10+1{,}2)\cdot 10^{n}

Aceasta este cea mai bună estimare medie care poate fi obținută printr-o încercare de aproximare liniară a funcției în intervalul . Estimarea are o eroare absolută maximă de 1,2 la punctul a=100 și o eroare relativă maximă de 30% la punctele S=1 și 10 [3] . $y=x^2$ $[1.100]$

Pentru a împărți la 10, scădeți unul din exponent sau, la figurat vorbind, mutați virgulă zecimală cu o poziție la stânga. Pentru această formulă, orice constantă adăugată egală cu 1 plus un mic increment oferă o estimare satisfăcătoare, deci nu este nevoie să memorați numărul exact. Aproximarea (rotunjită sau nerotunjită) folosind o linie dreaptă care scade regiunea în termeni de precizie nu dă mai mult de un semn corect. Eroarea relativă este mai mare de 1/2 2 , deci oferă mai puțin de 2 biți de informație. Precizia este sever limitată, deoarece regiunea se întinde pe două ordine de mărime, ceea ce este destul de mare pentru acest tip de estimare. $A$ $[1.100]$

O estimare semnificativ mai bună poate fi obținută folosind o aproximare liniară pe bucăți, adică folosind mai multe segmente care aproximează subarcul arcului original. Cu cât se folosesc mai multe segmente, cu atât este mai bună aproximarea. Cea mai frecventă utilizare a tangentelor. Punctul critic este cum să împărțiți arcul și unde să plasați punctele de atingere. O metodă eficientă de împărțire a arcului de la y=1 la y=100 este geometrică - pentru două intervale, limita intervalului este rădăcina pătrată a intervalului original, 1 * 100, adică și . Pentru trei intervale vor exista rădăcini cubice - , și , și așa mai departe. Pentru două intervale, acesta este un număr foarte convenabil. Este ușor să obțineți linii tangente în punctele de contact și . Ecuațiile lor sunt: și . Inversând ecuațiile, obținem că rădăcinile pătrate sunt egale cu și . Apoi pentru : $[1,{\sqrt[{2}]{100}}]$ $[{\sqrt[{2}]{100)),100]$ $[1,{\sqrt[{3}]{100}}],[{\sqrt[{3}]{100}},({\sqrt[{3}]{100}})^{ 2}]$ $[({\sqrt[{3}]{100)))^{2},100]$ ${\sqrt[{2}]{100}}=10$ $x={\sqrt {1*{\sqrt {10}}}}$ $x={\sqrt {10*{\sqrt {10}}))$ $y=3{,}56x-3{,}16$ $y=11{,}2x-31{,}6$ $x=0{,}28y+0{,}89$ $x=0{,}089y+2{,}8$ $S=a\cdot 10^{2n)$

{\sqrt {S}}\approx {\begin{cases}(0{,}28a+0{,}89)\cdot 10^{n}&{\text{if }}a<10, \\(0{,}089a+2{,}8)\cdot 10^{n}&{\text{if }}a\geqslant 10.\end{cases}}

Valorile absolute maxime sunt în limitele drepte ale intervalelor, la punctele a=10 și 100 și sunt egale cu 0,54 și, respectiv, 1,7. Erorile relative maxime apar la sfârşitul intervalelor, la punctele a=1, 10 şi 100, şi sunt egale cu 17%. 17% sau 0,17. Sunt mai mari decât 1/10, deci metoda oferă o precizie mai mică de o cifră semnificativă.

Estimare hiperbolica

În unele cazuri, estimarea hiperbolică poate fi validă, deoarece hiperbola este, de asemenea, o curbă convexă și poate să se afle de-a lungul arcului Y = x 2 mai bine decât o linie dreaptă. Estimatorul hiperbolic este mai dificil din punct de vedere computațional, deoarece necesită împărțirea cu un număr în virgulă mobilă. O aproximare hiperbolică aproape optimă la x 2 pe interval este . După transformare obținem . Apoi pentru : $[1.100]$ $y=190/(10-x)-20$ $x=-190/(y+20)+10$ $S=a\cdot 10^{2n)$

{\sqrt {S}}\aprox \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}

Diviziunea în virgulă mobilă trebuie să fie precisă până la o zecimală, deoarece toate evaluările oferă această precizie, iar o astfel de împărțire poate fi făcută mental. Estimarea hiperbolică este în medie mai bună decât estimarea scalară sau liniară. Eroarea sa absolută maximă este de 1,58 la punctul 100, iar eroarea sa relativă maximă este de 16,0% la punctul 10. Pentru cel mai rău caz a=10, scorul este 3,67. Dacă începem de la 10 și aplicăm direct iterațiile Newton-Rapson, este nevoie de două iterații, care dau 3,66, înainte de a ajunge la acuratețea estimării hiperbolice. Pentru un caz mai tipic, cum ar fi 75, estimarea hiperbolică este 8,00 și este nevoie de 5 iterații Newton-Rapson începând cu 75 pentru a obține un rezultat mai precis.

Evaluare aritmetică

O metodă similară cu aproximarea liniară pe bucăți, dar care utilizează numai operații aritmetice în loc de ecuații algebrice, folosește tabelul de înmulțire invers - rădăcina pătrată a numerelor între 1 și 100 este undeva între 1 și 10, deci știm că 25 este pătrat exact. (5 × 5) și 36 este un pătrat exact (6 × 6), apoi rădăcina pătrată a unui număr care este mai mare de 25, dar mai mic de 36 începe cu numărul 5. În mod similar, pentru numerele dintre alte pătrate. Această metodă oferă prima cifră corectă, dar acuratețea ei este doar o cifră - prima cifră a rădăcinii pătrate a lui 35, de exemplu, este 5, dar rădăcina lui 35 în sine este aproape egală cu 6.

Este mai bine să împărțiți intervalul dintre două pătrate în jumătate. Deci rădăcina oricărui număr între 25 și jumătate până la 36 (care este 30,5) evaluează la 5, alte numere mai mari de 30,5 până la 36 evaluează la 6 [4] . Procedura necesită foarte puțină aritmetică pentru a găsi mijlocul a două produse din tabel. Iată un tabel cu astfel de numere:

A	cel mai apropiat pătrat	$k={\sqrt {a)}$ EST.
1 la 2,5	1 (= 1 2 )	unu
2,5 până la 6,5	4 (= 2 2 )	2
6,5 până la 12,5	9 (= 3 2 )	3
12,5 până la 20,5	16 (= 4 2 )	patru
20,5 până la 30,5	25 (= 5 2 )	5
30,5 până la 42,5	36 (= 6 2 )	6
42,5 până la 56,5	49 (= 72 )	7
56,5 până la 72,5	64 (= 82 )	opt
72,5 până la 90,5	81 (= 9 2 )	9
90,5 până la 100	100 (= 102 )	zece

Operația finală va fi înmulțirea scorului k cu puterea zecilor împărțită la jumătate, astfel încât pentru , $S=a\cdot 10^{2n)$

{\sqrt {S}}\aproximativ k\cdot 10^{n}

Metoda oferă o precizie semnificativă pentru o cifră, deoarece se rotunjește la cea mai bună cifră.

Metoda poate fi extinsă la 3 cifre semnificative în majoritatea cazurilor prin interpolarea între cele mai apropiate pătrate. Dacă , atunci este aproximativ egal cu k plus o fracție egală cu diferența dintre a și , împărțit la diferența dintre cele două pătrate: $k^{2}\leqslant a<(k+1)^{2}$ ${\sqrt {a}}$ $k^{2}$

{\sqrt {a}}\aprox k+R

Unde

R={\frac {(ak^{2})}{(k+1)^{2}-k^{2)))

Operația finală, ca mai sus, este înmulțirea rezultatului cu puterea lui zece împărțită la jumătate

{\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\aproximativ (k+R)\cdot 10^{n}

Numărul k este cifra zecimală și R este fracția care trebuie convertită în zecimală. O fracție are de obicei o cifră în numărător și una sau două cifre în numitor, astfel încât conversia la o zecimală se poate face mental.

Exemplu: găsiți rădăcina pătrată a lui 75. , deci a este 75 și n este 0. Pe baza tabelului înmulțirii, rădăcina pătrată a mantisei ar trebui să fie 8 cu o fracție deoarece , a , este prea mare. Deci k este 8 , fracția fiind reprezentarea zecimală a lui R . Fracția R are atât un numărător, cât și un numitor. 11/17 este puțin mai mic decât 12/18, care este 2/3 sau 0,67, deci 0,66 este o estimare bună (este în regulă să faci o ghicire aici, deoarece eroarea este mică). Deci valoarea rădăcinii este . √ 75 până la trei cifre semnificative ar fi 8,66, deci un scor la trei cifre semnificative este bun. Nu toate estimările care utilizează această metodă sunt atât de precise, dar sunt destul de apropiate. $75=75\times 10^{2\cdot 0}$ $8\times 8=64$ $9\times 9=81$ $75-k^{2}=11$ $81-k^{2}=17$ $8+0{,}66=8{,}66$

Evaluare binară

Când munca este efectuată în sistem binar (să zicem, într-un procesor de calculator), este exprimată ca , unde , rădăcina pătrată poate fi estimată ca $S$ $a\times 2^{2n)$ $0{,}1_{2}\leqslant a<10_{2}$ ${\sqrt {S}}={\sqrt {a}}\times 2^{n}$

{\sqrt {S}}\aprox (0{,}485+0{,}485\cdot a)\cdot 2^{n}

care este o regresie cu cele mai mici pătrate pe cei 3 biți cei mai semnificativi. are o eroare absolută maximă de 0,0408 la punctul =2 și o eroare relativă maximă de 3,0% la punctul =1. Pentru calcule, o estimare rotunjită este convenabilă (deoarece coeficienții sunt puteri de 2) ${\sqrt {a}}$ $A$ $A$

{\sqrt {S}}\aprox (0{,}5+0{,}5\cdot a)\cdot 2^{n}

[5]

care are o eroare absolută maximă de 0,086 la punctul 2 și o eroare relativă maximă de 6,1% la punctele și . $a=0{,}5$ $a=2{,}0$

Pentru că aproximarea binară dă Deoarece , estimarea dă o eroare absolută de 19 și o eroare relativă de 5,3%. Eroarea relativă este puțin mai mică decât 1/2 4 , deci aproximarea este precisă la 4+ biți. $S=125348=1\;1110\;1001\;1010\;0100_{2}=1{,}1110\;1001\;1010\;0100_{2}\times 2^{16}\,$ ${\sqrt {S}}\aprox (0{,}5+0{,}5\cdot a)\cdot 2^{8}=1{,}0111\;0100\;1101\;0010_ {2}\cdot 1\;0000\;0000_{2}=1{,}456\cdot 256=372{,}8.$ ${\sqrt {125348}}=354{,}0$

O estimare pentru până la 8 biți poate fi obținută prin căutarea în tabel pentru cei mai semnificativi 8 biți , având în vedere că cel mai semnificativ bit este implicit în majoritatea reprezentărilor în virgulă mobilă, iar biții mai puțin semnificativi după 8 biți trebuie rotunjiți. Tabelul conține 256 de octeți de rădăcini pătrate de 8 biți precalculate. De exemplu, pentru indicele 11101101 2 , care este 1,8515625 10 în zecimală , valoarea din tabel este 10101110 2 , care este 1,359375 10 în zecimală , rădăcina pătrată a 1,8515625 10 până la 8 biți zecimale (+ 8 biți). $A$ $A$

Metoda babiloniană

Poate că primul algoritm folosit pentru aproximare este metoda cunoscută sub numele de metoda babiloniană , deși nu există nicio dovadă directă, în afară de inferența ipotetică, că matematicienii babilonieni au folosit această metodă [6] . Metoda este cunoscută și sub numele de metoda lui Heron , după matematicianul grec din secolul I Heron , care a dat prima descriere explicită a metodei în lucrarea sa de 60 de ani Metrica [7] Tehnica de bază este aceea că dacă x este mai mare decât pătratul rădăcină a unui număr real nenegativ S , atunci va fi mai puțin rădăcină și invers. Deci, este rezonabil să ne așteptăm ca media acestor două numere să fie mai aproape de rădăcină (dovada formală a acestui fapt se bazează pe inegalitatea cu privire la media aritmetică, geometrică și armonică , care arată că această medie este întotdeauna mai mare decât pătratul). rădăcină, care asigură convergența). Metoda este echivalentă cu utilizarea metodei lui Newton pentru a rezolva ecuația . ${\sqrt {S})$ ${\tfrac {S}{x}}$ $x^{2}-S=0$

Mai precis, dacă x este o estimare inițială pentru , iar eroarea din estimarea noastră este astfel încât , putem extinde parantezele și obținem ${\sqrt {S})$ $\varepsilon$ $S=(x+\varepsilon )^{2}$

\varepsilon ={\frac {Sx^{2}}{2x+\varepsilon }}\aprox {\frac {Sx^{2}}{2x}},

deoarece .

\varepsilon \ll x

Prin urmare, putem compensa eroarea și putem actualiza vechea noastră estimare

x+\varepsilon \approx x+{\frac {Sx^{2}}{2x}}={\frac {S+x^{2}}{2x}}={\frac {{\frac {S }{x}}+x}{2}}\equiv x_{\text{actualizat}}

Deoarece eroarea calculată nu a fost exactă, va deveni următoarea noastră aproximare. Procesul de actualizare continuă până când ajungem la precizia dorită. Este un algoritm cu convergență pătratică , ceea ce înseamnă că numărul de cifre corecte ale aproximării (în linii mari) se dublează cu fiecare iterație. Funcționează așa:

Începem cu orice valoare inițială pozitivă (cu cât este mai aproape de rădăcina pătrată adevărată a lui S , cu atât mai bine). $x_{0}$
Setăm egal cu media între și (folosim media aritmetică pentru a aproxima media geometrică ). $x_{{n+1}}$ $x_{n}$ ${\tfrac {S}{x_{n}})$
Repetați pasul 2 până ajungem la precizia dorită.

Algoritmul poate fi reprezentat astfel:

x_{0}\aprox {\sqrt {S}),

x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),

{\sqrt {S}}=\lim _{n\la \infty }x_{n}.

Algoritmul funcționează bine și pentru numerele p - adice , dar nu poate fi folosit pentru a identifica rădăcini pătrate reale cu rădăcini pătrate p - adice. Se poate construi, de exemplu, o succesiune de numere raționale obținute prin această metodă care converge către +3 în cazul numerelor reale, dar către -3 în numerele 2-adice.

Exemplu

Pentru a calcula √ S , unde S = 125348, la șase cifre semnificative, utilizați metoda de estimare aproximativă descrisă mai sus

{\begin{aligned}{\begin{array}{rlll}x_{0}&=6\cdot 10^{2}&&=600{,}000\\[0,3em]x_{1} &={\frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)&={\frac {1}{2}}\left (600{,}000+{\frac {125348}{600{,}000}}\right)&=404{,}457\\[0.3em]x_{2}&={\frac {1}{ 2}}\left(x_{1}+{\frac {S}{x_{1}}}\right)&={\frac {1}{2}}\left(404{,}457+{\ frac {125348}{404{,}457}}\right)&=357{,}187\\[0.3em]x_{3}&={\frac {1}{2}}\left(x_{2 }+{\frac {S}{x_{2}}}\right)&={\frac {1}{2}}\left(357{,}187+{\frac {125348}{357{,} 187}}\right)&=354{,}059\\[0.3em]x_{4}&={\frac {1}{2}}\left(x_{3}+{\frac {S}{} x_{3}}}\right)&={\frac {1}{2}}\left(354{,}059+{\frac {125348}{354{,}059}}\right)&=354 {,}045\\[0.3em]x_{5}&={\frac {1}{2}}\left(x_{4}+{\frac {S}{x_{4}}}\right) &={\frac {1}{2}}\left(354{,}045+{\frac {125348}{354{,}045}}\right)&=354{,}045\end{array} }\end{aliniat}}

Prin urmare . ${\sqrt {125348}}\approx 354{,}045$

Convergență

Să presupunem că x 0 > 0 și S > 0. Atunci pentru orice n x n > 0. Eroarea relativă x n este definită ca

\varepsilon _{n}={\frac {x_{n}}{\sqrt {S}}}-1>-1

și apoi

x_{n}={\sqrt {S}}\cdot (1+\varepsilon _{n}).

Acum se poate arăta că

\varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n}})))\geqslant 0.

si in consecinta

\varepsilon _{n+2}\leqslant \min \left\({\frac {\varepsilon _{n+1}^{2)} {2)), {\frac {\varepsilon _{n +1}}{2}}\dreapta\}

și aceasta implică convergență garantată, iar această convergență este pătratică .

Convergență în cel mai rău caz

Dacă folosim o metodă de estimare aproximativă cu metoda babiloniană, atunci cele mai grave cazuri de acuratețe în ordine descrescătoare sunt:

{\begin{aligned}S&=1;&x_{0}&=2;&x_{1}&=1{,}250;&\varepsilon _{1}&=0{,}250.\\ S&=10;&x_{0}&=2;&x_{1}&=3{,}500;&\varepsilon _{1}&<0{,}107.\\S&=10;&x_{0}& =6;&x_{1}&=3{,}833;&\varepsilon _{1}&<0{,}213.\\S&=100;&x_{0}&=6;&x_{1}&= 11{,}333;&\varepsilon_{1}&<0{,}134.\end{aligned}}

Și apoi oricum

\varepsilon _{1}\leqslant 2^{-2}.\,

\varepsilon _{2}<2^{-5}<10^{-1}.\,

\varepsilon _{3}<2^{-11}<10^{-3}.\,

\varepsilon _{4}<2^{-23}<10^{-6}.\,

\varepsilon _{5}<2^{-47}<10^{-14}.\,

\varepsilon _{6}<2^{-95}<10^{-28}.\,

\varepsilon _{7}<2^{-191}<10^{-57}.\,

\varepsilon _{8}<2^{-383}<10^{-115}.\,

Erorile de rotunjire slăbesc convergența. Este recomandat să stocați cel puțin o cifră suplimentară peste precizia dorită x n pentru a minimiza erorile de rotunjire.

Metoda Bakhshali

Această metodă pentru găsirea aproximării rădăcinii pătrate a fost scrisă într-un manuscris indian antic numit manuscrisul Bakhshali . Metoda este echivalentă cu două iterații ale metodei babiloniene cu valoarea inițială x 0 . Astfel, algoritmul este convergent pătratic, ceea ce înseamnă că numărul de semne valide ale aproximării crește de aproximativ patru ori cu fiecare iterație [8] . Reprezentarea algoritmului în notație modernă este următoarea: Calculați , fie x 0 2 aproximarea inițială a rădăcinii S . Iterațiile sunt efectuate secvenţial ${\sqrt {S})$

{\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\b_{n}&=x_{n} +a_{n},\\x_{n+1}&=b_{n}-{\frac {a_{n}^{2}}{2b_{n}}}=(x_{n}+a_{ n})-{\frac {a_{n}^{2}}{2(x_{n}+a_{n})}}.\end{aliniat}}

Aceasta poate fi folosită pentru a construi o aproximare rațională a rădăcinii pătrate, începând cu un număr întreg. Dacă este un număr întreg ales aproape de S și este diferența a cărei valoare absolută este minimizată, atunci prima iterație poate fi scrisă după cum urmează: $x_{0}=N$ $N^2$ $d=SN^{2}$

{\sqrt {S}}\aprox N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N ^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2 }}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)} }.

Metoda lui Bakhshali poate fi generalizată pentru a calcula o rădăcină arbitrară, inclusiv rădăcini fracționale [9] .

Exemplu

Să folosim același exemplu care a fost dat pentru metoda babiloniană. Fie Atunci prima iterație dă $S=125348.$

{\begin{aligned}x_{0}&=600\\a_{1}&={\frac {125348-600^{2}}{2\times 600}}&&=&-195{, }543\\b_{1}&=600+(-195{,}543)&&=&404{,}456\\x_{1}&=404{,}456-{\frac {(-195{, }543)^{2}}{2\times 404{,}456}}&&=&357{,}186\end{aligned}}

În mod similar, a doua iterație dă

{\begin{aligned}a_{2}&={\frac {125348-357{,}186^{2}}{2\times 357{,}186}}&&=&-3{,} 126\\b_{2}&=357{,}186+(-3{,}126)&&=&354{,}060\\x_{2}&=354{,}06-{\frac {(- 3{,}1269)^{2}}{2\times 354{,}06}}&&=&354{,}046\end{aligned}}

Număr după număr

Aceasta este o metodă pentru găsirea secvenţială a fiecărei cifre a rădăcinii pătrate. Metoda este mai lentă decât cea babilonică, dar are unele avantaje

Este mai ușor de calculat manual.
Se știe că fiecare semn găsit al rădăcinii este corect, adică nu va fi schimbat în următoarele iterații.
Dacă reprezentarea rădăcinii pătrate are un număr finit de cifre, algoritmul se termină după ultima cifră găsită. Astfel, poate fi folosit pentru a testa că un anumit număr este un pătrat perfect .
Algoritmul funcționează în orice sistem numeric și, desigur, funcționarea algoritmului depinde de sistemul numeric ales.

Bastoanele lui Napier includ facilitati suplimentare pentru realizarea acestui algoritm. Algoritmul pentru calculul a n-a rădăcină cifră cu cifră este o generalizare a acestei metode.

Principiul de bază

Luați în considerare mai întâi cazul găsirii rădăcinii pătrate a unui număr Z , care este pătratul unui număr de două cifre XY , unde X este cifra zecilor și Y este cifra unilor. Avem:

Z=(10X+Y)^{2}=100X^{2}+20XY+Y^{2}

Mai întâi , să definim valoarea lui X. X este cea mai mare cifră, astfel încât X 2 nu depășește Z , din care ultimele două cifre sunt eliminate.

În următoarea iterație, conectăm o pereche de cifre înmulțind X cu 2 și punând rezultatul în poziția zecilor, apoi încercând să aflăm cu ce Y este egal cu .

Deoarece în cazul nostru răspunsul este rădăcina pătrată exactă, algoritmul se oprește.

Aceeași idee poate fi extinsă pentru a calcula o rădăcină pătrată arbitrară. Imaginați-vă că putem găsi rădăcina pătrată a lui N ca sumă a n numere pozitive astfel încât

N=(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}.

Prin reutilizarea identității

(x+y)^{2}=x^{2}+2xy+y^{2},

partea dreaptă poate fi reprezentată ca

{\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{ 2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dotsb + a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\ \=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_ {3}+\dotsb +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end {aliniat}}

Această expresie ne permite să găsim rădăcina pătrată prin selectarea succesivă a valorilor . Să presupunem că numerele au fost deja selectate, atunci al-lea termen este dat de , unde este aproximarea găsită față de rădăcina pătrată. Acum fiecare nouă selecție trebuie să satisfacă recursiunea $a_{i}$ $a_{1},\ldots ,a_{m-1}$ $Y_{m}=[2P_{m-1}+a_{m}]a_{m},$ $P_{m-1}=\sum _{i=1}^{m-1}a_{i}$ $a.m$

X_{m}=X_{m-1}-Y_{m},

deci pentru toţi la valoarea iniţială Dacă se găseşte exact rădăcina pătrată. Dacă nu, atunci suma oferă o aproximare adecvată a rădăcinii pătrate și va fi o eroare de aproximare. $X_{m}\geqslant 0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ $X_{n}=0,$ $a_{i}$ $X_n$

De exemplu, în zecimală avem

N=(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n })^{2},

unde sunt indicatorii de poziție a cifrelor și coeficienții . La fiecare m-a pas de calcul al rădăcinii pătrate, se găsește aproximativ o rădăcină pătrată. Mărimea și termenii însumați sunt dați de formule ${\displaystyle 10^{ni))$ $a_{i}\in \{0,1,2,\ldots ,9\}$ $P_{m-1}$ $Y_{m}$

P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{ni}=10^{n-m+1}\sum _{i =1}^{m-1}a_{i}\cdot 10^{mi-1},

Y_{m}=[2P_{m-1}+a_{m}\cdot 10^{nm}]a_{m}\cdot 10^{nm}=\left[20\sum _{i= 1}^{m-1}a_{i}\cdot 10^{mi-1}+a_{m}\right]a_{m}\cdot 10^{2(nm)}.

Deoarece indicatorii de poziție au o putere uniformă de 10, trebuie să lucrăm doar cu perechea de cifre cele mai mari din termenul rămas la orice pas al lunei. Secțiunea de mai jos organizează această procedură. $Y_{m}$ $X_{m-1}$

Evident, o metodă similară poate fi folosită pentru a calcula rădăcina pătrată în orice sistem numeric, nu neapărat în zecimală. De exemplu, găsirea rădăcinii pătrate cifră cu cifră în binar este destul de eficientă, deoarece valoarea este căutată în setul mic de cifre {0,1}. Acest lucru face ca calculul să fie mai rapid, deoarece la fiecare pas valoarea este fie egală, fie egală cu . Faptul că există doar două posibilități pentru a face, de asemenea, mai ușoară alegerea unei valori la pasul al m-lea al calculului. Acest lucru se datorează faptului că trebuie doar să verificăm că pentru Dacă această condiție este îndeplinită, luăm ; iar dacă nu, atunci luăm De asemenea faptul că înmulțirea cu 2 se realizează prin deplasarea la stânga ajută la calcule. $a_{i}$ $Y_{m}$ $Y_{m}=0$ $a_{m}=0$ $Y_{m}=2P_{m-1}+1$ $a_{m}=1$ $a.m$ $a.m$ $Y_{m}\leqslant X_{m-1)$ $a_{m}=1.$ $a_{m}=1$ $a_{m}=0.$

Sistem de numere zecimale

Să scriem numărul original în formă zecimală. Numerele sunt scrise într-un mod similar cu împărțirea printr-un algoritm de împărțire lungă și , ca și în diviziunea lungă, rădăcina pătrată va fi scrisă pe linia de sus. Acum să împărțim numerele în perechi, începând cu o virgulă, pe ambele părți ale acesteia. Punctul zecimal al rădăcinii pătrate va fi pe punctul zecimal al pătratului. O cifră rădăcină pătrată este scrisă peste o pereche de cifre rădăcină pătrată.

Începând din poziția extremă din stânga, efectuăm următoarea procedură pentru fiecare pereche de cifre:

Luăm în jos cea mai mare pereche de cifre nefolosite (dacă sunt folosite toate cifrele, scrieți „00”) și le scriem în dreapta restului pasului precedent (nu există rest la primul pas). Cu alte cuvinte, înmulțiți restul cu 100 și adăugați două cifre. Aceasta va fi valoarea curentă a lui c .
Găsiți p , y și x astfel:
- Lăsați -l să facă parte din rădăcina deja găsită , ignorând punctul zecimal. (Pentru primul pas, p = 0.) ${\bold symbol {p}}$
- Determinați cel mai mare număr astfel încât . Vom folosi o variabilă nouă . ${\ simbol aldine {x}}$ $x(20p+x)\leqslant c$ ${\boldsymbol {y}}=x(20p+x)$
  - Rețineți că este doar dublat p cu cifra x atașată la el în dreapta . $20p+x$
  - Rețineți că x poate fi găsit ghicind aleatoriu ce ar trebui să fie c /(20• p ), cu un calcul de probă a lui y , apoi x este luat mai sus sau mai mic în funcție de rezultat.
- Plasăm cifra ca următoarea cifră a rădăcinii, adică deasupra perechii de cifre pătrate care tocmai au fost coborâte. Acum următoarea valoare a lui p se obține din vechea valoare folosind formula . $X$ $p\times 10+x$
Scădeți y din c pentru a forma un nou rest.
Dacă restul este zero și nu mai sunt cifre de mutat în jos, algoritmul se oprește. În caz contrar, revenim la pasul 1 și efectuăm următoarea iterație.

Exemple

Aflați rădăcina pătrată a lui 152,2756.

1 2. 3 4 / \/ 01 52.27 56 01 1*1 <= 1 < 2*2 x = 1 01 y = x*x = 1*1 = 1 00 52 22*2 <= 52 < 23*3 x = 2 00 44 y = (20+x)*x = 22*2 = 44 08 27 243*3 <= 827 < 244*4 x = 3 07 29 y = (240+x)*x = 243*3 = 729 98 56 2464*4 <= 9856 < 2465*5 x = 4 98 56 y = (2460+x)*x = 2464*4 = 9856 00 00 Se oprește algoritmul: Răspuns 12.34

Sistem de numere binar

Această secțiune folosește formalismul secțiunii Calcularea cifrei cu cifre , cu modificări minore, că , și fiecare este egal cu sau . Acum parcurgem toate de la jos la și construim o soluție aproximativă ca suma tuturor pentru care găsim o valoare. Pentru a determina dacă sau este egal cu , luăm . Dacă (adică pătratul aproximării noastre inclusiv nu depășește pătratul inițial), atunci setăm , în caz contrar setăm și . Pentru a evita pătratul la fiecare pas, stocăm diferența și o actualizăm la fiecare iterație setând c . Inițial am stabilit pentru cel mai mare cu . $N^{2}=(a_{n}+\dotsb +a_{0})^{2}$ $a.m$ $2^{m}$ $0$
$2^{m}$ $2^{n}$ $2^0$ $P_{m}=a_{n}+a_{n-1}+\ldots +a_{m)$ $a_{i}$
$a.m$ $2^{m}$ $0$ $P_{m}=P_{m+1}+2^{m)$ $P_{m}^{2}\leqslant N^{2)$ $2^{m}$ $a_{m}=2^{m)$ $a_{m}=0$ $P_{m}=P_{m+1}$
$P_{m)$ $X_{m}=N^{2}-P_{m}^{2)$ $X_{m}=X_{m+1}-Y_{m)$ ${\displaystyle Y_{m}=P_{m}-P_{m+1}=2P_{m+1}a_{m}+a_{m}^{2))$
$a_{n}=P_{n}=2^{n}$ $n$ $(2^{n})^{2}=4^{n}\leqslant N^{2)$

Ca o optimizare suplimentară, stocăm și , doi termeni în cazul în care nu sunt zero, în variabile separate , : $P_{m+1}2^{m+1}$ $(2^{m})^{2}$ $Y_{m}$ $a.m$ $c_{m)$ $d_{m)$

c_{m}=P_{m+1}2^{m+1}

d_{m}=(2^{m})^{2)

Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if } }a_{m}=0\end{cases}}

$c_{m)$ și poate fi actualizat eficient la fiecare pas: $d_{m)$

c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m} +a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{ m}/2&{\text{if }}a_{m}=0\end{cases}}

d_{m-1}={\frac {d_{m}}{4}}

observa asta

c_{-1}=P_{0}2^{0}=P_{0}=N

, care este rezultatul final returnat de funcția de mai jos.

Implementarea algoritmului în limbaj C [10] :

int32_t isqrt(int32_tn) { assert((„valoarea de intrare trebuie să fie nenegativă”, n > 0)); int32_t x = n; // int32_t c = 0; // // începe cu cea mai mare putere de patru <= n

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // Setați al doilea bit cel mai semnificativ la 1. // La fel ca ((nesemnat)INT32_MAX + 1) / 2. în timp ce (d > n) d >>= 2; în timp ce (d != 0) // pentru { dacă (x >= c + d) // dacă , atunci { x -= c + d; // c = (c >> 1) + d; //

d_{n}\dots d_{0)

X_{m+1}\geqslant Y_{m)

a_{m}=2^{m)

X_{m}=X_{m+1}-Y_{m)

c{m-1}=c_{m}/2+d_{m}(a_{=}2^{m})

} altfel c >>= 1; // d >>= 2; //

c_{m-1}=c_{m}/2(a_{m}=0)

d_{m-1}=d_{m}/4

} întoarcere c; //

c_{{-1}}

}

Este posibil să se implementeze un algoritm mai rapid atât în notație binară, cât și în zecimală dacă sunt folosite tabele pentru selecție, adică implementarea principiului utilizării mai multor memorie reduce timpul de execuție [11] .

Identitate exponențială

Calculatoarele de buzunar implementează de obicei programe bune de logaritm exponențial și natural . Calculul rădăcinii pătrate S se face apoi folosind proprietățile logaritmilor ( ) și exponențialelor ( ): $\ln x^{n}=n\ln x$ $e^{\ln x}=x$

{\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.

Numitorul fracției corespunde rădăcinii a n- a. În cazul nostru, numitorul este 2. Aceeași identitate este folosită pentru a calcula rădăcina pătrată folosind tabele de logaritmi sau reguli de calcul .

O metodă iterativă cu două variabile

Această metodă este aplicabilă pentru găsirea rădăcinii pătrate a și converge cel mai bine pentru . Aceasta, totuși, nu este o limitare semnificativă pentru calcularea pe computere, deoarece în reprezentările în virgulă mobilă și în virgulă fixă ale numerelor binare este trivial să se înmulțească cu o putere întreagă de 4 și apoi să se corecteze la puterea dorită de 2 prin schimbarea exponentul sau, respectiv, deplasarea. Astfel, poate fi mutat în . Mai mult, metoda de mai jos nu folosește împărțiri generale, ci doar adunarea, scăderea, înmulțirea și împărțirea cu o putere de doi. Ultima dintre aceste acțiuni este implementată trivial. Dezavantajul metodei este acumularea de erori, spre deosebire de metodele iterative cu o variabilă, cum ar fi Babilonian. $0<S<3\,\!$ $S\aproximativ 1$ $S\,\!$ ${\sqrt {S})$ $S\,\!$ ${\frac {1}{2}}\leqslant S<2$

Etapa inițială a metodei

a_{0}=S\,\!

c_{0}=S-1\,\!

Pași iterativi

a_{n+1}=a_{n}-a_{n}c_{n}/2\,\!

c_{n+1}=c_{n}^{2}(c_{n}-3)/4\,\!

Apoi (pentru ). $a_{n}\rightarrow {\sqrt {S)}$ $c_{n}\rightarrow 0$

Rețineți că convergența și, prin urmare , este pătratică. $c_{n}\,\!$ $a_{n}\,\!$

Dovada metodei este destul de simplă. Mai întâi rescriem definiția iterativă ca $c_{n}\,\!$

1+c_{n+1}=(1+c_{n})(1-c_{n}/2)^{2}\,\!

Acum, din față, se dovedește că

S(1+c_{n})=a_{n}^{2)

și deci convergența către rezultatul dorit este asigurată de convergența către 0, care, la rândul său, decurge din . $a_{n}\,\!$ ${\sqrt {S})$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Această metodă a fost dezvoltată în jurul anului 1950 de M. W. Wilks , D. J. Wheeler și S. Gill [12] pentru a fi utilizată în EDSAC , unul dintre primele calculatoare electronice [13] . Ulterior, metoda a fost generalizată la rădăcini nepătrate [14] .

Metode iterative pentru calcularea reciprocei rădăcinii pătrate a unui număr

Următoarele sunt metode iterative pentru calcularea reciprocei rădăcinii pătrate a lui S , adică . Dacă se găsește o astfel de valoare, o găsim pur și simplu înmulțind: . Aceste iterații folosesc doar înmulțirea și nu folosesc împărțiri. Pentru că metodele sunt mai rapide decât metoda babiloniană . Cu toate acestea, metodele sunt instabile, dacă valoarea inițială nu este aproape de inversul valorii rădăcinii, iterațiile diverge. Prin urmare, poate fi avantajos să repetați mai întâi metoda babiloniană pentru o estimare aproximativă a rădăcinii înainte de a începe să utilizați aceste metode. $1/{\sqrt {S})$ ${\sqrt {S})$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

Aplicând metoda lui Newton la ecuație rezultă o metodă care converge pătratic și utilizează trei înmulțiri la fiecare pas: $(1/x^{2})-S=0$ $x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2})=x_{n}\cdot \left( {\frac {3}{2}}-{\frac {S}{2}}\cdot x_{n}^{2}\right).$
O altă iterație se obține din metoda Halley , care este metoda Householder de ordinul doi. Metoda converge cubic , dar folosește cinci înmulțiri pe iterație: $y_{n}=S\cdot x_{n}^{2}$ $x_{n+1}={\frac {x_{n}}{8}}\cdot (15-y_{n}\cdot (10-3\cdot y_{n}))=x_{n }\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\frac {10}{8}}-{\frac {3}{8}}\cdot y_ {n}\dreapta)\dreapta)$ .
Când lucrați cu numere cu virgulă fixă , înmulțirea cu 3 și împărțirea cu 8 pot fi implementate prin schimburi și adunări. Când se lucrează cu virgulă mobilă, metoda lui Halley poate fi redusă la patru înmulțiri pe iterație prin precalcularea și ajustarea tuturor celorlalte constante pentru a compensa: ${\sqrt {\frac {3}{8}}}S$ $y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2}$ , $x_{n+1}=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\sqrt {\frac {25}{6} }}}-y_{n}\dreapta)\dreapta)$ .

Algoritmul lui Goldschmidt

Unele computere folosesc algoritmul Goldschmidt pentru a calcula și simultan . Algoritmul Goldschmidt găsește mai repede decât iterația Newton-Rapson pe computere cu operații de multiplicare-adunare partajate și fie un procesor în virgulă mobilă pipeline, fie două procesoare independente în virgulă mobilă [15] . ${\sqrt {S})$ $1/{\sqrt {S})$ ${\sqrt {S})$

Prima modalitate de a scrie algoritmul Goldschmidt începe cu

b_{0}=S

Y_{0}\aprox 1/{\sqrt {S)}

(de obicei este folosită căutarea în tabel)

y_{0}=Y_{0}

x_{0}=Sy_{0}

iar iterațiile sunt efectuate

b_{n+1}=b_{n}Y_{n}^{2}

Y_{n+1}=(3-b_{n+1})/2

x_{n+1}=x_{n}Y_{n+1}

y_{n+1}=y_{n}Y_{n+1}

până când este suficient de aproape de 1 sau au fost efectuate un număr fix de iterații. Iterațiile converg către $b_{i}$

\lim _{n\to \infty }x_{n}={\sqrt {S)}

\lim _{n\to \infty }y_{n}=1/{\sqrt {S)}

Rețineți că puteți omite calculul sau , iar dacă ambele sunt dorite, le puteți utiliza la sfârșit în loc să evaluați la fiecare iterație. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

A doua metodă, folosind operațiile combinate de înmulțire-adunare , începe cu

y_{0}\aprox 1/{\sqrt {S)}

(de obicei este folosită căutarea în tabel)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

iar iterațiile sunt efectuate

r_{n}=0{,}5-x_{n}h_{n}

x_{n+1}=x_{n}+x_{n}r_{n)

h_{n+1}=h_{n}+h_{n}r_{n)

până când se apropie suficient de 0 sau se efectuează un număr fix de iterații. Valorile converg spre $r_{i}$

\lim _{n\to \infty }x_{n}={\sqrt {S)}

\lim _{n\to \infty}2h_{n}=1/{\sqrt {S)}

Seria Taylor

Dacă N este o aproximare a , cea mai bună aproximare poate fi găsită folosind seria Taylor a funcției rădăcinii pătrate : ${\sqrt {S})$

{\sqrt {N^{2}+d}}=N\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!}{( 1-2n)n!^{2}4^{n))}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N ^{2))}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d ^{4}}{128N^{8}}}+\cdots \right)

Ordinea de convergență este egală cu numărul de termeni utilizați în serie. Când folosiți doi termeni, metoda este echivalentă cu metoda babiloniană . Când se utilizează trei termeni, fiecare iterație folosește aproape la fel de multe operații cât folosește aproximarea Bakhshali , dar convergența este mai slabă. Prin urmare, această metodă nu este o metodă de calcul deosebit de eficientă. Pentru a maximiza rata de convergență, N ar trebui să fie ales să fie cât mai mic posibil. ${\frac {|d|}{N^{2))}\,$

Expansiunea continuă a fracțiunilor

Iraționalitățile pătratice (numerele de forma , unde a , b și c sunt numere întregi), și în special rădăcinile pătrate ale numerelor întregi, au fracții continuate periodice . Uneori, scopul nu este de a găsi valoarea numerică a rădăcinii pătrate, ci de a o extinde într-o fracție continuă și, prin urmare, aproximarea sa rațională. Fie S un număr pozitiv a cărui rădăcină trebuie găsită. Acum fie a aproximația inițială și r restul, atunci putem scrie Deoarece avem , putem exprima rădăcina pătrată a lui S ca ${\frac {a+{\sqrt {b}}}{c}}$ $S=a^{2}+r.$ $Sa^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r$

{\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.

Aplicând această expresie pentru la numitorul fracției, obținem ${\sqrt {S})$

{\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S})}))))=a+{\frac {r} {2a+{\frac {r}{a+{\sqrt {S)))))).

notație compactă

Numărătorul/numitorul expansiunii continue a fracției (vezi stânga) este greu de notat și, de asemenea, dificil de încadrat în sistemul de formatare a documentelor existent. Din acest motiv, a fost dezvoltată o notație specială pentru a reprezenta în mod compact părțile întregi și periodice ale fracțiilor continue. O astfel de convenție folosește „linia întreruptă” lexicală pentru a reprezenta bara dintre numărător și numitor, ceea ce permite fracției să fie scrisă orizontal în loc de vertical:

{\sqrt {S}}=a+{\frac {r|}{|2a}}+{\frac {r|}{|2a}}+{\frac {r|}{|2a}} +\cdots

Aici, fiecare cursă orizontală (în fracțiune) este reprezentată de trei linii - două verticale și una orizontală, care se despart de . $r$ $2a$

O notație și mai compactă are o formă specială

[a;2a,2a,2a,...]

Pentru fracțiile periodice continuate (care sunt toate rădăcini pătrate), partea care se repetă este listată o singură dată, cu o bară peste partea care se repetă:

[a;{\overline {2a}}]

Pentru √ 2 valoarea este 1, deci reprezentarea va fi $A$

[1;{\overline {2}}]

Urmând această cale, obținem fracția continuă generalizată pentru rădăcina pătrată ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots )))))}$

Primul pas în calcularea unei astfel de fracțiuni pentru a obține o rădăcină pătrată este înlocuirea rădăcinii și alegerea numărului de numitori. De exemplu, în formă canonică este 1 și pentru √ 2 , este 1, deci fracția continuă numerică pentru 3 numitori este $r$ $A$

{\sqrt {2}}\aprox 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}

Pasul 2. Fracția continuă este rulată, câte un numitor, pentru a obține o fracție rațională al cărei numărător și numitor sunt numere întregi. Procesul de pliere arată astfel (luând primii trei numitori):

1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2)}))))=1+{\cfrac {1}{2+{ \cfrac {1}{\frac {5}{2}}}}}

=1+{\cfrac {1}{2+{\cfrac {2}{5)}})=1+{\cfrac {1}{\frac {12}{5)}}

=1+{\cfrac {5}{12}}={\frac {17}{12}}

În cele din urmă (pasul 3), împărțim numărătorul la numitorul fracției raționale pentru a obține o aproximare a rădăcinii:

17\div 12=1{,}42

rotunjite la trei zecimale.

Valoarea reală a rădăcinii √ 2 este 1,41 până la trei cifre semnificative. Eroarea relativă este de 0,17%, deci o fracție rațională este bună până la aproape trei zecimale. Dacă luăm mai mulți numitori, obținem o îmbunătățire consistentă a aproximării - patru numitori dau o fracție , ceea ce oferă aproape 4 cifre de precizie etc. ${\frac {41}{29}}=1{,}4137$

Fracțiile continuate sunt disponibile în tabele pentru cel puțin numere mici și constante bine-cunoscute. Pentru numerele arbitrare în notație zecimală, valorile precalculate sunt cel mai probabil inutile. Următorul tabel de fracții raționale mici, numite convergente , este derivat din fracții continue canonice pentru mai multe constante:

√S _	a continuat împuşcat	~zecimală	Fracții adecvate
√2 _	$[1;{\overline {2}}]$	1,41421	${\frac {3}{2)),{\frac {7}{5}),{\frac {17}{12)),{\frac {41}{29)),{\frac {99}{70}}$
√ 3	$[1;{\overline {1,2}}]$	1,73205	${\frac {2}{1)),{\frac {5}{3}),{\frac {7}{4)),{\frac {19}{11)),{\frac {26}{15)),{\frac {71}{41)),{\frac {97}{56}}$
√5 _	$[2;{\overline {4}}]$	2,23607	${\frac {9}{4)),{\frac {38}{17)),{\frac {161}{72)}$
√ 6	$[2;{\overline {2,4}}]$	2,44949	${\frac {5}{2)),{\frac {22}{9}),{\frac {49}{20)),{\frac {218}{89)}$
√ 10	$[3;{\overline {6}}]$	3,16228	${\frac {19}{6)),{\frac {117}{37}}$
${\sqrt {\pi ))$	$[1;1,3,2,1,1,6...]$	1,77245	${\frac {2}{1)),{\frac {7}{4)),{\frac {16}{9)),{\frac {23}{13)),{\frac {39}{22}}$
${\sqrt {e)}$	$[1;1,1,1,5,1,1...]$	1,64872	${\frac {2}{1)),{\frac {3}{2}),{\frac {5}{3)),{\frac {28}{17)),{\frac {33}{20)),{\frac {61}{37}}$
${\sqrt {\phi ))$	$[1;3,1,2,11,3,7...]$	1,27202	${\frac {4}{3)),{\frac {5}{4)),{\frac {14}{11)}$

Notă: Toate fracțiile aplicabile sunt enumerate până la numitorul 99.

În general, cu cât numitorul unei fracții raționale este mai mare, cu atât aproximarea este mai bună. Se poate demonstra, de asemenea, că tăierea unei fracții continuă are ca rezultat o fracție rațională, cu o mai bună aproximare a rădăcinii oricărei fracții cu un numitor mai mic sau egal cu numitorul acelei fracții. De exemplu, nicio fracție cu un numitor mai mic de 70 nu este la fel de bună ca 99/70 aproximând √2 .

Metoda secvenței lui Luke

Secvența Lucas de primul fel este definită de relația recursivă $U_{n}(P,Q)$

$U_{n}(P,Q)={\begin{cases}0&{\text{if }}n=0\\1&{\text{if }}n=1\\P\cdot U_{ n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)&{\text{otherwise}}\end{cases}}$

iar polinomul său caracteristic este

$x^{2}-P\cdot x+Q=0$

, are un discriminant și rădăcini $D=P^{2}-4Q$

${\begin{matrix}x_{1}={\dfrac {P+{\sqrt {D)}}{2)),&x_{2}={\dfrac {P-{\sqrt {D)} }{2}}\end{matrice}}}$

Toate acestea dau următoarea valoare pozitivă

$\lim _{n\to \infty }{\dfrac {U_{n+1}}{U_{n}}}=x_{1}$

. Deci, dacă vrem să obținem , putem alege și și apoi calcula folosind și pentru valori mari . Cel mai eficient mod de a calcula și − ${\sqrt {a}}$ $P=2$ $Q=1-a$ $x_{1}=1+{\sqrt {a}}$ $U_{n+1}$ $U_{n}$ $n$ $U_{n+1}$ $U_{n}$

${\begin{bmatrix}U_{n}\\U_{n+1}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin {bmatrix}U_{n-1}\\U_{n}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}^{n}\cdot {\begin{bmatrix }} }U_{0}\\U_{1}\end{bmatrix}}$

Rezultat:

${\begin{bmatrix}0&1\\a-1&2\end{bmatrix}}^{n}\cdot {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix} U_{n}\\U_{n+1}\end{bmatrix}},$

si apoi la : $n\la\infty$

${\sqrt {a}}={\frac {U_{n+1}}{U_{n}}}-1$

Aproximații dependente de reprezentarea în virgulă mobilă

Numărul este reprezentat ca un număr în virgulă mobilă ca . Acest format de notație este numit și notație exponențială . Rădăcina pătrată a acestui număr este egală și formule similare pot fi prezentate pentru rădăcini cubice și logaritmi. Acest lucru nu simplifică sarcina, dar dacă este necesară doar o aproximare, atunci este o estimare bună a ordinii mantisei. În plus, înțelegem că unele puteri ale lui p se pot dovedi impare, apoi în loc să lucrăm cu puteri fracționale ale bazei, înmulțim cu ea și scădem una din grad, făcându-l par. Reprezentarea rafinată este convertită în , deci rădăcina pătrată va fi . $m\times b^{p)$ ${\sqrt {m}}\times b^{\tfrac {p}{2}}$ $b^{\tfrac {p}{2)}$ $3141{,}59=3{,}14159{\times }10^{3)$ $31{,}4159{\times }10^{2)$ ${\sqrt {31.4159}}{\times }10^{1}$

Dacă este luată numai partea întreagă a mantisei, aceasta poate lua valori de la 1 la 99 și aceasta poate fi folosită ca index într-un tabel cu 99 de rădăcini precalculate pentru a finaliza estimarea. Un computer care utilizează o bază hexazecimală poate necesita un tabel mai mare, dar folosind baza 2, tabelul va consta doar din trei valori - biții posibili ai părții întregi a reprezentării rafinate a mantisei pot fi 01 (dacă exponentul este par, deci nu există nicio schimbare și rețineți că numărul normalizat în virgulă mobilă are întotdeauna o cifră mare diferită de zero), sau dacă exponentul a fost impar, 10 sau 11, aceștia sunt primii doi biți ai mantisei originale. Apoi 6,25 (= 110,01 în binar) se normalizează la o putere pară, deci perechea de biți mantise este 01, în timp ce 0,625 (= 0,101 în binar) se normalizează la o putere impară, deci este necesară o conversie a numărului la , iar apoi perechea de biți va fi 10. Rețineți că bitul cel mai puțin semnificativ al ordinului este reflectat în bitul cel mai semnificativ al mantisei grupate în perechi. Un exponent par are cel mai puțin semnificativ bit de zero și mantisa quad va începe la zero, în timp ce un exponent impar va avea un 1 în bitul cel mai puțin semnificativ și mantisa quad va începe la 1. Deci, atunci când exponentul este înjumătățit, este echivalent cu deplasarea celui mai puțin semnificativ bit al exponentului la primul bit al mantisei grupate în perechi. $1{,}1001\times 2^{2}$ $1{,}01\times 2^{-1}$ $10{,}1\times 2^{-2}$

Un tabel cu trei elemente poate fi extins pentru a include biți de mantisă suplimentari. Cu toate acestea, în cazul calculatoarelor, în loc să se calculeze interpolarea într-un tabel, este adesea mai bine să se caute o modalitate mai simplă de calcul care să dea aceleași rezultate. Totul depinde acum de detaliile exacte ale formatului de reprezentare a numerelor și de operațiunile care sunt disponibile pentru a obține părți din număr și a lucra cu ele. De exemplu, Fortran conține o funcție EXPONENT(x)pentru obținerea unei diplome. Efortul depus pentru a obține o aproximare inițială bună se plătește prin eliminarea iterațiilor suplimentare ale procesului de rafinare care ar fi necesare în cazul unei aproximări proaste.

Multe computere urmează standardul IEEE în virgulă mobilă (sau o reprezentare destul de apropiată) și o aproximare foarte rapidă a rădăcinii pătrate poate fi obținută ca punct de plecare pentru metoda lui Newton. Tehnica pentru această aproximare provine din faptul că formatul numărului flotant (baza doi) aproximează logaritmul de bază 2. Adică $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$

Deci, pentru un număr în virgulă mobilă IEEE pe 32 de biți (în care exponentul are un offset de 127 [16] ), puteți obține un logaritm aproximativ interpretând numărul ca un întreg de 32 de biți, înmulțindu-l cu și scăzând offset-ul 127, adică $2^{-23}$

x_{\text{int}}\cdot 2^{-23}-127\aprox \log _{2}(x).

De exemplu, numărul 1,0 în hexazecimal este 0x3F800000, care poate fi reprezentat ca atunci când este văzut ca un întreg. Folosind formula de mai sus, veți obține așa cum vă așteptați de la . În mod similar, veți obține 0,5 din 1,5 (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ $\log _{2}(1{,}0)$

Pentru a obține rădăcina pătrată, împărțiți logaritmul la 2 și convertiți rezultatul înapoi. Programul de mai jos demonstrează ideea. Rețineți că bitul cel mai puțin semnificativ al exponentului este tradus în mod deliberat în mantise. O modalitate de a justifica pașii acestui program, presupunând că acesta este decalajul gradului și este numărul de biți stocați în mantise, este de a demonstra $b$ $n$

(((x_{\text{int}}/2^{n}-b)/2)+b)\cdot 2^{n}=(x_{\text{int}}-2^{ n})/2+((b+1)/2)\cdot 2^{n}.

/* Presupunem că numărul flotant este în format IEEE 754 */ #include <stdint.h> float sqrt_approx ( float z ) { unire { float f ; uint32_t i ; } val = { z }; /* Convertiți tipul fără a schimba reprezentarea biților */ /* * Demonstrați că * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * unde * b = offset de putere * m = numărul de biți în mantise */ val . i -= 1 << 23 ; /* Scăderea 2^m. */ val . i >>= 1 ; /* Împărțiți la 2. */ val . i += 1 << 29 ; /* Adăugați ((b + 1) / 2) * 2^m. */ return val . f ; /* Interpretați din nou ca float */ }

Cele trei operații aritmetice care formează miezul funcției pot fi reprezentate într-o singură linie. Se poate adăuga o rafinare suplimentară pentru a reduce eroarea relativă maximă. Astfel, cele trei operații, fără a include reducerea la real, pot fi rescrise ca

val . i = ( 1 << 29 ) + ( val . i >> 1 ) - ( 1 << 22 ) + a ;

unde a este un offset pentru a reduce erorile de aproximare. De exemplu, cu a = 0 rezultatele sunt exacte pentru puterile pare ale lui 2 (ex. 1,0), dar pentru alte numere rezultatul va fi oarecum mare (ex. 1,5 pentru 2,0 în loc de 1,414... cu o eroare de 6%). Pentru a = −0x4B0D2, eroarea relativă maximă este redusă la ±3,5%.

Dacă aproximarea trebuie utilizată ca valoare inițială pentru metoda lui Newton în ecuație , atunci este de preferat forma inversă prezentată în secțiunea următoare. $(1/x^{2})-S=0$

Reciproca rădăcinii pătrate

O variantă a procedurii de mai sus este prezentată mai jos și poate fi utilizată pentru a calcula inversul rădăcinii pătrate, adică . Această variantă a fost scrisă de Greg Walsh. Aproximația deplasării dă o eroare relativă mai mică de 4% și eroarea este redusă la 0,15% după o iterație a metodei lui Newton [17] . În grafica computerizată, aceasta este o modalitate foarte eficientă de a normaliza un vector. $x^{-{1 \over 2}}$

float invSqrt ( float x ) { float xhalf = 0,5f * x ; unire { float x ; int i ; } u ; tu . x = x ; tu . i = 0x5f375a86 - ( u . i >> 1 ); /* Următoarea linie poate fi repetată de un număr arbitrar de ori pentru a crește precizia */ tu . x = u . x * ( 1,5f - xjumătate * u . x * u . x ); întoarce- te . x ; }

Unele VLSI implementează găsirea reciprocei rădăcinii pătrate folosind o estimare polinomială urmată de iterația Goldschmidt [18] .

Rădăcina unui număr negativ sau complex

Dacă , atunci rădăcina sa principală este egală cu $S<0$

{\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.

Dacă , unde a și b sunt numere reale și , atunci rădăcina sa principală este egală cu $S=a+bi$ $b\neq 0$

{\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2))}\,\,i\,.

Acest lucru poate fi verificat prin pătrat [19] [20] . Aici

\vert S\vert ={\sqrt {a^{2}+b^{2)})

este modulul numărului S . Rădăcina principală a unui număr complex este definită ca o rădăcină cu o parte reală nenegativă.

Vezi și

Algoritm alfa max plus beta min
rădăcină pătrată întreagă

Note

↑ Pe lângă rădăcina principală, există o rădăcină pătrată negativă egală în valoare absolută cu rădăcina principală, dar cu semnul opus, cu excepția cazului zero, când există două rădăcini zero identice.
↑ Factorii doi și șase sunt utilizați deoarece aproximează media geometrică a valorilor posibile inferioare și superioare cu un număr dat de cifre: și . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\aproximativ 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\aproximativ 5{,}62\,$
↑ Estimarea neronunjită are o eroare absolută maximă de 2,65 la punctul 100 și o eroare relativă maximă de 26,5% la punctele y=1, 10 și 100
↑ Dacă numărul se află exact la jumătatea distanței dintre două pătrate, cum ar fi 30,5, luați numărul mai mare, care în cazul nostru este 6
↑ Aceasta este ecuația dreptei tangente la y=x 2 în punctul y=1.
↑ Fowler și Robson 1998 , p. 376.
↑ Heath, 1921 , p. 323–324.
↑ Bailey, Borwein, 2012 , p. 646–657.
↑ Reducerea la manuscrisul Bakhshali . Blog Simply Curious (5 iunie 2018). Preluat la 21 decembrie 2020. Arhivat din original la 26 octombrie 2020. (nedefinit)
↑ Rădăcină pătrată întreagă rapidă de dl. Algoritmul abac al lui Woo (arhivat)
↑ Funcția Integer Square Root . Preluat la 30 decembrie 2021. Arhivat din original la 30 septembrie 2007. (nedefinit)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , p. 142-143, 1958.
↑ Markstein, Peter (noiembrie 2004). Divizia de software și rădăcină pătrată folosind algoritmii Goldschmidt (PDF) . A 6-a Conferință despre numere reale și calculatoare . Dagstuhl , Germania. CiteSeerX 10.1.1.85.9648 . Arhivat (PDF) din original pe 2022-04-28 . Accesat 2021-12-30 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ 127 se adaugă la exponentul numărului, ceea ce permite ca exponentul să fie interpretat ca un număr nesemnat.
↑ Fast Inverse Square Root Arhivat 6 februarie 2009 la Wayback Machine de Chris Lomont
↑ „Calcul cu dublă precizie de mare viteză a rădăcinii reciproce, diviziunii, pătratei și rădăcinii pătrate inverse” de José-Alejandro Piñeiro și Javier Díaz Bruguera 2002 (rezumat)
↑ Abramowitz, Stegun, 1964 , p. 17.
↑ Cooke, 2008 , p. 59.

Literatură

David Fowler, Eleanor Robson. Aproximații cu rădăcină pătrată în vechea matematică babiloniană: YBC 7289 în context // Historia Mathematica. - 1998. - T. 25 , nr. 4 . - doi : 10.1006/hmat.1998.2209 .
Thomas Little Heath . O istorie a matematicii grecești. - Oxford: Clarendon Press, 1921. - V. 2. - S. 323-324.
David Bailey, Jonathan Borwein. Ancient Indian Square Roots: An Exercise in Forensic Paleo-Mathematics // American Mathematical Monthly. - 2012. - T. 119 , nr. 8 .
Miltonn Abramowitz, Irene A. Stegun. Secțiunea 3.7.26 // Manual de funcții matematice cu formule, grafice și tabele matematice . - Publicațiile Courier Dover, 1964. - P. 17. - ISBN 978-0-486-61272-0 .
JC Gower. O notă despre o metodă iterativă pentru extragerea rădăcinilor // The Computer Journal. - 1958. - T. 1 1 , nr. 3 .
M. Campbell-Kelly. Originea calculului // Scientific American. - 2009. - Septembrie.
Roger Cooke. Algebra clasică: natura, originile și utilizările sale . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. Pregătirea programelor pentru un computer digital electronic. - Addison-Wesley, 1951.

Metode de calcul al rădăcinilor pătrate

Scorul inițial

Scor zecimal

Evaluare binară

Metoda babiloniană

Exemplu

Convergență

Metoda Bakhshali

Exemplu

Număr după număr

Principiul de bază

Sistem de numere zecimale

Sistem de numere binar

Identitate exponențială

O metodă iterativă cu două variabile

Metode iterative pentru calcularea reciprocei rădăcinii pătrate a unui număr

Algoritmul lui Goldschmidt

Seria Taylor

Expansiunea continuă a fracțiunilor

Metoda secvenței lui Luke

Aproximații dependente de reprezentarea în virgulă mobilă

Reciproca rădăcinii pătrate

Rădăcina unui număr negativ sau complex

Vezi și

Note

Literatură

Referințe Weisstein, Eric W. Algoritmi rădăcină pătrată (engleză) pe site-ul Wolfram MathWorld .