Кубический интерполяционный сплайн. Кубические сплайны

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»

Институт радиоэлектроники и информационных технологий - РТФ

Кафедра Автоматика и информационные технологии

Интерполяция сплайнами

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К лабороторной работе ПО ДИСЦИПЛИНЕ «Численные методы»

Составитель И.А.Селиванова, ст.преподаватель.

ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ: Методические указания к практическим занятиям по дисциплине «Численные методы»

Указания предназначены для студентов всех форм обучения направления 230100 – «Информатика и вычислительная техника».

Ó ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина», 2011

1. ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ. 4

1.1. Кубические сплайны. 4

1.2. Специальная форма записи сплайна. 5

1.3. Квадратичные сплайны. 13

1.4. Задание на практику. 18

1.5. Варианты заданий. 19

Список литературы 21

1. Интерполяция сплайнами.

В случаях, когда промежуток [a ,b ], на котором требуется заменить функцию f (x ) велик, можно применить интерполяцию сплайнами.

1.1. Кубические сплайны.

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

Пусть на отрезке [a , b ] вещественной оси x задана сетка , в узлах которой определены значения
функцииf (x ). Требуется построить на отрезке [a , b ] непрерывную функцию-сплайн S (x ), которая удовлетворяет следующим условиям:

Для построения искомого сплайна требуется найти коэффициенты
многочленов
,i =1,… n , т.е. 4 n неизвестных коэффициента, которые удовлетворяют 4 n -2 уравнениям (1), (2), (3). Чтобы система уравнений имела решение, добавляют еще два дополнительных (краевых) условия. Используется три типа краевых условий:

Условия (1), (2), (3) и одно из условий (4), (5), (6) образуют СЛАУ порядка 4 n . Решение системы можно провести с помощью метода Гаусса. Однако, выбрав специальную форму записи кубического многочлена, можно существенно снизить порядок решаемой системы уравнений.

1.2. Специальная форма записи сплайна.

Рассмотрим отрезок
. Введем следующие обозначения переменных:

Здесь
- длина отрезка
,

,
- вспомогательные переменные,

x – промежуточная точка на отрезке
.

Когда x пробегает все значения на интервале
, переменнаяизменяется от 0 до 1, а
изменяется от 1 до 0.

Пусть кубический многочлен
на отрезке
имеет вид:

Переменные и
определяются применительно к конкретному отрезку интерполяции.

Найдем значение сплайна
на концах отрезка
. Точка
является начальной для отрезка
, поэтому=0,
=1 и в соответствии с (3.8):
.

На конце отрезка
=1,
=0 и
.

Для интервала
точка
является конечной, поэтому=1,
=0 и из формулы (9) получаем:
. Таким образом, выполняется условие непрерывности функцииS (x ) в узлах стыковки кубических многочленов независимо от выбора чисел  i .

Для определения коэффициентов  i , i =0,… n продифференцируем (8) дважды как сложную функцию от x . Тогда

Определим вторые производные сплайна
и
:

Для многочлена
точкаявляется началом отрезка интерполяции и=0,
=1, поэтому

Из (15) и (16) следует, что на отрезке [a ,b ]сплайн-функция, «склеенная» из кусков многочленов 3-го порядка, имеет непрерывную производную 2-го порядка.

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

Для естественного кубического сплайна
, следовательно, система уравнений будет иметь вид:

и система уравнений (17) будет иметь вид:

Пример .

Исходные данные:

Заменить функцию
интерполяционным кубическим сплайном, значения которого в заданных узловых точках (см. табл.) совпадают со значениями функции в этих же точках. Рассмотреть разные краевые условия.

Рассчитаем значение функции в узловых точках. Для этого подставим в заданную функцию значения из таблицы.

Для разных краевых условий (4), (5), (6) найдем коэффициенты кубических сплайнов.

Рассмотрим первые краевые условия.

В нашем случае n =3,
,
,
. Чтобы найти
используем систему уравнений (3.18):

Вычислим и, используя формулы (7) и (11):

Подставим полученные значения в систему уравнений:

Решение системы:

С учетом первых краевых условий коэффициенты сплайна:

Рассмотрим определение коэффициентов сплайна с учетом краевых условий (3.5):

Найдем производную функции
:

Вычислим
и
:

Подставим в систему уравнений (21) значения и:

Используя формулу (20) определим  0 и  3:

С учетом конкретных значений:

и вектор коэффициентов:

Рассчитаем значения кубического сплайна S(x) в серединах отрезков интерполяции.

Середины отрезков:

Для вычисления значения кубического сплайна в серединах отрезков интерполяции воспользуемся формулами (7) и (9).

3.1.

Найдем и
:

В формулу (3.9) подставляем коэффициенты

3.2.

Найдем и
:

, для краевых условий (4), (5), (6):

3.3.

Найдем и
:

В формулу (9) подставляем коэффициенты
, для краевых условий (4), (5), (6):

Составим таблицу:

(1 кр.усл.)	(2 кр.усл.)	(3 кр.усл.)

Это функция, которая:

Проходит через все заданные точки
,
;

На каждом отрезке между соседними точками является кубической параболой;

Непрерывна вместе со своими первой и второй производными во всех точках.).

интерполяция
локальная			глобальная

линейная	параболическая	кубическая парабола	полином степени (N -1)	кубический сплайн
Рис. 1.5.

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

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

Если функция измеряется или вычисляется приближенно и погрешности существенны, то не имеет смысла проводить интерполяцию и переходят к аппроксимации. В латыни слово ap-proximo означает "почти близкий". При аппроксимации кривая проводится вблизи заданных точек в соответствии с некоторым критерием близости, например, критерием наименьших квадратов или минимаксным критерием. Различия интерполяции и аппроксимации иллюстрирует рис.1.6.

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

Непрерывная в дискретную (дискретизация),

Дискретная в непрерывную (интерполяция),

Дискретная в непрерывную (аппроксимация),

Непрерывная в непрерывную (интерполяция),

Дискретная в дискретную (сглаживание).

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

Кубический сплайн.
Кубические сплайны для интерполяции предложил использовать Шенберг в 1949 г. Слово "сплайн" происходит от названия длинных тонких металлических реек, которые с давних времен немецкие чертежники крепили гвоздиками на кульмане вместо лекал для проведения сложных кривых.

Кубический сплайн - это функция, которая:

Проходит через все заданные точек
,
;

На каждом отрезке между соседними точками является кубическим полиномом;

Непрерывна вместе со своими первой и второй производными во всех точках.

Заметим, что, благодаря третьему условию, кубическая парабола
через две точки проводится однозначно.

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

(2.1)

Причем между заданными точками имеем отрезок, так что в этой формуле
.

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

(2.2)

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

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

Постановка задачи: даны точек , . Определить все коэффициенты сплайна , , , т.е. всего
коэффициентов,
, т.к. отрезок.

Рассмотрим два любых соседних отрезка
и
с номерами
и . Точка для них является общей, см. рис. 2.1.

Для правого отрезка кубический сплайн имеет вид (2.1), а для левого, т.е. при

(2.3)

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

Такие тройки уравнений можно записать для всех внутренних узлов ,
, что даёт
уравнений.

В результате получаем

уравнений. Эти уравнения содержат

неизвестных, т.к. для каждого отрезка между узлами имеем 3 неизвестных. Очевидно, что для однозначного определения коэффициентов нужны ещё два уравнения.

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

Часто систему уравнений (2.8) записывают для вторых производных в узлах, обозначая их
. Тогда она принимает вид (Бахвалов, Численные методы, М., 2002):

(2.9)

, причем

и формально введено

ПОТОЧЕЧНОЕ ОПИСАНИЕ ПОВЕРХНОСТЕЙ.

Метод заключается в задании поверхности множеством принадлежащих ей точек. Следовательно, качество изображения при этом методе зависит от количества точек и их расположения.

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

Пример : Участки грунта на других планетах, формы небесных тел, информация о которых получена в результате спутниковых съемок. Микрообъекты, снятые с помощью электронных микроскопов.

Исходная информация о поточечно описанных объектах представляется в виде матрицы трехмерных координат точек.

Сплайны - это гладкие (имеющие несколько непрерывных производных) кусочно-полиномиальные функции, которые могут быть использованы для представления функций, заданных большим количеством значений и для которых неприменима аппроксимация одним полиномом. Так как сплайны гладки, экономичны и легки в работе, они используются при построении произвольных функций для:

o моделирования кривых;

o аппроксимации данных с помощью кривых;

o выполнения функциональных аппроксимаций;

o решения функциональных уравнений.

Рассмотрим задачу проведения гладких кривых по заданным граничным точкам, или задачу интерполяции. Поскольку через две точки можно провести сколь угодно много гладких кривых, то для решения этой задачи необходимо ограничить класс функций, которые будут определять искомую кривую. Математическими сплайнами называют функции, используемые для аппроксимации кривых. Важным их свойством является простота вычислений. На практике часто используют сплайны вида полиномов третьей степени. С их помощью довольно удобно проводить кривые, которые интуитивно соответствуют человеческому субъективному понятию гладкости. Термин “сплайн” происходит от английского spline – что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например для построения обводов кораблей или самолетов.

