Пифагорово сложение

В математике — сложение Пифагора это бинарная операция над действительными числами , которая вычисляет длину гипотенузы прямоугольного треугольника по двум его сторонам. По теореме Пифагора для треугольника со сторонами $a$ и $b$, эту длину можно рассчитать как $$a\oplus b={\sqrt {a^{2}+b^{2}}},$$где $\oplus$ обозначает операцию сложения Пифагора.

Эту операцию можно использовать при преобразовании декартовых координат в полярные координаты . Он также предоставляет простые обозначения и терминологию для некоторых формул, когда их слагаемые сложны; например, соотношение энергии-импульса в физике становится $$E=mc^{2}\oplus pc.$$Она реализована во многих библиотеках программирования как гипот -функция таким образом, чтобы избежать ошибок, возникающих из-за вычислений с ограниченной точностью, выполняемых на компьютерах. В приложениях к обработке сигналов и распространению та неопределенности измерений же операция также называется сложением в квадратуре ; это связано со средним квадратичным или «среднеквадратическим значением».

Приложения

Пример сложения независимых ошибок по Пифагору с использованием векторного сложения ортогональных векторов

Сложение Пифагора (и его реализация в виде гипот-функции) часто используется вместе с функцией atan2 для преобразования из декартовых координат. $(x,y)$ в полярные координаты $(r,\theta )$: $${\begin{aligned}r&=x\oplus y=\operatorname {hypot} (x,y)\\\theta &=\operatorname {atan2} (y,x).\\\end{aligned}}$$

Если измерения $X,Y,Z,\dots$ имеют независимые ошибки $\Delta _{X},\Delta _{Y},\Delta _{Z},\dots$ соответственно, метод квадратур дает общую ошибку, $$\varDelta _{o}={\sqrt {{\varDelta _{X}}^{2}+{\varDelta _{Y}}^{2}+{\varDelta _{Z}}^{2}+\cdots }}$$тогда как верхний предел общей ошибки равен $$\varDelta _{u}=\varDelta _{X}+\varDelta _{Y}+\varDelta _{Z}+\cdots$$если бы ошибки не были независимыми.

Это эквивалентно нахождению величины результата сложения ортогональных векторов , каждый из которых имеет величину, равную неопределенности, с использованием теоремы Пифагора .

При обработке сигналов квадратурное сложение используется для определения общего шума от независимых источников шума. Например, если датчик изображения выдает шесть цифр дробового шума , три — темнового шума и два — шума Джонсона-Найквиста при определенных условиях, общий шум равен $$\sigma =6\oplus 3\oplus 2={\sqrt {6^{2}+3^{2}+2^{2}}}=7$$цифровые номера, показывая доминирование более крупных источников шума.

Среднеквадратичное значение конечного набора $n$ числа — это просто их пифагорова сумма, нормализованная до обобщенного среднего путем деления на ${\sqrt {n}}$.

Характеристики

Операция $\oplus$ ассоциативен ​ и коммутативен , и $${\sqrt {x_{1}^{2}+x_{2}^{2}+\cdots +x_{n}^{2}}}=x_{1}\oplus x_{2}\oplus \cdots \oplus x_{n}.$$Это означает, что реальные цифры под $\oplus$ образуют коммутативную полугруппу .

Реальные цифры под $\oplus$ не группа , потому что $\oplus$ никогда не может дать в качестве результата отрицательное число, тогда как каждый элемент группы должен быть результатом применения групповой операции к самому себе и единичному элементу . Для неотрицательных чисел это все же не группа, потому что пифагорейское сложение одного числа на второе положительное число может только увеличить первое число, поэтому ни одно положительное число не может иметь обратный элемент . Вместо этого он образует коммутативный моноид неотрицательных чисел с нулем в качестве его единицы.

Выполнение

Гипота — это математическая функция, предназначенная для расчета длины гипотенузы прямоугольного треугольника. Он был разработан, чтобы избежать ошибок, возникающих из-за вычислений с ограниченной точностью, выполняемых на компьютерах. Вычислить длину гипотенузы треугольника можно с помощью функции извлечения квадратного корня из суммы двух квадратов , но гипотеза позволяет избежать проблем, возникающих при возведении в квадрат очень больших или очень маленьких чисел. Если рассчитывать по натуральной формуле, $$r={\sqrt {x^{2}+y^{2}}},$$квадраты очень больших или малых значений $x$ и $y$ может выйти за пределы машинной точности при расчете на компьютере, что приведет к неточному результату, вызванному арифметическим недостатком и переполнением . Функция гипот была разработана для вычисления результата, не вызывая этой проблемы.

