_{Министерство науки и высшего образования РОССИИ}

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра ИС

отчет

по лабораторной работе №4

по дисциплине «Конструирование программ»

Тема: Интерполирование и экстраполирование данных. Интерполяционный многочлен Лагранжа

Студент гр. 93—		—
Преподаватель		Копыльцов А. В.

Санкт-Петербург

2021

Цель работы.

Научится использовать интерполяционные многочлены Лагранжа невысоких степеней и находить приближённые значения функции для любых значений аргумента, лежащих между узлами заданной сетки.

Основные теоретические положения.

1. Задача приближения функций

Вычисление значений функции — задача, с которой постоянно приходиться сталкиваться на практике. Часто бывает, что вычисление затруднительно, например:

1) функция задана таблично , а вычисление необходимо проводить в точках , не совпадающих с табличными;

2) вычисление функции дорого;

3) для вычисления необходим эксперимент.

В таких условиях целесообразно заменить некоторой близкой к ней функцией , которая вычисляется быстро и надежно, а погрешность приближения достаточно мала. При этом полезно при выборе функции использовать любую дополнительную информацию о функции , о ее гладкости, четности, периодичности, монотонности и так далее. Это дает возможность осознанно выбрать класс аппроксимирующих функций.

Широко используются функции вида , представляющие собой линейные комбинации некоторых базисных функций . Функция называется обобщенным многочленом степени .

2. Интерполяция обобщёнными многочленами

Если ставится требование совпадения функции с функцией в некоторых фиксированных точках, то это приводит к задаче интерполяции.

Построить функцию , удовлетворяющую условиям , — узлы интерполяции. Очевидно, что выбор неоднозначен, так как по заданной таблице можно построить бесконечно много интерполирующих функций. Рассмотрим обобщенный многочлен , удовлетворяющий условию Эта формула, представленная в виде , очевидно, эквивалентна следующей системе линейных алгебраических уравнений:

Для определения необходимо решить систем относительно . На практике это делается чрезвычайно редко. Как правило, система плохо обусловлена. В большинстве приложений используются специальные явные формулы для записи и вычисление не нужно.

3. Полиномиальная интерполяция. Многочлен Лагранжа

Если в качестве базисной взять систему степенных функций, то есть , то получаем задачу полиномиальной интерполяции:

Теорема 2.1. Существует единственный интерполяционный многочлен степени , удовлетворяющий условиям.

В качестве искомого многочлена возьмём многочлен степени вида

Таким образом, система функций, по которой строится интерполяционный многочлен, есть

Для нахождения надо найти набор коэффициентов . Не будем составлять и решать систему линейных уравнений вида … , найдём коэффициенты иным способом.

Пусть , с учетом получим

Аналогично, полагая и учитывая, что будем иметь

Если , то Тогда сам многочлен будет иметь вид

Эта формула называется интерполяционной формулой Лагранжа. Приведём её в сокращённой записи:

Очевидно, представляет собой многочлен степени , удовлетворяющий условию

Таким образом, степень многочлена равна , при в формуле обращаются в нуль все слагаемые, кроме слагаемого с номером , равного .

Выпишем отдельно многочлены Лагранжа первой и второй степени, ибо именно они чаще всего используются на практике.

4. Погрешность интерполяции

Теорема 2.2. Пусть функция дифференцируема раз на отрезке , содержащем узлы интерполяции Тогда для погрешности интерполяции в точке справедливо равенство в котором

Последнюю формулу несколько модернизируют. Так как положение точки неизвестно, то заменяют на Тогда

5. Конечные разности и их свойства

Пусть функция задана таблично - шаг таблицы, - узлы таблицы.

Величина называется конечной разностью первого порядка функции в точке с шагом .

Конечная разность порядка функции в точке есть Таким образом, конечная разность второго порядка есть Аналогичным образом могут быть определены конечные разности произвольного порядка.

Теорема 2.3. -я конечная разность выражается через значения функции в точке по формуле , где .

Теорема 2.4. Пусть функция дифференцируема раз на отрезке . Тогда справедливо равенство

6. Разделённые разности и их свойства

Пусть функция задана на таблице значений аргумента с произвольным шагом, причем точки таблицы занумерованы также в произвольном порядке.

Величины называются разделенными разностями первого порядка функции в узлах Аналогично определяются разделённые разности более высокого порядка: — разделённая разность второго порядка в узлах Разделенной разностью -го порядка называется число

Разделённые разности обладают рядом замечательных свойств, изложенных в следующих теоремах.

Теорема 2.5. Разделённая разность является симметричной функцией своих аргументов (то есть ее свойства не меняются при любой их перестановке).

Теорема 2.6. Разделённая разность -го порядка выражается через значения функции следующим образом

Теорема 2.7. Пусть функция имеет на отрезке , содержащем точки , производную порядка . Тогда справедливо равенство

Теорема 2.8. В случае когда таблица значений аргумента имеет постоянный шаг , конечная и разделённая разность связаны соотношением

7. Вычислительная схема Эйткена.

Согласно этой схеме интерполяционные многочлены любого вида вычисляются последовательно по формулам:

и так далее. Интерполяционный многочлен -й степени, принимающий в точках значения запишется следующим образом:

Вычисления прекращают, если или если последовательные значения совпадут в пределах заданной точности.

Экспериментальные результаты.

Задание № 2

Используя схему Эйткена, вычислить приближенное значение функции , заданной таблично при значении аргумента .

0.45	2.5742
0.47	2.3251
0.52	2.0934
0.61	1.8620
0.66	1.7493
0.70	1.6210
0.74	1.3418
0.79	1.1212

Обработка результатов эксперимента.

Задание 2

2.261

Выводы.

Были освоены навыки использования метода Эйткена для нахождения приближённых значений функции для любых значений аргумента, лежащих между узлами заданной сетки.

ПРИЛОЖЕНИЕ 1. Код программы

package j.softwareconstruction.lab2; import j.math.types.Polynomial; public class Main { public static void main(String[] args) { task2(); }

private static void task2() { System.out.println("Задание 2"); double xT = 0.478; double[] x = {0.45, 0.47, 0.52, 0.61, 0.66, 0.70, 0.74, 0.79}; double[] y = {2.5742, 2.3251, 2.0934, 1.8620, 1.7493, 1.6210, 1.3418, 1.1212}; double[][] P = new double[y.length][]; P[0] = y; for (int j = 1; j < y.length; j++) { P[j] = new double[y.length - j]; for (int i = 0; i < P[j].length; i++) { P[j][i] = (P[j - 1][i] * (x[i + j] - xT) - P[j - 1][i + 1] * (x[i] - xT)) / (x[i + j] - x[i]); } } System.out.println("\t" + Math.round(P[P.length - 1][0] * 1000) / 1000.0); } }