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

Лекция 12 (продолжение лекции 11)МЕТОДЫ ИНТЕГРАЛЬНОГО СГЛАЖИВАНИЯА. ТОЧЕЧНЫЙ МЕТОД НАИМЕНЬШИХ КВАДРАТОВПРИМЕНЕНИЕ ОБОБЩЕННЫХ МНОГОЧЛЕНОВПусть на множестве   [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 ) .Как и ранее, будем использовать обозначение f i  f ( x i ) .На практике сглаживающую функцию удобно представить в виде обобщенногомногочленаf m ( x, a ) maj j ( x)  a 0  0 ( x)  a1 1 ( x)  ...  a m  m ( x) ,j 0где a  {a0 , a1,...,am }T – вектор неизвестных коэффициентов, { j }  { 0 , 1 ,...,  m } –заданная система базисных функций, степень многочлена удовлетворяет условию0  m  n .

В качестве базисных функций могут выбираться, например, степенныефункции { j }  { x j } , многочлены Чебышева, тригонометрические функции{ j }  {cos jx } . Требуется найти такие коэффициенты многочлена a0 , a1 ,..., am ,обеспечивающие минимум среднеквадратичной погрешности:m ( a ) 1 n. f m ( xi , a )  f i  2  a minn  1 i 00 , a1 ,...a mт.е. такой вектор a  {a0 , a1 ,..., am }T , который обеспечивает минимум величиныm ( a ) .В соответствии с постановкой задачи найдем коэффициенты a0 , a1 ,..., amмногочлена, обеспечивающие минимум критерия.Очевидно, минимум критерия достигается, еслиn  0 ( xi ) a0  1 (xi ) a1  ...

 m ( xi ) am  f i  2  a ,mina ,...ai 001.mТак как на коэффициенты не наложено никаких ограничений, применимнеобходимые условия безусловного экстремума: 0,ajj  0,1,..., m .В результате получаем систему111n 2    0 ( x i ) a0  1 ( x i ) a1  ...   m ( x i ) am  f i    0 ( x i )  0 , a0i 0n 2   0 ( x i ) a0  1 ( x i ) a1  ...   m ( x i ) am  f i   1 ( x i )  0 , a1i 0...................................................................................................n 2    0 ( x i ) a0  1 ( x i ) a1  ...   m ( x i ) am  f i    m ( x i )  0 . ami 0Для компактной записи полученного результата удобно использовать скалярноепроизведение.Скалярным произведением функций  k (x ) и l (x ) на множестве точекx , i  0, n называется сумма произведений значений функций, вычисленныхвсех точках, т.е.i( k , l ) воn  k ( x i ) l ( x i ) .i 0Число  k  ( k , k ) называется нормой функции  k (x ) на множестве точек x , i  0, n  .iТогда полученную систему можно переписать в форме:( 0 ,  0 ) a0  ( 0 , 1 ) a1  ...

 ( 0 ,  m ) am  ( f ,  0 ) ,(1 ,  0 ) a0  (1 , 1 ) a1  ...  (1 ,  m ) am  ( f , 1 ) ,.................................................................................( m ,  0 ) a0  ( m , 1 ) a1  ...  ( m ,  m ) am  ( f ,  m ) ,где ( f ,  k ) n fii 0 k ( x i ) . Таким образом, получена система (m  1) линейныхуравнений с (m  1) неизвестными a0 , a1 ,..., am . В силу равенства ( k , l )  (l , k )матрица( 0 , 1 ) .......... ( 0 ,  m )  ( 0 ,  0 )(1 , 1 ) ..........

(1 ,  m )  (1 ,  0 )A .....................................................  ( ,  ) ( ,  ) ......... ( ,  ) m1mm  m 0системы является симметрической. Если базисные функции  0 , 1 ,..., m линейнонезависимы, определитель матрицы А не равен нулю (он называется определителемГрама). Тогда решение системы существует и единственно. Аналогичный выводможно сделать и о задаче определения многочлена наилучшего среднеквадратичногоприближения.Метод решения поставленной задачи называется методом наименьшихквадратов или методом наилучшего среднеквадратичного приближения, посколькувеличина критерия представляет собой сумму квадратов отклонений значенийаппроксимирующей функции f m ( x, a ) от заданных значений f i на множестве точек x , i  0, n  . Согласно приведенной классификации метод является сглаживающим.i112ПРИМЕНЕНИЕ СТЕПЕННЫХ БАЗИСНЫХ ФУНКЦИЙВ качестве базисных функций используем степенные:  j ( x )  x j , j  0, m .В этом случае обобщенный многочлен имеет видf m ( x, a ) majjx a 0  a1 x  ...

 a m x m .j 0Тогда ( f ,  j ) nnni 0i 0i 0 f i xij , (k , l )   x ik  l , (k , k )   xi2kи система длянахождения коэффициентов имеет видn n  n n n  1  a0    x i a1    x i2 a2  ...    x im am   f i ,i 0 i 0 i 0 i 0  i 0n n n n n  x i a0    x i2 a1    x i3 a2  ...    x im 1 am   x i f i ,i 0 i 0 i 0 i 0  i 0.............................................................................................n n m n n n  x i a0    x im 1 a1    x im  2 a2  ...    x i2m am   x im f i .i 0 i 0 i 0i 0 i 0Обозначимs 0  n  1 , t 0  f 0  f1  ...

 f n ,s k  x 0k  x1k  ...  x nk , k  1,...,2m ;t k  x 0k f 0  x1k f1  ...  x nk f n , k  1,..., m .Тогда система преобразуется к видуs 0 a0  s1a1  ...  s m am  t 0 ,s1a0  s 2a1  ...  s m 1am  t1 ,(5.5)s m a0  s m 1a1  ...  s 2m am  t m .Решая систему линейных алгебраических уравнений, находим неизвестныекоэффициенты a0 , a1 ,..., am . Подставляя решение в f m ( x, a ) , получаем искомуюформулу, которая сглаживает экспериментальные данные.Методика решения задачи сглаживанияШаг 1.

