Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

== Введение == === Постановка математической задачи === '''Интерполя́ция'''&nbsp;— в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Рассмотрим систему несовпадающих точек <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>~F(x)</tex> — называют '''интерполирующей функцией''' . == Изложение метода == === Проблема выбора узлов === Рассмотрим задачу [[Интерполяция каноническим полиномом|интерполяции полиномами]]: <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_n, n = 0, ..., N и y = y_m, m = 0, ..., M, <br /> ::f_nm = f(x_n, y_m) — значение функции в узле {x_n, y_m }. === Билинейная интерполяция === '''Билинейной интерполяцией''' называют расширение линейной интерполяции для функций двух переменных. Для начала реализуется линейная интерполяция по x на каждой прямой y = y_m . Затем при каждом значении x = x_n реализуется линейная интерполяция по 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_nm(x,y), может иметь степень не больше n×m, и по определению L(x_n,y_m)=f(x_n,y_m) == Числовой пример == [[Изображение: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_точное(х_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 — длина наибольшей стороны треугольника АВС. == Список литературы == * ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы М.: Наука, 1989. * ''А.А.Самарский.''&nbsp; Введение в численные методы М.: Наука, 1982. * ''Н.Н.Калиткин.''&nbsp; Численные методы М.: Наука, 1978. == См. также == * [[Интерполяция каноническим полиномом]] * [[Тригонометрическая интерполяция]] * [[Рациональная интерполяция]] * [[Практикум ММП ВМК, 4й курс, осень 2008]] [[Категория:Численное интегрирование]] [[Категория:Учебные задачи]]

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