Рассмотрим вначале сплайновую функцию для построения графика функции одной переменной. Пусть на плоскости задана последовательность точек ,, причем . Определим искомую функцию , причем поставим два условия:

1) Функция должна проходить через все точки: , ;

2) Функция должна быть дважды непрерывно дифференцируема, то есть иметь непрерывную вторую производную на всем отрезке .

На каждом из отрезков , , будем искать нашу функцию в виде полинома третьей степени:

Сплайновая функция

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

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

Координаты точек на кривой описываются вектором , а три производные задают координаты соответствующего касательного вектора в точке. Например, для координаты :

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

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

Перепишем выражение для в векторном виде:

Обозначим вектор строку и вектор столбец коэффициентов , тогда .

Из (*) следует, что , . Для касательных ,

Отсюда получаем векторно-матричное уравнение:

Эта система решается относительно нахождением обратной матрицы размером .

Здесь - эрмитова матрица, - геометрический вектор Эрмита. Подставим выражение для нахождения : . Аналогично для остальных координат: , .

Рассмотрим задачу проведения гладких кривых по заданным граничным точкам, или задачу интерполяции. Поскольку через две точки можно провести сколь угодно много гладких кривых, то для решения этой задачи необходимо ограничить класс функций, которые будут определять искомую кривую. Математическими сплайнами называют функции, используемые для аппроксимации кривых. Важным их свойством является простота вычислений. На практике часто используют сплайны вида полиномов третьей степени. С их помощью довольно удобно проводить кривые, которые интуитивно соответствуют человеческому субъективному понятию гладкости. Термин “сплайн” происходит от английского spline – что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например, для построения обводов кораблей или самолетов.

Рассмотрим в начале сплайновую функцию для построения графика функции одной переменной. Пусть на плоскости задана последовательность точек , , причем . Определим искомую функцию , причем поставим два условия:

1) Функция должна проходить через все заданные точки: , .

На каждом из отрезков , будем искать нашу функцию в виде полинома третьей степени:

Рис. 40. Сплайновая функция.

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

Перепишем выражение для в векторном виде:

Обозначим вектор строку и вектор столбец коэффициентов , тогда .

Из (*) следует, что , . Для касательных ,

Отсюда получаем векторно-матричное уравнение:

Эта система решается относительно нахождением обратной матрицы размером .

Выпишем в явном виде формулы для вычисления координат точек сплайна. Так как , то умножая справа на , получаем:

Четыре функции в скобках называются функциями сопряжения.

Форму кривой, заданной в форме Эрмита, легко изменять если учитывать, что направление вектора касательной задает начальное направление, а модуль вектора касательной задает степень вытянутости кривой в направлении этого вектора, как показано на рис. 41.

Рис. 41. Параметрический сплайн в форме Эрмита. Вытянутость кривой вправо обеспечивается тем, что .

Рассмотрим форму Безье, которая отличается от формы Эрмита способом задания граничных условий, а именно, вместо векторов и вводятся точки (и соответствующие им радиус векторы) и , как показано на рис.42, такие что выполняются условия: и .

Рис. 42. Параметрический сплайн в форме Безье.

Переход от формы Эрмита к форме Безье осуществляется преобразованием:

, (*)

где - геометрический вектор Безье. Подставляя это в выражение для , получаем

Полезным свойством сплайнов в форме Безье является то что кривая всегда лежит внутри выпуклой оболочки, образованной четырехугольником . Это свойство можно доказать, пользуясь тем, что в выражении (*) коэффициенты принимают значения от 0 до 1 и их сумма равна единице.

Заметим, что матрица вида

- называется матрицей Безье.

Список литературы

1. Ньюмен, Спрулл, Основы интерактивной машинной графики, М. Мир, 1976.

2. Энджел Й. Практическое введение в машинную графику, Радио и Связь, 1984.

3. А. Вэн-Дэм, Дж. Фоли, Основы интерактивной машинной графики, т.1-2, М. Мир, 1985.

4. Е.В. Жикин, А.В.Боресков, Компьютерная графика. Динамика, реалистические ихображения, М., Диалог-МИФИ, 1995, 1997.

5. Л. Аммерал, Машинная графика на языке С, в 4-х томах, изд-во Сол. Систем, 1992.

6. Компьютер обретает разум. Пер. с англ. Под ред. В.Л.Стефанюка, М. Мир, 1990.

7. Роджерс, алгоритмические основы машинной графики. М. Мир, 1989.

