Аппроксимация

[Shurikenix]

Здравствуйте.
Подскажите, пожалуйста, какими методами можно решить вот такую аппроксимацию:
$\sum\limits_{i} (f_1[f_2(x_i)] - y_i) = 0$

[shwedka]

Shurikenix в сообщении #504562 писал(а):

Здравствуйте.
Подскажите, пожалуйста, какими методами можно решить вот такую аппроксимацию:
$\sum\limits_{i} (f_1[f_2(x_i)] - y_i) = 0$

А не трудно ли изложить задачу полностью. Что дано, что нужно найти.
И еще не повредит указать учебник, по которому вы учитесь.

[Shurikenix]

Да, пожалуйста.
$f_2(x) = - \frac{\sqrt{P^2+x-2xP}-P}{2P-1}$

$f_1(x) = (1-x^2)A + 2x(1-x)B + x^2C$

То есть, получается
$f_1[f_2(x)] = (1-f_2(x)^2)A + 2f_2(x)(1-f_2(x))B + f_2(x)^2C$
$x \in [0; 1]$, шаг инкремента фиксированный.
Соответственно, для аппроксимации нужно найти коэффициенты A, B, C, P.
Что можете посоветовать?
А учебника никакого нет. Давно уже не учусь.

[shwedka]

Ответ. подставьте данные функции в Ваше уравнение, получите условие для искомых коэффициентов. Одно уравнение для четырех коэффициентов. Плохо, слишком много свободы. подумайте над задачей. Что-то Вы перепутали или недописали. А совсем хорошо будет, если укажете источник задачи.

[Евгений Машеров]

В такой постановке, как у Вас, задача выглядит несколько тривиальной. Переносим сумму по y в правую часть. Берём произвольное P, такое, чтобы $f_2(x)$ имела бы значение при всех x, берём произвольные A, B, C, находим сумму слева и справа и затем домножаем A, B, C на отношение правой части к левой.
Вероятно, разность под знаком суммы возводится в квадрат (или берётся абсолютная величина, максимум и т.п.)? Но тогда надо не занулять, а минимизировать, что обычно и понимается под аппроксимацией.
Если там квадрат - это задача нелинейной регрессии (нелинейного МНК). В зависимости от Ваших средств (в смысле софта, компьютера и т.п.) можно рассматривать, как оптимизационную общего вида по P, A, B, C (для квадратов путь не лучший, но для некоторых функций общего вида иначе не выйдет), воспользоваться каким-то методом для нелинейной регрессии (Левенберга-Марквардта, скажем) или же, заметив, что по A, B, C задача линейна, а нелинейность связана с параметром P, решать, как серию линейных регрессий при разных P (этот параметр можно попросту перебирать по сетке, или же рассматривать его подбор, как задачу одномерной минимизации).

[Shurikenix]

shwedka в сообщении #504712 писал(а):

Ответ. подставьте данные функции в Ваше уравнение, получите условие для искомых коэффициентов. Одно уравнение для четырех коэффициентов. Плохо, слишком много свободы. подумайте над задачей. Что-то Вы перепутали или недописали. А совсем хорошо будет, если укажете источник задачи.

В данном случае можно было бы и одно уравнение написать, но представляете, какая громоздкая получилась бы запись?
Я ничего не перепутал. Источник задачи - аппроксимация полиномами Бернштейна, в данном случае кривыми Безье. Эти две формулы для кривой второй степени. Если взять четвертую степень, то $f_1(x)$ будет уже совершенно другой - не формула, а итерационный процесс по методу Ньютона. Я уже создавал ранее тему на эту тему (простите за каламбур), но никто ничего не ответил, пришлось зайти с другой стороны.

Евгений Машеров в сообщении #504749 писал(а):

Вероятно, разность под знаком суммы возводится в квадрат (или берётся абсолютная величина, максимум и т.п.)? Но тогда надо не занулять, а минимизировать, что обычно и понимается под аппроксимацией.

Да, я специально не стал указывать, потому как еще не знаю какой метод лучше подойдет - МНК, МНМ, равномерное приближение. Подскажите, пожалуйста, есть ли еще какие-нибудь (1-й вопрос)? Я только эти три знаю.

Цитата:

Если там квадрат - это задача нелинейной регрессии (нелинейного МНК). В зависимости от Ваших средств (в смысле софта, компьютера и т.п.) можно рассматривать, как оптимизационную общего вида по P, A, B, C (для квадратов путь не лучший, но для некоторых функций общего вида иначе не выйдет), воспользоваться каким-то методом для нелинейной регрессии (Левенберга-Марквардта, скажем) или же, заметив, что по A, B, C задача линейна, а нелинейность связана с параметром P, решать, как серию линейных регрессий при разных P (этот параметр можно попросту перебирать по сетке, или же рассматривать его подбор, как задачу одномерной минимизации).

Да, задача по A, B, C линейна. Для поиска P я уже сделал процедуру поиска методом деления отрезка пополам, коэффициенты A, B, C для текущего P находятся при помощи МНК. Но, как я писал уже выше, если будет кривая N-й степени, то количество P будет равно N - 2. И вся загвоздка в том, как мне находить такое количество. Если перебором, то получается хрень какая-то, уже пробовал, наверное, мой алгоритм - не то что нужно. Какие существуют методы решения путем перебора, кроме Монте-Карло для N неизвестных (2-й вопрос)? Я ничего найти не могу, вот и ищу помощи на форуме.

[mserg]

Эти задача известна как «глобальная оптимизация». Кроме околомаргинальных методов полуслучайного поиска есть еще и высокотехнологичные, «гарантирующие» оптимум. Погружение в предмет – несколько лет; минимальная программная реализация – сотни тысяч строк кода. Например:
http://www.coin-or.org/projects/Couenne.xml
Не исключаю, что вашу задачу можно решать учебным AMPL с помощью Couenne.

[Евгений Машеров]

Не понял утверждения:

Цитата:

если будет кривая N-й степени, то количество P будет равно N - 2

Из Вашей первоначальной записи следует, что P - единственный параметр. Независимо от степени $f_1$

Что до выбора критериев, кроме МНК, МНМ или чебышевского приближения - известную популярность приобрели "робастные", в которых пытаются совместить устойчивость к грубым ошибкам, несвойственную МНК, МНМ в этом отношении лучше, и эффективность МНК. Описание их есть в книгах:
Хьюбер "Робастность в статистике"Пер. с англ. - М.: Мир, 1984,
Хампель Ф., Рончетти Э., Рауссеу П., Штаэль В. Робастность в статистике. Подход на основе функций влияния М.: Мир, 1989.
Лонер Р.Л. Устойчивые статистические методы оценки данных М.: Машиностроение, 1984.
и др.

[Shurikenix]

Спасибо, санитар Женя.
Первоначальная запись для полинома второго порядка.