Дробно-рациональная аппроксимация функций и приложения

Петрак, Лариса Владимировна

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

Петрак, Лариса Владимировна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Дробно-рациональная аппроксимация функций и приложения»

Автореферат диссертации на тему "Дробно-рациональная аппроксимация функций и приложения"

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи УДК 519.6

Петрак Лариса Владимировна

Дробно-рациональная аппроксимация функций и приложения

01.01.07 - вычислительная математика

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

ЕКАТЕРИНБУРГ 2004

Работа выполнена в Институте математики и механики УрО РАН, в отделе теории приближения функций.

Научные руководители:

Официальные оппоненты:

кандидат физико-математических наук,

ст.н.с. Габушин В.Н.,

доктор физико-математических наук,

член-корреспондент РАН,

профессор Бердышев В. И.

доктор физико-математических наук,

член-корреспондент РАН,

профессор Васин В.В.,

доктор физико-математических наук,

профессор Пименов В.Г.

Ведущая организация:

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится

И " ШЮИ % 2004 г. в

часов на заседании

диссертационного совета К.004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ГСП-384, ул. С.Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке ИММ УрО РАН.

Автореферат разослан "_ 14 " и/М Зи 2004 г.

Ученый секретарь диссертационного совета К.004.006.01 к.ф.-м. н., ст.н.с.

Скарин В.Д.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Разработкой алгоритмов для численного решения задачи наилучшего равномерного приближения рациональными дробями занимались многие авторы: Е.Я. Ремез, Вернер, А.Л. Каленчук-Порханова, Ральстон, Стоер, Боммас, Белогус, Лирон (алгоритмы, основанные на характеристической теореме П.Л. Чебышева и являющиеся аналогами И-го полиномиального алгоритма Е.Я. Ремеза), Г.Ш. Рубинштейн, Лоэб, Чини, В.Т. Гаврилюк, Барродайль, Пауэл, Роберте, Кауфман, Тейлор, Лиминг, Мак-Кормик, В.М. Белых, А.И. Роженко и другие (алгоритмы, основанные на сведении нелинейной задачи к некоторой последовательности задач линейного программирования).

Одним из методов решения нелинейных задач среднеквадратического приближения является метод Марквардта и Левенберга2, предложенный ими для нахождения нелинейных аппроксимаций общего вида. Описание этого метода можно найти, например, в книге Ч. Лоусона, Р. Хенсона, посвященной методу наименьших квадратов (1986), у Дэнниса Дж., Шнабеля Р. в их книге о численных методах безусловной оптимизации и решения нелинейных уравнений (1988). Имеются исследования метода в статьях Мейера-Рота, Морисона, Осборна и др. также для случая нелинейных аппроксимаций общего вида.

'Marquardt D.W. An algorithm for least equares estimation of Donlinear parameters // J. Soc. Industr. Appl. Math. 1963. V.U, № 2. P.431-441.

2Levenberg £. A method for the solution of certain non-linear problema in least squares // Quart. Appl. M&th. 1944. V.2, № 3. P.164-168.

ruc. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

Цель работы:

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

2. Исследовать метод Чини-Лоэба с позиции построения общей схемы итерационных алгоритмов, для которой исходный алгоритм и его аналоги были бы частными случаями. Указать условия, при которых алгоритм, построенный на основе общей схемы, сходится, получить соответствующие теоремы сходимости и оценки скорости сходимости.

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

4. Разработать вычислительный алгоритм среднеквадратического приближения функций рациональными дробями, основанный на исследованиях Мейера-Рота 4 и Осбор-на s метода Марквардта-Левенберга.

5. Использовать разработанные алгоритмы при решении прикладных задач.

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

Научная новизна. На основе известного метода Чини-Лоэба предложена общая схема получения итерационных алгоритмов решения задачи наилучшей дробно-рациональной аппроксимации. Указаны условия, при которых алгоритм, построенный на основе этой общей схемы, сходится, приведены оценки скорости сходимости.

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

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

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

Теоретическая и практическая значимость. Теоретическое значение диссертационной работы связано с обобщением алгоритма Чини-Лоэба численного решения задачи наилучшего равномерного приближения рациональными дробями.

Практическое значение диссертационной работы состоит в том, что разработанные автором алгоритмы реализованы в виде программ. Эти программы включены в комплекс программ аппроксимации сеточных функций одной и многих переменных, созданный в лаборатории численных методов отдела теории приближения функций Института математики и механики УрО РАН на основе разработанных сотрудни-

â Cheney E.W., Loeb H.L. Two new algorithms for rational approximation // Numer. Math. 1961. V.3, № 1. P.72-75.

4Meyer R.R., Roth P.M. Modified dainpted least squares: an algorithm for non-linear estimation //J. lost. Math. App. 1972. V.9, № î. P.218-233.

'Osborne M.R. Nonlinear least squares - The Levenberg algorithm revised // J. Austral. Math. Soc. Ser. В. 1976. V.19. P.343-357.

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

Агшробация работы. Результаты диссертации докладывались на школе-конференции по теории аппроксимации и математической физике (Казань, 1984 г.), на Всесоюзной конференции по теории приближения функций (Ленинград, 1989 г.), на 3-й Всесоюзной конференции "Новые подходы к решению дифференциальных уравнений" (Дрогобыч, 1991 г.), на школе-конференции "Алгебра и анализ", посвященной 100-летию со дня рождения Б.М. Гагаева (Казань, 1997 г.), на совместных семинарах отдела теории приближения функций и отдела аппроксимации и приложений Института математики и механики УрО РАН (г. Екатеринбург), на семинаре кафедры вычислительной математики Уральского государственного университета (г. Екатеринбург).

Публикации. Основные результаты диссертации опубликованы в работах [1]-[9]. В (3) автором выполнены все расчеты. В [6] ему принадлежит раздел, относящийся к дробно-рациональной аппроксимации. Результаты первой и третьей глав описаны также в монографии [10], где автором диссертации написаны параграф 9 главы I и параграфы 6 и 8 главы III.

Структура и объём работы.

Диссертация состоит из введения, трех глав и списка литературы из 70 наименований. Общий объем диссертации — 123 страницы машинописного текста, включая 2 таблицы.

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

Во введении кратко изложено состояние вопроса, приводятся основные результаты диссертации.'

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

Пусть DcR' некоторое конечное множество, состоящее из N >т + п — 1 точек, т,п - натуральные числа. На множестве D заданы функция /(z) и две системы функций

Vi (я), •••.¥>«(*) и Щх),..., 1>т{х),

каждая из которых линейно-независима на D. Обозначим V^ — {Р : Р(х) — eupm{x)}, Q(m> = {Q : Q(x) = EJLi} (PuQi e R) - множества обобщенных полиномов. Определим множество рациональных дробей

Я,,т = {ад = P(x)/Q(x) : Р(х) е 7>М, Q(x) е Q(m), (1

Q(x) > 0 Vxe D, р„2, е R}. Обозначим Д(Я) = Д(P,Q) = тм|/(х) - Л(®)|.

Будем решать задачу наилучшего приближения: найти

А* = inf {Д(Я) : R 6 72n,m} (1.2)

и дробь Я*, для которой Д(Д') = Д*.

В 1961 году Чини и Лоэб 8 для решения задачи (1.2), предложили следующий итерационный алгоритм:

1) Пусть на начальном шаге задана дробь До = Po/Qo с положительным знаменателем в точках D. Обозначим До = Д(Ро, Q0)i

2) Пусть на к-м шаге получена дробь Pk/Qk- Тогда на (fc -I- 1)-м шаге Pk+i/Qkt-i получается решением следующей минимаксной задачи:

P.QztD Qk(x) '

при ограничениях

О < а < Q(x,) <ß Vi, G D, (1.4)

где a,ß > 0 — наперед заданные числа, Д* -= A(Pk,Qk). Ими было доказано, что Ак -+ Д* при fc —V оо. В 1962 году они в случае отрезка D = [о, 6] для алгебраических рациональных дробей доказали сходимость алгоритма для несколько измененного вида минимизируемого функционала:

max\f(x)Q(x) - Р(х)\ - AkQ(x) (1.5)

при ограничениях на коэффициенты числителя и знаменателя

|ц|<1, i=l,....п, |?,|<1, j=l.....m, (1.6)

показав при этом, что скорость сходимости этого алгоритма линейная. Позднее также в непрерывном случае ими была доказана сходимость этого алгоритма без требования ограниченности коэффициентов числителя. Барродайль, Пауэл и Роберте в 1972 году для дискретного случая доказали сходимость алгоритма для исходного вида минимизируемого функционала (1.3) и, кроме того, доказали, что при некоторых дополнительных условиях на функцию / скорость сходимости этого алгоритма квадратичная.

Развитием алгоритма в теоретическом плане занимались также Дьюа, Лоэб, Белых В.М., Кауфман, Лиминг, Тейлор.

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

Построение этой общей схемы дается в первом параграфе. Описывается некоторый достаточно широкий класс множеств Т С для которых алгоритм сходится.

'Cheney E.W., Loeb Н L. Two new algorithms for rational approximation // Numer. Math. 1961. V.3, № 1. P.72-75.

Пусть Т С Q(m) — некоторое множество полиномов. Будем решать следующую задачу

inf {Д(Я): Я = F/Q, Р е Vм, Q 6 Г} . (1.7)

В качестве начальной берем произвольную дробь Po/Qo, У которой Р0 е 7>(п\ Qa 6 Т, Qa(x) > 0 Vi 6 D. Пусть на к-м шаге получена дробь Pk/Qk и Д4 = Д(Р*, £?*). Тогда на (fc + 1)-м шаге решается минимаксная задача

JS* -МЗД (1.8)

где

•MP.S) = J^P.Q) - (L9)

