Численные Методы, 10 лекция (от 19 марта)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(→Построение H<sub>3</sub>(x)) |
||
(1 промежуточная версия не показана) | |||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 09 лекция (от 13 марта)|Предыдущая лекция]] | [[Численные Методы, 11 лекция (от 20 марта)|Следующая лекция]] |
- | + | ||
- | + | = Глава 2. Интерполирование и приближение функций = | |
- | + | == Параграф 3. Разделённые разности == | |
+ | |||
+ | Доказательство формулы, которая разделённая разность k-го порядка f. | ||
+ | |||
+ | Задача: выразить значение функции в k-м узле через значение функции в 0-м узле и разделённую разность k-го порядка. Решается она несложно. | ||
+ | |||
+ | <div class="comment">Как будто электричка подошла... Общий забег из столовой?</div> | ||
+ | |||
+ | * k = 1: | ||
+ | ** f(x<sub>0</sub>, x<sub>1</sub>) = f(x<sub>0</sub>)/(x<sub>0</sub> − x<sub>1</sub>) + f(x<sub>1</sub>)/(x<sub>1</sub> − x<sub>0</sub>) = (f(x<sub>1</sub>) − f(x<sub>0</sub>))/(x<sub>1</sub> − x<sub>0</sub>) | ||
+ | ** (x<sub>1</sub> − x<sub>0</sub>) × f(x<sub>0</sub>, x<sub>1</sub>) = −f(x<sub>0</sub>) + f(x<sub>1</sub>) | ||
+ | ** f(x<sub>1</sub>) = f(x<sub>0</sub>) + (x<sub>1</sub> − x<sub>0</sub>) × f(x<sub>0</sub>, x<sub>1</sub>) (1) | ||
+ | * k = 2 | ||
+ | ** f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) = f(x<sub>0</sub>)/((x<sub>0</sub> − x<sub>1</sub>)(x<sub>0</sub> − x<sub>2</sub>)) + f(x<sub>1</sub>)/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)) + f(x<sub>2</sub>)/((x<sub>2</sub> − x<sub>0</sub>)(x<sub>2</sub> − x<sub>1</sub>)) | ||
+ | ** ((x<sub>2</sub> − x<sub>0</sub>)(x<sub>2</sub> − x<sub>1</sub>)) × f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) = (−f(x<sub>0</sub>)(x<sub>2</sub> − x<sub>1</sub>))/(x<sub>0</sub> − x<sub>1</sub>) { = γ} + (f(x<sub>1</sub>)(x<sub>2</sub> − x<sub>0</sub>))/(x<sub>0</sub> − x<sub>1</sub>) { = α} + f(x<sub>2</sub>) | ||
+ | ** α = (f(x<sub>1</sub>)(x<sub>2</sub> − x<sub>0</sub>))/(x<sub>0</sub> − x<sub>1</sub>) = (x<sub>2</sub> − x<sub>0</sub>)/(x<sub>0</sub> − x<sub>1</sub>) × (f(x<sub>0</sub>) + (x<sub>1</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>)) = ((x<sub>2</sub> − x<sub>0</sub>)f(x<sub>0</sub>))/(x<sub>0</sub> − x<sub>1</sub>) { = β} − (x<sub>2</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) | ||
+ | ** β − γ = f(x<sub>0</sub>) × ((x<sub>2</sub> − x<sub>0</sub> − x<sub>2</sub> + x<sub>1</sub>)/(x<sub>0</sub> − x<sub>1</sub>)) = −f(x<sub>0</sub>) | ||
+ | ** ((x<sub>2</sub> − x<sub>0</sub>)(x<sub>2</sub> − x<sub>1</sub>)) × f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) = −f(x<sub>0</sub>) − (x<sub>2</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + f(x<sub>2</sub>) (2) | ||
+ | * По аналогии, общая формула: | ||
+ | ** f(x<sub>k</sub>) = f(x<sub>0</sub>) + (x<sub>k</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x<sub>k</sub> − x<sub>0</sub>)(x<sub>k</sub> − x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + … + (x<sub>k</sub> − x<sub>0</sub>)(x<sub>k</sub> − x<sub>1</sub>)…(x<sub>k</sub> − x<sub>k − 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>k</sub>) (3) | ||
+ | |||
+ | == Параграф 4. Интерполяционная формула Ньютона == | ||
+ | |||
+ | {x<sub>i</sub>}<sub>0</sub><sup>N</sup> — узлы интерполирования (n + 1 штук). Есть интерполируемая функция f(x), f(x<sub>i</sub>) = f<sub>i</sub>, i = 0…n. | ||
+ | |||
+ | Заменим в (3) x<sub>k</sub> на x: | ||
+ | |||
+ | N<sub>n</sub>(x) = f(x<sub>0</sub>) + (x − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x − x<sub>0</sub>)(x − x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + … + (x − x<sub>0</sub>)(x − x<sub>1</sub>)…(x − x<sub>n − 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>n</sub>) | ||
+ | |||
+ | Чтобы эта формула была интерполяционной функцией, N<sub>n</sub>(x<sub>i</sub>) = f(x<sub>i</sub>), i = 0…n | ||
+ | |||
+ | N<sub>n</sub>(x<sub>i</sub>) = f(x<sub>0</sub>) + (x<sub>i</sub> − x<sub>0</sub>)f(x<sub>0</sub>, x<sub>1</sub>) + (x<sub>i</sub> − x<sub>0</sub>)(x<sub>i</sub> − x<sub>1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, x<sub>2</sub>) + … + (x<sub>i</sub> − x<sub>0</sub>)(x<sub>i</sub> − x<sub>1</sub>)…(x<sub>i</sub> − x<sub>i − 1</sub>)f(x<sub>0</sub>, x<sub>1</sub>, …, x<sub>i</sub>) = f(x<sub>i</sub>), i = 0…n | ||
+ | |||
+ | Погрешность та же самая, но записана внешне по-другому: | ||
+ | |||
+ | |ψ<sub>N<sub>n</sub></sub>(x)| = |f(x) − N<sub>n</sub>(x)| ≤ M<sub>n + 1</sub>/(n + 1)! × |ω(x)|, M<sub>n + 1</sub> = sup<sub>a ≤ x≤ b</sub> |f(x)<sup>(n + 1)</sup>| | ||
+ | |||
+ | '''Замечание'''. Когда лучше использовать формулу Ньютона: очевидны два примера, которые показывают, что в одном случае удобно применять Ньютона, в другом — Лагранжа. У нас в Ньютоне всюду стоит функция и её разделённая разность, и она напоминает формулу Тейлора, некий её дискретный аналог, а узлы мы можем увеличивать сколько хотим, и если для специальной функции у нас она рассчитана грубая сетка, и нам надо её интерполировать. Лагранж удобен, когда у нас количество значений фиксировано, например, есть несколько датчиков. | ||
+ | |||
+ | == Параграф 5. Интерполирование с кратными узлами. Интерполяционная формула Эрмита == | ||
+ | |||
+ | Ранее мы добивались только совпадения значений функций, теперь же будем требовать совпадения производных. | ||
+ | |||
+ | Пусть у нас есть узлы x<sub>0</sub>, … x<sub>m</sub> — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных: | ||
+ | {| | ||
+ | |x<sub>0</sub> | ||
+ | |x<sub>1</sub> | ||
+ | |… | ||
+ | |x<sub>m</sub> | ||
+ | |- | ||
+ | |f(x<sub>0</sub>) | ||
+ | |f(x<sub>1</sub>) | ||
+ | |… | ||
+ | |f(x<sub>m</sub>) | ||
+ | |- | ||
+ | |f'(x<sub>0</sub>) | ||
+ | |f'(x<sub>1</sub>) | ||
+ | |… | ||
+ | |f'(x<sub>m</sub>) | ||
+ | |- | ||
+ | |… | ||
+ | |- | ||
+ | |f<sup>(a<sub>0</sub> − 1)</sup>(x<sub>0</sub>) | ||
+ | |f<sup>(a<sub>1</sub> − 1)</sup>(x<sub>1</sub>) | ||
+ | |… | ||
+ | |f<sup>(a<sub>m</sub> − 1)</sup>(x<sub>m</sub>) | ||
+ | |} | ||
+ | |||
+ | * a<sub>i</sub> ∈ N ( натуральное), i = 0…m | ||
+ | * a<sub>i</sub> — кратность i-го узла | ||
+ | |||
+ | Цель: построить H<sub>n</sub>(x) | ||
+ | |||
+ | Замечание. H<sub>n</sub><sup>(i)</sup> = f<sup>(i)</sup>(x<sub>k</sub>), k = 0…m, i = 0…a<sub>k</sub> − 1 (1) | ||
+ | |||
+ | При выполнении условия a<sub>0</sub> + a<sub>1</sub> + … + a<sub>m</sub> = n + 1 мы можем построить полином Эрмита, причём единственный. | ||
+ | |||
+ | Полином Эрмита строится аналогично полиному Лагранжа. | ||
+ | |||
+ | Общий вид полинома Эрмита: | ||
+ | H<sub>n</sub>(x) = ∑<sub>k = 0</sub><sup>m</sup> ∑<sub>i = 0</sub><sup>a<sub>k</sub> − 1</sup> c<sub>k, i</sub>(x)f<sup>(i)</sup>(x<sub>k</sub>) | ||
+ | * c<sub>k, i</sub>(x) — полином n-й степени | ||
+ | * x<sub>i</sub> — различные | ||
+ | |||
+ | В общем виде мы строить не будем, построим H<sub>3</sub>(x), у которого будет кратным только средний узел. Он потребуется для оценки в квадратурной формуле Гаусса. В чём фишка (тонкость): позволяет получать точную оценку квадратурной формулы. | ||
+ | |||
+ | === Построение H<sub>3</sub>(x) === | ||
+ | {| | ||
+ | |x<sub>0</sub> | ||
+ | |< | ||
+ | |x<sub>1</sub> | ||
+ | |< | ||
+ | |x<sub>2</sub> | ||
+ | |- | ||
+ | |f(x<sub>0</sub>) | ||
+ | | | ||
+ | |f(x<sub>1</sub>) | ||
+ | | | ||
+ | |f(x<sub>2</sub>) | ||
+ | |- | ||
+ | | | ||
+ | | | ||
+ | |f'(x<sub>1</sub>) | ||
+ | |} | ||
+ | |||
+ | Существует несколько способ построения H<sub>3</sub>(x). | ||
+ | |||
+ | <!-- педедыв --> | ||
+ | |||
+ | H<sub>3</sub>(x): | ||
+ | * H<sub>3</sub>(x<sub>0</sub>) = f(x<sub>0</sub>) | ||
+ | * H<sub>3</sub>(x<sub>1</sub>) = f(x<sub>1</sub>) | ||
+ | * H<sub>3</sub>(x<sub>2</sub>) = f(x<sub>2</sub>) | ||
+ | * H<sub>3</sub>'(x<sub>1</sub>) = f'(x<sub>1</sub>) (1) | ||
+ | |||
+ | Это получается из Лагранжа путём предельного перехода. | ||
+ | |||
+ | H<sub>3</sub>(x) будем искать в виде (2): | ||
+ | * H<sub>3</sub>(x) = c<sub>0</sub>(x)f(x<sub>0</sub>) + c<sub>1</sub>(x)f(x<sub>1</sub>) + c<sub>2</sub>(x)f(x<sub>2</sub>) + b<sub>1</sub>(x)f'(x<sub>1</sub>) (2) | ||
+ | * c<sub>i</sub>(x), b<sub>i</sub>(x) — многочлены 3-й степени | ||
+ | |||
+ | {| | ||
+ | |* c<sub>0</sub>(x<sub>0</sub>) = 1 | ||
+ | |* c<sub>1</sub>(x<sub>0</sub>) = 0 | ||
+ | |* c<sub>2</sub>(x<sub>0</sub>) = 0 | ||
+ | |* b<sub>1</sub>(x<sub>0</sub>) = 0 | ||
+ | |- | ||
+ | |* c<sub>0</sub>(x<sub>1</sub>) = 0 | ||
+ | |* c<sub>1</sub>(x<sub>1</sub>) = 1 | ||
+ | |* c<sub>2</sub>(x<sub>1</sub>) = 0 | ||
+ | |* b<sub>1</sub>(x<sub>1</sub>) = 0 | ||
+ | |- | ||
+ | |* c<sub>0</sub>(x<sub>2</sub>) = 0 | ||
+ | |* c<sub>1</sub>(x<sub>2</sub>) = 0 | ||
+ | |* c<sub>2</sub>(x<sub>2</sub>) = 1 | ||
+ | |* b<sub>1</sub>(x<sub>2</sub>) = 0 | ||
+ | |- | ||
+ | |* c<sub>0</sub>'(x<sub>1</sub>) = 0 | ||
+ | |* c<sub>1</sub>'(x<sub>1</sub>) = 0 | ||
+ | |* c<sub>2</sub>'(x<sub>1</sub>) = 0 | ||
+ | |* b<sub>1</sub>'(x<sub>1</sub>) = 1 | ||
+ | |} | ||
+ | |||
+ | * c<sub>0</sub>(x) = k(x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>2</sub>) | ||
+ | * c<sub>0</sub>(x<sub>0</sub>) = k(x<sub>0</sub> − x<sub>1</sub>)<sup>2</sup>(x<sub>0</sub> − x<sub>2</sub>) | ||
+ | Отсюда | ||
+ | * c<sub>0</sub>(x) = ((x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>2</sub>))/((x<sub>0</sub> − x<sub>1</sub>)<sup>2</sup>(x<sub>0</sub> − x<sub>2</sub>)) | ||
+ | Аналогично | ||
+ | * c<sub>2</sub>(x) = ((x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>0</sub>))/((x<sub>2</sub> − x<sub>1</sub>)<sup>2</sup>(x<sub>2</sub> − x<sub>0</sub>)) | ||
+ | * b<sub>1</sub>(x) = b<sub>0</sub>(x − x<sub>0</sub>)(x − x<sub>1</sub>)(x − x<sub>2</sub>) = b<sub>0</sub>[(x − x<sub>0</sub>)(x − x<sub>2</sub>)](x − x<sub>1</sub>) | ||
+ | * b<sub>1</sub>' = b<sub>0</sub>([ ]'(x − x<sub>1</sub>) + []) | ||
+ | * b<sub>1</sub>'(x<sub>1</sub>) = b<sub>0</sub>(x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>) | ||
+ | * b<sub>1</sub>(x) = ((x − x<sub>0</sub>)(x − x<sub>1</sub>)(x − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)) | ||
+ | * c<sub>1</sub>(x) = (x − x<sub>0</sub>)(x − x<sub>2</sub>)(ax + b) | ||
+ | * c<sub>1</sub>(x<sub>1</sub>) = 1 = (x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)(ax<sub>1</sub> + b) | ||
+ | * c<sub>1</sub>(x) = [(x − x<sub>0</sub>)(x − x<sub>2</sub>)](ax + b) | ||
+ | * c<sub>1</sub>'(x) = [ ]'(ax + b) + a[ ] | ||
+ | * c<sub>1</sub>'(x<sub>1</sub>) = (2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>)(ax + b) + a(x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>) = 0 | ||
+ | * (2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>)/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)) + a(x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>) = 0 | ||
+ | * a = −(2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>)/((x<sub>1</sub> − x<sub>0</sub>)<sup>2</sup>(x<sub>1</sub> − x<sub>2</sub>)<sup>2</sup>) | ||
+ | * b(x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>) − (x<sub>1</sub>(2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)) = 1 | ||
+ | * b = 1/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>)) × (1 + (x<sub>1</sub>(2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)<sup>2</sup>(x<sub>1</sub> − x<sub>2</sub>)<sup>2</sup>)) | ||
+ | * c<sub>1</sub>(x) = (x − x<sub>0</sub>)(x − x<sub>2</sub>)/((x<sub>1</sub> − x<sub>0</sub>)<sup>2</sup>(x<sub>1</sub> − x<sub>2</sub>)<sup>2</sup>)) & times; [1 − ((x − x<sub>1</sub>)(2x<sub>1</sub> − x<sub>0</sub> − x<sub>2</sub>))/((x<sub>1</sub> − x<sub>0</sub>)(x<sub>1</sub> − x<sub>2</sub>))] | ||
+ | |||
+ | === Погрешность интерполяционной формулы H<sub>3</sub>(x) === | ||
+ | |||
+ | ω(x) = (x − x<sub>0</sub>)(x − x<sub>1</sub>)<sup>2</sup>(x − x<sub>2</sub>) | ||
+ | |||
+ | Вводим g(s) = f(s) − H<sub>3</sub>(s) − kω(s), x<sub>0</sub> ≤ s ≤ x<sub>2</sub> (3) | ||
+ | |||
+ | Выберем константу k из условия, что в некоторой несовпадающей с узлами точке g(x) = 0: f(x) − H<sub>3</sub>(x) − kω(x) = 0, то есть k = (f(x) − H<sub>3</sub>(x))/ω(x). | ||
+ | |||
+ | У g(s) видим 4 нуля, то есть по теореме Ролля у первой производной существует не менее 3 нулей, у второй — не менее 2, у третьей — не менее 1, а нам нужна четвёртая. Откуда возмётся ещё один ноль: у производной по теореме Ролля ноль будет не в x<sub>1</sub>, но он есть из условия, то есть всего у первой производной не мкенее 4 нулей. Тогда существует ξ ∈ (x<sub>0</sub>, x<sub>2</sub>): g<sup>(4)</sup>(ξ) = 0. | ||
+ | |||
+ | * g<sup>(4)</sup>(ξ) = 0 = f<sup>(4)</sup>(ξ) − k × 4! | ||
+ | * k = f(x) − H<sub>3</sub>(x))/ω(x) = f<sup>(4)</sup>(ξ)/4! | ||
+ | * ψ<sub>H<sub>3</sub></sub>(x) = f(x) − H<sub>3</sub>(x) = f<sup>(4)</sup>(ξ)/4! | ||
+ | * M<sub>4</sub> = sup<sub>x<sub>0</sub> ≤ x ≤ x<sub>2</sub></sub> |f<sup>(4)</sup>(x)| | ||
+ | * |f(x) − H<sub>3</sub>(x)| ≤ M<sub>4</sub>/4! × |ω(x)| | ||
+ | |||
+ | * |f(x) − H<sub>n</sub>(x)| ≤ M<sub>n + 1</sub>/(n + 1)! × |ω(x)| | ||
+ | * ω(x) = (x − x<sub>0</sub>)<sup>a<sub>0</sub></sup>(x − x<sub>1</sub>)<sup>a<sub>1</sub></sup>…(x − x<sub>m</sub>)<sup>a<sub>m</sub></sup> | ||
+ | * M<sub>n + 1</sub> = sup<sub>a ≤ x ≤ b</sub> |f<sup>(n + 1)</sup>(x)| | ||
+ | |||
+ | {{Численные Методы}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 2. Интерполирование и приближение функций
[править] Параграф 3. Разделённые разности
Доказательство формулы, которая разделённая разность k-го порядка f.
Задача: выразить значение функции в k-м узле через значение функции в 0-м узле и разделённую разность k-го порядка. Решается она несложно.
- k = 1:
- f(x0, x1) = f(x0)/(x0 − x1) + f(x1)/(x1 − x0) = (f(x1) − f(x0))/(x1 − x0)
- (x1 − x0) × f(x0, x1) = −f(x0) + f(x1)
- f(x1) = f(x0) + (x1 − x0) × f(x0, x1) (1)
- k = 2
- f(x0, x1, x2) = f(x0)/((x0 − x1)(x0 − x2)) + f(x1)/((x1 − x0)(x1 − x2)) + f(x2)/((x2 − x0)(x2 − x1))
- ((x2 − x0)(x2 − x1)) × f(x0, x1, x2) = (−f(x0)(x2 − x1))/(x0 − x1) { = γ} + (f(x1)(x2 − x0))/(x0 − x1) { = α} + f(x2)
- α = (f(x1)(x2 − x0))/(x0 − x1) = (x2 − x0)/(x0 − x1) × (f(x0) + (x1 − x0)f(x0, x1)) = ((x2 − x0)f(x0))/(x0 − x1) { = β} − (x2 − x0)f(x0, x1)
- β − γ = f(x0) × ((x2 − x0 − x2 + x1)/(x0 − x1)) = −f(x0)
- ((x2 − x0)(x2 − x1)) × f(x0, x1, x2) = −f(x0) − (x2 − x0)f(x0, x1) + f(x2) (2)
- По аналогии, общая формула:
- f(xk) = f(x0) + (xk − x0)f(x0, x1) + (xk − x0)(xk − x1)f(x0, x1, x2) + … + (xk − x0)(xk − x1)…(xk − xk − 1)f(x0, x1, …, xk) (3)
[править] Параграф 4. Интерполяционная формула Ньютона
{xi}0N — узлы интерполирования (n + 1 штук). Есть интерполируемая функция f(x), f(xi) = fi, i = 0…n.
Заменим в (3) xk на x:
Nn(x) = f(x0) + (x − x0)f(x0, x1) + (x − x0)(x − x1)f(x0, x1, x2) + … + (x − x0)(x − x1)…(x − xn − 1)f(x0, x1, …, xn)
Чтобы эта формула была интерполяционной функцией, Nn(xi) = f(xi), i = 0…n
Nn(xi) = f(x0) + (xi − x0)f(x0, x1) + (xi − x0)(xi − x1)f(x0, x1, x2) + … + (xi − x0)(xi − x1)…(xi − xi − 1)f(x0, x1, …, xi) = f(xi), i = 0…n
Погрешность та же самая, но записана внешне по-другому:
|ψNn(x)| = |f(x) − Nn(x)| ≤ Mn + 1/(n + 1)! × |ω(x)|, Mn + 1 = supa ≤ x≤ b |f(x)(n + 1)|
Замечание. Когда лучше использовать формулу Ньютона: очевидны два примера, которые показывают, что в одном случае удобно применять Ньютона, в другом — Лагранжа. У нас в Ньютоне всюду стоит функция и её разделённая разность, и она напоминает формулу Тейлора, некий её дискретный аналог, а узлы мы можем увеличивать сколько хотим, и если для специальной функции у нас она рассчитана грубая сетка, и нам надо её интерполировать. Лагранж удобен, когда у нас количество значений фиксировано, например, есть несколько датчиков.
[править] Параграф 5. Интерполирование с кратными узлами. Интерполяционная формула Эрмита
Ранее мы добивались только совпадения значений функций, теперь же будем требовать совпадения производных.
Пусть у нас есть узлы x0, … xm — m + 1 узел. Информация в узлах такая: в узле может быть задано значение производных:
x0 | x1 | … | xm |
f(x0) | f(x1) | … | f(xm) |
f'(x0) | f'(x1) | … | f'(xm) |
… | |||
f(a0 − 1)(x0) | f(a1 − 1)(x1) | … | f(am − 1)(xm) |
- ai ∈ N ( натуральное), i = 0…m
- ai — кратность i-го узла
Цель: построить Hn(x)
Замечание. Hn(i) = f(i)(xk), k = 0…m, i = 0…ak − 1 (1)
При выполнении условия a0 + a1 + … + am = n + 1 мы можем построить полином Эрмита, причём единственный.
Полином Эрмита строится аналогично полиному Лагранжа.
Общий вид полинома Эрмита: Hn(x) = ∑k = 0m ∑i = 0ak − 1 ck, i(x)f(i)(xk)
- ck, i(x) — полином n-й степени
- xi — различные
В общем виде мы строить не будем, построим H3(x), у которого будет кратным только средний узел. Он потребуется для оценки в квадратурной формуле Гаусса. В чём фишка (тонкость): позволяет получать точную оценку квадратурной формулы.
[править] Построение H3(x)
x0 | < | x1 | < | x2 |
f(x0) | f(x1) | f(x2) | ||
f'(x1) |
Существует несколько способ построения H3(x).
H3(x):
- H3(x0) = f(x0)
- H3(x1) = f(x1)
- H3(x2) = f(x2)
- H3'(x1) = f'(x1) (1)
Это получается из Лагранжа путём предельного перехода.
H3(x) будем искать в виде (2):
- H3(x) = c0(x)f(x0) + c1(x)f(x1) + c2(x)f(x2) + b1(x)f'(x1) (2)
- ci(x), bi(x) — многочлены 3-й степени
* c0(x0) = 1 | * c1(x0) = 0 | * c2(x0) = 0 | * b1(x0) = 0 |
* c0(x1) = 0 | * c1(x1) = 1 | * c2(x1) = 0 | * b1(x1) = 0 |
* c0(x2) = 0 | * c1(x2) = 0 | * c2(x2) = 1 | * b1(x2) = 0 |
* c0'(x1) = 0 | * c1'(x1) = 0 | * c2'(x1) = 0 | * b1'(x1) = 1 |
- c0(x) = k(x − x1)2(x − x2)
- c0(x0) = k(x0 − x1)2(x0 − x2)
Отсюда
- c0(x) = ((x − x1)2(x − x2))/((x0 − x1)2(x0 − x2))
Аналогично
- c2(x) = ((x − x1)2(x − x0))/((x2 − x1)2(x2 − x0))
- b1(x) = b0(x − x0)(x − x1)(x − x2) = b0[(x − x0)(x − x2)](x − x1)
- b1' = b0([ ]'(x − x1) + [])
- b1'(x1) = b0(x1 − x0)(x1 − x2)
- b1(x) = ((x − x0)(x − x1)(x − x2))/((x1 − x0)(x1 − x2))
- c1(x) = (x − x0)(x − x2)(ax + b)
- c1(x1) = 1 = (x1 − x0)(x1 − x2)(ax1 + b)
- c1(x) = [(x − x0)(x − x2)](ax + b)
- c1'(x) = [ ]'(ax + b) + a[ ]
- c1'(x1) = (2x1 − x0 − x2)(ax + b) + a(x1 − x0)(x1 − x2) = 0
- (2x1 − x0 − x2)/((x1 − x0)(x1 − x2)) + a(x1 − x0)(x1 − x2) = 0
- a = −(2x1 − x0 − x2)/((x1 − x0)2(x1 − x2)2)
- b(x1 − x0)(x1 − x2) − (x1(2x1 − x0 − x2))/((x1 − x0)(x1 − x2)) = 1
- b = 1/((x1 − x0)(x1 − x2)) × (1 + (x1(2x1 − x0 − x2))/((x1 − x0)2(x1 − x2)2))
- c1(x) = (x − x0)(x − x2)/((x1 − x0)2(x1 − x2)2)) & times; [1 − ((x − x1)(2x1 − x0 − x2))/((x1 − x0)(x1 − x2))]
[править] Погрешность интерполяционной формулы H3(x)
ω(x) = (x − x0)(x − x1)2(x − x2)
Вводим g(s) = f(s) − H3(s) − kω(s), x0 ≤ s ≤ x2 (3)
Выберем константу k из условия, что в некоторой несовпадающей с узлами точке g(x) = 0: f(x) − H3(x) − kω(x) = 0, то есть k = (f(x) − H3(x))/ω(x).
У g(s) видим 4 нуля, то есть по теореме Ролля у первой производной существует не менее 3 нулей, у второй — не менее 2, у третьей — не менее 1, а нам нужна четвёртая. Откуда возмётся ещё один ноль: у производной по теореме Ролля ноль будет не в x1, но он есть из условия, то есть всего у первой производной не мкенее 4 нулей. Тогда существует ξ ∈ (x0, x2): g(4)(ξ) = 0.
- g(4)(ξ) = 0 = f(4)(ξ) − k × 4!
- k = f(x) − H3(x))/ω(x) = f(4)(ξ)/4!
- ψH3(x) = f(x) − H3(x) = f(4)(ξ)/4!
- M4 = supx0 ≤ x ≤ x2 |f(4)(x)|
- |f(x) − H3(x)| ≤ M4/4! × |ω(x)|
- |f(x) − Hn(x)| ≤ Mn + 1/(n + 1)! × |ω(x)|
- ω(x) = (x − x0)a0(x − x1)a1…(x − xm)am
- Mn + 1 = supa ≤ x ≤ b |f(n + 1)(x)|
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |