Аппроксимация данных экспонентой - область поиска минимума?

[DeadlineX]

Здравствуйте, всем,
Задача следующая: есть последовательность данных, более или менее хорошо укладывающаяся на экспоненту вида $y=C-Ae^{-Bx}$. Надо получить параметры $A$, $B$ и $C$. Характерный вид кривой приведен на скриншоте.
.
Для нахождения параметров берем, например, каждую 20-ю точку и по пяти таким выбранным точкам минимизируем сумму разностей квадратов $(y_i - f(A,B,C))^2$. Вопрос в том, как задать область поиска минимума, так, чтобы он там точно был? Я только очень приблизительно знаю характер ожидаемой кривой.
Пока что придумал только так:

  // здесь yv[i] - массив исходных данных
  // A
  krx[0][0] := 0;
  krx[0][1] := 4 * (yv[length(yv) - 1] - yv[0]);
  // B
  krx[1][0] := 0;
  krx[1][1] := 0.1;
  // C
  krx[2][0] := yv[length(yv) - 1];
  krx[2][1] := krx[2][0] + 4 * (yv[length(yv) - 1] - yv[0]);
  // точка старта поиска минимума
  x[0] := 0.5 * (krx[0][1] + krx[0][0]);
  x[1] := 0.5 * (krx[1][1] + krx[1][0]);
  x[2] := 0.5 * (krx[2][1] + krx[2][0]);
  //

Можно, конечно, задать какие-то очень широкие пределы, но я не уверен, что при этом не возникнет проблем с самим алгоритмом минимизации. Поэтому и возник вопрос, а нельзя ли как-то очень грубо оценить параметры, хотя бы $A$ и $B$, поскольку от $C$ зависимость, очевидно, квадратичная. Кроме того, я, в принципе, знаю его верхний предел, поскольку это конкретная физическая величина.

Заранее спасибо за любые подсказки.

[Deggial]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

DeadlineX
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: возвращено

[dsge]

Можно допустить, например, что
$C=y_{\max}$, $C-A=y_{\min}$, $y_{\max}-y_{\min}=A Be^{-x_{mean}}$

[Александрович]

Можно сначала избавиться от $C$ численным дифференцированием, затем найти $A$ и $B$, уточнить $C$.

[DeadlineX]

dsge в сообщении #1367280 писал(а):

Можно допустить, например, что
$C=y_{\max}$, $C-A=y_{\min}$, $y_{\max}-y_{\min}=A Be^{-x_{mean}}$

Я бы сказал, что (как я и написал выше), $C_{\min}=y_{\max}$. Вопрос был как раз, как оценить верхний предел $C_{\max}$. Хотя, как я и написал выше, верхний предел для $C$ я могу задать исходя из условий задачи (типа, если эта величина измеряется в процентах, то понятно, что больше 100 она быть не может). Ваше выражение для $B$ не очень понятно. $B_{\min}=0$. Из этой формулы находим что? $B_{\max}$?

Александрович в сообщении #1367332 писал(а):

Можно сначала избавиться от $C$ численным дифференцированием, затем найти $A$ и $B$, уточнить $C$.

Это Вы объясняете, как напрямую находить аппроксимационные коэффициенты? Я пробовал всякое, и через логарифмирование и через производные. Получается очень плохо. Экспонента очень пологая, и через МНК получается очень неточный результат. Поэтому я взял универсальный симплексный алгоритм минимизации функции $N$ переменных и им "в лоб" минимизирую. Безо всяких МНК. Работает вроде быстро, по крайней мере, меня устраивает. Но ему надо задать область определения целевой функции, причем, желательно, поуже. Чтобы меньше итераций делал.

[Александрович]

DeadlineX в сообщении #1367341 писал(а):

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

Аппроксимируйте линейной зависимостью, найдёте верхний предел целевой функции.

DeadlineX в сообщении #1367341 писал(а):

и им "в лоб" минимизирую. Безо всяких МНК.

Если целевая функция - сумма квадратов невязок, то это тоже МНК.

[dsge]

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

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

Если отклонения невелики, а отсчёты равномерны, вполне помогает переход к первым разностям. После чего логарифмируем и работаем с линейной регрессией. Рост отклонений может привести даже к отрицательным значениям под логарифмом, и такой простой подход не работает (а если не настолько велики, то всё равно может быть сильное искажение модели).
Общий подход - Левенберг-Марквардт, последовательно применяемая для уточнения значений параметров линеаризованная модель, в которой регрессоры производные по параметрам, а регрессанд - отклонения наблюдаемых значений от оцененных на предыдущем шаге нелинейной функцией (и регуляризация, поскольку производные сильно коррелированы, иногда и линейно зависимы).
Частный - перебирать C по сетке (или каким-то методом одномерной оптимизации, максимизируя коэффициент корреляции), на каждом шаге оценивая $z_i=y_i-C=Ae^{-Bx}$ переходя к $v_i=\ln(y_i-C)=\ln A - Bx$ и обычной парной линейной регрессией.

[DeadlineX]

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

Общий подход - Левенберг-Марквардт, последовательно применяемая для уточнения значений параметров линеаризованная модель