Л — фиксированное число. Если J&t ф 0, то в качестве Рц+i, Qt+i берется решение задачи (1.8), при этом Д*+1 = A(Pk+uQk+i)- Если J&k — 0, то считаем Р*+1 = Рк, Qt+i — Qk, Д*+1 = Д*. При практической реализации алгоритма условие = О означает необходимость останова.

Определение 1. Множество Т С будем называть допустимым, если множество

t+ = {qg7': q(x) > 0}

ограничено и замкнуто на D и выполнено следующее

Условие А. Для любой функции / существует такая последовательность дробей R, = Pi/Qi, Р, € 7><n>, Qi е Г, Q,(x) > 0 Vi € D, что

Д(Д|) -> Д* при I оо.

Если Т+ С является поглощающим множеством, то задачи (1.2) и (1.7) эквивалентны.

Определение 2. Множество полиномов Q е 74" таких, что t/Q £ Т при любом V > 1, будем называть границей Т4" и обозначать через Г+.

Заметим, что условие Л будет выполняться, если в задаче (1.2) для любой / существует наилучшая рациональная дробь R' = P'/Q* такая, что Q' е Т+ и <5* (г) >0 Vx € L>. Однако в алгоритме существование наилучшей дроби для функции /, вообще говоря, не требуется.

Решение задачи (1.8) является существенной частью алгоритма. Во втором параграфе рассматривается несколько более общая, чем (1.8), минимаксная задача:

Уд= inf MP,Q), (1.10)

Ре*><">, Oer

где

MP, Q) = W. «) = -ёЫ-•

Д > 0 — произвольное фиксированное число, Q(x) — некоторая функция, 0 < Q(x) < оо для любого х Е D. Исследуется зависимость решения задачи (1.10) от величины параметра Д, когда Д > Д* или Д < Д*. Доказана следующая теорема:

