3. Monotoninės sekos

keisti

1. Monotoninių sekų apibrėžimas.

keisti
Apibrėžimas. Seka   vadinama nemažėjančia (nedidėjančia), jei kiekvienas tos sekos elementas ne mažesnis (ne didesnis) už pirmesnįjį elementą, t. y., jei su visais numeriais n teisinga nelygybė
  ( ).
Nemažėjančios ir nedidėjančios sekos vadinamos monotoninėmis sekomis. Jei monotoninės sekos   elementai su bet kuriuo numeriu n tenkina nelygybę   ( ), tai seka   vadinama didėjančia (mažėjančia). Didėjančios ir mažėjančios sekos dar vadinamos griežtai monotoninėmis sekomis.
Monotoninės sekos yra aprėžtos arba iš viršaus, arba iš apačios; būtent, nedidėjančios sekos aprėžtos iš viršaus, o nemažėjančios aprėžtos iš apačios pirmaisiais savo elementais. Todėl nedidėjanti seka yra aprėžta iš abiejų pusių, kai ji aprėžta iš apačios, o nemažėjanti seka yra aprėžta iš abiejų pusių, kai ji aprėžta iš viršaus.
Pateiksime tris monotoninių sekų pavyzdžius.
1. Seka   nedidėjanti. Ji aprėžta iš viršaus savo pirmuoju elementu, lygiu vienetui, o iš apačios - skaičiumi 0.
2. Seka   nemažėjanti. Ji aprėžta iš apačios savo pirmuoju elementu, o iš viršaus neaprėžta.
3. Seka   didėjanti. Ji aprėžta iš abiejų pusių: iš apačios pirmuoju elementu   iš viršaus, pavyzdžiui, skaičiumi 1.

2. Monotoninės sekos konvergavimo požymis.

keisti
Įrodysime pagrindinę teoremą.
3.15 teorema. Jei nemažėjanti (nedidėjanti) seka   aprėžta iš viršaus (iš apačios), tai ji konverguoja.
Pagal praeitą skirsnį seka   atitinkanti 3.15 teoremos sąlygas, yra aprėžta. Todėl 3.15 teoremą galima trumpai formuluoti taip: jei monotoninė seka   yra aprėžta iš abiejų pusių, tai ji konverguoja.
Įrodymas. Kadangi seka   yra aprėžta, tai jos elementų aibė turi tikslųjį viršutinį rėžį   ir tikslųjį apatinį rėžį   Įrodysime štai ką: jei   – nemažėjanti seka, tai jos riba yra minėtasis tikslusis viršutinis rėžis; jei   – nedidėjanti seka, tai jos riba yra minėtasis tikslusis apatinis rėžis   Išnagrinėsime tik nemažėjančią seką, nes samprotavimai apie nedidėjančią seką būtų analogiški.
Kadangi   yra sekos   elementų aibės tikslusis viršutinis rėžis, tai kiekvieną   atitinka toks elementas   kad   ir   (bet koks elementas   ne didesnis už tikslųjį viršutinį rėžį   t. y.  ). Iš šitų nelygybių gauname nelygybes   Kadangi   – nemažėjanti seka, tai nelygybės   yra teisingos, kai   Iš to išplaukia, kad   kai   Anksčiau pabrėžėme, kad   todėl, kai   teisingos nelygybės   iš kurių gauname nelygybę   Vadinasi, įsitikinome, kad   yra sekos   riba. Teorema įrodyta.
1 pastaba. Monotoninės sekos aprėžtumas yra būtinas ir pakankamas jos konvergavimo požymis.
Iš tikrųjų, jei monotoninė seka yra aprėžta, tai pagal 3.15 teoremą ji konverguoja; jei monotoninė seka konverguoja, tai, remiantis 3.8 teorema, ji yra aprėžta.
2 pastaba. Konverguojanti seka gali ir nebūti monotoninė. Pavyzdžiui, seka   apibrėžta formule   konverguoja, o jos riba yra skaičius 0. Tačiau ši seka nėra monotoninė, nes po teigiamo elemento eina neigiamas, o po neigiamo – teigiamas.
3 pastaba. Jei   yra nemažėjanti ir aprėžta seka, o   – tos sekos riba, tai visi jos elementai tenkina nelygybę   Nedidėjančios ir aprėžtos sekos   konverguojančios į   elementai tenkina nelygybę   Kad šie teiginiai teisingi, įsitikinome, įrodinėdami 3.15 teoremą.
3.15 teoremos išvada. Sakykime, duota begalinė segmentų sistema   Jei kiekvienas segmentas yra pirmesniajame*, o skirtumas   (jį vadinsime segmento   ilgiu) artėja prie nulio, kai   (segmentų sistemą, turinčią šią savybę, vadinsime susitraukiančia), tai egzistuoja vienintelis taškas c, priklausantis visiems tos sistemos segmentams.
Įrodymas. Pirmiausia pastebėsime, kad taškas c, priklausantis visiems segmentams, gali būti tik vienas. Iš tikrųjų, jei būtų dar vienas taškas d, priklausantis visiems segmentams, tai segmentas ** [c; d] priklausytų visiems segmentams   Bet tokiu atveju su bet kokiu numeriu n būtų teisingos nelygybės   tai neįmanoma, nes   kai   Dabar įsitikinsime, kad taškas c, priklausantis visiems segmentams   egzistuoja. Kadangi segmentų sistema yra susitraukianti, tai kairiųjų galų seka   yra nemažėjanti, o dešiniųjų galų seka   – nedidėjanti. Kadangi abi tos sekos yra aprėžtos (visi sekų   ir   elementai priklauso segmentui  ), tai pagal 3.15 teoremą jos konverguoja. Iš to, kad skirtumas   nyksta, išplaukia, jog minimosios sekos turi bendrą ribą. Tą ribą žymėkime raide c. Remiantis 3 pastaba, su bet kokiu numeriu n teisingos šios nelygybės:   t. y. taškas c priklauso visiems segmentams  

