Численные методы (стр. 2 из 3)

(6.5)

Строится система вложенных отрезков

¦⁽ⁿ⁺¹⁾ -производная (n+1)-го порядка

Пусть

(6.6)

Если ¦(c)-полином n-ой степени, то производная (n+1)-го порядка равна 0, тогда R_n(x)≡0 и мы получаем точную аппроксимацию.

Теорема:

Многочлен Лагранжа вида (6.4) для таблично заданной функции единственен.

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

Пусть Q_n(x)- многочлен Лагранжа, построенный для этой же функции ¦(c) по тем же узлам интерполяции. Q_n(x)¹P_n(x) Q_n(x_i)=y_i=P_n(x_i),

Рассмотрим многочлен L_n(x)= Q_n(x)-R_n(x)-это многочлен n-ой степени, для которого точки x_i, i=0,n являются корнями. Это противоречит основной теореме алгебры, которая говорит о том, что полином n-ой степени имеет ровно n корней . А L_n(x) имеет n+1 корней . Противоречие доказывает теорему.

Интерполяционная схема Эйткина

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

Пусть ¦(c)- непрерывна, узлы выбраны на отрезке [a;b] таким образом, что:

Введем функцию

x_i-узлы интерполяции;

y_i=¦(c)

Полином Лагранжа: P_n (x) см. (6.4)

Таким образом, функция Q_0,1 (x) представляет собой полином Лагранжа l-ой степени, построенной по узлам x₀ ,x₁ введем функцию вида

Функция Q_1,2 (x)- интерполяционный полином Лагранжа, построенный по узлам x₁ ,x₂.

Введем теперь функцию

Аналогично:

Q_0,1,2 (x₂)= у₂

В силу единственности полинома Лагранжа, построенного по узлам x₀, x₁ ,x₂

функция Q_0,1,2 (x) представляет собой интерполяционный полином Лагранжа 2-ой степени, построенный по узлам x₀, x₁ ,x₂ .

Введем функцию:

(7.1)

Функция представляющая собой полином Лагранжа 2-ой степени, построенного по узлам x₀, x_1,…x_i.

Формула (7.1) позволяет рекуррентно вычислять полином Лагранжа любой степени.

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

(7.1)-интерполяционная схема Эйткина.

КОНЕЧНЫЕ РАЗНОСТИ

Пусть функция ¦(c) задана на системе равноотстоящих узлов x_i=x₀+ih,

где h-шаг сетки, y_i=¦(c_i).

Конечной разностью первого порядка в точке x₀ называется ∆y₀=y₁-y₀

Конечной разностью первого порядка в точке x_i: ∆y_i=y_i+1-y₀-y_i

Конечной разностью второго порядка в точке x₀ : ∆²y₀=∆y₁-∆y₀

Конечной разностью второго порядка в точке x_i: ∆²y_i=∆y_i+1-∆y_i

Общая формула для конечной разности k-того порядка в точке x_i:

∆^ky_i=∆^k-1y_i+1-∆^ky(7.2)

Заметим: ∆⁰y_i= y_i

Формула (7.2) позволяет вычислять рекуррентно конечные разности

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

чем меньше h, тем точность выше

Аналогично можем получить связь

; (7.3)

Свойства конечных разностей

В связи с производными вида(7.3)конечные разности обладают свойствами:

1. постоянные, равны нулю;

2. постоянный множитель у функции выносится за знак

3. суммы 2-х функций равны сумме каждой функции

4. полинома n-ой степени, n-го порядка постоянны и равны

∆ⁿy=hⁿa_nn!

a_n-коэффициент при xⁿ полинома R_n(x)

Верно и обратное утверждение: все конечные разности n-го порядка некоторой функции постоянны и одинаковы, конечные разности n +1-го порядка равны 0, а конечные разности n-1-го порядка различны, то функция представляет собой полином n-ой степени.

Распространение ошибки в исходных данныхпри вычислении конечные разности

Любые измерения несут в себе погрешность (ошибка округления, точность измерения приборов)

Пусть значения функции определены в узлах x₀,

и в некоторой точке x_kзначение некоторой точке x_kзначение функции найдено с ошибкой ε, т.е ỹ_k+ ε

Составим таблицу конечных разностей

x_k-2 y_k-2 ∆y_k-2 ∆²y_k-2 ∆³y_k-3 +ε

x_k-1 y_k-1 ∆y_k-1 +ε∆²y_k-2 +ε∆³y_k-2 -3ε

x_ky_k+ε ∆y_k-1 -ε∆²y_k-1 -2ε∆³y_k-1 +3ε

x_k+1y_k+1 ∆y_k+1 ∆²y_k+ε ∆³y_k-ε

x_k+2y_k+2 ∆²y_k+1

Как видно из таблицы конечных разностей при увеличении порядка конечных разностей ошибка в исходных данных распространяется и растет.

Такое взаимодействие ошибок называют шумом, если это ошибки округлений - то шумом округлений.

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

Столбец в таблице конечных разностей, в которой все конечные разности ≈0, называют «практическим постоянным»; при этом конечные разности высших порядков не используют.

Для интерполяции целесообразно использовать многочлен такой степени, которая совпадает с порядком «практической постоянной» конечных разностей.

ЛЕКЦИЯ №8

ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА НЬЮТОНА ДЛЯРАВНООТСТОЯЩИХ УЗЛОВ

Дана функция y=¦(c),заданная на сетке равноотстоящих узлов:

y_i=¦(c_i), x_i=x₀+ih_i,

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

N_n(x)=-a₀+a₁(x-x₀)+a₂(x-x₀)(x-x₁)+…+a_n(x-x₀)…(x-x_n-1) (8.1)

Необходимо посчитать его коэффициенты a_i. Будем находить из условия

N_n(x_i)=y_i

i=0: N_n(x₀)=y₀=a₀+a₁0+…+a_n0 a₀= y₀

i=1: N_n(x₁)=y₁= y₀+a₁(x₁-x₀) + a₂0+…+a_n0

x₁=x₀+1h=x₁-x₀=h

i=2: N_n(x₂)=y₂= y₀+∆y₀/h(x₂-x₀) (x₂-x₁) + a₃0+…+a_n0

x₂-x₀=2h

x₂-x₁=h

y₂= y₀+∆y₀2+a₂2h²

i=k:

(8.2)

Запишем теперь, используя (8.2), полином (8.1) в виде:

N_n(x)= y₀+∆y₀/h(x-x₀)+…+ ∆ⁿ y₀ /n!hⁿ(x-x₀)(x-x₁)… (x-x_n-1) (8.3)

Полином (8.3) 1-ый интерполяционный многочлен Ньютона. Он наиболее приспособлен для вычисления значения функции в точках, близких к x₀

С целью упрощения записи полинома введем переменную

x=x₀+gh

Если g-целое, то будет совпадать с номером узла

x₀ – базовый узел полинома (8.3)

x_i=x₀+gh- x₀-ih=h(g-i);

N_n(g)= y₀+∆y₀g+…+ ∆ⁿy₀ /n!g(g-1)(g-2)(g-n+1) (8.4)

Полином Ньютона в силу единственности существования интерполяционного полинома Лагранжа является одной из форм записи полинома Лагранжа, поэтому для полинома (8.3) справедливо, что формула остаточного члена полинома Лагранжа

Для вычисления функции в точках находящихся в середине сетки узлов интерполяции либо в ее конце, т. е близкие к x_n, применяют два подхода