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

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

Перейти к: навигация, поиск

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

Содержание

Глава 1. Численные методы линейной алгебры

Параграф 12. Предварительное преобразование к верхней почти треугольной форме

Ak = QkRk, Qk−1 = QkT, R — ВТФ, Ak + 1 = RkQk, k = 0 ,1, … (1)

Оценка количества действий:

  • A — произвольная: O(m3)
  • A — ВПТФ: O(m2)
  • A — трёхдиагональная: O(m)

Лемма 1. Пусть C = B × A, B — ВТФ, A — ВПТФ. Тогда C — ВПТФ.
Доказательство. Распишем cij = ∑α = 1mbaαj = (*). Так как B — ВТФ, то b = 0 при i > α. Тогда (*) = ∑α = imbaαj = (**). Так как A — ВПТФ, то aαj = 0 при j + 1 < α. Тогда (**) = ∑α = ij + 1baαj. Отсюда следует, что cij = 0, i > j + 1 ⇒ C — ВПТФ.

Задача. Пусть C = B × A, B — ВПТФ, A — ВТФ. Доказать, что C — ВПТФ.

Теперь мы можем сказать, что QR-алгоритм инвариантен относительно ВПТФ, он её не портит. Это не значит, что он её сохраняет, так как в результате мы должны получить ВТФ. Докажем это:

Пусть A = A0 — ВПТФ. Тогда мы можем выразить Qk = Rk−1Ak, Q0 = R0−1A0. Но так как A0 — ВПТФ, то Q0 тоже ВПТФ. Рассмотрим Ak + 1 = RkQk. Но Rk — ВТФ, Qk — ВПТФ. Тогда Ak + 1 тоже ВПТФ. В результате Ak, k = 0, 1, … — ВПТФ.

На этом завершим первую главу.

Глава 2. Интерполирование и приближение функций

Это очень ёмкое понятие. Это можно решать бесчисленным количеством способов, в зависимости от поставленной цели.

Сейчас мы вспомним и полином Лагранжа, затем рассмотрим интерполяционный полином Ньютона. Далее начнём строить полином Эрмита и покажем, для чего нужны они. Ну и наилучшее квадратичное приближение функции.

Это наиболее древняя область, но она актуальна и поныне, поскольку без интерполирования математик обойтись не может. Это актуально для специальных функций, которые не выражаются через элементарные, но используются для решения дифуров. Обычно используются таблицы, но возникает вопрос, что делать, когда нужно получить значение для аргумента, которого нет в таблице. Первое решение — сгущать таблицы. Ещё одно — пользоваться интерполированием.

Где ещё требуется интерполирование — есть домна, за ней надо следить. Надо наставить датчиков, но много их поставить нельзя, иначе она разрушится, а информацию надо получать по всему профилю. Поэтому надо использовать интерполяцию.

Ешё одно применение — разностные схемы.

Ещё одно применение — экстраполирование.

Обычно будем использовать приближение полиномом.

Параграф 1. Введение

Суть задачи: есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x0 < x1 < x2 < … < xn ≤ b — {xi}0n — узлы интерполирование (n + 1 штук). Есть f(xi) = fi, i = 0…n. Если полином Pn(x) = a0 + a1x + … anxn такой, что Pn(xi) = f(xi), i = 0…n (1), то данный полином называется интерполяционным для f (интерполирует f).

Докажем, что интерполирующий полином существует и единственный. Рассмотрим систему:

  • a0 + a1x0 + … anx0n = f0
  • a0 + a1x1 + … anx1n = f1
  • ...
  • a0 + a1xn + … anxnn = fn

Определитель этой системы Dn + 1 = ∏n ≥ i > j ≥ 1(xi − xj) ≠ 0 (xi ≠ xj) — определитель Вандермонда.

Параграф 2. Интерполяционная формула Лагранжа. Погрешность формулы Лагранжа

Есть {xi}0n — узлы интерполирования. Заданы f(xi) = fi, i = 0…n. Задача построить полином Ln(x): Ln(xi) = f(xi), i = 0…n (1). Будем искать полином в виде Ln(x) = ∑k = 0nck(x)f(xk) (2), ck(x) — полином n-й степени. Введём многочлен ω(x) = (x − x0)(x − x1)…(x − xn) = ∏i = 0n(xi − xj). Найдём производную:

  • ω(x) = [ ](x − xk)
  • ω'(x) = [ ] + [ ]'(x − xk)
  • ω'(xk) = ∏k ≠ jn(xk − xj)

