Neliöjuuren uuttaminen

In algoritmiikan ja numeerinen analyysi , neliöjuuri uutto on prosessi, annetaan numero, laskemalla sen neliöjuuri . Tämän laskennan suorittamiseksi on monia menetelmiä. Tämä on erityinen tapaus n: nnen juuren laskennan etsimiselle .

Asiayhteys

Koska luvun neliöjuuri voi olla irrationaalinen luku , neliöjuuren poiminta on yleensä likimääräinen.

Määritelmät

A: n neliöjuuren purkaminen on sama kuin yhtälön ratkaiseminen . Siksi sovelletaan yleisiä menetelmiä polynomiyhtälöiden ratkaisemiseksi ja yleisemmin algoritmeja funktion nollan löytämiseksi . Samoja työkaluja käytetään mittaamaan menetelmien suorituskykyä.

Kun ylimääräistä tarkkuutta ei anneta, neliöjuuren poiminta tehdään reaalilukujoukossa . Voimme kuitenkin olla kiinnostuneita muista numerosarjoista, kuten kompleksiluvuista tai renkaista , kuten ℤ / nℤ .

Menetelmät positiivisten reaalilukujen saamiseksi

Heronin menetelmä

Menetelmä Heron on historiallinen kehittämää babylonialaiset . Nykyaikaisemmin sanottuna tämä on Newtonin menetelmän erityistapaus .

(Positiivisen) luvun a neliöjuurin määrittämiseksi on siksi otettava huomioon induktiolla määritelty sekvenssi seuraavasti: ensimmäinen termi on valittu, jos mahdollista "tarpeeksi lähellä" on , yleensä kokonaisluku osa on .

Nopeus lähentyminen peräkkäisten likiarvojen kohti tarkkaa arvoa on neliömäinen .

Bakshalin käsikirjoitusmenetelmä

Se löytyy Intian käsikirjoitus, sanoi Bakshali käsikirjoitus, ehkä vuodelta VII : nnen  vuosisadan erilainen korjaus Heronin menetelmä, uusi arvo on arviolta . Se vastaa Heronin menetelmän soveltamista kahdesti peräkkäin. Tämän viimeisen menetelmän iterointi antaa kahden asteen lähentymisnopeuden:

a: n lähentäminen vierekkäisten sekvenssien avulla

Tarkastellaan sekvenssejä u ja v, jotka määritellään seuraavasti:

Sekvenssit u ja v ovat vierekkäisiä ja yhtenevät kohti samaa rajaa: a . Virhe kasvaa erolla . Sekvenssi v ei ole mikään muu kuin sekvenssi, joka on saatu iteroimalla Heronin menetelmä arvosta 1 .

Huomaa tämän esityksen omaperäisyys, jossa yhdistyvät harmoniset, geometriset ja aritmeettiset keskiarvot. Todellakin, ei ole mikään muu kuin geometrinen keskiarvo 1 ja , ja jos me korvata millä tahansa tiukasti positiivinen reaaliluku b , sekvenssit u ja v yhtyvät kohti geometrinen keskiarvo ab of ja b .

Desimaalimerkintää käyttävät algoritmit

Varren algoritmi

Numeroiden desimaalimerkinnän käyttöönotto sijainnin mukaan mahdollisti algoritmin kehittämisen hyödyntämällä tätä merkintää. Löydämme maininnan siitä intialaisen matemaatikon Âryabhatan teoksessa noin 499 jKr. AD Sitä käytettiin useiden vuosisatojen vasta puolivälissä XX : nnen  vuosisadan ennen keksintö elektronisia tietokoneita. Aryabhata antaa myös vastaavan algoritmin laskemiseksi kuutiometriä juuret .

Erota luvun numerot pareittain desimaalipisteestä alkaen. Sijoitamme numeron, josta haluamme poimia juuren, ylhäältä samalla tavalla kuin suoritettaessa jako klassisen menetelmän mukaisesti; neliöjuuri merkitään jakajalle normaalisti varattuun paikkaan tavanomaisessa poseeratussa jaossa .

Jokaisessa vaiheessa:

Huomaa, että x : n etsiminen laiminlyömällä termi x 2: ssa ei ole kukaan muu kuin Heronin menetelmä.

Esimerkki: 152,2756 = 12,34 hirsipuu-menetelmällä

