Методы интерполяции Интерполяция, экстраполяция, аппроксимация

Методы интерполяции

Интерполяция, экстраполяция, аппроксимация

• Интерполяция – определение промежуточных значений функции по известному дискретному набору значений функции
• Экстраполяция – определение значений функции за пределами первоначально известного интервала
• Аппроксимация – определение в явном виде параметров функции, описывающей распределение точек

экстраполяция

Задача интерполяции

• Пусть функция f(x) задана таблицей своих значений xi, yi: на интервале [a; b]:
• Задача интерполяции - найти функцию F(x), принимающую в точках xi те же значения yi
• точки xi – узлы интерполяции
• условие F(x)= yi – условие интерполяции
• Через заданные точки можно провести бесконечно много кривых, для каждой из которых выполнены все условия интерполяции
• Для практики важен случай аппроксимации функции многочленами:

Локальная и глобальная интерполяция

• Глобальная интерполяция
• функция f(x) интерполируется на всем интервале [a; b] с помощью единого интерполяционного полинома
• обычно m=n, т.е. степень полинома выбирается равной количеству узлов
• на практике не всегда применима
• Локальная (кусочно-полиномиальная) интерполяция
• на каждом интервале [xi , xi+1 ] строится отдельный интерполяционный полином невысокой степени

Кусочно-линейная интерполяция

• Узловые точки соединяются отрезками прямых
• через каждые две точки xi , xi+1 проводится полином первой степени:
• коэффициенты a0 , a1 разные на каждом интервале [xi , xi+1 ]:

Кусочно-квадратичная интерполяция

• Квадратичная интерполяция проводит через узловые точки уравнение параболы:
• коэффициенты a0 , a1 , a2 разные на каждом интервале[xi , xi+1 ]:

Многочлен Лагранжа

• На всем интервале [a; b] строится единый полином:
• где li(x) – базисные полиномы степени n:
• имеет малую погрешность при небольших значениях n<20. При больших n погрешность начинает расти
• применимо как для равноотстоящих, так и для не равноотстоящих узлов.
• кусочно-линейная и кусочно-квадратичная локальные интерполяции - частные случаи интерполяции многочленом Лагранжа.

Многочлен Ньютона (разделенные разности)

• Разделенные разности нулевого порядка совпадают со значениями функции в узлах
• Разделенные разности первого порядка:
• определяются через разделенные разности нулевого порядка
• Разделенные разности второго порядка:
• определяются через разделенные разности нулевого порядка
• Разделенная разность k-го порядка:
• определяются через разделенные разности порядка k - 1

Многочлен Ньютона

• где , , , - разделенные разности 1, 2, 3, n-го порядков
• если необходимо увеличить степень многочлена на единицу, добавив в таблицу еще один узел
• для многочлена Лагранжа необходимо вычислять каждое слагаемое заново
• для многочлена Ньютона достаточно добавить одно слагаемое
• Если функция достаточно гладкая, то:
• Погрешность интерполяции:

.

Лабораторная работа №3

• Сгенерировать выборку функции (размером 10 элементов). Выполнить интерполяцию кусочно-линейным и кусочно-квадратичным методами, а также интерполяционными многочленами Лагранжа и Ньютона, и перейти на выборку размером 100 точек.
• Прочитать из файла выборку и перейти на другую размерность выборки при помощи интерполяции кусочно-линейным и кусочно-квадратичным методами.
• Задание оценивается в баллах:
• 4 балла - выполнение локальной интерполяции + 1 балл первому кто выполнит задание
• 3 балла – выполнение глобальной интерполяции + 0.5 балла первому кто выполнит задание (по желанию)
• 4 балла - переход на другую размерность выборки + 1 балл первому кто выполнит задание
• + 2 балла - выполнение работы в срок

Переход на новую размерность выборки

• Преобразование Фурье (лекция №5) – быстрые алгоритмы работают наиболее эффективно с выборками, размерность которых является 2n, т.е. 2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048 и т.д.
• Если предыдущие вычисления были выполнены для другой размерности выборки, необходимо перейти на выборку другого размера
• например:
• было 100, стало 128
• было 512, стало 501