Математическая модель и численные методы. Интерполяционный полиномы

Лекция 1: Математическая модель и численные методы. Интерполяционный полиномы Численные методы развивались в зависимости от задач, стоящих перед человечеством. 3-4 тыс. лет назад людям необходимо было вычислить площади, объёмы. Первые инструменты: пальцы, счеты. Времена Ньютона. Решение задач астрономии, геодезии. Появляются логарифмические таблицы, логарифмическая линейка, примитивный арифмометр, численные методы. 40-50гг ХХ в. Этот период связан с развитием военной техники (развитие зенитных установок для быстрой и точной стрельбы). Появились первые ЭВМ. Определение: Под численным методом будем подразумевать тот метод решения задачи, который сводится к арифметическим и логическим операциям над числами, т.е. к тем действиям, которые выполняет ЭВМ. п.2 О погрешностях. Решения задачи, полученные численными методами, всегда имеют погрешности. Существует 4 типа погрешностей: 1) погрешность математической модели; 2) погрешность исходных данных; 3) погрешность численного метода; 4) погрешность округления в действиях над числами. Интерполяционный полиномы Одна из задач вычислительной математики состоит в том, чтобы более сложные объекты заменить более простыми, которые удобно записывать и хранить в памяти компьютера, в частности любую функцию можно приближенно представить в виде многочлена и в памяти компьютера хранить коэффициенты этого многочлена. При замене функции многочленом необходимо позаботиться о том, чтобы это приближение обладало необходимой точностью. На практике используют полиномы 2-х типов: полиномы Тейлора и интерполяционные полиномы. п.2 Интерполяционные многочлены Лагранжа. Постановка задачи: Пусть x0 , x1 ,..., xn- (n+1) точка, заданная на [a,b] причем Введем обозначения a = x0 < x1 < ... < xn = b f i = f ( xi ), i = 0,..., n i = 0,..., n приближенно Возникает задача: по заданным значениям f i , восстановить значение f (x ) в произвольной точке x . Часто для этого строиться многочлен Ln (x ) - степени n , такой, что (1.2) Ln ( xi ) = f ( xi ), i = 0,..., n Такой полином будем называть интерполяционным полиномом степени n, а точки xi – узлами интерполяции. a = x 0 x1 x2 b = xn Для удобства изложения под многочленами степени n мы будем подразумевать многочлены степени не выше n. Пример: Пусть задана (n+1) точка и значения функции f ( xi ) = 0, i Тогда Ln ( x) ≡ 0 . n = 0,..., является интерполяционным полиномом степени n. Задача восстановления функции f (x) по формуле f ( x) ≈ Ln ( x) при x ∈ [a, b] (1.3) называется задачей интерполяции. А восстановление функции f задачей экстраполяции. (x) по формуле (1.3) для x ∉ [a, b] наз. Выясним существование и единственность интерполяционного полинома, а затем решим вопрос о его погрешности. Теорема 9.1. Существует единственный интерполяционный интер полином n-ой степени, удовлетворяющий условиям (1.2). Док-во: Существование интерполяционного полинома установим построив этот полином: n=1 n=2 L1 ( x) = L2 ( x) = x − x1 x − x0 f0 + f1 , L1 ( x0 ) = f 0 , x0 − x1 x1 − x0 L1 ( x1 ) = f1 ( x − x1 )( x − x2 ) ( x − x0 )( x − x2 ) ( x − x0 )( x − x1 ) f0 + f1 + f2 ( x0 − x1 )( x0 − x2 ) ( x1 − x0 )( x1 − x2 ) ( x2 − x0 )( x2 − x1 ) L2 ( x0 ) = f 0 , L2 ( x1 ) = f1 , L2 ( x2 ) = f 2 (1.4) При ∀n ∈ N n Ln ( x) = ∑ pni fi ,где i =0 (1.5) ( x − x0 )...( x − xi −1 )( x − xi +1 )...( x − xn ) рni = , i = 0,...n. ( xi − x0 )...( xi − xi −1 )( xi − xi +1 )...( xi − xn ) Из (1.4) L n (x) является полиномом степени n и справедливо равенство: 1 при pni ( x j ) =  0 при i = j, i ≠ j. Интерполяционный полином построен – значит он существует. Определение. Интерполяционный полином, представленный в виде (1.4)называется интерполяционным полиномом Лагранжа, а функции (1.5)лагранжевыми коэффициентами Всегда можно записать равенство: f ( x) = Ln ( x) + Rn ( x), где Rn (x) – остаточный член или погрешности интерполяции. Справедлива следующая оценка погрешности M n +1 f (x) − L n (x) ≤ ω n (x) (n + 1)! где ωn ( x) = ( x − x0 )( x − x1 )...( x − xn ), M n +1 = max f ( n +1) ( x ) x∈( a ,b ) Оценка максимальной погрешности на [a, b] M n +1 max f ( x ) − L n ( x ) ≤ max ω n ( x ) x∈[ a , b ] x (n + 1)! ∈[ a , b ] Интерполяционный полином Ньютона. (см. Е.А. Волков Численные методы, М. Наука, 1987, & 7-9)