2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Аппроксимация с нормой L1
Сообщение11.02.2015, 13:11 


22/10/14
8
Требуется аппроксимировать набор точек нелинейной функцией $y(t) = A+B\cdot\sin^2(t)$ используя норму L1. С нормой L2 все понятно - получается метод наименьших квадратов:
$F = \sum (y_i - A-B\cdot\sin^2(t_i))^2\rightarrow \min$
В случае L1 в производной по коэффициентам получается необходимость учитывать знак и я что-то не соображу, как решать эту систему
$F = \sum |y_i - A-B\cdot\sin^2(t_i)|\rightarrow \min$

Прошу направить, потому что давно не математик

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение11.02.2015, 13:33 
Заслуженный участник
Аватара пользователя


18/05/06
13174
с Территории
Начнём с мелочи: ничего нелинейного по существу здесь нет. От коэффициентов зависимость линейная, а значит, это то же самое, что приближать прямой $Ax+B$.
Далее, насчёт как решать, если минимизируем разность модулей. Решается эта штука плохо и неоднозначно.

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение11.02.2015, 20:23 


17/10/08
1026
В принципе задача сводится к линейному программированию: каждый модуль в критерии это пара дополнительных переменных
http://lpsolve.sourceforge.net/5.1/absolute.htm

Тогда задачу можно решить с использованием готовых пакетов (линейное программирование есть даже в Excel). Если количество данных - сотни тысяч или даже миллионы, то метод внутренней точки.

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 11:42 
Заслуженный участник


22/11/10
1140
Если делать "руками", то я бы не так решал. Фиксируем $B$ и полагаем $x_i = y_i - B \sin^2 t_i$.
Функционал
$G = \sum |x_i - A|\rightarrow \min$
легко минимизируется по $A$. Для этого надо просто найти медиану в множестве $\{x_i\}, i = \overline {0,N}$.
Ну а дальше, что-нибудь типа делением пополам для оптимизации по $B$.
Сложность получится типа
$O(N \ln N |\ln \varepsilon |)$,
где $ \varepsilon$ - допустимая погрешность. Ну а если чуть постараться, то и от $\ln N$ можно избавиться.
По-моему дешево и сердито.

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 12:15 


22/10/14
8
Оказалось, что велосипед носит имя метода наименьших модулей. В англоязычных источниках Least Absolute Deviations. Методы решения базируются в том числе на симплекс-методе и МНК

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 12:34 
Заслуженный участник
Аватара пользователя


18/05/06
13174
с Территории
МНК служит для того, чтобы посмотреть, как надо, а потом сделать примерно так же?

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 13:02 


22/10/14
8
Не совсем. Это итеративный процесс. Отсылаю к древней книжке Мудров В.И. Кушко. В.Л. Метод наименьших модулей.

 Профиль  
                  
 
 Re: Аппроксимация с нормой L1
Сообщение12.02.2015, 14:14 
Заслуженный участник
Аватара пользователя


11/03/08
5623
Москва
Там взвешенный МНК используется. Веса подбираются так, чтобы результат минимизации взвешенных квадратов был бы эквивалентен минимизации по модулям.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group