20.1 Решатели

Octave может решать системы нелинейных уравнений вида

F (x) = 0

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

fsolve (fcn, x0)

fsolve (fcn, x0, options)

[x, fval, info, output, fjac] = fsolve (…)

Решает систему нелинейных уравнений, заданную функцией fcn.

fcn должна принимать вектор (массив), определяющий неизвестные переменные, и возвращать вектор левых частей уравнений. Правые части уравнений определены как нули. Другими словами, эта функция пытается определить вектор x такой, что fcn (x) даёт (приблизительно) все нули.

x0 — начальное приближение решения. Форма x0 сохраняется во всех вызовах fcn, но в остальном она обрабатывается как столбец.

options — структура, определяющая дополнительные параметры, которые управляют алгоритмом. В настоящее время, fsolve распознаёт следующие параметры: "AutoScaling", "ComplexEqn", "FinDiffType", "FunValCheck", "Jacobian", "MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX", "TypicalX" и "Updating".

Если "AutoScaling" равно "on", переменные будут автоматически масштабироваться в соответствии с нормами столбцов (оцененной) матрицы Якоби. В результате "TolFun" становится независимой от масштабирования. По умолчанию этот параметр установлен в "off", так как иногда он может давать неожиданные (хотя и математически правильные) результаты.

Если "ComplexEqn" равно "on", fsolve попытается решить комплексные уравнения в комплексных переменных, предполагая, что уравнения обладают комплексной производной (т.е. являются голоморфными). Если это не то, что вам нужно, вы должны разделить вещественные и мнимые части системы, чтобы получить вещественную систему.

Если "Jacobian" равно "on", это указывает, что fcn при вызове с 2 аргументами возвращает также матрицу Якоби правых частей в заданной точке.

"MaxFunEvals" определяет максимальное количество вычислений функции до остановки оптимизации. Значение по умолчанию равно 100 * number_of_variables, то есть 100 * length (x0). Значение должно быть положительным целым числом.

Если "Updating" равно "on", функция попытается использовать обновления Бройдена для обновления матрицы Якоби, чтобы сократить количество вычислений матрицы Якоби. Если ваша пользовательская функция всегда вычисляет матрицу Якоби (независимо от количества выходных аргументов), то этот параметр не дает преимуществ и должен быть отключён.

"TolX" задаёт точность завершения по неизвестным переменным, а "TolFun" — точность для уравнений. По умолчанию значение равно 1e-6 для обоих "TolX" и "TolFun".

Описание других параметров см. в optimset. Для инициализации структуры параметров со значениями по умолчанию для fsolve используйте options = optimset ("fsolve").

Первый выход x — решение, а второй выход fval содержит значение функции fcn, вычисленной в точке x (в идеале вектор всех нулей).

Третий выход info сообщает об успехе алгоритма и может принимать одно из следующих значений:

1

Сходимость к точке решения. Относительная ошибка остаточного члена меньше заданной в TolFun.

2

Последний относительный размер шага меньше TolX.

3

Последнее относительное уменьшение остаточного члена меньше TolFun.

0

Превышен предел итераций (либо MaxIter, либо MaxFunEvals).

-1

Остановлено по OutputFcn.

-3

Радиус области доверия стал чрезмерно малым.

output — структура, содержащая информацию о выполнении алгоритма fsolve. Поля в структуре:

iterations

Количество итераций.

successful

Количество успешных итераций.

funcCount

Количество вычислений функции.

Конечный выход fjac содержит значение матрицы Якоби, вычисленной в точке x.

Примечание: Если у вас есть только одно нелинейное уравнение одной переменной, использование fzero обычно гораздо более эффективно.

Примечание о пользовательских матрицах Якоби: Как неотъемлемое свойство алгоритма, матрица Якоби всегда запрашивается для вектора решения, вектор остатков которого уже известен, и это последний принятый успешный шаг. Часто это будет один из последних двух вызовов, но не всегда. Если экономия за счёт повторного использования промежуточных результатов вычисления остатков в вычислении матрицы Якоби значительна, лучшей стратегией является использование OutputFcn: после того как вектор был оценён по остаткам, если OutputFcn вызван с этим вектором, то промежуточные результаты следует сохранить для дальнейшего вычисления матрицы Якоби, и они должны храниться до тех пор, пока не будет запрошено вычисление матрицы Якоби или пока OutputFcn не будет вызван с другим вектором, в этом случае они должны быть отброшены в пользу этого последнего вектора. Следующий пример показывает, как этого можно добиться:

