semopt12 (Практические занятия)
Описание файла
Файл "semopt12" внутри архива находится в папке "Практические занятия". PDF-файл из архива "Практические занятия", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Занятие 12. МЕТОДЫ ПРИБЛИЖЕНИЯ ФУНКЦИЙ. ИНТЕРПОЛЯЦИЯИ ИНТЕГРАЛЬНОЕ СГЛАЖИВАНИЕЧасть I. ПРИМЕНЕНИЕ МЕТОДОВ ИНТЕРПОЛЯЦИИА. ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖА{}Пусть на множестве Ω = [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 ) ,где x i ∈ [a, b ] = [x 0 , x n ] - в общем случае неравноотстоящие узлы, определяемые шагами hi +1 = x i +1 − x i ( hi +1 = var ), i = 0, n − 1 .Требуется найти многочлен n-й степени, проходящий через все заданные точки.Интерполяционный многочлен Лагранжа n-й степени имеет видLn ( x) =n( x − x ) ⋅ ( x − x )...( x − x) ⋅ (x − x)...( x − x )∑ ( xi − x0 )0⋅ ( xi − x11)...( xi − xii−−11 ) ⋅ ( xi − ix+i1+1 )...( xi −n x n ) f i .i =0Многочлен 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Таблица 1f0f1f2#fnDifi...Π n +1 ( x ) = ( x − x 0 ) ( x − x1 ) ( x − x 2 ) ⋅ ...
⋅ ( x − x n )Здесь Di – произведение элементов i -й строки, Π n +1 ( x ) – произведение элементов главной диагонали.Тогда многочлен Лагранжа может быть записан в формеnLn ( x ) = Π n +1 ( x ) ∑i =0241fi.DiБ. ИНТЕРПОЛЯЦИОННЫЕ МНОГОЧЛЕНЫ НЬЮТОНАИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН НЬЮТОНА ДЛЯ НЕРАВНОМЕРНОЙ СЕТКИПусть исходная (интерполируемая) сеточная функция 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 +1 , x i + 2 ) − f ( x i , x i +1 )f ( x i , x i +1 , x i + 2 ) =;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 ) .ИНТЕРПОЛЯЦИОННЫЕ МНОГОЧЛЕНЫ НЬЮТОНА ДЛЯ РАВНОМЕРНОЙ СЕТКИПусть исходная (интерполируемая) сеточная функция 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 ;242– конечная разность первого порядка: Δ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 .Пример 1. Требуется:а) найти интерполяционный многочлен Лагранжа третьей степени для сеточнойфункции, заданной табл. 2. Вычислить значение функции в точке x ∗ = 2,5 ;б) найти интерполяционный многочлен Ньютона третьей степени для сеточнойфункции, заданной табл. 2.Таблица 20123i2345xi7587f (xi ) = f i 1. Составим многочлен Лагранжа. Для этого заполним табл. 3, соответствующую табл.
1.x−2123–1–2–3–1–2x −31–1x−421x−5Π 4 ( x ) = ( x − 2) ( x − 3) ( x − 4) ( x − 5)− 6 ⋅ ( x − 2)2 ⋅ ( x − 3)− 2 ⋅ ( x − 4)6 ⋅ ( x − 5)DiТаблица 37587fiПолучаем:3L3 ( x ) = Π 4 ( x ) ∑fii = 0 Di+=( x − 2) ( x − 3) ( x − 4) ( x − 5) ⋅ 7 ( x − 2) ( x − 3) ( x − 4) ( x − 5) ⋅ 5++2 ⋅ ( x − 3)− 6 ⋅ ( x − 2)( x − 2) ( x − 3) ( x − 4) ( x − 5) ⋅ 8 ( x − 2) ( x − 3) ( x − 4) ( x − 5) ⋅ 7=+− 2 ⋅ ( x − 4)6 ⋅ ( x − 5)243=−75⋅ ( x − 3) ( x − 4) ( x − 5) + ⋅ ( x − 2) ( x − 4) ( x − 5) − 4 ⋅ ( x − 2) ( x − 3) ( x − 5) +6273107+ ⋅ ( x − 2) ( x − 3) ( x − 4) = − x 3 + 16 x 2 −x + 62 .6222. Вычислим значение функции в заданной точке: L3 (2,5) = 4,8125 .
Составим многочлен Ньютона, справедливый для произвольного расположенияузлов. Для этого сформируем табл. 4.xifi27354857f ( x 0 , x1 ) =f ( x j , x j +1 )f ( x j , x j +1 , x j + 2 )Таблица 4f ( x j , x j +1 , x j + 2 , x j + 3 )52−−23−232−15−7= −2 ;3−2f ( x1 , x 2 ) =8−5= 3;4 −3f (x 2 , x3 ) =7−8= −1 ;5−43 − (−2) 5−1 − 3= ; f ( x1 , x 2 , x 3 ) == −2 ;5−34−225−2−2 = −3 .f ( x 0 , x1 , x 2 , x 3 ) =5−22f ( x 0 , x1 , x 2 ) =Для n = 3 имеемN 3 ( x ) = f ( x 0 ) + ( x − x 0 ) f ( x 0 , x1 ) + ( x − x 0 ) ( x − x1 ) f ( x 0 , x1 , x 2 ) ++ ( x − x 0 ) ( x − x1 ) ( x − x 2 ) f ( x 0 , x1 , x 2 , x 3 ) = 7 + ( x − 2) ⋅ (−2) + ( x − 2) ⋅ ( x − 3) ⋅5+233107+ ( x − 2) ⋅ ( x − 3) ⋅ ( x − 4) ⋅ (− ) = − x 3 + 16 x 2 −x + 62 .222Поскольку в данной задаче заданы равностоящие узлы, воспользуемся такжеформулой для первого интерполяционного многочлена Ньютона:N 3(I ) (q )где q =x − x0h== f (x0 ) +Δf 01!q+Δ2 f 02!q ⋅ (q − 1) +x −2= x −2.1Составим табл.
5.244Δ3 f 03!q ⋅ (q − 1) ⋅ (q − 2) ,Таблица 5xif i = f (xi )27354857Δf j−2Δ2 f jΔ3 f j53−4−9−1Имеем: Δ f 0 = 5 − 7 = −2 ; Δ f1 = 8 − 5 = 3 ; Δ f 2 = 7 − 8 = −1 ;Δ2 f 0 = 3 − (−2) = 5 ;Δ2 f1 = −1 − 3 = − 4 ; Δ3 f 0 = − 4 − 5 = − 9 . ПоэтомуN 3(I ) (x ) = 7 +=−5(−2)3(−9)15q + q ⋅ (q − 1) +q ⋅ (q − 1) ⋅ (q − 2) = − q 3 + 7q 2 − q + 71!2!3!22q=x −21=3153107⋅ ( x 3 − 6x 2 + 12x − 8) + 7 ⋅ ( x 2 − 4 x + 4) −⋅ ( x − 2) + 7 = − x 3 + 16x 2 −x + 62.2222Часть II. ПРИМЕНЕНИЕ МЕТОДОВ ИНТЕГРАЛЬНОГО СГЛАЖИВАНИЯТОЧЕЧНЫЙ МЕТОД НАИМЕНЬШИХ КВАДРАТОВМетодика решения задачи сглаживанияШаг 1.
Записать систему:s 0 a0 + s1a1 + ... + s m am = t 0 ,s1a0 + s 2a1 + ... + s m +1am = t1 ,#s m a0 + s m +1a1 + ... + s 2m am = t m .где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 .Шаг 2. Решить полученную систему одним из методов решения СЛАУ и найтикоэффициенты a0 , a1 ,..., am .Шаг 3. Записать искомую сглаживающую функциюf m ( x, a ) = a 0 + a1 x + ... + a m x m .245(*)Пример 2. Решить задачу аппроксимации сеточной функции, заданной табл.
6,при m = 1 и m = 2 .ixif (xi ) = f i027135248Таблица 6357 Пусть степень многочлена m = 1 , тогда решение ищется в видеf 1 ( x, a ) = a 0 + a1 x .1. Для составления системы (*):s 0 a0 + s1a1 = t 0 ,s1a0 + s 2a1 = t1найдем ее коэффициенты s 0 , s1 , s 2 . Расчеты поместим в табл.
7, где в последней числовой строке находятся коэффициенты системы.Таблица 7xifi1xi2xi f i234514s1758727t011114s049162554s21415323596t1В результате получаем4a0 + 14a1 = 27 ,14a0 + 54a1 = 96 .2. Решение системы: a0 = 5,7 ; a1 = 0,3 .3. Искомая сглаживающая функция имеет видквадратичная погрешность δ1 (a ) = 1,0368 .f 1 ( x, a ) = 5, 7 + 0,3x , а средне-Пусть m = 2 , тогда решение ищется в видеf 2 ( x, a ) = a 0 + a1 x + a 2 x 2 .1. Составим систему (*):s 0 a0 + s1a1 + s 2a2 = t 0 ,s1a0 + s 2a1 + s 3a2 = t1 ,s 2a0 + s 3a1 + s 4 a2 = t 2 .246Расчеты коэффициентов системы приведены в табл. 8.Таблица 8xifi1xi2xi3xi4xi f ix i2 f i234514s1758727t011114s049162554s282764125224s31681256625978s41415323596t12845128175376t2В результате получаем систему4a0 + 14a1 + 54a2 = 27 ,14a0 + 54a1 + 224a2 = 96 ,54a0 + 224a1 + 978a2 = 376 .yf 2 ( x, a ) =10169 291−x + x220 2049f 1 ( x, a ) = 5, 7 + 0,3x87654N 3 ( x ) = L3 ( x )321012345Рис.