Конспект лекций (стр. 2 )

(4')

(4")

где − символ Кронекера.

Из условий (4") следует, что полином имеет

корень кратности ,

…

корень кратности ,

корень кратности ,

…

корень кратности

т. е. его можно представить в виде

где

,

а полином степени нужно определить из условий (4'):

(5)

Матрица этой системы относительно неизвестных − нижняя треугольная (докажите!).

Напомним формулу Лейбница для производных от произведения функций:

С помощью этой формулы легко получить решение системы (5) относительно неизвестных :

… (5')

…

.

Тогда полином может быть представлен в виде

и представление (3) интерполяционного полинома Эрмита в форме Лагранжа получено.

Представление интерполяционного полинома Эрмита в форме Ньютона

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

, (6)

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

.

Здесь мы имеем естественный порядок вычисления разделенных разностей

по мере добавления новых интерполяционных узлов.

В случае интерполяции Эрмита (кратные интерполяционные узлы) ситуация меняется:

·  добавляется либо новый интерполяционный узел кратности 1,

·  либо кратность некоторого интерполяционного узла увеличивается на 1.

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

, (7)

и кратность интерполяционного узла равна количеству элементов последовательности (7) равных этому узлу.

Формально перепишем формулу (6) для узлов (7):

, (8)

разделенные разности в этой формуле пока неопределенны, так как некоторые из узлов могут совпадать.

Последовательность (7) приблизим последовательностью попарно различных узлов

(9)

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

, (10)

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

Лемма 1. На системе узлов (9) существуют и конечны пределы разделенных разностей:

Доказательство.

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

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

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

Тогда

если .

Но, если , т. е. , то этой формулой пользоваться трудно (деление на нуль), но можно воспользоваться леммой 1.4:

,

так как .

Что и требовалось доказать.

Теорема 2. Интерполяционный полином

, (10)

на системе узлов

(9)

сходится к полиному

, (8)

который является интерполяционным полиномом Эрмита (в форме Ньютона) для функции , заданной на отрезке , по ее значениям , по значениям первых производных , …, в попарно различных точках (узлах) , при условии .

Доказательство.

Существование полинома и сходимость к нему последовательности полиномов следует леммы 1, причем, как это отмечалось при доказательстве леммы, полиномы не зависят от способа нумерации узлов (9), и, стало быть, полином не зависит от способа нумерации кратных интерполяционных узлов:

. (7)

Последним фактом мы воспользуемся для проверки интерполяционных условий (2), например, в узле кратности :

.

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

,

затем все остальные в некотором порядке.

Тогда формула (8) для полинома может быть переписана в виде

,

по которому легко проверить (проверьте!) выполнение условий интерполяции в кратном узле .

В силу произвольности выбора интерполяционного узла (мы выбрали , но могли выбрать и любой другой) полином удовлетворяет всем условиям интерполяции с кратными узлами.

Теорема доказана.

Оценка погрешности интерполирования

Теорема 3. Для погрешности интерполирования функции по ее значениям , по значениям первых производных: , …, в попарно различных точках (узлах) , при условии , интерполяционным полиномом Эрмита (который мы построили либо в форме Лагранжа (3) либо в форме Ньютона (8)), справедлива оценка

,

где .

Доказательство оставляется читателю в качестве упражнения.

Замечание. Пусть и если в качестве узлов интерполирования выбрать корни полинома , то

Докажите, что коэффициент при старшей степени полинома равен единице, а сам полином является полиномом, наименее уклоняющимся от нуля на отрезке (см. лекцию 9 ВМЛА).

Лекция 3.

Интерполирование кубическим сплайном

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

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

·  либо для вышеуказанного разбиения строится кусочно-полиномиальная функция (сплайн), непрерывная вместе с несколькими своими первыми производными на интервале .

Определение и построение кубического сплайна

Определение.

Кубическим сплайном, аппроксимирующим функцию на сетке по ее значениям , называется функция , удовлетворяющая следующим условиям:

a)  − полином третьей степени на каждом подъинтервале ;

b)  ;

c)  , − условие интерполирования.

Для определения сплайна :

неизвестных: по четыре коэффициента полинома третьей степени (условие а)) на каждом подъинтервале ,

мы имеем:

условий непрерывности , первой и второй производных от в точках (условие b)),

