Сглаживание кривой заданной длины

[mais_]

Не то чтобы задача имела отношение к вариационному исчислению... совсем нет всего-то хочу численный алгоритм реализовать в маткаде...

задача: есть некий массив A[i], i равно 1,2,... N, если отложить по оси абцисс значения счётчика i, а по оси ординат - элементы вектора A, то получим график... который я хочу аппроксимировать кривой B[i] наперёд заданной длины, так, чтобы это было наилучшим приближением в смысле минимизации сумму (по i от 1 до N) модулей отклонений B от A. Под длиной кривой понимаю сумму модулей первых разностей |B[j+1]-B[j]|, j равно 1, ... N-1.

с какого бы бока подступиться к реализации алгоритма?

-- Пт мар 02, 2012 17:15:16 --

Вот как-то так. Только "длина" B задается наперед. И при фиксированной длине подбираю расположение этой кривой так, чтобы отклонение В от исходной А (на картинке D(B,A) ) было минимальным...

http://zalil.ru/32805760

P.S. А вставить картинку сразу в форум никак невозможно? Или я туплю?

[MaximVD]

Попытаемся перевести вашу задачу на язык математики. Обозначим $y_i = A[i]$, $i \in \{ 1, \ldots, N \}$, - заданные числа, $x_i = B[i]$ - то, что нужно найти. Пусть длина кривой - $c$. Тогда вам необходимо найти минимум $\sum_{i=1}^N |x_i - y_i|$ при ограничении $\sum_{j = 1}^{N-1} |x_{j+1} - x_j| = c$, так?
Во-первых, решение этой задачи точно существует (т.е. существует "самая лучшая кривая"), но, по-моему, может быть не единственно.
Я не специалист по численным методам, но могу предложить решать эту задачу с помощью штрафных функций. Если вкратце, то можно выбрать такое число $\lambda_0 > 0$, что для любого $\lambda > \lambda_0$ ваша исходная задача эквивалентна задаче минимизации функции $f(x_1, \ldots, x_N) = \sum_{i=1}^N |x_i - y_i| + \lambda \left| \sum_{j = 1}^{N-1} |x_{j+1} - x_j| - c \right|$ без ограничений (при желании можно найти оценку для $\lambda_0$, а на практике $\lambda$ постепенно увеличивают и находят такое, при котором всё работает). Для минимизации функции $f$ можно использовать численные методы недифференцируемой оптимизации (могу указать книгу, где их можно посмотреть). Хотя, это сложный путь, потому что там много чего лишнего надо будет реализовывать. Вероятно, кто-нибудь вам предложит что-нибудь попроще.

[mais_]

Всё так, как описано... но я почему-то склонен предполагать, что решение будет единственным...

[_hum_]

MaximVD в сообщении #544614 писал(а):

Попытаемся перевести вашу задачу на язык математики. Обозначим $y_i = A[i]$, $i \in \{ 1, \ldots, N \}$, - заданные числа, $x_i = B[i]$ - то, что нужно найти. Пусть длина кривой - $c$. Тогда вам необходимо найти минимум $\sum_{i=1}^N |x_i - y_i|$ при ограничении $\sum_{j = 1}^{N-1} |x_{j+1} - x_j| = c$, так?

Разве длина кривой равна сумме абсолютных значений разностей ординат? По идее, должно ж быть $L = \sum_j \sqrt{(x_{j+1} - x_j)^2 + (j+1 - j)^2}$.

Хотя, судя по тому, что писал ТС, да :) У него какая-то своя длина кривой.