Это что-то типа вот этого? http://www.davdata.nl/math/expfitting.html Я его попробовал. Он работает только на "хороших" экспонентах (со сравнительно большими $B$). В моем случае он дает расходящиеся итерации.

[mihiv]

Можно попробовать при заданном $B$ находить $A,C$ по МНК. Таким образом потребуется задать лишь диапазон значений параметра $B$ и пройти его с небольшим шагом.

[DeadlineX]

Можно взять оценку для $B$, как $B=-\frac{y^{\prime\prime}}{y^{\prime}}$, а затем, зная $B$, вычислить $A=\frac{y^{\prime}}{Be^{-Bx}}$, но такая оценка $B$ - это именно приближение, а никак не верхний предел. В частности, по моим точкам значение $B$ получается несколько меньше, чем у рассчитанной экспоненты. Ничего более умного, чем умножить его на некое число больше единицы, в голову не приходит.

-- 10.01.2019, 15:04 --

mihiv в сообщении #1367402 писал(а):

Можно попробовать при заданном $B$ находить $A,C$ по МНК. Таким образом потребуется задать лишь диапазон значений параметра $B$ и пройти его с небольшим шагом.

На мой взгляд это будет гораздо длиннее, чем напрямую минимизировать. Но вопрос остается про $B$ (см. пост выше).

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

DeadlineX в сообщении #1367390 писал(а):

Это что-то типа вот этого? http://www.davdata.nl/math/expfitting.html

Нет, там не Левенберг-Марквардт. Там что-то похожее на то, что я предлагаю, как упрощённый подход для малых возмущений.

[DeadlineX]

Допустим, у нас 100 точек. Если вторую производную (см. выше) $y^{\prime\prime}$ вычислять не по трем точкам: $y^{\prime\prime}=\dfrac{y_{99}+y_0-2y_{49}}{2500}$, а взять участки с интервалами в несколько точек в начале и конце диапазона: $y^{\prime\prime}=\dfrac{y_{99}-y_{94}-y_5+y_0}{25}$, то получится сильное завышение величины второй производной. Может так сделать? Не знаю, насколько это корректнее, чем просто умножить предыдущее выражение на некий коэффициент.

-- 10.01.2019, 17:07 --

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

Нет, там не Левенберг-Марквардт. Там что-то похожее на то, что я предлагаю, как упрощённый подход для малых возмущений.

Я плохо выразился, я и имел в виду Ваше предложение. Оно практически это же самое с виду, что и описанное там. Но, когда $A$ порядка единиц, а $B$ - порядка пары десятков тысячных, та программа не работает.

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

Ну, основное отличие предложенного мной приближённого подхода от там описанного - что я бы регрессию строил, по всем точкам, а там оценивают значение B по последовательным парам точек, а затем усредняют оценки. При малом B и наличии ошибки в наблюдениях там может быть даже последующее меньше предыдущего, то есть отрицательное под логарифмом (но это не само страшное, просто отбрасывается; хуже если положительное, но около нуля, получится после логарифмирования выброс и сильное искажение оценки). Для регрессии вроде не так страшно.
Но можно оценить B иначе, возможно, при малом B так лучше будет, всего по трём точкам.
Начальной точке ряда, конечной точке и средней между ними (при чётном числе точек можно интерполировать, или при неравномерных отсчётах). Если расстояние между первой и средней и средней и последней $\tau$, то $y_0=C-A$, $y_{\tau}=C-Ae^{-B\tau}$, $y_n=y_{2\tau}=C-Ae^{-2B\tau}$
Тогда $\Delta_0=y_{\tau}-y_0=-Ae^{-B\tau}+A$, $\Delta_1=y_n-y_{\tau}=-Ae^{-2B\tau}+Ae^{B\tau}$ и
$\frac {\Delta_1}{\Delta_0}=e^{-B\tau}$
Отсюда оценка $B=-\frac 1 {\tau}\ln{\frac {\Delta_1}{\Delta_0}}$

[DeadlineX]

Вот когда оно все так написано, то возникает естественный вопрос, что ж я сам-то до этого не додумался?
Это же прямо следует из уравнения экспоненты! Но, видите ли. в чем дело. Вы опять же дали оценку для $B$.
Обратно уходить на нахождение параметров экспоненты каким-либо методом, основанном на ее производных или на логарифмировании и сведении задачи к линейной регрессии, я уже не хочу. Дело в том, что на самом деле этот ряд совсем даже не экспонента. Если его прологарифмировать, вид функции будет скорее ближе к самой функции (по форме кривой), чем к линейной. А в идеале задача как раз и состоит в том, чтобы по некоторому начальному отрезку кривой найти ее асимптоту. Поэтому, если завтра захочется уточнить вид аппроксимирующей кривой, то весь алгоритм придется переделывать. Универсальному же алгоритму минимизации это все без разницы.
Вот поэтому мой основной вопрос и есть - как задать верхний предел для $B$. А предел для $A$, видимо, можно получить, зная предел для $B$ и грубо рассматривая зависимость, как экспоненту. Ну или просто (как уже было сказано ранее), учитывая, что верхний предел $C$ имеет некое физическое ограничение, просто принять $A_{\max}=C_{\max}-y_0$