Вопрос 5 Методы повышения точности интерполяции

⇐ ПредыдущаяСтр 2 из 5Следующая ⇒

Интерполяционный многочлен Лагранжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n+1 пар чисел (x₀, y₀), (x₁, y₁), …, (x_n, y_n), где все x_j различны, существует единственный многочлен L(x) степени не более n, для которого L(x_j) = y_j.

В простейшем случае (n=1) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.

Задача интерполяции

Пусть функция задана таблицей своих значений на интервале :

, , (1)

Задача интерполяции - найти функцию , принимающую в точках те же значения .

Условие интерполяции:

: (2)

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

Если ищется только на отрезке - то это задача интерполяции, а если за пределами первоначального отрезка, то это задача экстраполяции.

· Интерполяция – определение промежуточных значений функции по известному дискретному набору значений функции.

· Экстраполяция – определение значений функции за пределами первоначально известного интервала.

· Аппроксимация – определение в явном виде параметров функции, описывающей распределение точек.

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

, (3)

При этом искомый полином называется интерполяционным полиномом.

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

, (4)

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

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

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

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

Сплайн – функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке [a, b], а на каждом частичном отрезке [ , ] в отдельности является некоторым алгебраическим многочленом.

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

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

, при (5)

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

(6)

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

, (7)

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

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

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

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

, при (8)

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

(9)

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

(10)

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

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

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

(11)

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

(12)

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

(13)

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

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

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

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

Пример:

Найдем формулу интерполяции для f(x) = tan(x) имеющей следующие значения:

Получим

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

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

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

(14)

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

(15)

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

(16)

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

(17)

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

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

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

Вопрос 17 Аппроксимация, устойчивость и сходимость разностных схем. Пример

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

Рассмотрим дифференциальное уравнение, заданное в некоторой области D, ограниченной контуром Г:

LU = f, (9.2)

где U - решение (9.2). Множество D_h ={M_h} состоящее из изолированных точек M_h, принадлежащих замкнутой области D, называется сеткой, а точки M_h - узлами сетки. Функция, определенная в узлах сетки, называется сеточной функцией U_h_.На практике, как правило, можно вычислить только приближенное сеточное значение функции U^(h).

Для нахождения U^(h) строим систему численных уравнений:

L_h(U^(h)) = f^(h), (9.3)

где L_h – разностный оператор, соответствующий оператору L, f^(h) – разностный аналог правой части.Уравнение (9.3) является разностной схемой.

Таким образом, в методе сеток происходит замена пространства V (пространства непрерывных в D функций U) на пространство V_h (пространство, образованное совокупностью сеточных функций U_h, определенных на D_h.). В линейных пространствах V_h и F_h введем нормы и , которые являются сеточными аналогами норм в пространстве V и F.

Сходимость

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

Определение. Говорят, что разностная схема (9.3) является сходящейся, если при h ® 0 выполняется условие

. (9.4)

Если выполнено условие (с=const, s> 0), то говорят, что имеет место сходимость со скоростью порядка s.

Аппроксимация

Аппроксимация – это приближение. Приближение чего-то к чему-то с той или иной точностью.

Определение. Говорят, что разностная схема (9.3) аппроксимирует задачу (9.2) на решение U , если

L_h(U_h ) = f^(h)+d f^(h) (9.5)

при h ® 0,

величина d f^(h) называется погрешностью аппроксимации.

Если (M=const, β > 0), то говорят, что разностная схема (9.3) аппроксимирует задачу (9.2) с погрешностью порядка β относительно h.

Устойчивость

Усто́ йчивость — способность системы сохранять текущее состояние при влиянии внешних воздействий.

Определение. Разностная схема (9.3) называется устойчивой, если существует такое h₀> 0, что для всех h< h₀ и любых f^(h)Î F_h выполняются условия:

1) разностная схема (9.3) имеет единственное решение;

2) , где M – постоянная, не зависящая от h и f^(h).

Теорема. Пусть разностная схема L_h(U^(h)) = f^(h) аппроксимирует задачу LU = f на решение U с порядком s> 0 относительно h и устойчива. Тогда эта схема будет сходящейся и порядок ее сходимости будет совпадать с порядком аппроксимации, т. е. будет справедлива оценка:

, (9.6)

где с – постоянная, не зависящая от h.

⇐ Предыдущая 123 4 5 Следующая ⇒