Методи за изчисляване на квадратни корени

Методите за изчисляване на квадратни корени са изчислителни алгоритми за изчисляване на приблизителни стойности на главните (или неотрицателни) квадратни корени (обикновено обозначени като ${\sqrt {S}}$ , ${\sqrt[{2}]{S}}$ или $S^{1/2}$ ) на реално число. Аритметично означава, че за дадено число $S$ процедурата намира число, което, умножено по себе си, дава $S$ . Алгебрично това означава процедура за намиране на неотрицателен корен на уравнението $x^{2}-S=0$ . Геометрично това означава построяване на страната на квадрат с дадена площ.

Всяко положително реално число има два корена.^[1] Главната стойност на квадратния корен на повечето положителни реални числа е ирационално число с безкрайна поредица от десетични цифри. В резултат на това, десетичното представяне на всеки такъв квадратен корен може да се изчисли само приблизително с крайна точност (десетични знаци). Въпреки това, дори ако вземем корена от точен квадрат на цяло число, така че резултатът да има крайно представяне, някои процедури, използвани за изчисляване на корена, могат да върнат само серия от приближения с нарастваща точност.

Вместо десетично или двоично разлагане може да се използва представяне на реално число с верижна дроб. Това представяне има свойството, че квадратният корен на всяко рационално число (което не е точен квадрат) има период, т.е. периодично разлагане, подобно на това как рационалните числа имат повтарящо се разлагане в десетичната бройна система.

Повечето общоприети аналитични методи са итеративни и се състоят от две стъпки: намиране на подходяща начална стойност, последвано от итеративно уточняване, докато се достигне определен критерий за спиране. Началната стойност може да бъде всяко число, но ако е по-близо до крайната стойност, са необходими по-малко итерации. Най-известният и програмируем метод е методът на Нютон, който се основава на изчисляване на производната. Няколко метода, като например просто ръчно деление по метода на Хорнер или разлагане в редица, не изискват задаване на начална стойност. Някои приложения изискват намиране на корен квадратен от цяло число, който е корен квадратен, закръглен до най-близкото цяло число (в този случай може да се използва модифицирана процедура).

Използваният метод зависи от това как ще се използва резултатът (т.е. колко точен трябва да бъде резултатът) и от наличните ресурси. Методите могат грубо да се разделят на такива, които могат да се изпълнят наум, такива, които изискват молив и хартия, или такива, които се реализират като програма и се изпълняват на компютри или други изчислителни устройства. Могат да се вземат предвид скоростта на конвергенция (колко итерации са необходими за постигане на дадена точност), изчислителната сложност на отделните операции (като деление) или итерации и разпределението на грешките (точността на резултата).

Процедурите за намиране на квадратни корени (по-специално корен от 2) са известни поне от времето на древен Вавилон (XVII век пр.н.е.). Методът на Херон^[2] от Египет през първи век е първият проверим алгоритъм за изчисляване на квадратни корени. Съвременните аналитични методи започват да се разработват след приемането на арабските цифри в Западна Европа през Ранния Ренесанс. Днес почти всички изчислителни устройства имат бърза и точна функция за квадратен корен под формата на вградена конструкция на език за програмиране, библиотечна функция или апаратен оператор, основани на процедурите, описани по-долу.

Начална оценка

Много итеративни алгоритми за квадратен корен изискват начална случайна стойност. Тази стойност трябва да е ненулево положително число. Тя трябва да е между 1 и $S$ , числото, чийто квадратен корен търсим, тъй като квадратният корен трябва да е в този диапазон. Ако началната стойност е много далеч от корена, алгоритъмът ще изисква повече итерации. Ако започнем с $x_{0}=1$ (или с $S$ ), ще са необходими приблизително ${\tfrac {1}{2}}\vert \log _{2}S\vert$ допълнителни итерации, само за да се получи редът на корена. Следователно е полезно да има груба оценка на корена, която може да има ниска точност, но е лесна за изчисляване. Като цяло, колкото по-точна е оценката, толкова по-бърза е конвергенцията. За метода на Нютон (наричан още вавилонски или метод на Херон), начална стойност, малко по-голяма от корена, води до по-бърза конвергенция от начална стойност, по-малка от корена.

Общо казано, оценката се разглежда върху произволен интервал, за който е известно, че съдържа корена (като $[x_{0},S/x_{0}]$ ). Получаването на по-добра оценка включва или получаване на по-тесни граници на интервала, или по-добро функционално приближение на $f(x)$ . Последното обикновено означава използване на многочлени от по-висок ред за приближение, въпреки че не всички приближения използват многочлени. Често срещаните методи за оценка включват скаларни, линейни, хиперболични и логаритмични. Десетичната бройна система обикновено се използва за умствена или хартиена оценка. Двоичната бройна система е по-подходяща за компютърна оценка. При оценка, експонентата и мантисата обикновено се третират отделно.

Метод на Херон

