11 Задачи приближения функций. Интерполяция (Лекции по теории оптимизации и численным методам)

Лекция 115. МЕТОДЫ ПРИБЛИЖЕНИЯ ФУНКЦИЙПОСТАНОВКА ЗАДАЧИРассматриваются сеточные (табличные) функцииyi  f ( x i ), x i  a, b  , i  0, n ,(5.1)определенные в узлах x i (i  0, n) сетки  n . Каждая сетка характеризуется шагамиhi 1  x i 1  x i неравномерного или ( hi 1  const ) равномерного разбиения.Однако значения функции должны быть известны при любом значении аргументаx  x i , а в самих узлах x i , как правило, требуется знать также первые и вторые производные, поэтому сеточные функции yi  f ( x i ) необходимо восполнять. Данная проблема решается с помощью методов теории приближений путем выбора функцииy  F ( x, a ) , зависящей от вектора a  (a0 , a1 ,..., am )T неизвестных параметров, где m число параметров.Если требуется, чтобы искомая функция y  F ( x, a ) проходила через все заданныеточки, определенные сеточной функцией, то вектор неизвестных параметров находитсяиз условия интерполяции:F ( xi , a )  f ( xi )  y i ,i  0, n .(5.2)При этом способ приближения называется интерполяцией, а искомая функция интерполяционным многочленом (полиномом), график которого изображен на рис.

1,а.Если узлы и значения сеточной функции получены в ходе эксперимента и содержат случайные ошибки, то с практической точки зрения нет смысла требовать прохождения искомой функции через заданный набор точек. В этом случае логичнее сгладить экспериментальные данные и найти достаточно простую зависимость, характеризующуювзаимосвязь между значениями аргумента и величиной функции. С этой целью векторнеизвестных параметров ищется из интегрального условия21 n( m  n) . F ( x i , a )  f ( xi )   minan  1 i 0(5.3)Условие (5.3) выражает минимум среднеквадратичной погрешности (или отклонения)представления заданной сеточной функции f ( x i ), i  0, n , с помощью функции F ( x, a ) .Оно относится, как правило, ко всей области определения функции f ( x i ) , т.е.

к отрезкуa, b  . Сомножитель 1 иногда опускают, так как его наличие или отсутствие влияетn 1только на величину погрешности, но не влияет на вектор a , обеспечивающий ее минимум. Задача (5.3) называется задачей интегрального сглаживания (задачей аппроксимации, или приближенной замены), искомая функция – аппроксимирующей функцией102(рис.1,б), а используемый метод решения задачи аппроксимации – точечным методомнаименьших квадратов.yy0x 0 x1y  F ( x, a )y  F ( x, a )f (xi )xxnxi0x0аxnxixбyy  F ( x, a )y  f ( x)0baxвРис.

1Для восполнения исходных функций yi  f ( x i ), i  0, n , искомыми функциямиy  F ( x, a ) обычно используются алгебраические многочленыf m ( x, a ) majxj a 0  a1 x  ...  a m x m ,j 0где a  (a0 , a1 ,..., am )T – вектор неизвестных параметров, m – степень многочлена (напрактике m  n ).Можно выделить четыре способа применения методов приближения сеточныхфункций, отличающихся областями их «действия».1031. Глобальный способ, в котором для всей области   a, b  определяется однафункция f m ( x, a ) .2.

Локальный способ, когда функция восполняется только в окрестности некоторойточки x i . Это восполнение обычно осуществляется на основе формулы Тейлора.3. Кусочный способ, когдаищетсяоднаилинесколькофункцийf ki ( x, a ) , i  0,1,.. , каждая из которых является многочленом степени k и имеет областьопределения в виде частичного отрезка  ik  x i , x i  k  (1  k  n, k  1,2,..) , называемого «окном» аппроксимации, которое составляет шаблон x i , x i 1 ,..., x i  k  .

Саму функциюf ki ( x, a ) , построенную на одном шаблоне, будем называть звеном.4. Кусочно-глобальный способ, в котором область  представляется совокупностью N непересекающихся частичных отрезков  ik , таких, что  N ik . На первомi 1этапе на каждом из отрезков ищется функция f ki ( x, a ) – i -е звено с применением кусочного способа аппроксимации. На следующем этапе производится объединение всехNзвеньев в одну многозвенную функцию, т.е.

f k ( x, a )  f ki ( x, a ) . Данный способ примеi 1няется, например, при построении сплайнов.Если на отрезке [a, b] задана квадратично интегрируемая функция y  f ( x) ,которая по каким-либо причинам трудна для использования (например, трудно вычислить производные), то может быть поставлена задача ее аппроксимации более простойфункцией y  F ( x, a ) . Вектор неизвестных параметров a ищется из интегрального условия:ba  [ F ( x, a )  f ( x)] 2 dx  min .aИскомая функция y  F ( x, a ) называется аппроксимирующей функцией, а метод аппроксимации – интегральным методом наименьших квадратов. При решении этой задачиминимизируется заштрихованная площадь на рис.

