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



Дата16.12.2021
өлшемі189,48 Kb.
#101697
түріЗадача
Байланысты:
3 interpolation

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

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

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

интерполяция

fi , xi

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



аппроксимация

fi , xi

g(x)

f1

x1

f2

x2





fi

xi





fn

xn

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

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

y1

x1

y2

x2





yi

xi





yn

xn

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

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

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

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

xi

xi+1

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

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

xi

xi+1

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


Достарыңызбен бөлісу:




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет