Введение
Алгоритмы вычисления квадратных корней
Методы вычисления квадратных корней — это алгоритмы для приближенного вычисления неотрицательного квадратного корня положительного действительного числа. Поскольку все квадратные корни натуральных чисел, за исключением полных квадратов, являются иррациональными, квадратные корни обычно можно вычислить только с некоторой конечной точностью: эти методы обычно строят последовательность все более точных приближений. Большинство методов вычисления квадратного корня являются итеративными: после выбора подходящей начальной оценки выполняется итеративное уточнение до тех пор, пока не будет достигнут определенный критерий останова. Одной из схем уточнения является метод Герона, частный случай метода Ньютона. Если деление значительно дороже умножения, может быть предпочтительнее вычислять обратный квадратный корень. Существуют также другие методы вычисления квадратного корня по одной цифре или с использованием ряда Тейлора. Рациональные приближения квадратных корней могут быть вычислены с использованием разложения в цепные дроби. Выбор метода зависит от требуемой точности, а также от доступных инструментов и вычислительных ресурсов. Методы можно примерно классифицировать как подходящие для устных вычислений, требующие как минимум бумаги и карандаша, и реализуемые в виде программ для выполнения на цифровом электронном компьютере или другом вычислительном устройстве. Алгоритмы могут учитывать сходимость (количество итераций, необходимых для достижения заданной точности), вычислительную сложность отдельных операций (например, деления) или итераций, а также распространение ошибок (точность конечного результата). Некоторые методы, такие как ручное деление в столбик и разложение в ряд, не требуют начального значения. В некоторых приложениях требуется целочисленный квадратный корень, который представляет собой квадратный корень, округленный или усеченный до ближайшего целого числа (в этом случае может быть использована модифицированная процедура).
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 = x2 на интервале . Она имеет максимальную абсолютную погрешность 1,2 при a = 100 и максимальную относительную погрешность 30% при S = 1 и 10. Чтобы разделить на 10, вычтите единицу из показателя степени , или, другими словами, сдвиньте десятичную точку на одну позицию влево. Для данной формулировки любая аддитивная константа, равная 1 плюс небольшое приращение, даст удовлетворительную оценку, поэтому запоминание точного числа не является обременительным. Приближение (округленное или нет), использующее одну линию, охватывающую диапазон , имеет точность менее одного значащего знака; относительная погрешность больше 1/22, поэтому предоставляется менее 2 бит информации. Точность сильно ограничена, поскольку диапазон составляет два порядка величины, что довольно много для такого рода оценки. Гораздо лучшую оценку можно получить с помощью кусочно-линейного приближения: нескольких линейных сегментов, каждый из которых приближает некоторый подинтервал исходного интервала. Чем больше линейных сегментов используется, тем лучше приближение. Наиболее распространенный способ – использовать касательные линии; ключевые моменты – как разделить участок и где разместить точки касания. Эффективный способ разделить участок от y = 1 до y = 100 – геометрически: для двух интервалов границы интервалов являются квадратными корнями границ исходного интервала, 1 × 100, то есть [1,] и [,100]. Для трех интервалов границы – кубические корни из 100: [1,], [, 2] и [2,100] и т.д. Для двух интервалов = 10, что является очень удобным числом. Касательные линии легко вывести, и они расположены в точках x = и x = . Их уравнения: и, соответственно. Обращаясь к извлечению квадратного корня, получаем: и. Таким образом, для :
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.
Максимальные абсолютные погрешности возникают в верхних точках интервалов, при 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 = x² по сравнению с прямой линией. Гиперболические оценки более сложны в вычислительном плане, так как неизбежно требуют операции деления с плавающей точкой. Близким к оптимальному гиперболическим приближением к x² на заданном интервале является y = 190 / (10x + 20). Выражая x, получаем квадратный корень x = 190 / (y + 20) + 10. Таким образом, для:
Операция деления с плавающей точкой должна быть точной лишь до одной десятичной цифры, поскольку общая точность оценки не превышает этого значения и может быть выполнена в уме. В среднем гиперболическая оценка превосходит скалярные или линейные оценки. Максимальная абсолютная погрешность составляет 1,58 при значении 100, а максимальная относительная погрешность – 16,0% при значении 10. В наихудшем случае при a = 10 оценка равна 3,67. Если начать с 10 и сразу применить итерации метода Ньютона-Рафсона, потребуется две итерации, дающие результат 3,66, прежде чем будет достигнута точность, превышающая точность гиперболической оценки. Для более типичного случая, например, при значении 75, гиперболическая оценка составляет 8,00, и для получения более точного результата потребуется 5 итераций метода Ньютона-Рафсона, начиная с 75.
Метод Бакшали
Этот метод нахождения приближения к квадратному корню был описан в древнеиндийском манускрипте, известном как манускрипт Бахшали. Он эквивалентен двум итерациям вавилонского метода, начинающимся с x0. Таким образом, алгоритм обладает четвертичной сходимостью, что означает, что число верных цифр в приближении примерно у quadruples с каждой итерацией. Оригинальная формулировка, используя современную нотацию, выглядит следующим образом: Для вычисления , пусть будет начальным приближением к . Затем последовательно выполняйте итерации по формуле:
Этот метод можно использовать для построения рационального приближения к квадратному корню, начиная с целого числа. Если целое число выбрано так, чтобы было близко к , а является разностью, абсолютное значение которой минимально, то первую итерацию можно записать как:
Метод Бахшали может быть обобщен для вычисления произвольного корня, включая дробные корни.