Cálculo de la raíz cuadrada de un número usando el método  Newton-Raphson [Una guía práctica]

Situaciones

Dado un número total de estudiantes en una escuela y desea saber si todos los estudiantes caben en un lugar de reunión, necesita saber cuántas filas se deben formar como mínimo. Dada la dimensión de una puerta, debe saber qué tamaño de madera contrachapada se puede pasar a través de la puerta. No puedes hacer esto sin una cosa: la raíz cuadrada. Ya sea para encontrar la raíz cuadrada de un número o la raíz cuadrada de una suma de cuadrados, se necesita una función (o comando) para encontrar la raíz cuadrada de un número.

¿Fácil?

Está bien, fácil. Tenemos funciones integradas (o comandos/botones) en nuestras calculadoras, computadoras, lenguajes de programación, móviles y en todas partes para calcular la raíz cuadrada. Sí, eso se puede hacer de una manera directa. Pero, ¿qué pasa si estás en un lugar donde no hay electricidad disponible y tus dispositivos están muertos?

Ayúdame …

Sí, te estoy rescatando de esa situación si llega el día. Traigo a tu viejo amigo Newton (y también a Raphson), a quien amabas mucho durante tus días de escuela. Probablemente, algunos de ustedes también odiaron ver su nombre en todas partes, desde el libro de texto de matemáticas hasta el libro de texto de física, desde la mecánica clásica hasta el calor y la termodinámica, y desde la óptica hasta la cúbica. También recuerdo su nombre en el libro de GK.

Algoritmo

1. Tome una conjetura razonable (raíz aproximada) para la raíz cuadrada.
2. Sume la raíz aproximada con el número original dividido por la raíz aproximada y divida por 2.
   x_i := (x_i + n / x_i) / 2
3. Continúe con el paso 2 hasta que la diferencia en la raíz aproximada a lo largo de las iteraciones sea menor que el valor deseado (o valor de precisión).
4. La raíz aproximada es la raíz cuadrada que queremos.

Demostración de pizarra

Veámoslo en la pizarra ahora con n = 4 .

Fig: método de Newton para calcular la raíz cuadrada de 4

Es bien sabido que hay dos raíces cuadradas e ignoramos la raíz cuadrada negativa aquí. La raíz cuadrada negativa se puede calcular fácilmente tomando la primera aproximación cerca de la raíz cuadrada negativa.

Entonces, esto es todo, la receta para el rescate, pero no me detengo aquí ya que mis lectores amantes de la informática, Python y las matemáticas esperan ver más. Comencemos con el código de Python.

Pitón

 def mySqrt (x) : r = x precision = 10 ** ( -10 ) while abs(x - r * r) > precision: r = (r + x / r) / 2 return r

¿Por qué no lo implementas en tu sistema?

método de newton

El método de Newton, también conocido como método de Newton-Raphson, es un algoritmo de búsqueda de raíces que produce aproximaciones cada vez mejores de las raíces de una función de valor real. Las aproximaciones de la raíz son:

x_(n+1) = x_n - f(x_n) / f'(x_n)

x_0 es la aproximación aproximada de la raíz hecha al principio y las sucesivas aproximaciones van como x_1, x_2,….

f(x_n) es la función cuya raíz se quiere determinar y f'(x_n) es la derivada de la función.

Descripción

Para una aproximación x_n lo suficientemente cercana, la mejor aproximación de la raíz generalmente se puede encontrar dibujando la tangente al gráfico en x_n y encontrando dónde la tangente intersecta el eje x .

La ecuación de una recta con pendiente m que pasa por (x_1, y_1) sería:
y - y_1 = metro (x - x_1)

Aquí, la tangente es la recta, la derivada, f'(x_n) , es la pendiente y (x_n, f(x_n)) es el punto.

Entonces, y - f(x_n) = f'(x_n)(x - x_n)

Como la mejor aproximación será la intersección x de la tangente, ponga y = 0 y resuelva para x_n .

-f(x_n) = f'(x_n)(x - x_n)
o, x - x_n = -f(x_n) / f'(x_n)
Entonces, x = x_n - f(x_n) / f'(x_n) ………………. (1)

Este es el método de Newton para aproximar la raíz de una función, f(x).

