Курсовая работа: Методы расчета цифровых БИХ-фильтров и вид целевой функции

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

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

Помимо этих двух требований для обеспечения сходимости модельной схемы необходимо еще одно условие, которое накладывается на множество уровней целевой функции. Для функции F(x) и числа множеством уровней называется совокупность всех точек, для которых справедливо выражение F() . Дополнительное условие заключается в том, чтобы данное множество L(F()) было бы ограничено и замкнуто.

Таким образом, если

· функция F(x) непрерывна и дважды дифференцируема;

· ее множество уровней ограничено и замкнуто;

· функция F(x) существенно убывает от итерации к итерации и на каждом шаге угол между вектором-градиентом и направлением поиска всегда не равен 90 градусам на фиксированную положительную величину,

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

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

Четвертый шаг модельной схемы предполагает вычисление длины шага, то есть скалярной величины , которая должна удовлетворять условию спуска:

Для того, чтобы выбрать , удовлетворяющий этому условию, необходимо минимизировать значение целевой функции вдоль направления как функцию одной переменной (скалярной) h. То есть минимизировать функцию:

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

Для нахождения минимума используются две группы методов одномерной оптимизации:

1. Эффективные методы одномерного поиска (метод Золотого сечения и метод Фибоначчи);

2. Методы полиномиальной интерполяции (Пауэлл, Ньютон, сплайн-интерполяция).

Для конкретизации модельной схемы помимо процедуры вычисления длины шага h_k необходимо также задавать алгоритм расчета требуемого направления поиска .

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

В этом случае возникает проблема выбора направления поиска . Именно способ вычисления и определяет «лицо» алгоритма безусловной минимизации. Поэтому названия алгоритмам оптимизации даются по реализованным в них процедурам вычисления .

В данной курсовой работе в качестве метода синтеза применяется метод сопряженных градиентов. В группе данных методов процедура вычисления направления поиска не предполагает решения каких либо СЛАУ. Эти методы принципиально отличаются от методов Ньютна и квазиньютоновских методов.

Рассмотрим задачу поиска минимума квадратичной функции вида:

с,G - вектор и полноопределенная матрица, независящие от вектора .

Предполагается, что нам известно к-тое приближение в точке минимума и (к+1) линейно независимых векторов .

Будем искать точку минимума целевой функции Ф() на линейном множестве векторов +Р_к , где Р_к – (к+1)-мерное множество, образованное линейно независимыми векторами.

Множества, образованные вида +Р_к называются линейными многообразиями.

Задача сводится к нахождению точки минимума Ф() на этом линейном многообразии.

Для решения этой задачи сначала вводится матрица Р_к =[]. Введение такой матрицы позволяет сформулировать задачу поиска минимума функции Ф() на многообразии +Р_к следующим образом: найти