Интерполяционный многочлен Ньютона

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

Если задачу поставить так, что добавление лишней точки требовало бы лишь добавки некоторого многочлена степени (n+1) к многочлену Лагранжа n-й степени, то эту добавку можно искать, выполнив в общем виде преобразование разности двух многочленов Лагранжа: степени (n+1) и n. Несложные преобразования приводят к следующему соотношению для добавочного многочлена степени (n+1):

,

где – многочлен степени (n+1),

– разделенная разность (n+1)-го порядка.

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

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

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

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

5Приближение и интерполирование функций,

Приближение функций — нахождение для данной

функции f функции g из некоторого определённого класса (например, среди алгебраических многочленов заданной степени), в том или ином смысле близкой к f, дающей её приближённое представление. Существует много разных вариантов задачи о приближении функций в зависимости от того, какие функции используются для приближения, как ищется приближающая функция g, как понимается близость функций f и g. Интерполирование функций — частный случай задачи приближения, когда требуется, чтобы в определённых точках (узлах интерполирования) совпадали значения функции f и приближающей её функции g, а в более общем случае — и значения некоторых их производных.

Для оценки близости исходной функции f и приближающей её функции g используются в зависимости от рассматриваемой задачи метрики различных функциональных пространств. Обычно это метрики пространств непрерывных функций С и функций, интегрируемых с р-й степенью, L_p, р ³1, в которых расстояние между функциями f и g определяется (для функций, заданных на отрезке [а, b]) по формулам

и

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

a_kj_k (x),

