GuíaSistemas no linealesavanzado

Coste y eficiencia en dimensión n

Contabilidad del coste por iteración en sistemas: nn evaluaciones por FF, n2n^2 por jacobiano, coste de los sistemas lineales, índices de eficiencia y la conjetura de optimalidad multidimensional.

Qué cuesta cada iteración

En dimensión nn, cada evaluación de la función vectorial FF son nn evaluaciones escalares, y cada jacobiano F′F' son n2n^2. Además, cada sistema lineal resuelto de forma directa cuesta n33+n2−n3\frac{n^3}{3}+n^2-\frac{n}{3} productos/cocientes, y resolver qq sistemas con la misma matriz de coeficientes (factorizando una sola vez) cuesta n33+qn2−n3\frac{n^3}{3}+qn^2-\frac{n}{3}: por eso los métodos que congelan el jacobiano son tan atractivos.

EjemploEficiencia del método de Newton

Calcular los índices de eficiencia de Newton para sistemas en dimensión nn.

  1. Por iteración hay una evaluación de FF (nn escalares) y una del jacobiano (n2n^2): en total d=n2+nd=n^2+n evaluaciones funcionales.

  2. Se resuelve un único sistema lineal por iteración, así que op=n33+n2−n3op=\frac{n^3}{3}+n^2-\frac{n}{3} productos/cocientes.

  3. Con orden p=2p=2, los índices quedan:

    IN=21/(n2+n),ICN=21/(n33+2n2+2n3)I_N=2^{1/(n^2+n)},\qquad IC_N=2^{1/\left(\frac{n^3}{3}+2n^2+\frac{2n}{3}\right)}

Ambos índices tienden a 1 al crecer nn: en dimensiones altas, todas las eficiencias se comprimen y el coste de los sistemas lineales manda.

Optimalidad multidimensional

La conjetura de Kung-Traub escalar (p≤2d−1p\le 2^{d-1}) no es válida en varias variables. La conjetura multidimensional acota el orden por

p≤2k1+k2−1,k1≤k2p\le 2^{k_1+k_2-1},\qquad k_1\le k_2
k1k_1 = evaluaciones del jacobiano y k2k_2 = evaluaciones de FF por iteración (d=k1+k2d=k_1+k_2).