3.2.5. Примеры и сравнение методов

Здесь приведено несколько примеров фильтров, спроектированных с помощью алгоритмов, описанных в пп. 3.2.3 и 3.2.4. Речь идет о прямом применении линейного программирования и новом алгоритме. Рассматриваются факторы, влияющие на эффективность обоих методов. В их числе: значение того факта, что решается не двойственная, а основная задача линейного программирования; влияние числа точек с ограничениями; влияние числа независимых переменных. Кроме того, оцениваются вычислительная сложность и возможости каждого алгоритма.

Как отмечается в п. 3.1.2, если задача проектирования фильтра сформулирована как основная задача линейного программирования, то число строк в матрице ограничений намного превышает число столбцов. Если же эту задачу сформулировать в виде двойственной задачи линейного программирования, то число столбцов будет намного превышать число строк, что позволяет отыскать решение более эффективным способом. В случае прямого применения линейного программирования было установлено, что при решении основной задачи наиболее сложные фильтры, которые могли быть надежно спроектированы с помощью описанного комплекса линейного программирования,

имели импульсную характеристику размерности 7X7 (25 независимых коэффициентов импульсной характеристики). Был даже успешно спроектирован один фильтр с импульсной характеристикой размерности 9X9. Число точек с ограничениями, обработка которых не вызывает особых затруднений, составляет приблизительно 600 при полном числе ограничивающих равенств около 1200. Когда задача была переформулирована как двойственная задача линейного программирования, оказалось, что можно проектировать фильтры с импульсной характеристикой размерности 9X9 (41 независимый коэффициент) при использовании нескольких тысяч точек с ограничениями.

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

Таблица 3-1 (см. скан) Сравнение основной и двойственной форм задачи линейного программирования

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

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

аппроксимацией на данном множестве точек с ограничениями. С увеличением числа точек с ограничениями (а следовательно, числа столбцов в матрице ограничений) решение приближается к искомому решению, которое является наилучшей аппроксимацией на соответствующем подмножестве области Использование конечномерного множества точек с ограничениями для получения аппроксимации функции в пределах указанной области называется отбором, а ошибки, вносимые при этом, называются ошибками отбора [6].

Чтобы продемонстрировать влияние отбора на результирующее решение, один и тот же фильтр нижних частот был спроектирован четырьмя различными способами. Импульсная характеристика этого фильтра имеет размерность 7X7, причем единственным принятым допущением является допущение о действительности импульсной и частотной характеристик; таким образом, всего имеется 25 независимых коэффициентов импульсной характеристики. Радиус границы полосы пропускания ; радиус границы полосы задерживания Местоположение точек с ограничениями было определено с помощью метода, описанного в п. 3.2.3. Первые три решения были получены путем прямого применения линейного

Фиг. 3.7. Влияние отбора точек с ограничениями. (Размерность решетки точек с ограничениями

(кликните для просмотра скана)

Фиг. 3.10. Влияние отбора точек с ограничениями. (Новый алгоритм.}

программирования. Соответствующие перспективные виды представлены на фиг. Четвертое решение (фиг. 3.10) было получено с помощью нового алгоритма. В качестве исходной аппроксимации для этого четвертого решения было использовано первое из упомянутых трех решений.

На фиг. видно, что выбор точек с ограничениями мало влияет на форму частотной характеристики. В других примерах были отмечены более заметные изменения формы частотной характеристики. Фиг. 3.10 ясно показывает, что функция ошибки представленной частотной характеристики остается почти неизменной на границах Именно такие ситуации, как эта, привели к разработке метода нахождения локальных максимумов и минимумов функции ошибки, описанного в п. 3.2.4. Интересно отметить, что решение на фиг. 3.10 почти удовлетворяет условиям ограничений по симметрии хотя в этом направлении не было предпринято никаких попыток.

В табл. 3.2 приведены сравнительные данные по всем четырем решениям. Здесь дельта обозначает максимальное

абсолютное значение ошибки на множестве точек с ограничениями. Норма ошибки есть максимальное абсолютное значение ошибки на массиве 256X256 отсчетов частотной характеристики, вычисленных с помощью БПФ. Таблица с очевидностью показывает, что время вычислений увеличивается с увеличением числа столбцов в матрице ограничений, а дельта увеличивается с повышением плотности множества точек с ограничениями. Чем плотнее расположены точки с ограничениями, тем лучше аппроксимация (т. е. меньше норма ошибки) и тем меньше относительная ошибка.

Таблица 3.2 (см. скан) Влияние отбора точек с ограничениями

Время вычислений, которое требуется для обеспечения сходимости нового алгоритма, лишь на 22% превышает время вычислений для нахождения решения с 1311 точками с ограничениями. Из 13 итераций нового алгоритма наиболее короткая имела всего 47 точек с ограничениями, а наиболее длинная — 79 точек с ограничениями. Интересно отметить, что лишь три итерации (занявшие 3,61 мин) нового алгоритма дали относительную ошибку которая несколько меньше ошибки, полученной в наиболее объемном решении в случае прямого применения линейного программирования.

Другой фильтр, спроектированный с помощью нового алгоритма, представлен на фиг. 3.11. Его импульсная характеристи» имеет размерность 9X9 (41 независимый коэффициент), а радиусы границ полос пропускания и задерживания равны соответственно. Сходимость алгоритма наступала после 12 итераций с дельтой 0,115725 и нормой ошибки 0,115726. Полное время вычислений составило 31,75 мин.

Фиг. 3.11. Частотная характеристика фильтра нижних частот без ограничений по симметрии.

На фиг. 3.12 показано расположение точек, которые были бы использованы в качестве точек с ограничениями при вычислении следующей итерации. Фиг. 3.12 иллюстрирует два важных обстоятельства. Во-первых, наличие гребней частотной характеристики вынуждает находить слишком много локальных максимумов и минимумов. Поскольку имеются 42 базисные переменные для данной задачи, следует ожидать, что будет найдено приблизительно столько же локальных максимумов и минимумов. На самом же деле в рассматриваемом случае было найдено 109 локальных максимумов и минимумов. Выше было отмечено, что это обстоятельство не создает трудностей теоретического плана, хотя и приводит к увеличению полного времени вычислений. Во-вторых, важно отметить, что точки с ограничениями, соответствующие базисным переменным, в результирующем решении, а следовательно, и в предшествующих итерациях часто появляются парами (иногда тройками). Это явление наблюдалось почти во всех примерах проектирования фильтров. Объяснить это явление не удалось.

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

Фиг. 3.12. Размещение точек с ограничениями для частотной характеристики на фиг. 3.11; -локальные максимумы и минимумы, О — базисные переменные.

Была поставлена цель просто определить наилучшую аппроксимацию функции

Тем не менее оказалось, что результирующее решение почти полностью удовлетворяет условиям ограничений по симметрии. Не имеется доказательства того, что это должно всегда происходить в случае фильтров (нижних частот), подобных рассматриваемым. Однако этот факт отмечался и в ряде других примеров. Если ограничения по симметрии установить заранее, то будет найдено решение, которое иллюстрирует фиг. 3.13. При любом практическом подходе можно считать, что это решение тождественно решению, показанному на фиг. 3.11. В данном

Фиг. 3.13. Частотная характеристика фильтра нижних частот с ограничениями по симметрии.

случае имеется всего 15 независимых коэффициентов импульсной характеристики. Сходимость алгоритма наступила после 18 итераций с дельтой 0,115726 и нормой ошибки 0,115727. Полное время вычислений составило 17,45 мин. Интересно отметить, что при наложении ограничений по симметрии нахождение оптимального решения потребовало шести дополнительных итераций алгоритма, однако время вычислений уменьшилось на 14,3 мин.

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

Было наложено ограничение по симметрии На фиг. 3.14-3.17 показаны частотные характеристики каждого фильтра в одном квадранте. Табл. 3.3 содержит сравнительные данные по этим фильтрам. В каждом

Таблица 3.3 (см. скан) Примеры дифференциаторов

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

Фиг. 3.14. Аппроксимация частотной характеристики идеального дифференциатора. (Размерность импульспой характеристики 7X7.)

Фиг. 3.15. Аппроксимация частотной характеристики идеального дифференциатора. (Размерность импульсной характеристики 13 X 13.)

получаемых при проектировании фильтров нижних частот. Объяснение этому не найдено. Также не имеет объяснения тот факт, что функция ошибки никогда не имела гребней. В каждой из итераций, выполненных во всех примерах, все локальные максимумы и минимумы располагались в изолированных точках функции ошибки. Интересно отметить, что в примере с импульсной характеристикой размерности 13X13 потребовалось иметь на одну итерацию больше, чем в примере с импульсной характеристикой размерности 15 X 15. Однако в целом полное время вычислений и время вычисления одной итерации увеличиваются с увеличением размерности импульсной характеристики. Переход от фильтра с 10 независимыми коэффициентами к фильтру с 45 независимыми коэффициентами обеспечил уменьшение дельты в 2,82 раза. При этом полное время вычислений увеличилось в 8,22 раза, а время вычисления одной итерации — в 2,32 раза.

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

(кликните для просмотра скана)

задачи линейного программирования без каких-либо исключений. На практике, однако, приходится беспокоиться о вычислительной сложности алгоритма. На сложность алгоритма указывает схема допусков, которой неизбежно приходится пользоваться при реализации алгоритма вследствие отсутствия арифметических устройств с бесконечной точностью. В основном требуется использовать допуски двух видов: по точности и по значимости. Допуски по точности позволяют проводить определенную самопроверку, что обеспечивает возможность приостановки вычислений на ранних стадиях в случае обнаружения существенной потери точности. Допуски по значимости налагаются таким образом, что значения, очень близкие к нулю, при выполнении вычислений заменяются нулями. Эти допуски также могут стать причиной досрочной приостановки вычислений, если будут отсутствовать «ненулевые» элементы матрицы ограничений, требуемые для продолжения вычислений.

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

Аналогичные замечания, очевидно, можно сделать в отношении вычислительной сложности нового алгоритма, поскольку при выполнении каждой итерации этого алгоритма приходится решать задачу линейного программирования. Сложность усугубляется тем обстоятельством, что в каждой итерации требуется находить локальные максимумы и минимумы функции ошибки. Выше уже обсуждались проблемы, возникающие при нахождении этих точек. Очевидно, что фактическое решение, получаемое в результате каждой итерации, зависит от выбора точек с ограничениями, однако очень трудно проследить такую зависимость. Как и прежде, в данном случае невозможно предсказать число итераций, которые потребуется вычислить. Максимальное абсолютное значение ошибки на множестве точек с ограничениями при переходе от одной итерации к следующей

возрастает, однако такое приращение может оказаться очень малым. В такой ситуации нельзя прекращать вычисление алгоритма, поскольку через несколько итераций величина приращения может вновь оказаться значительной. При относительно плотном множестве точек с ограничениями время для схождения нового алгоритма может оказаться сравнимым или меньшим времени, которое потребовалось бы для проектирования того же фильтра методом прямого применения линейного программирования. Однако иногда случается так, что новый алгоритм требует большего времени вычислений, давая лишь незначительное улучшение аппроксимации. Создается впечатление, что лучше всего пользоваться новым алгоритмом следующим образом: надо принять решение о допустимом значении относительной ошибки и прекратить вычисление после достижения этого значения. Если требуются более качественные аппроксимации, то их можно получить путем вычисления дополнительных итераций. В этом состоит важное преимущество нового алгоритма перед методом прямого применения линейного программирования, при котором в случае получения недостаточно хорошей аппроксимации требуется повторить все вычисления.

Новый алгоритм имеет и другие преимущества перед прямым применением линейного программирования. Во-первых, новый алгоритм предполагает вычисление наилучшей аппроксимации требуемой частотной характеристики на множестве 256 X 256 точек частотной области; напротив, задача линейного программирования решается только на множестве точек с ограничениями. В этой связи следует сделать два замечания. Первое заключается в том, что размерность есть практическое, а не теоретическое ограничение. Увеличив объем БПФ, можно получить более качественные аппроксимации на более плотных множествах. Однако концепция алгоритма остается неизменной. Второе замечание заключается в том, что решить задачу линейного программирования с ограничивающими уравнениями просто невозможно. Новый алгоритм имеет еще одно преимущество: он позволяет проектировать фильтры, размерность которых несколько превышает размерность фильтров, проектируемых другими методами. Это объясняется тем, что алгоритм фактически позволяет расчленить объемную задачу линейного программирования на ряд небольших задач. Поскольку время вычисления одной итерации и число итераций увеличиваются с возрастанием размерности фильтра, указанное преимущество, к сожалению, нельзя считать существенным, за исключением того случая, когда время вычислений не имеет никакого значения. Например, прямое применение линейного программирования ни разу не позволило успешно спроектировать фильтр с импульсной характеристикой

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