Интерполяция функций двух переменных, проблема выбора узлов
Материал из MachineLearning.
м (→Постановка математической задачи) |
м (→Проблема выбора узлов) |
||
Строка 14: | Строка 14: | ||
== Изложение метода == | == Изложение метода == | ||
=== Проблема выбора узлов === | === Проблема выбора узлов === | ||
- | Рассмотрим [[Интерполяция каноническим полиномом| | + | Рассмотрим задачу [[Интерполяция каноническим полиномом|интерполяции полиномами]]: <br /> |
'''I.''' Заметим что не любое число узлов интерполяции выгодно. Если для одной переменной степень многочлена была взаимно однозначно связана с числом узлов, то для двух переменных многочлен ''n''-ой степени <tex>P_n(x,y)=\sum_{k+m=0}^na_{km}x^ky^m\ </tex> имеет (n+1)(n+2)/2 узлов. Если число узлов не соответствует этой формуле, то часть коэффициентов при высших степенях должна задаваться принудительно (в частности нулями): для выбора этих коэффициентов редко есть разумные основания. <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 /> | '''II.''' Также не всякое расположение узлов допустимо: в одномерном случае узлы не должны были совпадать. Теперь же для интерполяции многочеленом <tex>P_1(x,y)</tex> необходимо, чтобы узлы не лежали на прямой в плоскости <tex>(x,y)</tex>. При интерполяции многочленом <tex>P_n(x,y)</tex> требуется, чтобы узлы не лежали на кривой n-го порядка. <br /> |
Версия 07:33, 19 октября 2008
Содержание |
Введение
Постановка математической задачи
Интерполя́ция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.
Рассмотрим систему несовпадающих точек () из некоторой области . Пусть значения функции известны только в этих точках:
- Точки называют узлами интерполяции, а их совокупность — интерполяционной сеткой.
- Тройки называют точками данных или базовыми точками
Задача интерполяции состоит в поиске такой функции из заданного класса функций, что
- максимально приближает функцию в произвольной точке внутри интерполяционной сетки.
- Функцию — называют интерполирующей функцией .
Изложение метода
Проблема выбора узлов
Рассмотрим задачу интерполяции полиномами:
I. Заметим что не любое число узлов интерполяции выгодно. Если для одной переменной степень многочлена была взаимно однозначно связана с числом узлов, то для двух переменных многочлен n-ой степени имеет (n+1)(n+2)/2 узлов. Если число узлов не соответствует этой формуле, то часть коэффициентов при высших степенях должна задаваться принудительно (в частности нулями): для выбора этих коэффициентов редко есть разумные основания.
II. Также не всякое расположение узлов допустимо: в одномерном случае узлы не должны были совпадать. Теперь же для интерполяции многочеленом необходимо, чтобы узлы не лежали на прямой в плоскости . При интерполяции многочленом требуется, чтобы узлы не лежали на кривой n-го порядка.
Поэтому для хорошей интерполяции сетка должна быть регулярно построенной, а не представлять собой совокупность беспорядочно расположенных точек. Следущие два примера используют прямоугольную сетку, образованную пересечением прямых x = xn, n = 0, ..., N и y = ym, m = 0, ..., M,
- fnm = f(xn, ym) — значение функции в узле {xn, ym }.
Билинейная интерполяция
Билинейной интерполяцией называют расширение линейной интерполяции для функций двух переменных.
Для начала реализуется линейная интерполяция по x на каждой прямой y = ym . Затем при каждом значении x = xn реализуется линейная интерполяция по y с учетом значений функции, полученных на первом шаге.
Пусть
Результат билинейной интерполяции не зависит от порядка шагов: можно сначала интерполировать вдоль оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же.
Интерполяционный многочлен Лагранжа
Интерполяционный многочлен Лагранжа - многочлен минимальной степени, принимающий данные значения в данном наборе точек.
Для двумерного случая многочлен выглядит следующим образом
- при
базисные полиномы вычисляются по следующей формуле:
Отсюда следует, что L(x), как линейная комбинация lnm(x,y), может иметь степень не больше n×m, и по определению L(xn,ym)=f(xn,ym)
Числовой пример
Рекомендации программисту
Заключение
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
- А.А.Самарский. Введение в численные методы М.: Наука, 1982.
- Н.Н.Калиткин. Численные методы М.: Наука, 1978.