Задачник Базовый курс EN

Неявный шаг сквозь стену

симуляция линейная алгебра матрица точность вычислений наука и физика

Стену толщиной n·Δx разрезали на n слоёв. Узлы 0, 1, …, n: в узле 0 — улица, в узле n — комната. Температура внутренних узлов меняется так, будто каждый тянется к среднему соседей:

$$T_i' = \frac{\alpha}{\Delta x^2}\,\bigl(T_{i-1} - 2T_i + T_{i+1}\bigr), \qquad i = 1, \ldots, n - 1.$$

В комнате всё время B °C. На улице температура известна по часам — s₀ в момент 0, s₁ через час, и так далее, — а между часами меняется по прямой. В момент 0 температура в стене линейна от s₀ до B.

Сделайте K шагов неявного метода Эйлера с шагом h секунд: на шаге из момента t в t + h новые температуры находятся из уравнений

$$\frac{T_i^{\text{new}} - T_i}{h} = \frac{\alpha}{\Delta x^2}\,\bigl(T_{i-1}^{\text{new}} - 2T_i^{\text{new}} + T_{i+1}^{\text{new}}\bigr), \qquad i = 1, \ldots, n - 1,$$

где T₀^new — уличная температура в момент t + h, а T_n^new = B. Выведите температуру в середине стены и тепловой поток через её внутреннюю поверхность после последнего шага.

Во втором примере — кирпичная стена 40 см в самую холодную неделю зимы 2024/25 в Алматы, 7–14 декабря (реанализ ERA5-Land через Open-Meteo, CC BY 4.0); есть тесты и с целым отопительным сезоном.

Вход

В первой строке восемь чисел: n, Δx (м), α (м²/с), λ (Вт/(м·К)), B (°C), h (с), K, m. Во второй — m уличных температур по часам, °C. Ограничения: 2 ≤ n ≤ 400, n чётное, 1 ≤ K ≤ 3000, n·K ≤ 4·10⁵, 1 ≤ h ≤ 21 600, K·h ≤ 3600·(m − 1), m ≤ 5000.

Выход

Два числа: температура в узле n/2 и поток λ·(T_n − T_n−1)/Δx в Вт/м². Каждое принимается с ошибкой до 10⁻⁶ от модуля ответа (для ответов меньше единицы — с абсолютной).

Примеры

Пример 1

Вход

4 0.1 1e-06 1.0 20 3600 2 3
0 -10 -10

Выход

8.907939616 52.869980412

Пример 2

Вход

40 0.01 4.419e-07 0.7 20 3600 168 169
-3.8 -5 -7.2 -8.5 -9.7 -9.8 -10.1 -10.6 -9.9 -7.4 -4.7 -2.5 0.1 0.6 0.5 -0.2 -1.8 -2.5 -3.1 -3.2 -3.5 -4.5 -4.8 -5.5 -5.6 -4.8 -5 -5.1 -4.8 -4.5 -4.9 -4.6 -4.7 -5.1 -5.2 -5.3 -5.6 -5.8 -6.4 -6.6 -7.3 -7.4 -7.4 -7.7 -7.9 -8.1 -8.3 -8.9 -8.8 -9 -10.2 -10.3 -10.1 -10.3 -11.1 -11.9 -11.9 -10.2 -9.3 -8.5 -7.9 -7.5 -7.5 -7.8 -8.2 -10 -11.2 -11.5 -11.5 -11.7 -11.8 -11.6 -11.1 -11.3 -11.5 -11.5 -11.5 -11.4 -11.3 -11.3 -11.4 -10.8 -9.3 -8.5 -8.1 -7.5 -7.7 -8.2 -8.5 -8.9 -9.4 -10.2 -11.6 -12 -13.6 -14.8 -13.7 -14.9 -17.1 -18.6 -20 -21.2 -21.6 -21.4 -20.6 -18 -14.1 -10.8 -8.7 -6.6 -5.9 -6.7 -8.7 -9.6 -9.8 -9.9 -10.1 -10.1 -10.5 -11.3 -12.2 -12.9 -14.3 -15 -14.8 -14.8 -14.8 -15.1 -14.6 -11.5 -6.8 -5.1 -1.9 -1 -0.9 -2.2 -4.6 -6.4 -7.8 -9.3 -10.4 -10.9 -11.2 -11.4 -11.6 -11.4 -11.3 -11.2 -11 -10.6 -10.1 -9.9 -9.3 -7.1 -4 -1.5 0.9 2.3 2.3 1.3 -0.6 -2.2 -3.1 -3.8 -4.2 -4.1 -3.9 -3.8 -3.8

