§ 1.4. О сходимости явных методов

В этом параграфе доказываются общие теоремы об условиях сходимости явных одношаговых методов. В качестве приложений рассматриваются явные методы Рунге — Кутты.

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

1.4.1. Лемма.

Пусть последовательность a_n неотрицательных чисел удовлетворяет условиям: a₀ = 0 и

ai ≤ (1 + τA)ai–1 + τB,   i = 1,2, ...

(1)

(A и B — неотрицательные константы). Тогда при τi ≤ T

ai ≤  eAT – 1 A B.

Д о к а з а т е л ь с т в о.  (ср. с п. 1.2.10). По индукции покажем, что при всех i

ai ≤  (1 + τA)i – 1 A B.

(2)

При i = 0 неравенство (2) очевидно выполнено. Если же оно выполнено при некотором i > 0, то при том же i

ai+1 ≤ (1 + τA)ai + τB ≤ (1 + τA) (1 + τA)i – 1 A B + τB =

=  ( (1 + τA)i+1 – 1 – τA A B + τ ) B =  (1 + τA)i+1 – 1 A B

и (2) при всех i доказано.

Далее, поскольку 1 + τA ≤ 1 + τA + (τA)²/ 2! + ... = e^τA и τi ≤ T,

(1 + τA)i – 1 A B ≤  eiτA – 1 A B ≤  eAT – 1 A B,

что и требовалось.

Задача 1.4.1. Докажите, что если a > 0, то из неравенства (1) вытекает неравенство

ai ≤ eATa0 +  eAT – 1 A B

при iτ ≤ T.

В заключение отметим, что данная лемма является разностным аналогом классической леммы Гронуолла о дифференциальных неравенствах.

1.4.2. Явные одношаговые методы.

Явные методы Рунге — Кутты относятся к так называемым явным одношаговым методам: для того, чтобы вычислить значение сеточного решения в точке t_i необходимо знать его значение только в предшествующей точке t_i–1. Разностный оператор общего явного одношагового метода имеет вид

(Fτx)i =  { xi – xi–1 τ  – Φ(ti–1, xi–1, τ),   если i = 1, ..., n, x0,   если i = 0

(3)

(здесь Φ: R×R^m×[0, +∞) → R^m). Разностную схему (S) метода мы, как обычно, будем записывать в виде рекуррентного соотношения

xi = xi–1 + τΦ(ti–1, xi–1, τ),

(4)

опуская начальное условие x₀ = x⁰, которое мы считаем выполненным по умолчанию. Функция Φ часто называется инкрементом, или приращением метода.

Задача 1.4.2. Каков инкремент явного метода Эйлера и метода предиктор-корректор?

Всегда будем предполагать, что

инкремент метода есть непрерывная по совокупности переменных и удовлетворяющая при достаточно малых τ условию Липшица по второму аргументу с (универсальной) константой L функция.

1.4.3. Теорема (необходимое условие сходимости явных одношаговых методов).

Если явный одношаговый метод сходится, то Φ(t, x, 0) ≡ f(t, x) при всех (t, x) ∈ R×R^m.

Д о к а з а т е л ь с т в о.  Предположим противное: в некоторой точке (t₀, x₀) ∈ R×R^m

Φ(t0, x0, 0) ≠ f(t0, x0).

В силу теоремы Коши — Пикара начальная задача

x′ = Φ(t, x, 0),

(5)

x(t0) = x0

(6)

имеет единственное решение, скажем ψ (определенное на всей оси, поскольку Φ удовлетворяет условию Липшица по x). Через φ, как обычно, обозначается решение задачи (E) – (C).

Пусть теперь φ_τ — решение разностной схемы (S) с определенным формулой (3) разностным оператором, т. е. (см. (4))

(φτ)i = (φτ)i–1 + τΦ[ti–1, (φτ)i–1, τ].

(7)

По условию теоремы

||φτ – Pτφ||τ → 0 при τ → 0.

(8)

Если мы докажем, что

||φτ – Pτψ||τ → 0 при τ → 0.

(9)

то тогда из (8) и (9) будет вытекать, что

φ = ψ.

(10)

В самом деле, соотношения (8) и (9) означают, что функции φ и ψ равномерно аппроксимируются в узлах сетки одной и той же сеточной функцией φ_τ, а поскольку φ и ψ непрерывны на [t₀, t₀ + T] и шаг сетки стремится к нулю, имеет место (10).

Задача 1.4.3. Проведите подробные рассуждения.

Но тогда, в частности, φ(t₀) = ψ(t₀), а следовательно,

φ′(t0) = f[t0, φ(t0)] = f(t0, x0) ≠ Φ(t0, x0, 0) = Φ[t0, ψ(t0), 0] = ψ′(t0),

что противоречит (10).

Осталось доказать соотношение (9). Положим

ρi =  ψ(ti) – ψ(ti–1) τ ,

или, что то же,

ψ(ti) = ψ(ti–1) + τρi.

(11)

По теореме о среднем (см. любой курс математического анализа)

ρi = ψ′(ti–1 + θi τ) = Φ[ti–1 +θiτ, ψ(ti–1 + θiτ)],

(12)

где θ_i ∈ (0, 1). Обозначим (φ_τ)_i – ψ(t_i) через ε_i. В этих обозначениях из (7) и (11) следует, что

εi = εi–1 +τ(Φ[ti–1,(φτ)i–1, τ] – ρi).

Добавляя и отнимая необходимые слагаемые и используя (12), получаем следующую оценку

||εi|| ≤ ||εi–1|| + τ||Φ[ti–1, (φτ)i–1, τ] – Φ[ti–1, ψ(ti–1), τ]|| + + τ||Φ[ti–1, ψ(ti–1), τ] – Φ[ti–1, ψ(ti–1), 0]|| + + τ||Φ[ti–1, ψ(ti–1), 0] – Φ[ti–1 + θiτ, ψ(ti–1 + θiτ), 0]||.

(13)

Обозначим сумму двух последних слагаемых в правой части (13) через τ[r(τ)]_i. Очевидно, [r(τ)]_i → 0 при τ → 0 равномерно по i ∈ {1, ..., n}, так как Φ и ψ непрерывны (и, следовательно, равномерно непрерывны на компактах).

Задача 1.4.4. Докажите последнее утверждение.

Второе слагаемое в правой части оценивается с помощью условия Липшица величиной τL||(φ_τ)_i–1 – ψ(t_i–1)|| = τL||ε_i–1||. Тогда, продолжая (13), получаем

||εi|| ≤ (1 + τL)||εi–1|| + τ||r(τ)||τ.

По лемме 1.4.1 ||ε_i|| ≤ r(τ)(e^LT – 1)/L и соотношение (9), а вместе с ним и теорема доказаны.

Задача 1.4.5. Докажите, что явная схема Эйлера и схема предиктор-корректор удовлетворяют условиям теоремы 1.4.3.

1.4.4. Теорема (достаточное условие сходимости явных одношаговых методов).

Условие Φ(t, x, 0) ≡ f(t, x) при всех t ∈ R×R^m является и достаточным условием для сходимости метода (4).

Д о к а з а т е л ь с т в о  теоремы, по-существу, нами уже проведено: в силу теоремы Коши — Пикара решение φ задачи (E) – (C) и решение ψ задачи (5) – (6) единственны и поэтому φ = ψ, а следовательно, доказанное выше соотношение (9) равносильно нужному соотношению (8).

1.4.5. Сходимость схем Рунге — Кутты.

Поскольку для произвольной явной p-этапной схемы Рунге — Кутты (см. (1.3.10) – (1.3.12))

Φ(t, x, 0) =  ( p ∑ s = 1 αs  ) f(t, x),

в силу доказанных теорем 1.4.3 и 1.4.4 для сходимости этих схем необходимо и достаточно, чтобы

p ∑ s = 1 αs = 1.

Как уже говорилось выше, на практике гораздо более полезной оказывается информация о порядке сходимости схемы.

1.4.6. О порядке сходимости явных одношаговых схем.

Определим на R×R^m×[0, +∞) функцию ρ, положив для произвольных t₀ ∈ R, x₀ ∈ R^m и τ ≥ 0

ρ(t0, x0, τ) =  { f(t0, x0),   если τ = 0,   φ(t0 + τ) – φ(t0) τ ,   если τ > 0,

Рис. 4.

где φ — решение задачи (E) – (C) (рис. 4). Очевидно, при τ > 0

φ(t0 + τ) = φ(t0) +τρ(t0, x0, τ).

(14)

Другими словами, явный одношаговый метод с инкрементом ρ является идеальным, т. е. точным на каждом шаге.

Теорема о порядке сходимости явных одношаговых схем. Пусть для некоторых k > 0 и M ≥ 0

||Φ(t, x, τ) – ρ(t, x, τ)|| ≤ Mτk

(15)

при всех (t, x) ∈ R×R^m и достаточно малых τ. Тогда явный одношаговый метод (4) сходится с k-м порядком, точнее, имеет место оценка

||φτ – Pτφ||τ ≤  eLT – 1 L Mτk.

(16)

Суть этой теоремы другими словами можно выразить так: если инкремент метода (4) отличается от инкремента идеального метода на величину порядка O(τ^k), то метод сходится с k-м порядком.

Д о к а з а т е л ь с т в о.  Обозначим, погрешность (φ_τ)_i – φ(t_i) метода в точке t_i на решении φ через ε_i. Имеем (см. (4) и (14))

||εi|| = ||εi–1 + τ(Φ[ti–1, (φτ)i–1, τ] – ρ[ti–1, φ(ti–1), τ])|| ≤ ≤ ||εi–1|| + τ||Φ[ti–1, (φτ)i–1, τ] – Φ[ti–1, φ(ti–1), τ]|| + + τ||Φ[ti–1, φ(ti–1), τ] – ρ[ti–1, φ(ti–1), τ]|| ≤ ≤ ||εi–1|| + τL|| (φτ)i–1 – φ(ti–1)|| +Mτk+1 ≤ (1 + τL)||εi–1|| + τMτk+1.

Применяя к последовательности a_i = ||ε_i|| лемму 1.4.1, получаем неравенство

||εi|| ≤  eLT – 1 L Mτk при iτ ≤ T,

которое, очевидно, эквивалентно нужному нам неравенству (16).

1.4.7. Пример. Сходимость метода предиктор-корректор.

Теорема 1.4.6 позволяет устанавливать сходимость явных методов Рунге — Кутты и, более того, позволяет получать полезные на практике оценки близости между точным и сеточным решениями.

Рассмотрим, например, метод предиктор-корректор. Для простоты будем считать уравнение (E) скалярным. Для того чтобы воспользоваться оценкой (16), нам нужны оценки константы Липшица L инкремента метода Φ по второму аргументу и константы M в неравенстве (15). Начнем с более простой оценки константы L. Для метода предиктор-корректор (см. задачу 1.4.2)

Φ(t, x, τ) =  1 2 (f(t, x) + f[t + τ, x + τf(t, x)]).

Тогда (напомним, что L — константа Липшица функции f по x)

||Φ(t, x, τ) – Φ(t, y, τ)|| ≤  1 2 ||f(t, x) – f(t, y)|| +

+  1 2 ||f[t + τ, x + τf(t, x)] – f[t + τ, y + τf(t, y)]|| ≤

≤  L 2 ||x – y|| +  L 2 ||x + τf(t, x) – y – τf(t, y)|| ≤  L 2 ||x – y|| +

+  L 2 (||x – y|| + τ||f(t, x) – f(t, y)||) ≤ L ( 1 +  L 2 ) ||x – y||.

Поэтому

L ≤ L ( 1 +  L 2 ) .

Оценка константы M получается более громоздко. Пусть функция f дважды непрерывно дифференцируема и, кроме того, все частные производные от нулевого до второго порядков ограничены (скажем, константой M). Тогда, во-первых (напомним, что мы опускаем аргумент (t, x) у функции f и ее производных), раскладывая Φ в ряд Тейлора по степеням τ,

Φ(t, x, τ) = Φ(t, x, 0) + τΦ′τ(t, x,0)+  τ2 2 Φ′′ττ(t, x, θτ) =

=  1 2 f +  1 2 f +  τ 2 ft +  τ 2 fx f +  1 2 · τ 2 [fttθ+ 2ftxθf θ + fxxθ(f θ)2] =

= f +  τ 2 (ft + fx f )  +  τ2 4 M1(θ).

где верхний индекс θ означает, что аргумент, соответствующей функции равен (t + θτ, x + θτf(t, x)) (0 < θ < 1), а обозначение M₁(θ) очевидно. Во-вторых (здесь φ — решение уравнения (E), проходящее через точку (t, x), т. е. такое, что φ(t) = x),

ρ(t, x, τ) =  φ(t + τ) – φ(t) τ  =

=  x + τφ′(t) +  τ2 2 φ′′(t) +  τ3 6 φ′′′(t + ξτ) – x τ  =

= φ′(t) +  τ 2 φ′′(t) +  τ2 6 φ′′′(t + ξτ) =

= f +  τ 2 (ft + fx f ) +  τ2 6 (fttξ+ 2ftxξf ξ + fxxξ(f ξ)2+ fxξftξ + (fxξ)2f ξ) =

= f +  τ 2 (ft + fx f )  +  τ2 6 M2(ξ),

где 0 < ξ < 1. Поэтому

||Φ(t, x, τ) – ρ(t, x, τ)|| ≤  ( || M1(θ) 4 ||  +  || M2(ξ) 6 || ) τ2.

Поскольку все частные производные функции f до второго порядка ограничены константой M,

||M1(θ)|| ≤ M + 2M2 + M3,

а

||M2(ξ)|| ≤ M + 2M2 + M3 + M2 +M3 = M + 3M2 + 2M3.

Поэтому

||Φ(t, x, τ) – ρ(t, x, τ)|| ≤  5M +12M2 + 7M3 12 τ2,

и следовательно,

M ≤  5M +12M2 + 7M3 12 .

1.4.8. Замечания.

а) Условие ограниченности производных функции f можно ослабить до требования их ограниченности только на некотором множестве, о котором a priori известно, что в нем лежит искомое решение. В частности, если это множество замкнуто и ограничено, то достаточно требовать непрерывности соответствующих производных.

б) Полученная оценка погрешности, поскольку она расчитана на широкий класс функций, разумеется, на конкретных задачах выполняется с запасом. Часто на конкретных задачах полученная фактическая погрешность в десятки раз ниже теоретической.

File based on translation from T_EX by T_TH, version 3.05.
26 May 2002, 20: 16.