Численные Методы, 10 лекция (от 19 марта)

Материал из eSyr's wiki.

Версия от 18:56, 15 мая 2010; 93.175.201.141 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Предыдущая лекция | Следующая лекция

Содержание

[править] Глава 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 = 0mi = 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


Календарь

Февраль
пн
12 19
вт
13 20 27
Март
пн
05 12 19 26
вт
06 13 20 27
Апрель
пн
02 09 16 23 29
вт
03 10 17 24

Дополнительная информация

Содержание курса | Задачи на лекциях

Материалы к экзамену

Вопросы по курсу | Определения


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы