Această intrare este dedicată numeroaselor metode care au fost utilizate pentru a calcula rădăcinile pătrate ale numerelor reale pozitive, sau mai bine zis, pentru a calcula rădăcinile pătrate principale ale numerelor raționale.
Note istorice
Primii care s-au ocupat de problema extragerii rădăcinii pătrate a unui număr au fost babilonienii. Aceștia, printre primii care au folosit un sistem de numerotare pozițională, au dezvoltat o procedură pentru extragerea rădăcinii pătrate, care este adesea atribuită matematicienilor de mai târziu, precum Archita (428 - 365 î.Hr.) sau Eroului Alexandriei (care a trăit între Secolele I și II d.Hr.) sau către Newton .
Babilonienii obținuseră o valoare de {\ displaystyle {\ sqrt {2}}} egal cu 1.414222 cu o eroare de aproximativ 0,000008 din valoarea reală. Există puține informații biografice despre Hero of Alexandria, un matematician și om de știință grec. S-a ocupat de mecanică, matematică și fizică. Lui îi datorăm formula (numită exact formula lui Heron) prin care să calculăm aria oricărui triunghi, notăm laturile sale. El a studiat metode aproximative pentru rezolvarea problemelor de măsurare, atât în geometrie, cât și în geodezie și a inventat o metodă pentru aproximarea rădăcinilor pătrate și cubice ale numerelor care nu sunt pătrate sau cuburi perfecte și exact metoda de aproximare a rădăcinilor pătrate pe care vrem să le ocupăm. cu.
Metoda babiloniană
Având o valoare {\ displaystyle \ alpha> 0} , un algoritm pentru aproximare {\ displaystyle {\ sqrt {\ alpha}}} folosit în mod obișnuit este cunoscut sub numele de metoda babiloniană și exploatează aceleași principii codificate atunci în metoda lui Newton . Această metodă funcționează după cum urmează:
- Poni {\ displaystyle n = 1} și începe cu o valoare pozitivă arbitrară {\ displaystyle x_ {n}} (cu cât este mai aproape de rădăcină, cu atât este mai bună convergența algoritmului)
- a inlocui {\ displaystyle x_ {n}} cu media de {\ displaystyle x_ {n}} Și{\ displaystyle \ alpha / x_ {n}}
- creșteți nu mergeți la punctul 2
Acest algoritm poate fi reprezentat de
- {\ displaystyle x_ {n + 1} = {\ frac {1} {2}} \ left (x_ {n} + {\ frac {\ alpha} {x_ {n}}} \ right)}
din care derivă {\ displaystyle \ lim _ {n \ to \ infty} x_ {n} = {\ sqrt {\ alpha}}} .
Interpretarea geometrică
Având un număr {\ displaystyle \ alpha} pozitiv, rădăcina sa pătrată poate fi văzută ca partea unui pătrat a cărui suprafață este adecvată {\ displaystyle \ alpha} la fel. Ideea este să folosiți dreptunghiuri care au aceeași zonă {\ displaystyle \ alpha} a pătratului să ajungă prin aproximări succesive pentru a avea exact pătratul pe care îl căutăm.
Deci, să ne imaginăm începând cu o anumită valoare {\ displaystyle x_ {1}} pentru partea dreptunghiului nostru: cealaltă parte va măsura{\ displaystyle {\ frac {\ alpha} {x_ {1}}}} . Luând media acestor două valori
- {\ displaystyle {\ frac {1} {2}} \ left (x_ {1} + {\ frac {\ alpha} {x_ {1}}} \ right),}
avem două posibilități:
- media este egală cu {\ displaystyle x_ {1}} , așa că am găsit deja {\ displaystyle {\ sqrt {\ alpha}}} ;
- media este diferită de {\ displaystyle x_ {1}} .
În acest al doilea caz numim această valoare medie {\ displaystyle x_ {2}} și procedați în același mod ca pentru cel folosit {\ displaystyle x_ {1}} : calculăm valoarea cealaltă parte a dreptunghiului de zonă {\ displaystyle \ alpha} și lateral {\ displaystyle x_ {2}} , obținem o nouă valoare medie {\ displaystyle x_ {3}} si asa mai departe.
Vom da naștere unei succesiuni de dreptunghiuri de echestezie ale căror laturi vor fi mai apropiate în lungime la fiecare pas, obținând la limită un pătrat și deci valoarea corectă a rădăcinii lui {\ displaystyle \ alpha} . Metoda oferă un răspuns corect în număr finit de pași, pentru orice eventualitate {\ displaystyle \ alpha} este un pătrat perfect.
Demonstrație de convergență
Pentru a demonstra corectitudinea acestei metode, luăm secvența încercând să evaluăm dimensiunea elementului {\ displaystyle x_ {n}} în ceea ce privește {\ displaystyle {\ sqrt {\ alpha}}} : ceea ce putem spune imediat este că atât termenii succesiunii cât și {\ displaystyle \ alpha} sunt numere reale pozitive . Al n-lea termen al secvenței este:
- {\ displaystyle x_ {n} = {\ frac {1} {2}} \ left (x_ {n-1} + {\ frac {\ alpha} {x_ {n-1}}} \ right) = {\ frac {\ sqrt {\ alpha}} {2}} \ left ({\ frac {x_ {n-1}} {\ sqrt {\ alpha}}} + {\ frac {\ sqrt {\ alpha}} {x_ {n-1}}} \ dreapta).}
Al doilea factor al celei de-a doua egalități este de tipul
- {\ displaystyle f (x) = {\ frac {x} {\ sqrt {\ alpha}}} + {\ frac {\ sqrt {\ alpha}} {x}} \ qquad (x> 0)}
funcție care are un punct minim absolut în primul cadran pentru {\ displaystyle x = {\ sqrt {\ alpha}}} în care este egală cu 2. În special, valoarea 2 este asumată de funcție numai atunci când {\ displaystyle x = {\ sqrt {\ alpha}}} , în timp ce crește în altă parte. Din cele spuse rezultă că
- {\ displaystyle x_ {n} \ geq {\ frac {\ sqrt {\ alpha}} {2}} \ cdot 2 = {\ sqrt {\ alpha}}}
și asta înseamnă că, luată o valoare inițială {\ displaystyle x_ {0}> 0} , toate celelalte valori din {\ displaystyle x_ {1}} inclusiv înainte nu poate fi mai mic de {\ displaystyle {\ sqrt {\ alpha}}} . Din aceeași formulă rezultă că
- {\ displaystyle {\ frac {\ alpha} {x_ {n}}} \ leq {\ sqrt {\ alpha}} \ leq x_ {n}.}
Deci, luând formula pentru {\ displaystyle x_ {n + 1}} , primesti
- {\ displaystyle x_ {n + 1} = {\ frac {1} {2}} \ left (x_ {n} + {\ frac {\ alpha} {x_ {n}}} \ right) \ leq {\ frac {1} {2}} \ left (x_ {n} + x_ {n} \ right) = x_ {n}.}
Aceasta implică faptul că secvența este în scădere și este inclusă între valori {\ displaystyle {\ sqrt {\ alpha}}} Și {\ displaystyle x_ {1}} , deci este limitat. Deoarece o secvență monotonă converge dacă și numai dacă este delimitată, există o valoare {\ displaystyle x \ geq {\ sqrt {\ alpha}}} la care converge succesiunea noastră.
Să evaluăm acum abaterea termenului (n + 1) -al de la {\ displaystyle {\ sqrt {\ alpha}}} :
- {\ displaystyle {\ begin {align} x_ {n + 1} - {\ sqrt {\ alpha}} & = x_ {n + 1} -x_ {n} + x_ {n} - {\ sqrt {\ alpha} } = \\ & = {\ frac {1} {2}} \ left ({\ frac {\ alpha} {x_ {n}}} - x_ {n} \ right) + x_ {n} - {\ sqrt {\ alpha}} \ leq {\ frac {1} {2}} \ left ({\ sqrt {\ alpha}} - x_ {n} \ right) + x_ {n} - {\ sqrt {\ alpha}} = {\ frac {x_ {n} - {\ sqrt {\ alpha}}} {2}}. \ end {align}}}
Aplicând recursiv următoarea inegalitate:
- {\ displaystyle x_ {n + 1} - {\ sqrt {\ alpha}} \ leq {\ frac {x_ {n} - {\ sqrt {\ alpha}}} {2}},}
obții asta pentru fiecare {\ displaystyle \ varepsilon> 0} există o valoare {\ displaystyle N} astfel încât pentru fiecare {\ displaystyle n \ geq N}
- {\ displaystyle x_ {n + 1} - {\ sqrt {\ alpha}} \ leq {\ frac {x_ {1} - {\ sqrt {\ alpha}}} {2 ^ {n}}} <\ varepsilon}
și cu aceasta se demonstrează convergența secvenței a {\ displaystyle {\ sqrt {\ alpha}}} . Acest lucru sugerează, de asemenea, că convergența este foarte rapidă: pentru fiecare pas, distanța de la valoarea reală este cel puțin înjumătățită, făcând scăderea exponențială .
Viteza convergenței
Pentru a înțelege mai bine viteza de convergență a acestei metode de calcul, să spunem {\ displaystyle \ varepsilon _ {n} = x_ {n} - {\ sqrt {\ alpha}}} . Prin exploatarea relației recursive oferite de metoda însăși, avem:
- {\ displaystyle \ varepsilon _ {n + 1} = x_ {n + 1} - {\ sqrt {\ alpha}} = {\ frac {1} {2}} \ left (x_ {n} + {\ frac { \ alpha} {x_ {n}}} \ right) - {\ sqrt {\ alpha}} = {\ frac {{\ varepsilon _ {n}} ^ {2}} {2x_ {n}}}.}
De vreme ce s-a dovedit că pentru fiecare termen al secvenței deține {\ displaystyle x_ {n}> {\ sqrt {\ alpha}}} , asa de
- {\ displaystyle \ varepsilon _ {n + 1} <{\ frac {{\ varepsilon _ {n}} ^ {2}} {2 {\ sqrt {\ alpha}}}}.
Acum, aplicând relația de recurență înapoi și plasând pentru simplitatea notării {\ displaystyle \ beta = 2 {\ sqrt {\ alpha}}} , poti sa o obtii
- {\ displaystyle \ varepsilon _ {n + 1} <{\ frac {{\ varepsilon _ {n}} ^ {2}} {\ beta}} <{\ frac {1} {\ beta}} \ left ({ \ frac {\ varepsilon _ {n-1} ^ {2}} {\ beta}} \ right) ^ {2} = \ beta \ left ({\ frac {\ varepsilon _ {n-1}} {\ beta }} \ right) ^ {4} <\ cdots <\ beta \ left ({\ frac {\ varepsilon _ {nk}} {\ beta}} \ right) ^ {2 ^ {k + 1}}}
unde este {\ displaystyle k} este un număr întreg între 2 și {\ displaystyle n-1} . Când, în special, există {\ displaystyle k = n-1} , rezultă că
- {\ displaystyle \ varepsilon _ {n + 1} <\ beta \ left ({\ frac {\ varepsilon _ {1}} {\ beta}} \ right) ^ {2 ^ {n}}.}
Această ultimă relație demonstrează că metoda babiloniană este excelentă pentru calcularea rădăcinii pătrate, deoarece convergența sa este foarte rapidă. De fapt, este suficient să luăm cum {\ displaystyle x_ {1}} o valoare astfel încât
- {\ displaystyle x_ {1} <3 {\ sqrt {\ alpha}}}
pentru a face valoarea între paranteze rotunde mai mică de 1 și pentru a face totul să scadă extrem de repede (exponențialul unui exponențial). Această alegere a {\ displaystyle x_ {1}} se poate face întotdeauna pentru că ne găsim lucrând cu o succesiune descrescătoare.
Exemplu de utilizare
De exemplu, deoarece rădăcina pătrată a lui 2 trebuie să fie între 1 și 2, estimăm că este în jur de 1,5. Aplicând în mod repetat formula obținem următoarele valori:
- {\ displaystyle x_ {0} \, = \, 1,5}
- {\ displaystyle x_ {1} = {\ frac {1} {2}} \ left (1,5 + {\ frac {2} {1,5}} \ right) = 1,416667}
- {\ displaystyle x_ {2} = {\ frac {1} {2}} \ left (1.416667 + {\ frac {2} {1.416667}} \ right) = 1.414216}
- {\ displaystyle x_ {3} = {\ frac {1} {2}} \ left (1.414216 + {\ frac {2} {1.414216}} \ right) = 1.414214}
- {\ displaystyle x_ {4} = {\ frac {1} {2}} \ left (1.414214 + {\ frac {2} {1.414214}} \ right) = 1.414214}
- {\ displaystyle \ cdots} ;
în acest fel în al patrulea pas avem valoarea rădăcinii pătrate a 2 corectată la a șasea zecimală.
Acest algoritm funcționează la fel de bine pentru numerele p-adic , dar nu poate fi utilizat pentru a identifica rădăcini pătrate reale cu indexul rădăcinii p-a. Referindu-ne la această metodă, este ușor, de exemplu, să construim o succesiune de numere raționale care converg către {\ displaystyle +3} în real, dar a {\ displaystyle -3} în 2-adici.
Aproximare Bakhshali
Metoda Bakhshali este un alt mod de a găsi o aproximare a rădăcinii pătrate a unui număr care a fost descris într-un manuscris antic cu numele de Bakhshali Manuscript deoarece a fost descoperit în 1881 lângă satul Bakhshali (sau Bakhshalai) în cătunul Yusufzai din districtul Peshawar (acum parte a Pakistanului ). Textul a fost scris în limba Sarada pe scoarță de mesteacăn .
Aproximarea Bakhshali a rădăcinii pătrate se obține aplicând de două ori aproximarea simplă.
Cu notațiile anterioare pe care le introducem {\ displaystyle P \ ,: = \, {\ frac {d} {2N}} ~~ {\ mbox {e}} ~~ A: = N + P}
{\ displaystyle {\ sqrt {N ^ {2} + d}} \ approx A - {\ frac {P ^ {2}} {2A}}}
Dezvoltând ecuația devine:
- {\ displaystyle {\ sqrt {N ^ {2} + d}} \ approx N + {\ frac {d} {2 \, N}} - {\ frac {d ^ {2}} {8 \, N ^ {3} +4 \, N \, d}}}
Exemplu de aproximare Bakhshali
Descoperiri {\ displaystyle {\ sqrt {9,2345}}}
- Folosim {\ displaystyle \, N = 3 ~~ {\ mbox {e}} ~~ d = 9.2345-3 ^ {2} = 0.2345}
- {\ displaystyle {\ sqrt {3 ^ {2} + d}} \ approx 3 + {\ frac {d} {6}} - {\ frac {d ^ {2}} {216 + 12 \, d}} }
- {\ displaystyle {\ sqrt {3 ^ {2} +0.2345}} \ approx 3 + {\ frac {0.2345} {6}} - {\ frac {0.2345 ^ {2}} {216+ 12 \ cdot 0,2345 }}}
- {\ displaystyle {\ sqrt {3 ^ {2} +0.2345}} \ approx 3 + 0.039083 - {\ frac {0.055} {216 + 2.814}}}
- {\ displaystyle {\ sqrt {3 ^ {2} +0.2345}} \ approx 3 + 0.039083-0.000251}
- {\ displaystyle {\ sqrt {3 ^ {2} +0.2345}} \ aproximativ 3.038832}
Calculul rădăcinii pătrate a unui întreg: algoritmul lui Bombelli
Acest algoritm se aplică notației zecimale (și mai general unei scrieri de poziție în orice bază b ) de numere întregi și furnizează partea întreagă a rădăcinii și orice rest.
Pentru acest calcul începem prin a distinge în scrierea din baza 10 a grupurilor de înrădăcinare a două cifre consecutive începând de la grupul format din cifra unităților și cea a zecilor; grupul celor mai importante cifre poate fi redus la o cifră (ca în exemplul următor). Este convenabil să scrieți rezultatul în construcție deasupra acestei scrieri plasând fiecare cifră a rezultatului deasupra unui grup corespunzător de cifre ale radicandului: de fapt, numărul L al cifrelor zecimale ale rezultatului este egal cu numărul de grupuri de cifre ale radicandul.
Operăm cu trei variabile întregi curente: rezultatul în construcție x , un rest r și o cifră d care trebuie adăugate la scrierea anterioară a lui x . Inițial x și r sunt setate la 0 și următorul bloc de instrucțiuni se repetă de L ori.
- Modificați scrierea restului r adăugând cel mai semnificativ grup de cifre (cele mai îndepărtate spre stânga) neutilizate încă. Noi sunam {\ displaystyle c} numărul astfel obținut (valoarea curentă).
- Găsiți cea mai mare cifră {\ displaystyle d} astfel încât {\ displaystyle y: = d (20x + d)} nu depăși {\ displaystyle c} . Adăugați această nouă cifră la scrierea rezultatului x .
- Scădea {\ displaystyle y} din {\ displaystyle r} și astfel veți obține noua schimbare.
Exemplu: Găsiți rădăcina pătrată a lui 1522759
1 2 3 4
| 01 52 27 59 1 primă cifră a soluției
x 01 1 (20 * 0 + 1) = 1 + 1
00 52 2 2 a doua cifră a soluției
2x 00 44 2 (20 * 1 + 2) = 44 + 2
08 27 24 3 a treia cifră a soluției
24x 07 29 3 (20 * 12 + 3) = 729 + 3
98 59 246 4 a patra cifră a soluției
246x 98 56 4 (20 * 123 + 4) = 9856 4
00 03 Algoritmul se termină: partea întreagă este 1234, iar restul 3
Pentru a adapta algoritmul la o altă bază b decât 10, înlocuiți definiția anterioară a lui y cu {\ displaystyle y: = d (2bx + d)} . Folosind baza binară, algoritmul se simplifică foarte mult, deoarece la pasul 2, pentru a găsi cea mai mare cifră binară {\ displaystyle d} astfel încât {\ displaystyle y = d (2bx + d) <= c} , trebuie să încerci doar cu {\ displaystyle d = 1} , adică dacă 100 2 x + 1 ≤ c. Dacă inegalitatea se menține, atunci noua cifră a rezultatului este 1, altfel 0.
Estimare asimptotică a timpului luat de algoritm
Pentru a găsi fiecare cifră a rezultatului (în bază binară) sunt necesare următoarele operații:
- multiplica {\ displaystyle x} pentru 100 2 și adăugați 1 (echivalent cu anexarea 01 la scrierea binară);
- o comparație, adică pentru a verifica dacă inegalitatea este satisfăcută;
- o diferență între numere care au cel mult un număr de cifre egal cu cel al rezultatului.
Deci, pentru a găsi partea întreagă a rădăcinii unui întreg {\ displaystyle n} , dureaza {\ displaystyle O (\ log _ {2} ^ {2} (n))} .
Implementare cu o funcție în limbajul C ++
int intsqrt ( int a , int * pr )
// Având în vedere numărul întreg pozitiv a, calculați partea întreagă a lui
// principala rădăcină pătrată și repausul;
// pune restul în * pr și returnează rădăcina
{
int x , r , dp1 , L , g [ 10 ], j , y , yn ;
// separați perechile de cifre și calculați numărul de cifre din rădăcină
L = 0 ;
în timp ce ( a > 0 )
{
g [ L ++ ] = a % 100 ;
a / = 100 ;
}
// aleargă pentru a găsi următoarele cifre ale rădăcinii
x = r = 0 ;
pentru ( j = L -1 ; j > = 0 ; j - )
{
r = r * 100 + g [ j ]; // adăugați noul grup de 2 cifre la restul anterior înmulțit cu 100
y = 0 ; // determina cifra
pentru ( dp1 = 1 ; dp1 < 10 ; dp1 ++ )
{
yn = dp1 * ( 20 * x + dp1 );
dacă ( yn <= r ) y = yn ; altfel pauză ;
}
x = x * 10 + dp1 -1 ; r - = y ;
}
* pr = r ;
return ( x );
}
Calculul rădăcinii pătrate cu orice precizie
Algoritmul anterior poate fi adaptat pentru a obține rădăcina unui număr dat de o scriere zecimală (sau pozițională în orice bază) cu orice precizie. De exemplu, luați rădăcina numărului a = 152.3469 cu p = 4 cifre zecimale. În primul rând considerăm numărul întreg A = a * 100 p + 1 = 1523469000000; prin urmare, cu algoritmul anterior găsim rădăcina lui A prin găsirea părții întregi 1234288 și restul 2134056. Prin împărțirea părții întregi la 10 p + 1 , adică la rădăcina factorului multiplicativ anterior, obținem 12.34288 ca valoare implicită . Prin urmare, se poate concluziona că valoarea căutată este 12.3429 și că constituie o rotunjire în sus.
Cu toate acestea, aceste calcule întregi sunt mai scumpe decât calculele aproximative bazate pe considerații geometrice asupra funcției rădăcină pătrată, ca și celelalte prezentate aici. Cu toate acestea, calculele întregi au fost utilizate pentru a verifica acuratețea calculelor de inspirație geometrică.
Rădăcini pătrate folosind metoda iterativă a lui Newton
Metoda lui Newton găsește o singură rădăcină a unei funcții {\ displaystyle f (x)} plecând de la cunoașterea unei aproximări suficient de precise a rădăcinii. Această metodă converge foarte repede la soluție, necesită puține operațiuni pentru fiecare iterație și, din punct de vedere al calculului, este ușor de implementat (din acest motiv este utilizată în diverse biblioteci, inclusiv biblioteca standard C ). Se bazează pe iterația exprimată prin:
- {\ displaystyle x_ {n + 1} = x_ {n} - {f (x_ {n}) \ peste f ^ {\ prime} (x_ {n})}} .
Pentru a găsi rădăcina pătrată a unui număr z sunt utilizate pe scară largă două funcții speciale: {\ displaystyle f (x) = x ^ {2} -z} Și {\ displaystyle g (x) = {\ frac {1} {x ^ {2}}} - z} .
Prima metodă
Prima metodă caută rădăcina pătrată a lui z folosind
- {\ displaystyle f (x) = x ^ {2} -z}
Rețineți că acestea sunt rădăcinile funcției {\ displaystyle f (x)} este {\ displaystyle {\ sqrt {z}}} acea {\ displaystyle - {\ sqrt {z}}} , sau asta {\ displaystyle f ({\ sqrt {z}}) = f (- {\ sqrt {z}}) = 0} .
Prima derivată a funcției este {\ displaystyle f ^ {\ prime} (x) = 2x}
Apoi iterația pentru {\ displaystyle x_ {n + 1}} se obține ca:
{\ displaystyle x_ {0} = 1 \, \,} Și
{\ displaystyle x_ {n + 1}} | {\ displaystyle = x_ {n} - {f (x_ {n}) \ peste f ^ {\ prime} (x_ {n})}} |
| {\ displaystyle = x_ {n} - {(x_ {n} ^ {2} -z) \ peste 2x_ {n}}} |
| {\ displaystyle = x_ {n} - {\ frac {x_ {n}} {2}} + {\ frac {z} {2 \, \, \, x_ {n}}}} |
| {\ displaystyle = {\ frac {x_ {n}} {2}} + {\ frac {z} {2 \, \, \, x_ {n}}}} . |
Rețineți că corespunde exact metodei babiloniene.
A doua metodă
A doua metodă caută reciprocitatea rădăcinii pătrate a lui z folosind funcția
- {\ displaystyle g (x) = {\ frac {1} {x ^ {2}}} - z}
funcție având ca rădăcini {\ displaystyle {\ frac {1} {\ sqrt {z}}}} Și {\ displaystyle {\ frac {-1} {\ sqrt {z}}}} .
Primul derivat al acestei funcții este {\ displaystyle g ^ {\ prime} (x) = - 2x ^ {- 3}} .
De aici iterația newtoniană pentru {\ displaystyle x_ {n + 1}} se obține ca:
{\ displaystyle \, x_ {0} = 0,5 \ qquad} Și
{\ displaystyle x_ {n + 1} \, \!} | {\ displaystyle = x_ {n} - {g (x_ {n}) \ peste g ^ {\ prime} (x_ {n})}} |
| {\ displaystyle = x_ {n} - {x_ {n} ^ {- 2} -z \ over -2x_ {n} ^ {- 3}}} |
| {\ displaystyle = x_ {n} - (- 1/2) {x_ {n} ^ {3}} (x ^ {- 2} -z)} |
| {\ displaystyle = x_ {n} + (1/2) (x_ {n} -zx_ {n} ^ {3})} |
| {\ displaystyle = {\ frac {3x_ {n} -zx_ {n} ^ {3}} {2}}} |
| {\ displaystyle = 1.5 \, x_ {n} -0.5 \, zx_ {n} ^ {3} = 0.5 \, x_ {n} \, \, (3-zx_ {n} ^ {2})} . |
Exemplu
Folosim ambele metode pentru a găsi{\ displaystyle {\ sqrt {7}} = 2.6457513 ...} .
- {\ displaystyle z = 7} întrucât căutăm rădăcina pătrată a lui 7
{\ displaystyle f (x)} | {\ displaystyle g (x)} |
---|
{\ displaystyle x_ {0}} | {\ displaystyle 1} | {\ displaystyle x_ {0}} | {\ displaystyle 0,5} | |
{\ displaystyle x_ {1}} | {\ displaystyle {\ frac {1} {2}} + {\ frac {7} {2 \ times 1}} = 4} | {\ displaystyle x_ {1}} | {\ displaystyle 0,5 \ times 0,5 \, \, (3-7 (0,5) ^ {2}) = 0,312} | {\ displaystyle {\ frac {1} {x_ {1}}} = 3.2} |
{\ displaystyle x_ {2}} | {\ displaystyle {\ frac {4} {2}} + {\ frac {7} {2 \ times 4}} = 2.875} | {\ displaystyle x_ {2}} | {\ displaystyle 0,5 \ times 0.312 \, \, (3-7 (0.312) ^ {2}) = 0.362} | {\ displaystyle {\ frac {1} {x_ {2}}} = 2.762} |
{\ displaystyle x_ {3}} | {\ displaystyle {\ frac {2.875} {2}} + {\ frac {7} {2 \ times 2.875}} = 2.654} | {\ displaystyle x_ {3}} | {\ displaystyle 0,5 \ times 0,362 \, \, (3-7 (0,362) ^ {2}) = 0,376} | {\ displaystyle {\ frac {1} {x_ {3}}} = 2.652} |
{\ displaystyle x_ {4}} | {\ displaystyle {\ frac {2.654} {2}} + {\ frac {7} {2 \ times 2.654}} = 2.645} | {\ displaystyle x_ {4}} | {\ displaystyle 0,5 \ times 0,376 \, \, (3-7 (0,376) ^ {2}) = 0,378} | {\ displaystyle {\ frac {1} {x_ {4}}} = 2.645} |
{\ displaystyle {\ sqrt {7}} \ simeq 2.645} | {\ displaystyle {\ sqrt {7}} \ simeq 2.645} |
---|
Comparaţie
Iterația pentru {\ displaystyle f (x)} implică o împărțire care este mai oneroasă, din punct de vedere al timpilor de calcul, decât o multiplicare între numere întregi. Iterația pentru {\ displaystyle g (x)} nu implică diviziuni și, prin urmare, este recomandat pentru întregul mare z .
Această iterație folosind g implică doar o pătrare și două multiplicări, ca alternativă la o diviziune în cazul lui f . În implementarea practică a extracției rădăcinii pătrate a numerelor întregi mari, calculul iterativ care necesită g este mai rapid pentru numerele întregi mari z , deoarece diviziunea este cel mult {\ displaystyle O (M (n))} , care este un factor constant al timpului de multiplicare. Termenul constant este aproape întotdeauna 3 sau mai mult, întrucât o singură diviziune cu majoritatea dispozitivelor de calcul este mai rapidă decât trei înmulțiri.
Aproximare simplă
Această metodă de aproximare, după cum sugerează și numele, este destul de simplă, dar poate fi, de asemenea, foarte inexactă. Mărimea impreciziei pentru această aproximare depinde de valoarea expresiei {\ displaystyle d / 2N} : cu cât valoarea este mai mare, cu atât este mai mare inexactitatea rezultatului aproximativ.
Constructie
Fie N> 0 și> 0, apoi
- {\ displaystyle N ^ {2} \ quad <\ quad N ^ {2} + d \ quad <\ quad N ^ {2} +2 \, d + {\ frac {d ^ {2}} {N ^ { 2}}}}
- {\ displaystyle N ^ {2} \ quad <\ quad N ^ {2} + d \ quad <\ quad N ^ {2} +2 \ left (N \ right) \ left ({\ frac {d} {N }} \ right) + \ left ({\ frac {d} {N}} \ right) ^ {2}}
- {\ displaystyle N ^ {2} \ quad <\ quad N ^ {2} + d \ quad <\ quad \ left (N + {\ frac {d} {N}} \ right) ^ {2}}
- {\ displaystyle N \ quad <\ quad {\ sqrt {N ^ {2} + d}} \ quad <\ quad N + {\ frac {d} {N}}} .
De aici și valoarea lui {\ displaystyle {\ sqrt {N ^ {2} + d}}} trebuie să fie între {\ displaystyle (N)} Și {\ displaystyle (N + {\ frac {d} {N}})}} . Aproximarea este apoi luată în considerare
- {\ displaystyle {\ sqrt {N ^ {2} + d}} \, \ approx \, {\ mbox {media}} \ left (N, N + {\ frac {d} {N}} \ right) = {\ frac {1} {2}} \ left (N + N + {\ frac {d} {N}} \ right)}
adică
- {\ displaystyle {\ sqrt {N ^ {2} + d}} \, \ approx \, N + {\ frac {d} {2 \, N}}}
Exemplu:
- Pentru a aproxima rădăcina lui 39, înlocuiți 39 cu suma unui pătrat cunoscut și valoarea d egală cu diferența (în acest caz {\ displaystyle 39 = 36 + 3} ).
- {\ displaystyle {\ sqrt {39}} = {\ sqrt {36 + 3}} \, \ approx \, 6 + {\ frac {3} {12}} \, \ approx \, 6.25}
care aproximează destul de mult valoarea reală de 6.244997.
Metoda ecuațiilor cuadratice
Soluția la problema găsirii unei valori inițiale optime de găsit {\ displaystyle {\ sqrt {r}}} unde 1 <r <100 poate fi rezolvat astfel:
Metoda ecuațiilor cuadratice |
---|
Pentru rădăcinile pătrate cu valori mai mari de 100, se folosește următoarea identitate: - {\ displaystyle {\ sqrt {105,3}} = {\ sqrt {1.053}} \ ori 10}
Pentru rădăcinile pătrate cu valori mai mici de 1, se utilizează următoarea identitate - {\ displaystyle {\ sqrt {0,1053}} = {\ sqrt {10,53}} \, \ div \, 10}
|
Folosind ecuația {\ displaystyle {\ sqrt {r}} \, = \, N + {\ frac {1} {X}}} unde este {\displaystyle X>1} e {\displaystyle N\in \{1,2,3,4,5,6,7,8,9\}}
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {1}{X}}}
- {\displaystyle r\,=\,{\left(N+{\frac {1}{X}}\right)}^{2}}
- {\displaystyle r\,=\,N^{2}+{\frac {2\,N}{X}}+{\frac {1}{X^{2}}}}
- {\displaystyle 0\,=\,\left(N^{2}-r\right)+{\frac {2\,N}{X}}+{\frac {1}{X^{2}}}}
- {\displaystyle \left(N^{2}-r\right)+{\frac {2\,N}{X}}+{\frac {1}{X^{2}}}\,=\,0}
- {\displaystyle \left(N^{2}-r\right)\,X^{2}+\left(2\,N\right)X+1\,=\,0}
Risolvere {\displaystyle X} utilizzando la formula dell'equazione quadratica , scegliendo la soluzione che soddisfa la condizione {\displaystyle X>1} .
La soluzione finale è:
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {1}{X}}}
L'ovvio problema è che non possiamo valutare le soluzioni dell'equazione quadratica senza l'uso della funzione radice quadrata. Tuttavia possiamo fare in modo che il serpente morda la propria coda.
- {\displaystyle \left(N^{2}-r\right)\,X^{2}+\left(2\,N\right)X+1\,=\,0}
- Sia{\displaystyle r\,=\,N^{2}+d}
- Allora{\displaystyle d\,=\,rN^{2}}
- E {\displaystyle -d\,=\,N^{2}-r}
Così l'equazione quadratica diventa:
- {\displaystyle \left(-d\right)\,X^{2}+\left(2\,N\right)X+1\,=\,0}
Iterando per {\displaystyle X} quanto più possibile porta a
- {\displaystyle X\,=\,{\frac {N+{\sqrt {N^{2}+d}}}{d}}}
Reciprocamente
- {\displaystyle {\frac {1}{X}}\,=\,{\frac {d}{N+{\sqrt {N^{2}+d}}}}}
Così la soluzione finale diventa
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {1}{X}}}
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{N+{\sqrt {N^{2}+d}}}}}
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{N+{\sqrt {r}}}}}
Andiamo più a fondo sostituendo a destra {\displaystyle {\sqrt {r}}} la sua stessa definizione:
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{N+\left(N+{\frac {d}{N+{\sqrt {r}}}}\right)}}}
Rinormalizzando
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{2N+{\frac {d}{N+{\sqrt {r}}}}}}}
Iterando ulteriormente
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{2N+{\frac {d}{2N+{\frac {d}{N+{\sqrt {r}}}}}}}}}
E avanti così
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{2N+{\frac {d}{2N+{\frac {d}{2N+{\frac {d}{N+{\sqrt {r}}}}}}}}}}}
Esempio di uso del metodo dell'equazione quadratica
Trovare {\displaystyle {\sqrt {923,45}}}
- Utilizzando l'identità {\displaystyle {\sqrt {923,45}}\,=\,{\sqrt {9,2345}}\times 10}
- Prima trovare {\displaystyle {\sqrt {9,2345}}} .
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {1}{X}}}
- {\displaystyle {\sqrt {9,2345}}\,=\,N+{\frac {1}{X}}}
Così {\displaystyle N\,=\,3\,\!} perché {\displaystyle \!\;3^{2}\;<\;9,2345\;<\;4^{2}}
- {\displaystyle \left(N^{2}-r\right)\,X^{2}+\left(2\,N\right)X+1\,=\,0}
- {\displaystyle \left(3^{2}-9,2345\right)\,X^{2}+\left(2\,\cdot \,3\right)X+1\,=\,0}
- {\displaystyle -0.2345\,X^{2}+6\,X+1\,=\,0}
Usando la formula dell'equazione quadratica , otteniamo le due soluzioni:
- sol 1 = −0,165 o sol 2 = 25,7519
Scegliamo sol2 dato che soddisfa la condizione {\displaystyle X>1} .
- Quindi {\displaystyle X=25,7519}
- {\displaystyle {\sqrt {9,2345}}\,=\,3+{\frac {1}{25,7519}}\,=\,3,03883}
Alternativamente
- {\displaystyle {\sqrt {r}}\,=\,N+{\frac {d}{2N+{\frac {d}{2N+{\frac {d}{N+N}}}}}}}
- {\displaystyle {\sqrt {9,2345}}\,=\,3+{\frac {0,2345}{6+{\frac {0,2345}{6+{\frac {0,2345}{3+3}}}}}}}
- {\displaystyle {\sqrt {9,2345}}\,\approx \,3+{\frac {0,2345}{6+{\frac {0,2345}{6+{\frac {0,2345}{3+3}}}}}}}
- {\displaystyle {\sqrt {9,2345}}\,\approx \,3,03883}
E la soluzione finale è
- {\displaystyle {\sqrt {923,45}}\,=\,{\sqrt {9,2345}}\times 10\,=\,30,3883}
Voci correlate