Имеется довольно большой 2-мерным массив действительных чисел, представляющий собой некую поверхность. 

Разброс величин относительно этой поверхности определяется не только статистическим шумом, но и массой других факторов.

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

В принципе, задача решаема и решена (последовательная аппроксимация рядов и колонок полиномом). Проблема в том, что использованный алгоритм жрет немеряно времени.

Подскажите, пожалуйста, какой алгоритм делал бы работу с оглядкой на сроки исполнения.

Спасибо!

Для плоскости всё элементарно и быстро считается по МНК - все необходимые суммы произведений считаются за 1 проход, и система из 4 линейных уравнений решается чисельно.
Далее - задаётся параметр допустимого отклонения и начинается отбрасывание наиболее сильно отклоняющихся от плоскости точек, сама плоскость при этом пересчитывается. При этом наиболее отклоняющаяся точка считается за 1 проход, после нахождения суммы просто корректируются и система пересчитывается.
Когда максимальное отклонение перестанет превышать заданный параметр, отброшенные точки (вернее, их отклонение от окончательной плоскости) аппроксимируются на некую куполообразную поверхность (с нулевыми асимптотами по всем направлениям - нечто типа вероятностной кривой в сечении через максимум) - если повертеть карандашом, вряд ли аналитическое решение получится сложнее МНК, то же накопление сумм, только не произведений. Итогом будет сумма уравнений плоскости и купола.

Спасибо, но хотелось бы подробностей: как это считать?

Да как обычно - по МНК. Задаёшь аналитическое выражение для желаемого уравнения поверхности, в коем у тебя будет некое количество констант. Суммируешь отклонения расчётных точек от вычисленных для этого желаемого уравнения по всему массиву. Производная этой суммы по любой из констант при оптимальных значениях констант равна нулю. Преобразовываешь аналитически уравнения производных, получаешь систему уравнений, где количество уравнений равно количеству констант. Если функция уравнения поверхности не очень сложна, как правило удаётся получить аналитически систему линейных уравнений относительно этих констант, где коэффициенты являются сложными суммами экспериментальных значений. И решение системы даёт оптимальные значения констант.

Hу тогда остается спросить про подходящее уравнение  

Массив у тебя, я полагаю, не генератор случайных чисел производит? Если так, то под ним лежит какой-то процесс, со своей логикой и физикой, с ненким математическим описанием. Вот его и используй в качестве основы для построения аппроксимирующего уравнения.

По логике вещей, мне надо минимизировать такую функцию:



Попытался решить пролему аналитически, только усложнил, к сожалению. Так что буду благодарен за идеи как с ней побороться.

PS: Извиняюсь, что привел формулу в таком псевдокодовом виде. http://ipicture.ru почему-то не хочет загружать картинку с красиво набранным уравнением.

А локальный JPG загрузить в сообщение - не?

_Y_, 
Рассмотрим одномерный случай.
Существует несколько подходов:
- Аппроксимация полиномом.
- Аппроксимация сплайном.
- Фильтрация вч
- Фильтр Кальмана
- Оптимизация ломанной

Двухмерный аналогичен. Решается выполнением отдельно по Х и Y.
1) Аппроксимация требует. 81*N умножений и столько же сложений. И решения матричного уравнения.
Скорость регулируется степенью p. 81=p^2 но более p=6 не советую.
2) Тоже самое, но точность аппроксимации выше так как нет проблем со степенью. А скорость и гладкость регулируется разбиением на число полиномов(участков). 
3) Фильтрация зависит от множества факторов. Но от 10-100 умножений на точку. В зависимости от степени. 
4) Не в курсах как там.
5) Оптимизация ломанной этот тот же МНК  что в 1 и 2, только линейный. 
p*N умножений.  Гладкость определяется коэффициентом допустимого отклонения. 






Это сообщение отредактировал(а) Pavia - 19.11.2014, 21:24

Pavia, 

Именно так и делаю. Полиномом 4-й степени занимает 1,9 секунды на моем нотбуке, полиноммом 3-й 1,5 секунды (но результат уже не очень хороший). Можно, в принципе, подключить комп помощнее, но надо ускорить не в два раза, а в десять, наверное.


А про это я забыл  
Вот она:


Это сообщение отредактировал(а) _Y_ - 19.11.2014, 21:45

Присоединённый файл ( Кол-во скачиваний: 10 )
 Untitl.one.gif 2,84 Kb

_Y_, 
А размерность данных какая и какая сложность алгоритма? Просто я думаю где-то ошибка, из-за этого скорость маленькая. 
А вот качество да. Там хромает, поэтому я и предложил сплайн, тем более он может быть 3 порядка.

Алгоритм, собственно, предельно простой.

• Имеем 2-мерный массив значений. Все значения наличествуют, ни одного не пропущено.
• Проходим по рядам исходного массива, аппроксимируя полиномом каждый ряд как одномерный массив. Для аппроксимации используем библиотечную функцию.
• Полученый сглаженный по рядам массив пропускаем через ту же процедуру еще раз, но теперь сглаживая по колонкам.
• Вот и все - получилась поверхность, которая всех устраивает.

Собственно, сам я это не придумал: нашел в сети несколько готовых процедур. Эта дала ожидаемый результат. Единственно, что я в ней поменял, разрешил параллелизацию обработки рядов/колонок. иначе процедура работала еще раза в два медленнее.