_______________

* Tai reiškia, kad  
** Siekdami konkretumo, tariame, kad d > c.

3. Keli konverguojančių monotoninių sekų pavyzdžiai.

keisti
Išnagrinėsime kelias sekas, kurių ribas apskaičiuosime, remdamiesi 3.15 teorema apie monotoninės sekos ribą. Be to, šiame skirsnyje susipažinsime su vienu bendru sekos ribos ieškojimo metodu, kai seka apibrėžiama rekurentine formule (Rekurentinė formulė (lot. recurrens – grįžtas) – formulė, pagal kurią  -ąjį sekos elementą galima išreikšti jos pirmųjų n elementų reikšmėmis.).
1 pavyzdys. Tirsime seką   kurios elementas   lygus
 
(n radikalų). Tą pačią seką galima, savaime aišku, nusakyti šitokia rekurentine formule:
 
Norėdami įsitikinti, kad sekos   riba egzistuoja, įrodysime, jog ta seka yra didėjanti ir aprėžta. Kad ta seka didėja, matyti tiesiog. Įsitikinsime, kad seka   aprėžta iš viršaus skaičiumi A, kai A – didedsnysis iš dviejų skaičių a ir 2. Jei   tai teiginys jau įrodytas. Jei   tai, dešinėje nelygybės   pusėje skaičių a pakeitę didesniu už jį skaičiumi   gauname   o iš čia   Taigi įrodėme, kad seka   aprėžta iš viršaus. Pagal 3.15 teoremą ta seka turi ribą. Pažymėkime tą ribą raide c. Savaime aišku,   Iš rekurentinės formulės turime lygybę
 
iš kurios matyti, kad sekos   ir   sutampa. Todėl jos turi bendrą ribą. Kadangi pirmosios sekos riba lygi   o antrosios   (kai n varo į begalybę skaičiams   ir   tai   praktiškai nesiskiria nuo   ir abu yra labai arti c reikšmės (abu labai panašūs į c)), tai   Iš čia, turėdami mintyje, kad   randame c:
 
 
 
kadangi   tai
 
2 pavyzdys. Tirsime seką   kuria dažniausiai naudojamasi, apskaičiuojant teigiamo skaičiaus a kvadratinę šankį elektronine skaičiavimo mašina. Šita seka apibrėžiama tokia rekurentine formule:
 
Pirmuoju elementu   čia galima laikyti bet kokį teigiamą skaičių.
Įrodysime, kad ta seka konverguoja, o jos riba yra skaičius   Pirmiausia įsitikinsime, kad seka   turi ribą. Tam užtenka įrodyti, kad seka   yra aprėžta iš apačios ir kad, pradedant antruoju elementu, ji nedidėja. Iš pradžių įsitikinsime, kad seka   aprėžta iš apačios. Sąlygoje pasakyta, jog   o iš rekurentinės formulės, kai   gauname   Taip samprotaudami toliau, įsitikiname, kad visi   yra teigiami.
Dabar įrodysime, kad visi   kai   tenkina nelygybę   Parašę rekurentinę formulę šitaip:   remsimės beveik savaime aiškia nelygybe  *, kuri teisinga, kai   (imame  ). Gausime
 
kai   t. y.   pradedant numeriu  
Pagaliau įsitikinsime, kad seka   kai   nedidėja. Iš rekurentinės formulės matome, kad   o iš čia, turėdami mintyje, kad   gauname   arba   (kai  ).
Kadangi seka   kai   nedidėja ir yra aprėžta iš apačios skaičiumi   (nes  ), tai ji turi ribą, ne mažesnę kaip   (žr. 3.15 ir 3.13 teoremą). Tą ribą pažymėkime raide c ir atsižvelgę į tai, kad   o   gauname lygybę
 **,
 
 
 
 
Vadinasi,  
1 pastaba. Spręsdami pateiktuosius pavyzdžius, naudojomės plačiai taikomu metodu sekos ribai skaičiuoti. Metodo esmė: iš pradžių įsitikinama, kad sekos riba egzistuoja, o paskui iš lygties, kuri gaunama iš rekurentinės formulės, vietoje   ir   įrašius ieškomąją sekos   ribos reikšmę c, apskaičiuojama tos ribos skaitinė reikšmė.
2 pastaba. Rekurentinės formulės dažnai naudojamos skaičiavimo matematikoje, nes jas taikant daug kartų, atliekamos to paties tipo skaičiavimo operacijos, o tai labai patogu skaičiuojant elektroninėmis skaičiavimo mašinomis.
Išnagrinėtoji rekurentinė formulė aprašo, kaip įsitikinome,   skaičiavimo algoritmą (įrodėme, kad  ).
Vėliau bus tiriamas sekos   konvergavimo į   greitis. Įrodoma, kad, tinkamai pasirinkus pirmąjį artinį   kai   jau ketvirtasis artinys   nuo skaičiaus   skiriasi mažiau kaip  
3 pavyzdys. Įsitikinsime, kad sekos   kai   o x – bet koks fiksuotas skaičius, riba lygi nuliui. Kai n – pakankamai didelis natūralusis skaičius,   Todėl, pradedant kuriuo nors numeriu N, turi būti   nes  
Vadinasi, pradedant numeriu N, seka   mažėja. Kadangi, be to, ji aprėžta iš apačios (pavyzdžiui nuliu), tai pagal 3.15 teoremą seka   konverguoja. Tarkime, kad c yra tos sekos riba. Iš lygybės   išplaukia, kad   nes sekos   riba lygi c, o sekos   – nuliui.

_____________________

* Tą nelygybę įrodinėjant, užtenka pastebėti, kad, kai   ji ekvivalenti nelygybei  
** Ta lygybė gaunama iš rekurentinės formulės  