1, в.МЕТОДЫ ИНТЕРПОЛЯЦИИА. ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖАПусть на множестве   [a, b] задана сетка  n  x i , i  0, n , определяемая n  1точкой x 0 , x1 ,..., x n , а на сетке задана сеточная функция yi  f ( x i ), i  0, n :y 0  f ( x 0 ), y1  f ( x1 ),..., y n  f ( x n ) ,104где x i  a, b   x 0 , x n  - в общем случае неравноотстоящие узлы, определяемые шагамиhi 1  x i 1  x i ( hi 1  var ), i  0, n  1 .В некоторых случаях yi  f ( x i ), i  0, n , является сеточным представлением заданной формульной функции y  f (x ) . Сеточная функция может задаваться совокупностью пар: ( x 0 , y 0 ), ( x1 , y1 ),..., ( x n , y n ) .Требуется найти функцию y  F ( x, a ) , принимающую в точках x 0 , x1 ,..., x nте жезначения, что и функция yi  f ( x i ), i  0, n , т.е.

F ( x i )  yi , i  0, n .Точки x 0 , x1 ,..., x n называются узлами интерполяции, а искомая функцияy  F ( x, a ) – интерполирующей.Геометрически это означает, что нужно найти кривую, проходящую через заданноемножество точек ( x i , yi ), i  0, n (рис.2).Одной из целей решения задачи интерполяции является вычисление значенияфункции в произвольной точке x  (или точках x  j , j  1,..., p ). При этом различаютсясобственно интерполирование, когда точка x   [ x 0 , x n ] , и экстраполирование, когдаx   [x 0 , x n ] .Заметим, что можно провести бесчисленное множество «плавных» кривых, проходящих через заданное множество точек. Поэтому задача интерполяции в общей постановке не имеет единственного решения.yy0yi0x0y  F ( x, a )ynxnxixРис. 2Теорема (о единственности решения задачи интерполяции).

Если сеточная функция задана в (n  1) -м узле x 0 , x1 ,..., x n , а в качестве интерполирующей функцииy  F ( x, a ) выбран многочлен n-й степени (степень многочлена на единицу меньше числаузлов интерполяции), т.е.F ( x, a )  f n ( x, a ) najxj a 0  a1 x  ...  a n x n ,j 0то задачи интерполяции имеет единственное решение.105Значения коэффициентов a 0 , a1 ,..., a n можно найти из системы уравнений, следующей из условия интерполяции:a 0  a1 x 0  a 2 x 02  ...

 a n x 0n  y 0 ,a 0  a1 x1  a 2 x12  ...  a n x1n  y1 ,(5.4)................................................................a 0  a1 x n  a 2 x n2  ...  a n x nn  y n .Эта система линейных алгебраических уравнений относительно коэффициентовa 0 , a1 ,..., a n имеет единственное решение, так как определитель матрицы системы не равен нулю (доказательство последнего факта содержится в курсе линейной алгебры, гдеэтот определитель называется определителем Вандермонда). Следовательно, задача интерполяции также имеет единственное решение.

Описанная процедура соответствуетглобальному способу решения поставленной задачи.Методика решения задачи интерполяцииШаг 1. По заданной сеточной функции составить интерполяционный многочленсоответствующей степени.Шаг 2. Вычислить значения интерполяционного многочлена в заданных точкахx  j , j  1,..., p , путем их подстановки в формулу многочленаЗ а м е ч а н и я.1. Имеются различные формы записи интерполяционных многочленов. По теоремевсе эти многочлены степени n , удовлетворяющие условиям интерполяции и построенные по одним и тем же точкам, являются одним многочленом, записанным в разныхформах.2. При n  7 график интерполяционного многочлена, как правило, имеет колебательный характер, т.е.

содержит значительные «провалы» или «всплески» между узламиинтерполяции, что весьма неудобно на практике.При большом числе узлов решение системы (5.4) затруднительно. Искомый интерполяционный многочлен можно построить, не решая этой системы. Многочлены могутбыть построены так, чтобы в самой структуре формулы многочлена условие интерполяции учитывалось. Примерами таких многочленов являются интерполяционные многочлены Лагранжа и Ньютона.Интерполяционный многочлен Лагранжа n-й степени имеет видLn ( x ) n (xi 0( x  x 0 )  ( x  x1 )...(x  x i 1 )  ( x  x i 1 )...(x  x n )i x 0 )  ( x i  x1 )...(x i  x i 1 )  ( x i  x i 1 )...(x i  x n )fi n Pni (x )  f i ,i 0где коэффициенты Лагранжа Pni (x ) во внутренних точках отрезка записываются в( x  x 0 )  ( x  x1 )...( x  x i 1 )  ( x  x i 1 )...( x  x n ).форме Pni ( x) ( x i  x 0 )  ( x i  x1 )...( x i  x i 1 )  ( x i  x i 1 )...( x i  x n )106Многочлен Ln (x ) является многочленом степени n и удовлетворяет условиям интерполяции: Ln ( x i )  f i , i  0, n .Для записи интерполяционного многочлена Лагранжа удобно пользоваться табл.1.x  x0x 0  x1x0  x2x1  x 0x  x1x1  x 2x2  x0x 2  x1x  x2xn  x0x n  x1xn  x2.........x0  xnD0x1  x nD1x2  xnD2x  xnDn... n 1 ( x )  ( x  x 0 ) ( x  x1 ) ( x  x 2 )  ...