nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Как быстро оценить длину вектора - 2

Да, самое вовремя, когда я решил, что этот алгоритм мне в принципе не нужен, наконец догадался, как сделать его немножко точнее.

Тогда у нас получалась максимальная ошибка 5,5%, но попросту подобрав лучшие коэффициенты, эту ошибку можно снизить до 3,96%, т.е повысить точность примерно в 1,4 раза.

Старая формула:


Взвешенная сумма Чебышевской и Манхэттенской метрик, которая сколько-нибудь прилично приближает метрику Эвклидову. Почему-то я вбил себе в голову, что сумма двух коэффициентов должна равняться единице: все 3 метрики сходятся в точках (1;0), (0;1), (-1;0) и (0;-1), причём Чебышевская метрика всегда даёт результат меньше Эвклидовой, а Манхэттенская - всегда больше. Поэтому взять и сделать, чтобы в этих самых точках, самых очевидных, самых "важных", новая метрика ДАВАЛА ОШИБКУ, пусть даже это позволит снизить ошибку "в целом", казалось кощунством.

Но в последнее время у меня сорвало тормоза, сначала на нормировке кватернионов, потом на арктангенсе, и сейчас совсем пустился во все тяжкие. Вот такую формулу придумал:


Или, если сосчитать коэффициенты:


Максимальная ошибка в 3,96% достигается в самых простых и очевидных точках, (1;0), (0;1) и так далее.

Во всём этом есть своя извращённая логика...


Тогда мы приводили такую картинку:


Здесь изображены "окружности", т.е множество точек, отстоящих от центра ровно на единицу, но в разных метриках. "Нормальная" окружность - это в Эвклидовой метрике, квадрат поменьше - Манхэттенская, квадрат побольше - Чебышевская. Сочетая их, мы получили восьмиугольник, причём, задав сумму двух весов равной единице, мы зафиксировали 4 вершины из 8, и получили одну степень свободы - возможность радиально двигать оставшиеся 4 вершины.

А сейчас мне наконец-то захотелось использовать ПРАВИЛЬНЫЙ МНОГОУГОЛЬНИК! Если пока сохранить сумму коэффициентов, равной единице, то многоугольник получится вписанным в окружность.

Определим, при каких коэффициентах получится ровно так. Когда , мы должны получить нашу новую метрику, в точности равной единице. Если коэффициент при Манхэттенской метрике обозначить как a, то при Чебышевской он будет 1-a, и получаем уравнение:



Решим его:




И второй коэффициент получится:


Новая метрика выглядит так:


Максимальная ошибка достигается на углах 22,5°+45°·k, k - целые числа, и достигает она 8,2%, что хуже ранее предложенных коэффициентов.

Но теперь самое время немного смасштабировать этот восьмиугольник, чтобы он был не вписанным и не описанным, а ровно посерединке!

На угле 22,5° значение выражения завышается: подставь мы точку (cos(22,5°); sin(22,5°)) - и мы вместо длины 1 получим примерно 1,082. В строгой записи:



Хочется помножить результат на некое значение s<1, тогда в этом направлении ошибка уменьшится (если не переборщить), но увеличится в точке (1;0). Нам хочется эти ошибки сравнять. Получим довольно простое уравнение для величины s:



(при угле 22,5° получали результат больше единицы и хотим ЧАСТИЧНО скомпенсировать это превышение. А на угле 0° будем получать результат меньше единицы).

Откуда:


Выражение для k приведено чуть выше, k≈1,082.

Отсюда и получаем формулу, приведённую в начале поста!

А так выглядит новая метрика:



PS. А если нужна совсем грубая оценка, можно одно из следующих выражений применить:




Они оба дают одинаковую максимальную ошибку в 17%. Может, где и пригодится. Всё-таки лучше, чем 41%, если применить обычного Чебышева или Манхэттен...

Poll #2112997 Упоротые формулы

Приближения, дающие максимальную ошибку в самых тривиальных случаях

Красивое
5(45.5%)
Некрасивое, но коль работает - надо использовать
4(36.4%)
НИ ЗА ЧТО!
2(18.2%)
Tags: ПЛИС, математика, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Так есть ли толк в ковариационной матрице?

    Задался этим вопросом применительно к своему прибору чуть более 2 недель назад. Рыл носом землю с попеременным успехом ( раз, два, три, четыре),…

  • Big Data, чтоб их ... (4)

    Наконец-то стряхнул пыль с компьютерной модели сближения, добавил в неё код, чтобы мы могли определить интересующие нас точки, и выписать…

  • Потёмкинская деревня - 2

    В ноябре 2020 года нужно было сделать скриншот несуществующей программы рабочего места под несуществующий прибор, чтобы добавить его в документацию.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 6 comments