Посмотрите на неё с большим разрешением в районе минимума.
Там, действительно, достаточно искать нуль производной, так как все модули выпуклы вверх. Точнее, вниз. Точнее, не принципиально, но в одну сторону.

Про производные не понял. Бывает и так:

Искать точку (не ясно как), где производная равна нулю. И эта точка будет искомой, если попадает в отрезок [-1; 1]. Если же точка < -1, то искомая = -1. Если > 1, то искомая = 1.

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

Как ищут минимум непрерывно дифференцируемой функции? У вас она кусочно непрерывно дефференцируемая.
Верхний график у вас вводит в заблеждуние. Наклон линий только возрастает. Увеличте ещё.

Про необходимость поиска нулевой производной написал выше. А вот как ее численно искать пока не знаю.


Вот так выглядит график и его производная в на всем отрезке [0; 1] и вблизи минимума:

А так меняется производная при уменьшении Delta:

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

Это все, конечно, понятно. Но чем поиск нулевой производной будет превосходить поиск минимума так, как писали ранее?

Считать меньше. Дифференцировать целевую функцию, разумеется, нужно аналитически, а не численно. Это просто.

Конечно, производные N+2 линейных функций простые. Но как посчитать производную целевой функции?

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

Попробуйте для начала подсчитать её в некоторой точке, не совпадающей с изломом ни одного модуля.

Для интервала слева - до первого излома, производная будет Sum(a[i]-b[i])

Замечательно. Таперь, если она отрицательная, попробуйте найти для следующего интервала.

Примем, что производная слева равна D[0].
тогда производная после 1-го излома (слагаемые отсортировали по возрастанию точек излома) будет D[1] = D[0] + 2 * (b[1] - a[1]).
Ну и вообще итерационная формула такая D[k] = D[k - 1] + 2 * (b[k] - a[k]).
В итоге получается, что надо сначала отсортировать слагаемые по возрастанию точек изломов, а потом итерационно дойти до производной, которая меняет знак. После чего взять точку, которая соответствуюет минимальному значению модуля двух соседних D.
P.S. Возрастание производной совсем неочевидно.

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

Вот!
Правда, у вас в самой первой формуле для самого левого участка есть одна ошибка, В результате и последняя неправильная. Найдете?




Нет!
Нужно юбрать излом, при переходе через который производная меняет знак.

Ошибки нет, если считать, что производная убывает.



Туплю - не понял.

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

Есть.



Сорри, читать "нужно брать".