Sekos, aproksimuojančios a šaknyje, konvergavimo greitis

keisti
Šio skyriaus 3 paragrafo 3 skirsnyje įrodėme, kad sekos   apibrėžiamos rekurentine formule
 
kai   o   – bet koks teigiamas skaičius, riba lygi   Skaičiaus   artiniu galima laikyti bet kurį tos sekos narį   Tokiu atveju, be abejo, reikia išsiaiškinti, koks turi būti įteracijų* skaičius n, kad   artinys būtų nurodyto tikslumo.

______________

* Iteracija (lot. iteratio – kartojimas) – kokios nors matematinės operacijos pakartojimas. Šiuo atveju viena iteracija yra   apskaičiavimas, kai žinomas   pagal rekurentinę (3.10) formulę.

______________

Nagrinėsime seką   apibrėžtą rekurentine (3.10) formule. Tos sekos elementą   vadinsime skaičiaus   n-uoju artiniu. Skaičių
 
vadinsime n-ojo artinio santykine paklaida.
Įrodysime teiginį apie santykinės paklaidos   įvertinimą, remiantis pirmojo artinio santykine paklaida  
Jei   taip parinktas, kad   tai su bet kokiu   teisinga šitokia nelygybė:
 
[   kai   gali būti lygus nuliui.]
Įrodymas. Iš (3.11) formulės
 
Remdamiesi (3.10) ir (3.13) formulėmis bei lygybe   gauname
 
 
Kadangi   tai savaime aišku, kad
 
 
Pagal sąlygą   Iš to išplaukia nelygybės   Bet tada iš (3.14) lygybės, kai   išplaukia nelygybė   Panašiai naudodamiesi (3.14) lygybe, kai   įsitikiname, kad visi   yra neneigiami ( ).
Iš (3.14) lygybės, nelygybių   ir iš to, kad visi   kai   yra neneigiami, išplaukia nelygybė   kai   Iš čia gauname dešiniąją (3.12) nelygybę. Teiginys įrodytas.
[        ir taip toliau.]
Iš (3.12) nelygybių matyti, kad   artinio po n iteracijų santykinė paklaida įvertinama, remiantis pirmojo artinio   santykine paklaida   ir iteracijų skaičiumi n. Vėliau įsitikinsime, jog tuo atveju, kai  *, pirmąjį artinį galima pasirinkti taip, kad santykinės paklaidos   modulis nebūtų didesnis už 0.05. Savaime aišku, taip pasirinkus   santykinė paklaida tenkins įrodytojo teiginio sąlygas. Tuomet bus aišku ir koks turi būti iteracijų skaičius n, kad   artinio santykinė paklaida nebūtų didesnė už duotąjį skaičių  : tą skaičių n galima rasti iš nelygybės* (ta nelygybė gaunama tiesiog iš (3.12) nelygybių)
 
Taigi tarkime, kad   Skaičių a išreikšime šitaip:
 
čia k – sveikasis neneigiamas skaičius, skaičius i lygus arba nuliui, arba vienetui, o skaičius M tenkina sąlygą
 
Pabrėšime, kad skaičius a išreiškiamas (3.16) pavidalu vieninteliu budu.
Pirmąjį artinį   pasirinkime šitaip:
 
Įsitikinsime, kad tuo atveju, kai Mbet koks skaičius, tenkinantis (3.17) sąlygas, pirmojo   artinio   rasto pagal (3.18) formulę, santikinės paklaidos   modulis ne didesnis kaip 0.05.
Įrodinėdami šį teiginį, remsimės tikslia santykinės paklaidos išraiška   Iš (3.16) lygybės gauname   todėl iš   išraiškos ir iš (3.18) formulės
 
 
3.4 pav.
 
Alternatyvus 3.4 pav. Oy ašimi grafikas ištemptas tik maždaug 2 kartus daugiau nei Ox ašimi.
Kadangi skaičius i lygus arba nuliui, arba vienetui, o   tai   Todėl iš (3.19) lygybės išplaukia nelygybė
 
Pažymėkime   raide X. Kadangi   o i lygus arba nuliui, arba vienetui, tai visos galimos X reikšmės priklauso intervalui [1; 2):
 
Naudodami naujai įvestą žymėjimą, (3.20) nelygybę perrašysime šitaip:
 
Pagal (3.22) nelygybę maksimalioji   reikšmė ne didesnė už maksimaliąją reiškinio   reikšmę, kai X tenkina (3.21) sąlygas. Kad būtų aiškiau, išnagrinėkime funkcijos   grafiką. Iš elementariosios matematikos kurso žinome, kad šios funkcijos grafikas yra parabolė (3.4 pav.)**, kurios viršūnė atitinka  
[  
  ]
Kadangi   o   tai X reikšmės, tenkinančios (3.21) sąlygas, atitinka   reikšmėms, esančioms tarp   ir   Kitaip sakant,
 
Iš paskutinės ir (3.22) nelygybių gauname reikiamą   įvertinimą:
 
Pastaba. Jei nurodyta, kad santykinė paklaida   lygi   tai, norint tokiu tikslumu apskaičiuoti bet kokio skaičiaus   kvadratinę šaknį, reikia, suradus   pagal (3.18) formulę, atlikti tik tris iteracijas ( ), nes
 
[   Pasirodo, santykinė paklaida   visada bus mažesnė už   po 3 iteracijų ( ). ]

_______________

* Jei   tai   ir   Tada  
** 3.4 paveiksle ašies Oy mastelis 20 kartų didesnis už ašies Ox mastelį.

Pavyzdžiai

keisti
  • Apskaičiuosime   Iš (3.16) formulės   Matome, kad   turi būti lygus 4, t. y.   Tada aišku, kad   Toliau randame M:
 
 
 
Toliau randame   pagal (3.18) formulę:
 
 
= 2.58(3).
Skaičių   randame pagal (3.10) rekurentinę formulę:
 
