Математический вопрос

[spamsink]

Найти линейную функцию, приближающую данную выпуклую функцию так, чтобы минимизировать абсолютную ошибку, довольно легко: заключаем график функции на данном отрезке в полосу, параллельную прямой, соединяющей концы отрезка графика функции, и берем середину полосы.
Например, найдем линейное приближение к x² на отрезке [1;9].
Прямая, соединяющая концы: y=10x-9, она же верхняя граница полосы.
Нижняя граница - касательная к графику, паралелльная данной, это y=10x-25.
Середина между ними: y=10x-17.
К сожалению, получается, что в х=1 приближенное значение оказывается отрицательным, что нежелательно.

А как найти линейную функцию, минимизирующую относительную ошибку? Я туплю, или это действительно непросто?
Кроме описательных, принимаются также ответы, содержащие запросы к Wolfram alpha.

Comments

[xaxam.livejournal.com]

Даже в случае абсолютной ошибки приведённый ответ неверный. Пример: возьмём функцию у=х на отрезке (-1,1) и доопределим её нулём в концах отрезка (если хочется непрерывности, можно чуть-чуть поправить). Ваша конструкция даёт постоянную линейную функцию (константу, равную нулю), а правильный ответ у=(1/2)х.

[spamsink]

Прошу прощения, я имел в виду только выпуклые функции.

[xaxam.livejournal.com]

Да, для выпуклых алгоритм правильный. Д-во (для себя): сделаем аффинное преобразование плоскости (х,у) -> (х, у+ах), не меняющее расстояний вдоль вертикальных прямых и сохраняющее выпуклость так, чтобы в концах отрезка функция приняла одинаковые значения. Тогда решение задачи очевидно (константа, "средняя линия").

[juan-gandhi.livejournal.com]

Но неверно.

[juan-gandhi.livejournal.com]

Ну, МНК немножко не такой ответ дает. xaxam уже привел хороший контрпример.

Относительную ошибку - это надо брать логарифм, и аппроксимировать логарифмом же. Если функция пересекает ось, то хм.

[spamsink]

Если функция пересекает ось, то Лопиталь рулез.

Брать логарифм я уже пробовал. Вылезает Lambert W, и без вольфрамальфы не обойтись.

[xaxam.livejournal.com]

С точки зрения математики приближение в смысле относительной ошибки аффинной функцией выглядит довольно неестественно. Более естественный класс функций, - экспоненты. С другой стороны, условие выпуклости надо бы тогда заменить на логарифмическую выпуклость (http://mathemlib.ru/mathenc/item/f00/s00/e0000925/index.shtml)...

Но это всё пилосопия, конечно, если есть конкретный запрос. Просто не все конкретные задачи имеют красивые решения ;-) У меня в загашнике есть прелестная байка про то, как инженер допытывался у математика, как устроены конформные отображения многоугольника на полуплоскость.

[spamsink]

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

Что, численные методы у нас уже не математика? :)

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

[juan-gandhi.livejournal.com]

Не математика, конечно.

[ny-quant.livejournal.com]

Напомню чтоб далеко не ходить про квадратурные формулы ГАУССового типа.

Когда мы проходили численные методы, господа победители международных олимпиад они же в будущем хорошие профессиональные математики решили коллективно снять пенсне на численную математику и сдать не готовясь. Всех троих И.П.Мысовских вынес с экзамена с двойкой.

[juan-gandhi.livejournal.com]

Он, наверно, прав в данном случае, но я бы не воспринимал Ивана Петровича как математика.

[ny-quant.livejournal.com]

Как насчет Гаусса?

[spamsink]

Ой, прошу прощения, прикладная математика.

[spamsink]

Что же инженеру было на самом деле нужно, интересно?

[spamsink]

Рассмотрим только выпуклые функции.

[maksa.livejournal.com]

Хм. Мне казалось, что прямая, соединяющая конца отрезка [1; 9], — это не y = 10x - 9, а у = 0. Может, имелось в виду «прямая, соединяющая концы графика функции на этом отрезке»?

[spamsink]

Разумеется. :) Пост писался на телефоне, прошу прощения за неровный почерк.

[juan-gandhi.livejournal.com]

Не пойдет это все.
Начни с функции f(x) = x < 1 ? x : x < 2 ? 1 : 3 - x; на отрезке 0..3.

Короче, если тебя абсолютная ошибка интересует, то это l1, затрахаешься. Если квадратичная, то l2, там все проще, тебе нужно сосчитать три интеграла и минимизировать какой-то квадратный полином (думаю, сам нарисуешь).

Относительная... там тоже интегралов всяких надо набрать, но какую формулу минимизировать, надо посмотреть.

[spamsink]

И что не так с этой функцией?

Обозначения l1 и l2 мне неизвестны.

Интегралы и МНК не при делах, задача другая.

[anatoly borodin (from livejournal.com)]

Точнее L1 и L2.

https://en.wikipedia.org/wiki/Norm_(mathematics)#p-norm

[anatoly borodin (from livejournal.com)]

Минимизация L2 - это линейная регрессия/метод наименьших квадратов. Ну да, 3 интеграла и СЛИ с двумя неизвестными.

[spamsink]

Метод наименьших квадратов дает результат, зависящий от дискретного набора данных, и интеграл даст результат, зависящий от формы кривой. Мне же надо совсем другое.

[anatoly borodin (from livejournal.com)]

Кстати, раз пошла такая пьянка, то максимум абсолютного значения погрешности - это не L1, а Linf.

[spamsink]

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