Теорема 1. Пусть Т — допустимое множество. Если А > Д*, то задача (1.10) всегда имеет решение и 7д < 0. Если 0 < Д < Д*, (¿{х) = 0 принадлежит Т, то пара Р, (} : Р = ф г О является решением задачи (1.10) и = 0.

В частном случае, когда 5 5 1, |р,| < 1 (г — 1,...,п), < 1 (у = 1,...,тл) условие Д < Д*, рассматривалось также в работе Белых В.М. 7, где показано, что если в задаче линейного программирования, соответствующей задаче (1.10), имеется решение вида = 0, Р = <3 = 0 или Jй. = 0, <2(х,) = 0 для некоторого х,- € И, то Д < Д*.

Следствие 1. Если Т — допустимое множество, Д > 0, то Уд < 0 тогда и ШОлоки тоси'л, когда Д > А*.

В третьем параграфе устанавливается сходимость алгоритма и приводятся оценки скорости сходимости.

Отличия в доказательстве теоремы 2 от доказательства соответствующей теоремы сходимости из 8 связаны с тем, что рассматривается не только случай А = 1, но и случай, когда Л е [0,1). При этом дополнительно рассмотрен случай Д* — Д*.

Теорема 2. Пусть Т допустимое множество, 0 < А < 1. Тогда А/, —> А', к -+ оо. Равенство Д* — Д* (Я* = Я*) выполняется тогда и только тогда, когда 7д, = 0.

Следствие 2. Пусть для функции /(х) в множестве Лп,т существует наилучшая рациональная дробь И'(х) — Р*{х)/С}'(х) и пусть 0 < А < 1, Т — допустимое множество. Тогда

Д*+1 — Д* < С (Дц — Д*), (1.11)

где константа С < 1 и может быть записана в виде

г - í (Х - для 0 < А ^ (1-Ь)а*дА = о,

ti' = minQ*(i), rtk — minQ,(i) m = max maxO(a;).

Формулируемые далее теоремы 3 и 4 доказаны для случая алгебраических дробей. Будем использовать обозначение Т^ в принятом для алгебраического случая смысле: множество многочленов степени, не превосходящей п, т.е.

n m

7><"> = {Р(х): Р(х) = QM = W(x) : Q{x) = gjX>} (1.12)

¡=o 1=0

и lln.m определяется, как в (1.1) с учетом условия (1.12). Заметим, что в связи с таким пониманием пят прежнее ограничение для N перепишется соответственно в виде N > п + т -I-1.

'Белых В М. О решения вырожденных задач наилучшей дробно-рациональной аппроксимации // Вести. Ленингр. ун-та. 1976. № 7. С.5-12.

'Barrodale I., Powell M.J.D., Roberts F.D.K. The differential correction algorithm for rational {«,-approximation // SIAM J. Numer. Anal. 1972. V.9, № 3. P.493-504.

Приведем здесь определение нормальной наилучшей дроби и известную теорему о сильной единственности в.

Определение. Наилучшую дробь Я* -= P'/Q' называют нормальной, если она принадлежит пространству Hn,m\'R-n-i,m-i> т.е. она несократима и старшие коэффициенты числителя и знаменателя не равны нулю одновременно.

Теорема [о сильной единственности]. Если X - ограниченное множество и Я* е 71п т - нормальная наилучшая дробь для функции f, то для всех R € выполняется неравенство Д(Я) — Д(Д*) > 7ЦЯ — Я*||, где 7 > 0 не зависит от Я. Здесь и далее \\g(x)\\ = maxieD |s(x)|-

Введем следующее- _

Определение 3. П^схь R = 1 7Zn,m Т*. Будем говорить, что R обладает свойством L на Т, если для всех R = P/Q € Ип,т таких, что Q С Т+, имеет место неравенство

||в-<3]|<в||Д-Я||,

где в < оо не зависит от R.

ГГри доказательстве теоремы 3 используется схема доказательства из 10, однако оценки существенно изменены и приведены к виду, удобному для приложений.

Теорема 3. Пусть А = 1, Т — допустимое множество. Если Я* е Ип.т — нормальная наилучшая дробь для функции /, обладающая свойством Ь на Т, то

Д*+1 — Д* < с (Д* — Д*)4, (1.13)

где с > 0 — некоторая константа, не зависящая от к.

Теорема 4 обобщает следующий результат из работы п: если для функции / наилучшая рациональная дробь Я' С 7¿n,m является нормальной и коэффициенты знаменателя этой дроби удовлетворяют условию

= 1, ¿=1.........(1.14)

то для всех Я = P/Q 6 TZn,m, коэффициенты знаменателей которых удовлетворяют тому же условию, имеет место неравенство

||Q-Q'||<0||ß-Ä*|l, (1-15)

где в < оо не зависит от Я.

При доказательстве теоремы 4 мы используем некоторые идеи доказательства из работы ,2.

'Cheney E.W. Introduction to approximation theory. New York: McGraw-Hill, 1986.

'"Barrodale I., Powell M.J.D., Roberts F.D.K. The differential correction algorithm for rational loo-approximation // SIAM J. Numer. Anal. 1972. V.9, № 3. P.493-504.

"Barrodale I., Powell M.J.D., Roberts P.D.K. The differential correction algorithm for rational t»-approximation // SIAM J. Numer. Anal 1972. V.9, № 3. P.493-504.

"Dua S.N., Loeb H.L. Further remarks on the differential correction algorithm // SIAM J. Numer. Analysis. 1973. V.10, Jft 1. P.123-126.

Теорема 4. Если множество Т+ замкнуто и ограничено, Л* — Р*/(2* 6 Ип,т ~ нормальная наилучшая дробь для функции /, ф* ЕР, то существует константа в < оо такая, что для любых <2 и Р € выполняется неравенство

||<Э - Q*|| < м min " "» И — 0<|<п

Ii ~ Я'

+ 0||й-Я'||, (1.16)

где М — тахд6Г+ ||Q(x)||.

В четвертом параграфе приводятся конкретные множества Т, определяемые меньшим числом неравенств, чем у других авторов. Ранее рассматривались множества Т» — Т3, определяемые соответственно ограничениями (1.4), < 1 (j = 1,..., m) и (1.14). Для них доказана сходимость, в том числе и в случае обобщенных рациональных дробей 13. Введенные нами множества в случае алгебраических дробей имеют вид:

Г4 = {Q € Ö<m>: Q(xi)<Mit Vх4еУ}, где Y С D, М^ — M(zj) — некоторые положительные числа.

Г5 = {(3 = Е™о9,1,6(2(т': Qi < 1, ¿ = 0,1.....m},

7в = {0 = ЕГ=о9,^'ее(т): Qu < 1. 92»+i>-1, fc = 0,l,...,[m/2]},

7V = {Q = Er=o9i^eQ(",>: 92* <1, k = 0,1,..., [m/2]}; x € D (обозначение [а] здесь и далее означает целую часть числа а).

Доказаны следующие теоремы, устанавливающие допустимость множеств T^—Tj, а также соответствующую сходимость А» к Д* (к -* оо).

Теорема 5. Пусть De R — конечное множество точек N, где N > п + m +1, 1 — 2 • Множество Tt допустимо, если множество У CD содержит не ме-

нее (т + 1)-й различной точки; множество Ts допустимо, если среди точек множества D имеется хотя бы одна точка х > 0; множество Тв допустимо, если -имеется среди точек D хотя бы одна точка х < 0; множество TV допустимо в следующих случаях: a) D — непустое симметричное относительно нуля множество, б) D содержит симметричное относительно нуля подмножество D, состоящее не менее, чем мз1 + 1 точки, в) D таково, что найдется 2(1 — 1) непересекающихся попарно симметричных относительно нуля интервалов, каждый из которых содержит хотя бы одну точку из множества D (т> 1).

Теорема 6. Пусть DCR- конечное множество, содержащее не менее n+m+1 точки, Т = Ti (i = 4,5,6,7) — допустимое множество, А = 1, Лп,т — мнооюеетво алгебраических рациональных дробей. Если наилучшая для функции f дробь R* 6 Ип<т является нормальной, то скорость сходимости алгоритма по крайней мере квадратичная, т.е. верна оценка (1.13).

В дополнение к ранее известным случаям, когда знаменатели обобщенных рациональных дробей принадлежат множествам 7\ —Tj, приведем множество 7j = {Q(x) = EJLi Qjipjix) '■ < 1. j — 1,..., m}, аналог множества Ts, для которого также доказана сходимость.

14Cheney B.W. Introduction to Approximation theory. New York: McGraw-Hill, 1966.

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

Основным элементом итерационного алгоритма для задач наилучшего равномерного приближения является решение па каждом шаге следующей минимаксной задачи

тшр

<?*(*<) 1-1,...,Л, 11.10

при ограничении <5 £ Т, сводящейся к некоторой задаче лилейного программирования. Для решения этой задачи используется симплекс-метод с учетом специфики задач наилучшего равномерного приближения. Специфической чертой для таких задач является наличие симметрии в соответствующих парах ограничений задачи линейного программирования.

В первом алгоритме решается задача минимизации с односторонними ограничениями на коэффициенты знаменателя:

тш-/1 (1.18)

при ограничениях

*к = Е <Р„Ру + (Д* - /М) ЕФцЦ ~ > О,

п* = - £ Ч>№ + (Д* + /(*<)) £ - > О,

(1.19)

« = 1,

+1 > о,

где = Фч = Ф)(х*)> V = -Д-

Предлагается специальный способ исключения свободных переменных р„ з — 1,...,п, и ф, } — 1,...,т, в задаче (1.18)-(1.19), позволяющий сохранить неотрицательность элементов столбца свободных членов в (1.19) и, тем самым, избежать в симплекс-методе этапа поиска опорного решения. Используя особенности матрицы ограничений и симметрию коэффициентов р,, з = 1,..., п, в парах основных ограничений т^, »/_,•, в процессе их исключения преобразуется не вся матрица ограничений, а некоторая вспомогательная матрица меньшего размера, при этом размеры матрицы еще уменьшаются, если набор базисных функций числителя совпадает с первыми п базисными функциями знаменателя и наоборот. В последнем случае выведены формулы, позволяющие, используя элементы вспомогательной матрицы, получившиеся в результате исключения р„ з — 1,..., п, вычислять измененные значения всей матрицы. Эти формулы можно использовать в начале каждой итерации, считая, что переменные р„ з = 1,...,«, исключены через те же ограничения, что на первом шаге, и можно начинать итерацию сразу с исключения j — 1,..., т. В алгоритме не предполагается заранее линейная независимость на Б систем функций {и Возможная линейная зависимость функций отслеживается на ста-

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

Кроме того, имеется возможность после первой итерации решать задачу (1.18)-(1.19) на подмножестве D7 точек х € D, для которых

|/(i) - Я*(х)| > 7max\f(y) - Rk(y)\, к > 1,

где коэффициент 7, удовлетворяющий неравенству 0 < 7 < 1, изменяется по некоторому правилу. Отметим, что А.И. Роженко 14 разработан вычислительный алгоритм, в котором используется на каждой итерации подсетка и при этом соответствующая задача линейного программирования решается до тех пор, пока не возрастет максимум модуля уклонения на всем множестве.

Во втором алгоритме используется двойственная к исходной задача. Отметим, что в отличне от предшествующего случая, предполагается, что ¡¡jjj < 1, j — 1,..., от. С учетом специфики задач равномерного приближения предлагается способ конструктивного построения начального базисного множества, при котором за n+1 шаг жор-дановых исключений в двойственной задаче получается допустимое базисное решение. Этот способ является обобщением используемого В.Л. Александренко 15 приема построения базисного множества в полиномиальной задаче.

Так же, как в алгоритме В.Л. Александренко, можно вместо использования двумерного массива размера (n + m + 2) х (2N + 2т + 1), определяемого матрицей ограничений и строкой коэффициентов целевой функции рассматриваемой задачи, использовать массив размера (n+m+2) х (ЛГ+m+l), определяемый матрицей, соответствующей первым N основным ограничениям r^ {i — l,...,N) исходной задачи и первым m ограничениям на коэффициенты знаменателя. Информация, которая явно не присутствует в используемом массиве, но которая должна участвовать в процессе построения решения задачи, всегда может быть восстановлена в случае необходимости из соотношений, связывающих соответствующие в исходной задаче ограничения ц, и т?_( (аналогично для ограничений на коэффициенты знаменателя).

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

Пусть z* = (z*,..., z*+m)T — вектор коэффициентов (без коэффициента при он фиксирован и равен 1) некоторой дроби Rk = R[zh, s) G TC„,m, полученный на fc-м шаге алгоритма. Класс дробей Ti„,m определяется как в первой главе. На (к + 1)-м шаге решается задача

min ¡1W (JkAz + + 7* LJLi v^Az^ Qk(z* + АД г, Х() > О, |'=1,...,ЛГ, ¿ = 1,2,...

где ДzT = (Azu...,Azm), е{ = (е{.....ej,), е* = e,{zk) = R{zk,Xi) - /(¡г,). » =

1,...,N, W — диагональная матрица размера N х N с элементами ад« = > О,

Li Роженко А.И. Реализация некоторых алгоритмов теории приближения функций: Отчет / ВЦ СО АН СССР. Новосибирск, 1982.

1бАлехсандрепко В.Л. Алгоритм построения приближенного равномерно-наилучшего решения системы несовместных линейных уравнений // В кн.: Алгоритмы и алгоритмические языки. М: ВЦ АН СССР, 1968. вып. 3. С. 57-78.

Л = — матрица размера N х m, i = 1,..., ЛГ, j = 1,..., т, % = 1 j =

1.....т, или в качестве v,j можно взять соответствующие диагональные элементы

матрицы JjWJi¡, 7,t > 0 — некоторое действительное число. Если для полученного вектора-поправки Az значение полинома Д<Э(г) хотя бы в одной точке ДQ(xí) < О, то добиваемся положительности знаменателя за счет выбора параметра А = А* по формуле

А* = min{ |Qt(x,)/AQ(ri)|: C?fc(xt)/A<9(xt) < 0}

и дальнейшего уточнения коэффициента при Дz по правилу: находим номер j, такой, что в точке zk + At(l/2)J"Aí достигается минимум

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

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

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

Задача оперативного вычисления координат точки падения центра масс исходит от В.Д. Батухтина и Л .А. Майбороды. Разработка моделей движения центра масс с учетом различных возмущающих факторов и программ, реализующих решение соответствующих систем дифференциальных уравненией, описывающих движение материальной точки, осуществлялась А.Н. Ходаковским и сотрудниками ВИКИ им. А.Ф. Можайского. Разработка методики аппроксимации, ее реализация и построение моделей для вычисления точки падения из любой начальной точки рассматриваемой области осуществлялась под руководством и при непосредственном участии В.И. Бердышева В.П. Кондратьевым, Л.В. Петрак. В частности, Л.В. Пет-рак построены все дробно-рациональные модели. При их построении использовались разработанные автором программы наилучшего равномерного и среднеквадратиче-ского приближения функций многих переменных. В параграфе приводится общее описание задачи, постановка задачи аппроксимации, описание методики, приводятся построенные дробно-рациональные модели и величины, характеризующие точность моделей.

В качестве иллюстрации приведем вид рациональной дроби, используемой для приближения конкретной функции шести переменных ^'(А, Н,А,ч>,6., V). Для решения задачи аппроксимации в области изменения переменных

этой функции была выбрана прямоугольная сетка т = {х, = (А*,Н', А',<р',в',и')} так, чтобы сеточная функция отражала особенности поведения реальной функции. Общий размер сетки т, на которой требовалось построить аппроксимацию определялся общим числом точек

N - ЛГЛ х АГН х Лл х х Лг„ х = 7 х 4 х 20 х 5 х 16 х 8 = 358400.

В результате проведенных исследований полученной сеточной функции было выявлено, что поведение функциий Ж по переменным Н и Л носит простой - линейный характер, а для приближения по переменным А, <р, в, V использовались рациональные дроби (полиномы приемлемых степеней не давали достаточной точности). Полученная в результате расчетов рациональная дробь

Я = ЩА, <р, в, «) =

—^-]-7БГТ £ *т(Л){Е Е аЫтвкь1+

Е О.,*^ 0 V к=0 (1.21)

0<«+*+/<2 т**

+4? Е Е Ьк1твЧ + СълЧУО1 + СпМъЧ + СгаЗ^в2}, 1=0 »=0 '

где ^(Л) = 1, Ф2(Л) = зт(А), Ф3(Л) = со«(Л), Ф4(Л) = зт(2Л), Ф5(Л) = соз(2А), имеет в числителе 84 коэффициента, в знаменателе - 10.

Приближающая функция

Р = Р( А, Я, А, <р, в, v) = Я(Л, <р, в, V) + (Н~50)Д(Л, <р, в, ь)+

+(А-600)й{А,ч>,в,ь)

(Я, Я — функции вида (1.21), знаменатель у дробей Я, Я, Я общий) имеет 262 коэффициента. Для вычисления значения в точке требуется выполнить 3200 элементарных операций. При этом относительная погрешность в процентах составила 3.1% для максимального и 0.78% для среднеквадратического уклонения, что удовлетворяет точности, требуемой в данной задаче.

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

географических координат ч>,\ на любой высоте Н в пределах рассматриваемого региона.

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

(1.22)

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

1 10 181

= { ИМ £ А», Я,) - г(<рк, А*, Я,))2}

1/2

(1.23)

в пределах от 1.1 до 2.0°С в зависимости от месяца, что не превосходит средпеква-дратические ошибки измерения, которые колеблются от 1° до 2° в слое 3-15 км. и от 1° до 5° в слое 30 км.

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

Имеются различные способы приближенного вычисления функций К„ и Е„ (например, можно использовать таблицы, вычислять с помощью рядов и квадратур, определять их с помощью других вспомогательных функций, которые, в свою очередь, выражаются через табулированные функции Бесселя второго рода от мнимого аргумента и интегралы от них).

На основе рациональных дробей были получены эффективные формулы, дающие аналитическое представление для интегро-экспоненциальных функций Еп и модифицированных функций Бесселя третьего рода К„, использующихся в этих задачах.

С помощью программы, в которой реализовал алгоритм, описанный в § 1 второй главы, для функций Еп(х), 2<п <6, были получены формулы вида

Е„(х) <

для функций ^п0>0> 1 < п < 4, ~ формулы вида

Эти формулы можно использовать для вычисления значений на всем интервале [0,оо). Максимальная абсолютная погрешность всех формул на всем отрезке изменения аргумента [0, оо) не превышает для функции Еп(х) величины 3 • 10~6 (при х = 0), для функции К/х) - 13 • 10~8 (при х = 0). Относительная погрешность на исследованном отрезке х £ [0,7], как правило, значительно меньше 0.01% для функции Еп и 0.005% для К. Задача аппроксимации функций Е„, Кп возникла в связи с задачей рационализации расчетов лучистых потоков в простейших системах тел. Полученные результаты изложены в [3]. Как отмечено там, использование полученных формул при расчете лучистых потоков дает большую экономию времени, существенно облегчая процесс вычислений, без значимой потери точности.

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

Основные результаты диссертации состоят в следующем:

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

2. Предложена общая схема построения итерационных алгоритмов, в которую вкладываются алгоритм Чини-Лоэба и его аналоги. Приведены условия, при которых алгоритм, построенный на основе общей схемы, сходится, доказаны теоремы сходимости, приведены оценки скорости сходимости.

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

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

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

Автор глубоко признателен и искренне благодарен своим научным руководителям В.Н. Габушину и В.И. Бердышеву за помощь при выполнении работы и постоянный интерес, проявляемый к работе.

Основные результаты по теме диссертации изложены в следующих работах:

1. Петрак Л.В. Приближение функций одного переменного рациональными дробями // Тр. ИММ УНЦ АН СССР. 1975. Вып. 6: Программы оптимизации

(приближение функций). С.110—129.

2. Петрак Л.В. Приближение функций многих переменных рациональными дробями // Тр. ИММ УНЦ АН СССР. 1975. Вып. 6: Программы оптимизации (приближение функций). С. 130-144.

3. Детков СП., Пономарев Н.Н., Петрак Л.В. Рационализация расчетов лучистых потоков в простейших системах тел // Инж.-физ. журн. 1977. Т.ЗЗ, № 2. С.356. ( Минск, 1977. 9 с. Деп. в ВИНИТИ, Л* 784-77 Деп.)

4. Петрак Л.В. Об одном методе решения задачи наилучшей рациональной аппроксимации // Журн. вычисл. математики и мат. физики. 1978. Т.] 8, № 4. С.860-869.

5. Петрак Л.В. Рациональная аппроксимация функций обобщенным методом Чи-ни-Лоэба // Алгоритмы и программы приближения функций: (Материалы по мат. обеспечению ЭВМ). 1981. С.82-98.

6. Кондратьев В.П., Пацко Н.Л., Летрак Л.В. Комплекс программ аппроксимации // Структура и организация пакетов прикладных программ: (Материалы по мат. обеспечению ЭВМ). Свердловск: УНЦ АН СССР, 1983. С.116-131.

7. Петрак Л.В. Среднеквадратичное приближение функций многих переменных обобщенными рациональными дробями // Алгоритмы приближения функций: (Материалы по мат. обеспечению ЭВМ). 1987. С.89-106.

8. Петрак Л.В. Об одном алгоритме среднеквадратичной рациональной аппроксимации // Тез. докл. 3 Всесоюз. конф. "Новые подходы к решению дифференциальных уравнений"(Дрогобыч, 17-21 июня 1991 г.). М.: ВЦ АН СССР, 1991. С. 104.

9. Петрак Л.В. Об алгоритмах наилучшей рациональной аппроксимации // Тез. докл. шк.-конф. "Алгебра и анализ", посвящ. 100-летию со дня рождения Б.М. Гагаева. Казань, 1997. С. 170-171.

10. Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297 с.

Петрак Лариса Владимировна

Дробно-рациональная аппроксимация функций и приложения

АВТОРЕФЕРАТ Подписано в печать .05.2004. Формат 60x84/16. Объем i. п.л. Тираж 100 экз. Заказ №

Размножено с готового оригинал-макета в АСМ Электронике г. Екатеринбург, ул. Красноармейская. 1

PIO 140

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Петрак, Лариса Владимировна

ВВЕДЕНИЕ

I. ОБОБЩЕНИЕ МЕТОДА ЧИНИ-ЛОЕБА ДЛЯ РЕШЕНИЯ ЗАДАЧ АППРОКСИМАЦИИ РАЦИОНАЛЬНЫМИ ФУНКЦИЯМИ

1. Описание общей схемы алгоритмов типа алгоритма Чини-Лоэба.

2. Вспомогательная минимаксная задача. Существование ее решения.

3. Сходимость алгоритма и оценки скорости сходимости

4. Допустимые множества.

И. ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ РАВНОМЕРНОЙ ДРОБНО-РАЦИОНАЛЬНОЙ АППРОКСИМАЦИИ

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

1.1. Вид'решаемой задачи линейного программирования, основные особенности алгоритма.

1.2. Способ исключения свободных переменных

1.3. Информация, которую можно использовать на каждой итерации.

1.4. Правило выбора подмножества точек.

1.5. Тестовый пример.

2. Второй вычислительный алгоритм для равномерного приближения функций рациональными дробями.

2.1. Постановка задачи, обозначения, некоторые свойства решаемой задачи.

2.2. Способ построения подходящего начального базисного множества и его обоснование.

3. Алгоритм среднеквадратического приближения функций рациональными дробями

3.1. Постановка задачи.

3.2. Описание алгоритма. 3.3. Вычислительная схема алгоритма.

III. ИСПОЛЬЗОВАНИЕ АЛГОРИТМОВ ДРОБНО-РАЦИОНАЛЬНОЙ АППРОКСИМАЦИИ ПРИ РЕШЕНИИ ПРИКЛАДНЫХ ЗАДАЧ 82 1. Аппроксимация координат точки падения центра масс

1.1. Общее описание задачи.

1.2. Постановка задачи аппроксимации поправок

1.3. Дробно-рациональная аппроксимация в задачах приближения поправок

Щ' 2. Аппроксимация параметров атмосферы.

2.1. Введение.

2.2. Методика построения моделей атмосферы.

2.3. Постановка задачи.

2.4. Региональные модели температуры

2.5. Региональные модели скорости ветра.

3. Дробно-рациональная аппроксимация в задачах тепломассообмена

3.1. Примеры использования функций Еп и Кп в за дачах

3.2. Способы вычисления значений Кп и Еп.

3.3. Методика построения эффективных формул

3.4. Решаемая задача аппроксимации и полученные результаты

Введение диссертация по математике, на тему "Дробно-рациональная аппроксимация функций и приложения"

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

Разработкой алгоритмов для численного решения задачи наилучшего равномерного приближения рациональными дробями занимались многие авторы [б]-[8], [12], [21] [23], [26]-[29], [32]-[37], [42], [44]-[60], [65], [67], [68].

Идеи, разрабатываемые в этих алгоритмах, в той или иной мере, связаны с именами Е.Я. Ремеза, Г.Ш. Рубинштейна, Чини, Лоэба.

Среди алгоритмов для решения задачи наилучшего равномерного приближения рациональными дробями наибольшее развитие получили алгоритмы, основанные на двух основных подходах к ее численному решению: первый подход связан с характеристической теоремой П.Л. Че-бышева и теоремой Валле-Пуссена об оценке снизу величины наилучшего приближения [3], второй основан на сведении нелинейной задачи к некоторой последовательности задач линейного программирования [37], [19].

Алгоритмы, реализующие первый подход, наиболее эффективны, вообще говоря, для приближения функций одного независимого переменного. Наибольшее признание среди алгоритмов этого типа получили аналоги второго алгоритма Е.Я. Ремеза [34]. Ранние разработки, касающиеся этого алгоритма, связаны с именами Е.Я. Ремеза, Вернера, Ральстона [65], Коди - Стоера [50], Куртиса и Осборна [52]. Дальнейшим развитием таких алгоритмов занимались Вернер [67], Вернер - Стоер - Боммас [68], А.А. Каленчук-Порханова [33], [21], Белогус - Лирон [45]. Алгоритмы, основанные на втором алгоритме Е.Я. Ремеза, отличаются быстродействием, но сходятся не от любого начального приближения (обзоры алгоритмов разных лет [51], [59]).

Второй подход связан с именами Г.Ш. Рубинштейна, Лоэба и Чини [37], [60], [46]. Среди алгоритмов, реализующих этот подход, наиболее эффективным [59] в смысле универсальности и надежности является итерационный алгоритм Чини-Лоэба [46] и его аналоги [47], [42], [6], [28], [56]—[58], [36]. Эти алгоритмы сходятся при любом начальном приближении.

Задача среднеквадратической дробно-рациональной аппроксимации исследована существенно хуже с теоретической точки зрения, чем аналогичная задача наилучшего чебышевского приближения. Одним из методов решения нелинейных задач среднеквадратического приближения является метод Марквардта-Левенберга для нахождения нелинейных аппроксимаций общего вида. Идея метода изложена в статье Левенбер-га [61], усовершенствования в метод внесены Марквардтом [62] (часто метод называют методом Марквардта). Описание этого метода можно найти, например, в книге Ч. Лаусона, Р.Хенсона [24], посвященной методу наименьших квадратов, у Дж. Дэнниса, Р. Шнабеля в их книге о численных методах безусловной оптимизации и решения нелинейных уравнений [18]. Имеются исследования метода в статьях Морисона [64], Мейера-Рота [63], Осборна [66] и др. также для случая нелинейных аппроксимаций общего вида. В методе Марквардта-Левенберга делается попытка использовать преимущества метода минимизации Ньютона посредством учета нелинейности в квадратичной аппроксимации минимизируемой функции без использования вторых производных. Метод прост в реализации и несмотря на то, что он может медленно сходиться на сильно нелинейных задачах, он во многих случаях, как показывает опыт решения прикладных задач большой размерности, дает подходящее, с практической точки зрения, приближение за небольшое число итераций.

В первой главе содержатся результаты, связанные с обобщением метода Чини-Лоэба [46] для решения задачи наилучшей равномерной аппроксимации функций, заданных на дискретном множестве точек, рациональными дробями. Глава состоит из 4 параграфов.

Пусть D С R* некоторое конечное множество, состоящее из N > тп + п — 1 точек, m, п - натуральные числа. На множестве D заданы функция f(x) и две системы функций

Pl{x),.,lfn(x) и ^i(x),., 1рт{х), каждая из которых линейно-независима на D. Обозначим V^ = {Р :

Р{х) = Q{m) = {Q : Q(x) = EJL(PuQj e R)

0.1)

- множества обобщенных полиномов. Определим множество рациональных дробей пп,т = {Д(*) = P(x)/Q(x) : Р(х) <Е P<n>, Q(x) G Q(m), Q(x) >0 € D, Pi, qj € R}.

Обозначим A(R) = A(P, Q) = max \f(x) - R(x) |.

Будем решать задачу наилучшего приближения: найти

A* = inf{A(£): Renn,m} (0.2) и дробь R*, для которой A(R*) = А*.

В 1961 году Чини и Лоэб [46] для решения задачи (0.2) предложили следующий итерационный алгоритм:

1) Пусть на начальном шаге задана дробь Rq = Pq/Qq с положительным знаменателем в точках D. Обозначим До = A(Po>Qo);

2) Пусть на к-и шаге получена дробь Pk/Qk • Тогда на (к + 1)-м шаге Pk+i/Qk+i получается решением следующей минимаксной задачи: infmaxi' (0.3)

P,Q xeD Qk(x) v ' при ограничениях

0 < а < Q(xi) < /3 Vxi е D, (0.4) где а, (3 > 0 — наперед заданные числа, А& = A(Pk,Qk). Ими было доказано, что —У А* при к —> со. В 1962 году они [47] в случае отрезка D = [а,Ь] для алгебраических рациональных дробей доказали сходимость алгоритма для несколько измененного вида минимизируемого функционала: max |f(x)Q{x) - Р{х)\ - AkQ{x) при ограничениях на коэффициенты числителя и знаменателя Ы < 1, г = 1,., n, \qj\ < 1, j = l,.,m, показав при этом, что скорость сходимости этого алгоритма линейная. Позднее также в непрерывном случае ими была доказана сходимость этого алгоритма без требования ограниченности коэффициентов числителя. Барродайль, Пауэл и Роберте [42] в 1972 году для дискретного случая доказали сходимость алгоритма для исходного вида минимизируемого функционала (1.3) и, кроме того, доказали, что при некоторых дополнительных условиях на функцию / скорость сходимости этого алгоритма квадратичная. Развитием алгоритма в теоретическом плане занимались также Дьюа, Лоэб, Белых В.М., Кауфман, Лиминг, Тейлор [53], [б], [56]-[58] и др.

Построение этой общей схемы дается в первом параграфе. Описывается некоторый достаточно широкий класс множеств Т С Q(m\ для которых алгоритм сходится.

Пусть Т С Q— некоторое множество полиномов. Будем решать следующую задачу inf {Д(Д) : R = P/Q, Р е 7>(n), Q е Т) . (0.5)

В качестве начальной берем произвольную дробь Po/Qo, у которой Ро е V{n), Qo е Т, Qo(x) > 0 Ух £ D. Пусть на к-м шаге получе-ф на дробь Pk/Qk и Ак = А(Рк, Qk)• Тогда на (к + 1) -м шаге решается минимаксная задача 0 где

J&k — inf JAk(P,Q), (0.6) Ja^Q) - 4) - max-щ-^-,

Л — фиксированное число, одно и то же на каждом шаге. Если <7дк ^ О, то в качестве Рк+и Qk+i берется решение задачи (0.6), при этом Afc+i = A(Pk+i,Qk+i). Если JAk = 0, то считаем Рм = Рк, Qk+i = Qk, Д&+1 = А*. При практической реализации алгоритма условие JAk = 0 означает необходимость останова. Ранее рассматривались только случаи Л = 0 и А = 1.

Определение 1. Множество Т С Q^ будем называть допустимым, если множество

T+ = {QeT: Q{x) > 0} ограничено и замкнуто на D и выполнено следующее

Условие А. Для любой функции / существует такая последовательность дробей Ri = PijQu Pi е V{n), Qi E T, Qi(x) >0 Vx e D, что

A (Ri) А* при I oo.

Если T+ С является поглощающим множеством, то задачи (0.2) и (0.5) эквивалентны.

Определение 2. Множество полиномов Q £ Т+ таких, что vQ ^ Т при любом v > 1, будем называть границей Т+ и обозначать через Т+.

Заметим, что условие А будет выполняться, если в задаче (0.2) для любой / существует наилучшая рациональная дробь R* = Р*/Q* такая, что Q* 6 Т+ и Q*(x) >0 Уж 6 D. Однако в алгоритме существование наилучшей дроби для функции /, вообще говоря, не требуется.

Решение задачи (0.6) является существенной частью алгоритма. Во втором параграфе рассматривается несколько более общая, чем (0.6), минимаксная задача:

JA= inf Ja(P,Q), (0.7)

РеЯп>, QeT где т>п\ 1 ipm .l/WQW-PW l-AQW MP, Q) = Ja,q(p* Q) = -Щх)-•

A > 0 — произвольное фиксированное число, Q{x) — некоторая функция, 0 < Q{x) < оо для любого х 6 D. Исследуется зависимость решения задачи (0.7) от величины параметра А, когда А > А* или А < А*.

Доказана следующая теорема:

Теорема 1. Пусть Т — допустимое множество. Если А > А*, то задача (0.7) всегда имеет решение и 7д < 0. Если 0 < А < A*, Q(x) = 0 принадлежит Т, то пара Р, Q : Р = Q = 0 является решением задачи (0.7) и J& = 0.

В частном случае, когда Q = 1, < 1 (г = 1,., n), \qj\ < 1 (j = 1,., m), условие A < А* рассматривалось также в работе Белых В.М. [6], где показано, что если в задаче линейного программирования, соответствующей задаче (0.7), имеется решение вида J а = 0, Р = Q = 0 или 7д = 0, Q(xi) = 0 для некоторого Х{ 6 D, то А < А*.

Следствие 1. Если Т — допустимое множество, А > 0, то «Тд < 0 тогда и только тогда, когда А > А*.

В третьем параграфе устанавливается сходимость алгоритма и приводятся оценки скорости сходимости.

Отличия в доказательстве теоремы 2 от доказательства соответствующей теоремы сходимости [42] связаны с тем, что рассматривается не только случай Л = 1, но и случай, когда Л € [0,1). При этом дополнительно рассмотрен случай А^ = А*.

Теорема 2. Пусть Т - допустимое множество, 0 < Л < 1. Тогда Ajfc A*, к —> оо. Равенство А к = А* (Rk = R*) выполняется тогда и только тогда, когда J&k = 0.

Следствие 2. Пусть для функции f(x) в множестве Ип,т существует наилучшая рациональная дробь R*(x) = P*(x)/Q*(x) и пусть О < А < 1, Т — допустимое множество. Тогда

Afe+i — Д* < С (Afc — А*), где константа С < 1 и может быть записана в виде с = С1 " лр ) для 0 < Л ^

I (1 - для А = О, rf = minQ*(x), % = minQfc(a;), М = max maxQ(ж). x€D xEL) QEl+ x£JJ

Формулируемые далее теоремы 3 и 4 приведены для случая алгебраических дробей.

Будем использовать обозначение V^ в принятом для алгебраического случая смысле: множество многочленов степени, не превосходящей п, т.е.

7><Л> = {Р(аО : Р(х) = Ejhx*}, Q(m) = {Q(x) : Q(x) = £ цх*} (0.8) i=0 j=0 и определяется, как в (0.1) с учетом условия (0.8). Заметим, что в связи с таким пониманием пит прежнее ограничение для N перепишется соответственно в виде N > п + т + 1.

Приведем здесь определение нормальной наилучшей дроби и известную теорему о сильной единственности [49].

Определение. Наилучшую дробь R* = P*/Q* называют нормальной, если она принадлежит пространству 7£n,m \ Ип-1,т-и т.е. она несократима и старшие коэффициенты числителя и знаменателя не равны нулю одновременно.

Теорема [о сильной единственности]. Если X - ограниченное множество точек и R* Е 7Zn,m - нормальная наилучшая дробь для функции f, то для всех R 6 выполняется неравенство A (R) — A(R*) > 7||R — Д*||, где 7 > 0 не зависит от R.

Здесь и далее ||<7(я)|| = тахх€£> |р(ж)| (в качестве X у нас D ).

Введем следующее

Определение 3. Пусть R = P/Q € 7£n,m и Q € Т+. Будем говорить, что R обладает свойством L на Т, если для всех R = P/Q € Ип,т таких, что Q £ Т+, имеет место неравенство

HQ-QH < e\\R-R\\, где в < оо не зависит от R.

При доказательстве теоремы 3 используется схема доказательства из [42], однако оценки существенно изменены и приведены к виду, удобному для приложений.

Теорема 3. Пусть Л = 1, Т — допустимое множество. Если R* Е 7Zn>m — нормальная наилучшая дробь для функции /, обладающая свойством L на Т, то

A k+1-A*<c(Ak-A*)\ (0.9) где с > 0 — некоторая константа, не зависящая от к.

Теорема 4 обобщает следующий результат из работы [42]: если для функции / наилучшая рациональная дробь R* G Ип,т является нормальной и коэффициенты знаменателя этой дроби удовлетворяют условию max \qj\ = 1, j = l, .,m, (0.10) то для всех R = P/Q 6 коэффициенты знаменателей которых удовлетворяют тому же условию, имеет место неравенство

WQ-Ql <6\\R-R*l где 0 < оо не зависит от R.

При доказательстве теоремы 4 мы используем некоторые идеи доказательства из работы [53].

Теорема 4. Если множество Т+ замкнуто и ограничено, R* = P*/Q* е к п,т ~ нормальная наилучшая дробь для функции /, Q* £ Т+, то существует константа в < оо такая, что для любых Q Е Т+ и Р £ V^ выполняется неравенство

Чг ~ Я*

Q-Q*\\ < М min и ^ II — 0<г<ш

Qi 0||Д-Д*||, где М = тахдетч- ||Q(x)||.

В четвертом параграфе приводятся конкретные множества Т, определяемые меньшим числом неравенств, чем у других авторов. Ранее рассматривались множества Т\ — Тз, определяемые соответственно ограничениями (0.4), \qj\ <1 (j = 1,., га) и (0.10). Для них доказана сходимость, в том числе и в случае обобщенных рациональных дробей [49]. Введенные нами множества в случае алгебраических дробей имеют вид: т4 = {Q е Q<m> : Q(Xi) < Mi, Va* € У], где У С D, Mi = M{xi) — некоторые положительные числа. ш

Tb = {Q= Е qjXJ : qj < 1, j = 0,1,. ,m}, j=0 771

T7 = {Q = £ qjX3 : g2fe<l, fc = 0,1,., [m/2]}; j=o обозначение [а] здесь и далее означает целую часть числа а ).

Доказаны следующие теоремы, устанавливающие допустимость множеств Т4 — Т7, а также соответствующую сходимость Ак к А* (к —> оо).

Теорема 5. Пусть D С R — конечное множество точек N, где N > п+га+1, 1 = 2 . Множество Т4 допустимо, если мноэюеcmeo У С D содержит не менее (т + 1) -и различной точки; множество Т5 допустимо, если среди точек множества D имеется хотя бы одна точка х > 0; множество Tq допустимо, если имеется среди точек D хотя бы одна точка х < 0; множество Tj допустимо в следующих случаях: a) D — непустое симметричное относительно нуля множество, б) D содержит симметричное относительно нуля подмножество D, состоящее не менее, чем из 1 +1 точки, в) D таково, что найдется 2(1 — 1) непересекающихся попарно симметричных относительно нуля интервалов, каждый из которых содержит хотя бы одну точку из множества D (ш >1).

Следствие 3. Если 0<А<1, DC R — конечное множество, содержащее не менее п+тп+1 точки, и для множества Т{ выполняются соответствующие условия теоремы 5, то при Т = Tj, г = 4,5, б, 7, алгоритм сходится.

Теорема 6. Пусть D С R — конечное множество, содержащее не менее п + тп + 1 точки, Т = Т{ (г = 4,5,6,7) — допустимое множество, А = 1, Ип,тп — множество алгебраических рациональных дробей. Если наилучшая для функции f дробь R* £ 7£П)ТО является нормальной, то скорость сходимости алгоритма по крайней мере квадратичная, т.е. верна оценка (0.9).

В дополнение к ранее известным случаям, когда знаменатели обобщенных рациональных дробей принадлежат множествам Т\ — Тз, приведем множество Т5 = {Q(x) = E™=i qji}>j(x) : qj < 1, j = 1,., m}, аналог множества T5, для которого также доказана сходимость.

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

Основным элементом итерационного алгоритма для задач наилучшего равномерного приближения является решение на каждом шаге следующей минимаксной задачи min/i f(xi)Q(xi) - Р(х{)\ - AkQ(xi) 1Л, i = 1,., N,

Qk(xi) при ограничении Q E T, сводящейся к некоторой задаче линейного программирования. Для решения этой задачи используется симплекс-метод с учетом специфики задач наилучшего равномерного приближения. Цель, которую мы ставили при разработке обоих алгоритмов, состояла в построении вычислительных схем симплекс-метода, в которых использовались бы специфические черты, присущие задачам чебышевского приближения.

Специфической чертой для таких задач является наличие симметрии в соответствующих парах ограничений задачи линейного программирования. Для случая приближения дробями, в отличие от линейного случая, у пар ограничений rji, rj-i имеется симметрия только относительно части переменных, а именно, относительно переменных pj, j = 1,., n, и нет симметрии относительно переменных qj, j = 1,., m).

В первом алгоритме решается задача минимизации с односторонними ограничениями на коэффициенты знаменателя: min— ц (0-11) при ограничениях

Щ = Е VijPj + (Д* - f(xi)) Е фцЯ.j ~ vQh{xi) > 0,

3=1 3=1

V-i = ~ Е VijPj + (Afe + f(xi)) E ipijqj - vQk{xi) > 0,

3=1 3=1 i = 1,., iV,

-Qj + 1 > 0, j = 1,., m, где ipij = <Pj(xi), ipij = ipj(xi), fx = -jz > 0.

0.12)

Предлагается специальный способ исключения свободных переменных р3, s = 1 и qj, j = 1 в задаче (0.11)—(0.12), позволяющий сохранить неотрицательность элементов столбца свободных членов в (0.12) и, тем самым, избежать в симплекс-методе этапа поиска опорного решения. Используя особенности матрицы ограничений и симметрию коэффициентов р8, s = 1,., п, в парах основных ограничений в процессе их исключения преобразуется не вся матрица ограничений, а некоторая вспомогательная матрица меньшего размера, при этом размеры матрицы еще уменьшаются, если набор базисных функций числителя совпадает с первыми п базисными функциями знаменателя и наоборот. В последнем случае выведены формулы, позволяющие, используя элементы вспомогательной матрицы, получившиеся в результате исключения р8, s = 1,.,п, вычислять измененные значения всей матрицы. Эти формулы можно использовать в начале каждой итерации, считая, что переменные р3, s = 1,., п, исключены через те же ограничения, что на первом шаге, и можно начинать итерацию сразу с исключения qj, j = 1,., т. В алгоритме не предполагается заранее линейная независимость на D систем функций {<pj}j=l, и {il)j}™=l. Возможная линейная зависимость функций отслеживается на стадии исключения свободных переменных. Выявленные линейно-зависимые функции выбрасываются из рассмотрения. Кроме того, имеется возможность после первой итерации решать задачу (0.11)—(0.12) на подмножестве D1 точек х 6 D, для которых - > 7тах|/(у) - Д*(у)|, к > 1,

