Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Декабрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Тригонометрия |
---|
Ссылка |
Законы и теоремы |
Исчисление |
В математике таблицы тригонометрических функций полезны во многих областях. До существования карманных калькуляторов , тригонометрические таблицы были необходимы для навигации , науки и техники . Расчет математических таблиц был важной областью исследований, которая привела к разработке первых механических вычислительных устройств .
Современные компьютеры и карманные калькуляторы теперь генерируют значения тригонометрических функций по запросу, используя специальные библиотеки математического кода. Часто эти библиотеки используют предварительно рассчитанные таблицы внутри и вычисляют требуемое значение, используя соответствующий метод интерполяции . Интерполяция простых справочных таблиц тригонометрических функций все еще используется в компьютерной графике , где может потребоваться лишь умеренная точность, а скорость часто имеет первостепенное значение.
Еще одно важное применение тригонометрических таблиц и схем генерации - это алгоритмы быстрого преобразования Фурье (БПФ), в которых одни и те же значения тригонометрических функций (называемые множителями тиддла)) должны оцениваться много раз в данном преобразовании, особенно в общем случае, когда вычисляется много преобразований одного и того же размера. В этом случае вызов стандартных библиотечных подпрограмм каждый раз является недопустимо медленным. Один из вариантов - вызвать библиотечные подпрограммы один раз, чтобы построить таблицу тех тригонометрических значений, которые потребуются, но это требует значительного объема памяти для хранения таблицы. Другая возможность, поскольку требуется регулярная последовательность значений, заключается в использовании формулы повторения для вычисления тригонометрических значений на лету. Значительные исследования были посвящены поиску точных, стабильных схем повторения, чтобы сохранить точность БПФ (которое очень чувствительно к тригонометрическим ошибкам).
Вычисление по запросу [ править ]
Современные компьютеры и калькуляторы используют различные методы для получения значений тригонометрических функций по запросу для произвольных углов (Kantabutra, 1996). Один из распространенных методов, особенно на высокопроизводительных процессорах с модулями с плавающей запятой , заключается в объединении полиномиального или рационального приближения (например, приближения Чебышева , наилучшего равномерного приближения и приближения Паде , и, как правило, для более высокой или переменной точности, рядов Тейлора и Лорана).) с уменьшением диапазона и поиском в таблице - сначала они ищут ближайший угол в небольшой таблице, а затем используют полином для вычисления поправки. Однако сохранение точности при выполнении такой интерполяции нетривиально; и такие методы, как точные таблицы Гала, редукция Коди и Уэйта и алгоритмы редукции Пейна и Ханека, могут использоваться для этой цели. На более простых устройствах, в которых отсутствует аппаратный умножитель , существует алгоритм под названием CORDIC (а также связанные с ним методы), который более эффективен, поскольку использует только сдвиги и добавления. Все эти методы обычно реализуются аппаратно из соображений производительности.
Конкретный полином, используемый для аппроксимации триггерной функции, генерируется заранее с использованием некоторой аппроксимации алгоритма минимаксного приближения .
Для очень точных вычислений, когда сходимость разложения в ряд становится слишком медленной, тригонометрические функции могут быть аппроксимированы средним арифметико-геометрическим , которое само аппроксимирует тригонометрическую функцию ( комплексным ) эллиптическим интегралом (Brent, 1976).
Тригонометрические функции углов, рациональных кратных 2π, являются алгебраическими числами . Значения для a / b · 2π могут быть найдены путем применения тождества де Муавра для n = a к корню b- й степени из единицы , который также является корнем многочлена x b - 1 на комплексной плоскости . Например, косинус и синус 2π ⋅ 5/37 являются действительной и мнимой частями соответственно 5-й степени 37-го корня из единицы cos (2π / 37) + sin (2π / 37) i, который является корень многочлена степени -37 x 37 - 1. В этом случае алгоритм поиска корней, такой как метод Ньютона, намного проще, чем описанные выше алгоритмы среднего арифметико-геометрического, но сходятся с аналогичной асимптотической скоростью. Однако последние алгоритмы требуются для трансцендентных тригонометрических констант.
Формулы половинного угла и сложения углов [ править ]
Исторически сложилось так, что самый ранний метод расчета тригонометрических таблиц и, вероятно, наиболее распространенный до появления компьютеров, заключался в многократном применении тригонометрических тождеств с половинным углом и сложением углов, начиная с известного значения (например, sin (π / 2 ) = 1, cos (π / 2) = 0). Этот метод использовал древний астроном Птолемей , который вывел их в Альмагесте , трактате по астрономии. В современной форме полученные им тождества формулируются следующим образом (со знаками, определяемыми квадрантом, в котором находится x ):
Они были использованы для построения таблицы аккордов Птолемея , которая применялась к астрономическим задачам.
Возможны различные другие перестановки этих тождеств: например, в некоторых ранних тригонометрических таблицах использовались не синус и косинус, а синус и версин .
Быстрое, но неточное приближение [ править ]
Быстрый, но неточный алгоритм вычисления таблицы из N приближений s n для sin (2 π n / N ) и c n для cos (2π n / N ):
- s 0 = 0
- с 0 = 1
- s n +1 знак равно s n + d × c n
- c n +1 = c n - d × s n
для п = 0, ..., N - 1, где d = 2π / N .
Это просто метод Эйлера для интегрирования дифференциального уравнения :
с начальными условиями s (0) = 0 и c (0) = 1, аналитическое решение которого s = sin ( t ) и c = cos ( t ).
К сожалению, это не является полезным алгоритмом генерации таблиц синуса , поскольку он имеет значительную ошибку, пропорциональную 1 / N .
Например, для N = 256 максимальная ошибка значений синуса составляет ~ 0,061 ( с 202 = -1,0368 вместо -0,9757). Для N = 1024 максимальная ошибка значений синуса составляет ~ 0,015 ( s 803 = -0,99321 вместо -0,97832), что примерно в 4 раза меньше. Если бы полученные значения синуса и косинуса были нанесены на график, этот алгоритм нарисовал бы логарифмическую спираль, а не круг.
Лучшая, но все еще несовершенная формула повторения [ править ]
Эта статья, возможно, содержит оригинальные исследования . Декабрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( |
Простая формула повторения для создания тригонометрических таблиц основана на формуле Эйлера и соотношении:
Это приводит к следующему повторению для вычисления тригонометрических значений s n и c n, как указано выше:
- с 0 = 1
- s 0 = 0
- c n +1 знак равно w r c n - w i s n
- s n +1 знак равно w i c n + w r s n
для n = 0, ..., N - 1, где w r = cos (2π / N ) и w i = sin (2π / N ). Эти два исходных тригонометрические значения обычно вычисляется с использованием существующих библиотечных функций (но можно также найти , например , с использованием метода Ньютона в комплексной плоскости , чтобы решить для примитивного корня из г N - 1).
Этот метод дает точную таблицу в точной арифметике, но имеет ошибки в арифметике с плавающей запятой конечной точности . Фактически, ошибки растут как O (ε N ) (как в худшем, так и в среднем случае), где ε - точность с плавающей запятой.
Значительным улучшением является использование следующей модификации вышеизложенного, трюка (из-за Синглтона, 1967), часто используемого для генерации тригонометрических значений для реализаций БПФ:
- с 0 = 1
- s 0 = 0
- c n +1 = c n - (α c n + β s n )
- s n +1 = s n + (β c n - α s n )
где α = 2 sin 2 (π / N ) и β = sin (2π / N ). Погрешности этого метода намного меньше, O (ε √ N ) в среднем и O (ε N ) в худшем случае, но этого все же достаточно, чтобы существенно ухудшить точность БПФ больших размеров.
См. Также [ править ]
- Плимптон 322
- Числовой анализ
- КОРДИК
- Точные тригонометрические константы
- Таблица синусов Арьябхаты
- Таблица синусов Мадхавы
Ссылки [ править ]
- Карл Б. Бойер (1991) История математики , 2-е издание, John Wiley & Sons .
- Манфред Таше и Хансмартин Зойнер (2002) «Улучшенный анализ ошибок округления для предварительно вычисленных факторов вращения», Журнал вычислительного анализа и приложений 4 (1): 1–18.
- Джеймс С. Шацман (1996) "Точность дискретного преобразования Фурье и быстрого преобразования Фурье", SIAM Journal on Scientific Computing 17 (5): 1150–1166.
- Витит Кантабутра (1996) «Об оборудовании для вычисления экспоненциальных и тригонометрических функций», IEEE Transactions on Computers 45 (3): 328–339.
- Р.П. Брент (1976) « Быстрая оценка элементарных функций с множественной точностью », Журнал Ассоциации вычислительной техники 23: 242–251.
- Синглтон, Ричард К. (1967) «О вычислении быстрого преобразования Фурье», Сообщения ACM 10: 647–654.
- Гал, Шмуэль и Бачелис, Борис (1991) «Точная элементарная математическая библиотека для стандарта IEEE с плавающей запятой», Транзакции ACM по математическому программному обеспечению .