9. Алгоритмы аппроксимации рациональными дробями

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

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

Можно выделить два основных подхода к решению задачи наилучшего равномерного приближения функций рациональными дробями [106]. Первый подход основан на характеристической теореме П.Л. Чебышева и теореме Валле-Пуссена об оценке снизу величины наилучшего приближения. Второй подход основан на сведении исходной нелинейной задачи к последовательности задач линейного программирования. Алгоритмы, реализующие первый подход, предназначены для приближения функций одного независимого переменного. Наиболее эффективными среди алгоритмов этого типа являются аналоги полиномиального алгоритма Ремеза [118], [57], [82]. Эти алгоритмы отличаются быстродействием, но сходятся не от любого начального приближения. Второй подход связан с именами Чини, Лоеба и Рубинштейна [87], [61]. Среди алгоритмов, реализующих этот подход, исходным и наиболее эффективным является итерационный алгоритм Чини-Лоеба [87] и его аналоги [88], [78], [104] [11], [54], [60]. Эти алгоритмы сходятся при любом начальном приближении.

Описание обобщенного алгоритма Чини-Лоеба.

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

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

соответственно.

Определим множество рациональных дробей

Заметим, что требование постоянства знака у знаменателя на множестве точек определения является естественным. Обозначим

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

и дробь для которой

Общая схема построения сходящихся итерационных алгоритмов типа Чини-Лоэба для численного решения задачи (9.2) имеет следующий вид.

Пусть множество, обладающее свойством: для любого такое, что Это условие обеспечивает эквивалентность задачи (9.2) и задачи

В качестве начальной берется произвольная дробь которой Пусть на шаге получена дробь Тогда на шаге решается минимаксная задача

где

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

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

Существенной частью алгоритма является решение задачи (9.3). В связи с этим рассмотрим несколько более общую минимаксную задачу:

где

произвольное (в отличие от ) фиксированное число, некоторая функция, для любого

Введем два определения:

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

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

Условие А. Для любой функции существует такая последовательность дробей что

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

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

Рассмотрим зависимость решения задачи (9.5) от величины параметра когда или

Лемма 1. Пусть Тогда

3) если допустимое множество, то существуют такие что

4) если пара является решением задачи (9.5) и то

Похожие утверждения для конкретных множеств (см. п. 9.1.3) имеются в работах [88], [11].

Доказательство. Разобьем доказательство леммы на четыре части.

1. Имеем

2. Для любого имеем Отсюда, очевидно, следовательно,

3. Согласно условию А, существуют последовательности для любого такие, что

Если то для достаточно больших I имеем следовательно, в силу Пусть Покажем, что последовательность ограничена. Действительно, в силу (9.7) существует такое, что для любых отсюда где

и, следовательно, Так как последовательности принадлежат ограниченным и замкнутым и, следовательно, компактным множествам, то из можно выделить равномерно сходящиеся подпоследовательности

Учитывая (9.7), имеем

откуда

4. Пусть являются экстремальными, т.е. -Юсли то для некоторого будет и при этом

что противоречит экстремальности

Следствие 1. Если допустимое множество, то тогда и только тогда, когда

Теорема 1. Пусть допустимое множество. Если то задача (9.5) всегда имеет решение и Если принадлежит то пара являются решением задачи (9.5) и

Доказательство. Пусть Если и хотя бы в одной точке будет то если то Отсюда и из утверждения 3) леммы 1 следует, что при иычислении минимума в (9.5) можно ограничиться полиномами такими, что где достаточно большое число, т.е.

Пусть последовательности таковы, что Используя компактность множеств выделим сходящиеся подпоследовательности Тогда имеем для любого

Так как неравенство имеет место для всех то т. е. пара является решением задачи (9.9) и, следовательно, задачи 9.5).

Пусть Покажем, что в этом случае Предположим, что Тогда найдется пара такая, что и по свойству 2) леммы 1 будет что противоречит условию Таким образом, . С другой стороны, для имеем Следовательно,

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

В этом пункте предполагается, что произвольное допустимое множество, а множество содержит не менее точки.

Теорема 2. Пусть допустимое множество, Тогда Равенство выполняется тогда и только тогда, когда

Доказательство. Условия леммы 1 выполняются. Из (9.8) имеем можно считать, без ограничения общности, что Тогда для Докажем, что Предположим, что Тогда

а отсюда, очевидно, что противоречит утверждению 3) леммы 1. Значит, не возрастает и, следовательно, существует