V&D где коэффициент 7, удовлетворяющий неравенству 0 < 7 < 1, изменяется по некоторому правилу. Отметим, что А.И. Роженко [36] разработан вычислительный алгоритм, в котором используется на каждой итерации подсетка и при этом соответствующая задача линейного программирования решается до тех пор, пока не возрастет максимум модуля уклонения на всем множестве.

Во втором алгоритме используется двойственная к исходной задача. Отметим, что в отличие от предшествующего случая, предполагается, что \qj\ < 1, j = l,.,m. С учетом специфики задач равномерного приближения предлагается способ конструктивного построения начального базисного множества, при котором за п+1 шаг жордановых исключений в двойственной задаче получается допустимое базисное решение. Этот способ является обобщением используемого B.JI. Александренко [1] приема построения базисного множества в полиномиальной задаче.

Так же, как в алгоритме B.JI. Александренко, можно вместо использования двумерного массива размера (n + т + 2) х (2N + 2т + 1), определяемого матрицей ограничений и строкой коэффициентов целевой функции рассматриваемой задачи, использовать массив размера (га + т 2) х (N + т + 1), определяемый матрицей, соответствующей первым N основным ограничениям щ (г = 1,., N) исходной задачи и первым т ограничениям на коэффициенты знаменателя. Информация, которая явно не присутствует в используемом массиве, но которая должна участвовать в процессе построения решения задачи, всегда может быть восстановлена в случае необходимости из соотношений, связывающих в исходной задаче соответствующие ограничения щ и rj-i (аналогично для ограничений на коэффициенты знаменателя).

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

Пусть D — произвольное множество из Rz, состоящее из N точек, n, m — натуральные числа, N > п-\-т+1. На множестве D определены функция /(х), весовая положительная функция w(x) и две линейно-независимые системы функций <pi(x),., ipn(x) и ф^х),., фт(х).

Множество Ип,т рациональных дробей определяется как в (0.1).

Задача наилучшего среднеквадратического с весом w(x) > 0 приближения функции f(x) рациональными дробями из класса 7состоит в отыскании дроби R*(x) = R(z*,x) £ 7£П)ТО, на которой реализуется равенство

N N 2

Р* = Е *Ф;)[/(х;) ~ = Jgf Е wC^OLffe) - **)] 1 где z = (zi, z2,., zm,., 2TO+n), ZjG R (i = 1,., m + n). Решение этой задачи существует не всегда (см., напр., [69], [70]).

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

Пусть zk = (zk,., zk+mx)T — вектор коэффициентов (без коэффициента при фх, он фиксирован и равен 1) некоторой дроби Rk = R(zk, х) £ 7ZntTTl, полученный на к -м шаге алгоритма. На (к + 1) -м шаге решается задача mm \\W (JkAz + ек)\\2р + 7* £?Li v^Az]+l Qk{zk + XAz, Xi)> 0, i = 1,., N, k = 1,2,., m = n + m - 1, где AzT = (Azx,Azm), = (e{,., e{ = et(zk) = R(zk, xt) -/(zj), i = 1,.,JV, W — диагональная матрица размера N X N с элементами wu = \]w(xi) >0, Jk = xi) J матрица размера

N x га, г = 1,., N, j = 1,., ra, Vjj = 1, j = 1,., га, или в качестве Vjj можно взять соответствующие диагональные элементы матрицы J%WJk, 7jt > 0 — некоторое действительное число. Если для полученного вектора-поправки Az значение полинома AQ(x) хотя бы в одной точке AQ(xi) < 0, то добиваемся положительности знаменателя за счет выбора параметра \ = \к по формуле

ЛЛ = min{ \Qk{xi)/AQ(xi)\ : Qk{xi)/AQ{xi) < 0} i и дальнейшего уточнения коэффициента при Az по правилу: находим номер j* такой, что в точке zk -f Ajt(l/2)J*Az достигается минимум min p(zk + \k(h3Az). o<j<Kx 2

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

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

Задача оперативного вычисления координат точки падения центра масс исходит от В.Д. Батухтина и JT.A. Майбороды. Разработка моделей движения центра масс с учетом различных возмущающих факторов и программ, реализующих решение соответствующих систем дифференциальных уравненией, описывающих движение материальной точки, осуществлялась А.Н. Ходаковским (ИММ) и сотрудниками ВИКИ им. А.Ф. Можайского. Разработка методики аппроксимации, ее реализация и построение моделей для вычисления точки падения из любой начальной точки рассматриваемой области осуществлялась В.П. Кондратьевым, JI.B. Петрак под руководством и при непосредственном участии В.И. Бердышева. В частности, J1.B. Петрак построены все дробно-рациональные модели. При их построении использовались разработанные автором программы наилучшего равномерного и среднеквадратиче-ского приближения функций многих переменных. В параграфе приводится общее описание задачи, постановка задачи аппроксимации, описание методики, приводятся построенные дробно-рациональные модели и величины, характеризующие точность моделей.

В качестве иллюстрации приведем вид рациональной дроби, используемой для приближения конкретной функции шести переменных F(A, Я, А, ip, в, v). Для решения задачи аппроксимации в области изменения переменных

D = {x = {\,H,A,<p,e,v)} этой функции была выбрана прямоугольная сетка т = {х8 = (\8, H3,A3,<ps,63,vs)} так, чтобы сеточная функция отражала особенности поведения реальной функции. Общий размер сетки т, на которой требовалось построить аппроксимацию определялся общим числом точек

N = N\x Nh xNa xN,pxNexNv = 7x4x 20 x5x 16 x8 = 358400.

В результате проведенных исследований полученной сеточной функции было выявлено, что поведение функции F по переменным Я и Л носит простой - линейный характер, а для приближения по переменным А, </?, в, v использовались рациональные дроби (полиномы приемлемых степеней не давали достаточной точности). Полученная в результате расчетов рациональная дробь

R = R(A,<p,d,v) =

---\-ШП Е ФтИНЕ S akimOkvl+ (о 13)

0<i+fc+i<2 го*4 е е bkimekvl + cmi^u2 + ст2^2в + ст3(ру2в2}, 1=0 к=О где ЩА) = 1, Ф2(Л) = sin{A), Ф3(Л) = cos{A), Ф4(Л) = sin(2A), Ф5(А) = cos(2A), имеет в числителе 84 коэффициента, в знаменателе - 10.

Приближающая функция Р = Р( А, Я, л, = Д(А, W) + (Я~50)Д(Л, <р, в, «)+

А-60°)Я(А,<£>, и)

R, R — функции вида (0.13), знаменатель у дробей Д, R, Д общий) имеет 262 коэффициента. Для вычисления значения в точке требуется выполнить 3200 элементарных операций. При этом относительная погрешность в процентах составила 3.1% для максимального и 0.78% для среднеквадратического уклонения, что удовлетворяет точности, требуемой в данной задаче.

