нужен алгоритм нахождения максимума, простой с апроксимацией для МК! Опции

[Make_Pic]

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

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

[arttab]

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

[Eugeno]

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

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

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

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

[Fast]

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

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

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

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

[Alexandr]

 
1. выбираем второй "опорный" справа или слева от максимума (который больше). Точный максимум будет расположен в интервале между двумя этими отсчетами.

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

Эскизы прикрепленных изображений

 

[Fast]

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

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

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

[Make_Pic]

[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 Гц.

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

[Fast]

На входе устройства две частоты речевого диапозона 300- 2000Гц. Точные частоты неизвестны но разнесены на 200 Гц. После АЦП (10 бит) и обработки 256-точечного FFT...

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

[Make_Pic]

На входе устройства две частоты речевого диапозона 300- 2000Гц. Точные частоты неизвестны но разнесены на 200 Гц. После АЦП (10 бит) и обработки 256-точечного FFT...

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

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