¿Existe alguna fórmula que indique cuánto tiempo se necesita para resolver un sistema de más de $200$ ecuación lineal manualmente?

Question

Si resolviéramos un sistema de ecuaciones numéricamente, podríamos encontrar el tiempo que nos llevó el cálculo, pero ¿qué pasa si quiero resolverlo manualmente? ¿Existe alguna fórmula o relación que indique cuánto tiempo se tarda?

Answer 1

El número de operaciones aritméticas necesarias para resolver un sistema de $n$ ecuaciones lineales en $n$ incógnitas por eliminación gaussiana es del orden de $n^3$ Así que la pregunta es: ¿cuánto tiempo se tarda en hacer una multiplicación a mano? Pero el problema es que los números con los que tienes que trabajar pueden llegar a ser muy grandes, por lo que o bien estarías haciendo tu aritmética con números de 200 dígitos, o bien estarías utilizando sólo unos pocos dígitos significativos y tendrías problemas con los errores de redondeo.

Answer 2

A menos que el sistema tenga una estructura especial, la eliminación gaussiana toma $\frac{n^3-n}3$ adiciones, $\frac{n(n-1)(2n+5)}6$ multiplicaciones y $\frac{n(n+1)}2$ divisiones.

Cuando se hace a mano de la forma habitual y manteniendo $d$ dígitos significativos, las adiciones suponen un esfuerzo muy proporcional a $d$ , multiplicaciones y divisiones proporcionales a $d^2$ .

Dado que la constante de proporcionalidad variará de una persona a otra, y posiblemente de forma ligera con $d$ es mejor medir un valor medio por tiempo para el $d$ .

Una aproximación muy burda es $$Cn^3d^2.$$

---

Suponiendo que pueda procesar un $4\times4$ sistema a la precisión deseada en una hora (¿calculadora profesional?), se necesitaría como $125000$ horas para $200\times200$ es decir $52$ años, contando $8$ horas al día y trabajando $300$ días al año.

---

Según la respuesta de @GerryMyerson, efectivamente hay que tener en cuenta que los sistemas más grandes requieren más dígitos de precisión. Por el análisis de errores hacia atrás, el error es del orden de $8n^3g(A)u$ donde $u$ es la precisión de los cálculos individuales y $g(A)$ es el llamado factor de crecimiento de la matriz. Se puede considerar razonablemente igual a $n$ .

Así, la fórmula podría escribirse

$$C'n^3\log^2n.$$

No cabe duda de que existe una dependencia residual de $d=\log n$ debido al hecho de que las cargas implican números cada vez más grandes y otros efectos no lineales como la tendinitis y el envejecimiento de la calculadora. Pero esto probablemente no es medible para tamaños "pequeños" como $n=200$ .

---

Tenga en cuenta que para los grandes $d$ las multiplicaciones y divisiones se realizan mejor utilizando tablas especializadas de logaritmos, por lo que la complejidad disminuye de $O(d^2)$ a $O(d)$ más o menos. (Aunque el coste del proceso de interpolación es difícil de evaluar).