Исходной информацией для построения моделей служат данные, подготовленные в Одесском гидро-метеорологическом институте (ОГМИ), на основе данных "Аэроклиматического справочника северного полушария" и данных, накопленных в (ОГМИ) в результате теоретических и экспериментальных исследований по аэроклиматическому описанию различных регионов. Рассматриваются две характерики атмосферы: температура и скорость ветра. Приводится методика разработки моделей, отражающих характер исходных данных и содержащих возможно меньшее число коэффициентов, обеспечивающих необходимую точность аппроксимации. Приводятся построенные двумерные и трехмерные дробно-рациональные модели для среднестатистических значений температуры и скорости ветра. В качестве примера приведем приближающую рациональную дробь вида CLijkipi \>Нк \ гт\ 0<i+j+fc<4 г(У,А,Я)= Е - ,

0<i+j+k<2 взятую в качестве трехмерной модели температуры. Построенная приближающая дробь имеет 35 коэффициентов в числителе, 10 коэффициентов в знаменателе и дает среднеквадратическое уклонение

1 10 181 х/2 в пределах от 1.1 до 2.0° С в зависимости от месяца, что не превосходит среднеквадратические ошибки измерения, которые колеблются от 1° до 2° в слое 3-15 км. и от 2° до 5° в слое 30 км.

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

