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

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

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

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

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

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

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

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

Алгоритм доверительной области

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

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

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

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

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

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

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

(1)

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

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

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

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

$H \cdot s_{2} = - g,$

или направление отрицательной кривизны,

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

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

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

Сформулируйте двумерную подпроблему доверительной области.
Решите уравнение 1, чтобы определить испытательный шаг 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 является или направлением отрицательной кривизны или приближенным решением системы Ньютона 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{1}{2} 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{1}{2} {‖ M (x_{k} + d) ‖}_{2}^{2} = \frac{1}{2} {‖ F (x_{k}) + J (x_{k}) d ‖}_{2}^{2} \\ = \frac{1}{2} F {(x_{k})}^{T} F (x_{k}) + d^{T} J {(x_{k})}^{T} F (x_{k}) + \frac{1}{2} d^{T} J {(x_{k})}^{T} J (x_{k}) d . \end{matrix}

(2)

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

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

(3)

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

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

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

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

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

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

где α минимизирует уравнение 2.

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

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}),

(4)

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

(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}),

(5)

где скалярный _λk управляет и величиной и направлением _dk. Установите fsolve опция ScaleProblem к 'none' использовать уравнение 4 или установить эту опцию на 'jacobian' использовать уравнение 5.

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

Алгоритм fzero

fzero попытки найти корень скалярной функции f скалярной переменной x.

fzero ищет интервал вокруг точки начальной буквы, таким образом, что f (x) изменяет знак. Если вы задаете начальный интервал вместо начальной точки, fzero проверки, чтобы убедиться, что f (x) имеет различные знаки в конечных точках интервала. Начальный интервал должен быть конечным; это не может содержать ±Inf.

fzero использует комбинацию деления пополам интервала, линейной интерполяции и обратной квадратичной интерполяции для того, чтобы определить местоположение корня f (x). Смотрите fzero для получения дополнительной информации.