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

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

(Различия между версиями)

Текущая версия

Содержание

1 Введение
- 1.1 Постановка математической задачи
2 Изложение метода
3 Числовой пример
4 Рекомендации программисту
5 Список литературы
6 См. также

Введение

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

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

Рассмотрим систему несовпадающих точек $~(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 = x_n, n = 0, ..., N и y = y_m, m = 0, ..., M,

f_nm = f(x_n, y_m) — значение функции в узле {x_n, y_m }.

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

Билинейной интерполяцией называют расширение линейной интерполяции для функций двух переменных. Для начала реализуется линейная интерполяция по x на каждой прямой y = y_m . Затем при каждом значении x = x_n реализуется линейная интерполяция по 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), как линейная комбинация l_nm(x,y), может иметь степень не больше n×m, и по определению L(x_n,y_m)=f(x_n,y_m)

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

На Рис.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) прекратить деление.

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

Такая ситуация возникает когда базовыми точками, например, являются данные эксперимента, и нам необходимо проинтерполировать их на все мн-во промежуточных значений. Тогда надо проводить интерполяцию по трем точкам: если f_A, f_B, f_С — значение функции f(x, y) в вершинах A, B, С некоторого, то вычислить приближенное значение функции внутри этого треугольника можно с помощью билинейной функции f(x, y) ≈ F(x, y) = ax + by + c, находя коэффициенты a, b, c из условий

ax_A + by_A + c = f_A, ax_B + by_B + c = f_B, ax_С + by_С + c = f_С, где {x_A, y_A}, {x_B, y_B}, {x_С, y_С} - координаты вершин A, B , С . Погрешность такой интерполяции для функции f(x, y) с непрерывными вторыми производными будет O(h2) , где h — длина наибольшей стороны треугольника АВС.

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

А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 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»

Категории: Численное интегрирование | Учебные задачи

@@ Строка 3: / Строка 3: @@
 '''Интерполя́ция'''&nbsp;— в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.
-Рассмотрим систему несовпадающих точек  <tex>~(x_i , y_i)</tex>  (<tex>i\in{0,1,\dots,N}</tex>) из некоторой области <tex>~D</tex>. Пусть значения функции <tex>~f</tex> известны только в этих точках:
+Рассмотрим систему несовпадающих точек  <tex>~(x_i , y_i)</tex>  (<tex>i\in{1,\dots,N}</tex>) из некоторой области <tex>~D</tex>. Пусть значения функции <tex>~f</tex> известны только в этих точках:
 : <tex>z_i = f(x_i,y_i),\quad i=1,\ldots,N.</tex>
+* Точки <tex>~(x_i , y_i)</tex> называют '''узлами интерполяции''', а их совокупность — '''интерполяционной сеткой'''.
+* Тройки <tex>~(x_i,y_i,z_i)</tex> называют '''точками данных''' или '''базовыми точками'''
 Задача интерполяции состоит в поиске такой функции <tex>~F</tex> из заданного класса функций, что
 : <tex>F(x_i,y_i) = z_i,\quad i=1,\ldots,N.</tex>
+: <tex>F(x,y)</tex>  максимально приближает функцию <tex>f(x,y)</tex> в произвольной точке <tex>(x,y)</tex> внутри интерполяционной сетки.
-* Точки <tex>~(x_i , y_i)</tex> называют '''узлами интерполяции''', а их совокупность — '''интерполяционной сеткой'''.
-* Тройки <tex>~(x_i,y_i,z_i)</tex> называют '''точками данных''' или '''базовыми точками'''.
-* Разность между «соседними» значениями <tex>~\Delta x_i=x_i-x_{i-1}</tex> — '''шагом интерполяционной сетки'''. Он может быть как переменным так и постоянным.
 * Функцию <tex>~F(x)</tex> — называют '''интерполирующей функцией''' .
 == Изложение метода ==
-Пусть сетка образована пересечением прямых x = x<sub>n</sub>, n = 0, ..., N и y = y<sub>m</sub>, m = 0, ..., M, f<sub>nm</sub> = f(x<sub>n</sub>, y<sub>m</sub>) — значение функции в узле {x<sub>n</sub>, y<sub>m</sub> }.
+=== Проблема выбора узлов ===
-=== Билинейная интерполяция ===
+Рассмотрим задачу [[Интерполяция каноническим полиномом|интерполяции полиномами]]: <br />
+'''I.''' Заметим что не любое число узлов интерполяции выгодно. Если для одной переменной степень многочлена была взаимно однозначно связана с числом узлов, то для двух переменных многочлен ''n''-ой степени <tex>P_n(x,y)=\sum_{k+m=0}^na_{km}x^ky^m\ </tex>  имеет (n+1)(n+2)/2 узлов. Если число узлов не соответствует этой формуле, то часть коэффициентов при высших степенях должна задаваться принудительно (в частности нулями): для выбора этих коэффициентов редко есть разумные основания. <br />
+'''II.''' Также не всякое расположение узлов допустимо: в одномерном случае узлы не должны были совпадать. Теперь же для интерполяции многочеленом <tex>P_1(x,y)</tex> необходимо, чтобы узлы не лежали на прямой в плоскости <tex>(x,y)</tex>. При интерполяции многочленом <tex>P_n(x,y)</tex> требуется, чтобы узлы не лежали на кривой n-го порядка.  <br />
+Поэтому для хорошей интерполяции сетка должна быть регулярно построенной, а не представлять собой совокупность беспорядочно расположенных точек. Следущие два примера используют прямоугольную сетку, образованную пересечением прямых x = x<sub>n</sub>, n = 0, ..., N и y = y<sub>m</sub>, m = 0, ..., M, <br />
+::f<sub>nm</sub> = f(x<sub>n</sub>, y<sub>m</sub>) — значение функции в узле {x<sub>n</sub>, y<sub>m</sub> }.
-Билинейной интерполяцией называют расширение линейной интерполяции для функций двух переменных. Для этого сначала реализуется линейная интерполяция по x на каждой прямой y = y<sub>m</sub> . Затем при каждом значении x = x<sub>n</sub> реализуется линейная интерполяция по y с учетом значений функции, полученных на первом шаге.<br/>
+=== Билинейная интерполяция ===
+'''Билинейной интерполяцией''' называют расширение линейной интерполяции для функций двух переменных.
+Для начала реализуется линейная интерполяция по x на каждой прямой y = y<sub>m</sub> . Затем при каждом значении x = x<sub>n</sub> реализуется линейная интерполяция по y с учетом значений функции, полученных на первом шаге.<br/>
 Пусть  <tex>\ x\in[x_n,x_n_+_1],\ \ y\in[y_m,y_m_+_1]</tex><br/>
 ::<tex>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)}</tex><br/>
