Вычислительная математика. Лекция сентября 2014 г., МФТИ, Долгопрудный к.ф.-м.н. Уткин Павел Сергеевич (926) Интерполяция функций. Интерполяционные полиномы в форме Лагранжа и Ньютона. Погрешность интерполяции. Данная лекция доступна по адресу:

2 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Задача интерполяции. Примеры.

Постановка задачи интерполяции 3 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Неединственность

Приложения из области автоматизации проектирования 4 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Математическая модель течения Численная реализация Геометрия объекта Расчетная сетка Визуализация результатов Иллюстрации из: Плыкин М. FSI-технологии ANSYS // САПР и графика. – – Т. 7.

5 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Интерполяционные полиномы в форме Лагранжа и Ньютона

Интерполяция алгебраическими полиномами 6 Строим интерполянт в виде полинома: Коэффициенты a i находим из решения СЛАУ: Определитель матрицы – детерминант Вандермонда. В случае различия всех узлов сетки он отличен от нуля, и, значит, существует единственное решение системы – набор коэффициентов. Неизвестны Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

Определитель Вандермонда 7 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

Различные формы записи решения СЛАУ 8 Интерполяционный алгебраический полином В форме ЛагранжаВ форме Ньютона Утверждение 2.1. Если заданы N+1 узлов x 0, …, x N среди которых нет совпадающих, и значения функции в этих узлах u(x 0 ),..., u(x N ), то существует один и только один многочлен степени не выше N, принимающий в узлах x i заданные значения u(x i ). Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

Интерполяционный полином в форме Лагранжа (1) 9 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Строим интерполяционный полином в виде: Из условий интерполирования получаем: Эти соотношения выполняются при условиях: Каждая из функций c k (x) имеет не менее N нулей на [a,b].

Интерполяционный полином в форме Лагранжа (2) 10 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Ищем c k (x) в виде многочлена степени N: Из условия c k (x k ) = 1 находим: Таким образом, найден вид функций c k (x):

11 Примеры Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Интерполяционный полином в форме Лагранжа (2)

Интерполяционный полином в форме Ньютона. Разделенные разности. 12 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Данный полином – разностный аналог формулы Тейлора: Разделенные разности 1-го порядка: Тогда разделенные разности 2-го порядка: Рассмотрим u(x 0,x 1 ), u(x 1,x 2 ),..., u(x N–1,x N )

Таблица разделенных разностей 13 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. x0x0 u(x0)u(x0) x1x1 u(x1)u(x1) x2x2 u(x2)u(x2) xNxN u(xN)u(xN) Разделенные разности (РР) k-го порядка: u(x0,x1)u(x0,x1) u(x1,x2)u(x1,x2)... u(x N–1,x N ) РР 0РР 1РР 2РР N u(x0,x1,x2)u(x0,x1,x2) u(x N,x N–1,x N–2 ).... u(x 0,x 1,…,x N )

14 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Интерполяционный полином в форме Ньютона Примеры Добавка к P 1 (x)

15 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. «Лагранж» vs «Ньютон» Удобно применять, когда интерполируется одна и та же функция, но число узлов интерполяции постепенно увеличивается. Удобно применять, когда узлы интерполяции фиксированы и интерполируется не одна, а несколько функций. L N (x) и P N (x) – различные формы записи одного и того же многочлена Рекомендуется использовать при программной реализации Используют при доказательствах теорем

16 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Погрешность интерполяции

17 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Погрешность интерполяции Ошибка приближения функции интерполяционным полиномом N-ой степени в точке x: R N (x) = u(x) – L N (x) Утверждение 2.2. Пусть на отрезке [a,b] функция u(x) (N+1) раз непрерывно дифференцируема. Тогда: Доказательство. Если x = x i, то утверждение верно. Иначе введем в рассмотрение функцию: Функция g(t) имеет N+2 нуля на [a,b]:

18 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Погрешность интерполяции (доказательство) По обобщенной теореме Ролля:

19 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Погрешность интерполяции на равномерной сетке Утверждение 2.3. Для случая равномерной сетки на отрезке [a,b] для любого x на отрезке [a,b] Доказательство. Положим Тогда 0……N …… Маж. мн. в…3211…N

20 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Примеры

21 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

22 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Погрешность в задаче экстраполяции Экстраполяция – аппроксимация функции вне отрезка, на котором заданы узлы интерполяции. Экстраполяция функции менее надежна, чем интерполяция, и ее точность резко падает по мере удаления от носителя информации. Оценка ухудшается как за счет появления множителей, пропорциональных N, так и за счет увеличения оценки производной.

23 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

24 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

25 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Оптимальный выбор узлов интерполяции. Многочлены Чебышева.

26 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Как минимизировать погрешность интерполяции? Минимизируем за счет выбора узлов интерполяции Получили задачу на минимакс (или задачу о построении полинома, наименее уклоняющемся от нуля на заданном отрезке): Решение задачи – нормированный многочлен Чебышева степени N, а оптимальный выбор узлов интерполяции – нули многочлена Чебышева.

27 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Многочлены Чебышева

28 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Другая форма записи многочленов Чебышева Функция cos( N arccos x ) удовлетворяет тому же разностному уравнению, что и T N (x)

29 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. Нули многочленов Чебышева Отрезок [–1,1] Отрезок [a,b]

30 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол.

31 Интерполяция функций. Инт. пол. в форме Лагранжа и Ньютона. Погрешн. интерпол. При подготовке к лекции использовались 1. Петров И.Б., Лобанов А.И. Лекции по вычислительной математике: учеб. пособие. – М.: Интернет-Университет Информационных Технологий. Бином. Лаборатория знаний, – С. 133 – Самарский А.А., Гулин А.В. Численные методы. – М.: Наука, – С. 127 – Федоренко Р.П. Введение в вычислительную физику: учеб. пособие. – М.: Изд-во МФТИ, – С. 28 – Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.: Бином. Лаборатория знаний, – С. 58 – Press W.H. et al. Numerical Recipes in C. – Cambridge University Press. – P – пример программной реализации построения интерполяционных полиномов.