С помощью программы, в которой реализован алгоритм, описанный в § 1 второй главы, на основе рациональных дробей для функций Еп(х), 2 < п < 6, были получены формулы вида для функций Кп(х), 1 < п < 4, — формулы вида кп(х) «

Максимальная абсолютная погрешность всех формул на всем отрезке изменения аргумента [0, оо) не превышает для функции Еп(х) величины 3 • 106 (при х = 0), для функции Кп(х) - 1.3 • 10~5 (при х = 0). Относительная погрешность на исследованном отрезке х G [0,7], как правило, значительно меньше 0.01% для функции Еп и 0.005% для Кп. Использование этих формул при расчете лучистых потоков позволило без значимой потери точности существенно упростить процесс организации вычислений, что привело к экономии времени, затраченного на получение решения задачи. Отметим также, что полученные формулы имеют простой вид, их можно использовать для вычисления значений функций на всем интервале [0, оо), и, при том, формулы обеспечивают достаточно хорошую точность. Эти формулы могут использоваться в других задачах теплотехники, нейтронной физики, оптики атмосферы, астрофизики и других разделах науки. Очевидно, что с помощью программы можно получить аналогичные формулы и для других значений п.

Основные результаты диссертации состоят в следующем:

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

4. На основе исследований Мейера-Рота [63] и Осборна [66] метода Марк-вардта-Левенберга [61], [62] для нелинейных аппроксимирующих функций общего вида разработан численный алгоритм среднеквадратическо-го приближения функций рациональными дробями, учитывающий специфику приближения рациональными функциями.

Основные результаты автора по теме диссертации опубликованы в работах: [26]—[32], [16], [22]. В [16] автором выполнены все расчеты. В [22] ему принадлежит раздел, относящийся к дробно-рациональной аппроксимации. Результаты первой и третьей глав описаны также в монографии [8], где автором диссертации написаны параграф 9 главы I и параграфы 6 и 8 главы III.

Результаты диссертации докладывались на школе-конференции по теории аппроксимации и математической физике (Казань, 1984 г.), на Всесоюзной конференции по теории приближения функций (Ленинград, 1989 г.), на 3-й Всесоюзной конференции "Новые подходы к решению дифференциальных уравнений"(Дрогобыч, 1991 г.), на школе-конференции "Алгебра и анализ", посвященной 100-летию со дня рождения Б.М. Гагаева (Казань, 1997 г.), на совместных семинарах отдела теории приближения функций и отдела аппроксимации и приложений Института математики и механики УрО РАН (г. Екатеринбург), на семинаре кафедры вычислительной математики Уральского государственного университета (г. Екатеринбург).

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Петрак, Лариса Владимировна, Екатеринбург

1. Александренко B.J1. Алгоритм построения приближенного равномерно-наилучшего решения системы несовместных линейных уравнений // Алгоритмы и алгоритмические языки. М: ВЦ АН СССР, 1968. Вып. 3. С. 57-78.

2. Аппазов Р.Ф., Лавров С.С., Мишин В.П. Баллистика управляемых ракет дальнего действия. М.: Наука, 1966. 307 с.

3. Ахиезер Н.И. Лекции по теории аппроксимации. М.: Наука, 1965. 407 с.

4. Бахвалов Н.С. Численные методы. I. М.: Наука, 1973. 631 с.

5. Белоглазов И.Н., Джанжгава Г.И., Чигин Г.П. Основы навигации по геофизическим полям. М.: Наука. 1985.

6. Белых В.М. О решении вырожденных задач наилучшей дробно-рациональной аппроксимации // Вестн. Ленингр. ун-та. 1976. № 7. С.5-12.

7. Белых В.М. Решение задачи дробно-рациональной аппроксимации // Вопросы теории и элементы программного обеспечения минимаксных задач / Под ред. В.Ф. Демьянова, В.Н. Малоземова. Л.: Изд-во Ленингр. ун-та, 1977. С. 145-151.

8. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: Изд-во УрО РАН, 1999. 297 с.

9. Бердышев В.И., Субботин Ю.Н. Численные методы приближения функций. Свердловск: Ср.-Урал. кн. изд-во, 1979. 120 с.

