Приближение многочленами

Цель лекции: Рассмотреть основные методы аппроксимации числовых функций полиномами. Описать методы полиномиальной интерполяции функций.

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

Пусть на отрезке $$[a,b]$$ задана некоторая числовая функция $$f(x)$$. Разбиением отрезка $$[a,b]$$ называется конечное множество точек $$\{x_n\}_{n=0}^N$$ таких, что$$0=x_0<x_1<\dots<x_N=b.$$ Точки $$x_n$$ мы будем называть узловыми точками. Пусть также на ряду с разбиением отрезка нам дан набор чисел $$\{f_n\}_{n=0}^N$$, который имеет смысл значений функции в узловых точках $$f(x_n)=f_n,\quad n=0,\dots,N$$. Задача интерполяции состоит в том, чтобы найти значение функции $$f$$ в произвольной точке $$x\in[a,b]$$. Несколько реже возникает задача экстраполяции состоящей в том, чтобы найти значение функции $$f$$ в точке $$x\notin[a,b]$$. Мы будем в основном рассматривать задачу интерполяции.

Решение задачи интерполяции может быть представлено в виде функции (алгоритма)$$R(x,x_0,\dots,x_N,f_0,\dots,f_N):\Bbb{R}\times\Bbb{R}^{n+1}\times\Bbb{R}^{n+1}\to\Bbb{R}.$$ Однако чаще под решением задачи интерполяции понимают построение такой функции $$\tilde f_N(x)$$, которая определена на всем отрезке $$[a,b]$$. Эта функция называется интерполяционной.

Классическим методом построения интерполяционной функции является построение многочлена степени $$N$$$$P_N(x)=a_Nx^N+a_{N-1}x^{N-1}+\dots+a_1x+a_0$$ такого, что$$P_N(x_n)=f_n,\quad n=0,1,\dots,N.$$ Очевидно, что для определения этого многочлена необходимо и достаточно найти значения $$\{a_n\}_{n=0}^N$$.

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

Введем функции:$$p_N^i(x)=\frac{(x-x_0)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_N)} {(x_i-x_0)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_N)}.$$ Видно, что эти функции сами являются многочленами порядка $$N$$. Непосредственно из этой формулы мы имеем следующие соотношения$$p_N^i(x_j)=0,\quad j\neq i$$ и$$p_N^i(x_i)=1.$$ Тогда искомый интерполяционный многочлен может быть найден по формуле$$P_N(x)=\sum\limits_{i=0}^Np_N^i(x)f_i.$$

Можно убедиться также в том, что этот многочлен единственный. Действительно, для любого другого многочлена, для которого$$Q_N(x_i)=f_i,\quad i=0,\dots,N$$ мы имеем, что $$Q_N(x_i)=P_N(x_i),\quad i=0,\dots,N$$. Тогда многочлен $$L_N(x)=P_N(x)-Q_N(x)$$ имеет степень не большую, чем $$N$$, а также имеет $$N+1$$ корней. По основной теореме алгебры этот многочлен $$L_N(x)\equiv0$$.

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

Лагранжева форма интерполяционного многочлена является не единственной формой интерполяционного многочлена. Более удобной для практических расчетов является интерполяционный многочлен в форме Ньютона. Для заданного разбиения отрезка и значений функции в этих узлах введем понятие раздельной разности. Раздельной разностью первого порядка называется число$$f(x_0;x_1)=\frac{f(x_1)-f(x_0)}{x_1-x_0}.$$ Раздельная разность $$N$$ -го порядка определяется по рекуррентной формуле$$f(x_0;x_1;\dots;x_N)=\frac{f(x_1;x_1;\dots;x_N)-f(x_0;x_1;\dots;x_{N-1})}{x_N-x_0}.$$ Теперь мы можем определить интерполяционный многочлен в форме Ньютона по формуле$$Q_N(x)=f_0+f(x_0;x_1)(x-x_0)+\dots$$ $$+f(x_0;x_1;\dots;x_N)(x-x_0)(x-x_1)\dots(x-x_{N-1}).$$ Разумеется, интерполяционный многочлен в форме Ньютона совпадает с интерполяционным многочленом в форме Лагранжа.

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

Рассмотрим этот пример. Пусть функция$$f(x)=\frac{1}{1+25x^2},$$ заданная на $$[-1,1]$$. Это функция обладает почти всеми "хорошими" свойствами. Для каждого $$N$$ введем узловые точки по формуле$$x_i=-1+i\frac{2}{N},\quad i=0,1,\dots,N.$$ Через $$P_N(x)$$ введем интерполяционный многочлен, построенный по формуле 14.1. К.Рунге было показано, что для этого случая имеет место$$\lim\limits_{N\to\infty}\max\limits_{x\in[-1,1]}|f(x)-P_N(x)|=\infty.$$

Ключевые термины

Разбиение отрезка - конечное множество точек, принадлежащих заданному отрезку.

Узловые точки - элементы из множества разбиения отрезка.

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

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

Интерполяционная функция - функция, которая реализует интерполяцию.

Краткие итоги: Рассмотрены методы интерполяции функции на основе приближения полиномами. Приведены методы построения интерполяционных полиномов в форме Лагранжа и в форме Ньютона.