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

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

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

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

Кусочно-линейная интерполяция

Простейшим и часто используемым видом локальной интерполяции является линейная (или кусочно-линейная) интерполяция. Она заключается в том, что узловые точки соединяются отрезками прямых (Рис.3.1), то есть через каждые две точки и проводится полином первой степени:

, при (3.5)

Коэффициенты и разные на каждом интервале , и находятся из выполнения условий интерполяции на концах отрезка:

(3.6)

Из системы уравнений (3.6) можно найти коэффициенты:

, (3.7)

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

Рис. 3.1. Кусочно-линейная интерполяция

Кусочно-квадратичная интерполяция

В случае квадратичной интерполяции, для каждых трех узловых точек , , , строится уравнение параболы:

, при (3.8)

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

(3.9)

Из системы уравнений (3.9) можно найти коэффициенты:

(3.10)

Рис.3.2. Кусочно-квадратичная интерполяция

Многочлен Лагранжа

При глобальной интерполяции на всем интервале строится единый многочлен. Одной из форм записи интерполяционного многочлена для глобальной интерполяции является многочлен Лагранжа:

(3.11)

где – базисные многочлены степени n:

(3.12)

То есть многочлен Лагранжа:

(3.13)

Многочлен удовлетворяет условию . Это условие означает, что многочлен равен нулю при каждом кроме , то есть – корни этого многочлена. Таким образом, степень многочлена равна n и при в сумме обращаются в нуль все слагаемые, кроме слагаемого с номером , равного .

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

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

Кусочно-линейная и кусочно-квадратичная локальные интерполяции являются частными случаями интерполяции многочленом Лагранжа.

Многочлен Ньютона

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

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

(3.14)

Разделенные разности второго порядка определяются через разделенные разности первого порядка:

(3.15)

Разделенные разности k -го порядка определяются через разделенную разность порядка :

(3.16)

Используя понятие разделенной разности интерполяционный многочлен Ньютона можно записать в следующем виде:

(3.17)

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

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

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

Интерполирование функций.

1) Необходимость: приблизить f(x) более простой функцией ф(х), совпадающей в узлах x_i с f(x_i), если f(x) определена только в узловых точках (результат эксперимента) или очень сложно вычисляется.

Условия Лагранжа: ф(х, с₀, с₁…с_n) = f_i,

0 < _{_}i < n, где с_i - свободные параметры, определяемые из данной системы уравнений.

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

приближения).

2) Пусть ф (х) = с₀ + с₁х + с₂х² +…+ с_nxⁿ (канонический вид полинома);сетка узлов может быть неравномерной.

Коэффициенты с_i определяются из условий Лагранжа:

Получившаяся СЛАУ относительно свободных

параметров с_i имеет решение, если среди узлов

х_i нет совпадающих.Ее определитель – определитель Вандермонда:

 

 

Общая блок-схема:

Ввод степени полинома N, значения аргумента х

Формирование (ввод) таблично заданной функции из N значений xi, F(xi), i = 1…N

Формирование Расширенной матрицы коэффициентов xi, fi

Вычисление коэффициентов Полинома сi Методом Гаусса

Вычисление Ф (х) в заданной точке

Вывод значения ф(х)

Стоп

 

3) Пусть задано n+1 значение функции f(x) в узлах x_j

ф(х) = P_n(х) = _i (x-x_j)/(x_i-x_j) - полином Лагранжа.

Преимущества: потребуется решать СЛАУ для определения значения полинома в точке х.

Недостатки: для каждого х полином требуется читать заново.

Погрешность формулы: (*)

Увеличение числа узлов и, соответственно, степени полинома P_n(x) ведет к увеличению погрешности из-за роста производных .

4) ф(х) = P_n(x) = A₀+A₁(x-x₀)+A₂(x-x₀)(x-x₁)+…+A_n(x-x₀)(x-x₁)…(x-x_n-1) - многочлен Ньютона для n+1 узла.

Коэффициенты Ф представляют собой разделенные разности и записываются в виде:

А₀ = f₀

A₁ = (f₀-f₁)/(x₀-x₁) = f₀₁

A₂ = (f₀₁-f₀₂)/(x₁-x₂) = f₀₁₂, где f₀₂ = (f₀-f₂)/(x₀-x₂)

A₃ = (f₀₁₂-f₀₁₃)/(x₂-x₃) = f₀₁₂₃, где f₀₁₃ = (f₀₁-f₀₃)/(x₁-x₃), а f₀₃ = (f₀-f₃)/(x₀-x₃)

и в общем случае A_k = (f_01…k-1-f_01…k)/(x_k-1-x_k)

Т.е. многочлен n-й степени выражается при помощи разделенных разностей через свои значения в узлах.

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

