Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
Hauptverfasser:	Ромм, Я.Е., Тюшнякова, И.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2010
Schlagworte:	Прикладне програмне забезпечення
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/14672
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации/ Я.Е. Ромм, И.А. Тюшнякова// Пробл. програмув. — 2010. — № 2-3. — С. 593-603. — Бібліогр.: 16 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-14672
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-146722025-02-09T14:50:09Z Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации Program identification of zeroes and features of functions on the basis of sorting with the application to the digital filtration Ромм, Я.Е. Тюшнякова, И.А. Прикладне програмне забезпечення На основе сортировки синтезируются схемы устойчивой локализации и вычисления нулей полиномов и функций с учетом их кратности. Схемы отличаются от известных по построению на основе сортировки, свойством автоматической локализации области всех нулей и каждого нуля в отдельности, параллелизмом, а также вычислительной устойчивостью. С помощью сортировки строится схема приближенного вычисления полюсов комплексных функций с учетом порядка, алгоритмы приближенного вычисления вычетов функций в полюсах и, на этой основе, схема приближенного вычисления криволинейных интегралов по замкнутому контуру. Исследуется применимость метода для анализа цифровых фильтров с помощью обратного z-преобразования, для анализа временной функции линейной динамической системы и для анализа устойчивости дискретной цепи. On the basis of sorting schemes of steady localization and calculation of zeroes of polynomials and functions with consideration of multiplicity are synthesized. Schemes differ from known ones by construction on the basis of sorting, by property of automatic localization of area all zeroes and each zero separately, by parallelism and by computing stability. By means of sorting the scheme of the approached calculation of residues of functions in poles is constructed and on this basis the scheme of the approached calculation of curvilinear integrals on the closed contour is constructed. Applicability of a method for the analysis of digital filters by means of inverse z-transformation and for the analysis of time function of linear dynamic system and for the analysis of stability of a discrete chain is investigated. 2010 Article Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации/ Я.Е. Ромм, И.А. Тюшнякова// Пробл. програмув. — 2010. — № 2-3. — С. 593-603. — Бібліогр.: 16 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14672 519.6 ru application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладне програмне забезпечення Прикладне програмне забезпечення
spellingShingle	Прикладне програмне забезпечення Прикладне програмне забезпечення Ромм, Я.Е. Тюшнякова, И.А. Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
description	На основе сортировки синтезируются схемы устойчивой локализации и вычисления нулей полиномов и функций с учетом их кратности. Схемы отличаются от известных по построению на основе сортировки, свойством автоматической локализации области всех нулей и каждого нуля в отдельности, параллелизмом, а также вычислительной устойчивостью. С помощью сортировки строится схема приближенного вычисления полюсов комплексных функций с учетом порядка, алгоритмы приближенного вычисления вычетов функций в полюсах и, на этой основе, схема приближенного вычисления криволинейных интегралов по замкнутому контуру. Исследуется применимость метода для анализа цифровых фильтров с помощью обратного z-преобразования, для анализа временной функции линейной динамической системы и для анализа устойчивости дискретной цепи.
format	Article
author	Ромм, Я.Е. Тюшнякова, И.А.
author_facet	Ромм, Я.Е. Тюшнякова, И.А.
author_sort	Ромм, Я.Е.
title	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
title_short	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
title_full	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
title_fullStr	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
title_full_unstemmed	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
title_sort	программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации
publisher	Інститут програмних систем НАН України
publishDate	2010
topic_facet	Прикладне програмне забезпечення
url	https://nasplib.isofts.kiev.ua/handle/123456789/14672
citation_txt	Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации/ Я.Е. Ромм, И.А. Тюшнякова// Пробл. програмув. — 2010. — № 2-3. — С. 593-603. — Бібліогр.: 16 назв. — рос.
work_keys_str_mv	AT rommâe programmnaâidentifikaciânulejiosobennostejfunkcijnaosnovesortirovkispriloženiemkcifrovojfilʹtracii AT tûšnâkovaia programmnaâidentifikaciânulejiosobennostejfunkcijnaosnovesortirovkispriloženiemkcifrovojfilʹtracii AT rommâe programidentificationofzeroesandfeaturesoffunctionsonthebasisofsortingwiththeapplicationtothedigitalfiltration AT tûšnâkovaia programidentificationofzeroesandfeaturesoffunctionsonthebasisofsortingwiththeapplicationtothedigitalfiltration
first_indexed	2025-11-27T00:43:17Z
last_indexed	2025-11-27T00:43:17Z
_version_	1849902184051769344
fulltext	Прикладне програмне забезпечення © Я.Е. Ромм, И.А. Тюшнякова, 2010 ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск 593 УДК 519.6 ПРОГРАММНАЯ ИДЕНТИФИКАЦИЯ НУЛЕЙ И ОСОБЕННОСТЕЙ ФУНКЦИЙ НА ОСНОВЕ СОРТИРОВКИ С ПРИЛОЖЕНИЕМ К ЦИФРОВОЙ ФИЛЬТРАЦИИ Я.Е. Ромм, И.А. Тюшнякова Таганрогский государственный педагогический институт, 347936, Таганрог, ул. Инициативная, 48, тел. (863)(44) 60 1753, факс (863)(44) 60 5397, Romm@list.ru На основе сортировки синтезируются схемы устойчивой локализации и вычисления нулей полиномов и функций с учетом их кратности. Схемы отличаются от известных по построению на основе сортировки, свойством автоматической локализации области всех нулей и каждого нуля в отдельности, параллелизмом, а также вычислительной устойчивостью. С помощью сортировки строится схема приближенного вычисления полюсов комплексных функций с учетом порядка, алгоритмы приближенного вычисления вычетов функций в полюсах и, на этой основе, схема приближенного вычисления криволинейных интегралов по замкнутому контуру. Исследуется применимость метода для анализа цифровых фильтров с помощью обратного z-преобразования, для анализа временной функции линейной динамической системы и для анализа устойчивости дискретной цепи. On the basis of sorting schemes of steady localization and calculation of zeroes of polynomials and functions with consideration of multiplicity are synthesized. Schemes differ from known ones by construction on the basis of sorting, by property of automatic localization of area all zeroes and each zero separately, by parallelism and by computing stability. By means of sorting the scheme of the approached calculation of residues of functions in poles is constructed and on this basis the scheme of the approached calculation of curvilinear integrals on the closed contour is constructed. Applicability of a method for the analysis of digital filters by means of inverse z-transformation and for the analysis of time function of linear dynamic system and for the analysis of stability of a discrete chain is investigated. Введение Алгоритмы сортировки традиционно применяются в методах поиска, для моделирования операторных схем, находят разнообразное применение в системах программирования, операционных системах, системах обработки информации, управления базами данных, используются в базовых элементах компьютеров. Применение сортировки опирается на упорядочение информации и содержит только операции сравнения, исключая накопление погрешности. Отсюда возникает цель применить сортировку для построения схем вычислений, отличающихся снижением роста погрешности и максимальным упорядочением обрабатываемой информации. Традиционный поиск нулей функций не основан на их одновременной локализации, – требуется указать область каждого нуля в отдельности. Кроме того, надежность вычислений зависит от выбора начального приближения и характера функции. По этим причинам не разработаны универсальные компьютерные способы нахождения нулей различных функций, в том числе полиномов с переменными коэффициентами. В данном аспекте ставится вопрос о применении сортировки для локализации и устойчивого вычисления нулей полиномов и функций. Такая задача актуальна сама по себе, кроме того, на основе ее решения конструируется приближенное вычисление полюсов функций. Расчет нулей и полюсов функций – одна из важных задач цифровой обработки сигналов (ЦОС). Значения нулей и особенностей функций требуется знать при выполнении ЦОС в таких областях, как акустика, звуковая локация, радиолокация, сейсмология, связь, системы передачи данных, ядерная техника и др. Области применения ЦОС постоянно расширяются. В работе предложен распараллеливаемый метод вычисления нулей полиномов и функций общего вида, инвариантный относительно области поиска нулей, устойчивость которого обусловлена применением сортировки. Нули автоматически локализуются с учетом их кратности. Приведены оценки временной сложности максимально параллельного варианта метода. Метод модифицирован для приближенного вычисления полюсов, вычетов функций и на этой основе распространяется на вычисление криволинейных интегралов по замкнутому контуру. Представлено применение метода для схем ЦОС. В качестве языка программирования используется объектно-ориентрованный Pascal в среде Borland Delphi. Применение сортировки для нахождения экстремальных элементов последовательности Под экстремальными элементами последовательности понимаются локально минимальные и максималь- ные элементы. Локально минимальный элемент последовательности в точности меньше предыдущего и не больше последующего элементов, локально максимальный элемент строго больше предшествующего, но не меньше последующего элементов. Для нахождения экстремальных элементов последовательности используется адресная сортировка ее элементов. В качестве сортировки возможно использовать одну из двух параллельных внутренних сортировок по возрастанию ключей – подсчетом [1, 2] или слиянием [2, 3], или любую другую с прямой и обратной адресностью, смысл которых сводится к программной реализации взаимно однозначного соответствия между входными и выходными индексами сортируемого массива. Прикладне програмне забезпечення 594 К выходу сортировки подсоединяется условный оператор, локализующий все экстремальные элементы (далее экстремумы) среди этих значений [8, 4]. Оператор локализации минимума имеет вид {Процедура сортировки} k:=1; while k<= nn0 do begin for l:=1 to k-1 do if abs ( e [k]– e [k–l] ) <= eps0 then goto 22; writeln (c[k], e[k]); (1) 22: k := k+1 end; Оператор локализации максимума {Процедура сортировки} k:=1; while k<= nn0 do begin for l := 1 to n – k do if abs(e[k]-e[k+l]) <= eps0 then goto 222; writeln (c[k], e[k]); (2) 222: k:=k+1; end. В программных фрагментах (1), (2) 0nn – число сортируемых элементов, 0eps – константа, обозначающая окрестность локализации экстремумов, равная целому числу номеров влево и вправо от входного номера e[k]. Экстремум, локализуемый данными операторами, является локальным экстремумом среди ближайших значений последовательности, отсчитанных на eps0 влево и вправо от e[k]. В частности, при 10eps локализуется минимальный (максимальный) элемент среди двух ближайших слева и справа. При этом локализация означает конкретное значение как точки (индекса) экстремума e[k], так и экстремального значения ]][[ kea . Оператор локализации находит минимальные (максимальные) элементы последовательности по смыслу своего построения. Работая после сортировки, он для текущего элемента, определяемого индексом, записанным в e[k], находит каждый элемент, в eps0-окрестности которого нет элементов, доставляющих значения элементов входной последовательности, предшествующие (последующие) ]][[ kea в отсортированном массиве. Среди элементов последовательности с равными значениями оператор локализации минимума (максимума) фиксирует элемент, соответствующий первому в порядке нумерации элементу отсортированного массива. Этот факт опирается на устойчивость используемой сортировки. Локализовать экстремальные элементы в рассматриваемом смысле предлагаемым способом можно только при сохранении обратных адресов на выходе сортировки, причем строго в том порядке, в каком располагаются отсортированные элементы. Пример 1. Найти экстремальные элементы последовательности )1,3,0,3,2( , 10eps . Входной массив ][ka –2 3 0 3 1 Адреса входных элементов ][ke 1 2 3 4 5 Отсортированный массив ]][[ kea –2 0 1 3 3 Обратные адреса элементов 1 3 5 2 4 max max min min min -2 3 3 1 0 1 2 3 4 5 Рис. 1. Экстремальные элементы последовательности )1,3,0,3,2( Результаты работы программы, листинг которой приведен в [12], отображены на рис. 1. После сортировки массива )1,3,0,3,2( с помо- щью циклического сравнения входных индексов, при- надлежащих окрестности локализации экстремумов, идентифицируются локализуемые минимальные (–2, 0, 1) и максимальные (3, 3) элементы входной после- довательности. Подход к локализации и вычислению нулей полиномов с учетом кратности на основе сортировки Рассмотрим полином n n zazP 0 )(    , у которого могут быть комплексные нули и коэффициенты ( ,z x y I I – мнимая единица). Для формирования функции ),( yxf , которая подается на вход метода, необходимо выделить действительную и мнимую части рассматриваемого полинома. Для этого осуществляется построение функции двух действительных переменных 2 ),( zPyxf n с применением схемы Горнера. Ее программная реализация [5] для комплексных коэффициентов и операций имеет вид: FUNCTION func (VAR x,y: extended; var bdv, bmv: vect3): extended; VAR i1: 0..n1; p1,p2,pp1,pp2,d1,d2,d3,d4:extended; BEGIN p1:=bdv[n1];p2:=bmv[n1]; FOR i1:=1 TO n1 DO begin um(p1,p2,x,y,d1,d2); pp1:=bdv[n1-i1]; pp2:=bmv[n1-i1]; sum(pp1,pp2,d1,d2,d3,d4); p1:=d3; p2:=d4; end; func:=sqr(p1)+sqr(p2); END; Прикладне програмне забезпечення 595 Вышеиспользуемые процедуры um и sum реализуют соответственно комплексное умножение и сложение двух комплексных чисел. На выходе схемы Горнера получаются действительная и мнимая часть комплексного значения полинома. Функция ),,,( bmvbdvyxfunc , – представляет сумму квадратов действительной и мнимой части этого значения (в математической записи 22 )))((Im()))((Re(),( zPzPyxf nn ). Замечание 1. Для формирования входной функции возможно использовать бином Ньютона для возведения в степень ll Iyxz )( , коэффициенты бинома определяются по треугольнику Паскаля, затем приводятся подобные при действительной и мнимой части. После умножения )(zPn на комплексно- сопряженное значение нахождение нулей )(zPn сводится к нахождению нулей функции двух действительных переменных 2\|)(\|),( zPyxf n . Вводится равномерная прямоугольная сетка, заключающая внутри себя область всех нулей ),,,( bmvbdvyxfunc . Значения функции берутся во всех узлах сетки, образуя двумерный массив, и среди его элементов ищутся все возможные минимумы. Схема поиска нулей полиномов подробно описана в [1, 6] и включает следующие процедуры: построение сетки, процедуру минимизации по строкам в текущем столбце, процедуру сортировки найденных минимумов, локализацию абсциссы и ординаты точки минимума и в итоге спуск к наименьшему значению в окрестности локализованной точки. Следует отметить, что алгоритм локализации всех комплексных нулей полиномов в 0eps -окрестности без применения спуска к локализованному нулю осуществляет их одновременное вычисление с границей абсолютной погрешности 0eps в евклидовой метрике пространства 2R [5]. При этом значение 0eps может быть задано априори. В этом случае рассматриваемый алгоритм, локализуя значение нуля, всегда вычисляет его с априори заданной границей абсолютной погрешности 0eps в метрике евклидова пространства 2R , что существенно отличает данный алгоритм от известных алгоритмов локализации. Замечание 2. Особенности перехода от одного фрагмента области поиска нулей (и экстремумов) к другому рассмотрены в [7], там же предложены инвариантные относительно вида исследуемой функции, размеров области и числа фрагментов ее разбиения способы идентификации нулей (и экстремумов). Распространение схемы вычисления нулей полиномов на случай определения кратности найденных нулей достигается рекуррентным повторением приводимого далее алгоритма [5], для простоты описания приведенного для действительного случая. Алгоритм идентификации кратности нулей полинома: 1. Найти все нули исходного полинома 01 1 1 ...)( axaxaxaxP n n n nn с помощью изложенного метода. Если количество найденных нулей полинома )(xPn меньше чем его степень n , то среди нулей имеются кратные, иначе все нули – не кратные. При наличии кратных нулей перейти к пункту 2, иначе конец алгоритма. 2. Выполнить деление исходного полинома на линейный двучлен 1xx , где 1x – первый из нулей полинома )(xPn . После деления получаем новый полином 01 2 2 1 11 ...)( bxbxbxbxG n n n nn степени 1n , коэффициенты которого вычисляются путем сравнения коэффициентов при равных степенях полиномов )(xPn и 11 )( xxxGn по следующим формулам (схема Горнера): ....,,, 111011121 xbabxbabab nnnnn (3) Перейти к пункту 3. 3. Заново по программе локализации и вычисления нулей на основе сортировки выполнить поиск всех нулей полинома )(1 xGn . Если среди них не оказалось значения 1x , то этот нуль не является кратным. В этом случае все операции, включая схему (3), повторяются для нуля 2x . Если же среди найденных нулей оказалось значение 1x , то перейти к пункту 4. 4. Выполнить деление по схеме (3) полинома )(1 xGn на линейный двучлен 1xx с тем, чтобы выполнить проверку на наличие в нем нуля 1x . Процесс продолжается до исчерпания кратности нуля 1x . Перейти к пункту 5. 5. Выполняется аналогичная проверка на кратность каждого из оставшихся нулей nxxx ,...,, 32 исходного полинома )(xPn . 6. Конец алгоритма. Замечание 3. Для нахождения нулей трансцендентных функций с учетом кратности необходимо использовать метод, подробно описанный в [3, 4]. В основе его идеи лежит деление функции, нули которой уже найдены, на циклически подсчитываемое выражение ))()((: 22 ykoryxkorxpppp , где число шагов цикла равно текущему счетчику кратности, а ykorixkor – текущий корень. В случае если 0pp , деление производится на другое, отличное от близкого к нулю, циклически подсчитываемое выражение epspppppp : , где число шагов цикла совпадает с текущим значением порядка найденных нулей, eps – наперед заданная погрешность вычислений. Алгоритм и программная реализация данного метода приведены в [8]. Прикладне програмне забезпечення 596 Изложенное использование сортировки позволяет обойти математическую трудность решения классической задачи вычисления нулей, связанную с отысканием областей, в которых располагаются единственные нули; с поиском первого приближения к нулю; с необходимостью в дифференцировании полинома, кратность нулей которого требуется вычислить. При решении различных практических задач часто отсутствует априорная информация о границах области, охватывающей нули полинома. Поэтому возникает задача программной локализации области нахождения всех нулей полинома с их одновременным вычислением. Замечание 4. Возможно распространение изложенной схемы нахождения нулей на случай области на комплексной плоскости, границы которой не являются фиксированными. Переход к области с произвольно заданными границами, которые, в частности, могут не примыкать к области всех нулей полинома, напротив, они могут быть отделены от этой области произвольно большим расстоянием, основывается на следующих соображениях. Вне области нулей полинома )(zPn , квадрат его модуля, т.е. функция ),( yxf , фактически оказывается монотонной по каждой переменной в отдельности при фиксировании другой переменной в качестве локализованного приближения. На основе достигаемой таким способом монотонности, при фиксировании одной локализованной координаты, из любых двух значений модуля полинома, взятых слева (справа), сверху (снизу) от области всех нулей полинома, меньшее значение всегда ближе к этой области. Можно взять произвольно большой квадрат и сужать его до момента обнаружения хотя бы одного приближения нулевого минимума. При этом локализацию и вычисление каждого минимума модуля полинома можно осуществлять на основе вышеописанной схемы для ограниченной области комплексной плоскости. Работоспособность схемы можно гарантировать для полиномов произвольной степени с комплексными коэффициентами, имеющих как кратные, так и некратные нули, включая случай их плохой отделенности. Значение полинома не должно выходить из диапазона представления чисел в конкретном языке программирования. Длительность работы программы, реализующей алгоритм нахождения комплексных нулей полиномов с учетом кратности, компенсируется параллелизмом изложенного метода. На основе взаимной независимости рассматриваемого алгоритма по всем фрагментам в произвольно выбранном прямоугольном разбиении области произведена оценка параллельного по данным фрагментам выполнения предложенного алгоритма [8]. Для оценки временной сложности (времени выполнения) параллельного алгоритма использована модель неветвящейся параллельной программы без учета обмена. В результате, полное время параллельного вычисления всех нулей полинома zPn оценивается из соотношения: )()log() 0 (log)( 2 npOnO eps eps ORT , число процессоров )( 4 )0011)(0011( 5 2 npO n hh yyxx OR . Здесь [x00,x11] [y00,y11] – область поиска нулей; hh – длина текущего промежутка, на котором формируется равномерная сетка с шагом h; n – число узлов равномерной сетки; eps0 – радиус окрестности локализации нуля, включающий не больше половины числа узлов, отсчитываемых вдоль оси ОХ между ближайшими друг к другу нулями полинома; eps – наперед заданная граница абсолютной погрешности вычислений; np – степень полинома; – коэффициент пропорции, в которой сокращается диаметр окрестности текущего приближения нуля при спуске. Данные оценки соответствуют максимально параллельному варианту метода, показывая потенциал быстродействия рассмотренной схемы. При распараллеливании временная сложность схемы не будет критичной в сравнительно больших областях поиска нулей, включая случай их плохой отделенности. Локализация и приближенное вычисление нулей в окрестности единичной окружности На основе описанной схемы возможно производить поиск нулей в произвольной области комплексной плоскости, границами которой является не только некоторый прямоугольник или квадрат, но и произвольная кривая. Рассмотрим в качестве области поиска окрестность окружности единичного радиуса. Для удобства передвижения по контуру в данном случае целесообразно перейти к полярной системе координат sin cos y x , где 1 . Модификация схемы заключается в следующем. После определения точки, находящейся на контуре, она окружается квадратом со стороной epsilon2 , где epsilon – произвольно заданное значение, определяющее близость границы области поиска по отношению к контуру. В построенном квадрате поиск нулей осуществляется по вышеописанной схеме без каких-либо изменений, причем равномерная сетка строится слева направо сверху вниз, начиная с нижней левой вершины квадрата. После этого выполняется переход к следующей точке контура таким образом, чтобы полученные квадраты пересеклись. Данный процесс осуществляется до тех пор, пока весь исходный контур не будет покрыт цепочкой квадратов. Для случая окружности в качестве первоначальной точки контура выбирается точка с нулевым аргументом phi 0 . Она окружается квадратом x0:=cos(phi)-epsilon; y0:=sin(phi)-epsilon; сторона которого epsilon2 , где epsilon:=eps020, причем основные константы сохраняют вышеописанный смысл: eps0 – константа, не превышающая половины числа узлов, отсчитываемых вдоль оси ОХ между ближайшими друг к Прикладне програмне забезпечення 597 другу нулями полинома; n=1024 – число узлов равномерной сетки; h:=2epsilon/n; – шаг равномерной сетки. После нахождения нулей в текущем квадрате переход к следующему осуществляется с помощью операторов: phi:=phi+Pi/8 ; if phi<2Pi then begin x0:=cos(phi)-epsilon; y0:=sin(phi)-epsilon; goto 14;…. Описанным образом удается отыскать все значения нулей, находящиеся в заданной области, включающей единичную окружность. Пример 2. В окрестности единичной окружности найти все нули полинома, квадрат модуля которого задается выражением: 5 2 1 ( ) ( ( 0[ ]) ( 01[ ]))n i \| P z \| sqr x b i +sqr y b i . В 0[ ]b i и 01[ ]b i хранятся значения действительной и мнимой частей i-го нуля многочлена, заданные в разделе описания констант (b0: vek = (1 , –0.99, 0.5 , –0.3,1); b01: vek = (0.01, 0.01, 0.85 , –0.95,1);). Рис. 2. Иллюстрация схемы поиска нулей в окрестности заданной окружности Результаты работы программы приведены в табл. 1. Рис. 2 иллюстрирует программный поиск нулей в окрестности окружности по описанной схеме. Найденные нули отображены темными маркерами. Очевидно, что один из нулей полинома – (1, 1) не удовлетворяет заданной области поиска и поэтому не был найден. Таблица 1. Результаты работы программы вычисления нулей полинома в окрестности единичной окружности Действительная часть нуля Мнимая часть нуля Значение функции 1 0,5 –0,99 –0,3 0,01 0,85 0,01 –0,95 0.00E+0000 0.00E+0000 0.00E+0000 0.00E+0000 Описанный метод позволяет искать нули функций вблизи практически любых кривых на плоскости, если дополнительно использовать известные алгоритмы выделения контура (отслеживающие, сканирующие). Вычисление полюсов комплексной функции с учетом порядка на основе сортировки Изложенный метод вычисления нулей ниже модифицируется для автоматической программной идентификации полюсов комплексных функций с учетом их порядка. Полюсы исходной комплексной функции ),(),(),( yxpIyxgyxf , квадрат модуля обратной к которой возможно представить в виде ),(),(),(1 222 yxvyxuyxf , определяются как нули квадрата модуля обратной функции. В случае невозможности такого представления, на вход метода подается непосредственно функция )(1 22 pg , обратная к квадрату модуля, однако необходимо ослабить условия сужения окрестности при спуске [8]. Тем самым осуществляется перенос схемы нахождения нулей, изложенной выше, на вычисление полюсов комплексной функции с учетом их порядка. Пример 3. В прямоугольнике ]5.1,5.1[]5,0,5.0[ найти полюсы функции 22 )1( )( z z zf и определить их порядок. Результаты работы программы [8] приведены в табл. 2. Таблица 2. Результаты работы программы вычисления полюсов функции Действительная часть полюса Мнимая часть полюса Порядок полюса Значение обратной функции –6.72E-0011 –6.72E-0011 –1.00E+0000 1.00E+0000 2 2 0.00E+0000 0.00E+0000 Схема распространяется на вычисление вычетов комплексных функций, имеющих в качестве особенностей полюсы, с последующим вычислением криволинейных интегралов по замкнутому контуру. Прикладне програмне забезпечення 598 Вычет 1 0 )( Czfres z исходной функции )(zf в полюсе 0z определяется при последовательном вычислении всех отрицательных коэффициентов ряда Лорана 0 0lim ( )( ) ,n n z z C f z z z 0 0 1 0 ( )( ) ( lim ,...) n n n z z f z z z C C z z априори заданной границей абсолютной погрешности [8]. Эти коэффициенты вычисляются при повторном применении схемы вычисления нулей в месте спуска к наименьшему значению в окрестности локализованной точки по ходу циклического приближения значения z к заново вычисляемому значению 0z при существенном сужении области поиска вокруг найденного значения полюса. За количественную меру сужения окрестности области поиска отвечает специально введенный коэффициент )10,10( 9424g , определяющий зависимость между константой eps0 и граничными значениями области поиска: eps0 = zzg; x00 = x0–eps0/g; x11 = x0+eps0/g; y00= y0–eps0/g; y11= y0+eps0/g; 000 * yixz – полюс, в котором вычисляется вычет. Значение множителя zz константы eps0 подобрано эвристически в ходе численного эксперимента, оно варьируется в зависимости от порядка найденных полюсов, однако выбранные значения zz [8] остаются постоянными для различных функций, имеющих одинаковый порядок полюсов. Коэффициент g принимает произвольные значения из указанного интервала, остальные же константы программы [8] находятся в прямой или обратной пропорции к g и eps0. На основе сортировки, с использованием метода нахождения вычетов функций в полюсах возможно вычисление криволинейных интегралов по замкнутому контуру. В силу основной теорема о вычетах – Dzzfresidzzf k n k zD k ),(2)( 1 , где D – односвязная область в комплексной плоскости. Определив вычеты исходной функции, непосредственно можно перейти к вычислению интеграла по замкнутому контуру. Этот переход возможен в случае полюсов, находящихся внутри области D, поэтому необходимо программное представление этой области. Представляется возможным также нахождение всех полюсов исходной функции и последующий выбор тех из них, которые входят в область, ограниченную криволинейным контуром. Схемы анализа цифровых фильтров с использованием сортировки При моделировании линейных динамических систем, а также при фильтрации или обработке сигналов проектируются и применяются цифровые фильтры. Термин цифровой фильтр [9] относится к процессу вычислений по некоторому алгоритму, с помощью которого дискретный сигнал преобразуется в последовательность чисел, выражающих выходной сигнал. Основным математическим аппаратом для анализа проектирования цифровых фильтров, является z-преобразование [9], которое отображает дискретизированные сигналы из временной области в их алгебраическое представление в области z, что значительно упрощает анализ систем с дискретизированными сигналами. Двустороннее z-преобразование дискретной функции )(nTf определяется как n nznTfzF )()( для всех z, для которых ряд сходится. Одностороннее z-преобразование дискретной функции )(nTf представляется в виде 0 1 )()( n nznTfzF . По отношению к )(zF функция )(nTf называется обратным z-преобразованием функции )(zF , )(nTf и используется для получения соответственной временной функции и определяет коэффициенты дискретного сигнала, отвечающего этой функции. В силу сходимости ряда функция )(nTf однозначно определяется соотношением dzzzF i nTf n 1)( 2 1 )( , где – контур, охватывающий все полюсы функции )(zF [9]. Поэтому k i z zFresnTf k1 0 )]([)( , где 1 0 )()( nzzFzF . (4) На этой основе описанный метод нахождения вычетов с помощью сортировки распространяется на программное вычисление обратного z-преобразования. Предложенный подход иллюстрирует следующий пример. Пример 4 [1]. Задано z-преобразование вида z z zX 1 )( . Найти коэффициенты nx дискретного сигнала, отвечающего этой функции. Прикладне програмне забезпечення 599 Заметим, что функция )(zX аналитична на всей комплексной плоскости за исключением точки 0z (полюс )(zX ), следовательно, она может описывать z-преобразование. Для нахождения коэффициентов дискретного сигнала необходимо вычислить обратное z-преобразование )(nTf из (4). Поскольку речь идет об одностороннем z-преобразовании, то ...,2,1,0n . В качестве области поиска полюсов функций 1 0 )()( nzzFzF выберем квадрат ]1,1[]1,1[ . Следует отметить, что для поиска полюсов можно пользоваться программой [8], модифицированной для области на комплексной плоскости с границами, которые не являются фиксированными. Результаты работы соответствующих программ представлены в табл. 3. Мнимая часть полученных вычетов достаточно мала (порядка 1610 ), приближенно ее можно считать нулем (если полюса функций вычисляются с точностью 1510 , можно пользоваться программой нахождения вычетов для действительного случая). Каждая из функций 1 0 )()( nzzFzF (где ...,2,1,0n ) имеет не более одного полюса. Таблица 3. Результаты работы программы вычисления обратного z-преобразования функции z z zX 1 )( Вид правой части входной функции Полюс Порядок полюса Вычет в полюсе Приближенное значение обратного z-преобразования 0 42224 1222 yyxx yxx 8.52E-0016+ +i8.52E-0016 2 1.00E-0000+ +i 8.78E-0016 1 1 22 1222 yx yxx 8.52E-0016+ +i8.79E-0016 1 9.99E-0001+ +i 8.78E-0016 1 2 1222 yxx – – 0 0 3 24222222324 yyxyxyxxx – – 0 0 В результате коэффициенты дискретного сигнала имеют вид ...,0,0,1,1 . Предложенный метод также применим для анализа временных функций в зависимости от расположения нулей и полюсов на комплексной плоскости. Полюсы внутри круга единичного радиуса, имеющие 1z , соответствуют затухающим сигналам и наоборот. Полюс на положительной действительной оси соответствует дискретизированной действительной экспоненте. Полюс на отрицательной действительной оси соответствует дискретизированному гармоническому сигналу с двумя отсчетами на период. Сигнал с четырьмя интервалами дискретизации на период соответствует полюсу на мнимой оси. Для гармонических сигналов моменты дискретизации связаны с нулями z-преобразования. Таким образом, программная идентификация нулей и полюсов z-преобразования позволяет сделать вывод о характере временной функции линейной динамической системы. Метод вычисления полюсов функции на основе сортировки применим к анализу устойчивости дискретной цепи, которая считается неустойчивой, если ограниченное по амплитуде входное воздействие вызывает на ее выходе бесконечно нарастающий отклик. Наоборот, дискретная цепь устойчива, когда отклик на ограниченное воздействие также ограничен [9]. Передаточной или системной функцией называют z-преобразование импульсной характеристики. Передаточная функция характеризует поведение системы в зависимости от частоты синусоидального воздействия. Известно, что в устойчивой аналоговой цепи полюсы передаточной функции располагаются в левой полуплоскости переменной p. При переходе от аналоговой цепи к дискретной и замене преобразования Лапласа z-преобразованием точки левой полуплоскости p-плоскости переходят в точки, лежащие внутри единичной окружности z-плоскости. Таким образом, полюсы передаточной функции устойчивой дискретной цепи располагаются внутри единичной окружности z-плоскости. На основе метода с применением сортировки всегда оказывается возможным по виду передаточной функции дискретной цепи определить устойчива или нет данная дискретная цепь. Пример 5. Цифровой фильтр Баттерворта нижних частот 3-го порядка описывается передаточной функцией 1 1 2 3 0.1317 ( ) 1 1.785 1.202 0.2853 H z z z z . На вход метода подается полином, заданный своими коэффициентами ( 0.2853,1.202, 1.785,1). Результаты работы программы приведены в табл. 4. Прикладне програмне забезпечення 600 Таблица 4. Результаты работы программы вычисления полюсов функции )(1 zH Действительная часть полюса Мнимая часть полюса Порядок полюса Значение обратной функции 5.35E–0001 6.24E–0001 6.24E–0001 9.57E–0445 –3.77E–0001 3.77E–0001 1 1 1 2.08Е–0890 1.78Е–0022 1.82Е–0022 Расположение полюсов в плоскости z показано на рис. 3, а. Здесь показана структурная схема такого фильтра (рис. 3, б). Цепь устойчива, поскольку все полюсы передаточной функции лежат внутри единичной окружности. 1 z z z 1 2 3 z-плоскость а -1.785 1.202 -0.2853 Т Т Т 0.1317+ X[n] Y[n] б Рис. 3. Расположение полюсов передаточной функции, описывающей фильтр Баттерворта Замечание 5. Для того чтобы обойти некоторые алгебраические преобразования, связанные с приведением к общему знаменателю компонент передаточной функции, возможно использовать следующее положение об устойчивости цифрового фильтра. Его называют устойчивым, когда полюсы передаточной функции расположены вне окружности 1 1z [9]. Сравнение метода вычисления нулей и полюсов функций на основе сортировки с существующими методами Известные методы вычисления экстремумов и нулей функций [10–13] в своем большинстве базируются на градиентных схемах и не включают автоматическую идентификацию области каждого нуля (экстремума). Предложенный метод отличается от известных методов построением на основе сортировки, включает автоматическую программную идентификацию области каждого нуля исходной функции и позволяет вычислять нули с учетом их кратности. На его основе возможно нахождение полюсов функций с учетом их порядка, вычетов функций в полюсах и, как следствие, криволинейных интегралов по замкнутому контуру. Метод практически применим для анализа цифровых фильтров. Следует отметить, что предложенный метод использования сортировки с последующим условием локализации экстремумов затруднительно заменить другим приемом. В ходе численного эксперимента нули функций вычислялись на основе непосредственного выделения минимальных значений путем сравнения текущего значения с соседними. В результате применения данной схемы обнаружилось, что она неустойчива в случае поиска нулей сложных функций комплексной переменной, что иллюстрирует следующий пример. Пример 6. Вычислить нули функции 2 1 1 1 1 : cos sin 1 0 sin 2 sin 1 cos 1.2 sin F p p eps p eps p eps p eps p p , в квадрате ]11,00[]11,00[ yyxx , где eps=1.1e–444; eps0=0.000000000000000000291e–286; x00=–0.0000000000000000000891e–287; x11=0.000000000000000000841e–287; y00=–0.0000000000000000000891e–287; y11=0.000000000000000000841e-287; p конструируется в виде – 22 ][1][ ibyibxpp , а в массивы ][ib и ][1 ib записываются значения, заданные в разделе описания констант: Прикладне програмне забезпечення 601 b: vect3 =(0.0000000000000000001011e–287, 0.0000000000000000002031e–287, 0.0000000000000000003021e–287, 0.0000000000000000004011e–287, 0.0000000000000000005051e–287, 0.0000000000000000006021e–287, 0.0000000000000000007011e–287, 0.0000000000000000008051e–287); b1: vect3 =(0.0000000000000000001071e–287, 0.0000000000000000002031e–287, 0.0000000000000000003091e–287, 0.0000000000000000004041e–287, 0.0000000000000000005031e–287, 0.0000000000000000006031e–287, 0.0000000000000000007021e–287,0.0000000000000000008061e–287); Табл. 5 с очевидностью показывает неустойчивость схемы вычисления нулей без использования сортировки. Таблица 5. Результаты работы программ определения комплексных нулей функции ),( yxF с использованием сортировки и без ее использования Схема на основе сортировки Схема без использования сортировки и условия локализации Действительная часть нуля Мнимая часть нуля Значение функции Действительная часть нуля Мнимая часть нуля Значение функции 2.03E-0306 2.03E-0306 0.00E+0000 1.01E-0306 1.07E-0306 0.00E+0000 5.05E-0306 5.03E-0306 0.00E+0000 –– –– –– 4.01E-0306 4.04E-0306 0.00E+0000 –– –– –– 3.02E-0306 3.09E-0306 0.00E+0000 –– –– –– 6.02E-0306 6.03E-0306 0.00E+0000 –– –– –– 7.01E-0306 7.02E-0306 0.00E+0000 –– –– –– 8.05E-0306 8.06E-0306 0.00E+0000 –– –– –– 1.01E-0306 1.07E-0306 0.00E+0000 –– –– –– Проведем сравнение предложенной схемы с математическими методами. Поведение нулей полиномов и функций исследуется в алгебре и математическом анализе [14, 15]. Схемы численного решения задачи опираются на алгебраические преобразования [10, 15] и методы последовательных приближений [13, 16]. В своем большинстве известные методы ориентированы на нахождение единственного нуля, расположенного внутри некоторого интервала. Помимо того, присутствует необходимость поиска первого приближения, после чего возможно использование расчетных формул конкретного метода. Известные подходы включают больше средств теоретической математики, чем специфики компьютерных вычислений. В этом можно видеть одну из причин, по которой компьютерная реализация методов нахождения нулей полиномов и функций общего вида в существенных аспектах не гарантирует завершенности решения. С другой стороны, при наличии возможности программной реализации некоторых схем, вообще говоря, не исключается проблема локализации, накопления погрешности и вычислительной неустойчивости [10, 16]. В этом контексте выделяются классические методы Штурма и Бюдана – Фурье [15], однако они относятся строго к случаю локализации действительных нулей полинома, не распространяясь на случай комплексных нулей и нулей трансцендентных функций. В отличие от известных математических методов предложенный метод на основе сортировки дает программную идентификацию области всех нулей и каждого нуля в отдельности (с одновременным вычислением с точностью до eps0), фактически не используя при этом ограничения на вид входной функции. Требуется только, чтобы функция была непрерывной и чтобы дискретизация не приводила к существенным изменениям рельефа функции. Для сравнения получим результаты вычисления нулей функций по описанной схеме на основе сортировки и в системах компьютерной математики Mathcad и Maple. Пример 7. Найти нули функции pp pp ppF sin2.1 1 cos 1 102 1 sin1 102 1 sincos: 2323 , где )0000011.1)(000001.1( xxp . Результаты вычислений приведены в табл. 6, которые показывают, что в Mathcad нули данной трансцендентной функции не найдены. В Maple приближенный результат удается получить с помощью функции fsolve , которая используется для численного решения уравнений в тех случаях, когда трансцен- дентные уравнения не имеют аналитических решений. В результате найдено достаточно грубое приближение к нулям. Использование сортировки в этом случае дает точный результат с автоматической идентификацией всех нулей исходной функции. Прикладне програмне забезпечення 602 Таблица 6. Сравнительная таблица вычисления нулей трансцендентной функции на основе сортировки, в Mathcad и в Maple Метод на основе сортировки Mathcad Maple Нули функции Значение функции Нули функции Значение функции Нули функции Значение функции 1.000001E+0000 1.44E–0903 –– –– 1.308077894 1.96Е–0009 1.0000011E+0000 1.44E–0903 –– –– –– –– Пример 8. Найти нули функции двух переменных 333),( 22 yyxxyxf Таблица 7. Сравнительная таблица вычисления нулей функции двух переменных на основе сортировки, в Mathcad и в Maple Метод на основе cортировки Mathcad Maple Нули функции Значение функции Нули функции Значение функции Нули функции Значение функции x=8.88E-0001 y=-2.56E+0000 0.00Е+0000 x=1.65950126458145 y=-0.285685647670115 0.32E-0009 –– –– x=4.46E-0001 y=-2.12E+0000 0.00Е+0000 x=1.26577088735596 y=-2.70213839319366 0.63E-0008 –– –– ……………… …………… ……………… …………… –– –– x=4.46E-0001 y=-8.74E-0001 0.00Е+0000 x=0.936172287252808 y=-0.412756580408887 0.56E-0008 –– –– x=1.49E+0000 y=-2.72E+0000 0.00Е+0000 x=0.304414215462631 y=-1.23434113712145 0.38E-0009 –– –– Результаты вычислений представлены в табл. 7. Исходная функция имеет бесконечное множество нулей, поэтому Maple не дал результатов, строка вывода отображается в виде: 0, {[FAIL, 0]}. Это означает, что минимум модуля исходной функции равен нулю, а координаты точек минимума не известны. Столбец решений данного примера в Mathcad получен при различных начальных значениях переменных yx, . Однако результаты решения существенно зависят от выбора начальных значений переменных и имеют высокую погрешность вычислений. На основе сравнения можно сделать следующий вывод. Предложенный метод дает программную идентификацию области каждого нуля функции одной и двух переменных, включая случай нулей комплексных полиномов и трансцендентных функций, при этом достигается точность вычислений в максимальном формате представления данных. Такая идентификация инвариантна относительно вида функции, ее области определения, области расположения всех и каждого нуля в отдельности. Существующие схемы не обладают инвариантной идентификацией области нулей или требуют начального приближения, соответственно они могут игнорировать наличие нулей в некоторых сложных случаях, либо не достигают в этих случаях аналогичной точности вычислений. Существующие схемы, как правило, неустойчивы при поиске нулей трансцендентных функций. Помимо устойчивости предложенный метод обладает параллелизмом и свойством совмещения локализации одновременно всех нулей с их вычислением с априори заданной границей абсолютной погрешности. Заключение В работе описан распараллеливаемый метод вычисления нулей полиномов и функций общего вида с учетом кратности, инвариантный относительно области поиска нулей, устойчивость которого обусловлена применением сортировки. Метод модифицирован для приближенного вычисления полюсов и вычетов функций и на этой основе распространяется на вычисление криволинейных интегралов по замкнутому контуру. Разработанная схема приближенного вычисления полюсов комплексных функций с учетом порядка использует обработку индексов отсортированных элементов, в результате не вносится вычислительная погрешность, метод достигает устойчивости, фактически не включает ограничений на вид входной функции, отличаясь этим от известных аналогов. Построенные на данной основе алгоритмы приближенного вычисления вычетов функций в полюсах отличаются от известных методов вычислительной устойчивостью и параллелизмом. Представлено применение предложенных методов для анализа цифровых фильтров с помощью обратного z-преобразования, для анализа временной функции линейной динамической системы и для анализа устойчивости дискретной цепи. Прикладне програмне забезпечення 603 1. Ромм Я. Е., Заика И.В., Тюшнякова И.А. Идентификация экстремумов функций на основе сортировки с приложением к вычислительным схемам алгебры, анализа и распознаванию изображений. // Проблеми програмування: Матерiали 5-й мiжнар. науково-практичноi конф. з програмування УкрПРОГ’2006. 23–25 травня 2006 р. Україна, Київ. – 2006. – № 2–3. – С. 708 – 717. 2. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ, Киев. – 2007. – № 1. – С. 165 – 182. 3. Ромм Я.Е., Гуревич М.Ю., Белоконова С.С., Соловьѐва И.А. Вычисление нулей и полюсов функций на основе устойчивой адресной сортировки с приложением к поиску и распознаванию. // Проблеми програмування. – 2004. – № 2 – 3. – С. 462–472. 4. Ромм Я.Е., Тюшнякова И.А. Применение сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений. – Таганрог: Изд-во Таганрог. гос. пед. ин-та, 2009. – 155 c. 5. Веселая А.А. Вычисление нулей и экстремумов функций при вариации параметров на основе сортировки с приложением к моделированию устойчивости систем линейных дифференциальных уравнений: Автореф. дис. ... канд. техн. наук. – Изд-во ТТИ ЮФУ, Таганрог, 2009. – 18 с. 6. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. – Киев. – 2007. – № 2. – С. 161 – 174. 7. Заика И.В. Разработка и исследование схем оптимизации на основе алгоритмов сортировки с приложением к идентификации экстремумов решений дифференциальных уравнений: Автореф. дис. ... канд. техн. наук. Изд-во ТРТУ, Таганрог, 2007. – 19 с. 8. Тюшнякова И.А. Разработка и исследование схем применения сортировки для поиска нулей и особенностей функций с приложением к идентификации плоских изображений:Диссертация канд. техн. наук. – Таганрог: ТРТУ. – 2006. – 196 с. 9. Баскаков С.И. Радиотехнические цепи и сигналы. – М.: Высшая школа, 2003. – 462 с. 10. Березин И.С., Жидков Н.П. Методы вычислений. – Т. 2. – М.: Физматгиз, 1962. – 640 с. 11. Киреев В.И., Пантелеев А.В. Численные методы в примерах и задачах. – М.: Высшая школа, 2004. – 480 с. 12. Kalinina E.A., Uteshev A.Yu. Determination of the Number of Roots of a Polynomial Lying in a Given Algebraic Domain // Linear Algebra and its Applications. – 1993. – V. 185. – P. 61 81. 13. Semerdziev Khr. Iteration methods for simultaneous finding all roots of generalized polynomial equations // Math. Balkan. – 1994. – 8, № 4. – P. 311 – 335. 14. Маркушевич А.И. Краткий курс теории аналитических функций. – М.: Наука, 1978. – 416 c. 15. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. – СПб: Лань, 2002. – 736 с. 16. Форсайт Д.Э., Малькольм М., Моулер К. Машинные методы математических вычислений. – М.: Мир, 1980. – 279 с.

Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации

Institution

Ähnliche Einträge