Алгоритмы решения уравнения

Определение решения уравнения

Учитывая набор n нелинейные функции _Fi (x), где n является количеством компонентов векторного x, цель решения уравнения состоит в том, чтобы найти векторный x, который делает весь _Fi (x) = 0.

fsolve пытается решить системы уравнений путем минимизации суммы квадратов компонентов. Если сумма квадратов является нулем, система уравнения решена. fsolve имеет три алгоритма:

Доверительная область
Резкое искривление доверительной области
Levenberg-Marquardt

Все алгоритмы являются крупномасштабными; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы.

Функция fzero решает одно одномерное уравнение.

Функция mldivide решает системы линейных уравнений.

Доверительная область fsolve Алгоритм

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

Чтобы понять подход доверительной области к оптимизации, рассмотрите проблему безусловной минимизации, минимизируйте f (x), где функция берет аргументы вектора и возвращает скаляры. Предположим, что вы - в точке x в n - пробел, и вы хотите улучшиться, т.е. переместиться в точку с более низким значением функции. Основная идея состоит в том, чтобы аппроксимировать f с более простым функциональным q, который обоснованно отражает поведение функционального f в окружении N вокруг точки x. Это окружение является доверительной областью. Испытательный шаг s вычисляется путем минимизации (или приблизительно минимизации) по N. Это - подпроблема доверительной области,

\min_{s} {q (s), s \in N} .

(1)

Текущая точка обновляется, чтобы быть x + s если f (x + s) < f (x); в противном случае текущая точка остается неизменной, и N, область доверия, уменьшается, и испытательное вычисление шага повторяется.

Ключевые вопросы в определении определенного подхода доверительной области к минимизации f (x) состоят в том, как выбрать и вычислить приближение q (заданный в текущей точке x), как выбрать и изменить доверительную область N, и как точно решить подпроблему доверительной области. Этот раздел фокусируется на неограниченной проблеме. Более поздние разделы обсуждают дополнительные осложнения из-за присутствия ограничений на переменные.

В стандартном методе доверительной области ([48]), квадратичное приближение q задан первыми двумя сроками приближения Тейлора к F в x; окружение N является обычно сферическим или эллипсоидальным в форме. Математически подпроблема доверительной области обычно утверждается

\min {\frac{}{12} s^{T} H s + s^{T} g таким образом , что ‖ D s ‖ \leq Δ},

(2)

где g является градиентом f в текущей точке x, H является матрицей Гессиана (симметрическая матрица вторых производных), D является диагональной матрицей масштабирования, Δ является положительной скалярной величиной и ∥. ∥ является 2-нормой. Хорошие алгоритмы существуют для решения уравнения 2 (см. [48]); такие алгоритмы обычно включают вычисление всех собственных значений H, и процесс Ньютона применился к характеристическому уравнению

$\frac{1}{Δ} - \frac{1}{‖ s ‖} = 0.$

Такие алгоритмы предоставляют точное решение уравнения 2. Однако они требуют времени, пропорционального нескольким факторизациям H. Поэтому для проблем доверительной области другой подход необходим. Несколько приближений и эвристических стратегий, на основе уравнения 2, были предложены в литературе ([42] и [50]). Подход приближения, сопровождаемый в решателях Optimization Toolbox, должен ограничить подпроблему доверительной области двумерным подпространством S ([39] и [42]). Однажды подпространство S был вычислен, работа, чтобы решить уравнение 2 тривиальна, даже если полная информация о собственном значении/собственном векторе необходима (поскольку в подпространстве, проблема только двумерна). Доминирующая работа теперь переключила к определению подпространства.

Двумерное подпространство S определяется при помощи предобусловленного процесса метода сопряженных градиентов, описанного ниже. Решатель задает S как линейный пробел, заполненный s ₁ и s ₂, где s ₁ является в направлении градиента g, и s ₂ является любой аппроксимированным направлением Ньютона, т.е. решением

H \cdot s_{2} = - g,

(3)

или направление отрицательного искривления,

s_{2}^{T} \cdot H \cdot s_{2} < 0.

(4)

Философия позади этого выбора S должна обеспечить глобальную сходимость (через направление быстрейшего спуска или отрицательное направление искривления) и достигнуть быстро локальной сходимости (через шаг Ньютона, когда это существует).

Эскиз безусловной минимизации с помощью идей доверительной области теперь легко дать:

Сформулируйте двумерную подпроблему доверительной области.
Решите уравнение 2, чтобы определить испытательный шаг s.
Если f (x + s) <f (x), то x = x + s.
Настройте Δ.

Эти четыре шага повторяются до сходимости. Размерность доверительной области Δ настроена согласно стандартным правилам. В частности, это уменьшено, если испытательный шаг не принят, т.е. f (x + s) ≥ f (x). См. [46] и [49] для обсуждения этого аспекта.

Решатели Optimization Toolbox обрабатывают несколько важных особых случаев f со специализированными функциями: нелинейный метод наименьших квадратов, квадратичные функции и линейный метод наименьших квадратов. Однако базовые алгоритмические идеи эквивалентны для общего случая. Эти особые случаи обсуждены в более поздних разделах.

Предобусловленный метод сопряженных градиентов

Популярным способом решить большие симметричные положительные определенные системы линейных уравнений Hp = –g является метод Предобусловленных методов сопряженных градиентов (PCG). Этот итерационный подход требует способности вычислить матричные векторные произведения формы H·v, где v является произвольным вектором. Симметричный положительный определенный матричный M является предварительным формирователем для H. Таким образом, M = C ², где C ^–1HC–1 является хорошо подготовленной матрицей или матрицей с кластеризованными собственными значениями.

В контексте минимизации можно принять, что матрица Гессиана H симметрична. Однако H, как гарантируют, будет положителен определенный только в окружении сильного минимизатора. PCG алгоритма выходит, когда с направлением отрицательных (или нуль) искривление сталкиваются, т.е. ^dTHd ≤ 0. PCG направление вывода, p, является или направлением отрицательного искривления или аппроксимированным (tol средства управления как аппроксимированный) решение системы Ньютона Hp = –g. В любом случае p используется, чтобы помочь задать двумерное подпространство, используемое в подходе доверительной области, обсужденном в Методах Доверительной области для Нелинейной Минимизации.

Метод резкого искривления доверительной области

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

J (_xk) _dk = –F (_xk)
x _{k + 1} = _xk + _dk,

где J (_xk) является n-by-n якобиан

$J (x_{k}) = [\begin{matrix} \nabla F_{1} {(x_{k})}^{T} \\ \nabla F_{2} {(x_{k})}^{T} \\ ⋮ \\ \nabla F_{n} {(x_{k})}^{T} \end{matrix}] .$

Метод Ньютона может столкнуться с трудностями. J (_xk) может быть сингулярным, и таким образом, шаг Ньютона _dk даже не задан. Кроме того, точный шаг Ньютона _dk может быть дорогим, чтобы вычислить. Кроме того, метод Ньютона не может сходиться, если отправная точка далека от решения.

Используя методы доверительной области (введенный в Методах Доверительной области для Нелинейной Минимизации) улучшает робастность при запуске далекий от решения и обрабатывает случай, когда J (_xk) сингулярен. Чтобы использовать стратегию доверительной области, оценочная функция необходима, чтобы решить, лучше ли x _{k + 1} или хуже, чем _xk. Возможный выбор

$\min_{d} f (d) = \frac{}{12} F {(x_{k} + d)}^{T} F (x_{k} + d) .$

Но минимум f (d) является не обязательно корнем F (x).

Шаг Ньютона _dk является корнем

M (_xk + d) = F (_xk) + J (_xk) d,

и таким образом, это - также минимум m (d), где

\begin{matrix} \min_{d} m (d) = \frac{}{12} {‖ M (x_{k} + d) ‖}_{}^{22} = \frac{}{12} {‖ F (x_{k}) + J (x_{k}) d ‖}_{}^{22} \\ = \frac{}{12} F {(x_{k})}^{T} F (x_{k}) + d^{T} J {(x_{k})}^{T} F (x_{k}) + \frac{}{12} d^{T} J {(x_{k})}^{T} J (x_{k}) d . \end{matrix}

(5)

Затем m (d) является лучшим выбором оценочной функции, чем f (d), и таким образом, подпроблема доверительной области

\min_{d} [\frac{}{12} F {(x_{k})}^{T} F (x_{k}) + d^{T} J {(x_{k})}^{T} F (x_{k}) + \frac{}{12} d^{T} J {(x_{k})}^{T} J (x_{k}) d],

(6)

таким образом, что ∥D · d ∥ ≤ Δ. Эта подпроблема может быть эффективно решена с помощью стратегии резкого искривления.

Для обзора методов доверительной области смотрите Коннектикут [4], и Nocedal [31].

Реализация резкого искривления доверительной области

Ключевая возможность этого алгоритма является использованием процедуры резкого искривления Пауэлла для вычисления шага d, который минимизирует уравнение 6. Для подробного описания смотрите Пауэлла [34].

Шаг d создается из выпуклой комбинации шага Коши (шаг вдоль направления быстрейшего спуска) и шаг Ньютона Гаусса для f (x). Шаг Коши вычисляется как

_dC = –αJ (_xk) ^T F (_xk),

где α выбран, чтобы минимизировать уравнение 5.

Шаг Ньютона Гаусса вычисляется путем решения

J (_xk) · _dGN = –F (_xk),

использование MATLAB^® mldivide (матрица покинула деление), оператор.

Шаг d выбран так, чтобы

d = _dC + λ (_dGN – _dC),

где λ является самым большим значением в интервале [0,1] таким образом что ∥d ∥ ≤ Δ. Если _Jk (почти) сингулярен, d является только направлением Коши.

Алгоритм резкого искривления эффективен, поскольку он требует, чтобы только один линейный решил на итерацию (для вычисления шага Ньютона Гаусса). Кроме того, это может быть более устойчиво, чем использование метода Ньютона Гаусса с поиском строки.

Метод Levenberg-Marquardt

Levenberg-Marquardt [25], и [27] метод использует поисковое направление, которое является решением линейной системы уравнений

(J {(x_{k})}^{T} J (x_{k}) + λ_{k} I) d_{k} = - J {(x_{k})}^{T} F (x_{k}),

(7)

или, опционально, уравнений

(J {(x_{k})}^{T} J (x_{k}) + λ_{k} d i a g (J {(x_{k})}^{T} J (x_{k}))) d_{k} = - J {(x_{k})}^{T} F (x_{k}),

(8)

где скалярный _λk управляет и значением и направлением _dk. Установите опцию ScaleProblem на 'none' выбирать Equation 7 и устанавливать ScaleProblem на 'Jacobian' выбирать Equation 8.

Когда _λk является нулем, направление_{, dk} является методом Ньютона Гаусса. Когда _λk склоняется к бесконечности, _dk склоняется к направлению быстрейшего спуска со значением, имеющим тенденцию обнулять. Это подразумевает, что для некоторого достаточно большого _λk, термин F (_xk + _dk) < F (_xk) сохраняется. Термином _λk можно поэтому управлять, чтобы гарантировать спуск, даже когда с условиями второго порядка, которые ограничивают эффективность метода Ньютона Гаусса, сталкиваются. Метод Levenberg-Marquardt поэтому использует поисковое направление, которое является пересечением направления Ньютона Гаусса и направления быстрейшего спуска.