§ 6. Приближенное построение алгебраических многочленов наилучшего приближения

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

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

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

1. Предварительные замечания.

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

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

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

что

где При этом наилучшее приближение функции на

Точки (1), для которых выполняется условие (2), будем называть чебышевским альтернатом.

Справедлива также и следующая теорема (Балле —

Если и точки таковы, что

то

При фиксированных величина зависит от выбора комбинации удовлетворяющей условию (3). Верхнюю границу для при выборе всевозможных таких комбинаций обозначим через А. Если то А можно найти следующим образом. Рассматриваем разность Пусть

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

Рис. 29.

Если их число больше то наверняка имеет место неравенство так как в этом случае на найдутся точек для которых будет иметь место (3) и

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

Заметим без доказательства, что если где

то для длин интервалов существует положительная нижняя граница зависящая только от (а не от причем только при

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

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

Рассмотрим определители

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

Умножая (5) на и суммируя по от 1 до будем иметь:

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

где

Таким образом,

а

Из (5) и (9) следует, что

Если в (9) числитель и знаменатель разделить на

и ввести обозначение

то получим;

В частности, если имеют чередующиеся знаки, то

и

где

3. Пусть произвольные точки множества расположенные в порядке возрастания -Положим

Эта величина обладает тем свойством, что

2) существует система точек для которой

Эта система точек образует чебышевский альтернанс и, следовательно,

где многочлен наилучшего приближения к на

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

Пусть чебышевский альтернанс на По доказанному ранее (см. (10))

Так как множество состоит только из точек то они образуют чебышевский альтернанс по отношению к 5, а следовательно,

Далее,

Отсюда

и неравенство (16) доказано.

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

Пусть теперь есть множество точек для которых

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

Но Следовательно,

Но так как

то

Это означает, что есть многочлен наилучшего приближения к на 5 и в силу единственности многочлена наилучшего приближения

Но так как 5 состоит из различных точек, то

Это и доказывает, что множество есть альтернанс к на а поэтому имеет место и равенство (18) (см. (11)).

4. Предыдущие рассуждения позволяют с помощью конечного числа шагов построить многочлен наилучшего приближения к на множестве состоящем из конечного числа точек

Рассмотрим сначала случай

Располагая точки этого множества в порядке возрастания вычисляем используя равенства (15), (6), (8). Значение Зная знак определителя определяем знак разности с помощью равенства (18).

Далее, пишем систему равенств

где если если

Из этой системы равенств находим значения искомого многочлена в точках

Этими значениями многочлен полностью определяется. Найти его можно, строя интерполяционный многочлен по любым «4-1

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

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

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

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

Доказательство этой теоремы существенно опирается на лемму: Из всякой, последовательности многочленов ограниченных на одной и той же константой можно выбрать подпоследовательность, равномерно сходящуюся на к многочлену

Для доказательства леммы прежде всего докажем, что если

то существуют такие постоянные не зависящие от что

В самом деле, если положить то при

Отсюда

и неравенство (23) доказано. Для доказательства неравенства (22) возьмем на некоторые точки при Тогда по интерполяционной формуле Лагранжа

где многочлен степени обладающий свойством

Пусть Тогда

Отсюда

Полагая не зависит от получим неравенство (22).

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

Правая часть стремится к нулю при а это и означает, что равномерно на сходится к

Используя эту лемму, докажем сформулированную выше теорему. Из неравенства (21) и условия, что при следует существование такой постоянной К, что

ибо

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

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

но так как

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

Таким образом, подпоследовательность равномерно на сходится к

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