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

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

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

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

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

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

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

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

x^{n + 1} = xⁿ − f(ⁿ)/f(^{n + 1}), n = 0, 1, …, x⁰ — начальное приближение (2)

• x^{n + 1} = S(xⁿ)
• S(x) = x − f(x)/f'(x)
• |S'(x)| ≤ q < 1, x ∈ U_a(x_*)
• S'(x) = (1 − f'(x)f'(x) − f(x)f''(x))/(f'(x))² = (f(x)f''(x))/(f'(x))²
• S'(x_*) = (f(x_*)f''(x_*))/(f'(x_*))² = 0

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

• Z_{n + 1} = x^{n+ 1} − x_* = S(xⁿ) − S(x_*) = Z_n = xⁿ − x_* — погрешность = S(Z_n + x_*) − S(x_*) = S(x_*) + S'(x_*)Z_n + 0,5S''(x~_n)Z_n² − S(x_*)
  • x~_n = x_* + ΘZ_n, |Θ| < 1
• Z_{n + 1} = 0,5S''(x~_n)Z_n²

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

• ∃ M > 0: 0,5|S''(x~_n)| ≤ M
• |Z_{n + 1}| ≤ M|Z_n|²
• MZ_{n + 1} ≤ (M|Z_n|)²
• v_n = M|Z_n|
• v_{n + 1} ≤ v_n² ⇒ v_n ≤ v₀²ⁿ
• v₀ = M|x⁰ − x_*|
• q = M|Z₀|
• M|Z_n| ≤ (M|Z₀|)²ⁿ
• |Z_n| ≤ (M|Z₀|)²ⁿ/M = 1/M × q²ⁿ

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

• M|Z₀| < 1
• |Z₀| < 1/M
• |x⁰ − x_*| < 1/M (4)
• |xⁿ − x_*| ≤ 1/M × (M|x⁰ − x_*|)², n → ∞, x_n → x_* (5)

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

• |xⁿ − x_*| ≤ 1/M × (M|x⁰ − x_*|)²ⁿ

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

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

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

• S'(x) = 1 − f'(x)/f'(x⁰)
• S'(x_*) = 1 − f'(x_*)/f'(x₀)

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

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

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

• x ∈ [0, 1], t ∈ [0, T]
• δu/δt = δ²u/δx² + f(x, t) (1)
• u(0, t) = μ₁(t); u(1, t) = μ₂(t), 0 ≤ t ≤ T (2)
• u(x, 0) = u₀(x), 0 ≤ x ≤ 1 (3)

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

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

Пункт 1. Явная разностная схема

• y_iⁿ = y(x_i, t_n)
• (y_i^{n + 1} − y_iⁿ)/τ = (y_{i + 1}ⁿ − 2y_iⁿ + y_{i − 1}ⁿ)/h₂ + f(x_i, t_j), (x_i, t_j) ∈ ω_τh (4)
• y₀^{n + 1} = μ₁(t_{n + 1}); y_N^{n + 1} = μ₂(t_{n + 1}), t_{n + 1} ∈ ω__τ (5)
• y_i⁰ = u₀(x_i), x_i ∈ ω__h (6)

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

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

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

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