Если у нас N отсортированных по возрастанию изломов слагаемых, то
D[0] = Sum(b[i] - a[i])
D[k] = D[k-1] + 2 * (a[k] - b[k]), k = 0..N
D[N+1] = Sum(a[i] - b[i])


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

Задумайтесь о смысле разности b[i] - a[i].



Думайте.

На всякий случай напишу целевую функцию: Sum(|a[i] * x + b[i] * (1 - x)|) = Sum((|(a[i] - b[i]) * x + b[i]|).
b[i] - a[i] - это изменение угла наклона.

Нулевой производной может и не существовать. Поэтому нам нужна производная, как можно ближе к нулю. Т.е. если D[M] * D[M + 1] < 0, то искомый излом будет соответствовать min(|D[M]|, |D[M + 1]|)

Сообщение отредактировал getch - Nov 23 2010, 15:29

А теперь продифференцируйте модуль.



Но всегда существует излом, при переходе которой производная меняет знак. Он и есть минимум.

D(x) = b[i] - a[i], x < b[i] / (b[i] - a[i])
D(x) = Unknown, x = b[i] / (b[i] - a[i])
D(x) = a[i] - b[i], x > b[i] / (b[i] - a[i])

Так такой излом и слева и справа от нуля!

P.S. Unknown можно считать нулем.

Сообщение отредактировал getch - Nov 23 2010, 15:44

А если a[i] < b[i]?




От какого ещё нуля?

D[0] = -Sum(|b[i] - a[i]|)
D[k] = D[k-1] + 2 * |a[k] - b[k]|, k = 0..N
D[N+1] = Sum(|b[i] - a[i]|)


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

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

Допустим, что мы пронумеровали изломы слева направо 1, 2, 3, ...., N
И для них получили такие значения производной:
D[100] = -1
D[101] = -0.25
D[102] = 0.5
D[103] = 1

Какой излом брать, 101 или 102?

Заметил у себя ошибку, проивзодных будет не N+2, а 2 * N + 2:
D[0] = -Sum(|b[i] - a[i]|)
D[k] = D[k-1] + |a[k/2] - b[k/2]|, k = 0..2 * N
D[2 * N+1] = Sum(|b[i] - a[i]|)

Сообщение отредактировал getch - Nov 23 2010, 16:34

102




Мы уже добрались до полуцелых индексов массивов?

Я не понимаю, почему брать надо первый положительный при ходе слева-направо, а не первый отрицательный при ходе справа-налево. Произвел проверку на множестве вариантов, Вы правы. Но почему, так и не пойму.
Написал нахождение минимума:

Спасибо огромное за разъяснения!

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

Количество вариантов таких сигналов бесконечно. А вот как найти такой сигнал, у которого коэффициент корреляции с исходными не только одинаковый, но и максимально-возможный?

Сообщение отредактировал getch - Nov 23 2010, 19:15

Да потому что у вас в массиве вершин к вершине приписана производная справа от неё

Написал нахождение минимума:



С какой это стати "бесконечно"? Они все пропорциональны друг другу. Если ковариационная матрица невырождена, то решение, написанное ранее, дает ровно один вектор.

Ну я и ступил... Точно!

Похоже, вы правы. Меня ввел в заблуждение такой результат (на знаки корреляции не обратил внимание):

P.S. Допустим мы имеем всего два вектора длинной единица в трехмерном пространстве. Тогда вектора, которые одинаково коррелированы с исходными двумя, разве не образуют окружность?

Сообщение отредактировал getch - Nov 23 2010, 21:17

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

Я что-то запутался. Правильно ли я понимаю:
1. Количество непропорциональных векторов с одинаковой корреляцией к исходным бесконечно.
2. С одинаковой корреляцией и максимально-возможной - один.
3. К какому пункту относится вектор, находящийся, как обратная ковариационная матрица уноженная на единичную?