Наилучшие дробно-рациональные приближения на системе отрезков тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

' : Ч А ^ 1

: ' * ' V » .

САИКТ-ПЕТВРБУРГСКИЙ ГОСУЛАРС'ГВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи ГХАШИМ Мохамад

УДК 519.651+519.853

НАИЛУЧШИЕ ДРОБНО-РАЦИОНАЛЬНЫЕ ПРИБЛИЖЕНИЯ НА СИСТЕМЕ ОТРЕЗКОВ

Специальность: 01.01.07 - вычислительная математика 01.01.11 - системный анализ и автоматическое управление

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

САНКТ-ПЕТЕРБУРГ 1992 г.

Работа выполнена на кафедре исследования операций математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель-доктор физико-математических наук, проф. В.Н.МАЛОЗЕМОВ

Официальные оппоненты: доктор физико-математических наук, профессор И.К.ДАУГАВЕ'] кандидат физико-математических наук, доц. А.Б.ПЕПНЫЙ

Ведущая организация-Институт математики АН Беларуси

Защита состоится "/О » /С-7 1992 г. в ' часов

на заседании специализированного совета Д 063.57.30 по зашит диссертаций на соискание ученой степени доктора филико-м.тп матических наук в Санкт-Петербургском университете по адрес.' 198904, г.Санкт-Петербург, Старый Петергоф, Библиотечная плс щадь, дом 2, иатематико-механический факультет.

С диссертацией можно ознакомиться в библиотеке Сапкт-Пстс! бургского государственного университета по адресу: 199034, г.Санкт-Петербург, Университетская набережная, лом 7/9.

Автореферат разослан 1992 г.

Ученый секретарь специализированного совета Д 003.57.30, лоцент СУШКОВ Ю.А.

! С-.-: I

I

. 0В1ДЛЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исторически первыми задачами наилуч-iaero дробно-рационального приближения на системе отрезков били Третья и Четвертая задачи Золотарева (1877 г.). Напомним их формулировки. Обозначим семейство дробно-рациональпых функций, в числителе и знаменателе которых стоят алгебраические полиномы стеиени не выше >i и т соответственно.

ТРЕТЬЯ ЗАДАЧА ЗОЛОТАРЕВА. Пусть г € (0,1) - фиксированное число. Решить экстремальную задачу

max |Я(*)| -+ inf, «И.»]1

где инфимум бере гся по всем дробям Я из fiJ, удовлетворяющим ограничению

|Я(«)| > 1 при|/|>1/т.

ЧЕТВЕРТАЯ ЗАДАЧА ЗОЛОТАРЕВА. Пусть ае € (0,1) -фиксированное число и D = [—1/зе, —1] и[1,1/ае]. Решить экстремальную задачу t

max |#(t) - signfi)l ini •

teu w ° v ' H0 i

К.И.Золотарев получил решеция этих задач в явном виде с помощью элллиптических функций. Точнее, он указал 16 решений Третьей задачи, легко конструируемых из основного решения, и 4 решения Четвертой задачи, не интересуясь, какие из решений по существу различаются между собой.

Н.И.Ахиезер отметил, что Четвертая задача Золотарева экви-налонтпа следующей задаче Чебышева (1889 г.).

ЗАДАЧА ЧЕВЫШЕВА. Найти приближение функции y/lft nil отрезке [l,ft], гдн h > 1, дробями вида

ßi Ö»

с;, +1 . ' с„ +1

V наименьшей относительной погрешностью.

Эта задача интересовала П.Л.Чобыпгева'в связи с приближением шпчиодениемг интегрален вида

