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

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

Версия от 18:12, 3 февраля 2008; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

[править] Глава 3. Численное решение нелинейных уравнений и систем нелинейных уравнений

[править] Параграф 3. Метод Ньютона (касательных) и метод секущих

Метод секущих — двухшаговый.

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

[править] Параграф 4. Сходимость метода Ньютона. Оценка скорости сходимости.

Есть f(x) = 0 (1)

xn + 1 = xn − f(n)/f(n + 1), n = 0, 1, …, x0 — начальное приближение (2)

  • xn + 1 = S(xn)
  • S(x) = x − f(x)/f'(x)
  • |S'(x)| ≤ q < 1, x ∈ Ua(x*)
  • S'(x) = (1 − f'(x)f'(x) − f(x)f''(x))/(f'(x))2 = (f(x)f''(x))/(f'(x))2
  • S'(x*) = (f(x*)f''(x*))/(f'(x*))2 = 0

Теперь оценим скорость сходимости:

  • Zn + 1 = xn+ 1 − x* = S(xn) − S(x*) = Zn = xn − x* — погрешность = S(Zn + x*) − S(x*) = S(x*) + S'(x*)Zn + 0,5S''(x~n)Zn2 − S(x*)
    • x~n = x* + ΘZn, |Θ| < 1
  • Zn + 1 = 0,5S''(x~n)Zn2

Требуем гладкости, наличия третьей производной исходной функции. Тогда получим:

  • ∃ M > 0: 0,5|S''(x~n)| ≤ M
  • |Zn + 1| ≤ M|Zn|2
  • MZn + 1 ≤ (M|Zn|)2
  • vn = M|Zn|
  • vn + 1 ≤ vn2 ⇒ vn ≤ v02n
  • v0 = M|x0 − x*|
  • q = M|Z0|
  • M|Zn| ≤ (M|Z0|)2n
  • |Zn| ≤ (M|Z0|)2n/M = 1/M × q2n

Если мы затребуем q < 1, то получим очень быструю сходимость.

  • M|Z0| < 1
  • |Z0| < 1/M
  • |x0 − x*| < 1/M (4)
  • |xn − x*| ≤ 1/M × (M|x0 − x*|)2, n → ∞, xn → x* (5)

'''Утверждение'''. ∃ M: 0,5|S''(x)| ≤ M, x ∈ Ua(x*). Пусть |x0 − x*| < 1/M

  • |xn − x*| ≤ 1/M × (M|x0 − x*|)2n

'''Замечание 1'''. Если метод Ньютона сходится, то он сходится очень быстро (3—4—5 итераций)

'''Замечание 2'''. Метод Ньютона очень чуток к точкам начального приближения, надо выбирать их близко к корню.

[править] Модифицированный метод Ньютона

  • S'(x) = 1 − f'(x)/f'(x0)
  • S'(x*) = 1 − f'(x*)/f'(x0)

Чем ближе это значение к нулю, тем ближе скорость сходимости к методу Ньютона.

[править] Глава 4. Разностные методы решения задач математической физики

[править] Параграф 1. Разностные схемы для первой краевой задачи уроавнения теплопроводности

  • x ∈ [0, 1], t ∈ [0, T]
  • δu/δt = δ2u/δx2 + f(x, t) (1)
  • u(0, t) = μ1(t); u(1, t) = μ2(t), 0 ≤ t ≤ T (2)
  • u(x, 0) = u0(x), 0 ≤ x ≤ 1 (3)

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

  • &omegah = {xi = i × h, i = 1…N − 1, hN = 1}, h = 1/N > 0
  • &omega_h = {xi = i × h, i = 0…N, hN = 1}, h = 1/N > 0
  • τ — размер шага по t
  • h — размер шага по x
  • ωτ = {tj = τ × j, j = 1…j0, τj0 = FT}
  • ω_τ = {tj = τ × j, j = 0…j0, τj0 = FT}
  • ωτh = ωτ × ωh — внутренние узлы (О)
  • ω_τh = ω_τ × ω_h — все узлы (О)

[править] Пункт 1. Явная разностная схема

  • yin = y(xi, tn)
  • (yin + 1 − yin)/τ = (yi + 1n − 2yin + yi − 1n)/h2 + f(xi, tj), (xi, tj) ∈ ωτh (4)
  • y0n + 1 = μ1(tn + 1); yNn + 1 = μ2(tn + 1), tn + 1 ∈ ω_τ (5)
  • yi0 = u0(xi), xi ∈ ω_h (6)

Схем разностных, которые это аппроксимируют, существует бесконечно много, и главная задача — выбрать правильную, устойчивую.

Для решения урматов есть и другие методы, но эти — самые эффективные.

Пять вопросов физики:

  1. Существует и единственно решение (4)—(6)?
  2. Погрешность аппроксимации разностной схемы исходной задачи
  3. Алгоритм нахождения решения разностной задачи
  4. Исследование устойчивости разностной схемы
  5. Изучение сходимости разностной схемы


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


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

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

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

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

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


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

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