= 2.646505376344086021505376344086.
Toliau rasime  :
 
= 2.6457514184920023809913880196814.
[Atėmę tikslią   reikšmę iš   reikšmės gauname:
2.6457514184920023809913880196814 - 2.6457513110645905905016157536393 = 1.0742741179048977226604214545141e-7.]
Toliau rasime  :
 
 
= 120178103989057/45423053741472 = 2.6457513110645927714791488926518.
Atėmę tikslią   reikšmę iš gautos   reikšmės, gauname:
2.6457513110645927714791488926518 - 2.6457513110645905905016157536393 = 2.1809775331390125063383535564728e-15.
Tai yra gavome paklaidą  
Santykinė paklaida yra tokia:
 
(2.6457513110645927714791488926518 - 2.6457513110645905905016157536393)/2.6457513110645905905016157536393 =
= 8.2433202395785127055094193690687e-16.
Taigi  


  • Apskaičiuosime   Iš (3.16) formulės   Pagal (3.17)   Todėl   Tada   Iš čia gauname, kad  
Toliau randame M:
 
 
 
 
Toliau randame   pagal (3.18) formulę:
 
= 6.08(3).
[   6.2449979983983982058468931209398. ]
Skaičių   randame pagal (3.10) rekurentinę formulę:
 
= 0.5*(6.0833333333333333333333333333333 + 6.4109589041095890410958904109589) =
= 0.5 * 12.494292237442922374429223744292 = 6.2471461187214611872146118721461.
Toliau rasime  :
 
= 0.5*(6.2471461187214611872146118721461 + 39/6.2471461187214611872146118721461) =
= 6.2449983677207123204232036062421.
[Atėmę tikslią   reikšmę iš   reikšmės, gauname:
6.2449983677207123204232036062421 - 6.2449979983983982058468931209398 = 3.693223141145763104853022918526e-7.]
Toliau rasime  :
 
= 0.5*(6.2449983677207123204232036062421 + 39/6.2449983677207123204232036062421) =
= 6.2449979983984091265040071378015.
Atėmę tikslią   reikšmę iš   reikšmės, gauname:
6.2449979983984091265040071378015 - 6.2449979983983982058468931209398 = 1.0920657114016861678930991073622e-14.
Taigi, gavome paklaidą   O santykinė paklaida   lygi
 
= (6.2449979983984091265040071378015 - 6.2449979983983982058468931209398)/6.2449979983983982058468931209398 =
= 1.7487046620059110065547770263338e-15.
T. y.  


  • Apskaičiuosime   Iš (3.16) formulės   Pagal (3.17)   Todėl   Tada   Iš čia gauname, kad  
Kadangi   tai  
Toliau randame   pagal (3.18) formulę:
 
Skaičių   randame pagal (3.10) rekurentinę formulę:
 
= 0.5*(1.375 + 1.4545454545454545454545454545455) = 0.5 * 2.8295454545454545454545454545455 =
= 1.4147727272727272727272727272727.
Toliau rasime  :
 
= 0.5*(1.4147727272727272727272727272727 + 2/1.4147727272727272727272727272727) =
= 1.4142136728733114275282949981745.
[1.4142136728733114275282949981745 - 1.4142135623730950488016887242097 = 0.0000001105002163787266062739648  ]
Toliau rasime  :
 
= 0.5*(1.4142136728733114275282949981745 + 2/1.4142136728733114275282949981745) =
= 1.4142135623730993657935457387426.
Atėmę tikslią   reikšmę iš   reikšmės, gauname:
1.4142135623730993657935457387426 - 1.4142135623730950488016887242097 = 4.316991857014532913283559342618e-15.
Santykinė paklaida yra tokia:
 
=(1.4142135623730993657935457387426 - 1.4142135623730950488016887242097)/1.4142135623730950488016887242097 =
= 3.0525742164220827729222598916484e-15.
Gavome, kad  


Šiaip, skaičiuojant su kompiuteriu, santikinę paklaidą   (arba  ) reikia padauginti iš 10, nes procesoriaus x87 FPU be eksponentės dirba su skaičiais nuo 1.00000000000000001 iki 9.99999999999999999. Tada nebus prarastas tikslumas, jei įvertinsime, kad FPU paklaida yra  

Šaknies traukimas iš didelių skaičių

keisti
Bet kokį skaičių a ( ) galima užrašyti taip:
 
Čia   skaičius v gali būti nulis arba teigiamas lyginis skaičius (v gali būti 0, 2, 4, 6, 8, 10 ir t. t.); skaičius j lygus arba nuliui arba vienetui.
Jeigu ištrauksime kvadratinę šaknį iš a, tai gausime:
 
Jegiu v nelygus nuliui, tai   bus sveikasis skaičius su dvigubai mažiau nulių nei pas   Jeigu   tai tereikia apskaičiuoti   kurį bus galima visada taikyti (2) formulėje. Vadinasi, tereikia mokėti greitai ištraukti šaknį iš skaičiaus p.
1) Jeigu   tai pagal (3.16) formulę
 
iš čia  
Tada pagal (3.18) formulę randame  :
 
Ir toliau, darant iteracijas, apskaičiuojamas   pagal (3.10) formulę:
 
2) Jeigu   tai pagal (3.16) formulę
 
iš čia   Tada  
Pagal (3.18) formulę randame  :
 
Matome, kad šiuo atveju artinio   formulė tokia pati kaip ir 1) atveju.
Toliau skaičiuojama kaip ir pirmu atveju.
3) Jeigu   tai pagal (3.16) formulę
 
iš čia   Tada  
Pagal (3.18) formulę randame  :
 
Toliau skaičiuojama kaip ir pirmu atveju.
4) Jeigu   tai pagal (3.16) formulę
 
iš čia   Tada  
Pagal (3.18) formulę randame  :
 