где (j₁,..., j_n—заданные функции, a a₁,..., a_n — произвольные числа. Обычно это алгебраические многочлены

a_kx_k

или тригонометрические полиномы

а₀ + (a_k coskx + b_k sinkx).

Рассматриваются также полиномы по ортогональным многочленам, по собственным функциям краевых задач и т.п. Другим классическим средством приближения являются рациональные дроби P (x)/Q (x), где в качестве Р и Q берутся алгебраические многочлены заданной степени.

В последнее время (60—70-е гг. 20 в.) значительное развитие получило приближение т. н. сплайн-функциями (сплайнами). Характерным их примером являются кубические сплайн-функции, определяемые следующим образом. Отрезок [a, b] разбивается точками a = x₀ < x₁ <... < x_n = b, на каждом отрезке [x_k, x_k+1] кубическая сплайн-функция является алгебраическим многочленом третьей степени, причём эти многочлены подобраны так, что на всём отрезке [а, b] непрерывны сама сплайн-функция и её первая и вторая производные. Оставшиеся свободными параметры могут быть использованы, например, для того чтобы сплайн-функция интерполировала в узлах x_k приближаемую функцию. Улучшение приближения достигается за счёт увеличения числа узлов x_k правильного их расположения на отрезке [а, b]. Сплайн-функции оказались удобными в вычислительной математике, с их помощью удалось решить также некоторые задачи теории функций.

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

Теория приближений функций берёт начало от работ П. Л. Чебышева. Он ввёл одно из основных понятий теории — понятие наилучшего приближения функции полиномами и получил ряд результатов о наилучших приближениях. Наилучшим приближением непрерывной функции f (x)полиномами a_kj_k (x) в метрике С называется величина

E_n = min || f - a_kj_k (x)||_c,

где минимум берётся по всем числам а₁,..., a_n. Полином, для которого достигается этот минимум, называется полиномом наилучшего приближения (для других метрик определения аналогичны). Чебышев установил, что наилучшее приближение функции xⁿ⁺¹ на отрезке [—1, 1] в метрике С алгебраическими многочленами степени n равно 1/2ⁿ, а многочлен наилучшего приближения таков, что для него

xⁿ⁺¹ - = (1/2ⁿ) cos (n + 1) arccosx.

Следующая теорема Чебышева указывает характеристическое свойство полиномов наилучшего приближения в пространстве непрерывных функций: алгебраический многочлен , в том и только в том случае является многочленом наилучшего приближения непрерывной функции f в метрике С [—1, 1], если существуют n + 2 точки -1 £ x₁ < x₂ <... < x_n+2 £ 1, в которых разность f (x) — 2 принимает максимальное значение своего модуля с последовательно чередующимися знаками.

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

С начала 20 в. началось систематическое исследование поведения при n ® ¥ последовательности E_n — наилучших приближений функции f алгебраическими (или тригонометрическими) многочленами. С одной стороны, выясняется скорость стремления к нулю величин E_n в зависимости от свойств функции (т. н. прямые теоремы теории приближений), а с другой — изучаются свойства функции по последовательности её наилучших приближений (обратные теоремы теории приближений). В ряде важных случаев здесь получена полная характеристика свойств функций. Приведём две такие теоремы.

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

E_n £ Aq ⁿ,

где q < 1 и А — некоторые положительные числа, не зависящие от n (теорема С. Н. Бернштейна).

Для того чтобы функция f периода 2p имела производную порядка r, r = 0, 1,2,..., удовлетворяющую условию

|f ^(r)(x + h) - f ^(r)(x)| £ M|h|^a,

0 < a < 1, М — некоторое положительное число, или условию

|f ^(r)(x + h) - 2f ^(r)(x) + f ^(r)(x - h)| £ M|h|^a

(в этом случае a = 1), необходимо и достаточно, чтобы для наилучших приближений функции f тригонометрическими полиномами была справедлива оценка

Е_п £ А/n ^r+a,

где А — некоторое положительное число, не зависящее от n. В этом утверждении прямая теорема была в основном получена Д. Джексоном (США), а обратная является результатом исследований С. Н. Бернштейна, Ш. Ж. Ла Валле Пуссена и А. Зигмунда (США). Характеристика подобных классов функций, заданных на отрезке, в терминах наилучших приближении алгебраическими многочленами оказалась невозможной. Её удалось получить, привлекая к рассмотрению приближение функций с улучшением порядка приближения вблизи концов отрезка.

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

Для приближений в метрике L₂ полином наилучшего приближения может быть легко построен. Для других пространств нахождение полиномов наилучшего приближения является трудной задачей и её удаётся решить только вотдельных случаях. Это привело к разработке разного рода алгоритмов для приближённого нахождения полиномов наилучшего приближения.

Трудность нахождения полиномов наилучшего приближения отчасти объясняется тем, что оператор, сопоставляющий каждой функции её полином наилучшего приближения, не является линейным: полином наилучшего приближения для суммы f + g не обязательно равен сумме полиномов наилучшего приближения функций f и g.Поэтому возникла задача изучения (по возможности простых) линейных операторов, сопоставляющих каждой функции полином, дающий хорошее приближение. Например, для периодической функции f (x) можно брать частные суммы её ряда Фурье S_n (f, х). При этом справедлива оценка (теорема А. Лебега)

||f - S_n ||_c£ (L_n + 1) E_n ,

где L_n — числа, растущие при n ®¥ как (4/p²) lnn. Они получили название констант Лебега. Эта оценка показывает, что полиномы S_n доставляют приближение, не очень сильно отличающееся от наилучшего. Подобная оценка имеет место и для приближений интерполяционными тригонометрическими полиномами с равноотстоящими узлами интерполирования, а также для приближений интерполяционными алгебраическими многочленами на отрезке [-1, 1] с узлами , k =1, 2,..., n, т. е. в нулях полинома Чебышева cosn arccosx. Для основных встречающихся в анализе классов функций известны такие линейные операторы, построенные с помощью рядов Фурье или на основе интерполяционных полиномов, что значениями этих операторов являются полиномы, дающие на классе тот же порядок убывания приближений при n ® ¥, что и наилучшие приближения.

А. Н. Колмогоров начал изучение нового вопроса теории приближений — задачи о нахождении при фиксированном n такой системы функций j₁,..., j_n, для которой наилучшие приближения функций заданного класса полиномами были бы наименьшими (т. н. задача о поперечнике класса функций). В этом направлении в дальнейшем было выяснено, например, что для ряда важных классов периодических функций наилучшими в указанном смысле системами являются тригонометрические полиномы.

Теория приближений функций является одним из наиболее интенсивно разрабатываемых направлений в теории функций. Идеи и методы теории приближений являются отправной точкой исследования в ряде вопросов вычислительной математики. С 1968 в США издаётся специализированный журнал «Journal of Approximation Theory».