ЛР3. 2.1. Интерполирование и экстраполирование данных. Интерполяционный многочлен Лагранжа
.docxМинистерство науки и высшего образования РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра ИС
отчет
по лабораторной работе №3
по дисциплине «Конструирование программ»
Тема: Интерполирование и экстраполирование данных. Интерполяционный многочлен Лагранжа
Студент гр. 93— |
|
— |
Преподаватель |
|
Копыльцов А. В. |
Санкт-Петербург
2021
Цель работы.
Научится использовать интерполяционные многочлены Лагранжа невысоких степеней и находить приближённые значения функции для любых значений аргумента, лежащих между узлами заданной сетки.
Основные теоретические положения.
Задача приближения функций
Вычисление значений функции — задача, с которой постоянно приходиться сталкиваться на практике. Часто бывает, что вычисление затруднительно, например:
1) функция задана таблично , а вычисление необходимо проводить в точках , не совпадающих с табличными;
2) вычисление функции дорого;
3) для вычисления необходим эксперимент.
В таких условиях целесообразно заменить некоторой близкой к ней функцией , которая вычисляется быстро и надежно, а погрешность приближения достаточно мала. При этом полезно при выборе функции использовать любую дополнительную информацию о функции , о ее гладкости, четности, периодичности, монотонности и так далее. Это дает возможность осознанно выбрать класс аппроксимирующих функций.
Широко используются функции вида , представляющие собой линейные комбинации некоторых базисных функций . Функция называется обобщенным многочленом степени .
Интерполяция обобщёнными многочленами
Если ставится требование совпадения функции с функцией в некоторых фиксированных точках, то это приводит к задаче интерполяции.
Построить функцию , удовлетворяющую условиям , — узлы интерполяции. Очевидно, что выбор неоднозначен, так как по заданной таблице можно построить бесконечно много интерполирующих функций. Рассмотрим обобщенный многочлен , удовлетворяющий условию Эта формула, представленная в виде , очевидно, эквивалентна следующей системе линейных алгебраических уравнений:
Для определения необходимо решить систем относительно . На практике это делается чрезвычайно редко. Как правило, система плохо обусловлена. В большинстве приложений используются специальные явные формулы для записи и вычисление не нужно.
Полиномиальная интерполяция. Многочлен Лагранжа
Если в качестве базисной взять систему степенных функций, то есть , то получаем задачу полиномиальной интерполяции:
Теорема 2.1. Существует единственный интерполяционный многочлен степени , удовлетворяющий условиям.
В качестве искомого многочлена возьмём многочлен степени вида
Таким образом, система функций, по которой строится интерполяционный многочлен, есть
Для нахождения надо найти набор коэффициентов . Не будем составлять и решать систему линейных уравнений вида … , найдём коэффициенты иным способом.
Пусть , с учетом получим
Аналогично, полагая и учитывая, что будем иметь
Если , то Тогда сам многочлен будет иметь вид
Эта формула называется интерполяционной формулой Лагранжа. Приведём её в сокращённой записи:
Очевидно, представляет собой многочлен степени , удовлетворяющий условию
Таким образом, степень многочлена равна , при в формуле обращаются в нуль все слагаемые, кроме слагаемого с номером , равного .
Выпишем отдельно многочлены Лагранжа первой и второй степени, ибо именно они чаще всего используются на практике.
Погрешность интерполяции
Теорема 2.2. Пусть функция дифференцируема раз на отрезке , содержащем узлы интерполяции Тогда для погрешности интерполяции в точке справедливо равенство в котором
Последнюю формулу несколько модернизируют. Так как положение точки неизвестно, то заменяют на Тогда
Конечные разности и их свойства
Пусть функция задана таблично - шаг таблицы, - узлы таблицы.
Величина называется конечной разностью первого порядка функции в точке с шагом .
Конечная разность порядка функции в точке есть Таким образом, конечная разность второго порядка есть Аналогичным образом могут быть определены конечные разности произвольного порядка.
Теорема 2.3. -я конечная разность выражается через значения функции в точке по формуле , где .
Теорема 2.4. Пусть функция дифференцируема раз на отрезке . Тогда справедливо равенство
Разделённые разности и их свойства
Пусть функция задана на таблице значений аргумента с произвольным шагом, причем точки таблицы занумерованы также в произвольном порядке.
Величины называются разделенными разностями первого порядка функции в узлах Аналогично определяются разделённые разности более высокого порядка: — разделённая разность второго порядка в узлах Разделенной разностью -го порядка называется число
Разделённые разности обладают рядом замечательных свойств, изложенных в следующих теоремах.
Теорема 2.5. Разделённая разность является симметричной функцией своих аргументов (то есть ее свойства не меняются при любой их перестановке).
Теорема 2.6. Разделённая разность -го порядка выражается через значения функции следующим образом
Теорема 2.7. Пусть функция имеет на отрезке , содержащем точки , производную порядка . Тогда справедливо равенство
Теорема 2.8. В случае когда таблица значений аргумента имеет постоянный шаг , конечная и разделённая разность связаны соотношением
Вычислительная схема Эйткена.
Согласно этой схеме интерполяционные многочлены любого вида вычисляются последовательно по формулам:
и так далее. Интерполяционный многочлен -й степени, принимающий в точках значения запишется следующим образом:
Вычисления прекращают, если или если последовательные значения совпадут в пределах заданной точности.
Экспериментальные результаты.
Задание № 1
Восстановить многочлен Лагранжа, удовлетворяющий приведённым исходным данным.
|
0 |
1 |
2 |
3 |
4 |
|
-2 |
-1 |
0 |
1 |
2 |
|
5 |
0 |
1 |
0 |
5 |
Обработка результатов эксперимента.
Задание 1
2/3x^4-5/3x^2+1
Выводы.
Были освоены навыки использования метода Лагранжа для нахождения интерполяционных многочленов Лагранжа.
ПРИЛОЖЕНИЕ 1. Код программы
jpackage j.softwareconstruction.lab2; import j.math.types.Polynomial; public class Main { public static void main(String[] args) { task1(); } private static void task1() { System.out.println("Задание 1"); int[] x = {-2, -1, 0, 1, 2}; int[] y = {5, 0, 1, 0, 5}; Polynomial result = Polynomial.ZERO_VALUE; for (int i = 0; i < x.length; i++) { Polynomial summand = Polynomial.ONE_VALUE; if (y[i] == 0) continue; for (int j = 0; j < x.length; j++) { if (i == j) continue; if (x[j] < 0) summand = summand.multiply(Polynomial.parse("x + " + (-x[j]))); else summand = summand.multiply(Polynomial.parse("x - " + x[j])); summand = summand.divide(Polynomial.parse(String.valueOf(x[i] - x[j]))); } summand = summand.multiply(Polynomial.parse(String.valueOf(y[i]))); result = result.add(summand); } System.out.println("\t" + result); } }