Интерполяция функций двух переменных, проблема выбора узлов
Материал из MachineLearning.
(→Изложение метода) |
(→Изложение метода) |
||
Строка 15: | Строка 15: | ||
== Изложение метода == | == Изложение метода == | ||
+ | === Проблема выбора узлов === | ||
+ | '''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_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>\ x\in[x_n,x_n_+_1],\ \ y\in[y_m,y_m_+_1]</tex><br/> | ||
Строка 25: | Строка 28: | ||
оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же. | оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же. | ||
=== Интерполяционный многочлен Лагранжа === | === Интерполяционный многочлен Лагранжа === | ||
- | '''Интерполяционный многочлен Лагранжа''' - многочлен минимальной степени, принимающий данные значения в данном наборе точек. | + | '''Интерполяционный многочлен Лагранжа''' - многочлен минимальной степени, принимающий данные значения в данном наборе точек. <br /> |
- | Для двумерного случая: для (n+1) | + | |
+ | Для двумерного случая: для (n+1)×(m+1) точек <tex>(x_i,y_j,f(x_i,y_j))</tex> i=0..n, j=0..m, где все пары <tex>(x_i,y_j)</tex> различны, существует единственный многочлен L(x,y) степени не более n×m для которого L(x<sub>i</sub>,y<sub>j</sub>) = f(x<sub>i</sub>,y<sub>j</sub>) | ||
== Числовой пример == | == Числовой пример == |
Версия 12:54, 16 октября 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 с учетом значений функции, полученных на первом шаге.
Пусть
Результат билинейной интерполяции не зависит от порядка шагов: можно сначала интерполировать вдоль оси абсцисс а затем вдоль оси ординат, так и наоборот, результат будет одним и тем же.
Интерполяционный многочлен Лагранжа
Интерполяционный многочлен Лагранжа - многочлен минимальной степени, принимающий данные значения в данном наборе точек.
Для двумерного случая: для (n+1)×(m+1) точек i=0..n, j=0..m, где все пары различны, существует единственный многочлен L(x,y) степени не более n×m для которого L(xi,yj) = f(xi,yj)