Возьмём ck(x) = (ω(x))/((x − xk)ω'(xk))

Тогда Ln(x) = ∑k = 0n(ω(x))/((x − xk)ω'(xk)) × f(xk) (3)

Пример

Для трёх точек x0, x1, x2 L2(x) = (x − x0)(x − x1)(x − x2)/(x − x0)(x0 − x1)(x0 − x2) + (x − x0)(x − x1)(x − x2)/(x − x1)(x1 − x0)(x1 − x2) + (x − x0)(x − x1)(x − x2)/(x − x2)(x2 − x0)(x2 − x1) = (x − x1)(x − x2)/(x0 − x1)(x0 − x2) + (x − x0)(x − x2)/(x1 − x0)(x1 − x2) + (x − x0)(x − x1)/(x2 − x0)(x2 − x1).

Погрешность полинома

Погрешность интерполяционной формулы Лагранжа ψLn(x) = f(x) − Ln(x). Во всех узлах она будет совпадать: ψLn(xi) = 0.

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

В данном случае рассматриваем g(s) = f(s) − Ln(s) − Kω(s), ω(s) = ∏i = 0n(s − xi)

f(s) − Ln(s) = Kω(s)

В данном случае получали оценку f(s) − Ln(s) = (f(n + 1)(ξ)/(n + 1)!) × ω(x)

На физфаке один профессор замечательно читал. И на каждой лекции он клал перед собой на стол тоненькую тетрадку, истрёпаную (как корочка лектора, которой 25 лет), и он периодически туда заглядывал. И поскольку почти не перелистывал её, то студентов разбирало, что в ней записано, и когда он однажды вышел и забыл её, один из студентов в неё посмотрел и увидел, что там написано: «Мижа, не забудь зайти в булочную.»

|f(x) − Ln(x)| ≤ (Mn + 1/(n + 1)!) × |ω(x)|

Замечание 1. Если f(x) — полином степени ≤ n, то полином Лагранжа даёт точное приближение, то есть погрешность тождественно равна 0.

Замечание 2. По большому числу узлов интерполяцию проводят крайне редко. Можно подобрать узлы так, что при увеличении количества узлов сходимости не будет.

Параграф 3. Разделённые разности

Разделённые разности — подводка к интерполяционным полиномам Ньютона.

Есть отрезок x ∈ [a, b]. Мы разбиваем его несовпадающими узлами a ≤ x0 < x1 < x2 < … < xN ≤ b — {xi}0N — узлы интерполирования (n + 1 штук). Есть интерполируемая функция f(x), f(xi) = fi, i = 0…N.

Разделённой разностью первого порядка, построенной по узлам xi, xj называется отношение f(xi, xj) = (f(xj) − f(xi)/(xj − xi))

Рассмотрим разделённые разности между соседними узлами:

  • f(x0, x1) = (f(x1) − f(x0)/(x1 − x0))
  • f(x1, x2) = (f(x2) − f(x1)/(x2 − x1))

Разделённая разность второго порядка:

  • f(xi, xj, xk) = (f(xj, xk) − f(xi, xj)/(xk − xi))
  • f(x0, x1, x2) = (f(x1, x2) − f(x0, x1)/(x2 − x0))
  • f(x1, x2, x3) = (f(x2, x3) − f(x1, x2)/(x3 − x1))

Разделённая разность k+1-го порядка: пусть есть f(xj, xj + 1, …, xj + k), f(xj + 1, xj + 2, …, xj + k + 1) — разности k-го порядка. Тогда f(xj, xj + 1, …, xj + k + 1) = (f(xj + 1, xj + 2, …, xj + k + 1) − f(xj, xj + 1, …, xj + k))/(xj + k + 1 − xj) — разделённая разность k + 1-го порядка.

Докажем, что разделённые разности выражаются через значения функций в точках. Рассмотрим:

  • ω(x) = (x − x0)…(x − xN) = ω0, N(x)
  • ωα, β(x) = (x − xα)…(x − xβ)
  • ωα, β'(x) = ∏σ, (α ≠ k)β(xk− xσ), k = 1

Утверждение. Разделённая разность k-го порядка, построенная по узлам x0, … xk может быть записана как f(x0, x1, …, xk) = ∑i = 0k(f(xi))/(ω0, k'(xi)) (1)

Доказательство (методом полной математической индукции).

  1. f(x0, x1) = (f(x1) − f(x0))/(x1 − x0) = f(x0)/(x0 − x1) + f(x1)/(x1 − x0)
  2. По предпололжению индукции:
    • f(x0, x1, …, xl) = ∑i = 0l(f(xi))/(ω0, l'(xi))
    • f(x1, x2, …, xl + 1) = ∑i = 1l + 1(f(xi))/(ω1, l + 1'(xi))
  3. Рассмотрим f(x0, x1, …, xl + 1)
    • f(x0, x1, …, xl + 1) = 1/(xl + 1 − x0) × (∑i = 1l + 1(f(xi))/(ω1, l + 1'(xi)) − ∑i = 0l(f(xi))/(ω0, l'(xi))) = 1/(xl + 1 − x0) × ((f(xl + 1))/(ω1, l + 1'(xl + 1)) − (f(x0))/(ω0, l'(x0)) + ∑i = 0l((f(xi))/(ω1, l + 1'(xi)) − (f(xi))/(ω0, l'(xi)))) = (***)
      • (f(xl + 1))/((xl + 1 − x01, l + 1'(xl + 1)) = (f(xl + 1))/(ω0, l + 1'(xl + 1))
      • (f(x0))/((xl + 1 − x00, l'(x0)) = (f(x0))/(ω0, l + 1'(x0))
      • (f(xi)(xi − x0))/(ω1, l + 1'(xi)) − (f(xi)(xi − x0))/(ω0, l'(xi)) = (f(xi))/(ω0, l + 1'(xi))
    • (***) = ∑l = 0l + 1f(xi/(ω0, l + 1'(xi)))


Численные Методы


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

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

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

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

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


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

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