Предположим, что . В силу условия А существуют

такие, что Так как то в каждой точке имеем

Отсюда, применяя (9.6) и учитывая, что получаем

где

Если то из (9.10) при к сразу получаем противоречие. Если то при любом из (9.10) и при сходимости разности к нулю имеем

для достаточно больших k. Используя это неравенство при где число точек множества неравенство (9.11) и очевидное неравенство получаем

откуда следует расходимость последовательности а это противоречит ограниченности множества Следовательно,

Вторая часть теоремы легко доказывается, если использовать следствие 1 и тот факт, что при любых k.

Далее будем предполагать, что в задаче (9.2) для функции в множестве существует наилучшая рациональная дробь

Следствие 2. Пдстпъ допустимое множество. Если наилучшая дробь для функции то

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

Оценка (9.12) легко следует из (9.10).

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

Будем предполагать, что пространство, натянутое на

является пространством Хаара размерности т.е. пространство имеет размерность и нет нетривиального элемента из него, имеющего более чем нулей в При этих предположениях легко можно доказать теорему о сильной единственности (см. гл. I, п. 7.2) и предшествующие ей леммы 1, 2 ([89], с. 164-166). Приведем формулировку леммы 1:

Лемма 2 (Чини, [89], с. 164). Пусть наилучшая дробь в для функции Если пространство Хаара, то единственный элементу? из удовлетворяющий неравенству для всех у из множества критических точек есть нулевой элемент.

Определение 3. Наилучшая дробь из класса называется нормальной, если пространство пространство Хаара (что эквивалентно включению

Лемма 3. Пусть множество ограничено и замкнуто, наилучшая дробь для является нормальной, Если равномерно на

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

имеем

где

Переходя к пределу, получим

откуда в силу леммы 2 будет при любых Так как нормальная дробь, то причем число по предположению. Это противоречит тому, что Значит, следовательно, равномерно на

Определение 4. Пусть Будем говорить, что обладает свойством на если для всех таких, что имеет место неравенство

где не зависит от

Теорема 3. Пусть в допустимое множество. Если нормальная наилучшая дробь для функции обладающая свойством на то

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

Доказательство. Используем схему доказательства теоремы 3 из [78], несколько изменив оценки для удобства использования на практике. Из свойства и теоремы о сильной единственности получаем оценку

где не зависит от k. Так как , то в каждой точке выполняется неравенство

Отсюда и из (9.6), учитывая, что для любой точки получаем неравенство

из которого, в силу того, что имеем

Пусть Из (9,14) следует, что

Действительно, пусть Тогда

откуда

Аналогично доказывается второе неравенство.

Оценим сомножители в правой части неравенства (9.15),

Функция возрастает при возрастании (константа следовательно,

Таким образом, для первого сомножителя имеем оценку

Оценим второй сомножитель. Для любой точки

Тогда

Так как функция возрастает при возрастании то

следовательно, имеем оценку

С помощью этих оценок неравенство (9.15) преобразуем к виду

Используя последнее неравенство и оценку снизу для из (9.16), получим оценку

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

Примеры допустимых множеств

Следующие множества, как легко проверить, допустимы:

Эти множества для алгебраических дробей со степенями, не превосходящими для числителя и для знаменателя, и рассмотрены впервые в [78],

Для алгебраических дробей множества:

где некоторые положительные числа,

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

Приведем формулировки из [54] теоремы, устанавливающей допустимость множеств и соответствующие для этих множеств теоремы сходимости.

Теорема 4. Пусть произвольное ограниченное множество, Множество допустимо, если содержит не менее различной точки; множество допустимо, если содержит хотя бы одну положительную точку; множество допустимо, если содержит хотя бы одну отрицательную точку; множество допустимо в следующих случаях: непустое симметричное относительно нуля множество, б) содержит симметричное относительно нуля подмножество состоящее не менее, чем из точки, в) таково, что найдется непересекающихся попарно симметричных относительно нуля интервалов, каждый из которых содержит хотя бы одну точку из множества

Следствие 3. Если конечное множество и для множества выполняются соответствующие условия теоремы 4, то при алгоритм сходится.

Теорема 5. Пусть конечное множество, содержащее не менее точки, допустимые множества, множество алгебраических рациональных дробей. Если наилучшая для функции дробь является нормальной, то скорость сходимости алгоритма по крайней мере квадратичная, т.е. верна оценка (9.13).