Возможно ли решить нелинейные уравнения в частных производных без использования итерации Ньютона-Рафсона?

Я пытаюсь понять некоторые результаты и был бы признателен за некоторые общие замечания по решению нелинейных проблем.

Уравнение Фишера (нелинейная реакция-диффузионная ФДЭ),

U_{T} знак равно d U_{Икс Икс} + β U (1 - U) знак равно F (U)

$u_t = du_{xx} + \beta u (1 - u) = F(u)$

в дискретной форме,

U_{J}^{'} знак равно L U + β U_{J} (1 - U_{J}) знак равно F (U)

$u_j^{\prime} = \boldsymbol{L}\boldsymbol{u} + \beta u_j (1 - u_j) = F(\boldsymbol{u})$

где - дифференциальный оператор, а - трафарет дискретизации. $\boldsymbol{L}$ $\boldsymbol{u}=(u_{j-1}, u_j, u_{j+1})$

метод

Я хочу применить неявную схему, потому что мне нужна стабильность и неограниченный временной шаг. Для этой цели я использую -метод (обратите внимание, что дает полностью неявную схему, а дает трапециевидную или схему "Кранка-Николсона"), $\theta$ $\theta=1$ $\theta=0.5$

U_{J}^{'} знак равно θ F (U^{N + 1}) + (1 - θ) F (U^{N})

$u_{j}^{\prime} = \theta F(\boldsymbol{u}^{n+1}) + (1-\theta) F(\boldsymbol{u}^{n})$

Однако для нелинейных задач это сделать невозможно, поскольку уравнение нельзя записать в линейной форме.

Чтобы обойти эту проблему, я изучал два численных подхода,

Метод IMEX

$U_{J}^{'} знак равно \underset{θ - метод диффузионного члена}{\underset{⏟}{θ L U^{N + 1} + (1 - θ) L U^{N}}} + \underset{Полностью явный термин реакции}{\underset{⏟}{β U_{J}^{N} (1 - U_{J}^{N})}}$ $u_j^{\prime} = \underbrace{\theta\boldsymbol{L}\boldsymbol{u^{n+1}} + (1-\theta)\boldsymbol{L}\boldsymbol{u^{n}}}_{\theta-\text{method diffusion term}} + \underbrace{\beta u_j^{n} (1 - u_j^{n})}_{\text{Fully explicit reaction term}}$
Наиболее очевидный способ - игнорировать нелинейную часть члена реакции и просто обновить член реакции с максимально возможным значением, то есть с предыдущего временного шага. Это приводит к методу IMEX.
Ньютон Солвер

ν^{К + 1} знак равно ν^{К} - (я - θ τ A^{N})^{- 1} (ν^{К} - U_{N} - (1 - θ) τ F ({вес}^{N}) - θ τ F ({вес}^{N + 1}))

$\nu^{k+1} = \nu^{k} - (I - \theta\tau A^{n})^{-1} \left( \nu^{k} - u_{n} - (1-\theta) \tau F(w^n) - \theta\tau F(w^{n+1}) \right)$

Полное уравнение метода может быть решено с помощью итерации Ньютона-Рафсона, чтобы найти будущую переменную решения. Где - индекс итерации ( ), а - матрица Якоби . Здесь я использую символы для переменных итерации, так что они отличаются от решения уравнения в точке реального времени . Это на самом деле модифицированный решатель Ньютона, потому что якобиан не обновляется с каждой итерацией. $\theta$ $k$ $k\geq0$ $A^{n}$ $F(w^n)$ $\nu^{k}$ $u^n$

Результаты

Сравнение уравнений Фишера численных методов.

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

Вещи, которые я не понимаю:

Я удивлен тем, что метод пошагового выполнения работает нормально, но со временем он отстает от аналитического решения. ( Примечание: если я выбрал меньший временной шаг, то подход с временным шагом дает результаты, близкие к аналитической модели). Почему подход с шагом по времени дает разумные результаты для нелинейного уравнения?
Модель Ньютона работает намного лучше, но со временем начинает лидировать в аналитической модели. Почему точность подхода Ньютона уменьшается со временем? Можно ли улучшить точность?
Почему существует общая особенность, заключающаяся в том, что после многих итераций численная модель и аналитическая модель начинают расходиться? Это просто потому, что шаг по времени слишком велик или это всегда будет происходить?

numerical-analysis nonlinear-equations implicit-methods newton-method explicit-methods boyfarrell
источник

Я рекомендую ознакомиться с базовым анализом ошибок решателей ODE, например, в Hairer / Nørsett / Wanner, а также с некоторым анализом стабильности. На большинство ваших вопросов будет дан ответ.

Гвидо Каншат

@boyfarrell, чтобы избежать путаницы с другими читателями, вы должны поместить терминологию туда, где объясняется ваш метод: 1. IMEX - явный в нелинейности и неявный в линейной части. 2. это стандартная схема, которая обычно требует, чтобы метод Ньютона нашел решение для обновления

θ

$\theta$

января

Привет @ Ян, я думаю, что я получил все. Еще раз спасибо за помощь.

Boyfarrell

Ответы:

Я предполагаю, что вы провели пространственную дискретизацию, так что вы (векторное) ODE через числовую схему которая продвигает приближение в текущий момент времени к следующему значению при .

{\dot{U}}_{час} (T) знак равно F_{час} (T, U_{час} (T)), на [0, T], U_{час} (0) знак равно α,

$\dot u_h(t) = F_h(t,u_h(t)), \text{ on [0,T] }, u_h(0) = \alpha.$

Φ

$\Phi$

u_{h}^{n}

$u_h^n$

t = t^{n}

$t=t^n$

u_{h}^{n + 1}

$u_h^{n+1}$

t = t^{n + 1} := t^{n} + τ

$t=t^{n+1}:=t^n+\tau$

Тогда ваши вопросы относятся к свойствам явного , где обновление записывается как

U_{час}^{N + 1} знак равно U_{час}^{N} + Φ_{е} (T^{N}, τ, U_{час}^{N}),

$u_h^{n+1} = u_h^n + \Phi_e(t^n,\tau,u_h^n),\quad \quad \quad$

неявный , записанный как

U_{час}^{N + 1} знак равно U_{час}^{N} + Φ_{я} (T^{N}, τ, U_{час}^{N + 1}, U_{час}^{N}), (*)

$u_h^{n+1} = u_h^n + \Phi_i(t^n,\tau,u_h^{n+1},u_h^n), \quad \quad \quad (*)$

или комбинация обоих (« IMEX », см. @Jed Brown's answer) одноступенчатые схемы временного шага.

В этой установке метод Ньютона просто является подходом для решения, возможно, нелинейных в систем, возникающих из . $u_h^{n+1}$ $(*)$

А мои ответы основаны на результатах численного анализа одношаговых методов.

Если вы используете конвергентные схемы, с точки зрения порядка сходимости, нет общего преимущества использования неявных схем (см. 2.). Однако для жестких систем, например вашей системы, содержащей лапласиан, существуют неявные схемы, которые стабильны без временных ограничений. Тем не менее, теоретически, для явной схемы вы получите лучшие результаты с меньшими временными шагами, пока ваше уравнение устойчиво (например, ссылаясь на теорему Пикара-Линделёфа, если - Липшиц во втором аргументе) и ваше время Шаг не слишком маленький. $F_h$
Вы можете найти примеры, где явные схемы работают лучше. (Теоретически, вы можете обратить вспять время в вашем примере, начать со значения терминала и найти неявные и явные взаимозаменяемые значения.) Если вы сделаете ошибку Ньютона достаточно малой, вы все равно сможете повысить точность, уменьшив шаг по времени или используя время схемы высшего порядка.
Константа в оценке ошибки для глобальной ошибки растет экспоненциально с длиной интервала времени. Смотрите, например, здесь для явной схемы Эйлера. Это верно для каждого одношагового метода. Поскольку оценка имеет тип , , меньший временной шаг только откладывает этот эффект. $C$ $err \approx C \tau^p$ $p>0$ $\tau$

Еще несколько замечаний и окончательный ответ:

Схемы IMEX могут использоваться для неявной обработки только линейной части, что позволяет избежать нелинейных решений. Смотрите ответ Джеда Брауна.
Crank-Nicolson - это одностадийный метод. «Многоуровневый» в многошаговых методах относится к использованию ряда предшествующих временных шагов для определения текущего обновления. Например, как Это сильно отличается от одношаговых, а также двухшаговых или IMEX-методов, где обновление определяется без повторения предыдущих значений. $U_{час}^{N + 1} знак равно Φ_{м} (T^{N}, τ, U_{час}^{N + 1}, U_{час}^{N}, U_{час}^{N - 1}),$ $u_h^{n+1} = \Phi_m(t^n,\tau,u_h^{n+1},u_h^n,u_h^{n-1}).$

Итак, мой ответ: да , вы можете решать нелинейные уравнения без метода Ньютона. Вы можете использовать явные схемы, схемы IMEX или так называемые линейно неявные методы (например, методы Розенброка). Кроме того, вы можете использовать другие подходы для решения систем из такие как итерации с фиксированной точкой или, в некоторых случаях, алгебраические решатели. $(*)$

январь
источник

Да, я применил стандартный трафарет центральной разницы к термину диффузии. Я не могу использовать явную схему (для реальной проблемы, которую я хочу решить), потому что стабильный временной шаг нереально мал. Вот почему я изучаю IMEX или неявные варианты. Что касается вашего третьего пункта, чтобы избежать накопления ошибок, я должен использовать многошаговые методы. Является ли схема Кранка-Николсона, которую я использовал выше (с решателем Ньютона), классифицированной как многошаговый метод (она имеет два момента времени)? Я был удивлен, что ошибка увеличивается со временем при использовании метода решателя Ньютона.

boyfarrell

Crank-Nicolson - это одношаговый метод, который записывается как , Кроме того, я не понимаю, почему многошаговые схемы должны избегать накопления ошибок.

u_{h}^{n + 1} = u_{h}^{n} + Φ (t^{n}, τ^{n}, u_{h}^{n}, u_{h}^{n + 1})

$u_h^{n+1}=u_h^n + \Phi(t^n,\tau^n,u_h^n,u_h^{n+1})$

Jan

Хорошо, спасибо за объяснение о методе CN. Да, интересно, почему у многоступенчатых методов накопление ошибок меньше. Причина, по которой у решателя Ньютона возникает ошибка, заключается в том, что это один шаг, я теперь понимаю. Кстати, я знаю, что ты любишь Python. Я сделал все вышеизложенное, используя scipy, numpy и matplotlib, gist.github.com/danieljfarrell/6353776

boyfarrell

Я удалил ссылку на статью Trefethen et. и др. об интеграции IMEX высокого порядка из моего ответа, поскольку есть лучшие ссылки, чтобы узнать о схемах IMEX.

января

Короткий ответ

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

Длинный ответ

Реакция-диффузия, даже с линейной реакцией, известна тем, что демонстрирует ошибку расщепления. На самом деле, это может быть гораздо хуже, в том числе «сходиться» к неправильным установившимся состояниям, принимать устойчивые состояния за предельные циклы, путать стабильные и нестабильные конфигурации и многое другое. См. Ropp, Shadid и Ober (2004), а также Knoll, Chacon, Margolin и Mousseau (2003), чтобы взглянуть на это с точки зрения вычислительных физиков. Для анализа математики с точки зрения условий порядка, см. Книгу Хайрера и Ваннера о жестком ОДУ (методы Розенброка-W - линейно-неявный метод IMEX), Кеннеди и Карпентер (2003) для нелинейно-неявного IMEX «аддитивный» Рунге-Кутта, и страница Эмиля Константинеску для более новых методов IMEX.

В общем, методы IMEX имеют больше условий порядка, чем только лежащие в основе неявные и явные методы. Пары метода IMEX могут быть спроектированы с желаемой линейной и нелинейной стабильностью, чтобы они удовлетворяли всем условиям порядка, вплоть до порядка разработки метода. Удовлетворение всем условиям порядка сохранит асимптотическую ошибку расщепления в том же масштабе, что и ошибка в каждой схеме в отдельности. В нем ничего не говорится о доасимптотическом режиме (большие временные шаги / низкое требование к точности), но он редко бывает более строгим, чем разрешение каждой части в отдельности. В любом случае ошибка разделения видна встроенному оценщику ошибок (при использовании адаптивного контроля ошибок).

У PETSc есть много методов IMEX семейства Rosenbrock-W и аддитивных семейств Рунге-Кутты , и мы будем иметь экстраполяцию и линейный многошаговый IMEX в нашем следующем выпуске.

Отказ от ответственности: я написал большую часть поддержки временной интеграции PETSc и сотрудничаю с Эмилем (ссылка выше).

Джед браун
источник

Я, конечно, подхожу к этому с точки зрения физики, поэтому все технические детали занимают у меня некоторое время, потому что я не знаком со многими терминами. Я на самом деле экспериментатор! Не могли бы вы объяснить немного больше об условиях заказа? IMEX - эти многошаговые методы, упомянутые Яном?

Boyfarrell

Условия заказа - это отношения между коэффициентами методов ODE (например, записи в таблице Батчера для методов Рунге-Кутты), которые должны быть выполнены, чтобы иметь порядок точности. Условия заказа обсуждаются в любой книге или статье, в которой разрабатываются методы интеграции ODE, но в основном это сводится к многократному применению производных и соответствующих терминов в расширении Тейлора. Число условий порядка быстро растет для методов высокого порядка, поэтому становится сложно разрабатывать методы высокого порядка. Барьеры устанавливаются, показывая, что условия заказа взаимно несовместимы.

Джед Браун