После определения коэффициентов полинома Ньютона вычисление его значений при конкретных аргументах х наиболее экономично проводить по схеме Горнера:

P₂(x) = A₀+ (x-x₀)(A₁+(x-x₂)(A₃+…)…)

Погрешность определяется тем же соотношением (*)

Входящая в состав погрешности величина

(х-х_i) = w_n(x) ведет себя при постоянном шаге так, как показано на рисунке. Многочлен Ньютона имеет погрешность 0(hⁿ⁺¹) и обеспечивает n+1-й порядок точности интерполяции.

 

! Между разделенными разностями и производными соответствующих порядков существует соотношение f ^<n>(x) ~ n! F_01…n, где n – степень производной. Это используется в численном дифференцировании и при оценке погрешностей интерполяции.

! Можно строить полиномы, не только проходящие через заданные точки, но и имеющие в них заданные касательные (интерполяционный многочлен Эрмита) или заданную кривизну. Количество всех полагаемых условий должно быть n-1, если n – степень полинома.

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

 

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

 

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

 

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

Обычно для сплайна выбирают кубический полином , определенный на интервале х из [x_i-1, х_i].

При этом вся кривая представляет собой набор таких кубических полиномов, с определенным образом подобранными коэффициентами а_i, b_i, c_i, d_i, i- параметр сплайна.

! Если вдоль сплайна совершается механическое движение, то непрерывность второй производной предполагает непрерывность ускорения и, следовательно, отсутствие резких изменений приложенной силы.

N

узлы

N+1 узлов

N интервалов

4N неизвестных

 

Условия подбора коэффициентов:

1)условия Лагранжа:, ,

2)непрерывность первой и второй производной в узлах

ф_i’(x_i) = ф_i+1’(x_i); ф_i”(x_i) = ф_i+1(x_i)

3) условия в крайних узлах x₀ и x_n. Обычно задают условия свободных концов сплайна:

ф₁”(x₀) = 0, ф_n”(x_n) = 0

Из полученных условий определяются зависимости между коэффициентами сплайнов:

В узле х = х_i-1 коэффициент a_i = f_i-1.

В следующем узле x = x_i выполняется условие a_i+b_ih_i+c_ih_i²+d_ih_i³ = f_i, где элементарный шаг h_i = x_i – x_i-1.

Потребуем непрерывности первой и второй производной на конце интервала

ф_i^/(x) = b_i+2c_i(x-x_i-1)+3d_i(x-x_i-1)² ,

ф_i^//(x) = 2c_i+6d_i(x-x_i-1);

 

В узле x = x_i первая производная

ф_i^/(x_i) = b_i+2c_ih_i+3d_ih_i² (1)

ф_i+1^//(x_i) = b_i+1 (2)

Приравнивая (1) и (2), получаем b_i +2c_ih_i+3d_ih_i² = b_i+1.

Вторая производная

ф_i^//(x_i) = 2c_i+6c_ih_i (3)

ф_i+1^//(x_i) = 2c_i (4)

Приравнивая (3) и (4), получаем в свою очередь c_i+3d_ih_i = c_i+1. Таким образом стыкуем все полиномы в узлах 1 ≤ i ≤ n-1. В крайних точках диапазона

ф₁^//(x₀) = 2c₁ = 0 → c₁ = 0

ф₁^//(x_n) = 2c_n+6d_nh_n = 0 → c_n +3d_nh_n = 0

Для всех 0 ≤ i ≤ n вышеприведенные соотношения представляют собой полную систему 4 n линейных алгебраических уравнений относительно коэффициентов сплайнов, которую можно привести к системе ЛАУ, выразив коэффициенты a _i, b _i, d _i через c_i и решить методом Гаусса или прогонки.

Система N линейных уравнений для коэффициентов с_i:

 

для ,

где h_i = x_i-x_i-1

 

После определения коэффициентов c_i, 2N коэффициентов b_i и d_i вычисляются по формулам:

,

И N уравнений для ,

 

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

Многомерная интерполяция

1) Последовательная интерполяция на прямоугольной сетке. Пусть заданы z _{i j} = z(x_i, y_j) требуется найти z(x, y). Сначала при фиксированных y_j0 найдем значение z(x, y_j0),

Затем по полученному набору значений найдем z(x, y).

В случае интерполяции полиномом Лагранжа общая формула имеет вид

где k и m – количество узлов по сторонам прямоугольной сетки.

2) Треугольная конфигурация узлов.

z (x₀, x₁, y) = [z(x₀, y)-z(x₁, y)]/(x₀-x₁)

z (x, y₀, y₁) = [z(x, y₀)-z(x,y₁)]/(y₀-y₁)

Многочлен Лагранжева типа в этом случае имеет вид