УМК (1013374), страница 18
Текст из файла (страница 18)
От этогонедостатка свободны многочлены Ньютона.2. Выделим «окно» или частичный отрезок [x i , x i +1 ] , содержащий только две точки (шаблон ( x i , x i +1 ) ). Тогда многочлен Лагранжа, интерполирующий исходную функцию на данном шаблоне, имеет видL1 ( x) =( x − x i +1 )( x i − x i +1 )fi +( x − xi )( x i +1 − x i )f i +1 .Действительно, легко убедиться в том, что L1 ( x ) – алгебраический многочлен первойстепени,которыйудовлетворяетусловияминтерполяции,т.е.L1 ( x i ) = f i , L1 ( x i +1 ) = f i +1 . Полученный многочлен соответствует линейной интерполяции, так как графиком функции является прямая линия.3. Выделим «окно» в виде двойного частичного отрезка [x i , x i + 2 ] с шаблоном( x i , x i +1 , x i + 2 ) .
Тогда многочлен Лагранжа записывается в виде( x − x i +1 ) ⋅ ( x − x i + 2 )( x − xi ) ⋅ ( x − xi + 2 )L2 ( x) =fi +f i +1 +( x i − x i +1 ) ⋅ ( x i − x i + 2 )( x i + 1 − x i ) ⋅ ( x i +1 − x i + 2 )+( x − x i ) ⋅ ( x − x i +1 )fi+2.( x i + 2 − x i ) ⋅ ( x i + 2 − x i +1 )Легко проверить, что L2 ( x) – многочлен второй степени и также удовлетворяет условиям функциональной интерполяции: L2 ( x i ) = f i ; L2 ( x i +1 ) = f i +1 , L2 ( xi + 2 ) = f i + 2 .Полученный многочлен соответствует параболической (квадратичной интерполяции), так как графиком функции является парабола.107Б.
ИНТЕРПОЛЯЦИОННЫЕ МНОГОЧЛЕНЫ НЬЮТОНАИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН НЬЮТОНА ДЛЯ НЕРАВНОМЕРНОЙ СЕТКИПусть исходная (интерполируемая) сеточная функция y i = f ( x i ) = f i , i = 0, n ,задана на неравномерной сетке Ω n ≡ {x 0 , x1 , x 2 ,..., x n }, характеризующейся шагамиhi +1 = x i +1 − x i = var .Выбрав внутри неравномерной сетки соответствующие шаблоны интерполяции(xi , xi +1 ) , (x i , xi +1 , xi + 2 ) ,..., (xi , xi +1 ,.., xi + k ) , введем следующие определения разделенных разностей:– разделенная разность нулевого порядка: f ( x i ) = f i ;– разделенная разность первого порядка: f ( x i , x i +1 ) =f i +1 − f ix i +1 − x i– разделенная разность второго порядка: f ( x i , x i +1, x i + 2 ) =;f ( x i +1 , x i + 2 ) − f ( x i , x i +1 )xi + 2 − xi;– разделенная разность k-го порядка:f ( x i , x i +1 ,..., x i + k ) =f ( x i +1 , x i + 2 ,..., x i + k ) − f ( x i , x i +1 ,..., x i + k −1 )xi + k − xi;– разделенная разность n-го порядка в узле x 0 :f ( x 0 , x1 ,..., x n ) =f ( x1 , x 2 ,..., x n ) − f ( x 0 , x1 ,..., x n −1 )xn − x0.Интерполяционный многочлен Ньютона n-й степени имеет видN n (x ) = f 0 + f (x 0 , x1 )(x − x 0 ) + f (x 0 , x1 , x 2 )(x − x 0 )(x − x1 ) + ...
++ f (x 0 , x1 ,..., x n )(x − x 0 )(x − x1 ) ⋅ ... ⋅ (x − x n −1 ) .З а м е ч а н и я. Интерполяционный многочлен Ньютона (так же, как и многочленНьютона, выражаемый ниже через конечные разности) записан не через значения функции, как это имеет место для многочлена Лагранжа, а через разделенные разности.
Поэтому при изменении степени k в процессе интерполирования у многочлена НьютонаN k (x ) требуется только добавить или отбросить соответствующее число слагаемых. Этоиногда упрощает алгоритм интерполирования.108ИНТЕРПОЛЯЦИОННЫЕ МНОГОЧЛЕНЫ НЬЮТОНАДЛЯ РАВНОМЕРНОЙ СЕТКИПусть исходная (интерполируемая) сеточная функция y i = f ( x i ) = f i , i = 0, n ,задана на равномерной сетке Ω n ≡ {x 0 , x1 , x 2 ,..., x n }, характеризующейся шагамиhi +1 = x i +1 − x i = h = const .Выбрав внутри равномерной сетки соответствующие шаблоны интерполяции(xi , xi +1 ) , (x i , xi +1 , xi + 2 ) ,..., (xi , xi +1 ,.., xi + k ) , введем следующие определения конечныхразностей:fi ;– конечная разность нулевого порядка:– конечная разность первого порядка: Δf i = f i +1 − f i ;– конечная разность второго порядка: Δ2 f i = Δ(Δf i ) = Δf i +1 − Δf i = f i + 2 − 2 f i +1 + f i ;– конечная разность k -го порядка: Δk f i = Δ(Δk −1 f i ) =где Ckj =k∑ (−1) j C kj f i + j ,j =0k!;(k − j )! j !– конечная разность n -го порядка в узле x 0 : Δ n f 0 = Δ n−1 f 1 − Δ n −1 f 0 .Интерполяционный многочлен Ньютона n -го порядка имеет видN n(I ) (q ) = f 0 +где q =x − x0hΔf 01!q+Δ2 f 02!q (q − 1) + ...
+Δn f 0n!q (q − 1) ... (q − n + 1) ,– фаза интерполяции относительно точки x 0 .В. ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИСплайн-функцией, или сплайном, называется совокупность S m,i (x ) − алгебраических многочленов степени m (звеньев), т.е.S m,i (x ) =гдеm∑ ak ,i (x − xi )k ,k =0a k ,i , k = 0, m – коэффициенты, определенных на частичных отрезках [x i , x i +1 ] ,i = 0, n − 1 , и соединенных вместе по всем частичным отрезкам так, чтобы можнобыло составить многозвенную функцию S m (x ) =n −1∪ S m,i (x ) ,i =0определенную и непрерыв-ную на всем отрезке [a, b ] вместе со всеми своими производными S m( p ) (x ) до некоторого их порядка p = 1,2, … .Разность между m и наибольшим порядком производной, непрерывной на отрезке [a, b ] , определяет дефект сплайна q .109Рассмотрим задачу восполнения заданной сеточной функции yi = f (x i ) , i = 0, n ,x i ∈ [a, b ] на базе интерполяционных глобальных кубических дифференциальных сплайнов дефекта один ( m = 3 , q = 1 ), т.е.
S 3 (x ) ∈ C 2 [a, b ] . При этом предположим, что восполняемая функция достаточно гладкая.Уравнение i -го звена сплайна ( i = 0,1,..., n − 1 ) ищется в видеS 3,i (x ) = a0,i + a1,i (x − x i ) + a2,i (x − x i )2 + a3,i (x − x i )3 , x ∈ [x i , x i +1 ] ,где a 0,i , a1,i , a 2,i , a 3,i - неизвестные коэффициенты. Они вычисляются на основе применения условий непрерывности (гладкости) сплайна S 3 ( x ) , которые называются условиями стыковки и согласования:1) условие интерполяции S 3 ( x i ) = f i , i = 0, n ;2) условие непрерывности во внутренних узлах сетки:S 3 ( x i − 0) = S 3 ( x i + 0), i = 1, n − 1 ;3) условие непрерывности первой производной во внутренних узлах сетки:S 3′ ( x i − 0) = S 3′ ( x i + 0), i = 1, n − 1 ;4) условие непрерывности второй производной во внутренних узлах сетки:S 3′′( x i − 0) = S 3′′( x i + 0), i = 1, n − 1 ;5) условие для определения второй производной в узлах x 0 , x n :S 3′′( x 0 ) = 0,S 3′′( x n ) = 0 .Заметим, что имеется n частичных отрезков [x i , x i +1 ] и, следовательно, 4n неизвестныхкоэффициентовсплайна,длянахождениякоторыхимеется(n + 1) + 3(n − 1) + 2 = 4n условий.Можно показать, что уравнение звена сплайна удобно записать в форме⎛ 1⎞hhΔf i − i +1 mi − i +1 Δmi ⎟⎟ ⋅ (x − x i ) +S 3,i (x ) = f i + ⎜⎜26⎝ hi +1⎠+mi2⋅ (x − x i )2 +1Δmi ⋅ (x − x i )3 ,6hi +1i = 0, n − 1 ,где hi +1 = x i +1 − x i , Δf i = f i +1 − f i , Δmi = mi +1 − mi , а параметры miузлах сетки находятся из системы трехдиагонального вида:hi6mi −1 +hi + hi +13mi +hi +16mi +1 =Δf ihi +1−Δf i −1hiво внутренних, i = 1, n − 1 .Из условия 5 согласования и стыковки следуют два так называемых краевых условия: m0 = 0 ; mn = 0 .
Такие краевые условия называются условиями натуральногосплайна. Решая систему, можно найти параметры mi , i = 0, n и получить уравнения всехзвеньев сплайна.110Лекция 14 (продолжение лекции 13)МЕТОДЫ ИНТЕГРАЛЬНОГО СГЛАЖИВАНИЯА. ТОЧЕЧНЫЙ МЕТОД НАИМЕНЬШИХ КВАДРАТОВПРИМЕНЕНИЕ ОБОБЩЕННЫХ МНОГОЧЛЕНОВ{}Пусть на множестве Ω = [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системы является симметрической.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