Выход

7.817095065 44.002810480

Ограничения

Время · Python: 6000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Почему не явный шаг T_i ← T_i + c(T_i−1 − 2T_i + T_i+1), где c = αh/Δx²? Посчитайте c во втором примере и вспомните, что в статье сказано о пределе шага.

2Подсказка 2

Неявный шаг — это система из n − 1 линейных уравнений. Сколько неизвестных входит в каждое уравнение? Как это меняет цену метода Гаусса?

3Идея

Перенесём неизвестные влево: −c·T_i−1^new + (1 + 2c)·T_i^new − c·T_i+1^new = T_i. У матрицы этой системы ненулевые только главная диагональ и две соседние — она трёхдиагональная. Метод Гаусса на ней не создаёт новых ненулей: исключая T_i−1 из i-го уравнения, мы трогаем только его диагональ и правую часть. Прямой ход — один проход по узлам, обратный — второй, всего O(n) на шаг. Этот частный случай метода Гаусса называют методом прогонки, или алгоритмом Томаса.

4Разбор

Известные края переносим в правую часть: к первому уравнению прибавляется c·(уличная температура в момент t + h), к последнему — c·B. Прямой ход: для первого уравнения делим всё на диагональ 1 + 2c и запоминаем коэффициент при следующем неизвестном u₀ = −c/(1 + 2c). Для каждого следующего вычитаем из него предыдущее, умноженное на −c: диагональ становится 1 + 2c + c·u_i−1, правая часть — r_i + c·r_i−1, и снова делим. Обратный ход: последнее неизвестное уже найдено, каждое предыдущее — r_i − u_i·(следующее).

Деления на ноль не будет: диагональ 1 + 2c больше суммы модулей соседних коэффициентов 2c, такая матрица называется матрицей с диагональным преобладанием, и для неё каждая новая диагональ при исключении остаётся больше c, а |u_i| < 1 — ошибки округления не растут.

Почему явный шаг не подходит. Во втором примере c = 4,4·10⁻⁷·3600/10⁻⁴ ≈ 16. Зигзаг — профиль, где соседние слои отклоняются в разные стороны, — явный шаг умножает на 1 − 4c ≈ −63, и через десяток шагов числа уходят за пределы float. Явная схема устойчива, только если c не больше примерно 1/2, то есть при шаге меньше двух минут; неявная — при любом. Но и в первом примере, где c = 0,36 и явный шаг устойчив, он даёт другой ответ: это другой метод, а условие требует неявный.

4+Решение

5Сложность

O(n) на шаг и O(n·K) всего — до 4·10⁵ простых операций, доли секунды даже на Python. Обычный метод Гаусса на плотной матрице — O(n³) на шаг: при n = 400 это 2·10⁷ операций на шаг и 2·10¹⁰ на тысячу шагов, далеко за пределом времени.

6Типичные ошибки

Явный шаг. Взрывается при c > 1/2, а при меньших c даёт другие числа — первый тест.
Плотная матрица. Хранить и исключать (n − 1)² чисел незачем: почти все они нули. Метод Гаусса «в лоб» не уложится во время на тестах с n = 400.
Улица в старый момент. В неявном шаге все значения — новые, в том числе уличная температура: в момент t + h, а не t.
Номер часа. Уличная температура между часами линейна: в момент t берутся часы ⌊t/3600⌋ и следующий; на последнем шаге момент может совпасть с последним часом таблицы.

Алгоритмы задачи

NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи