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

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

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

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

Разработкой алгоритмов для численного решения задачи наилучшего равномерного приближения рациональными дробями занимались многие авторы [б]-[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) иⁱ (x),., 1рт{х), каждая из которых линейно-независима на D. Обозначим V^ = {Р :

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

0.1).

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

Обозначим A® = 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 ® — A (R*) > 7||R — Д*||, где 7 > 0 не зависит от R.

Здесь и далее ||<7(я)|| = тахх&euro-£> |р (ж)| (в качестве 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* 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: Q (Xi) < Mi, Va* € У], где У С D, Mi = M{xi) — некоторые положительные числа. ш.

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

Te = W=E^: (c)fc+i>-l, fe = 0, l,.,[m/2]}l j=0 Tfl.

T7 = {Q =? qjX3: g2fe.

Доказаны следующие теоремы, устанавливающие допустимость множеств Т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 = 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 систем функций { 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) и две линейно-независимые системы функций.

Множество Ип, т рациональных дробей определяется как в (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* такой, что в точке zkf Ajt (l/2)J*Az достигается минимум min p (zk + k (h3Az). o.

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

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

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

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

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

D = {x = {, H, A,.

N = Nx Nh xNa xN, pxNexNv = 7x4x 20 x5x 16×8 = 358 400.

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

R = R (A,.

——ШП Е ФтИНЕ S akimOkvl+ (о 13).

0<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<4 г (У, А, Я)= Е — ,.

0<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, оо), и, при том, формулы обеспечивают достаточно хорошую точность. Эти формулы могут использоваться в других задачах теплотехники, нейтронной физики, оптики атмосферы, астрофизики и других разделах науки. Очевидно, что с помощью программы можно получить аналогичные формулы и для других значений п..

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

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

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

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

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

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

Основные результаты автора по теме диссертации опубликованы в работах: [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 rationalapproximation // 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 looapproximation // 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..