-Результат билинейной интерполяции не зависит от порядка шагов: можно сначала интерполировать вдол оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же.
+Результат билинейной интерполяции не зависит от порядка шагов: можно сначала интерполировать вдоль
+оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же.
+=== Интерполяционный многочлен Лагранжа ===
+[[Интерполяция полиномами Лагранжа и Ньютона|'''Интерполяционный многочлен Лагранжа''']] - многочлен минимальной степени, принимающий данные значения в данном наборе точек. <br />
+Для двумерного случая многочлен выглядит следующим образом
+:<tex>L(x) = \sum_{n=0}^N \sum_{m=0}^M f_{nm} l_{nm}(x,y)</tex>
+:<tex>l_{nm}(n,m)=1</tex>
+:<tex>l_{nm}(x,y)=0</tex> при <tex>x\ne n\  V \ y\ne m</tex>
+базисные полиномы вычисляются по следующей формуле:
+:<tex>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)}</tex>
+Отсюда следует, что L(x), как линейная комбинация l<sub>nm</sub>(x,y), может иметь степень не больше n×m, и по определению L(x<sub>n</sub>,y<sub>m</sub>)=f(x<sub>n</sub>,y<sub>m</sub>)
 == Числовой пример ==
+[[Изображение:Function.jpg]] <br />
+На Рис.1 исходная функция двух переменных ( значение функции в точке - уровень серого 0..255) <br />
+На Рис.2 сверху функция полученная с помощью билинейной интерполяции при сетке размера 6×6, на этом же рисунке снизу показана абсолютная разность между исходным изображанием и интерполируещей функцией. <br />
+На Рис.3 изображено то же что и на Рис.2 только с сеткой 11×11.
 == Рекомендации программисту ==
-== Заключение ==
+=== Исходный код ===
+[[Media:Text bilinear Interpolation.zip|Код программы на языке С++]], вычисляющий приближенное значение функции по методу билинейной интеполяции <br />
+[[Media:Project bilinear Interpolation.zip|Полный проект для Microsoft Visual Studio 2008]], вычисляющий приближенное значение функции по методу билинейной интеполяции
+=== Выбор шага сетки ===
+Если перед нами стоит задача интерполяции функции, как упрощение некой трудновычислимой функции, т.е. мы сами можем выбирать узлы сетки и соответственно её шаг, то возникает вопрос насколько нам дробить сетку? При делении сетки пополам можно рассматривать следующий параметр f<sub>точное</sub>(х<sub>i+1/2</sub>) - точное значение функции на k+1 итерации минус  f<sub>приближенное</sub>(½(х<sub>i</sub>+х<sub>i+1</sub>)) - приближенное значение в той же точке на k-ой итерации и деленое все на <sub>точное</sub>(х<sub>i+1/2</sub>). Также эти значения можно усреднить по всем узлам решётки, и при некотором его значении (например < 0.01) прекратить деление.
+=== Случай не прямоугольной сетки ===
+Такая ситуация возникает когда базовыми точками, например, являются данные эксперимента, и нам необходимо проинтерполировать их на все мн-во промежуточных значений. Тогда надо проводить интерполяцию по трем точкам: если f<sub>A</sub>, f<sub>B</sub>, f<sub>С</sub> — значение функции f(x, y) в вершинах A, B, С некоторого, то вычислить приближенное значение функции внутри этого треугольника можно с помощью билинейной функции f(x, y) ≈ F(x, y) = ax + by + c, находя коэффициенты a, b, c из условий
+ax<sub>A</sub> + by<sub>A</sub> + c = f<sub>A</sub>,
+ax<sub>B</sub> + by<sub>B</sub> + c = f<sub>B</sub>,
+ax<sub>С</sub> + by<sub>С</sub> + c = f<sub>С</sub>,
+где {x<sub>A</sub>, y<sub>A</sub>}, {x<sub>B</sub>, y<sub>B</sub>}, {x<sub>С</sub>, y<sub>С</sub>} - координаты вершин A, B , С . Погрешность такой интерполяции для функции f(x, y) с непрерывными вторыми производными будет O(h2) , где h — длина наибольшей стороны треугольника АВС.
 == Список литературы ==
+* ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы М.: Наука, 1989.
+* ''А.А.Самарский.''&nbsp; Введение в численные методы М.: Наука, 1982.
+* ''Н.Н.Калиткин.''&nbsp; Численные методы М.: Наука, 1978.
+== См. также ==
+* [[Интерполяция каноническим полиномом]]
+* [[Тригонометрическая интерполяция]]
+* [[Рациональная интерполяция]]
+* [[Практикум ММП ВМК, 4й курс, осень 2008]]
-{{stub}}
+[[Категория:Численное интегрирование]]
-[[Категория:Численное дифференцирование]]
+[[Категория:Учебные задачи]]