Matome, kad šiuo atveju artinio   formulė tokia pati kaip ir 3) atveju.
Toliau skaičiuojama kaip ir pirmu atveju.
Apibendrinant, skaičiaus   ( ) apskaičiavimui, taikoma   reikšmė
 
kai  
ir taikoma   reikšmė
 
kai  


  • Apskaičiuosime   Čia   Tada pagal (1) formulę
 
Pagal (2) formulę
 
Toliau randame   skaičiui  :
 
= 1.2083333333333333333333333333333.
[   1.2247448713915890490986420373529. ]
[1.2247448713915890490986420373529 - 1.2083333333333333333333333333333 = 0.0164115380582557157653087040196; tai yra ne santykinė paklaida, o reali paklaida.]
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(1.2083333333333333333333333333333 + 1.5/1.2083333333333333333333333333333) = 1.2248563218390804597701149425287.
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(1.2248563218390804597701149425287 + 1.5/1.2248563218390804597701149425287) = 1.2247448764620622240199548319682.
[1.2247448764620622240199548319682 - 1.2247448713915890490986420373529 = 0.0000000050704731749213127946153 =  ]
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(1.2247448764620622240199548319682 + 1.5/1.2247448764620622240199548319682) = 1.2247448713915890595945823395751.
Iš ką tik gautos   reikšmės atėmę   reikšmę, gauname:
1.2247448713915890595945823395751 - 1.2247448713915890490986420373529 = 0.0000000000000000104959403022222 =  
Santykinė paklaida yra tokia:
 
(1.2247448713915890595945823395751 - 1.2247448713915890490986420373529)/1.2247448713915890490986420373529 =
= 8.5698993703859497564530032133562e-18.
Taigi  
Iš anksčiau apskaičiuoto
 
= 1.2247448713915890595945823395751 * 10000 = 12247.448713915890595945823395751.
Atėmę tikslią   iš 12247.448713915890595945823395751, gauname paklaidą:
12247.448713915890595945823395751 - 12247.448713915890490986420373529 = 1.0495940302222154304017026259951e-13.
O santykinė paklaida skaičiui   yra
(12247.448713915890595945823395751 - 12247.448713915890490986420373529)/12247.448713915890490986420373529 =
= 8.5698993703859497564530032133562e-18.
Tokia pati, kaip skaičiui  


  • Apskaičiuosime   Čia   Tada pagal (1) formulę
 
Pagal (2) formulę
 
Šaknį iš 10 lengva apskaičiuoti (nes (4) formulė tinka skaičiams  ).
  3.1622776601683793319988935444327.
Toliau randame   skaičiui   pagal (4) formulę:
 
= 0.16666666666666666666666666666667*9.6 + 1.4166666666666666666666666666667 = 3.0166666666666666666666666666667.
[   3.0983866769659335081434123198259. ]
[3.0983866769659335081434123198259 - 3.0166666666666666666666666666667 = 0.0817200102992668414767456531592; tai yra ne santykinė paklaida, o reali paklaida.]
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(3.0166666666666666666666666666667 + 9.6/3.0166666666666666666666666666667) = 3.0994935543278084714548802946593.
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(3.0994935543278084714548802946593 + 9.6/3.0994935543278084714548802946593) = 3.0983868746074953885623653564026.
[3.0983868746074953885623653564026 - 3.0983866769659335081434123198259 = 0.0000001976415618804189530365767 =
 ]
Toliau pagal (3.10) formulę apskaičiuojame  :
 
= 0.5*(3.0983868746074953885623653564026 + 9.6/3.0983868746074953885623653564026) = 3.0983866769659398117763289613096.
Iš ką tik gautos   reikšmės atėmę   reikšmę, gauname:
3.0983866769659398117763289613096 - 3.0983866769659335081434123198259 = 0.0000000000000063036329166414837 =
 
Santykinė paklaida yra tokia:
 
(3.0983866769659398117763289613096 - 3.0983866769659335081434123198259)/3.0983866769659335081434123198259 =
= 2.0344887755631127106428103904763e-15.
Taigi  
Iš ankstesnių skaičiavimų
 
= 3.0983866769659398117763289613096 * 3.1622776601683793319988935444327 * 100000 = 979795.89711327323266266864962311.
Tiksli   reikšmė yra tokia:
  979795.89711327123927891362988236.
Atėmę tikslią   reikšmę iš 979795.89711327323266266864962311, gauname paklaidą:
979795.89711327323266266864962311 - 979795.89711327123927891362988236 = 0.00000000199338375501974075 =
 
Santykinė paklaida skaičiui   yra
(979795.89711327323266266864962311 - 979795.89711327123927891362988236)/979795.89711327123927891362988236 =
= 2.0344887755631126970242116177837e-15,
t. y. tokia pati (su 16 pirmų tokių pačių skaitmenų) kaip skaičiui  
[Čia kažkas negerai su tais 16 skaitmenų, nes iš viso ciferblate yra 32 skaitmenys... Jeigu įdėti (padaryti copy-paste) į kalkuliatorių tokį reiškinį:
(3.0983866769659398117763289613096 - 3.0983866769659335081434123198259)/3.0983866769659335081434123198259 -(979795.89711327323266266864962311 - 979795.89711327123927891362988236)/979795.89711327123927891362988236 =
tai gaunamas toks rezultatas:
= 1.3618598772692596082816173047622e-32.
Kažkokie dvigubi skaičiavimo standartai su "Windows 10" kaluliatorium... Gal po kokių nors dalybos iteracijų labai prasiranda tikslumas, nes ne visi skaitmenys Winows 10 kalkuliatoriuje rodomi (jų yra virš 40, gal apie 47 skaitmenys iš viso, iš kurių rodomi tik 32 skaitmenys). Nors gal ir ne tai, nes ten tik atimtis atliekama... Gal koks bug'as?
Bendrai, viskas teisingai, nes
2.0344887755631127106428103904763e-15 - 2.0344887755631126970242116177837e-15 = 1.36185987726926e-32.
Tai rodo, kad skaičiavimo tikslumas yra 32 skaitmenys, nes jų šituose skaičiavimuose tiek ir yra.]


