GuíaEcuaciones no linealesavanzado

Orden de convergencia y eficiencia

Definición del orden de convergencia y la ecuación del error, sus estimadores computacionales COC y ACOC, los índices de eficiencia y la conjetura de Kung-Traub que define los métodos óptimos.

Orden de convergencia y ecuación del error

De forma equivalente, escribiendo el error como $e_k=x_k-\alpha$ , el método tiene orden $p$ si y solo si cumple la ecuación del error:

e_{k+1}=C\,e_k^p+\mathcal{O}\bigl(e_k^{p+1}\bigr)

La ecuación del error se obtiene con desarrollos de Taylor, como en la demostración del orden de Newton o en el teorema de punto fijo.

Medir el orden en la práctica: COC y ACOC

Dada la secuencia de iterados, el orden teórico se estima con el orden de convergencia computacional (COC), que requiere conocer $\alpha$ :

COC=\frac{\ln\bigl(|x_{k+1}-\alpha|/|x_k-\alpha|\bigr)}{\ln\bigl(|x_k-\alpha|/|x_{k-1}-\alpha|\bigr)},\qquad k=1,2,\dots

Como en la práctica $\alpha$ no se conoce, se sustituye el error por la diferencia entre iterados consecutivos, obteniendo el orden de convergencia computacional aproximado (ACOC):

ACOC=\frac{\ln\bigl(|x_{k+1}-x_k|/|x_k-x_{k-1}|\bigr)}{\ln\bigl(|x_k-x_{k-1}|/|x_{k-1}-x_{k-2}|\bigr)},\qquad k=2,3,\dots

Es la misma filosofía que la estimación del orden en métodos para EDO: comparar cómo decrecen los errores al refinar. El ejercicio de Newton muestra el ACOC tendiendo a 2.

Eficiencia y métodos óptimos

Un orden alto no es gratis: cada iteración puede exigir varias evaluaciones de $f$ y sus derivadas. Para comparar métodos se define el índice de eficiencia $I=p^{1/d}$ , donde $p$ es el orden y $d$ el número de evaluaciones funcionales distintas por iteración, y el índice de eficiencia computacional $IC=p^{1/(d+op)}$ , que además cuenta los productos y cocientes $op$ de cada iteración.

Método	$p$	$d$	$I$	¿Óptimo?
Newton	2	2	$2^{1/2}\approx 1.414$	✔
Halley	3	3	$3^{1/3}\approx 1.442$	✘
Chebyshev	3	3	$3^{1/3}\approx 1.442$	✘
Super-Halley	3	3	$3^{1/3}\approx 1.442$	✘
Ostrowski	4	3	$4^{1/3}\approx 1.587$	✔

Orden, evaluaciones por iteración e índice de eficiencia de varios métodos.

Newton es óptimo ( $2=2^{2-1}$ ); los métodos de tercer orden con tres evaluaciones no lo son ( $3<2^{3-1}=4$ ). Los métodos multipunto como Ostrowski o Jarratt alcanzan orden 4 con solo tres evaluaciones: son óptimos y por eso destacan en la comparativa numérica.