Вычислить коэффициенты s k , k  0,2m; t k , k  0, m , по заданнойсеточной функции и записать систему (5.5).Шаг 2. Решить полученную систему одним из методов решения СЛАУ и найтикоэффициенты a0 , a1 ,..., am .Шаг 3. Записать искомую сглаживающую функциюf m ( x, a )  a 0  a1 x  ...  a m x m .113З а м е ч а н и я. Если для сеточной функции, заданной в (n  1) -й точкеx 0 , x1 ,..., x n , определять многочлен степени m  n методом наименьших квадратов,то тогда f m ( x, a ) совпадает с интерполяционным многочленом и метод становитсяэквивалентным методу интерполяции.

При этом   0 и  m ( a )  0 .Б. ИНТЕГРАЛЬНЫЙ МЕТОД НАИМЕНЬШИХ КВАДРАТОВПРИМЕНЕНИЕ ОБОБЩЕННЫХ МНОГОЧЛЕНОВПусть на отрезке [a, b] задана интегрируемая с квадратом функция y  f ( x )b( f 2 ( x)dx   ), которая по каким-либо причинам трудна для использованияa(например, трудно вычислить производные).

Тогда может быть поставлена задача ееприближенной замены (аппроксимации) более простой функцией y  F ( x, a ) . Векторнеизвестных параметров a ищется из условия минимального расстояния d ( f , F )между функциями y  f ( x) и y  F ( x, a ) :b [ F ( x, a)  f ( x)]d( f ,F) 2dx  min .aaЭта задача называется задачей наилучшего интегрального среднеквадратичногоприближения (аппроксимации) на отрезке [a, b] .

Она эквивалентна проблеменахождения функции y  F ( x, a ) из интегрального условия:b  [ F ( x, a )  f ( x)] 2 dx  min ,aaгде  – погрешность аппроксимации. Искомая функция y  F ( x, a ) называетсяаппроксимирующей функцией, а метод аппроксимации – интегральным методомнаименьших квадратов. При решении этой задачи минимизируется заштрихованнаяплощадь на рис.1, в.На практике аппроксимирующую функцию удобно искать в виде обобщенногомногочленаF ( x, a )  f m ( x, a ) maj j ( x)  a 0  0 ( x)  a1 1 ( x)  ...  a m  m ( x) ,j 0где a  {a0 , a1,...,am }T – вектор неизвестных коэффициентов, { j }  { 0 , 1 ,...,  m } –заданная система базисных функций, степень многочлена удовлетворяет условию0  m  n . В качестве базисных функций могут выбираться, например, степенныефункции { j }  { x j } , ортогональные многочлены и др. Функции, входящие всистему, должны быть линейно независимыми.найтитакиекоэффициентымногочленаТребуетсяa0 , a1 ,..., am ,обеспечивающие минимум погрешности аппроксимации:b [fm ( x, a ) f ( x)] 2 dx  min .a114a 0 ,a1 ,...a mт.е.

такой вектор a  {a0 , a1 ,..., am }T , который обеспечивает минимум величины  .В соответствии с постановкой задачи найдем коэффициенты a0 , a1 ,..., amобобщенного многочлена, обеспечивающие минимум критерия:b 0 ( x) a 0 1 ( x) a1  ...   m ( x) a m  f ( x)  dx  min .2a 0 ,a1 ,...a maТак как на коэффициенты не наложено никаких ограничений, применимнеобходимые условия безусловного экстремума: 0,ajj  0,1,..., m .В результате получаем системуb 2   0 ( x) a 0  1 ( x) a1  ...   m ( x) a m  f ( x)    0 ( x) dx  0 , a0ab 2   0 ( x) a 0  1 ( x) a1  ...   m ( x) a m  f ( x)  1 ( x) dx  0 , a1a...................................................................................................b 2   0 ( x) a 0  1 ( x) a1  ...

  m ( x) a m  f ( x)    m ( x) dx  0 . amaДля компактной записи полученного результата удобно использовать скалярноепроизведение.Скалярным произведением функций  k (x ) и l ( x ) на отрезке [a, b] называетсяинтеграл от их произведения на этом отрезкеb( k ,  l )   k ( x)  l ( x) dx .abЧисло  k  ( k ,  k ) 2k ( x ) dxявляется нормой функции  k (x ) на отрезке [a, b] .aТогда полученную систему можно переписать в форме:( 0 ,  0 ) a0  ( 0 , 1 ) a1  ...  ( 0 ,  m ) am  ( f ,  0 ) ,(1 ,  0 ) a0  (1 , 1 ) a1  ...  (1 ,  m ) am  ( f , 1 ) ,.................................................................................( m ,  0 ) a0  ( m , 1 ) a1  ...