Интерполирование функций (стр. 1 из 3)
Содержание
Введение
1. Формула Лагранжа
2. Интерполирование по схеме Эйткена
3. Интерполяционные формулы Ньютона для равноотстоящих узлов
4. Формула Ньютона с разделенными разностями
5. Интерполяция сплайнами
Заключение
Список литературы
Введение
Цель работы: изучение и сравнительный анализ методов интерполяции функций; реализация этих методов в виде машинных программ на языке высокого уровня и практическое решение задач интерполяции на ЭВМ.
При разработке математического обеспечения САПР часто приходится иметь дело с функциями f(x), заданными в виде таблиц, когда известны некоторое конечное множество значений аргумента и соответствующие им значения функции. Аналитическое выражение функции f(x) при этом неизвестно, что не позволяет определять ее значения в промежуточных точках аргумента, отсутствующих в таблице. В таком случае решается задача интерполирования, которая формулируется следующим образом.
На отрезке [a, b] заданы n + 1 точки x0, x1, ..., xn, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках f(x0) = y0,f(x1) = y1, ..., f(xn) = yn. Требуется построить интерполирующую функцию F(x), принимающую в узлах интерполяции те же значения, что и f(x), т.е. такую, что F(x0) = y0,F(x1) = y1, ...,F(xn) = yn.
Геометрически это означает, что нужно найти кривую y = F(x) некоторого определенного типа, проходящую через заданную систему точек Mi(xi, yi) дляi =
. Полученная таким образом интерполяционная формула y = F(x) обычно используется для вычисления значений исходной функции f(x) для значений аргумента x, отличных от узлов интерполяции. Такая операция называется интерполированием функции f(x). При этом различают интерполирование в узком смысле, когда x принадлежит интервалу [x0, xn], и экстраполирование, когда x не принадлежит этому интервалу.В такой общей постановке задача интерполирования может иметь бесчисленное множество решений. Чтобы получить единственную функцию F(x), необходимо предположить, что эта функция не произвольная, а удовлетворяет некоторым дополнительным условиям.
В простейшем случае предполагается, что зависимость y = f(x) на каждом интервале (xi, xi+1) является линейной. Тогда для каждого участка (xi, xi+1) в качестве интерполяционной формулы y =F(x) используется уравнение прямой, проходящей через точки Mi(xi, yi) и Mi+1(xi+1, yi+1), которое имеет вид
. (1)Припрограммировании процедур линейной интерполяции следует учитывать, что процесс решения задачи интерполирования с использованием формулы (1) включают два этапа: выбор интервала (xi, xi+1), которому принадлежит значение аргумента х; собственно вычисление значения y =F(x) по формуле (1).
На практике в качестве интерполирующей функции F(x) обычно используется алгебраический многочлен
Pn(x) =a0 + a1x +a2x2+ ... +anxn
степени не выше n, такой, что Pn(x0) = y0,Pn(x1) = y1,...,Pn(xn) = yn. Наиболее известными методами построения интерполяционного многочлена Pn(x)являются метод Лагранжа, итерационные и разностные методы.
1. Формула Лагранжа
Интерполяционная формула Лагранжа обеспечивает построение алгебраического многочлена Pn(x) для произвольно заданных узлов интерполирования. Для n + 1 различных значений аргумента x0, x1, ..., xn и соответствующих значений функции f(x0) = y0,f(x1) = y1, ..., f(xn) = yn интерполяционная формула Лагранжа имеет вид
,где х - значение аргумента функции, расположенного в интервале [x0, xn].
Необходимо отметить, что формула Лагранжа, в отличие от других интерполяционных формул, содержит явно yi(i = 
), что бывает иногда важно.
Пример 1. Построить интерполяционный многочлен Лагранжа для функции, заданной следующей таблицей.
| x0 = 0, | x1 = 1, | x2 = 2, | x 3 = 5, |
| y0 = 2, | y1 = 3, | y2 = 12, | y 3 = 147. |
 |
Для случая четырех узлов интерполяции (n = 3) многочлен Лагранжа представляется следующим образом:
Заменив переменные xi, yi(i = 
)их числовыми значениями, получим интерполяционный многочлен
 |
Интерполирование по формуле Лагранжа связано с большим объемом вычислений, значительная часть которых повторяется при получении нескольких значений Pn(x) для одной функции f(x).В том случае, когда формула Лагранжа используется для многократного получения значений одной функции при различных значениях аргумента, можно значительно уменьшить объем вычислений. Для этого формула Лагранжа представляется в виде
 |
где
- лагранжевы коэффициенты, определяемые как  |
 |
Вычисление лагранжевых коэффициентов выполняется по следующей схеме, удобной при использовании ЭВМ. Составляется таблица разностей:
Произведение элементовi-й строки обозначается через Ki. Отсюда лагранжевы коэффициенты вычисляются по формуле
 |
где Пn+1(x) = (x - x0)(x - x1)…(x - xn) - произведение элементов главной диагонали таблицы (эти элементы подчеркнуты). Тогда формула Лагранжапринимает вид:
 |
Использование формулы (2) позволяет сократить значительную часть вычислений по определению лагранжевых коэффициентов Li(n)(x)при различных значениях аргумента. Для этого произведение элементов i-й строки таблицы разностей представляется как Ki = (x – xi)Di, где Di - произведение всех элементов строки, кроме расположенного на главной диагонали. Величина Di(i= 
)не зависит от значения аргумента x и может быть вычислена для заданной функции только один раз.
2. Интерполирование по схеме Эйткена
Итерационные методы интерполирования основаны на повторном применении некоторой простой интерполяционной схемы. Наиболее известным из итерационных методов является метод Эйткена, в основе которого лежит многократное применение линейной интерполяции.
В соответствии со схемой Эйткена линейная интерполяция по точкам Mi(xi, yi) и Mi+1(xi+1, yi+1) сводится к вычислению определителя второго порядка
 |
При интерполировании по трем и более точкам последовательно вычисляются многочлены
 |
 |
В общем случае интерполяционныймногочлен n-й степени, принимающий в точках xiзначения yi(i = 
), записываются следующим образом:
 |
(3)
Основным достоинством схемы Эйткена является возможность постепенного увеличения числа используемых значений xi до тех пор, пока последовательные значения P0,1,2,…,n(x) и P1,2,…,n-1(x) не совпадут в пределах заданной точности. Иначе говоря, вычисления прекращаются при выполнении условия