Jeigu   tai pažymėję   galime, jei b didelis skaičius, apskaičiuoti   pagal pateiktą aukščiau būdą. Apskaičiavę   galime rasti   taip:
 
Tačiau toks   ( ) skaičiavimo būdas nėra ekonomiškas, nes reikia atlikti dvi [papildomas] dalybos operacijas.
Pateiksime ekonomiškesnį, greitesnį   skaičiavimo būdą. Jei   tai a galima užrašyti taip:
 
Čia   skaičius v gali būti nulis arba neigiamas lyginis skaičius (v gali būti 0, -2, -4, -6, ...); skaičius j lygus arba nuliui arba  
Jeigu ištrauksime kvadratinę šaknį iš a, tai gausime:
 
Jeigu   tai tereikia apskaičiuoti   kurį bus galima visada taikyti (6) formulėje. Vadinasi, tereikia mokėti greitai ištraukti šaknį iš skaičiaus p. O toliau jau lengva pagal (6) formulę surasti kam lygus   Kaip rasti   pateikta aukščiau.
Kiek pamenu, skaičiau, kad jeigu norima padauginti skaičių dvejetainėje sistemoje iš 2, tai reikia visus bitus pastumti per vieną bito poziciją į kairę. O jeigu norima skaičių dvejetainėje sistemoje padalinti iš 2, tai reikia visus bitus pastumti viena bito pozicija į dešinę. Tokiu budu, jeigu skaičius j nelygus nuliui, tai reikia skaičių a padauginti iš 10, jei 0<a<1 (arba padauginti iš 0.1, jei a>1). Tada skaičius v bus lyginis skaičius. Toliau norint padalinti v iš 2, tereikia rodiklio v visus bitus pastumti per vieną bitą į dešinę. Taip mes gausime v/2. Ir nereikia procesoriaus FPU daryti sudetingų eksponentės dalybos operacijų (skaičiuojant šaknį iš kokio nors skaičiaus).
Lieka tik paslaptis kodėl procesorių FPU šaknies traukimo operacijai sunaudoja tiek pat arba tik apie 1.5 karto (priklausomai nuo procesoriaus) daugiau ciklų negu dalybos operacijai. Net jeigu artinį   kažkokiu budu galima gauti su santykine paklaida apie   tai vis tiek reikės dviejų iteracijų ir to pasekoje reikės dviejų dalybos operacijų (kiekvienoje iteracijoje yra viena dalybos operacija). Kad užtektų apskaičiuoti   iš vienos iteracijos, artinio   santykinė paklaida   turi būti apie   (kad gauti   su santykine paklaida apie  ). Jeigu kažkokiu budu galima pagal skaičių p pažiūrėt į kažkokią artinių   lentelę, tai ta lentelė turės apie milijardą artinių ir užims apie   10 GB, t. y. apie 10 gigabaitų. Į procesorių akivaizdu to neįstatysi, tuo labiau, kad, pavyzdžiui, Pentium II/III naudojo 17...38 ciklus dalybos operacijai ir 27...50 ciklų šaknies traukimo operacijai (tik apie 1.5 karto daugiau ciklų šakniai nei dalybai). Tais laikais ir 1 MB (megabaito) kokios nors atminties (pvz., cache atminties) įdėjimas į procesorių buvo techniškai neįmanomas ar sunkiai pasiekiamas dalykas.
Kadangi artinio   skaičiavimui [pateiktam aukščiau] nereikia daryti dalybos operacijos, tai galbūt yra, tarkim, apie 100 ar 1000 artinio   skaičiavimo grupių skaičiui   Kaip matėme, tik dviejų grupių (1<p<4 ir  ) užtenka   skaičiavimui, kad gauti pirmo artinio   santykinę paklaidą   Jeigu sukurti apie 10 tokių artinio   grupių (1<p<2, 2<p<3, 3<p<4, ..., 9<p<10) arba apie 100 tokių artinio   grupių (1<p<1.1, 1.1<p<1.2, 1.2<p<1.3, ..., 9.9<p<10), tai peršasi mintis, kad 10-iai grupių tikslumas gali būti apie   o šimtui tokių grupių santykinės paklaidos   tikslumas gali būti apie   Tik tai gali užimti darbo suradimui artinio   formulės kiekvienai grupei (tokia formulė padidinanti tikslumą siauro/trumpo intervalo grupei turėtų egzistuot matematiškai mąstant ir lažinantis...). Tik gal tikslumo padidėjimas gali būti ne toks žymus, kai grupių padaugėja apie 10 kartų (arba 100 kartų), nežinau...
Kitas klausimas yra, kaip kiekvieną skaičių p nusiusti į jį atitinkančią vieną iš 10 (ar vieną iš 100) grupę (kad paskui gauti artinį  ). Programuotojas sakytų, kad reikia vidutiniškai praifint 5 kartus, jei yra 10 grupių (arba ~50 kartų, jei yra 100 grupių). Pavyzdžiui, jei yra skaičius 3.5346, tai pirmą kartą paklaust ar skaičius p [jei yra 10 grupių] yra mažiau už 2, antrą kartą paklaust ar skaičius p yra mažiau už 3 ir trečią kartą palyginus 3.5346 su 4 nustatoma, kad skaičius p patenka į trečią grupę, nes yra mažiau už 4. Bet su ifinimais šaknies skaičiavimai bus dar ilgesni. Todėl su tranzistoriais galima sukurt painią schemą, kuri, jeigu skaičiaus p pirmas skaitmuo yra 3, siunčia skaičių p į trečią grupę, kurioje skaičiuoja artinį   skaičiams nuo 3 iki 4 ir gauna numanomai minėtą tikslumą   O jeigu skaičiaus p pirmas skaitmuo yra 4, tai siunčiasi per tą loginę schemą toks skaičius į ketvirtą grupę (į kurią įeina skaičiai nuo 4 iki 5) ir t. t. Kas ten žino, gal taip ir randamas [skaičiaus p]   artinys (apie   tikslumu) naudojant apie 100 tokių grupių. Ir tada užtenka tik vienos iteracijos (t. y. užtenka vienos dalybos operacijos [kuri yra iteracijoje]), kad gauti apie   tikslumą.
Pastebėsime, kad jeigu artinys   tai pagal (3.10) formulę
 
Čia aiškinama kaip dalybos operacija vyksta procesoriuje:
https://www.quora.com/How-is-integer-division-implemented-in-Computer-Hardware
https://en.wikipedia.org/wiki/Division_algorithm#SRT_division
Pavyzdžiui čia:
https://electronics.stackexchange.com/questions/22410/how-does-division-occur-in-our-computers
skaitant, gali būti neaišku kas yra "reciprocal", "denominator", "numerator". Jie yra atitinkamai 1/x, vardiklis, skaitiklis.
Šis tekstas:
"For floating point numbers, however, it may be quicker to first compute the reciprocal of the denominator and then multiply that times your numerator."
verčiamas per Google translate taip:
"Tačiau slankiojo kablelio skaičiams gali būti greičiau pirmiausia apskaičiuoti vardiklio atvirkštinį skaičių ir tada padauginti jį iš skaitiklio."
Ten pat duotas pavyzdys, jeigu norima apskaičiuoti 1/3.5. Iš pradžių spėjama, koks turi būti g, kad g*3.5 būtų lygus 1. Spėjimas, kad g=0.3. Tada g*3.5=0.3*3.5=1.05. Tada toliau naudojama pagerinta formulė g'=g(2-gd). Gauname 0.3*(2-1.05)=0.285. Jau gana arti 1/3.5=0.28571428571428571428571428571429. Toliau kartojamas procesas: 0.285*(2-0.285*3.5)=0.2857125. Dar toliau: 0.2857125*(2-0.2857125*3.5)=0.285714285703125. Paklaida yra:
0.28571428571428571428571428571429 - 0.285714285703125 = 0.00000000001116071428571428571429  
Čia
https://www.reddit.com/r/explainlikeimfive/comments/yc5qkp/eli5_how_does_a_computer_do_division_efficiently/
dar papildomai rašo apie šitą būdą, kuris ką tik buvo pateiktas skaičiuot 1/D, o suradus kam tai lygu, galima paskui sužinot kam lygu N/D, padauginus N iš apskaičiuoto 1/D (kai D=p, t. y. kai 1<D<10, o jei D>10, tai skaičiaus D eksponentės rodiklis atimamas iš skaičiaus N eksponentės rodiklio...).
Šito metodo išvedimas aprašytas angliškoje Vikipedijoje: https://en.wikipedia.org/wiki/Division_algorithm#Newton–Raphson_division
Jame naudojamas Niutono metodas (liesinių metodas), kuris taikomas polinomo realiųjų šaknų apytikslėms reikšmėms rasti.

Greitas šaknies iš skaičiaus a traukimo būdas

keisti
Parodysime praktiškai greičiausią kvadratinės šaknies traukimo būdą. Šitas būdas paremtas Niutono metodu (liestinių metodu). Todėl pirma trumpai apžvelgsime Niutono metodą.
Niutono metodas. Naudojant Niutono metodą galima rasti polinomo (arba kokios nors funkcjos) f(x) šaknį (sprendinį) bet kokiu norimu tikslumu. Nagrinėkime atkarpą [a; b], kurioje yra viena šaknis c (taške c funkcija f(x) kerta ašį Ox). Toliau, priklausomai nuo to ar funkcija f(x) atkarpoje [a; b] įgaubta ar išgaubta bei priklausomai nuo to ar funkcija f(x) didėja ar mažėja atkarpoje [a; b], pasirenkamas tinkamas atkarpos vienas iš galų (a arba b). Pažymėkime tą galą   (  arba  ). Toliau taške   surandame funkcijos f(x) liestinės lygtį, kuri atrodo taip:
 
Arba taip:
 
Toliau randamas liestinės y(x) susikirtimo taškas su Ox ašimi. Tą tašką pažymėkime (x; y)=(d; f(d))=(d; 0). Įstatę šio taško koordinates į (1) lygtį gausime:
 
 
 
Dabar turime siauresnį intervalą, kuriame ant Ox ašies yra šaknis c (per kurią pereina funkcjos f(x) grafikas). Ir dabar reikšmė   yra arčiau šaknies c. Pakartoję šį procesą rasime tašką   esantį dar arčiau prie c taško (ant Ox ašies):
 
Taip kartodami (2) formulę galime labai tiksliai rasti funkcijos f(x) susikirtimo su Ox ašimi tašką c. Šios formulės paklaida mažėja kvadratu po kiekvienos iteracijos, kai   konverguoja į tašką c (po kiekvienos iteracijos, tikslumas didėja daug greičiau, nei jeigu spėliotume šaknį c, dalindami intervalą [a; b] kaskart per pusę ir tikrindami ar skirtinguose intervalų pusėse funkcija f(x) turi priešingus ženklus). Išsamiai apie Niutono metodą galima paskaityti aukštosios algebros arba matematinės analizės vadovėliuose.


Čia pasakojama apie   skaičiavimo metodus: https://www.quora.com/How-do-computers-calculate-square-roots
O čia
https://en.wikipedia.org/wiki/Fast_inverse_square_root#Newton's_method
aprašoma, kaip apskaičiuoti   Kai apytiksliai apskaičiuojama   reikia gautą rezultatą padauginti iš a. Tada ir gausime   Be to   rezultatas yra net naudingesnis, nes nereikia dalinti   iš a, kad gauti  
Pereikime prie   skaičiavimo algoritmo, kuris vadinasi Niutono metodu [šaknies skaičiavimui]. Pažymėkime   o skaičių a pažymėkime per x. Tada
 
