| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 09 лекция (от 13 марта)|Предыдущая лекция]] | [[Численные Методы, 11 лекция (от 20 марта)|Следующая лекция]]
| + | == From Ebaums Inc to MurkLoar. == |
| - | | + | We at EbaumsWorld consider you as disgrace of human race. |
| - | = Глава 2. Интерполирование и приближение функций = | + | Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. |
| - | == Параграф 3. Разделённые разности ==
| + | Dig yourself a grave - you will need it. |
| - | | + | |
| - | Доказательство формулы, которая разделённая разность 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}}
| + | |
