Имеем 4 или 5 точек прендадлежащих функции, функция непрерывная, как малой "кровью" и быстро найти максимум (предпологаем, что он должен где то быть между точками)?

Прогу надо на микроконтроллер посадить.

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

Может вытолкнуть максимум "пузырьком" правда это не быстро зато надежно.

P.S. Sorry, что то я стормозил с "пузырьком" вопрос неправильно понял

Оригинальней ничего не надо. Задача самодостаточна.

По четырём точкам можно найти однозначную апроксимацию участка кривой полиномом третьей степени x(t) = a*t*t*t + b*t*t + c*t*t + d*t + e;
Производную полинома приравниваем к нулю и вуаля - результат.

Полином третьей степени имеет хорошую устойчивость в силу своей простоты, а решение по четырём точкам однозначно - это тоже больщое преимущество.

Не согласен с Eugeno . Задача не является самодостаточной. У Eugeno . ошибка, лишний коэффициент при квадрате аргумента.

1. Постановка задачи звучит некорректно. Фактически задача должна быть
разбита на две подзадачи
а) интерполяция функции
б) поиск максимума для интерполированной функции

2.1 Совсем малая кровь. Рассматривать линейную аппроксимацию, тогда максимум совпадет с одной из точек.

2.2 Использовать интерпляционный полином Лежандра. Как раз то, что хотел предложить Eugeno

Pn(x)=f(x0)*{(x-x1)*(x-x2)*...*(x-xn) / {(x0-x1)*(x0-x2)*..*(x0-xn)}}+
+f(x1)*{(x-x0)*(x-x2)*...*(x-xn) / {(x1-x0)*(x1-x2)*..*(x1-xn)}}+...+
+f(xn)*{(x-x0)*(x-x1)*...*(x-xn_1) / {(xn-x0)*(xn-x1)*..*(x1-xn_1)}}

где (n+1) - кол-во точек,
В этом случае утверждается
f_апп ~= Pn(x)

Для поиска максимума берется аналитически производная (для ленивых - Maple), приравнивается к нулю. Получаете (n-1) корней, т.е. получаете точки экстремумов. Подставляете их поочередно в Pn(x) и выбираете максимум; или ищете вторую производную, находите те точки, для которых она < 0 - для этих точек будет локальный максимум

2.3 Использовать кубическую интерполяцию, минимальное количество точек - 4. Кубическая интерполяция дает построение функции непрерывной саму функцию, первую и вторую производную. Алгоритм несложный и с ним можно разобраться. Зато он лишен недастатков полиномной аппроксимации.
Поиск максимума - такой же как и для случая 2.1

2.4 Полиномы Чебышева.

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

Полином к нулю приравнять, конечно, хорошо, только как решать на МК это дело?
Предлагаю итеративный вариант на базе интерполятора степени N (пусть N=4), например Лагранжа.
вначале находим максимальный отсчет в регистре, затем

1. выбираем второй "опорный" справа или слева от максимума (который больше). Точный максимум будет расположен в интервале между двумя этими отсчетами.
2. Делим интервал пополам, вычисляем посредством интерполяции значение функции в данной точке.
3. Измеряем дельту, как разность максимума и вычисл. значения
4. Если дельта со знаком " - ", то значение функции в точке больше, чем максимум, тогда [максимум = значение функции в точке]
5. Устанавливаем новые границы интервала, соотв. одна - максимуму, вторая - "опорному" отсчету.
6. Если [дельта < ПОРОГ] - или [итерация < ITERmax] - выход, иначе идти к 1.

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

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

[quote=Alexandr,Jun 21 2005, 11:49]
Производная и экстремумы, боюсь, тоже ничего не дадут. Не факт, что аналитически мы получим истинные значения точного максимума и другие экстремумы для функции на рисунке.

Это случай, когда полоса сигнала зарезана. Т.е. частота выборок меньше, чем удвоенная макс. частота спектра сигнала (при разложении функции в ряд Фурье).
Да, такая штука будет имеет место.
Обходится увеличением частоты выборок, чтобы эта частота была больше 4х на макс. частоту спектра сигнала + ФНЧ по полосе сигнала.
Если такое условие трудно достижимо (при 2.5-3 :1, вместо 4:1), то можно попробовать различные виды сплайна в качестве интерполятора, но ФНЧ обязательно.

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

[quote=Fast,Jun 21 2005, 12:25]
[quote=Alexandr,Jun 21 2005, 11:49]
Производная и экстремумы, боюсь, тоже ничего не дадут. Не факт, что аналитически мы получим истинные значения точного максимума и другие экстремумы для функции на рисунке.

Это случай, когда полоса сигнала зарезана. Т.е. частота выборок меньше, чем удвоенная макс. частота спектра сигнала (при разложении функции в ряд Фурье).
Да, такая штука будет имеет место.
Обходится увеличением частоты выборок, чтобы эта частота была больше 4х на макс. частоту спектра сигнала + ФНЧ по полосе сигнала.
Если такое условие трудно достижимо (при 2.5-3 :1, вместо 4:1), то можно попробовать различные виды сплайна в качестве интерполятора, но ФНЧ обязательно.

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

