Точки Чебычева и точность с плавающей запятой

В своих конспектах лекций я видел, что точки Чебычева, определенные (в обозначениях MatLab) как

n = 20;
i = (1:n+1)';
% Chebychev
xi = 5*cos((2*i-1)*pi/(2*(n+1)))

несимметричны в [-1,1] в точности с плавающей запятой. Но если использовать тригонометрическое тождество cos(x) = sin( pi/2 - x), примененное к указанным выше точкам, он обнаружит, что точки Чебычева

xxi = 5*sin(pi*(n+2-2*i)/(2*(n+1)))

теперь симметричны в интервале.

Теперь большой вопрос: почему эта замена дает симметрию? Я почти уверен, что это связано с pi, но он присутствует в обеих формулировках, так что же происходит на самом деле? Я хотел бы увидеть формальный аргумент или математический расчет такой ситуации


interpolation precision floating-point floating-accuracy numerical-analysis
person andereBen    schedule 01.05.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Формула синуса использует точки, симметрично распределенные вокруг нуля, а формат косинуса — нет. Особенности формата с плавающей запятой, особенно степень детализации, с которой он представляет числа, симметричны относительно нуля, и поэтому вычисления, симметричные относительно нуля, дают результаты, симметричные относительно нуля.

Формула косинуса использует cos в точках (2i−1)/(2n+2) π для 1 ≤ i ≤ n+1. Для n=20 эти точки равны 1/42 π, 3/42 π, 5/42 π,… 41/42 π.

1/42 π составляет около 0,075. Наибольшая степень двойки, не превышающая 0,075, равна 2−4. Когда 1/42 π вычисляется в формате IEEE-754 binary64, который имеет 53 бита в мантиссе, масштабирование с плавающей запятой таково, что наибольшая битовая позиция в мантиссе представляет 2−4, а самая младшая битовая позиция представляет 2−56. Таким образом, результат необходимо округлить до ближайшего кратного 2−56. Напротив, 41/42 π составляет около 3,067, и позиция ведущего бита его мантиссы представляет 22, а позиция младшего бита представляет 2−50. Таким образом, результат необходимо округлить до ближайшего кратного 2−50, что в 64 раза больше, чем для 1/42 π. Таким образом, ошибки округления в вычислениях с плавающей запятой обычно различны для 1/42 π и 41/42 π, для 3/42 π и 39/42 π и так далее.

Формула синуса использует sin в точках (n+2-2i)/(2n+2) π для 1 ≤ i ≤ п+1. Для n=20 эти точки равны 20/42 π, 18/42 π, 16/42 π, … −16/42 π, −18/42 π, −20/42 π. При этом, когда 20/42 π и −20/42 π вычисляются в двоичном формате64, они оба используют одно и то же масштабирование для мантиссы. Таким образом, их ошибки округления идентичны, за исключением знака, и результаты вычислений идентичны, за исключением знакового бита. Точно так же 18/42 π и -18/42 π используют одно и то же масштабирование, и все термины связаны с симметричным партнером, за исключением 0/42 π, но он равен нулю и имеет ошибку вычисления (ноль), которая является симметричной. с собой.

Кроме того, типичные реализации подпрограммы sin симметричны относительно нуля, так что sin(-x) и -sin(x) дают идентичные результаты. Обычно они действуют путем уменьшения аргумента по модулю 2π (по крайней мере, в действительности) и вычисления многочлена, который аппроксимирует синус, и этот многочлен обычно симметричен относительно нуля (имеет все нечетные степени своей переменной x). Таким образом, вычисление sin(x) и sin(-x) сохраняет симметрию, как и окончательное умножение на 5. (Реализации cos могут иметь аналогичную симметрию, но поскольку аргументы в этом случае уже асимметричны, cos не может восстановить симметрию.)

person Eric Postpischil    schedule 01.05.2020
comment
Я помню, что многие реализации sin на самом деле делали что-то в несколько ином порядке: сначала отбрасывали знак, и только потом уменьшали аргумент по модулю 2π. Это избавляет от головной боли по сокращению негативных аргументов. Получение sin(x)==sin(-x) — это просто приятный побочный эффект. - person MSalters; 01.05.2020

arrow_upward
1
arrow_downward

И sin, и cos имеют период 2*pi, и, как вы знаете, эти две функции можно легко преобразовать друг в друга. Есть и другие отношения, такие как sin(-x)=-sin(x), cos(-x)=cos(x), sin(x+2pi)=sin(x) и т.д.

Ваш исходный набор точек отбирает cos(x) на интервале 0,2*pi. Это один полный период. Этого более чем достаточно для вычислительных целей; на самом деле интервал 0,pi/2 уже достаточен. Другие значения cos(x) могут быть найдены из вышеупомянутых соотношений.

Теперь подстановка просто преобразует x ∈ 0,2*pi в x' ∈ -pi, +pi. Это все еще один полный период, но теперь он симметричен относительно 0.

person MSalters    schedule 01.05.2020
comment
Да, но как это влияет на точность с плавающей запятой? Я имею в виду, почему сейчас соблюдается численная симметрия? - person andereBen; 01.05.2020
comment
@andereBen: я понятия не имею, почему вы связываете два вопроса. Я имею в виду, что вы думаете, что оба вопроса — это просто разные способы выражения одной и той же идеи, но они совершенно не связаны. Они симметричны, потому что -(-pi)=+pi. - person MSalters; 01.05.2020
comment
Да, но если вы посмотрите на 16-ю десятичную цифру, полученную в первой формулировке, то они не симметричны с точностью до машины. Во второй формулировке они симметричны. - person andereBen; 01.05.2020
comment
Тот факт, что синус и косинус являются периодическими, не имеет отношения к вопросу о симметрии. Период позволяет легко преобразовать формулу косинуса в формулу синуса, но у нас может быть некоторая формула f(x) в точках x, которую можно преобразовать в формулу g(t(x)) в точках t(x), и f(x) может быть непериодическим, но обладать тем свойством, что для используемого набора точек каждая точка x0 в наборе имеет точку x1 такую, что f(x0) = −f(x1). g также непериодична, но обладает тем свойством, что g(z) = −g(z), а t таково, что t(x0) = −t(x1) для тех же пар… - person Eric Postpischil; 01.05.2020
comment
… Тогда результаты вычисления f(x), как правило, не будут симметричными, но результаты вычисления g(t(x)) будут. Единственная часть этого ответа, которая говорит об этом, — это последние слова «теперь симметричны относительно 0». - person Eric Postpischil; 01.05.2020