интерполяция. Реферат по дисциплине Математическое моделирование на тему Интерполяция Промзелева Е. С. Номер зачетной книжки 185038
![]()
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «Ивановский государственный политехнический университет» ![]() Институт информационных технологий, естественных и гуманитарных наук Кафедра информационных технологий и сервиса РЕФЕРАТ по дисциплине Математическое моделирование на тему: «Интерполяция» Выполнил: Промзелева Е.С. Номер зачетной книжки: 185038 Направление подготовки: 28.03.02 Наноинженерия Курс, группа: НИ-31 Проверил: д.т.н., проф.Коробов Н.А. Оценка_____________ Подпись ___________ Дата _______________ СодержаниеВведение 3 1 Определение интерполяции и информация о применении интерполяции 4 2 Перечисление известных методов интерполяции с указанием их достоинств и недостатков 5 2.1 Интерполяция методом ближайшего соседа 5 2.2 Интерполяция многочленами 5 2.3 Обратное интерполирование (вычисление x при заданной y) 6 2.4 Интерполяция функции нескольких переменных 7 2.5 Другие способы интерполяции 7 3 Подробное описание двух методов 8 3.1 Кубический сплайн 8 3.2 Линейная интерполяция 12 Заключение 14 Список литературы 15 Введение Аппроксимация функций заключается в приближенной замене заданной функции f(x) некоторой функцией j(x) так, чтобы отклонение функции j(x) от f(x) в заданной области было наименьшим. Функция j(х) при этом называется аппроксимирующей. Типичной задачей аппроксимации функций является задача интерполяции. Необходимость интерполяции функций в основном связана с двумя причинами: 1. Функция f(x) имеет сложное аналитическое описание, вызывающее определенные трудности при его использовании (например, f(x) является спец функцией: гамма-функцией, эллиптической функцией и др.). 2. Аналитическое описание функции f(x) неизвестно, т. е. f(x) задана таблично. При этом необходимо иметь аналитическое описание, приближенно представляющее f(x) (например, для вычисления значений f(x) в произвольных точках, определения интегралов и производных от f(x) и т. п.). 1 Определение интерполяции и информация о применении интерполяции Интерполяция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчётами, часто приходится оперировать наборами значений, полученных опытным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных. Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах. Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина и теорема Марцинкевича, являющиеся основой для множества других работ . 2 Перечисление известных методов интерполяции с указанием их достоинств и недостатков 2.1 Интерполяция методом ближайшего соседа Метод интерполяции, при котором в качестве промежуточного значения выбирается ближайшее известное значение функции. Интерполяция методом ближайшего соседа является самым простым методом интерполяции. 2.2 Интерполяция многочленами На практике чаще всего применяют интерполяцию многочленами. Это связано, прежде всего, с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций (теорема Вейерштрасса). Преимущества: Для заданного набора точек и сетки параметра кривая строится однозначно. Кривая является интерполяционной, то есть проходит через все заданные точки. Кривая имеет непрерывные производные любого порядка. Недостатки: С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой. С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции Линейная интерполяция - интерполяция алгебраическим двучленом P1(x) = ax + b функции f, заданной в двух точках x0 и x1 отрезка [a, b]. В случае если заданы значения в нескольких точках, функция заменяется кусочно-линейной функцией. Интерполяционная формула Ньютона - формулы вычислительной математики, применяющиеся для полиномиального интерполирования. Если узлы интерполяции, равноотстоящие и упорядочены по величине, так что, то есть, то интерполяционный многочлен можно записать в форме Ньютона. Интерполяционные полиномы в форме Ньютона удобно использовать, если точка интерполирования находится вблизи начала (прямая формула Ньютона) или конца таблицы (обратная формула Ньютона). Сплайн-функция - функция, область определения которой разбита на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1. Сплайны имеют многочисленные применения, как в математической теории, так и в разнообразных вычислительных приложениях. В частности, сплайны двух переменных интенсивно используются для задания поверхностей в различных системах компьютерного моделирования. Кубический сплайн - Некоторая функция f(x) задана на отрезке , разбитом на части . Кубическим сплайном дефекта 1 называется функция , которая: на каждом отрезке является многочленом степени не выше третьей; имеет непрерывные первую и вторую производные на всём отрезке ; в точках выполняется равенство, т. е. сплайн интерполирует функцию f в точках. Для однозначного задания сплайна перечисленных условий недостаточно, для построения сплайна необходимо наложить какие-то дополнительные требования. Естественным кубическим сплайном называется кубический сплайн, удовлетворяющий также граничным условиям вида. 2.3 Обратное интерполирование (вычисление x при заданной y) Полином Лагранжа-многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n+1 пар чисел (x0, y0), (x1, y1),..., (xn, yn), где все xj различны, существует единственный многочлен степени не более, для которого. В простейшем случае (n=1)— это линейный многочлен, график которого — прямая, проходящая через две заданные точки. 2.4 Интерполяция функции нескольких переменных Билинейная интерполяция — в вычислительной математике расширение линейной интерполяции для функций двух переменных. Ключевая идея заключается в том, чтобы провести обычную линейную интерполяцию сначала в одном направлении, затем в другом. Недостаток метода: Главным минусом билинейной интерполяции при масштабировании изображений является тот факт, что при увеличении в раз изображения размером на пикселей в результате будет получено изображение размером не на пикселей, а на пикселей. Связано это с тем, что в исходном изображении, например, по горизонтали имеется точек, то есть смежных пар. При увеличении изображения в раз между каждой парой основных точек вставляется дополнительных точек (то есть при увеличении вдвое между основными точками вставляется еще по одной, при увеличении втрое — по две и т. д.). Итого в результате ширина результирующего изображения будет равна сумме количества основных и дополнительных точек: проще говоря, для последнего пикселя (в каждой строке и столбце) исходного изображения не находится пары, с которой можно было бы провести интерполирование. Бикубическая интерполяция - в вычислительной математике расширение кубической интерполяции на случай функции двух переменных, значения которой заданы на двумерной регулярной сетке. Поверхность, полученная в результате бикубической интерполяции является гладкой функцией, в отличие от поверхностей, полученных в результате билинейной интерполяции или интерполяции методом ближайшего соседа. Так же бикубическая интерполяция часто используется в обработке изображений, давая более качественное изображение по сравнению с билинейной интерполяцией. 2.5 Другие способы интерполяции Рациональная интерполяция - представление интерполируемой функции (точнее говоря, ряда табличных значений) в виде отношения двух полиномов. Ряд функций, плохо интерполируемых полиномиальными методами, удаётся хорошо приблизить рациональной функцией с полиномом в числителе и знаменателе. Особенно это касается функций с нерегулярным характером поведения (в частности, рациональная интерполяция хорошо подходит для функций с особыми точками резкими изменениями). 3 Подробное описание двух методов 3.1 Кубический сплайн Кубические сплайны - это мощное и удобное средство, но и они небезупречны: необходимо учитывать влияние направления и величины касательных векторов, указывать все точки кривой до ее изображения, невозможна локальная коррекция кривой. Последнее особенно важно для интерактивной работы. Расчет кубического сплайна требует обращения большой матрицы, зависящей от всех элементов сплайна; т.е. изменение любого сегмента затрагивает все остальные сегменты. Воздействие уменьшается при удалении от точки возмущения, но полностью пренебречь им нельзя. Параболическая интерполяция разрешает большинство этих проблем за счет того, что она только непрерывна, т. е. в точках соединения сегментов сохраняется непрерывность лишь первой производной. Для многих прикладных задач этого достаточно, причем параболическая интерполяция не требует больших расчетов. Параболическая интерполяция была разработана Оверхаузером (Рис.1.). Оверхаузер строил кривую интерполяции, исходя из геометрических соображений. Идея состоит в линейной интерполяции пересекающихся частей двух парабол. Параболы заданы четырьмя последовательными точками: первая - тремя первыми точками, вторая - тремя последними. Пересечение лежит между второй и третьей точками. ![]() Рис.1. Параболическая интерполяция. Несмотря на то, что параболы-плоские кривые, их линейная интерполяция это кубическая пространственная кривая, как показано на рис.1. Рассмотрим обобщенный вывод для всего семейства. Параболически интерполированная кривая имеет вид С (t) = (1-t) p (r) + t q (s), (1) где r, s, t - параметры, p(r), q(s) - параметрические параболы, проходящие через P1, P2, P3 и P2, P3, P4, соответственно, как показано на рис.2. Для простоты параболы на рис.2 лежат в одной плоскости, но это не обязательно. Параметрическое представление p(r) и q(s) следующее: p (r) = [r2 r 1] [B], (2) q (s) = [s2 s 1] [D], (3) где [B] и [D] - матрицы, представляющие положение вектор-точек P1, P2, P3 и P2, P3, P4, соответственно. Результат интерполяции - кубическая кривая C (t) = [ t3 t2 t 1] [A] [G] = [T] [A] [G], (4) ![]() Рис.2. Обозначение для параболической интерполяции. Чтобы определить [B] и [D], а затем [A] и [G], необходимо установить связь между параметрами r, s, t. Из рис.2., замечая, что r меняется от 0 до 1 на сегменте от P1 до P3 вдоль p(r), s меняется от 0 до 1 на сегменте от P2 до P4 вдоль q(s), и t меняется от 0 до 1 на сегменте от P2 до P4 вдоль C(t), разумно предположить, что r и t, а также s и t связаны линейно. Отсюда r = k1t+k2, s = k3t+k4, (5) где ki - константы, заданные граничными условиями в вектор-точках P1, P2, P3 и P4. Предположим, что данные распределены равномерно или почти равномерно, и диапазон параметров нормализован, т.е. 0 ![]() p (0) = P1, p (1\2) = P2, p (1) = P3, (6а) q (0) = P2, q (1\2) = P3, q (1) = P4, (6b) C (0) = P2, C (1) = P4. (6с) Здесь основные предположения таковы: p(r)=P2 для r=1\2 и q(s)=P3 для s=1\2. В результате получаем единственный член семейства параболических интерполированных кривых, как будет показано ниже. В предположениях уравнений (5) @P2: r=1\2, t=0 ![]() @P3: r=1, t=1 ![]() ![]() @P2: s=0, t=0 ![]() @P3: s=1\2, t=1 ![]() Итак r (t) = ![]() ![]() Вспомним уравнение (2) и используем уравнение (6а), чтобы выразить [B] через P1, P2, P3, p (0) = P1 = [0 0 1] [B], (8а) p (1\2) = P2 = [1\4 1\2 1] [B], (8b) p (1) = P3 = [1 1 1] [B]. (8с) Запишем в виде одной матрицы ![]() Отсюда [B]= ![]() ![]() Аналогично через P2, P3, P4 находится выражение [D]. Пользуясь уравнением (6b), получаем q (0) = P2 = [0 0 1] [D], (10a) q (1\2) = P3 = [ 1\4 1\2 1] [D], (10b) q (1) = P4= [1 1 1] [D]. (10c) Сравнение с уравнениями (8) сразу же дает ![]() ![]() Вспомним уравнение (1) и подставим уравнения (2) и (3): C (t) = (1-t) [r2 r 1] [B] + t [s2 s 1] [D]. Используем уравнение (7), чтобы переписать это только в терминах параметра t, C (t) = [- ![]() ![]() ![]() Подставив [B] и [D] из уравнений (9) и (11), получим C (t) = [- ![]() ![]() ![]() ![]() ![]() ![]() ![]() Перепишем уравнение так, чтобы включить все четыре точки P1, P2, P3, P4: ![]() ![]() Наконец, перепишем результат в форме уравнения (4) C (t) = [t3 t2 t 1] [A][G]=[T][A][G], (4) где ![]() и [G]T=[P1 P2 P3 P4]. (13) Заметим, что результат имеет вид произведения матрицы интерполяционных функций и геометрической матрицы. 3.2 Линейная интерполяция Простейшим и часто используемым видом локальной интерполяции является линейная интерполяция. Она состоит в том, что заданные точки (xi, yi) при (i = 0. 1, ..., n) соединяются прямолинейными отрезками, и функция f(x) приближается ломаной с вершинами в данных точках. Уравнения каждого отрезка ломаной в общем случае разные. Поскольку имеется n интервалов (xi-1,xi), то для каждого из них в качестве уравнения интерполяционного многочлена используется уравнение прямой, проходящей через две точки. В частности, для i-го интервала можно написать уравнение прямой, проходящей через точки(xi-1,yi-1) и (xi,yi), в виде ![]() ![]() Отсюда
ai= ![]() Следовательно, при использовании линейной интерполяции сначала нужно определить интервал, в который попадает значение аргумента х, а затем подставить его в формулу (*) и найти приближенное значение функции в этой точке. ![]() Рис.3. График зависимости линейной интерполяции. Заключение В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например, полученным в ходе некоторого эксперимента. Для вычисления многих функций, оказывается, эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений. Основным недостатком полиномиальной интерполяции является то, что она неустойчива на одной из самых удобных и часто используемых сеток - сетке с равноудаленными узлами. Если позволяет задача, эту проблему можно решить за счет выбора сетки с Чебышевскими узлами. Если же мы не можем свободно выбирать узлы интерполяции или нам просто нужен алгоритм, не слишком требовательный к выбору узлов, то рациональная интерполяция может оказаться подходящей альтернативой полиномиальной интерполяции. К достоинствам сплайн-интерполяции следует отнести высокую скорость обработки вычислительного алгоритма, поскольку сплайн - это кусочно-полиномиальная функция и при интерполяции одновременно обрабатываются данные по небольшому количеству точек измерений, принадлежащих к фрагменту, который рассматривается в данный момент. Интерполированная поверхность описывает пространственную изменчивость различного масштаба и в то же время является гладкой. Последнее обстоятельство делает возможным прямой анализ геометрии и топологии поверхности с использованием аналитических процедур. Список литературы Б.В.Соболь, Б.Ч.Месхи, И.М.Пешхоев. Практикум по вычислительной математике. - Ростов-на-Дону: Феникс, 2008; Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003 Н.Н. Калиткин . Численные методы. – М.: Наука, 1982. Г.И. Марчук . Методы вычислительной математики – М.: Наука, 1977. В.В. Носач. Решение задач аппроксимации с помощью персональных компьютеров.. М.: Бином, 1994 А.А. Самарский. Численные методы. – М.: Наука, 1989. Иваново 2020 |