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

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

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

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

Доверительный регион
Trust-region-dogleg
Левенберг-Марквардт

Все алгоритмы большие шкалы; см. «Алгоритмы большого и среднего масштаба».

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 1 и _s 2, где s 1 находится в направлении градиента g, и s 2 является либо приблизительным направлением Ньютона, то есть решением

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

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

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

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

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

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

Решатель повторяет эти четыре шага до сходимости, корректируя ему размерность trust-region в соответствии со стандартными правилами. В частности, решатель уменьшает размер доверительной области, если он не принимает пробный шаг, когда 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 выходит, когда он сталкивается с направлением отрицательной (или нулевой) кривизны, то есть d^THd ≤ 0. Выходное направление PCG p является либо направлением отрицательной кривизны, либо приблизительным решением системы Ньютона Hp = - g. В любом случае p помогает задать двумерный подпространство, используемый в подходе доверительной области, обсуждаемом в Методах доверительной области для нелинейной минимизации.

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

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

J _{(<reservedrangesplaceholder3>)} dk = – F (<reservedrangesplaceholder0>)
<reservedrangesplaceholder3> <reservedrangesplaceholder2> + 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. A возможного элемента для выбора есть

$\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 _{(<reservedrangesplaceholder3>)} + J (<reservedrangesplaceholder1>) 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)

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

Обзор методов доверительной области см. в Conn [4] и Nocedal [31].

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

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

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

_dC = – αJ _{(<reservedrangesplaceholder0>)}^TF _{(<reservedrangesplaceholder0>)},

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

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

J _{(<reservedrangesplaceholder3>)} · dGN = – F (<reservedrangesplaceholder0>),

использование MATLAB^® mldivide (матричный оператор левого деления).

Алгоритм выбирает d шага так, чтобы

d = _dC + λ (_dGN – _dC),

где λ - самое большое значение в интервале [0,1] таким образом что  <reservedrangesplaceholder2> Δ. Если Jk (почти) сингулярна, d всего лишь направление Коши.

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

Метод Левенберга-Марквардта

Алгоритм Левенберга-Марквардта ([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} diag (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 для обеспечения спуска, несмотря на условия второго порядка, которые ограничивают эффективность метода Гаусса-Ньютона. Алгоритм Левенберга-Марквардта, следовательно, использует поисковое направление, которое является сечением между направлением Гаусса-Ньютона и направлением наискорейшего спуска. Для получения дополнительной информации смотрите Метод Левенберга-Марквардта в документации методом наименьших квадратов.

fzero алгоритм

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

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

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