[/quote]

На входе устройства две частоты речевого диапозона 300- 2000Гц. Точные частоты неизвестны но разнесены на 200 Гц. После АЦП (10 бит) и обработки 256-точечного FFT (для большего количества точек нет не RAM, не ресурсов). Получаем спектральное распределение после FFT. Берем несколько точек выше определеного уровня и далее
ищем экстремум для определения частоты с более высокой точностью чем 4000/256 Гц.

Может быть иначе, но как не придумал.

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

Найдите pls! А то совсем я закопался

Можно подробнее по п.2 - Как интерполировать (функция неизвестна, можно предположить, что она sinc)? Желательно расписать для меня чайника!

To Make_Pic,
Интерполировать функцию нужно исходя из физического смысла сигнала, который мы снимаем. Иначе смысл и ценность от этой интерполяции??? Т.к. насколько я понял сигнал речевой, то нужно примерно представлять, какому закону распределяется его спектральная плотность. А этого я не знаю (здесь я не силен, но смею предположить, нечто подобное на распределение Гаусса с нарушением симметрии).

To Fast, интерполирование по двум точкам – крайне не благодарная задача. См. рисунок от Alexander, оставив только две точки

А для чайников исходя из предложенного Fast с использованием интерполяционного полинома Лагранжа второй степени следующий алгоритм без всяких циклов.
п.1 Выбираем максимум функции (x1,y1) и берем две соседние точки (x0,y0) и (x1,y2), так чтобы выполнялись условия x0<x1<x2, и y1>=y0, и y1>=y2.
п.2 Находим точку экстремума (формула 3)
п.3 Подставляем найденное значение в полином (формула 1)
п.4 Полученное значение и есть максимум.

P.S. Можно уменьшить объем вычислений, введя промежуточные переменные типа dx01=x0-x1 для формул 1 и 2. На рис. представлены формулы, записанные в Maple.

Я вроде выше писал, что сигнал - синус/частота, посему симетричный гаусс, дык как интерполировать - КТО-НИБУДЬ ПОДСКАЖЕТ???

Кстати на телесистемах некий alostap предложил оригинальный метод, ссылаясь на статью Нажмите для просмотра прикрепленного файла

>Есть гармонический сигнал, есть его DFT:
>X(i)=sum(x(k)exp(-1j*2*pi*k*i/N)
>, требуется измерить как можно точнее частоту сигнала.
>Алгоритм примерно таков:
>1) Находите два соседних отчета для которых abs(X(i))+abs(X(i+1))>максимальна.
>2) Отклонение от сетки частот DFT будет =
>abs(X(i+1))/(abs(X(i))+abs(X(i+1)))/N, значение частоты относительное,
>X(i)- максимальный отсчет
>
>IEEE trans. on comm No 7 2003
>
Опять же про интерполяцию функции - как ее реализовать -
НО неясен п.2
Можно поподробнее как здесь связать известные точки DFT и искомую?
Вроде из этой формулы нельзя, а точнее я не понял алгоритм.

Все же настоятельно рекомендую МНК, и посмотреть стаью 2inc_new.pdf f cthdtht (\upload\doc\)
Просто на заметку, очень может иногда помочь.

P.S. Добавил файл к посту, на всякий случай.

P.P.S. В примере оценки гауса есть ошибки в вычислениях, их просто необходимо повторить самому (где-то индексы напутаны).

mikola1, айяйяй, Вы меня откровенно за чайника держите да еще других в заблуждение вводите.
Ну где там полином 2-й степени??? Я же говорю: степени N (пусть, например, N=4). Это центральный интервал для полинома сужается (я так понимаю, с этим путаница)...
Вот нашел функцию, переделал для этой задачи - ловите. Там Лагранж 7-й степени, исследовал как-то - лучшие результаты получаются для N=6-8.
Блин.

Хочу извиниться перед Fast, я действительно неправильно Вас понял.
И не Вас я держу за чайника, а всего лишь повторил слова автора темы.

Однако прежде чем стрить полином, нужно помнить о теореме. "Для
любых f(xj) и различных узлов xj 0<=j<=n, существует единственный
интерполяционный полином". Простым языком говоря - сколько точек участвует
в интерполяции, такой степени и следует использовать полином

To Major Спасибо за бдительность, только это не оценка Гаусса.
Ошибка была в первой формуле во втором слагаемом в числителе. Заменил (x-x1) на (x-x2).
А по поводу МНК, возможно Вы и правы, МНК - вещь хорошая в большинстве случаев..

To Make_Pic. Предлагаю Вам выложить два файла. В первом набор точек с частой
выборкой, второй - с той выборкой по которой собираетесь искать максимум.
И объявит конкурс на лучшее решение , с призом

P.S. (to Make_Pic) От sin/cos до полиномов один шаг. Разложение Тейлора ...