10. Библиотека программ "ЛИДА-2"по аппроксимации функций и цифровой фильтрации (оперативно-информационный материал) / ВЦ СО АН СССР; Сост. В.А. Василенко, А.В. Ковалков, М.В. Зю-зин, А.И. Роженко, А.Ю. Бежаев, С.К. Махкамов. Новосибирск, 1983.

11. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977. 303 с.

12. Гаврилюк В.Т. Обобщение первого полиномиального алгоритма Е.Я. Ремеза для задач построения дробно-рациональных чебышев-ских приближений // Укр. мат. журн. 1964. Т.16, № 5. С.575-585.

13. Гасс С. Линейное программирование (методы и приложения). М.: Изд-во физ.-мат. литературы, 1961. 304 с.

14. Детков С.П., Виноградов А.В. Приближенные угловые коэффициенты для двумерных задач // Инж.-физ. журн. 1969. Т.16, № 3. С.499-503.

15. Детков С. П. Степени черноты объемов и угловые коэффициенты в системах с реальной средой // Инж.-физ. журн. 1971. Т.21, № 2. С.205-212.

16. Детков С.П., Пономарев Н.Н., Петрак JI.B. Рационализация расчетов лучистых потоков в простейших системах тел // Инж.-физ. журн. 1977. Т.ЗЗ, № 2. С.356.

17. Детков С.П., Пономарев Н.Н., Петрак JI.B. Рационализация расчетов лучистых потоков в простейших системах тел. Минск, 1977. 9 с. Деп. в ВИНИТИ, № 784-77 Деп.

18. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988. 440 с.

19. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. М.: Наука, 1967. 460 с.

20. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 191 с.

21. Каленчук-Порханова А.А. Алгоритмы и анализ погрешностей наилучшей чебышевской аппроксимации функции одной переменной // Теория приближения функций. М.: Наука, 1977. С.213-218.

22. Кондратьев В.П., Пацко H.JL, Петрак Л.В. Комплекс программ аппроксимации // Структура и организация пакетов прикладных программ: (Материалы по мат. обеспечению ЭВМ). Свердловск: УНЦ АН СССР, 1983. С.116-131.

23. Коллатц Л., Крабе В. Теория приближений. Чебышевские приближения и их приложения / Пер. с нем. Б.И. Голубова под ред. С.Б. Стечкина. М.: Наука. 1978. 272 с.

24. Лаусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986. 231 с.

25. Муртаф Б. Современное линейное программирование. М.: Мир, 1984. 224 с.

26. Петрак Л.В. Приближение функций одного переменного рациональными дробями // Тр. ИММ УНЦ АН СССР. 1975. Вып. 6: Программы оптимизации (приближение функций). С.110-129.

27. Петрак Л.В. Приближение функций многих переменных рациональными дробями // Тр. ИММ УНЦ АН СССР. 1975. Вып. 6: Программы оптимизации (приближение функций). С. 130-144.

28. Петрак Л.В. Об одном методе решения задачи наилучшей рациональной аппроксимации // Журн. вычисл. математики и мат. физики. 1978. Т. 18, № 4. С.860-869.

29. Петрак Л.В. Рациональная аппроксимация функций обобщенным методом Чини-Лоэба // Алгоритмы и программы приближения функций: (Материалы по мат. обеспечению ЭВМ). 1981. С.82-98.

30. Петрак Л.В. Среднеквадратичное приближение функций многих переменных обобщенными рациональными дробями // Алгоритмы приближения функций: (Материалы по мат. обеспечению ЭВМ). 1987. С.89-106.

31. Петрак JI.B. Об одном алгоритме среднеквадратичной рациональной аппроксимации // Тез. докл. 3 Всесоюз. конф. "Новые подходы к решению дифференц. уравнений"(Дрогобыч, 17-21 июня 1991 г.). М.: ВЦ АН СССР, 1991. С. 104.

32. Петрак Л.В. Об алгоритмах наилучшей рациональной аппроксимации // Тез. докл. шк.-конф. "Алгебра и анализ", посвященной 100-летию со дня рождения Б.М. Гагаева. Казань, 1997. С. 170-171.

33. Порханова А.А. Чебышевская аппроксимация дробно-рациональными выражениями // Вычисл. математика в соврем, науч.-техн. прогрессе. Киев: Знание, 1974. С.300-308.

34. Ремез Е.Я. К вопросу построения чебышевских приближений дробно-рационального и некоторых других типов // Укр. мат. журн. 1963. Т.15, № 4. С.400-411.

35. Ремез E.5L Основы численных методов чебышевского приближения. Киев: Наук, думка, 1969. 624 с.

36. Роженко А.И. Реализация некоторых алгоритмов теории приближения функций: Отчет / ВЦ СО АН СССР. Новосибирск, 1982.

37. Рубинштейн Г.1П. О равномерном приближении непрерывной функции с помощью рациональных дробей // Успехи мат. наук. 1960. Т.14, вып. 3. С.232-234.

38. Справочник по специальным функциям с формулами, графиками и математическими таблицами / Под ред. М. Абрамовица и И. Сти-ган; Пер. с англ. под ред. В.А. Диткина и JI. Н Кармазиной. М.: Наука, 1979. 830 с.

39. Стренг. Линейная алгебра и ее применения: Пер. с англ. М.: Мир, 1980. 456 с.

40. Химмельблау Д. Прикладное нелинейное программирование: Пер. с англ. М.: Мир, 1975. 534 с.

41. Хорн Р., Джонсон Ч. Матричный анализ: Пер. с англ. М.: Мир, 1989. 655 с.

42. Barrodale I., Powell M.J.D., Roberts F.D.K. The differential correction algorithm for rational -approximation // SIAM J. Numer. Anal. 1972. V.9, № 3. P.493-504.

43. Barrodale I. Best rational approximation and strict quasi-convexity // SIAM J. Numer. Anal. 1973. V.10, № 1. P.8-12.

44. Belogus D., Liron N. DCR2: An Improved Algorithm for /<» Rational Approximation on Intervals // Numer. Math. 1978. V.31, № 1. P.17-29.

45. Cheney E.W., Loeb H.L. Two new algorithms for rational approximation // Numer. Math. 1961. V.3, № 1. P.72-75.

46. Cheney E.W., Loeb H.L. On rational Chebyshev approximation // Numer. Math. 1962. V.4, № 2. P.124-127.

47. Cheney E.W., Southard Т.Н. A survey of methods for rational approximation // SIAM. Rev. 1963. V.5, № 3. P.219-231.

48. Cheney E.W. Introduction to approximation theory. New York: McGraw-Hill, 1966. 259 p.

49. Cody W.J., Stoer J. Rational Chebeshev approximation using interpolation // Numer. Math. 1966. V.9, № 3. P.177-188.

50. Cody W.J. A survey of practical rational and polynomial approximation of functions // SIAM. Rev. 1970. V.12, № 3. P.400-423.

51. Curtis A., Osborne M.R. The construction of Minimax Rational Approximation // Comput. J. 1966. V.9, № 3. P.286-293.

52. Dua S.N., Loeb H.L. Further remarks on the differential correction algorithm // SIAM J. Numer. Analysis. 1973. V.10, № 1. P.123-126.

53. Eraser W., Hart J.F. On the computation of rational approximations to continuous functions // Communs. ACM. 1962. V.5, № 7. P.401-403.

54. Hastings C., Hayward J.T., Wong J.P. Approximations for digital computers. Princeton (NJ): Princeton Univ. Press, 1955. 201 p.

55. Kaufman E.H., Taylor G.D. Uniform rational approximation of functions of several variables // Intern. J. Numer. Math. Eng. 1975. V.9, № 2. P.297-323.

56. Kaufman E.H., Leeming Jr.D.J., Taylor G.D. A combined Remes-differential correction algorithm for rational approximation // Math. Comput. 1978. V.32, № 141. P.233-242.

57. Kaufman E.H., Leeming Jr.D.J., Taylor G.D. A combined Remes-differential correction algorithm for rational approximation: experimental results // Comput. Maths. Appls. 1980. V.6, № 2. P.155-160.

58. Lee C.M., Roberts F.D.K. A comparison of algorithms for rational loo -approximation // Math. Comput. 1973. V.27, № 121. P.lll-121.

59. Loeb H.L. Algoriths for Chebyshev approximations using the ratio of linear forms // SIAM J. 1960. V.8, № 3. P.458-465.

60. Levenberg E. A method for the solution of certain non-linear problems in least squares // Quart. Appl. Math. 1944. V.2, № 1. P.164-168.

61. Marquardt D.W. An algorithm for least squares estimation of nonlinear parameters // J. Soc. Industr. Appl. Math. 1963. V.ll, № 2. P.431-441.

62. Meyer R.R., Roth P.M. Modified dampted least squares: an algorithm for non-linear estimation j j J. Inst. Math, and Appl. 1972. V.9, № 2. P.218-233.

63. Morison D.D. Methods for nonlinear least squares problems and convergence proofs // JPL Seminar Proc. 1960. 9 p.

64. Ralston A. Rational Chebyshev approximation by Remes' algorithms // Numer. Math. 1965. Bd.7, H. 4. S.322-330.

65. Osborne M.R. Nonlinear least squares The Levenberg algorithm revised // J. Austral. Math. Soc. Ser. B. 1976. V.19. P.343-357.

66. Werner H Die Bedeutung der Normalitat bei rationaler Tschebyscheff-Approximation // Computing. 1967. V.2, № 1. P.34-52.

67. Werner H., Stoer J., Bommas W. Rational Chebyshev approximation // Numer. Math. 1967. V.10, № 4. P.289-306.

68. Wolf J.M. Discrete rational Lp approximation // Math. Comput. 1975. V.29, № 130. P.540-548.

69. Wolf J.M. Convergence of discrete rational approximations // J. Appo-xim. Theory. 1979. V.27, № 3. P.271-277.