(Ь

j U/s/Vdt.

а

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

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

К началу 1970-х годов утвердился более широкий взгляд па задачи чебышевского приближения как на задачи негладкой оптимизации. Успехи общей теории экстремальных задач позволили значительно продвинуться в изучении задач нелинейного чебышевского приближения, в частности, в разработке численных методов их решения. Расширился и круг приложений. Кроме обычных задач обработки экспериментальных данных, стали решаться задачи параметрического синтеза, возникающие но многих технических дисциплинах (радиоэлектронике, механике и т.д.).

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

Цель работы.

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

В.М.Белых и В.Н.Малоземовым, провести детальный качественный анализ решений Третьей и Чётвертой задач Золотарева. В частности, выяснить вонрос о количестве различных решений этих задач.

2. Провести детальный качественный анализ одной фильтровой задачи.

3. Исследовать эффективность численных методов решения задач наилучшего дробно-рационального приближения на системе

отрезков и задач сиптеза трехполосных фильтров.

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

Научная новизна. В диссертации получены следующие результаты.

1. Проведен детальный качественный анализ решений Третьей и Четвертой задач Золотарева. В частности, установлено, что обе задачи имеют т о ч н о но два решения.

2. Проведен детальный качественный анализ одной фильтровой задачи на основе установленного факта ее эквивалентности Четвертой задаче Золотарева. Доказано, что фильтровая задача имеет точно два решения. Найден нестандартный инвариант этой задачи.

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

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

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

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

и нелинейных функциональных уравнений.

Аппробация работы и публикации. По результатам диссертации сделаны доклады на семинаре кафедры исследонанкя операций и семинаре по нелинейным экстремальным задачам ари С.-Петербургском университете, на конференции цо теории дробно-рациональных приближений (Махачкала, сентябрь 1991 г.) и па конференции по конструктивной теории функций, иоснященноИ 70-летию проф. В.С.Виденского (С.-Петербург, май 1992 г.).

Основные результаты опубликованы в 4 работах.

Структура и объем работы. .Диссертация состоит из введения, двук глав (14 параграфов), списка литературы и приложения. Объем диссертации - 140 стр. основного текста и 17 стр. приложения. Список литературы насчитывает 57 наименований. В диссертации имеется 23 рис. и 10 табл.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

Глава I (§1.1-1.10) посвящена вопросам теории. Рассматривается система попарно не пересекающихся отрезков £> = и'= ,[<:;,а1;]. С этой системой связывается знаковый вектор сг = (сг;, <гг,..., сг,). Его компоненты равны +1 или —1. Знаковый класс ¿/(сг) образуют те дроби из семейства Я*, знаменатель которых отличен от нуля и имеет данный знак ст,- на отрезке [с,Д] при всех »61:5.

В §1.1-1.5 подробно изложены общие результаты о наилучшем дробво-радиональном приближении на знаковом классе (существование решения, его альтернансная характеризадия, единственность и сильная единственность). В основном мы следуем работам В.М.Белых и В.Н.Малоземова. Усовершенствования внесены в формулировку и доказательство осповпой леммы и н интерпретацию знакового правила из критерия оптимальности. Теорема о сильной единственности па знаковом классе является новой.

В §1.6,1.7 на основе общих результатом проведен детальный качественный апализ решений Четвертой задачи Золотарев:). Установлено , что Четвертая задача Золотарева имеет точки

в

дна решения - непрерывное па и разрывное при < = 0. Для непрерывного решения //„(() доказаны следующие тождества

#„(*) = Па при и = 2к,

где >рл - величина лаилучшего приближения. На базе этих тождеств получена полезная информация о расположении точек алмернанса дроби наилучшего приближения.

В §1.8 развивается техника дробио-линейньи,преобразований днух отрезкой, необходимая для доказательства эквивалентности задач наилучшего дробно-рационального приближения. Понятие эквивалентное™ было введено Н.И.Ахиезером.

В §1.9 доказана эквивалентность Третьей и Четвертой задач Золотарева при я> = (результат Н.И.Ахиезера).

11а этой основе проведен качественный анализ решений Третьей задачи Золотарева. Установлено, что эта задача имеет точно два решения, различающиеся лишь знаком. Одпо из решений называется дробью Золотарева. Для дроби Золотарева Za(t) получено тождество

где А„ - величина наименьшего уклонения от нуля. Из этого тождества следует пажпая информадия о.расположении точек аль-юрыаисч!, пулей и полюсов •£„(<).

В §1.10 рассматривается фильтровая задача

зир Н{-а) —► Ы, (1)

