Оценка погрешности интерполяционных формул При заданном наборе узлов интерполяции существует один и только один интерполяционный многочлен. Формулы Лагранжа, Ньютона, Гаусса и другие порождают один и тот же многочлен (при условии, что вычисления производятся точно). Разница между ними лишь в алгоритме построения, а многочлен Лагранжа не содержит явных выражений для коэффициентов. Исходя из принципа построения интерполяционного полинома, следует, что в точках узлов значения полинома и табличной функции полностью совпадают. В других же точках существует разница между полиномом и функцией, которая определяется остаточным членом R xf x L x n n Пусть функция f (x ) во всей области a x b n 1 имеет производные f x ,f x ,f x ,..., f x до n 1 порядка включительно. Введём вспомогательную функцию u x f x L x k x n n 1 где x x x x x x x ... x x n 1 0 1 2 n k - постоянный коэффициент. x0,x1,x2,.... xn Функция u x имеет n 1 корень в точках Выберем коэффициент k таким образом, чтобы функция u x имела n 2 -й корень в любой, но фиксированной, точке x отрезка не совпадающей с a ,b узловыми точками. Для этого нужно положить f x L x k x 0(*-*) n n 1 Отсюда, так как , следует k x 0 n1 fxL x n k x n 1 (*--*) При таком выборе коэффициента k функция u x будет иметь n 2 корня на отрезке a ,b и обращаться в нуль на концах каждого отрезка x , x , x , x , ..., x , x x , x ,... x , x 0 1 1 2 i i 1 n 1 n Применяя теорему Ролля к каждому из этих отрезков, можно сделать вывод, что производная u x имеет не менее n 1 корня на отрезке a ,b . Теорема Ролля Производная f x действительного многочлена f (x) имеет нечётное число действительных корней между двумя соседними действительными корнями многочлена f (x ). Вторая производная u x имеет не менее n корней на отрезке a ,b . Продолжая эти рассмотрения для производных более высоких порядков, можно сделать вывод, n1 x что производная u имеет хотя n1 бы один нуль на отрезке a ,b , т.е. u 0 . n 1 n1 x n 1 ! Так как Ln x0и , то из n 1 n 1 n 1 (*-*) имеем u x f x k n 1 ! 1 и при x получаем 0 n fn k 1 ! f , откуда следует k n1! n1 (*---*) Сравнивая правые части (*--*) и (*---*) получаем соотношение n 1 f x L x f n n 1 ! x n 1 и, следовательно, f (*-4-*) f x L x x n 1 n 1 ! n n 1 т.к x произвольно, то можно записать (*-4-*) в виде n 1 f (*-5-*) R x f x L x x n n 1 n 1 ! n где зависит от x и лежит внутри отрезка a ,b . Введя обозначение M max f x n 1 a x d получаем оценку абсолютной погрешности интерполяционной формулы Лагранжа n 1 M n 1 R x f x L x x n n n 1 n 1 ! (*-6-*) x x x x x ... x x n 1 0 1 n x x0 Используя замену q h записать как (*-7-*) можно (*-6-*) M n 1 n 1 R x f x L x q q 1 q 2 ... q n h n n n 1 ! Из проведенной оценки абсолютной погрешности интерполяционной формулы Лагранжа можно для функции f (x ) с равноотстоящими узлами (первая интерполяционная формула Ньютона) записать n 1 f n 1 R x q q 1 q 2 ... q n h n n 1 ! где - некоторое промежуточное значение между узлами интерполирования x0,x1,x2,.... xn и точкой x . Интерполяционная формула Ньютона, как правило, обрывается на членах, содержащих такие разности, которые в пределах заданной точности можно считать постоянными. n 1 Полагая, что конечные разности y почти постоянны для функции f (x ) и шаг h достаточно мал, и учитывая, что n 1 y x lim n 1 h 0h n 1 f можно положить y 0 n1 h n 1 f n 1 тогда остаточный член для первой интерполяционной формулы Ньютона n 1 y n 1 0 R x q q 1 q 2 ... q n h n n 1 ! При тех же условиях остаточный член для второй интерполяционной формулы Ньютона n 1 y n 1 n R x q q 1 q 2 ... q n h n n 1 ! Выбор способа интерполяции – локального или глобального - определяется особенностями решаемой задачи (точностью, быстродействием и др.). Повышение степени интерполяционного полинома (при локальной интерполяции) не всегда повышает точность интерполяции, т.к. не всегда ясно поведение производной n1 f x при увеличении n Интерполяция табличной функции с неравноотстоящими узлами Единственность полинома Лагранжа. Пусть существует другой полином Qn x степени не выше n , который решает задачу интерполяции Qnxi yi Построим новый многочлен , Rx Lx Qx n n n который имеет степень не выше n и во всех xn обращается в нуль, в силу узлах x0,x1,x2,.... x x L y равенства значений Q . n i n i i xn Получается, что точки x0,x1,x2,.... являются корнями многочлена Rn x . Многочлен Rn x не может иметь более корней n . Следовательно, многочлены Qn xi и Ln xi должны полностью совпадать Разделённые разности На практике часто встречаются таблицы с неравноотстоящими узлами, т.е. таблицы с переменным шагом. Для этих таблиц понятие конечных разностей обобщается введением так называемых разделённых разностей. Пусть функция y f x задана yn таблично y0,y 1,y 2,... xn , а и значения аргумента x 0,x 1,x 2,.... x x x 0 i i 1 i i 0 , 1 , 2 ,... соответствующие значения функции, у которой разности не равны между собой. Отношения вида y y i 1 i xi,xi1 x x i 1 i называются разделёнными разностями первого порядка. По аналогии - разделённые разности второго порядка запишутся как x , x x , x i 2 i 1 i 1 i x , x , x i i 1 i 2 x x i 2 i По аналогии строятся разделённые разности более высоких порядков. Интерполяционная формула Ньютона для неравноотстоящих значений аргумента записывается как P x y x , x x x 0 0 1 0 x , x , x x x x x ... 0 1 2 0 1 x , x ,... x x x x x ... x x 0 1 n 0 1 n 1 Интерполяция сплайнами Механическая модель сплайна Узлы фиксации Гибкий стержень Форма этого стержня описывается функцией y S x Из курса сопротивления материалов известно, что уравнение свободного равновесия имеет вид IV S x 0 следовательно, между парой соседних узлов интерполяции функция S x является многочленом степени не выше третьей. S x S x a b x x c x x d x x , i i i i 1 i 2 i 1 i x x x i 1 i (*) 3 i 1 На каждом отрезке xi1 xxi имеется четыре неизвестных коэффициента ai , bi , ci ,di , следовательно, на всём интервале x0 , xn число неизвестных - 4n . Для их определения необходимо построить систему 4n уравнений. На каждом отдельном участке xi 1 , xi из условия прохождения графика функции S x через заданные точки следует S x y ,S x y i i 1 i 1 i i i Эти условия можно записать в виде S x a y i i 1 i 1 i 1 S x a b c h d h y i i i ih i i 2 ii h x x , i i i 1 3 ii i 1 ,2 , 3 , ..., n Эта система содержит уравнений 2n . Свободное равновесие обеспечиваются условиями непрерывности первых и вторых производных во внутренних узлах интерполяции, т.е. условиями гладкости второго порядка кривой во всех внутренних точках – S x S x ,S x S x , (**) i i i 1 i i i i 1 i i 1 , 2 , 3 , ... , n 1 Вычисляя эти производные из многочлена 2 (***) S x b 2 c x x 3 d x x , i i i i 1 i i 1 S x 2 c 6 d x x i i i i 1 Подставляя эти выражения в (**)получаем уравнений 2 b b 2 h c 3 h i 1 i i i id i (*) ci1 ci 3 h id i i1 ,2 ,3 ,... ,n 1 (*4*) 2n 2 Оставшиеся необходимые два уравнения получаются из условий закрепления концов сплайна, в которые входят значения первой и второй производной функции S x в точках x 0 и i i S b 2 c n . Из (***) следует, ix 1 i, S ix 1 i и, следовательно, в точке x 0 имеем , x S x b ,S x 2 c 1 0 1 1 0 1 т.е. значения производных в точке x 0 присутствуют в системе. Значения производных в точке x n отсутствуют в системе, поэтому они вводятся с помощью дополнительных переменных bn 1 и c n 1 , т.е. S x b ,S x 2 c n n 1 n n 1 Из условия непрерывности производных в точке x n 2 следует, что b b 2 h c 3 h d n 1 n nn n ni c c 3 h d n 1 n n n С учётом этих дополнений (*4*) можно рассматривать для всего диапазона индексов i 1,2,3,...,n Построенная таким образом система содержит 4n 2 неизвестных и 4n уравнений. Эту систему можно дополнить одним из двух условий закрепления концов сплайна: S x b k , S x b k 0 1 1 n n 1 2 (%) или S x 2 c m , S x 2 c m 0 1 1 n n 1 2(%%) где k1, k2, m 1, m 2 - заданные числа. Например, из рис. «Механическая модель сплайна» видно, что при заданных углах наклона и k tg , k tg 1 2 При свободном закреплении концов сплайна, можно приравнять нулю кривизну линии в точках закрепления (т.е. вторые производные равны нулю). Полученная таким образом функция называется свободным кубическим сплайном. С учётом (%) или (%%) получаем систему 4 n 2 уравнений для определения коэффициентов - 2n уравнений, a i 1 ,2 ,..., n i,d i b i,c i i 1 ,2 ,..., n 1 - 2n 2 уравнений. Полученную систему линейных алгебраических уравнений можно существенно упростить, используя условия сшивки функции S x на n) границах отдельных участков (в узлах i 1, 2,..., по значениям функции и её первой и второй производным. ai = yi 1 ci1 ci di 3hi y y i i 1 h i b c 2 c i i 1 i h 3 i Система уравнений относительно коэффициентов y1 y0 2 1 h1*c1 h1*c2 k1 3 3 h1 ci y2 y1 y1 y0 h1*c1 2h1 h2 *c2 h2 *c3 3 h h 1 2 y3 y2 y2 y1 h2 *c2 2h2 h3*c3 h3 *c4 3 h h c 3 2 .......... .......... .......... .......... ......... i yn yn1 yn1 yn2 hn1*cn1 2hn1 hn *cn hn *cn1 3 h h n n1 yn yn1 1 2 hn *cn hn *cn1 k2 3 3 hn 1 3 5 0 2 4 y y 1 0 k 1 h 1 y y0 y2y 1 1 1 2 3 * h h 0 0 0 0 c 1 1 h h 3 1 2 1 3 h 2 h h h 0 0 0 c y y2 y2y 1 2 2 3 1 1 2 3 * 0 h 2 h h h 0 0 c 3 h h 2 2 3 3 3 2 0 h3h4 h4 0 h 2 0 c y y y2 3 4 y 4 3 3 3 * 0 h h4h5 h5 c5 h4 0 0 h 2 3 4 1 2 y y4 y4y 5 3 6 c 3 0 0 0 0 h h 5 5 * h 3 3 h 5 4 k ynyn1 2 h n аппроксимация Аппроксимация табличной функции y f(xi) Невязка yi i f(xi )yi mini2 x xi y Экспериментальные данные с погрешностью измерений Аппроксимирующая функция x Метод наименьших квадратов. Метод наименьших квадратов заключается в построении функции приближения на всём множестве точек xi . В качестве функции приближения используем полином x c c x c x c x ... c x 0 1 2 3 2 3 m m Для каждого значения табличной функции y f (x) можно записать c c x cx cx ... cx y 1 0 1 1 1 2 21 3 31 m m1 c c x cx cx ... cx y 2 0 1 2 2 2 22 3 32 m m2 i 2 3 m c c x c x c x ... c x y 3 0 13 23 33 m3 3 .......... .......... .......... .......... .......... .......... ......... ... 2 3 m c c x c x c x ... c x y n 0 1n 2n 3n mn n где i - невязка, т.е. разница между значением y i и значением приближающей функции xi в точке xi . Наилучшее приближение табличной функции y f (x) определяется путём минимизации функции S построенной из невязок i . n n xi,c0,c1,c2,..., yi S c m i 0 2 i 2 i 0 или n S c c x cx ... cx y 0 1 i i i 0 2 2i m mm 2 cm Считаем коэффициенты c0,c 1,c 2,..., независимыми переменными, тогда условия минимума функции S определяются из выполнения условий минимума S S S S 0 , 0 , 0 , 0 c c c c 0 1 2 m n S 2c0 c1xi c2xi2 c3xi3 ...cmximyi 0 co i0 n S 2c0 c1xi c2xi2 c3xi3 ...cmximyi xi 0 c1 i0 n S 2c0 c1xi c2xi2 c3xi3 ...cmximyi xi2 0 c2 i0 .......... .......... .......... .......... .......... .......... .......... ... n S 2 3 m m 2c0 c1xi c2xi c3xi ...cmxi yi xi 0 cm i0 cm Собирая коэффициенты при неизвестныхc0,c1,c2,..., получаем систему уравнений n n n n n 0 i 0 i 0 i 0 i 0 i n n n n n n 0 i 0 i 0 i 0 i 0 i 0 i m 3 2 n1c0c1 yi x c ... x c x c x i m i 3 i 2 i 1 m 4 3 2 x x c ... x c x c x c x c i i iy m i 3 i 2 i 1 i 0 n n n n n n 2 x x c ... x c x c x c x c i yi m 3 2 1 0 0 i 2 i 0 i 3 i 0 i 4 i 0 i 5 i 0 i 2 m i 0 i ....... .......... .......... .......... .......... .......... .......... .......... .......... n n n n n n 0 i 0 i 0 i 0 i 0 i 0 i m m 2 3 m 2 m 1 m m x x c ... x c x c x c x c i i yi m i 3 i 2 i 1 i 0 Получена система линейных относительно cm уравнений, в коэффициентов c0,c1,c2,..., которой при любом n m 1 число уравнений равно числу неизвестных. Такая система называется нормальной системой и решается методами решения СЛАУ, рассмотренными в последующих разделах.