Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Algoritmos de resolución de ecuaciones

Definición de resolución de ecuaciones

Dado un conjunto de funciones no linealesn Fi(), donde está el número de componentes del vector, el objetivo de la resolución de ecuaciones es encontrar un vector que haga que todos losxnxx Fi() = 0.x

intenta resolver sistemas de ecuaciones minimizando la suma de los cuadrados de los componentes.fsolve Si la suma de los cuadrados es cero, se resuelve el sistema de la ecuación. tiene tres algoritmos:fsolve

  • Confianza-región

  • El dogleg de la región de confianza

  • Levenberg-Marquardt

Todos los algoritmos son a gran escala; Ver.Algoritmos a gran escala frente a mediano escala

La función resuelve una única ecuación unidimensional.fzero

La función resuelve sistemas de ecuaciones lineales.mldivide

Algoritmo de fsolve de la región de confianza

Muchos de los métodos utilizados en los solucionadores se basan en un concepto simple pero potente en la optimización.Optimization Toolbox™trust regions,

Para comprender el enfoque de optimización de la región de confianza, considere el problema de minimización sin restricciones, minimice (), donde la función toma argumentos vectoriales y devuelve escalares.fx Supongamos que está en un punto en el espacio y desea mejorar, es decir, pasar a un punto con un valor de función inferior.xn La idea básica es aproximarse con una función más simple, que refleja razonablemente el comportamiento de la función en un vecindario alrededor del punto.fqfNx Este vecindario es la región de confianza. Un paso de prueba se calcula minimizando (o aproximadamente minimizando) más.sN Este es el subproblema de la región de confianza,

mins{q(s), sN}.(1)

El punto actual se actualiza para ser + sixs f(x + s) < f(x); de lo contrario, el punto actual permanece sin cambios y, la región de confianza, se encogió y se repite el cálculo del paso de prueba.N

Las preguntas clave en la definición de un enfoque específico de la región de confianza para minimizar () son cómo elegir y calcular la aproximación (definida en el punto actual), cómo elegir y modificar la región de confianza y cómo resolver con precisión el subproblema de la región de confianza.fxqxN Esta sección se centra en el problema sin restricciones. Las secciones posteriores discuten complicaciones adicionales debido a la presencia de restricciones en las variables.

En el método de la región de confianza estándar (), la aproximación cuadrática se define por los dos primeros términos de la aproximación de Taylor a en; la vecindad es generalmente esférica o elipsoidal en forma.[48]qFxN Matemáticamente el subproblema de la región de confianza normalmente se indica

min{12sTHs+sTg  such that  DsΔ},(2)

donde está el gradiente de en el punto actual, es la matriz de hessian (la matriz simétrica de segundo derivados), es una matriz de escalado diagonal, Δ es un escalar positivo, y ∥. ∥ es la norma 2.gfxHD Existen buenos algoritmos para resolver (ver); Estos algoritmos suelen implicar el cálculo de todos los valores propios y un proceso de Newton aplicado a laEcuación 2[48]H ecuación secular

1Δ1s=0.

Estos algoritmos proporcionan una solución precisa.Ecuación 2 Sin embargo, requieren tiempo proporcional a varias factorizaciones de.H Por lo tanto, para los problemas de la región de confianza se necesita un enfoque diferente. Varias estrategias de aproximación y heurística, basadas en, se han propuesto en la literatura (y).Ecuación 2[42][50] El enfoque de aproximación seguido en los solucionadores es restringir el subproblema de la región de confianza a un subespacio bidimensional (y).Optimization ToolboxS[39][42] Una vez que se ha calculado el subespacio, el trabajo a resolver es trivial incluso si se necesita información completa de eigenvalue/Eigenvector (ya que en el subespacio, el problema es sólo bidimensional).SEcuación 2 La obra dominante se ha desplazado ahora a la determinación del subespacio.

El subespacio bidimensional se determina con la ayuda de unS proceso de gradiente conjugada precondicionado descrito a continuación. El solucionador define como el espacio lineal extendido porSs1 Ys2Dóndes1 está en la dirección del degradado ygs2 es un aproximado Newton Dirección, es decir, una solución para

Hs2=g,(3)

o una dirección de curvatura negativa,

s2THs2<0.(4)

La filosofía detrás de esta elección es forzar la convergencia global (a través de la dirección de descenso más pronunciada o dirección de curvatura negativa) y lograr una rápida convergencia local (a través del paso de Newton, cuando existe).S

Un boceto de minimización sin restricciones utilizando ideas de la región de confianza es ahora fácil de dar:

  1. Formule el subproblema de la región de confianza bidimensional.

  2. Resuelva para determinar el paso de prueba.Ecuación 2s

  3. Si f(x + s) < f(x)Entonces x = x + s.

  4. Ajuste Δ.

Estos cuatro pasos se repiten hasta la convergencia. La dimensión de la región de confianza Δ se ajusta según las reglas estándar. En particular, se disminuye si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Ver y para una discusión de este aspecto.[46][49]

solucionadores tratan algunos casos especiales importantes de funciones especializadas: mínimos cuadrados no lineales, funciones cuadráticas y mínimos cuadrados lineales.Optimization Toolboxf Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones posteriores.

Método de gradiente conjugada precondicionado

Una forma popular de resolver los grandes sistemas de ecuaciones lineales definidas de manera simétrica y positiva Hp = –g es el método de los degradados de conjugación preacondicionados (PCG). Este enfoque iterativo requiere la capacidad de calcular los productos de vector de matriz de la forma, donde es un vector arbitrario.H·vv La matriz definida simétrica positiva es unaM preacondicionador Para.H Es decir M = C2Dónde C–1HC–1 es una matriz bien acondicionadas o una matriz con valores eigenados agrupados.

En un contexto de minimización, puede suponer que la matriz de Hessian es simétrica.H Sin embargo, está garantizado para ser positivo definitivo sólo en el vecindario de un fuerte minimizador.H El algoritmo PCG sale cuando se encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de salida PCG,, o bien una dirección de curvatura negativa o una solución aproximada (controla la aproximación) al sistema Newtonptol Hp = –g. En ambos casos se utiliza para ayudar a definir el subespacio bidimensional utilizado en el enfoque de la región de confianza discutido en.pMétodos de la región de confianza para la minimización no lineal

Método dogleg de la región de confianza

Otro enfoque es resolver un sistema lineal de ecuaciones para encontrar la dirección de búsqueda, es decir, el método de Newton dice que resolver para la dirección de búsqueda Dk tal que

(JXk)Dk = – (FXk)
xk + 1 = Xk + Dk,

dondeJXk) es el-por-jacobianonn

J(xk)=[F1(xk)TF2(xk)TFn(xk)T].

El método de Newton puede tener dificultades. (JXk) puede ser singular, por lo que el paso de Newton Dk ni siquiera está definido. Además, el paso exacto de Newton Dk puede ser costoso de calcular. Además, el método de Newton no puede converger si el punto de partida está lejos de la solución.

El uso de técnicas de región de confianza (introducidas en) mejora la robustez cuando se inicia lejos de la solución y maneja el caso cuando (Métodos de la región de confianza para la minimización no linealJXk) es singular. Para utilizar una estrategia de región de confianza, se necesita una función de mérito para decidir sixk + 1 es mejor o peor que Xk. Una posible opción es

mindf(d)=12F(xk+d)TF(xk+d).

Pero un mínimo de () no es necesariamente una raíz de (). fdFx

El paso de Newton Dk es una raíz de

(MXk + ) = (dFXk) + (JXk) ,d

y, por lo tanto, también es un mínimo de (), dondemd

mindm(d)=12M(xk+d)22=12F(xk)+J(xk)d22=12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d.(5)

Entonces () es una mejor opción de la función de mérito que (), y por lo que el subproblema de la región de confianza esmdfd

mind[12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d],(6)

tal que D·d∥ ≤ Δ. Este subproblema puede resolverse eficientemente utilizando una estrategia dogleg.

Para obtener información general sobre los métodos de la región de confianza, consulte Conn y Nocedal.[4][31]

Implementación dogleg de la región de confianza

La característica clave de este algoritmo es el uso del procedimiento dogleg de Powell para calcular el paso, que minimiza.dEcuación 6 Para una descripción detallada, véase Powell.[34]

El paso se construye a partir de una combinación convexa de un paso de Cauchy (un paso a lo largo de la dirección de descenso más pronunciada) y un paso de Gauss-Newton para ().dfx El paso Cauchy se calcula como

DC = – (αJXk)T(FXk),

donde se elige minimizar.αEcuación 5

El paso de Gauss-Newton se calcula resolviendo

(JXkDGN = – (FXk),

utilizando el operador (División de la matriz izquierda).MATLAB®mldivide

El paso se elige para qued

=d DC + (λDGNDC),

donde es el valor más grande en el intervalo [0,1] tal queλ d∥ ≤ Δ. Si Jk es (casi) singular, es sólo la dirección Cauchy.d

El algoritmo dogleg es eficiente, ya que sólo requiere una resolución lineal por iteración (para el cálculo del paso Gauss-Newton). Además, puede ser más robusto que usar el método Gauss-Newton con una búsqueda de línea.

El método Levenberg-Marquardt

El método Levenberg-Marquardt y utiliza una dirección de búsqueda que es una solución del conjunto lineal de ecuaciones[25][27]

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(7)

o, opcionalmente, de las ecuaciones

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(8)

donde el escalar Λk controla tanto la magnitud como la dirección de Dk. Establezca la opción a elegir y establezca a elegir.ScaleProblem'none'Ecuación 7ScaleProblem'Jacobian'Ecuación 8

Cuando Λk es cero, la dirección Dk es el método Gauss-Newton. Como Λk tiende al infinito, Dk tiende hacia la dirección de descenso más pronunciada, con una magnitud que tiende a cero. Esto implica que para algunos suficientemente grandes Λk, el término F(xk + dk) <  F(xk) Se aplica. El término Λk por lo tanto, se puede controlar para garantizar el descenso, incluso cuando se encuentran los términos de segundo orden, que restringen la eficiencia del método Gauss-Newton. Por lo tanto, el método Levenberg-Marquardt utiliza una dirección de búsqueda que es un cruce entre la dirección Gauss-Newton y la dirección de descenso más pronunciada.

\ Algoritmo

Este algoritmo se describe en la sección de operadores aritméticos para.MATLABmldivide

Algoritmo fzero

intenta encontrar la raíz de una función escalar de una variable escalar.fzerofx

busca un intervalo alrededor de un punto inicial de tal forma que () cambie el signo.fzerofx Si usted da un intervalo inicial en vez de un punto inicial, los controles para aseeguran () tienen diversos signos en los puntos finales del intervalo.fzerofx El intervalo inicial debe ser finito; no puede contener ±.Inf

utiliza una combinación de bisección de intervalo, interpolación lineal y interpolación cuadrática inversa para localizar una raíz de ().fzerofx Consulte para obtener más información.fzero