Veamos ahora si podemos llegar al algoritmo provisto arriba usando la fórmula general.

Método de Newton para la raíz cuadrada

Si tenemos que encontrar la raíz cuadrada de un número n , la función sería f(x) = x² - N y tendríamos que encontrar la raíz de la función, f(x).

Aquí, el valor f(x_n) en x = x_n es:
f(x_n) = x_n² - N

Y, la derivada en el punto es:
f'(x_n) = 2 * x_n

Ahora, la mejor aproximación se puede encontrar usando (1).

x_(n+1) = x_n - (x_n² - N) / (2 * x_n)
x_(n+1) = x_n - x_n² / (2 * x_n) + N/ (2 * x_n)
x_(n+1) = x_n - x_n / 2+ N/ (2 * x_n)
x_(n+1) = x_n / 2+ N/ (2 * x_n)
x_(n+1) = (x_n + N/ x_n) / 2

Así surge el algoritmo para hallar la raíz cuadrada de un número.

Raíz cuadrada entera de un número

La raíz cuadrada entera de un número es el piso de la raíz cuadrada. El algoritmo se puede modificar un poco para encontrar la raíz cuadrada entera de un número. La condición while aquí sería aproximado * aproximado > n . El algoritmo termina cuando el cuadrado aproximado es menor o igual a N.

La relación de iteración aquí es:
x_(n+1) = (x_n + N // x_n) // 2,
donde // es la división de enteros.

Prueba de corrección

Primero, probemos la corrección de la condición while .

La relación de iteración es:
x_(n+1) = (x_n + N // x_n) // 2

Se puede escribir como:
x_(n+1) = suelo((x_n + N / x_n) / 2)

Para a ≥ 0 y b ≥ 0, a + b ≥ 2 * sqrt(a*b) .
Entonces, x_(n+1) ≥ piso(2 * sqrt(x_n * N / x_n) / 2)
o, x_(n+1) ≥ piso(raíz cuadrada(N))
Entonces, x_(n+1) ≥ enterosqrt(N)

Por lo tanto, el valor de la aproximación nunca cae por debajo del valor de intsqrt(N) .

Ahora, demostremos que la aproximación es monótonamente decreciente .

Encontremos la diferencia x_(n+1) - x_n.

x_(n+1) - x_n = (x_n + N // x_n) // 2 - x_n

Como N // x_n es menor o igual que x_n (según la condición while),
(x_n + N // x_n) // 2 ≤ (2 * x_n) // 2

Entonces, x_(n+1) - x_n ≤ (2 * x_n) // 2 - x_n

Como x_n es un número entero, (2 * x_n) // 2 = x_n.
es decir , x_(n+1) - x_n ≤ x_n - x_n
Entonces, x_(n+1)-x_n ≤ 0

Por lo tanto, la sucesión {x_n} es monótonamente decreciente.

Los valores x_(n+1) y x_n son iguales solo cuando N // x_n es igual a x_n y ahí es cuando encontramos la solución y el ciclo while se detiene. En todos los demás casos, la sucesión {x_n} es estrictamente decreciente.

Por lo tanto, se prueba la corrección del algoritmo para calcular la raíz cuadrada entera.

Análisis numérico — EndNote

El análisis numérico es el campo de los algoritmos que utilizan la aproximación numérica para los problemas de análisis matemático. Desde la ingeniería y las ciencias físicas hasta las ciencias de la vida, las ciencias sociales, la medicina, los negocios y las artes, los cálculos científicos se aplican en todas partes. El aumento de la potencia informática ha fomentado y permitido el uso de modelos matemáticos realistas en la ciencia y la ingeniería, y se requiere un análisis numérico para la implementación detallada.

Este es un ejemplo de análisis numérico, donde usamos el método de Newton para calcular la raíz de la función. Hay dos cosas que me emocionan sobre el análisis numérico.

• Se pueden resolver funciones y ecuaciones complejas que de otro modo serían irresolubles.
• Los algoritmos se pueden programar y automatizar, lo que hace que la solución sea más fácil de implementar, reproducir y empaquetar.

¿A usted también le pareció interesante el análisis numérico ? Si es así, comenta aquí tu algoritmo de análisis numérico favorito.