function [fval, fjac] = user_func (x, optimvalues, state)
persistent sav = [], sav0 = [];
if (nargin == 1)
  ## evaluation call
  if (nargout == 1)
    sav0.x = x; # mark saved vector
    ## calculate fval, save results to sav0.
  elseif (nargout == 2)
    ## calculate fjac using sav.
  endif
else
  ## outputfcn call.
  if (all (x == sav0.x))
    sav = sav0;
  endif
  ## maybe output iteration status, etc.
endif
endfunction

## …

fsolve (@user_func, x0, optimset ("OutputFcn", @user_func, …))

См. также: fzero, optimset.

Следующий пример является полным. Для решения системы уравнений

-2x^2 + 3xy   + 4 sin(y) = 6
 3x^2 - 2xy^2 + 3 cos(x) = -4

сначала нужно написать функцию для вычисления значения заданной функции. Например:

function y = f (x)
  y = zeros (2, 1);
  y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
  y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
endfunction

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

[x, fval, info] = fsolve (@f, [1; 2])

результатом является решение

x =

  0.57983
  2.54621

fval =

  -5.7184e-10
   5.5460e-10

info = 1

Значение info = 1 указывает, что решение сошлось.

Когда матрица Якоби не задана (как в приведённом выше примере), она аппроксимируется численно. Это требует больше вычислений функции и поэтому менее эффективно. В приведённом выше примере мы могли бы вычислить матрицу Якоби аналитически как

function [y, jac] = f (x)
  y = zeros (2, 1);
  y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
  y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
  if (nargout == 2)
    jac = zeros (2, 2);
    jac(1,1) =  3*x(2) - 4*x(1);
    jac(1,2) =  4*cos(x(2)) + 3*x(1);
    jac(2,1) = -2*x(2)^2 - 3*sin(x(1)) + 6*x(1);
    jac(2,2) = -4*x(1)*x(2);
  endif
endfunction

Матрица Якоби затем может быть использована с последующим вызовом fsolve:

[x, fval, info] = fsolve (@f, [1; 2], optimset ("jacobian", "on"));

что даёт то же самое решение, что и раньше.

fzero (fun, x0)

fzero (fun, x0, options)

[x, fval, info, output] = fzero (…)

Находит нуль однопеременной функции.

fun — указатель на функцию, встроенная функция или строка, содержащая имя функции для вычисления.

x0 должен быть вектором из двух элементов, определяющим две точки, которые обрамляют нуль. Другими словами, между x0(1) и x0(2) должно быть изменение знака функции. Математически это означает следующее

sign (fun(x0(1))) * sign (fun(x0(2))) <= 0

Если x0 — один скаляр, то исследуются несколько близких и удалённых значений в попытке получить корректное обрамление. Если это не удаётся, функция возвращает ошибку.

options — структура, определяющая дополнительные параметры. В настоящее время fzero распознаёт следующие параметры: "FunValCheck", "MaxFunEvals", "MaxIter", "OutputFcn" и "TolX".

"MaxFunEvals" определяет максимальное количество вычислений функции до остановки поиска. Значение по умолчанию равно Inf. Значение должно быть положительным целым числом.

"MaxIter" определяет максимальное количество итераций алгоритма до остановки поиска. Значение по умолчанию равно Inf. Значение должно быть положительным целым числом.

"TolX" задаёт точность завершения для решения x. Значение по умолчанию равно eps.

Описание других параметров см. в optimset. Для инициализации структуры параметров со значениями по умолчанию для fzero используйте options = optimset ("fzero").

При выходе функция возвращает x — приближённую точку нуля, и fval — значение функции, вычисленное в точке x.

Третий выход info сообщает об успехе алгоритма и может принимать одно из следующих значений:

• 1 Алгоритм сошёлся к решению.
• 0 Достигнуто максимальное число итераций или вычислений функции.
• -1 Алгоритм прерван пользователем OutputFcn.
• -5 Алгоритм, возможно, сошёлся к особой точке.

output — структура, содержащая информацию о работе алгоритма fzero. Поля в структуре:

• iterations Количество итераций.
• funcCount Количество вычислений функции.
• algorithm Строка "bisection, interpolation".
• bracketx Вектор из двух элементов с конечным обрамлением нуля по оси x.
• brackety Вектор из двух элементов с конечным обрамлением нуля по оси y.

См. также: optimset, fsolve.