Интерполяция полиномами Лагранжа и Ньютона
Материал из MachineLearning.
м (→Постановка задачи) |
|||
| Строка 8: | Строка 8: | ||
Пусть значения функции <tex> f </tex> известны только в этих точках.<br> | Пусть значения функции <tex> f </tex> известны только в этих точках.<br> | ||
Точки <tex> \bf{x} </tex> называют узлами интерполяции.<br> | Точки <tex> \bf{x} </tex> называют узлами интерполяции.<br> | ||
| - | <tex> \delta x_i = x_i - x_{i-1}</tex> - | + | <tex> \delta x_i = x_i - x_{i-1}</tex> - шаг интерполяционной сетки.<br> |
Задача интерполяции состоит в поиске такой функции <tex> F </tex> из заданного класса функций, что | Задача интерполяции состоит в поиске такой функции <tex> F </tex> из заданного класса функций, что | ||
<tex> F(x_i) = y_i</tex> | <tex> F(x_i) = y_i</tex> | ||
== Метод решения задачи == | == Метод решения задачи == | ||
| - | + | ===Полином Лагранжа=== | |
| + | Представим интерполяционную функцию в виде полинома<br> | ||
| + | <tex>P_n(x) = \sum_{i=0}^n y_i Q_{n,i}(x)</tex><br> | ||
| + | где <tex>Q_{n,i}(x)</tex> - полиномы степели n вида:<br> | ||
| + | <tex>Q_{n,i}(x) = \prod_{j=0, j\neq i}^{n} \frac{(x-x_j)}{(x_i-x_j)}</tex><br> | ||
| + | Очевидно, что <tex>Q_{n,i}(x)</tex> принимает значение 1 в точке <tex>x_i</tex> и 0 в остальных узлах интерполяции. Следовательно в точке <tex>x_i</tex> исходный полином принимает значение <tex>y_i</tex><br> | ||
| + | Таким образом, построенный полином <tex>P_n(x)</tex> является интерполяционным полиномом для функции | ||
| + | <tex> y = f(x) </tex> на сетке <tex> \bf{x} </tex>. <br> | ||
| + | ===Полином Ньютона=== | ||
| + | Интерполяционный полином в форме Лагранжа не удобен для вычислений тем, что при увеличении числа узло интерполции приходится перестраивать весь полином заного.<br> | ||
| + | Перепишем полином Лагранжа в другом виде:<br> | ||
| + | <tex>P_n(x) = P_0(x) + \sum_{i=1}^n{(P_i(x) - P_{i-1}(x))} </tex><br> | ||
== Пример == | == Пример == | ||
== Литература == | == Литература == | ||
Версия 13:49, 19 октября 2008
Содержание |
Постановка задачи
Пусть задана функция
.
Пусть заданы точки
из некоторой области
.
Пусть значения функции известны только в этих точках.
Точки называют узлами интерполяции.
- шаг интерполяционной сетки.
Задача интерполяции состоит в поиске такой функции из заданного класса функций, что
Метод решения задачи
Полином Лагранжа
Представим интерполяционную функцию в виде полинома
где - полиномы степели n вида:
Очевидно, что принимает значение 1 в точке
и 0 в остальных узлах интерполяции. Следовательно в точке
исходный полином принимает значение
Таким образом, построенный полином является интерполяционным полиномом для функции
на сетке
.
Полином Ньютона
Интерполяционный полином в форме Лагранжа не удобен для вычислений тем, что при увеличении числа узло интерполции приходится перестраивать весь полином заного.
Перепишем полином Лагранжа в другом виде:
