readln(b_s);
val(b_s,matr2[j],code);
until code=0;
end;
end;
Разработать схему алгоритма и написать программу на языке Turbo Pascal 7.0 для интерполирования функции, заданной в узлах, используя метод Ньютона с разделенными разностями.
Дана табличная функция:
i | xi | yi |
0 | x0 | y |
1 | x1 | 0 |
2 | x2 | y |
... | ... | 1 |
n | xn | y |
2 | ||
... | ||
y | ||
n |
или
Точки с координатами (xi, yi) называются узловыми точками или узлами.Количество узлов в табличной функции равно N=n+1.
Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем
.Для решения задачи строим интерполяционный многочлен.
Интерполяция по Лагранжу
Интерполяционный многочлен может быть построен при помощи специальных интерполяционных формул Лагранжа, Ньютона, Стерлинга, Бесселя и др.
Интерполяционный многочлен по формуле Лагранжа имеет вид:
Докажем, что многочлен Лагранжа является интерполяционным многочленом, проходящим через все узловые точки, т.е. в узлах интерполирования xi выполняется условие Ln(xi) = yi. Для этого будем последовательно подставлять значения координат узловых точек таблицы в многочлен (2.1). В результате получим:
если x=x0, то Ln(x0) = y0,
если x=x1, то Ln(x1) = y1,
……………
если x=xn, то Ln(xn) = yn.
Это достигнуто за счет того, что в числителе каждой дроби при соответствующем значении уj, j=0,1,2,…,n отсутствует сомножитель (x-xi), в котором i=j, а знаменатель каждой дроби получен заменой переменной х на соответствующее значение хj.
Таким образом, интерполяционный многочлен Лагранжа приближает заданную табличную функцию, т.е. Ln(xi) = yi и мы можем использовать его в качестве вспомогательной функции для решения задач интерполирования, т.е.
.Чем больше узлов интерполирования на отрезке [x0,xn] , тем точнее интерполяционный многочлен приближает заданную табличную функцию, т.е. тем точнее равенство:
Однако с увеличением числа узлов интерполирования возрастает степень интерполяционного многочлена n и в результате значительно возрастает объем вычислительной работы. Поэтому при большом числе узлов необходимо применять ЭВМ. В этом случае удобно находить значения функции в промежуточных точках, не получая многочлен в явном виде.
При решении задачи экстраполирования функции с помощью интерполяционного многочлена вычисление значения функции за пределами отрезка [x0,xn] обычно производят не далее, чем на один шаг h, равный наименьшей величине
так как за пределами отрезка [x0,xn] погрешности, как правило, увеличиваются.
Интерполяция по Ньютону
Интерполяционный многочлен по формуле Ньютона имеет вид:
(2.2)где n – степень многочлена,
- разделенные разности 0-го, 1-го, 2-го,…., n-го порядка, соответственно.Сплайн-интерполяция
Сплайны стали широко использоваться в вычислительной математике сравнительно недавно. В машиностроительном черчении они применяются уже давно, так как сплайны – это лекала или гибкие линейки, деформация которых позволяет провести кривую через заданные точки (xi, уi).
Используя теорию изгиба бруса при малых деформациях, можно показать, что сплайн – это группа кубических многочленов, в местах сопряжения которых первая и вторая производные непрерывны. Такие функции называются кубическими сплайнами. Для их построения необходимо задать коэффициенты, которые единственным образом определяют многочлен в промежутке между данными точками.
Например, для некоторых функций (рис.) необходимо задать все кубические функции q1(x), q2(x), …qn(x).
В наиболее общем случае эти многочлены имеют вид:
где kij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов kij необходимо построить и решить систему порядка 4n.
Первые 2n условий требуют, чтобы сплайны соприкасались в заданных точках:
Следующие (2n-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:
Система алгебраических уравнений имеет решение, если число уравнений соответствует числу неизвестных. Для этого необходимо ввести еще два уравнения. Обычно используются следующие условия:
При построении алгоритма метода первые и вторые производные удобно аппроксимировать разделенными разностями соответствующих порядков.
Полученный таким образом сплайн называется естественным кубическим сплайном. Найдя коэффициенты сплайна, используют эту кусочно-гладкую полиноминальную функцию для представления данных при интерполяции.
Значения f(x0), f(x1), … , f(xn) , т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k=0).
Отношение
называется разделенной разностью первого порядка (k=1) на участке [x0, x1] и равно разности разделенных разностей нулевого порядка на концах участка [x0, x1], разделенной на длину этого участка.Для произвольного участка [xi, xi+1] разделенная разность первого порядка (k=1) равна
Отношение
называется разделенной разностью второго порядка (k=2) на участке [x0, x2] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x0, x2].Для произвольного участка [xi, xi+2] разделенная разность второго порядка (k=2) равна
Таким образом, разделенная разность k-го порядка на участке [xi, xi+k] может быть определена через разделенные разности (k-1)-го порядка по рекуррентной формуле:
(2.3)Где
n – степень многочлена.Максимальное значение k равно n. Тогда i =0 и разделенная разность n-го порядка на участке [x0,xn] равна
,т.е. равна разности разделенных разностей (n-1)-го порядка, разделенной на длину участка [x0,xn].
Разделенные разности
являются вполне определенными числами, поэтому выражение (2.2) действительно является алгебраическим многочленом n-й степени. При этом в многочлене (2.2) все разделенные алгебраическим многочленом n-й степени. При этом в многочлене (2.2) все разделенные разности определены для участков [x0, x0+k],
.Лемма: алгебраический многочлен (2.2), построенный по формулам Ньютона, действительно является интерполяционным многочленом, т.е. значение многочлена в узловых точках равно значению табличной функции
Докажем это. Пусть х=х0 , тогда многочлен (2.2) равен
Пусть х=х1, тогда многочлен (2.2) равен
Пусть х=х2, тогда многочлен (2.2) равен
Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2.2). Это удобно на практике и ускоряет процесс вычислений.