Схема Кранка — Николсон (разностная схема Кранка — Николсон, метод Кранка — Николсон) — метод конечных разностей, используемый для численного решения уравнения теплопроводности и подобных уравнений в частных производных. Метод является неявным по времени и может быть записан как неявный метод Рунге — Кутты. Этот метод второго порядка точности по времени, который также обладает вычислительной устойчивостью. Метод разработан Джоном Крэнком и Филлис Николсон в 1940-х годах.
Для уравнений диффузии (и многих других уравнений) можно показать, что метод Кранка — Николсон безусловно устойчив. Example 3.3.2 shows that Crank-Nicolson is unconditionally stable when applied to .. Однако приближенные решения могут всё ещё содержать (затухающие) ложные колебания, если отношение временного шага умноженного на коэффициент температуропроводности и квадрата шага пространства () имеет большое значение (обычно больше 1/2 согласно анализу устойчивости по фон Нейману). По этой причине, когда требуются большие временные шаги или высокое пространственное разрешение, часто используется менее точный неявный метод Эйлера, который одновременно устойчив и невосприимчив к колебаниям.
Описание
Схема Кранка — Николсон основана на формуле трапеций, дающей сходимость второго порядка по времени. Для линейных уравнений формула трапеций эквивалентна неявному методу средней точки. Простейший пример неявного метода Гаусса — Лежандра — Рунге-Кутты, который также обладает свойством интегралов сохранения. В одномерном случае уравнение в частных производных имеет вид
Пусть и значения для и , уравнение для схемы Кранка — Николсон представляет собой комбинацию прямого метода Эйлера при -ом слое (шаге) и обратного метода Эйлера на слое (однако сам метод не является просто средним значением этих двух методов, поскольку обратное уравнение Эйлера имеет неявную зависимость от решения): метод Эйлера неявный метод ЭйлераСхема Кранка — Николсон Таким образом, это неявный метод: для получения следующего значение во времени необходимо решить систему алгебраических уравнений. Если уравнение в частных производных нелинейно, то конечно-разностная схема также будет нелинейной, поэтому продвижение во времени потребует решения системы нелинейных алгебраических уравнений, хотя возможна линеаризация. Во многих задачах, особенно в линейной диффузии, система линейных уравнений оказывается трёхдиагональной и может быть эффективно решена с помощью метода прогонки. Метод прогонки обеспечивает быстрое решение системы уравнений за операций, в отличие от классического метода Гаусса, который требует операций для решения системы с плотной матрицей, где — размер матрицы.
Одномерная диффузия Метод Кранка — Николсон часто применяется к задачам диффузии. Например, в случае линейной диффузии:
После пространственной дискретизации с конечными разностями для правой части, дискретизация Кранка — Николсон выглядит следующим образом:
или, обозначая ,
Учитывая, что члены в правой части уравнения известны, это трёхдиагональная матрица, поэтому может быть эффективно решена с использованием метода прогонки вместо другого более затратного метода обращения матрицы.
Простое квазилинейное уравнение
приведёт к нелинейной системе алгебраических уравнений, которую нельзя будет легко решить; однако в некоторых случаях можно линеаризовать задачу, используя старое значение для , то есть, вместо . В других случаях, возможно, удастся оценить используя явный метод и сохранить стабильность.
Одномерная диффузия с адвекцией для устойчивого потока с несколькими соединёнными каналами Эта задача обычно рассматривается, когда возникает проблема загрязнения ручьёв или рек в условиях постоянного течения, но информация представлена только в одном измерении. Часто задачу можно упростить до одномерной и всё равно получить полезную информацию.
Ставится вопрос о концентрации растворённого загрязняющего вещества в воде. Эта задача состоит из трёх частей: известны уравнение диффузии ( выбрано как постоянное), адвективный компонент (что означает, что система развивается в пространстве из-за поля скорости), который выбирается как постоянное , и боковое взаимодействие между продольными каналами ():
где — неизветная концентрация загрязняющего вещества, а индексы и соответствуют предыдущему и следующему каналу.
По схеме Кранка — Николсон (где представляет координату, — время) каждый компонент уравнения преобразуется согласно формулам:
Для упрощения записи вводят следующие константы:
и заменить (), (), (), (), (), (), , и в (). Затем новые временные слагаемые (-слой) помещают слева и слагаемые в текущий момент времени справа (-слой)
Первый канал может контактировать только со следующим каналом (), поэтому выражение упрощается до
Таким же образом, для последнего канала, учитывается, что он может контактировать только с предыдущим каналом (), поэтому выражение упрощается до
Для решения этой линейной системы уравнений, нужно учесть, что граничные условия должны быть заданы сначала в начале каналов:
: граничное условие для канала на текущем шаге, : граничное условие для канала на следующем шаге, : граничное условие для канала, предыдущего по отношению к каналу на текущем шаге. : граничное условие для канала, следующего по отношению к каналу на текущем шаге.
Для последней ячейки каналов (), наиболее удобным условием становится адиабатическое, поэтому
Это условие выполняется тогда и только тогда, когда (независимо от нулевого значения)
Например, в матричном предствалении для случая 3 каналов и 5 узлов (включая начальное граничное условие) можно написать:
где
Здесь AA и BB должны быть массивами, состоящими из четырёх различных подмассивов:
где элементы, упомянутые выше, соответствуют следующим массивам, а также дополнительному массиву 4×4, заполненному нулями. Размеры клеток AA и BB составляют 12×12:
Вектор d здесь используется для задания граничных условий и имеет ращмер 12×1:
Чтобы найти концентрацию в любой момент времени, необходимо повторить итерационный процесс:
Двумерная диффузия Аналогичный подход применяется для двух измерений на равномерной декартовой сетке, но результаты могут привести к системе ленточно-диагональных уравнений, а не к трёхдиагональным. Двумерное уравнение теплопроводности
может быть решено с помощью разностной схемы Кранка — Николсон
предполагая, что используется квадратная сетка, при этом . Это уравнение можно несколько упростить, переставив члены и используя параметр
Схемы Кранка — Николсон устойчива при произвольных значениях параметра , однако выбор параметра сказывается на точности схемы. Теперь схема записываться в виде
Решение такой линейной системы требует больших затрат. Поэтому для численного решения уравнения в частных производных можно использовать неявный метод с чередующимися направлениями (ADI). В такой схеме одно измерение рассматривается неявно, а другое — явно для половины заданного временного шага, и наоборот — для оставшейся половины временного шага. Преимущество этой стратегии заключается в том, что неявная задача сводится к решению системы уравнений с трёхдиагональной матрицей, которая эффективно выполняется методом прогонки. Разница между истинным решением Кранка — Николсон и приближённым решением ADI имеет порядок точности и, следовательно, может быть проигнорирован при достаточно малом шаге по времени.
Нелинейные задачи
Поскольку метод Кранка — Николсон неявный, то нахождение решения для нелинейной системы уравнений, как правило, оказывается невозможным. Вместо этого обычно используется тот или иной итерационный метод. Один из вариантов — итерационный метод Ньютона, но он требует вычисления якобиана. Для многомерных систем, таких как системы вычислительной гидродинамики или численной теории относительности, даже вычисление якобиана может оказаться невозможным.
Альтернативой, свободной от якобиана, является метод простой итерации. Если — это скорость системы, тогда предсказание Кранка — Николсон будет фиксированной точкой отображения Если итерация отобоажения не сходится, то параметризованное отображение , с , может вести себя лучше. В развёрнутом виде формула для последующего шага выглядит так:
где — текущее предположение и — предыдущий временной шаг.
Даже для многомерных систем итерация этого оттображения может сходиться достаточно быстро.
В финансовой математике Поскольку ряд других явлений можно моделировать с помощью уравнения теплопроводности (часто называемого в финансовой математике уравнением диффузии), метод Кранка — Николсон также применяется в этих областях. В частности, дифференциальное уравнение модели ценообразования опционов Блэка — Шоулза можно преобразовать в уравнение теплопроводности, и, таким образом, с помощью схемы Кранка — Николсон можно получить численные решения для ценообразования опционов.
Важность этого метода для финансов заключается в том, что задачи ценообразования опционов, выходящие за рамки стандартных предположений (например, учитывающие изменение дивидендов), не могут быть решены в замкнутой форме, но могут быть решены с помощью этого метода. Однако для негладких конечных условий (которые возникают для большинства финансовых инструментов) метод Кранка — Николсон неудовлетворителен, поскольку числовые колебания не затухают. Для ванильных опционов это приводит к колебаниям значения гаммы вокруг цены исполнения. Поэтому необходимы специальные этапы инициализации затухания (например, полностью неявный метод конечных разностей).
Примечания
Ссылки Методы численного решения уравнений в частных производных для ученых и инженеров, открытый доступ к лекциям и кодам для численного решения уравнений в частных производных Пример применения и реализации метода Кранка-Николсона для уравнения адвекции
Категория:Конечные разности Категория:Численные методы дифференциальных уравнений Категория:Финансовая математика Категория:Википедия:Страницы с непроверенными переводами