¿Cuál es la complejidad temporal del método Newton-Raphson utilizado para calcular las raíces cuadradas?

Answer 1

Hola quora

No soy estudiante de matemáticas, así que no entiendo completamente la solución de Tom. Pero escribí un programa de computadora para el método de Newton-Raphson e intenté ejecutar valores crecientes.

/*Fragmento de código */

/ *

x = n = 100;

y = 1

i = 0;

mientras x> y:

x = (x + y) / 2

y = n / x

i = i + 1

print “Iterations for convergence:”, i

* /

Valores: (Todos los valores de registro son base 2) *

N = 10000, iteraciones: 9, log (N) = 13.28

N = 100000000, iteraciones: 16, log (N) = 26.57

N = 10000000000000000, iteraciones: 30, log (N) = 53,15

… y así sucesivamente … Suponiendo que la división 2 tiene un valor constante, ¿la complejidad del método es menor que log (N)? Al menos eso es lo que pude ver de mis valores. ¿Puede alguien intentar responder en términos simples si el método NR es menor que logN o es mayor que igual a logN.

Answer 2

Del método de Newton – artículo de la enciclopedia – Citizendium:

Usando el método de Newton como se describió anteriormente, la complejidad temporal del cálculo de una raíz de una función f (x) con precisión de n dígitos, siempre que se conozca una buena aproximación inicial, es O ((\ log n) F (n)) donde F (n) es el costo de calcular f (x) / f ‘(x) \, con precisión de n dígitos.

Sin embargo, dependiendo de sus requisitos de precisión, puede hacerlo mejor:

Si f (x) puede evaluarse con precisión variable, el algoritmo puede mejorarse. Debido a la naturaleza de “autocorrección” del método de Newton, lo que significa que no se ve afectado por pequeñas perturbaciones una vez que ha alcanzado la etapa de convergencia cuadrática, solo es necesario utilizar la precisión de m dígitos en un paso donde la aproximación tiene m- precisión de dígitos. Por lo tanto, la primera iteración se puede realizar con una precisión dos veces mayor que la precisión de x_0, la segunda iteración con una precisión cuatro veces mayor, y así sucesivamente. Si los niveles de precisión se eligen adecuadamente, solo la iteración final requiere que f (x) / f ‘(x) \, se evalúe con precisión de n dígitos. Siempre que F (n) crezca de forma superlineal, como es el caso en la práctica, el costo de encontrar una raíz es, por lo tanto, solo O (F (n)), con un factor constante cercano a la unidad.