Если любой вход в гипотезу бесконечен, результат бесконечен. Поскольку это верно для всех возможных значений другого входного сигнала, стандарт IEEE 754 с плавающей запятой требует, чтобы это оставалось истинным, даже если другой входной сигнал не является числом (NaN).

Начиная с C++17 , появилась дополнительная гипот-функция для 3D-расчетов: $$r={\sqrt {x^{2}+y^{2}+z^{2}}}.$$

Порядок расчета

Трудность с наивной реализацией заключается в том, что $x^{2}+y^{2}$ может переполняться или опустошаться, если только промежуточный результат не вычисляется с повышенной точностью . Распространенный метод реализации заключается в обмене значениями, если это необходимо, так, чтобы $|x|\geq |y|$, а затем использовать эквивалентную форму $${\begin{aligned}r&={\sqrt {x^{2}+y^{2}}}\\&={\sqrt {x^{2}\!\left(1+\left({\tfrac {y}{x}}\right)^{2}\right)}}\\&=|x|{\sqrt {1+\left({\tfrac {y}{x}}\right)^{2}}}\left(=|x|+{\frac {y}{|x|}}{\frac {y}{1+{\sqrt {1+\left({\tfrac {y}{x}}\right)^{2}}}}}\right)\!.\end{aligned}}$$

Вычисление $y/x$ не может переполниться, если только оба $x$ и $y$ равны нулю. Если $y/x$ происходит переток, конечный результат равен $|x|$, что верно в пределах точности расчета. Квадратный корень вычисляется из значения от 1 до 2. Наконец, умножение на $|x|$ не может переполниться и переполняется только тогда, когда результат слишком велик для представления. Недостатком этой реализации является то, что она требует дополнительного деления с плавающей запятой, что может удвоить стоимость простой реализации, поскольку умножение и сложение обычно выполняются намного быстрее, чем деление и извлечение квадратного корня. Обычно реализация происходит медленнее в 2,5–3 раза.

Более сложные реализации позволяют избежать этого, разделив входные данные на большее количество случаев:

• Когда $x$ намного больше, чем $y$, $x\oplus y\approx |x|$ до , с точностью машины .
• Когда $x^{2}$ переполняется, умножаем оба $x$ и $y$ с небольшим коэффициентом масштабирования (например, 2 ⁻⁶⁴ для одинарной точности IEEE), используйте простой алгоритм, который теперь не будет переполняться, и умножьте результат на (большое) обратное значение (например, 2 ⁶⁴ ).
• Когда $y^{2}$ при меньшем потоке, масштабируйте, как указано выше, но поменяйте коэффициенты масштабирования, чтобы увеличить промежуточные значения.
• В противном случае наивный алгоритм безопасен в использовании.

Однако эта реализация работает чрезвычайно медленно, поскольку из-за различных случаев она приводит к неправильным предсказаниям прыжков. Дополнительные методы позволяют вычислить результат более точно, например, с точностью менее одного ulp .

Поддержка языков программирования

Функция присутствует во многих языках программирования и библиотеках, в том числе CSS , С++11 , Д , Идти , JavaScript (начиная с ES2015), Юля , Java (начиная с версии 1.5), Котлин , МАТЛАБ , PHP , Питон , Руби , Ржавчина , и Скала .

См. также

• Евклидово расстояние
• Алгоритм альфа-макс плюс бета-мин
• В Metafont есть встроенные операции сложения и вычитания Пифагора под названиями ++ и +-+ соответственно.

Дальнейшее чтение

• Дюбрюлль, Огюстен А. (1983). «Класс численных методов вычисления сумм Пифагора» (PDF) . Журнал исследований и разработок IBM . 27 (6): 582–589. CiteSeerX   10.1.1.94.3443 . дои : 10.1147/rd.276.0582 . .