Jeigu   yra apytikslė skaičiaus y reikšmė, tai   yra dar tikslesnė skaičiaus y reikšmė (pagal liestinių metodą):
 
Surandame f(y) išvestinę:
 
 
Toliau įstatome   ir   į (3) formulę:
 
 
 
Gavome rekurentinę formulę   reikšmei skaičiuoti:
 

Pavyzdžiai

keisti
  • Apskaičiuosime   ir rasime kam lygus  
Pirmiausia turime žinoti   apytikslią reikšmę. Tą reikšmę procesoriaus FPU gali gauti iš tam tikros lentelės, kuri galbūt yra procesoriaus L1 Data cache'e arba L2 cache. Tiksli   reikšmė yra tokia:
  1.5165750888103101108513650872564.
O   0.65938047339578700471798482054627.
Mes paimsime, kad   Tada pagal formulę
 
rasime
 
Toliau pagal (4) formulę rasime  :
 
[0.65938047339578700471798482054627 - 0.6592433044896 = 0.00013716890618700471798482054627  ]
Toliau pagal (4) formulę rasime  :
 
= 0.6592433044896*(3 - 2.3*0.6592433044896^2)/2 = 0.65938043059651203399501910136126.
[0.65938047339578700471798482054627 - 0.65938043059651203399501910136126 =
= 0.00000004279927497072296571918501  ]
Toliau pagal (4) formulę rasime  :
 
= 0.65938043059651203399501910136126*(3 - 2.3*0.65938043059651203399501910136126^2)/2 = 0.65938047339578283767489142997287.
Taigi,   paklaida yra tokia:
0.65938047339578700471798482054627 - 0.65938047339578283767489142997287 =
= 0.0000000000000041670430933905734  
Po 4 iteracijų gavome paklaidą mažesne nei  
Dabar galime rasti a šaknyje:
  2.3*0.65938047339578283767489142997287 = 1.5165750888103005266522502889376.
[1.5165750888103101108513650872564 - 1.5165750888103005266522502889376 = 0.0000000000000095841991147983188 =
 ]
Pažiūrėkime kaip konverguoja   į   iš dešinės pusės, kai   parenkamas taip, kad  
Taigi parinkime   Tada
 
[0.65938047339578700471798482054627 - 0.6593796 = 0.00000087339578700471798482054627  ]
Toliau pagal (4) formulę rasime  :
 
  1.3187609467881033886272/2 = 0.6593804733940516943136.
[0.65938047339578700471798482054627 - 0.6593804733940516943136 = 0.00000000000173531040438482054627  ]
Toliau pagal (4) formulę rasime  :
 
0.6593804733940516943136*(3 - 2.3*0.6593804733940516943136^2)/2 = 0.65938047339578700471797797024742.
Paklaida lygi
0.65938047339578700471798482054627 - 0.65938047339578700471797797024742 =
= 0.00000000000000000000000685029885  
Po 3 iteracijų gavome paklaidą mažesne nei  
Šį kartą, parenkant   iš dešinės,   reikšmė buvo daug tikslesnė negu anksčiau. Bet teoriškai Niutono metodas (liestinių metodas) bent jau polinomams gali greitai konverguoti tik iš vienos šaknies y pusės. Čia gi greitas konvergavimas į   vyksta tiek iš kairės pusės, tiek iš dešinės pusės, kas atrodo kaip prieštaravimas liestinių metodo teorijai. Gal greito konvergavimo tik iš vienos pusės taisyklė taikoma tik polinomams ir kai kurioms funkcjoms, o ši funkcija   yra išimtis.
Dabar galime rasti a šaknyje:
  2.3*0.65938047339578700471797797024742 = 1.5165750888103101108513493315691.
[1.5165750888103101108513650872564 - 1.5165750888103101108513493315691 = 0.0000000000000000000000157556873 =
 ]


  • Apskaičiuosime   ir rasime kam lygus  
Tiksli   reikšmė yra tokia:
  2.4083189157584590960256482060757.
O   0.41522739926869984414235313897857.
Mes paimsime, kad   Tada pagal (4) formulę
 
[0.41522739926869984414235313897857 - 0.4144 = 0.00082739926869984414235313897857  ]
Toliau pagal (4) formulę rasime  :
 
= 0.4144*(3 - 5.8*0.4144^2)/2 = 0.4152249278464.
[0.41522739926869984414235313897857 - 0.4152249278464 = 0.00000247142229984414235313897857  ]
Toliau pagal (4) formulę rasime  :
 
= 0.4152249278464*(3 - 5.8*0.4152249278464^2)/2 = 0.41522739924663512944560082817282.
[0.41522739926869984414235313897857 - 0.41522739924663512944560082817282 = 0.00000000002206471469675231080575 =
 ]
Toliau pagal (4) formulę rasime  :
 
= 0.41522739924663512944560082817282*(3 - 5.8*0.41522739924663512944560082817282^2)/2 = 0.41522739926869984414059439797726.
[0.41522739926869984414235313897857 - 0.41522739926869984414059439797726 = 0.00000000000000000000175874100131 =
 ]
Tada   5.8*0.41522739926869984414059439797726 = 2.4083189157584590960154475082681.
[2.4083189157584590960256482060757 - 2.4083189157584590960154475082681 = 0.0000000000000000000102006978076 =
 ]
Po 4 iteracijų gavome paklaidą mažesne nei   (beveik  ).
Dabar pažūrėsime kaip konverguos   į   iš dešinės pusės (kai  ). Parenkame   Tada pagal (4) formulę
 
[0.41522739926869984414235313897857 - 0.4151448 = 0.00008259926869984414235313897857  ]
Toliau pagal (4) formulę rasime  :