Кіріспе
Квадрат түбірлерді есептеу алгоритмдері
Оң нақты санның теріс емес квадрат түбірін табу әдістері – бұл оны шамалау алгоритмдері. Табиғи сандардың толық квадраттардан басқа барлық квадрат түбірлері иррационал болғандықтан, квадрат түбірлерді көбінесе белгілі бір шекті дәлдікпен ғана есептеуге болады: мұндай әдістер әдетте күрделене түсетін шамалаулар тізбегін құрастырады. Көптеген квадрат түбірді есептеу әдістері итеративті болып келеді: бастапқы шамалау таңдалғаннан кейін, белгілі бір тоқтату шарты орындалғанша итеративті жақсарту жүргізіледі. Бір жақсарту схемасы – Герон әдісі, бұл Ньютон әдісінің ерекше жағдайы. Егер бөлу көбейтуден әлдеқайда қиын болса, кері квадрат түбірді есептеу ыңғайлы болуы мүмкін. Квадрат түбірін цифр бойынша немесе Тейлор қатарын пайдалану арқылы есептеудің басқа да әдістері бар. Квадрат түбірлердің рационал шамаларын үздіксіз бөлшектерді пайдалану арқылы табуға болады. Қолданылатын әдіс қажетті дәлдікке, қолда бар құралдар мен есептеу қуатына байланысты. Әдістерді шамамен есептеуге жарамды, қағаз мен қаламды қажет ететін және цифрлік электрондық компьютерде немесе басқа есептеу құрылғысында іске асырылатын бағдарламалар ретінде жүзеге асырылатын әдістер деп жіктеуге болады. Алгоритмдер конвергенцияны (белгіленген дәлдікке жету үшін қажетті итерациялар саны), жеке операциялардың (мысалы, бөлу) немесе итерациялардың есептеу күрделілігін және қателердің таралуын (соңғы нәтиже дәлдігі) ескере алады. Қағаз бен қаламмен жүзеге асырылатын синтетикалық бөлу және қатарларды кеңейту сияқты кейбір әдістер бастапқы мәнді қажет етпейді. Кейбір қолданбаларда бүтін сан квадрат түбірі қажет, яғни квадрат түбірі ең жақын бүтін санға дейін дөңгеленеді немесе қысқартылады (мұндай жағдайда өзгертілген процедура қолданылуы мүмкін).
square roots can usually only be computed to some finite precision: these methods typically construct a series of increasingly accurate approximations. Most square root computation methods are iterative: after choosing a suitable initial estimate of , an iterative refinement is performed until some termination criterion is met. One refinement scheme is Heron's method, a special case of Newton's method. If division is much more costly than multiplication, it may be preferable to compute the inverse square root instead. Other methods are available to compute the square root digit by digit, or using Taylor series. Rational approximations of square roots may be calculated using continued fraction expansions. The method employed depends on the needed accuracy, and the available tools and computational power. The methods may be roughly classified as those suitable for mental calculation, those usually requiring at least paper and pencil, and those which are implemented as programs to be executed on a digital electronic computer or other computing device. Algorithms may take into account convergence (how many iterations are required to achieve a specified precision), computational complexity of individual operations (i. e. division) or iterations, and error propagation (the accuracy of the final result). A few methods like paper and pencil synthetic division and series expansion, do not require a starting value. In some applications, an integer square root is required, which is the square root rounded or truncated to the nearest integer (a modified procedure may be employed in this case).
Бастапқы баға
Көптеген итеративтік квадрат түбір алгоритмдері бастапқы тұқымдық мәнді қажет етеді. Тұқым нөлден өзгеше оң сан болуы керек; ол 1 мен, квадрат түбірі анықталуға тиіс санның арасында болуы керек, өйткені квадрат түбірі сол диапазон ішінде жатады. Егер тұқым түбірден алыс болса, алгоритмге көбірек итерациялар қажет болады. Егер бастапқы мән (немесе) болса, онда шамамен итерациялар тек түбірдің шамасын анықтауға жұмсалады. Сондықтан, жақсы бастапқы бағалау пайдалы, ол шектеулі дәлдікке ие болғанымен, есептеуге оңай. Жалпы алғанда, бастапқы бағалау неғұрлым жақсы болса, конвергенция соғұрлым жылдам болады. Ньютон әдісі (бавилондық немесе Герон әдісі деп те аталады) үшін түбірден сәл үлкен тұқым, түбірден сәл кіші тұқымға қарағанда сәл жылдам конвергенцияға ие болады. Жалпы алғанда, бағалау түбірді қамтитын белгілі бір аралық бойынша жасалады (мысалы, ). Бағалау – интервал бойынша функциялық жуықтаудың нақты мәні. Жақсырақ бағалау алу үшін интервалдың шектерін нақтылау немесе жақсы функциялық жуықтау табу қажет. Соңғысы көбінесе жуықтауда жоғары дәрежелі полиномды пайдалануды білдіреді, бірақ барлық жуықтаулар полиномдық емес. Бағалаудың кең таралған әдістеріне скалярлық, сызықтық, гиперболалық және логарифмикалық әдістер жатады. Ақыл-ойымен немесе қағаз бен қарындашпен бағалау үшін ондық жүйе көбінесе қолданылады. Компьютерлік бағалау үшін екілік жүйе ыңғайлырақ. Бағалау кезінде экспонента мен мантисса әдетте бөлек қарастырылады, өйткені сан ғылыми нотацияда беріледі.
Ондық бағалар
Көбінесе сан ғылыми жазбада былай көрсетіледі: , мұнда және n – бүтін сан, ал мүмкін болатын квадрат түбірлердің диапазоны: , мұнда .
Сызықтық бағалау
Жақсырақ бағалау, және қолданылатын стандартты әдіс – функцияның кішкентай доғадағы сызықтық жуықтауы. Жоғарыда айтылғандай, саннан негіздің дәрежелерін шығарып алып, аралықты қысқартсақ, доғаны кесіп өтетін секунтық түзу немесе доға бойындағы бір нүктедегі жанама түзу жуықтау ретінде қолданылуы мүмкін, бірақ доғаны кесіп өтетін ең кішкентай квадраттардың регрессиялық түзуі дәлірек болады. Ең кішкентай квадраттардың регрессиялық түзуі бағалау мен функция мәні арасындағы орташа айырманы азайтады. Оның теңдеуі – коэффициенттерді есептеуді жеңілдету үшін қайта реттеу және дөңгелету, бұл y=x² функциясын бір сызықтық жуықтау арқылы алуға болатын орташа ең жақсы бағалау. Оның максималды абсолютті қатесі 1,2 (a=100 болғанда) және максималды салыстырмалы қатесі 30% (S=1 және 10 болғанда). Бұл формула үшін кез келген тұрақты сан (1-ге қосылған) және кішкентай түзету қанағаттанарлық бағалау береді, сондықтан нақты санды жаттап алудың қажеті жоқ. Бір түзуді қолданып (дөңгеленген немесе дөңгеленбеген) жуықтау бір маңызды цифрдан кем; салыстырмалы қате 1/22-ден үлкен, сондықтан 2 биттен кем ақпарат беріледі. Дәлдік өте шектеулі, себебі ауқым екі разрядқа жетеді, бұл осы типтегі бағалау үшін өте үлкен. Көп бөлікті сызықтық жуықтау арқылы жақсырақ бағалау алуға болады: бірнеше түзу сегменттері, олардың әрқайсысы бастапқы доғаның кіші бөлігіне жуықтайды. Қолданылған түзу сегменттерінің саны неғұрлым көп болса, жуықтау соғұрлым жақсы болады. Ең көп қолданылатын әдіс – жанама түзулерді пайдалану; маңызды таңдаулар – доғаны қалай бөлу және жанама нүктелерді қайда орналастыру. y=1-ден y=100-ге дейінгі доғаны бөлудің тиімді жолы геометриялық: екі аралық үшін аралықтардың шекаралары бастапқы аралықтардың шекараларының квадрат түбіріне тең, 1×100, яғни [1,] және [,100]. Үш аралық үшін шекаралар 100-дің куб түбіріне тең: [1,], [, 2] және [2,100] және т.б. Екі аралық үшін = 10, бұл өте ыңғайлы сан. Жанама түзулерді алу оңай, және олар x= және x= нүктелерінде орналасқан. Олардың теңдеулері: және Инверсия арқылы квадрат түбірлер: және Сондықтан үшін: Максималды абсолютті қателер аралықтардың жоғарғы нүктелерінде, a=10 және 100 нүктелерінде болады, және олар тиісінше 0,54 және 1,7-ге тең. Максималды салыстырмалы қателер аралықтардың соңғы нүктелерінде, a=1, 10 және 100 нүктелерінде болады, және екі жағдайда да 17%-қа тең. 17% немесе 0,17, 1/10-нан үлкен болғандықтан, бұл әдіс ондық цифрдан кем дәлдік береді.
That is the best estimate on average that can be achieved with a single piece linear approximation of the function y=x2 in the interval It has a maximum absolute error of 1.2 at a=100, and maximum relative error of 30% at S=1 and 10. To divide by 10, subtract one from the exponent of , or figuratively move the decimal point one digit to the left. For this formulation, any additive constant 1 plus a small increment will make a satisfactory estimate so remembering the exact number isn't a burden. The approximation (rounded or not) using a single line spanning the range is less than one significant digit of precision; the relative error is greater than 1/22, so less than 2 bits of information are provided. The accuracy is severely limited because the range is two orders of magnitude, quite large for this kind of estimation. A much better estimate can be obtained by a piece wise linear approximation: multiple line segments, each approximating some subarc of the original. The more line segments used, the better the approximation. The most common way is to use tangent lines; the critical choices are how to divide the arc and where to place the tangent points. An efficacious way to divide the arc from y = 1 to y = 100 is geometrically: for two intervals, the bounds of the intervals are the square root of the bounds of the original interval, 1×100, i. e. [1,] and [,100]. For three intervals, the bounds are the cube roots of 100: [1,], [, 2], and [ 2,100], etc. For two intervals, = 10, a very convenient number. Tangent lines are easy to derive, and are located at x = and x = Their equations are: and Inverting, the square roots are: and Thus for :
The maximum absolute errors occur at the high points of the intervals, at a=10 and 100, and are 0.54 and 1.7 respectively. The maximum relative errors are at the endpoints of the intervals, at a=1, 10 and 100, and are 17% in both cases. 17% or 0.17 is larger than 1/10, so the method yields less than a decimal digit of accuracy.
Гиперболалық бағалаулар
Кейбір жағдайларда гиперболалық бағалаулар тиімді болуы мүмкін, өйткені гипербола да дөңгелек қисық болып табылады және түзу сызықтан гөрі Y = x2 доғасы бойымен жақсырақ орналасуы мүмкін. Гиперболалық бағалаулар есептеу жағынан күрделірек, өйткені олар міндетті түрде қалқыма бөлуді қажет етеді. [Белгілі бір] интервалдағы x2 үшін жақын оңтайлы гиперболалық жуықтау y=190/(10x)^20 болады. Транспозицияласақ, квадрат түбір x = 190/(y+20)+10 болады. Осыған сәйкес:
Қалқыма бөлу тек бір ондық таңбаға дейін дәл болуы керек, өйткені бағалаудың жалпы дәлдігі де сондай және оны есептеуде санақта жасауға болады. Гиперболалық бағалау скалярлық немесе сызықтық бағалауларға қарағанда орташа есеппен жақсырақ. Оның максималды абсолютті қатесі 100-де 1,58, ал максималды салыстырмалы қатесі 10-да 16,0%-ды құрайды. Ең нашар жағдайда, a=10 болғанда, бағалау 3,67-ге тең. Егер 10 санынан бастап бірден Ньютон-Рафсон итерацияларын қолданса, гиперболалық бағалаудың дәлдігінен асып түсу үшін екі итерация қажет болады, нәтижесі 3,66 болады. 75 сияқты типтік жағдайда гиперболалық бағалау 8,00-ге тең, ал 75-тен басталатын 5 Ньютон-Рафсон итерациясы толыққанды нәтиже алу үшін қажет болады.
Бахшали әдісі
Квадрат түбірін табудың бұл әдісі Бахшали қолжазбасы деп аталатын ежелгі үнді қолжазбасында сипатталған. Бұл x0-дан басталатын Вавилон әдісінің екі итерациясына тең. Осылайша, алгоритм төртінші дәрежелі конвергентті, яғни әр итерацияда шамалаудың дұрыс цифрлары шамамен төрт есеге артады. Қазіргі нотацияны қолдана отырып, бастапқы ұсынылым былай: есептеу үшін, болып алғанда бастапқы шамалауды қабылдаңыз. Содан кейін, кезегімен итерациялаңыз:
Бұл әдісті бүтін саннан бастау арқылы квадрат түбірге рационалды шамалау құру үшін қолдануға болады. Егер бүтін сан -қа жақын болу үшін таңдалса, ал абсолюттік мәні ең аз айырмашылық болса, онда бірінші итерацияны былай жазуға болады:
Бахшали әдісін кез келген түбірді есептеу үшін, соның ішінде бөлшекті түбірлерді есептеу үшін де жалпылауға болады.