8. Грайс, Графические средства персональных компьютеров, М., Мир, 1980.

9. Роджерс, Адамс, Математические основы машинной графики, М. Машиностроение, 1985.

10. Гилой, Интерактивная машинная графика, М., Мир, 1981.

11. Ф. Препарата, М. Шеймос, Вычислительная геометрия: Введение, М. Мир, 1989.

12. А.Фокс, М. Пратт, Вычислительная геометрия, М., Мир, 1982.

13. А.Б.Боресков, Е.В.Шикина, Г.Е.Шикина, Компьютерная графика: первое знакомство, Под ред. Е.В.Шикина, М., Финансы и статистика, 1996.

14. А.В.Фролов, Г.В.Фролов, Графический интерфейс GDI в MS WINDOWS, Москва, Изд-во Диалог-МИФИ, 1994.

15. Майкл Ласло, Вычислительная геометрия и компьютерная графика на С++, Москва, Бином, 1997.

16. Ю.Тихомиров, Программирование трехмерной графики, С.-Пб.: БХВ‑Санкт-Петербург,1999.

17. А.Хонич, Как самому создать трехмерную игру. М.:МИКРОАРТ, 1996.

18. М.Маров, 3D Studio MAX 2.5: справочник – СПб: «Питер», 1999. – 672 с.

19. А.Ла Мот, Д.Ратклифф и др. Секреты программирования игр/ Перев с англ. – СПб: Питер, 1995. – 720 с.

20. Н. Томпсон, Секреты программирования трехмерной графики для Windows 95. Перев с англ. – СПб: Питер, 1997. – 352 с.

* В этом определении при замене, скажем, оси Oz на ось Ox остальные оси заменяются по правилу циклической перестановки, то есть Oy заменится на Oz, а Ox заменится на Oy. Всего циклических перестановок может быть три: (x,y,z)®(y,z,x)®(z,x,y).

* Более строгое определение однородных координат дается в разделе линейной алгебры «Проективные пространства».

Слово сплайн (английское слово "spline") означает гибкую линейку, используемую для проведения гладких кривых через заданные точки на плоскости. Форма этого универсального лекала на каждом отрезке описывается кубической параболой. Сплайны широко используются в инженерных приложениях, в частности, в компьютерной графике. Итак, на каждом i –м отрезке [x i –1 , x i ], i= 1, 2,…, N, решение будем искать в виде полинома третьей степени:

S i (x )=a i +b i (x–x i )+c i (x –x i ) 2 /2+d i (x–x i ) 3 /6

Неизвестные коэффициенты a i , b i , c i , d i , i= 1, 2,..., N, находим из:

Условий интерполяции: S i (x i )=f i , i= 1, 2,..., N ; S 1 (x 0)=f 0 ,

