MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Математика\Optimization Toolbox

Список функций Optimization Toolbox

  В оглавление \ К следующему разделу \ К предыдущему разделу

FSOLVE

Решение системы нелинейных уравнений

для x, где x есть вектор и F(x) есть такая функция, которая возвращает значение вектора.

Синтаксис:

x = fsolve(fun,x0)
x = fsolve(fun,x0,options)
x = fsolve(fun,x0,options,P1,P2, ... )
[x,fval] = fsolve(...)
[x,fval,exitflag] = fsolve(...)
[x,fval,exitflag,output] = fsolve(...)
[x,fval,exitflag,output,jacobian] = fsolve(...)

Описание:

fsolve находит корни (нули) системы нелинейных уравнений.

  • x = fsolve(fun,x0) начинает с точки x0 и пытается решить описанные в fun уравнения.
  • x = fsolve(fun,x0,options) проводит оптимизацию с определенными в структурной опции параметрами оптимизации.
  • x = fsolve(fun,x0,options,P1,P2,...) передает зависящие от типа задачи параметры P1, P2 и т.д. непосредственно в функции fun. Передает пустые матрицы для опций для того, что бы использовать принимаемые по умолчанию значения опций.
  • [x,fval] = fsolve(fun,x0) возвращает значение целевой функции fun как решение от х.
  • [x,fval,exitflag] = fsolve(...) возвращает значение exitflag, которое содержит описание выходных условий.
  • [x,fval,exitflag,output] = fsolve(...) возвращает структурный выход с информацией об оптимизации
  • [x,fval,exitflag,output,jacobian] = fsolve(...) возвращает Якобиан от fun как решение от x.

Аргументы:

Входные аргументы.

Таблица 4-1, Входные аргументы, содержит общее описание аргументов, передаваемых в fsolve. Данный подраздел приводит функционально-специфические детали для fun и options:

fun

Подлежащая решению система уравнений.

fun есть такая функция, которая принимает вектор х и возвращает вектор F, нелинейные уравнения х. Функция fun может задаваться с помощью описателя функций

x = fsolve(@myfun,x0)
где myfun есть такая функция MATLAB, что

function F = myfun(x)
F = ... % Расчет значений функции от x
fun так же может быть внутренним объектом.

x = fsolve(inline('sin(x.*x)'),x0);

Если к тому же может быть рассчитан Якобиан и установленная с помощью options = optimset('Jacobian','on') опция options.Jacobian равна 'on', то функция fun во втором выходном аргументе должна возвращать значение Якобиана J, как матрицы от х.

Отметим, что посредством проверки значения nargout данная функция может обойти расчет J в случае, когда fun вызывается только с одним выходным аргументом (это случай, когда для оптимизационного алгоритма необходимо только значение F, а не J).

function [F,J] = myfun(x)
F = ... % значения целевой функции от x
if nargout > 1 % два выходных аргумента
    J = ... % Якобиан как функции от x
end

Если fun возвращает вектор (матрицу) из m компонентов и х имеет длину n, где n есть длина х0, то Якобиан J есть матрица m х n и J(i,j) будут частные производные от F(i) по x(j). (Отметим, что Якобиан J есть транспонирование градиента от F.)

options

Опции обеспечивают учет специфических деталей функции виде параметров options.

Выходные аргументы.

Таблица 4-2. “Выходные аргументы” содержат общее описание возвращаемых fsolve. аргументов. В этом разделе приводятся общие специфические детали для величин exitflag и output:

exitflag

Описывает выходные условия.

  • > 0 Данная функция сходится к решению по х.
  • 0 Максимальное число оценки функции или итерации было превышено
  • < 0 Функция не сходится к некому решению.

output

Структура, которая содержит информацию об оптимизации. Поле структуры:

  • iterations Число выполненных итераций
  • funcCount Число оценок функции
  • algorithm Используемый алгоритм
  • cgiterations Число PCG итераций (только для крупно-масштабного или большой размерности алгоритма)
  • stepsize Окончательно принятый размер шага (только для средне-масштабного алгоритма)
  • firstorderopt Измерение оптимальности первого порядка (только для крупно-масштабного алгоритма).

Для крупно-масштабной или большой размерности задачи оптимальность первого порядка есть бесконечная норма градиента g = JTF (смотри нелинейный среднеквадратичный метод)

Options

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

Для детальной информации смотри Таблицу 4-3, Параметры Опций Оптимизации.

Мы начнем с описания опции LargeScale, поскольку она устанавливает преимущественное право какой алгоритм использовать. Это только преимущественное право, поскольку должны быть выполнены определенные условия для того, что бы можно было использовать крупно-масштабный алгоритм. Для fsolve, поскольку система нелинейных уравнений не может быть недоопределенной, число уравнений (или иначе число возвращаемых fun элементов F) должно быть, по крайней мере, длины х или в противном следует использоваться средне-масштабный алгоритм.

LargeScale В случае установки 'on' используется, если это возможно, крупно-масштабный алгоритм. Для использования средне-масштабного алгоритма устанавливается значение 'off'.

Medium-Scale и Large-Scale Algorithms. Эти параметры используются как для средне-масштабного, так и крупно-масштабного алгоритмов:

Diagnostics

Проводится печать диагностической информации о минимизируемой функции.

Display

Уровень отображения. 'off' отображение не производится, 'iter' отображение проводится на каждой итерации, 'final' (принимается по умолчанию) отображение только конечной информации.

Jacobian

При установке 'on', fsolve использует заданный пользователем Якобиан (определенный в fun), или информацию об Якобиане (при использовании JacobMult) для целевой функции. При установке 'off', fsolve аппроксимирует Якобиан с помощью конечных разностей.

MaxFunEvals

Максимально число допустимых расчетов функции.

MaxIter

Максимальное число допустимых итераций.

TolFun

Конечное допустимое отклонение по значению функции.

TolX

Конечное допустимое отклонение по значению х.

Large-Scale Algorithm Only. Эти параметры используются только для крупно-масштабного алгоритма

JacobMult

Указатель функции для функции множителей Якобиана.

В случае крупно-масштабной задачи данная функция вычисляет произведение матриц Якобиана J*Y, J'*Y или J'*(J*Y) без действительного формирования J. Такая функция имеет форму

W = jmfun(Jinfo,Y,flag,p1,p2,...),

где Jinfo и дополнительные параметры p1,p2,... включают в себя используемые для расчета J*Y (или J'*Y или J'*(J*Y)) матрицы. Первый аргумент Jinfo должен быть таким же, как и возвращаемый целевой функцией fun второй аргумент.

[F,Jinfo] = fun(x,p1,p2,...)

Переменные p1,p2,... есть дополнительные параметры, передаваемые в fsolve (и в fun).

fsolve (fun,...,options,p1,p2,...)

Y есть матрица с тем же самым числом строк, что и размерность данной задачи.

flag определяет какое произведение нужно вычислять.

If flag == 0 then W = J'*(J*Y).
If flag > 0 then W = J*Y.
If flag < 0 then W = J'*Y
.

Примечание. 'Jacobian' должен быть установлен как 'on' для того, чтобы передать Jinfo из fun в jmfun.

В каждом случае J явно не формируется.

fsolve использует Jinfo для расчета предварительных данных.

В качестве примера смотри Нелинейную Оптимизацию с Компактной, но Структурированной Матрицей Гессе и Ограничениями Типа Равенств.

JacobPattern

Разреженные шаблоны Якобиана для конечного дифференцирования. В случае, если в fun неразумно вычислять матрицу Якобиана J, то lsqnonlin может аппроксимировать J через заданные разреженные конечные разности и структура J -- т.е. расположение не нулей – обеспечиваются как значения для JacobPattern. В наихудшем случае, когда эта структура неизвестна, можно установить JacobPattern, что бы плотная матрица и полные конечно-разностные аппроксимации вычислялись на каждой итерации (что принимается по умолчанию в случае неустановки JacobPattern). Это может быть чрезвычайно затратным для больших задач, поэтому обычно заслуживает внимания усилие по определению разреженной структуры.

MaxPCGIter

Максимальное число PCG (предварительно сопряженный градиент) итераций (Смотри ниже раздел Алгоритм).

PrecondBandWidth

Верхняя полоса предварительной обработки для PCG. По умолчанию используется диагональная начальная подготовка (верхняя полоса из 0). Для некоторых задач увеличение полосы снижает число итераций PCG.

TolPCG

Конечное допустимое число итераций PCG.

TypicalX

Типичные значения х.

Medium-Scale Algorithm Only. Эти параметры используются только для средне-масштабного алгоритма.

DerivativeCheck

Сравнение вводимых пользователем производных (Якобиана) с конечноразностными производными.

DiffMaxChange

Максимальное изменение в переменных для конечных-разностей.

DiffMinChange

Минимальное изменение в переменных для конечных-разностей.

LevenbergMarquardt

Выбор алгоритма Левенберга-Макуарда вместо Гаусса-Ньютона.

LineSearchType

Выбор алгоритма линейного поиска.

Примеры:

Пример 1. В данном примере находятся нули для системы из двух уравнений и двух неизвестных

Таким образом, необходимо решить следующую систему уравнений от х

Начнем с точки x0 = [-5 -5].

Сперва запишем М-файл для расчета F или значений уравнений от х

function F = myfun(x)
F = [2*x(1) - x(2) - exp(-x(1));
   -x(1) + 2*x(2) - exp(-x(2))];

Далее вызовем подпрограмму оптимизации

x0 = [-5; -5]; % примем начальное приближение за решение
options=optimset('Display','iter'); %Опция выходного отображения
[x,fval] = fsolve(@myfun,x0,options) % вызов оптимизатора

после 28 обращений к функциям нули будут найдены.

Итерация

Func-расчет

f(x)

Норма шага

Оптимальность первого порядка

CG- итерации

1

4

47071.2

1

2.29e+004

0

2

7

6527.47

1.45207

3.09e+003

1

3

10

918.372

1.49186

418

1

4

13

127.74

1.55326

57.3

1

5

16

14.9153

1.57591

8.26

1

6

19

0.779051

1.27662

1.14

1

7

22

0.00372453

0.484658

0.0683

1

8

25

9.21617e-008

0.0385552

0.000336

1

9

28

5.66133e-017

0.000193707

8.34e-009

1

Оптимизация завершена успешно:

Относительное изменение значений функции меньше, чем в OPTIONS.TolFun

x =
    0.5671
    0.5671

fval =
    1.0e-008 *
    -0.5320
    -0.5320

Оптимизация завершена успешно:

Относительное изменение значений функции меньше, чем в OPTIONS.TolFun

x =
    0.5671
    0.5671

fval =
    1.0e-08 *
    -0.5320
    -0.5320

Пример 2. Найти матрицу x, которая удовлетворяет уравнению

начнем с точки x= [1,1; 1,1].

Сперва запишем М-файл, необходимый для расчета решаемых уравнений.

function F = myfun(x)
F = x*x*x-[1,2;3,4];

Далее запустим подпрограмму оптимизации

x0 = ones(2,2); % примем начальное приближение за решение
options = optimset('Display','off'); % Выключим отображение
[x,Fval,exitflag] = fsolve(@myfun,x0,options)

Решение будет

x =
    -0.1291    0.8602
    1.2903    1.1612

Fval =
    1.0e-03 *
    0.1541    -0.1163
    0.0109    -0.0243

exitflag =
    1

и остаток будет близок к нулю.

sum(sum(Fval.*Fval))
ans =
    3.7974e-008

Примечания:

Если система уравнений является линейной, то для ускорения и повышения точности следует использовать \ (оператор обратный слэш – смотри help slash). Например. Необходимо решить следующую систему линейных уравнений

Данная задача формулируется и решается как

A = [ 3 11 -2; 1 1 -2; 1 -1 1];
b = [ 7; 4; 19];
x = A\b
x =
    13.2188
    -2.3438
    3.4375

Алгоритм:

Данный метод основан на алгоритме метода нелинейных среднеквадратичных отклонений, используемого в lsqnonlin. Достоинство используемого метода среднеквадратичных отклонений состоит в том, что данная система уравнений не равна нулю вследствие малых погрешностей и потому, что она как раз не имеет нулей, кстати алгоритм приходит в точку с малым остатком. Однако, если Якобиан системы является вырожденным, то алгоритм может сходиться в точку, неявляющуюся решением системы уравнений (Смотри ниже Ограничения и Диагностика).

Крупно-масштабная оптимизация. По умолчанию fsolve выберет крупно-масштабный алгоритм. Данный алгоритм является реализацией метода доверительных подпространств и основан на методе внутренних отражений Ньютона, описанного в [1], [2]. Каждая итерация включает в себя приближенное решение крупной линейной системы с помощью метода предварительно сопряженных градиентов(PCG). Смотри описания доверительной области и метода предварительно сопряженных градиентов в разделе “Крупно-Масштабные Алгоритмы”.

Средне-масштабная оптимизация. fsolve при установке options.LargeScale как 'off' использует метод Гаусса-Ньютона [3] с линейным поиском. В качестве альтернативы может быть выбран метод Левенберга-Макуарда [4], [5], [6] с линейным поиском. Выбор алгоритма проводится при помощи установки опции options.LevenbergMarquardt. Установка options.LevenbergMarquardt как 'on' (и опции options.LargeScale как 'off') выбирается метод Левенберга-Макуарда.

Принимаемый по умолчанию алгоритм линейного поиска, т.е. опция options.LineSearchType установлена как 'quadcubic', обеспечивается методом смешанной квадратичной и кубической полиноминальной интерполяции и экстраполяции. Защищенный кубической полиномиальный метод может быть выбран установкой опции LineSearchType как 'cubicpoly'. В общем, данный метод требует меньшего расчета функций, но большего обращения к расчету градиента. Таким образом, если градиенты приведены и могут быть вычислены без больших затрат, то метод с кубическим полиномиальным линейным поиском является предпочтительным. Используемые алгоритмы полностью описаны в разделе Стандартные Алгоритмы.

Диагностика:

fsolve может сходиться к ненулевой точке и давать следующие сообщения:

Оптимизатор затормозился в точке, которая не является минимумом.

Повторите расчет с новой начальной точки.

В этом случае снова выполните fsolve но с другой начальной точки.

Ограничения:

Разрешаемая функция должна быть непрерывной. В случае успеха fsolve дает только один корень. fsolve может сходиться к ненулевой точке, то в этом случае необходимо пытаться стартовать с другой точки.

fsolve оперирует только с реальными переменными. Если х имеет комплексные значения, то эти переменные должны быть разделены на мнимую и реальные части.

Крупно-масштабная оптимизация. В настоящее время, если Якобиан задан аналитически в fun, то параметр опции DerivativeCheck нельзя использовать в крупно-масштабном методе для проведения сравнения аналитического Якобиана с конечно-разностным Якобианом. Вместо этого, для контроля производных используется средне-масштабный метод при установке опции MaxIter как 0 итераций. Далее, задача запускается снова уже с крупно-масштабным методом. Смотри Таблицу 1-4, Область Определения и Требования к Крупо-Масштабным Задачам относительно формулировки задачи и требуемой информации.

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

Смотри также:

inline, lsqcurvefit, lsqnonlin, optimset

Литература:

  1. [1] Coleman, T.F. and Y. Li, "An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds," SIAM Journal on Optimization, Vol. 6, pp. 418-445, 1996.
  2. [2] Coleman, T.F. and Y. Li, "On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds," Mathematical Programming, Vol. 67, Number 2, pp. 189-224, 1994.
  3. [3] Dennis, J. E. Jr., "Nonlinear Least Squares," State of the Art in Numerical Analysis, ed. D. Jacobs, Academic Press, pp. 269-312.
  4. [4] Levenberg, K., "A Method for the Solution of Certain Problems in Least Squares," Quarterly Applied Mathematics 2, pp. 164-168, 1944.
  5. [5] Marquardt, D., "An Algorithm for Least-squares Estimation of Nonlinear Parameters," SIAM Journal Applied Mathematics, Vol. 11, pp. 431-441, 1963.
  6. [6] More, J. J., "The Levenberg-Marquardt Algorithm: Implementation and Theory," Numerical Analysis, ed. G. A.
  7. Watson, Lecture Notes in Mathematics 630, Springer Verlag, pp. 105-116, 1977.

  В оглавление \ К следующему разделу \ К предыдущему разделу


Поиск по сайту:

Система Orphus

Яндекс.Метрика