условие интерполяции (условие c)).

Таким образом, для определения неизвестных мы имеем условий, т. е., если условия независимы, то для единственности задачи построения сплайна нам не хватает двух условий. Обычно эти условия ставят на концах интервала (граничные условия). Мы ограничимся случаем

d)  .

Итак, мы должны определить кусочно-кубическую функцию :

, ,

по заданным значениям:

, , . (1)

Учитывая, что на интервале

сплайн можно представить в виде

(2)

(докажите эту формулу и равенства , …, , , …, ).

Для определения неизвестных воспользуемся условиями непрерывности первой производной от сплайна:

.

Вычислив эти производные, получим систему уравнений

(3)

Симметричная трехдиагональная матрица этой системы

имеет строгое диагональное преобладание в каждой строке и поэтому положительно определена и систему легко решить, например, методом прогонки.

Оценка погрешности

Погрешность интерполирования мы оценим, предполагая, что функция достаточно гладка: , а сетка равномерна, т. е. все ее шаги равны: .

Так как , то . Тогда (4)

Таким образом, нам осталось оценить

. (5)

Перепишем систему (3) в виде

и оценим разности , для которых легко получить соотношения

Практически очевидна справедливость следующих неравенств:

(6)

Используя следующие разложения в ряд Тейлора:

оценим :

. (7)

Получите неравенство (7) в качестве упражнения.

Неравенства (6) и (7) обеспечивают справедливость следующей леммы.

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

.

Теперь мы можем оценить .

Лемма 2. Вторая производная сплайна аппроксимирует вторую производную от функции в равномерной норме со вторым порядком точности по :

. (8)

Доказательство.

Неравенство (8) достаточно установить для любой точки .

Перепишем (5) в виде

Из леммы 1 следует, что .

Используя явный вид ошибки линейной интерполяции функции

получим для любой точки

,

что и требовалось доказать.

Из неравенств (4) и (8) получаем оценку погрешности.

Теорема 1. Для погрешности аппроксимации сплайном справедливы следующие оценки:

.

Численное дифференцирование

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

, (9)

где коэффициенты

не зависят от функции .

Оценить точность приближения производной, т. е. разность

,

довольно сложно: во-первых, мы не характеризовали функцию ; во-вторых, потребуется существование производных функции до порядка .

Оценка погрешности численного дифференцирования

Поэтому для оценки разности мы заменим разложением в ряд Тейлора в точке :

(10)

Тогда для любой функции имеем тождество

(11)

Если в это тождество подставить функцию равную полиному степени , -ая производная которого в точке равна 1, а значения остальных производных равны 0, т. е. функцию такую, что , и, следовательно, , то

Из этого тождества сразу получаем следующую лемму.

Лемма 3. Коэффициенты из (9) удовлетворяют соотношениям

(12)

Из (11) и леммы 3 получаем оценку погрешности численного дифференцирования.

Теорема 2. Для погрешности приближения линейной комбинацией из (9) имеет место представление

, (13)

где − остаточные члены разложений в ряды Тейлора (10).

Аппроксимация значения функции в центре интервала полусуммой ее значений на краях интервала

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

.

Так как интерполяционный полином по значениям и имеет вид

,

то

,

а из теоремы 2 имеем оценку

Итак, если , то

Аппроксимация производной разностью вперед

− разность вперед; так как то .

Аппроксимация производной разностью назад

− разность назад; так как то .

Аппроксимация производной центральной разностью

− центральная разность; так как то .

Некорректность численного дифференцирования

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