Ы>1/*

где кпфимум берется по всем дробям Я из удовлетворяющим ограничениям

[Н(и) - 1| < Л при ив [-1,1], Н(и) > 0 при |«| > 1 /г. Здесь Д 6 (0,1) фиксированное число (параметр).

Установлено, что задача (1) эквивалентна Четвертой задаче Золотарева при ае = [(1 - у/т)/(1 + а/г)]2. На этой основе доказано следующее утверждение.

ТЕОРЕМА ЮЛ. Задача (1) имеет точно два решения и Уя(1)(и). Они связаны с решениями //п(0 и Четвертой

задачи Золотарева формулами

уМ(и) = и,(Яя(*(«))),

Уп<1>0) = и,(//«(<(«))),

где

и>(у) =

1 1 + и^т

а(1 - А)(у - 1 - у„) - (1 + Д)(у - 1 + у.) а(у - 1 - <рп) - (у - 1 + <рп) 1+ Д

а —

(1- Д)(1+у»)'

- величина наилучшего приближения в Четвертой задаче Золотарева. Экстремальное значение целевой функции в задаче (1) равно '

. ^"гд + а-д)^-

Свойства решений Уп°'(и) и У»^(и) изучаются отдельно при нечетном и четном п.

ТЕОРЕМА 10,2. При п = 2к + 1 справедливо тождество

• . УЯООЕЕУ.РЧ-и).

Дробь У»(0)(и)

обладает такими свойствами:

1) Существуют п+ 1 точки -1 = и0 < щ... < «„ = I, в коюрих

У<0>М - 1 = (-1){+1Д, ¿60: п.

Между втими точками У^ изменяется строго монотонно.

2) На промежутках [1/т,+<х>) и (-сю,-1/г] существуют еще пс к + 1 точек ,

1/т = и»+| < «в+2 < • <

< "»+3+-* < •• • < «а»-и = -I/'",

]) которых

yj°>(un+1+i) = % {»л + (- 1)'+Vn), i € 0 : n.

Межлу втими точками, включая пару (u»+i+n,u»+j+n), дробь Y$°\u) изменяется строго монотонно. 3) Спрапедлтш предельное соотношение

Jm П(0)(«) = А»,

где Лп G (0, цп).

■i) На отрезке [-1/т,-1] дробь монотонно возрастает от

значения /<„ до 1 - Д.

5) В интервале (1,1/т) у Ул"\п) имеется полюс и», причем на промежутках [!,««,) и (и«,, 1/т] дробь vic)(ti) монотонно возрастает от 1 + Д до 4-оо и от -оо до 0 соответственно.

Столь же полные результаты получены и в случае четного г». Отметим, н частности, что дробь VÎ%) при п = 2к непрерывна и неотрицательна на всей вещественной оси. Она монотонно возрастает на [-] /г, -1) от /i» до 1-Д и мопотовво убывает на (1,1/г] от 1 - Д до //». ,

Величина наименьшего уклонения от пуля конечно, зависит ог Д. Однако существует простое выражение, содержащее ц* и Д, значения которого не зависят от Д. ТЕОРЕМА 10.4. Значения выражения

е

* (1-Д)(1 + Д-Й»)

не завися г от Д, т.е. 0П является инвариантом задачи (1).

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

Все результаты §1.10 являются новыми. Глава II (§2.1-2.4) посвящена анализу эффективности'численных методом решения задачи наилучшего дробяо-рацш>шш>пого приближения на системе отрезков. В §2.1 описан метод дифференциальной коррекции для решения сеточной задачи наилучшего приближения на знаковом классе. Сформулированы

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

В §2.2 описан метод выравнивания максимумов для решения непрерывной задачи наилучшей дробно-рациональной аппроксимации на системе отрезков при наличии у решения полного альтернанса.' Летально разработала вычисл ительная схема метода. Сеточные решения из предыдущего параграфа доведены до решений непрерывных задач.

В §2.3 приведены результаты обширных экспериментов по численному решению задачи Чебыгасва. Эта задача рассматривалась как параметрическая, где параметром считался правый конец отрезка аппроксимации. С помощью только выравнивания максимумов решение задачи Чебышева'на отрезке [1,20] последовательно преобразовано в решение на отрезке'[1,10000]. Подтверждена высокая эффективность параметрического метода.

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

В диссертации имеется приложение. Оно содержит программу . на языке SUPER BASIC численного решения непрерывной ладами наилучшего дробно-рационального приближения аа системе от-

ш

резко».

Основное содержание диссертации опубликовано в работах:

1. Гхптшш М. Об одной фильтровой задаче // Теория дробно-рациональных приближеяий.Тезисы докладов конференции. Махачкала, 1991.С.11.

2. Гхашим М. О сильной единственности в задаче наилучшей дробно-рациональной аппроксимации на системе отрезков // Конструктивная теория функций. Тезисы докладов конференции, посвященной 70-летию проф.В.С.Виденского. • С.-Петербург, 1992. С.19-20.

3. Г хашим М.,Малоземоп В.Н. Эквивалентность в задачах наилучшей дробно-рациональной аппроксимации // Вестн. С.-Петербург.ун-та. Сер.1. 1992. Вып. 2. С.3-8.

4. Гхашим М.,Малозомои В.Н. Инвариант одной фильтровой задачи // Вестн.С.-Иетербург. ун-та. Сер.1. 1992.

Пыл. 3. С.89-91.