Непрерывности функции S i (x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., N,

Непрерывности первой и второй производной:

S / i (x i– 1)=S / i– 1 (x i –1), S // i (x i –1)=S // i –1 (x i –1), i= 2, 3,..., N .

Учитывая, что , для определения 4N неизвестных получаем систему 4N –2 уравнений:

a i =f i , i= 1, 2,..., N,

b i h i – c i h i 2 /2 + d i h i 3 /6=f i – f i –1 , i= 1, 2,..., N,

b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., N,

d i h i = c i – c i– 1 , i= 2, 3,..., N.

где h i =x i – x i– 1. Недостающие два уравнения выводятся из дополнительных условий: S // (a )=S // (b )=0. Можно показать, что при этом . Из системы можно исключить неизвестные b i , d i , получив систему N+ 1 линейных уравнений (СЛАУ) для определения коэффициентов c i :

c 0 = 0, c N = 0,

h i c i –1 + 2(h i +h i +1)c i +h i +1 c i +1 = 6 , i= 1, 2,…, N –1. (1)

После этого вычисляются коэффициенты b i , d i:

, i= 1, 2,..., N. (2)

В случае постоянной сетки h i =h этасистема уравнений упрощается.

Данная CЛАУ имеет трехдиагональную матрицу и решается методом прогонки.

Коэффициенты определяются из формул:

Для вычисления значения S (x ) в произвольной точке отрезка z ∈[a, b ] необходимо решить систему уравнений на коэффициенты c i , i= 1,2,…, N –1, затем найти все коэффициенты b i , d i . Далее, необходимо определить, на какой интервал [x i 0, x i 0–1 ] попадает эта точка, и, зная номер i 0 , вычислить значение сплайна и его производных в точке z

S (z )=a i 0 +b i 0 (z–x i 0)+c i 0 (z–x i 0) 2 /2+d i 0 (z–x i 0) 3 /6

S / (z )=b i 0 +c i 0 (z–x i 0)+d i 0 (z–x i 0) 2 /2, S // (z )=c i 0 +d i 0 (z–x i 0).

Требуется вычислить значения функции в точках 0.25 и 0.8, используя сплайн – интерполяцию.

В нашем случае: h i =1/4, .

Выпишем систему уравнений для определения :

Решая эту систему линейных уравнений, получим: .

Рассмотрим точку 0.25, которая принадлежит первому отрезку, т.е. . Следовательно, получим,

Рассмотрим точку 0.8, которая принадлежит четвертому отрезку, т.е. .

Следовательно,

Глобальная интерполяция

В случае глобальной интерполяции отыскивается единый полином на всем интервале [a, b ], т.е. строится полином, который используется для интерполяции функции f(x) на всем интервале изменения аргумента x. Будем искать интерполирующую функцию в виде полинома (многочлена) m –ой степени P m (x )=a 0 +a 1 x+a 2 x 2 +a 3 x 3 +…+a m x m . Какова должна быть степень многочлена, чтобы удовлетворить всем условиям интерполяции? Допустим, что заданы две точки: (x 0 , f 0) и (x 1 , f 1), т.е. N=1. Через эти точки можно провести единственную прямую, т.е. интерполирующей функцией будет полином первой степени P 1 (x )=a 0 +a 1 x. Через три точки (N=2) можно провести параболу P 2 (x )=a 0 +a 1 x+a 2 x 2 и т.д. Рассуждая таким способом, можно предположить, что искомый полином должен иметь степень N .

Для того, чтобы доказать это, выпишем систему уравнений на коэффициенты. Уравнения системы представляют собой условия интерполяции в при каждом x=x i :

Данная система является линейной относительно искомых коэффициентов a 0 , a 1 , a 2 , …, a N. Известно, что СЛАУ имеет решение, если ее определитель отличен от нуля. Определитель данной системы

носит имя определителя Вандермонда . Из курса математического анализа известно, что он отличен от нуля, если x k ≠ x m (т.е. все узлы интерполяции различные). Таким образом, доказано, что система имеет решение.

Мы показали, что для нахождения коэффициентов
a 0 , a 1 , a 2 , …, a N надо решить СЛАУ, что является сложной задачей. Но есть другой способ построения полинома N –й степени, который не требует решения такой системы.

Полином Лагранжа

Решение ищем в виде , где l i (z ) – базисные полиномы N –й степени, для которых выполняется условие: . Убедимся в том, что если такие полиномы построены, то L N (x) будет удовлетворять условиям интерполяции:

Каким образом построить базисные полиномы ? Определим

, i= 0, 1,..., N.

Легко понять, что

Функция l i (z ) является полиномом N –й степени от z и для нее выполняются условия "базисности":

0, i≠k;, т.е. k=1,…,i-1 или k=i+1,…,N.

Таким образом, нам удалось решить задачу о построении интерполирующего полинома N– й степени, и для этого не нужно решать СЛАУ. Полином Лагранжа можно записать в виде компактной формулы: . Погрешность этой формулы можно оценить, если исходная функция g (x ) имеет производные до N+ 1 порядка:

Из этой формулы следует, что погрешность метода зависит от свойств функции g (x ), а также от расположения узлов интерполяции и точки z. Как показывают расчетные эксперименты, полином Лагранжа имеет малую погрешность при небольших значениях N <20 . При бόльших N погрешность начинает расти, что свидетельствует о том, что метод Лагранжа не сходится (т.е. его погрешность не убывает с ростом N ).

Рассмотрим частные случаи. Пусть N=1, т.е. заданы значения функции только в двух точках. Тогда базовые полиномы имеют вид:

, т.е. получаем формулы кусочно–линейной интерполяции.

Пусть N=2. Тогда:

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

Пример: Заданы значений некоторой функции:

x				3.5
f	-1	0.2	0.5	0.8

Требуется найти значение функции при z= 1, используя интерполяционный полином Лгранжа. Для этого случая N =3, т.е. полином Лагранжа имеет третий порядок. Вычислим значения базисных полиномов при z =1:

Подбор эмпирических формул

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

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

Для практики важен случай аппроксимации функции многочленами, т.е. .

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

Метод наименьших квадратов

Пусть для исходных данных x i , f i , i= 1,…,N (нумерацию лучше начинать с единицы), выбран вид эмпирической зависимости: с неизвестными коэффициентами . Запишем сумму квадратов отклонений между вычисленными по эмпирической формуле и заданными опытными данными: