Интерполяция функций двух переменных, проблема выбора узлов

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Введение

Постановка математической задачи

Интерполя́ция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.

Рассмотрим систему несовпадающих точек ~(x_i , y_i) (i\in{1,\dots,N}) из некоторой области ~D. Пусть значения функции ~f известны только в этих точках:

z_i = f(x_i,y_i),\quad i=1,\ldots,N.
  • Точки ~(x_i , y_i) называют узлами интерполяции, а их совокупность — интерполяционной сеткой.
  • Тройки ~(x_i,y_i,z_i) называют точками данных или базовыми точками

Задача интерполяции состоит в поиске такой функции ~F из заданного класса функций, что

F(x_i,y_i) = z_i,\quad i=1,\ldots,N.
F(x,y) максимально приближает функцию f(x,y) в произвольной точке (x,y) внутри интерполяционной сетки.
  • Функцию ~F(x) — называют интерполирующей функцией .

Изложение метода

Проблема выбора узлов

Рассмотрим задачу интерполяции полиномами:
I. Заметим что не любое число узлов интерполяции выгодно. Если для одной переменной степень многочлена была взаимно однозначно связана с числом узлов, то для двух переменных многочлен n-ой степени P_n(x,y)=\sum_{k+m=0}^na_{km}x^ky^m\ имеет (n+1)(n+2)/2 узлов. Если число узлов не соответствует этой формуле, то часть коэффициентов при высших степенях должна задаваться принудительно (в частности нулями): для выбора этих коэффициентов редко есть разумные основания.
II. Также не всякое расположение узлов допустимо: в одномерном случае узлы не должны были совпадать. Теперь же для интерполяции многочеленом P_1(x,y) необходимо, чтобы узлы не лежали на прямой в плоскости (x,y). При интерполяции многочленом P_n(x,y) требуется, чтобы узлы не лежали на кривой n-го порядка.
Поэтому для хорошей интерполяции сетка должна быть регулярно построенной, а не представлять собой совокупность беспорядочно расположенных точек. Следущие два примера используют прямоугольную сетку, образованную пересечением прямых x = xn, n = 0, ..., N и y = ym, m = 0, ..., M,

fnm = f(xn, ym) — значение функции в узле {xn, ym }.

Билинейная интерполяция

Билинейной интерполяцией называют расширение линейной интерполяции для функций двух переменных. Для начала реализуется линейная интерполяция по x на каждой прямой y = ym . Затем при каждом значении x = xn реализуется линейная интерполяция по y с учетом значений функции, полученных на первом шаге.
Пусть \ x\in[x_n,x_n_+_1],\ \ y\in[y_m,y_m_+_1]

f(x,y)\approx \ f_{nm}\frac{(x_{n+1}-x)(y_{m+1}-y)}{(x_{n+1}-x_n)(y_{m+1}-y_m)}\ \ \ +\ \ \ f_{n+1,m}\frac{(x-x_n)(y_{m+1}-y)}{(x_{n+1}-x_n)(y_{m+1}-y_m)}+<br/>\ \ \ \ \ \ \ \ \ \ \ \ +f_{n,m+1}\frac{(x-x_n)(y-y_m)}{(x_{n+1}-x_n)(y_{m+1}-y_m)}\ +\ f_{n+1,m+1}\frac{(x_{n+1}-x)(y-y_m)}{{(x_{n+1}-x_n)(y_{m+1}-y_m)}

Результат билинейной интерполяции не зависит от порядка шагов: можно сначала интерполировать вдоль оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же.

Интерполяционный многочлен Лагранжа

Интерполяционный многочлен Лагранжа - многочлен минимальной степени, принимающий данные значения в данном наборе точек.

Для двумерного случая многочлен выглядит следующим образом

L(x) = \sum_{n=0}^N \sum_{m=0}^M f_{nm} l_{nm}(x,y)


l_{nm}(n,m)=1
l_{nm}(x,y)=0 при x\ne n\ V \ y\ne m

базисные полиномы вычисляются по следующей формуле:

l_{nm}(x,y)=\prod_{i=0 \\i \ne n}^N\ \prod_{j=0 \\j\ne m}^M\frac{(x-x_i)(y-y_j)}{(x_n-x_j)(y_m-y_j)}

Отсюда следует, что L(x), как линейная комбинация lnm(x,y), может иметь степень не больше n×m, и по определению L(xn,ym)=f(xn,ym)

Числовой пример

Изображение:Function.jpg
На Рис.1 исходная функция двух переменных ( значение функции в точке - уровень серого 0..255)
На Рис.2 сверху функция полученная с помощью билинейной интерполяции при сетке размера 6×6, на этом же рисунке снизу показана абсолютная разность между исходным изображанием и интерполируещей функцией.
На Рис.3 изображено то же что и на Рис.2 только с сеткой 11×11.

Рекомендации программисту

Исходный код

Код программы на языке С++, вычисляющий приближенное значение функции по методу билинейной интеполяции
Полный проект для Microsoft Visual Studio 2008, вычисляющий приближенное значение функции по методу билинейной интеполяции

Выбор шага сетки

Если перед нами стоит задача интерполяции функции, как упрощение некой трудновычислимой функции, т.е. мы сами можем выбирать узлы сетки и соответственно её шаг, то возникает вопрос насколько нам дробить сетку? При делении сетки пополам можно рассматривать следующий параметр fточное(хi+1/2) - точное значение функции на k+1 итерации минус fприближенное(½(хi+хi+1)) - приближенное значение в той же точке на k-ой итерации и деленое все на точное(хi+1/2). Также эти значения можно усреднить по всем узлам решётки, и при некотором его значении (например < 0.01) прекратить деление.

Случай не прямоугольной сетки

Заключение

Список литературы

  • А.А.Самарский, А.В.Гулин.  Численные методы М.: Наука, 1989.
  • А.А.Самарский.  Введение в численные методы М.: Наука, 1982.
  • Н.Н.Калиткин.  Численные методы М.: Наука, 1978.

См. также

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9_%D0%B4%D0%B2%D1%83%D1%85_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85%2C_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0_%D1%83%D0%B7%D0%BB%D0%BE%D0%B2»
Личные инструменты