Интерполирование функций

Лекция 1. Интерполирование функций 1.1. Постановка задачи Пусть на отрезке заданы точек , которые называются узлами интерполяции, и значения некоторой функции в этих точках: , , ,…, . Требуется построить интерполирующую функцию , принимающую в узлах интерполяции те же значения, что и . Интерполяционную формулу используют для приближенного вычисления значений функции в точках , отличных от узлов интерполирования. Рис. 1.1. Интерполяционная кривая Геометрически это означает, что нужно найти кривую определенного типа, проходящую через точки , (рис. 1.1). 1.2. Интерполяционный многочлен Пусть функция , определённая на промежутке , задана на нём своими значениями , , в точках – узлах интерполирования. Многочлен , степени не выше называется интерполяционным, если для любого . Теорема Вейерштрасса. Если функция непрерывна на промежутке и число , то существует многочлен , степени не выше n, такой, что . Замечание Можно доказать, что в сформулированных условиях существует единственный интерполяционный многочлен, степени не выше . Интерполяционный многочлен может строиться для двух случаев: 1) узлы являются равноотстоящими, т.е. , где число называется шагом таблицы; 2) узлы произвольно размещены на . 1.3. Интерполяционный многочлен в форме Лагранжа Интерполяционный многочлен в форме Лагранжа строится в виде: , (1.1) где , а функции задаются в виде: . (1.2) Постоянные числа можно определить, полагая в формуле (1.2) и учитывая, что . Поэтому . (1.3) Подставляя (1.3) и (1.2) в формулу (1.1), получим формулу интерполяционного многочлена Лагранжа: , (1.4) где , . В частных случаях: 1)  — многочлен Лагранжа 1 порядка; 2)  — многочлен Лагранжа 2 порядка. 1.4. Конечные разности Для построения интерполяционного многочлена для функции , заданной табличными значениями , в случае равноотстоящих узлов , , где , вводятся конечные разности: – конечная разность первого порядка: , – конечная разность второго порядка: , – конечная разность третьего порядка: . В общем случае для произвольного порядка : , при . Из первого из выписанных равенств: , а также из следующих равенств: . . ………………………………… следует, что . 1.5. Интерполяционный многочлен Ньютона Интерполяционный многочлен Ньютона для равноотстоящих узлов имеет вид . (1.5) Ясно, что его степень не выше . Покажем, что . , , ................................................................. . Поскольку узлы равноотстоящие, т.е. , то , ,…, поскольку , аналогично и поэтому , ............................................................. , для любого . Если ввести переменную , то многочлен Ньютона запишется в виде: . (1.6) Формулу (1.6) называют первой интерполяционной формулой Ньютона. Она, как и формула (1.5), применяется для интерполирования в начале и середине таблицы значений функции (интерполирование вперед). Для интерполирования в конце таблицы используется вторая интерполяционная формула (интерполирование назад): . (1.7) или с переменной : . (1.8) При первая интерполяционная формула . вторая интерполяционная формула . Замечание 1 Как первая, так и вторая интерполяционные формулы Ньютона могут быть использованы для экстраполирования функции, т.е. для вычисления значений функции , лежащих вне таблицы . Если при этом , то используют первую интерполяционную формулу Ньютона, причем (экстраполирование назад). Если , то используют вторую интерполяционную формулу Ньютона, причем (экстраполирование вперед). Замечание 2 Интерполяционные многочлены в формах Лагранжа и Ньютона тождественно совпадают, если они составлены для одинакового набора узлов в силу теоремы единственности. Теорема 1.1. Если функция непрерывна на промежутке вместе с производными до n+1 порядка, то для любого найдётся точка такая, что имеет место равенство , где , а — многочлен Лагранжа. Следствие. Если на промежутке , то . В частности, если и , то (рис. 1.2) и поэтому . Рис. 1.2. 1.6. Построение интерполяционного многочлена методом наименьших квадратов 1. Согласно методу наименьших квадратов интерполяционный многочлен по заданному набору точек , при , строится так, чтобы функция , (1.9) принимала наименьшее значение. Необходимым условием этого является равенство нулю всех частных производных: (1.10) Система (1.10) – эта система m+1 линейных алгебраических уравнений с m+1 неизвестными . Если записать то система примет вид (1.11) Решением системы (1.11) является набор коэффициентов интерполяционного многочлена .., а многочлен принимает вид . 1.7. Интерполяция сплайнами Интерполяция полиномами не всегда дает удовлетворительные результаты в задачах аппроксимации. Интерполяционный многочлен может совпадать с аппроксимируемой функцией в узлах интерполирования, но существенно отличаться от нее между узлами. Такая ситуация возникает при аппроксимации кривых, описывающих колебательные процессы с большими амплитудами. В этом случае используют сплайн-интерполяцию (spline-interpolation). Интерполяция сплайнами – это аппроксимация заданной таблично функции между узлами сетки на , т.е. на промежутках сплайном, т.е. некоторым многочленом , , удовлетворяющим условиям: – , , где , ; – функции дважды непрерывно дифференцируемы на промежутке ; – на концах интервала для функций выполнено условие . Степенью сплайна называется максимальная по всем частичным отрезкам степень многочленов , а дефектом сплайна – разность между степенью сплайна и порядком наивысшей непрерывной на производной. Например, непрерывная ломанная (линейный сплайн) является сплайном первой степени с дефектом 1 (так как сама функция непрерывна, а ее первая производная уже разрывная). В зависимости от того, какая функция выбирается в качестве сплайна, различают интерполяцию линейными, квадратичными или кубическими сплайнами. Интерполяция линейными сплайнами В случае линейной интерполяции в качестве сплайна выступает линейная функция (рис. 1.3): , , (1.14) удовлетворяющая условиям , , в которой коэффициенты и вычисляются по формулам: , . (1.15) , замечание Линейная интерполяция дает достаточно хорошие результаты, в том случае, когда от функции не требуется дополнительных свойств, например, дифференцируемости. Рис. 1.3. Интерполяция линейными сплайнами Интерполяция квадратичными и кубическими сплайнами При интерполяции квадратичными сплайнами функция задается как квадратичная, т.е. в виде: , при условиях , . При интерполяции кубическими сплайнами функция задается в виде: , (1.16) где , , при условиях , . 1.8. Интерполяция в пакете Mathematica В пакете Mathematica возможна полиномиальная аппроксимация через функцию Interpolating Polynomial, где интерполяционный полином степени (– число узлов) ищется в явном виде. Функция выбирает сама интерполяционный многочлен в зависимости от свойств таблично заданной функции. Пример 1.1. Построить аппроксимирующий полином в пакете Mathematica для функции , заданной таблицей 1.1. Таблица 1.1 0,25 0,5 0,75 1,0 1,25 1,5 1,85 2,85 3,90 5,00 6,15 7,34 Решение. Показано на рисунке 1.4, где набор точек, по которым строится интерполяционный многочлен, задается в виде списка, с парами точек в фигурных скобках через запятую. Интерполяционный многочлен строится функцией Interpolating Polynomial [data, x], где data – список, по которому строится многочлен, x – переменная многочлена. Функция Collect [P, x] представляет интерполяционный многочлен в стандартном виде. На экран выводится интерполяционный многочлен в стандартной форме. График многочлена построен с помощью функции построения графиков , а список точек, по которым построен многочлен, выводится с помощью функции List Plot. Оба графика построены в одном шаблоне через функцию Show [g1, g2, опции Plot], где g1 и g2 – функции, описывающие построение соответствующих графиков, т.е. функция выполняет построение двух графиков – непрерывной кривой и набора точек – по заданным «правилам» и объединяет их в один шаблон. Обратите внимание, что аппроксимирующий многочлен в пакете Mathematica получен в явном виде, что позволяет использовать его в других математических задачах. Рис. 1.4. Полиномиальная аппроксимация в Mathematica Лабораторное занятие 1. Интерполирование функций Пример 1.2. Для функции , заданной табл.1.2, в пакете Mathcad Prime построить многочлены Лагранжа и Ньютона, интерполяционный многочлен методом наименьших квадратов, а также провести интерполяцию кубическими, квадратичными и линейными сплайнами. Таблица 1.2 0,25 0,5 0,75 1,0 1,25 1,5 1,75 2,0 1,85 2,85 3,90 5,00 6,15 7,34 8,56 9,83 На рис. 1.5 показано формирование оператором присваивания векторов узлов интерполирования и значений функции в этих узлах. Векторы задаются в виде строк и транспонируются. Можно задавать их сразу в виде столбцов, хотя это увеличивает размер рабочего поля пакета. Рис. 1.5. Задание исходных данных Интерполяционный многочлен Лагранжа Листинг 1.6 – продолжение листинга 1.5, т.е. векторы и заданы. На рис. 1.6 показано создание пользовательской функции для построения многочлена Лагранжа по формуле (1.1): , где используется обозначение , – аргумент многочлена, – его порядок. При создании этой функции, используются оператор суммирования и оператор вычисления произведения Рис. 1.6. Построение многочлена Лагранжа В одном шаблоне построены: – график многочлена Лагранжа на промежутке наивысшей степени ; – векторы и , задающие аппроксимируемую функцию. Условный оператор if при такой конструкции пользовательской функции, набирается не с клавиатуры, а с вкладки Все функции, опции Кусочно-непрерывные, а оператор с вкладки Сравнение, группы Операторы. Интерполяционный многочлен Ньютона Интерполяционный многочлен Ньютона для функции , заданной табличными значениями , , в случае равноотстоящих узлов , , где , записывается в виде , где , , ..., так называемые конечные разности. Рис. 1.7. Формирование матрицы конечных разностей Если векторы и заданы (рис. 1.5), то для построения многочлена Ньютона следует: 1) задать степень многочлена и размерности массивов и через встроенную функцию last, или (рис. 1.7). 2) сформировать матрицу – матрицу конечных разностей, в которой: – нулевой столбец – столбец значений , , т.е. , , – –й столбец – столбец конечных разностей –го порядка, т.е. , , (рис. 1.7); 3) построить многочлен Ньютона, создав функцию , параметрами которой являются ее аргумент и порядок. На рисунке 1.8 сформирован многочлен Ньютона для равноотстоящих узлов , , а также в одном шаблоне построены: – график многочлена Ньютона на промежутке наивысшей степени ; – векторы и , задающие аппроксимируемую функцию. Рис. 1.8. Построение многочлена Ньютона Построение интерполяционного многочлена методом наименьших квадратов Рис. 1.9. Построение интерполяционного многочлена методом наименьших квадратов Для построения интерполяционного многочлена методом наименьших квадратов можно использовать пару встроенных функций regress и interp (bt, X, Y, t) (они используются только вместе). Параметрами этих функций являются: – – векторы узлов интерполирования и значений функции; – – порядок аппроксимации; – – переменная интерполяционного многочлена; – – вектор вторых производных (вычисляется через ). На рисунке 1.9 описано построение интерполяционного многочлена порядка 7 для уже заданных векторов и (рис. 1.5), через пару функций regress и interp, а также построен его график на промежутке в одном шаблоне с вектором . Интерполяция линейными, квадратичными и кубическими сплайнами Интерполяция линейными сплайнами функции в пакете Mathcad Prime проводится через встроенную функцию , где – массив точек , – массив точек , – точка, в которой вычисляется значение аппроксимирующей функции. На рисунке 1.10 показана интерполяция линейными сплайнами функции, заданной в таблице 1.2. На построенном графике линейного сплайна отмечены точки , по которым проведена линейная интерполяция. Рис. 1.10. Интерполяция линейными сплайнами Функции вычисления коэффициентов кубического, квадратичного и линейного сплайнов имеют вид: , , , где – массив точек , – массив точек . При этом функция , где – массив коэффициентов сплайна, – массив точек , – массив точек , возвращает значение интерполяционного многочлена в точке . Интерполяция сплайнами показана на рисунке 1.11 для функции, заданной в таблице 1.2. На одном графике показана интерполяция кубическими сплайнами – функция fc(t), квадратичными – функция f p (t), и линейными – функция f l (t), из вида которых ясно, что в пределах таблицы они практически совпадают, а существенное отличие при интерполяции линейными сплайнами происходит за пределами таблицы. Рис.1.11. Интерполяция кубическими, квадратичными и линейными сплайнами Задачи для самостоятельного решения Задача 1.1. Для функции , заданной таблицей, построить многочлены Лагранжа и Ньютона наивысшего порядка, а также методом наименьших квадратов, построить аппроксимирующий многочлен и провести интерполирование квадратичными, кубическими и линейными сплайнами. Сравнить результаты. Вариант 1 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,09 0,18 0,26 0,34 0,41 0,47 0,53 0,59 Вариант 2 0,2 0,6 1,0 1,4 1,8 2,2 2,6 3,0 0,18 0,47 0,69 0,87 1,03 1,16 1,28 1,39 Вариант 3 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 0,74 0,79 0,83 0,89 0,92 0,96 0,99 1,03 Вариант 4 1,2 1,6 2,0 2,4 2,8 3,2 3,6 4,0 0,79 0,96 1,10 1,22 1,34 1,44 1,54 1,61 Вариант 5 1,0 1,2 1,4 1,6 1,8 2,0 2,2 2,4 0,69 0,79 0,87 0,96 1,03 1,10 1,16 1,22 Вариант 6 0,0 0,2 0,4 0,6 0,8 1,0 1,2 1,4 0,00 0,18 0,34 0,47 0,59 0,69 0,79 0,87 Вариант 7 0,0 0,25 0,50 0,75 1,00 1,25 1,50 1,75 0,00 0,22 0,41 0,56 0,69 0,81 0,92 1,02 Вариант 8 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 0,69 1,10 1,39 1,61 1,79 1,95 2,08 2,20 Вариант 9 1,3 1,6 1,9 2,2 2,5 2,8 3,1 3,4 0,83 0,96 1,06 1,16 1,25 1,33 1,41 1,48 Вариант 10 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 0,00 0,41 0,69 0,92 1,10 1,25 1,39 1,50 Вариант 11 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,74 0,79 0,83 0,88 0,92 0,96 0,99 1,03 Вариант 12 0,00 0,25 0,50 0,75 1,00 1,25 1,50 1,75 0,69 0,81 0,92 1,01 1,10 1,18 1,25 1,32 Вариант 13 0,0 0,3 0,6 0,9 1,2 1,5 1,8 2,1 0,69 0,83 0,96 1,06 1,16 1,25 1,33 1,41 Вариант 14 1,0 1,3 1,6 1,9 2,2 2,5 2,8 3,1 1,10 1,19 1,28 1,36 1,43 1,50 1,57 1,63 Вариант 15 0,2 0,4 0,6 0,8 1,0 1,2 1,4 1,6 0,79 0,87 0,96 1,03 1,10 1,16 1,22 1,28 Вариант 16 1,0 1,2 1,4 1,6 1,8 2,0 2,2 2,4 1,10 1,16 1,22 1,28 1,33 1,39 1,43 1,48 Вариант 17 1,2 1,6 2,0 2,4 2,8 3,2 3,6 4,0 1,16 1,28 1,39 1,48 1,57 1,65 1,72 1,79 Вариант 18 0,0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 0,69 0,92 1,10 1,25 1,39 1,50 1,61 1,71 Вариант 19 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 1,10 1,38 1,61 1,79 1,95 2,08 2,20 2,30 Вариант 20 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 1,10 1,25 1,39 1,50 1,61 1,70 1,79 1,87 Вариант 21 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,99 0,97 0,94 0,90 0,87 0,86 0,85 0,86 Вариант 22 0,00 0,25 0,50 0,75 1,00 1,25 1,50 1,75 1,00 0,95 0,88 0,86 1,00 1,39 2,12 3,30 Вариант 23 0,0 0,3 0,6 0,9 1,2 1,5 1,8 2,1 1,00 0,94 0.86 0,92 1,29 2,13 3,59 5,85 Вариант 24 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,00 1,12 1.29 1,51 1,78 2,13 2,54 3,02 Вариант 25 0,2 0,4 0,6 0,8 1,0 1,2 1,4 1,6 0,97 0,90 0,86 0,87 1,0 1,29 1,78 2,53 Вариант 26 1,0 1,2 1,4 1,6 1,8 2,0 2,2 2,4 1,00 1,29 1,78 2,54 3,59 5,00 6,81 9,06 Вариант 27 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,12 1,29 1,51 1,78 1.13 2,54 3,02 3,59 Вариант 28 0,05 0,10 0,15 0,20 0,25 0,30 0,35 0,40 1,00 0,99 0,98 0,97 0,95 0,94 0,92 0,90 Вариант 29 1,0 1,05 1,10 1,15 1,20 1,25 1,30 1,35 1,00 1,06 1,12 1.20 1.29 1.39 1,51 1,64 Вариант 30 – 0,3 0,0 0,3 0,6 0,9 1,2 1,5 1,8 0,88 1,00 0,94 0,86 0,92 1,29 2,13 3,59