Кратко — набор практичных методов для приближённого решения нелинейной системы $F(x)=0$, $x\in {\mathbb{R}}^n$ при большом $n$, их свойства и зависимость сходимости от начального приближения.
Основные методы (описание, сложность, сходимость, устойчивость)
- Ньютон (точный):
- Шаг: $x_{k+1}=x_k-J(x_k{)}^{-1}F(x_k)$, где $J(x)=\nabla F(x)$.
- Стоимость: факторизация/обратная — дорого для больших плотных систем (обычно $O(n^3)$), для разрежных — разрежённые факторы.
- Сходимость: квадратичная локально при невырожденном $J(x^{\ast })$ и Липшицевом градиенте; требует начального приближения в окрестности корня.
- Устойчивость: чувствителен к плохому начальному приближению и к плохо обусловленному $J$. Глобализуют через line-search или trust-region.
- Квази-Ньютон (Broyden и вариации):
- Идея: апдейт приближённой якобианы $B_k$, вместо её вычисления.
- Broyden-update: $B_{k+1}=B_k+\frac{(y_k-B_k{s}_k)s_k^{\top }}{s_k^{\top }{s}_k}$, $s_k=x_{k+1}-x_k,y_k=F(x_{k+1})-F(x_k)$.
- Стоимость: нет необходимости пересчитывать $J$; хранение полного $B_k$ — $O(n^2)$. Есть ограниченная память (L-Broyden).
- Сходимость: суперлинейная в лучшем случае; хуже локально, иногда менее устойчива, но экономнее по затратам.
- Хорош для средних $n$ или когда вычисление $J$ дорого.
- Newton–Krylov (JFNK, inexact Newton + Krylov итераторы):
- На шаге решают $J(x_k)p=-F(x_k)$ приближённо через GMRES/CG, применяя операции $v\mapsto J(x)v$ без явного $J$.
- Аппроксимация произведения: $J(x)v\approx \frac{F(x+\epsilon v)-F(x)}{\epsilon }$.
- Стоимость: одна или несколько оценок $F$ за GMRES-итерацию; экономно при большой разрежённости/структуре.
- Сходимость: при точном решении — как Ньютон; при inexact-решении — сохраняет квадратическую сходимость, если относительная точность решения линейной системы ${\eta }_k$ контролируется (правила Eisenstat–Walker).
- Устойчивость/зависимость: зависит от качества предобуславливателя; хорош для больших $n$.
- Gauss–Newton и Levenberg–Marquardt (для несвязной НЛЗ вида минимизации невязки $\min \frac{1}{2}\Vert r(x){\Vert }^2$):
- Gauss–Newton: решают $(J^{\top }J)p=-J^{\top }r$ — эффективно если остатки малы.
- Levenberg–Marquardt: $(J^{\top }J+\lambda I)p=-J^{\top }r$ — регуляризация для стабилизации при плохом условии.
- Сходимость: приближение квадратической при малых остатках; LM даёт лучшую глобальную устойчивость.
- Фиксированная точка + ускорения:
- Простой шаг $x_{k+1}=G(x_k)$ (нужно компактное представление $F(x)=0\Rightarrow x=G(x)$).
- Сходимость линейная при условии сжимающей карты ($\Vert G^{\prime }(x)\Vert <1$); скорость = константа сжатия.
- Anderson acceleration: использует последние $m$ итераций для решения линейной задачи и часто драматически ускоряет фикспойнт-итерации в больших размерностях.
- Метод продолжения / гомотопия:
- Постепенно изменяют параметр $t$ в $G(x,t)=(1-t)G_0(x)+tF(x)$, отслеживая корень от лёгкой задачи к нужной.
- Сильно расширяет область сходимости; полезен при множественных корнях или при слабом начальном приближении.
- Trust-region / damped Newton / line-search:
- Глобализация Ньютона: ограничивают шаг по норме или применяют дэмпинг, выбирают шаг по критерию уменьшения мерит-функции $\varphi (x)=\frac{1}{2}\Vert F(x){\Vert }^2$.
- Повышают устойчивость против дивергенции.
Особенности и практические рекомендации для больших размерностей
- Якобиан и его обработка:
- Если $J$ разрежён — используйте разрежённые факторы/многошаговые разрежённые решатели.
- Если явный $J$ недоступен или дорог — JFNK (Jacobian-free Newton–Krylov).
- Для JFNK критично предусмотреть хороший предобуславливатель $M$ (левый/правый): решаем приближённую систему $M^{-1}Jp=-M^{-1}F$.
- Память и вычисления:
- Для очень больших $n$ предпочтительны методы с операторными (matrix-free) действиями и ограниченной памятью: JFNK, L-Broyden, Anderson с малым $m$.
- Проблемы обусловленности:
- Плохо обусловленный $J$ замедляет сходимость и делает шаги нестабильными — используйте регуляризацию (LM), масштабирование переменных, предобусловливание.
Сходимость и устойчивость в зависимости от начального приближения
- Ньютон: локальная квадратичная сходимость, но глобально может расходиться — требуется $x_0$ в базисе притяжения корня. Если $J(x^{\ast })$ вырожден, квадратичность теряется.
- Квази-Ньютон: менее требователен к $x_0$, но может застревать; часто лучше, если $J$ шумный или вычисление якобиана дорого.
- JFNK: аналогично Ньютону в локальном смысле; его успех зависит от предобуславливателя и числа GMRES-итераций; иногда более устойчив при плохих $x_0$ при включении глобализации.
- Фиксированная точка/Anderson: требуется глобальная контрактность; Anderson расширяет области сходимости, но не гарантирует.
- Homotopy/continuation: работает при произвольном $x_0$ для старта простой задачи и постепенно ведёт к целевой — самый надёжный для проблем с несколькими решениями.
Практические правила выбора и приёмы повышения надёжности
- Если $n$ среднее и можно строить $J$: Ньютон с line-search/trust-region.
- Если $n$ большое и $J$ дорогой: JFNK с предобуславливателем + глобализация.
- Если есть форма задачи как невязка: Gauss–Newton / LM.
- Если вычисления $F$ стоят дорого и $J$ отсутствует: Anderson или L-Broyden.
- Всегда: масштабирование неизвестных, использование мерит-функции $\varphi (x)=\frac{1}{2}\Vert F(x){\Vert }^2$, адаптивная остановка по $\Vert F(x_k)\Vert$ и по шагу $\Vert x_{k+1}-x_k\Vert$.
- Для расширения области сходимости: демпинг, trust-region, продолжение по параметру, многократные попытки с разных $x_0$.
Краткие формулы-ориентиры (все указанные выше методы)
- Ньютон: $x_{k+1}=x_k-J(x_k{)}^{-1}F(x_k)$.
- Inexact Newton: решаем приближённо $J(x_k)p_k=-F(x_k)$ с относительной погрешностью ${\eta }_k$, затем $x_{k+1}=x_k+p_k$.
- Broyden-update: $B_{k+1}=B_k+\frac{(y_k-B_k{s}_k)s_k^{\top }}{s_k^{\top }{s}_k}$.
- Gauss–Newton: решают $(J^{\top }J)p=-J^{\top }r$.
- Levenberg–Marquardt: $(J^{\top }J+\lambda I)p=-J^{\top }r$.
- JFNK приближение: $J(x)v\approx \frac{F(x+\epsilon v)-F(x)}{\epsilon }$.
Вывод — для высокоразмерных задач в большинстве практических случаев оптимальным компромиссом является Newton–Krylov с хорошим предобуславливателем и глобализацией; если Jacobian недоступен или нерегулярны вычисления — Anderson или квази-Ньютон (L-Broyden). Важнейшая роль у начального приближения: плохое $x_0$ может привести к расходимости либо к приходу к нежелательному корню — спасают continuation, демпинг и глобализационные стратегии.