(Huomaa: Juuren muodostavien numeroiden sekvenssi merkitään jakelijalle siirrettyyn paikkaan klassisessa jaossa, jolloin saadaan tulos: 12.34. Pilkun paikka on merkittävä, mutta sitä ei tarvitse ottaa huomioon huomioi se laskun aikana)

1 52 , 27 56 1 2 , 3 4   Juuren r progressiivinen rakenne . Laske ensimmäinen viipale.
1 ? ×? Etsimme suurinta x, niin että x ² ei ylitä arvoa 1. Se on 1 . Täydennämme r .
-1 1 × 1 = 1 että yksi ottaa pois nykyisestä lopusta ja toinen laskee seuraavan viipaleen.
0 52 2? ×? r = 1, etsimme suurinta x siten, että (20+ x ) x ei ylitä 52. Se on 2 . Täydennämme r .
- 44 2 2 × 2 = 44 että yksi ottaa pois nykyisestä jäljellä olevasta ja toinen laskee seuraavan erän. Laitamme pilkun r: ään .
8 27 24? ×? r = 12, etsimme suurinta x siten, että (240+ x ) x ei ylitä 827. Se on 3 . Täydennämme r .
-7 29 24 3 × 3 = 729 että yksi ottaa pois nykyisestä lopusta ja toinen laskee seuraavan viipaleen.
  98 56 246? ×? r = 123, etsimme suurinta x siten, että (2460+ x ) x ei ylitä 9856. Tämä on 4 . Täydennämme r .
- 98 56 246 4 × 4 = 9856 että otamme pois nykyisestä leposta
0   Loppu

Tähän  algoritmiin käytettiin yleisesti XX - luvulle saakka nopeuttamalla laskutoimituksia abakilla, joka muodosti joukon nauhoja: Napier-tikkuja .

Vaikka tässä kuvataan tukiasemaan 10 kirjoitetuille numeroille, menettely toimii missä tahansa numeropohjassa, esimerkiksi kannassa 2 .

Ruffini-Horner-menetelmä

A: n neliöjuuren löytäminen on polynomin P (X) = X² - ​​A positiivisen juuren löytäminen. Olkoon a suurin kokonaisluku siten, että P (a) on negatiivinen tai nolla. A: n juuri on kokonaisluku a: n ja + 1: n välillä. Asetamme sitten X = a + Y / 10. P (X) = P (a + Y / 10) = P 1 (Y). Neliöjuuri A on sitten yhtä kuin + r / 10, jossa r on juuri polynomin P 1 . Jos b on suurin kokonaisluku siten, että P 1 (b) on negatiivinen, niin juuri A on välillä + b / 10 ja a + b / 10 + 1/10. Sen jälkeen määritetään Y = b + Z / 10, P 1 (Y) = P 2 (Z). Etsimme sitten P 2 : n juurta jne.

Ruffini-Horner menetelmän avulla on helppo vaihtaa muuttujiin

Esimerkki: 152,2756 = 12,34 Hornerin menetelmällä

P (X) = X2 - 152,2756

a = 12, koska P (12) <0 ja P (13)> 0

Muuttujan X = 12 + Y / 10 muutos polynomissa P suoritetaan Hornerin menetelmän mukaisesti:

P: n kertoimet 1 0 - 153,2756
1 12 144-152,2756 = -8,2756
1 12 + 12 = 24
1

Siksi

Suurin kokonaisluku b, kuten P 1 (b) on negatiivinen, on 3 (etsimme arvoa, joka on lähellä arvoa 827/240). Etsitty juuri on siis välillä 12,3–12,4

Teemme muutoksen muuttujan Y = 3 + Z / 10 polynomin P 1

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

Siksi

4 on P 2: n juuri . Joten 152.2756: n neliöjuuri on 12.34

Uuttaminen peräkkäisinä parittomina summina

Tämä menetelmä joskus opetti XIX : nnen  vuosisadan eduksi alennetaan useita lisäyksiä (enintään 9 kohti haetaan desimaalin) peräkkäisten pariton

Se koostuu peräkkäisten neliöiden taulukon ja niiden eron hyödyntämisestä huomioimalla se . Neliötaulukon skannaus koostuu siis peräkkäisten parittomien numeroiden lisäämisestä. Leikattuamme numeron kahden numeron viipaleiksi alkaen oikealta, löydämme neliön heti ryhmän alapuolelta, joka on kauimpana vasemmalla. Antaa olla tämän juuri alemman neliön neliöjuuri. Kerrotaan löydetty kokonaisluku ja pyyhkäistään neliötaulukko alkaen (ja ) lähestyäksesi kahden vasemmanpuoleisen ryhmän muodostamaa lukua. Tämä luku löydetään, kerrotaan se selaamalla neliötaulukkoa alkaen jne.

Ennen kuin skannataan neliötaulukko, 5: llä päättyvien kokonaislukujen neliöiden helppo laskettavuus voi joissakin tapauksissa antaa mahdollisuuden päästä eroon viidestä lisäyksestä testaamalla, pysyykö kumpikaan myös alhaisemmalla (vai ei) etsivät juurta. Jos näin on, on parempi jatkaa algoritmia alkaen kuin .

Esimerkiksi haluamme pyöristää lähellä . Tämän tarkkuuden kunnioittamiseksi meidän on etsittävä juuret . Riittää sitten lopullisen juuren jakaminen .

Kuten sanoen , meillä on: . Mutta ollessa lähempänä kuin , on lähempänä kuin .

Sen sijaan, että alkaa pyyhkäisemään ja voimme, tässä tapauksessa, prosessin aloittamiseksi  : . Se oli hyvä, kuten odotettiin .

Algoritmi (joka on yksityiskohtainen seuraavassa esimerkissä) tuo meidät vähitellen, johon lisäämme , mikä on lähempänä kuin . Päättelemme: on suljettava.

Esimerkki: 152,2756 = 12,34 peräkkäisten parittomien lukumäärien menetelmällä

Neliöjuuri 1,522,756 antaa kertoimelle 100 halutun neliöjuuren. Tämä luku on leikattu 2-numeroisiksi viipaleiksi 1 52 27 56. Ensimmäistä ryhmää lähinnä oleva neliö on 1.

Skannataan sitten neliötaulukko 10: stä lähestymään 152

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

25 lisääminen johtaisi ylittämään 152. Siksi siirrymme seuraavaan kymmeneen käymällä neliötaulukon läpi 120: stä lähestyessä 15227.

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

247: n lisääminen johtaisi 15227: n ylitykseen. Siksi siirrymme seuraavaan kymmeneen selaamalla neliötaulukkoa vuodelta 1230 lähestyessä 1522756.

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

1522756 on siis neliön 1234 ja 152.2756 neliön 12.34 neliö


Tätä samaa periaatetta käytetään neliöjuuren uuttamisessa tippumismenetelmällä .

Uuttaminen lisäämällä ja vähentämällä

Tällä hyvin yksinkertaisella menetelmällä on erityispiirre, kun käytetään vain hyvin yksinkertaisia ​​operaatioita: summaus, vähennys ja 0: n summa. Harkitse sekvenssejä a ja b, jotka määritellään

  • ,
  • Jos sitten ja
  • Muussa tapauksessa (mikä merkitsee kahden nollan lisäämistä lopussa ) ja (mikä tarkoittaa nollan lisäämistä juuri ennen viimeistä numeroa, koska jälkimmäinen päättyy aina 5: ään)

Siten numeroiden määrä lähestyy yhä enemmän numeroiden lukumäärää . Huomaa, että se on kokonaisluku (yhä suurempi), joten se ei ole suuntaus kohti, vaan vain sen numerot desimaaliesityksessä.

Esimerkki: 3 ≈ 1,732 summaamalla ja vähentämällä

,

Kommentit
0 15 5 Voimme vähentää
1 10 1 5 Emme voi enää vähentää
2 1000 105 Voimme vähentää
3 895 115 Voimme vähentää
4 780 125 Voimme vähentää
5 655 135 Voimme vähentää
6 520 145 Voimme vähentää
7 375 155 Voimme vähentää
8 220 165 Voimme vähentää
9 55 17 5 Emme voi enää vähentää
10 5500 1705 Voimme vähentää
11 3795 1715 Voimme vähentää
12 2080 1725 Voimme vähentää
13 355 173 5 Emme voi enää vähentää
14 35500 17305 Voimme vähentää
15 18195 17315 Voimme vähentää
16 880 1732 5 emme voi enää vähentää
...

Jos sen sijaan, että 5 m , otamme -lyhennyksiin välein kaksi numeroa ja lisäämisen sijaan kaksi nollaa ja n , me laskemme seuraavat lisäykset, me päätyä muunnos 5 pisaran menetelmää. Pisaralta.

Jatkuvan jakeen menetelmä

Jatkuva osa irrationaalisen on sekvenssi sen "optimaalinen" likiarvoja fraktioilla, toisin sanoen, että jos p / q on yksi arvoista tämän sekvenssin, niin ei osa / b , jossa b < q ei lähestyy tarkemmin todellisuutta. Tietyssä tapauksessa neliön juuret, yksi laskee suhteellisen yksinkertaisesti tämän sekvenssin, sekä alasekvenssi , joka vastaa tiettyä tapauksessa menetelmä Heron .

Dikotomimenetelmä

On myös mahdollista edetä dikotomialla edellyttäen, että halutulle neliöjuurelle on olemassa kehys. Tätä varten voimme käyttää neliöjuuren etsimän numeron lukumäärää. Tällä juurella olisi puolet niin monta numeroa. Jos luvulla on 1024 numeroa, sen neliöjuuren välillä on 511 - 513. Voimme myös ensin käyttää aikaisempia menetelmiä saadaksesi ensimmäisen likimääräisen neliöjuuren arvon, ennen kuin jatkat kaksisuuntaisuuteen.

Dikotomialgoritmi on seuraava. Se välttää jakamisten suorittamisen (muu kuin jakaminen 2: lla, joka on vain rekisterisiirtymä, jos numerot ovat binäärikoodattuja. Tämä jako on merkitty alla olevaan 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;

Samaa menetelmää sovelletaan n: nteen juuriin korvaamalla D2 = D * D: n laskenta D ^ n: n laskennalla.

Dikotomimenetelmällä on kuitenkin hitaampi lähentymisnopeus kuin Heronin menetelmän iteroinnilla.

Muissa numerosarjoissa

Monimutkaiset numerot

Renkaat ℤ / nℤ

Yritämme ratkaista yhtälö . Voimme sitten erottaa kolme tapausta:

  • on alkuluku (esim. 19);
  • on teho on alkuluku (esim 81 = 3 4 );
  • on yhdistetty luku (esim. 35 = 5 × 7).

Jos on olemassa ratkaisu, eli jos on modulo neliönjäännös , yksi on tehokkaita algoritmeja löytää sen kahdessa ensimmäisessä tapauksessa. Jos on yhdistetty luku, tällä hetkellä meillä on vain tehokas algoritmi, jos tekijöihinjako ja on tunnettua. Lisäksi voimme osoittaa, että jos olisi ollut tehokas algoritmi neliöjuuren laskemiseksi ilman tekijöiden jakamista , tätä algoritmia voitaisiin käyttää tehokkaan tekijäalgoritmin saamiseen . Siksi emme voi laskea tehokkaasti modulo-neliöjuuria, ennen kuin voimme tehokkaasti laskea minkä tahansa kokonaisluvun ja päinvastoin.

Huomautuksia ja viitteitä

Huomautuksia

Viitteet

  1. T. Hayashi, Bakhshalin käsikirjoitus, muinainen intialainen matemaattinen tutkielma , John Benjamins Publishing Company, Amsterdam (2005).
  2. WE Clarke, Aryabhatan aryabhatia, muinainen intialainen työ matematiikasta ja tähtitieteestä , Chicagon yliopisto, Chicago IL (1930).
  3. Joseph Claudel, Johdatus insinöörien tieteeseen , Dunod, 1863 sivut 86/87
  4. Frazer Jarvis, neliön juuret vähentämällä [1]
  5. (en) Victor Shoup , Laskennallinen johdanto numeroteoriaan ja algebraan , Cambridge University Press,2009, 2 nd  ed. , 580  Sivumäärä ( ISBN  9780521516440 ja 0521516447 , OCLC  277069279 , luettu verkossa ) , 12. Toissijainen vastavuoroisuus ja modulaaristen neliöjuurien laskenta , luku .  5 ("Modulaaristen neliöjuurien laskeminen") , s.  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;">