Вероятно първият алгоритъм, използван за апроксимация на ${\sqrt {S}}$ , е методът, известен като вавилонски метод, въпреки че няма преки доказателства, освен спекулации, че вавилонските математици са използвали този метод.^[3] Методът е известен още като метод на Херон, на името на гръцкия математик от първи век Херон, който дава първото изрично описание на метода в своя труд „Метрика“ от 60 г. сл. н.е.^[4] Основният принцип е, че ако $x$ е по-голямо от квадратния корен на неотрицателното реално число $S$ , тогава ${\tfrac {S}{x}}$ ще бъде по-малко от корена и обратно. Така че може разумно да се очаква средната стойност на тези две числа да е по-близо до корена (формално доказателство за този факт се основава на неравенството на средноаритметичната, средногеометричната и среднохармоничната стойност, което показва, че тази средна стойност винаги е по-голяма от квадратния корен, осигурявайки сходимост). Методът е еквивалентен на използването на метода на Нютон за решаване на уравнението $x^{2}-S=0$ .

По-точно, ако $x$ е първоначално приближение за ${\sqrt {S}}$ , а $\varepsilon$ е грешката в нашата оценка, така че $S=(x+\varepsilon )^{2}$ , можем да разкрием скобите и получаваме

\varepsilon ={\frac {S-x^{2}}{2x+\varepsilon }}\approx {\frac {S-x^{2}}{2x}},

тъй като

\varepsilon \ll x

.

Следователно можем да компенсираме грешката и да актуализираме старата си оценка.

x+\varepsilon \approx x+{\frac {S-x^{2}}{2x}}={\frac {S+x^{2}}{2x}}={\frac {{\frac {S}{x}}+x}{2}}\equiv x_{\text{обновен}}

Тъй като изчислената грешка не е точна, тя ще стане нашето следващо приближение. Процесът на актуализиране продължава, докато не се постигне желаната точност. Това е алгоритъм с квадратична сходимост, което означава, че броят на правилните цифри на приближението (грубо казано) се удвоява с всяка итерация. Работи по следния начин:

Започва се с произволна положителна начална стойност $x_{0}$ (колкото по-близо до истинския корен квадратен от числото $S$ , толкова по-добре).
Задава се $x_{n+1}$ да бъде средната стойност на $x_{n}$ и ${\tfrac {S}{x_{n}}}$ (използва се средноаритметичната стойност, за да се приближи средногеометричната).
Повтаря се стъпка 2, докато се постигне желаната точност.

Алгоритъмът може да бъде представен по следния начин:

x_{0}\approx {\sqrt {S}},

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

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

Алгоритъмът работи еднакво добре за $p$ -адични числа, но не може да се използва за идентифициране на реални квадратни корени с $p$ -адични квадратни корени. Може например да се конструира поредица от рационални числа, получени по този метод, която се сближава до +3 в случай на реални числа, но до -3 в 2-адични числа.

Пример

За да изчислим √S, където $S$ = 125348, с точност до шест значещи цифри, използваме метода за груба оценка, описан по-горе.

{\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{aligned}}

Следователно, ${\sqrt {125348}}\approx 354{,}045$ .

Сходимост

Да предположим, че x₀ > 0 и S > 0. Тогава за всяко n важи x_n > 0. Относителната грешка на x_n се определя като

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

,

а тогава

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

Сега може да се покаже, че

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

следователно

\varepsilon _{n+2}\leqslant \min \left\{{\frac {\varepsilon _{n+1}^{2}}{2}},{\frac {\varepsilon _{n+1}}{2}}\right\},

а от тук следва гарантирана сходимост и тя е квадратична.

Цифра по цифра

Това е метод за последователно търсене на всяка цифра от квадратния корен. Той е по-бавен от вавилонския метод, но има някои предимства.

По-лесен е за ръчно изчисляване.
Всяка намерена цифра от корена е известна като правилна, което означава, че няма да се промени в следващите итерации.
Ако представянето на квадратния корен има краен брой цифри, алгоритъмът завършва след последната намерена цифра. По този начин може да се използва за проверка дали дадено число е точен квадрат.
Алгоритъмът работи във всяка бройна система и, естествено, неговата производителност зависи от избраната бройна система.

Пръчките на Непeр включват допълнителни инструменти за реализиране на този алгоритъм. Алгоритъмът за изчисляване на n-тия корен цифра по цифра е обобщение на този метод.

Десетична бройна система

Записва се оригиналното число в десетична форма. Числата се записват подобно на алгоритъма за деление с дължина и, както при деление с дължина, квадратният корен ще бъде записан на горния ред. Групират се цифрите по двойки, започвайки с десетичната запетая, от двете ѝ страни. Десетичната запетая на квадратния корен ще бъде върху десетичната запетая на квадрата. Една цифра на квадратния корен се пише над двойката цифри на квадрата.

Започвайки от най-лявата позиция, изпълняваме следната процедура за всяка двойка цифри:

Сваляме най-високата двойка неизползвани цифри (ако всички цифри са използвани, написваме „00“) и ги записваме вдясно от остатъка от предишната стъпка (в първата стъпка няма остатък). С други думи, умножаваме остатъка по 100 и добавяме две цифри. Това ще бъде текущата стойност c.
Намираме p, y и x, както следва:

Нека ${\boldsymbol {p}}$ е част от вече намерения корен, игнорирайки десетичната запетая. (За първата стъпка, p = 0.)
Определяме най-голямата цифра ${\boldsymbol {x}}$ ${\boldsymbol {x}}$ такава, че $x(20p+x)\leqslant c$ $x(20p+x)\leqslant c$ . Ще използваме нова променлива ${\boldsymbol {y}}=x(20p+x)$ ${\boldsymbol {y}}=x(20p+x)$ .
- Отбелязваме, че $20p+x$ е просто удвоеното p с добавена цифрата x, отдясно.
- Отбелязваме, че x може да се намери чрез произволно предположение колко трябва да бъде c/(20•p), с пробно изчисление на y, след което x се коригира нагоре или надолу в зависимост от резултата.
Поставяме цифрата $x$ като следващата цифра на корена, т.е. над двойката цифри на квадрата, които току-що бяха свалени долу. Сега следващата стойност на p се получава от старата стойност по формулата $p\times 10+x$ .

Изваждаме y от c, за да образуваме нов остатък.
Ако остатъкът е нула и няма повече цифри за намаляване, алгоритъмът спира. В противен случай се връщаме към стъпка 1 и извършваме следващата итерация.

Примери

Намиране на квадратния корен от 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          Алгоритъмът завършва. Отговор: 12,34

Вижте също

Източници и бележки

↑ В допълнение към главния корен има отрицателен квадратен корен, равен по модул на главния корен, но с обратен знак, с изключение на случая на нула, когато има два еднакви корена, равни на нула.
↑ Итерационна формула на Херон: $\ \ x_{n+1}={\frac {1}{2}}~\left(x_{n}+{\frac {a}{x_{n}}}\right)\$ , където $a$ > 0 е фиксирано, а $x_{1}$ > 0 e произволно число.
Формулата задава намаляваща последователност, която при всеки избор на $x_{1}$ бързо клони към ${\sqrt {a}}$ , т.е. $\lim _{n\rightarrow \infty }x_{n}={\sqrt {a}}$ .
↑ Fowler, Robson 1998, с. 376.
↑ Heath 1921, с. 323 – 324.
↑ Alpha max plus beta min algorithm – версия на статията „Алгоритъм алфа max плюс бета min“ на английски език.

Външни препратки

Square roots by subtraction
Integer Square Root Algorithm by Andrija Radović
William E. Egbert – Personal Calculator Algorithms I : Square Roots, Hewlett-Packard Journal (май 1977) : стр. 22
Калкулатор за обучение на квадратни корени (на английски)

Литература

David Fowler, Eleanor Robson. Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context // Historia Mathematica. — 1998. — Т. 25, вып. 4. — doi:10.1006/hmat.1998.2209.
Thomas Little Heath. A History of Greek Mathematics. — Oxford: Clarendon Press, 1921. — Т. 2. — С. 323–324.
David Bailey, Jonathan Borwein. Ancient Indian Square Roots: An Exercise in Forensic Paleo-Mathematics // American Mathematical Monthly. — 2012. — Т. 119, вып. 8.
Miltonn Abramowitz, Irene A. Stegun. Section 3.7.26 // Handbook of mathematical functions with formulas, graphs, and mathematical tables. — Courier Dover Publications, 1964. — С. 17. — ISBN 978-0-486-61272-0.
J. C. Gower. A Note on an Iterative Method for Root Extraction // The Computer Journal. — 1958. — Т. 1 1, вып. 3.
M. Campbell-Kelly. Origin of Computing // Scientific American. — 2009. — Сентябрь.
Roger Cooke. Classical algebra: its nature, origins, and uses. — John Wiley and Sons, 2008. — ISBN 978-0-470-25952-8.
M. V. Wilkes, D. J. Wheeler, S. Gill. The Preparation of Programs for an Electronic Digital Computer. — Addison-Wesley, 1951.

[1] В допълнение към главния корен има отрицателен квадратен корен, равен по модул на главния корен, но с обратен знак, с изключение на случая на нула, когато има два еднакви корена, равни на нула.

[2] Итерационна формула на Херон: $\ \ x_{n+1}={\frac {1}{2}}~\left(x_{n}+{\frac {a}{x_{n}}}\right)\$ , където $a$ > 0 е фиксирано, а $x_{1}$ > 0 e произволно число.
Формулата задава намаляваща последователност, която при всеки избор на $x_{1}$ бързо клони към ${\sqrt {a}}$ , т.е. $\lim _{n\rightarrow \infty }x_{n}={\sqrt {a}}$ .

[Fowler,_Robson1998376-3] Fowler, Robson 1998, с. 376.

[Heath1921323&#32;–&#32;324-4] Heath 1921, с. 323 – 324.

[5] Alpha max plus beta min algorithm – версия на статията „Алгоритъм алфа max плюс бета min“ на английски език.

[1]

[2]

[3]

[4]

[5]