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

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

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

[Make_Pic]

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

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

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

[mikola1]

Можно подробнее по п.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.

Сообщение отредактировал mikola1 - Jun 24 2005, 21:45

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

 

[Make_Pic]

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

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

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