Haha, I’ve played the role of a “clickbaiter” this time; perhaps that was a bit of an exaggeration. I call it the “Ultimate Algorithm” primarily because it can increase precision arbitrarily and can handle almost any nonlinear equation (at least in theory). Improving precision involves adding terms to the known iterative formula rather than completely changing its form. Of course, as precision increases, the computational cost also grows accordingly. Its theoretical basis remains the Taylor series.
We consider the equation x=f(y). Given y, finding x is very easy, but given x, finding y is not. We consider expanding y as a Taylor series of x at the point (x_0, y_0). The key is to find the n-th order derivative of y, \frac{d^n y}{dx^n}. We denote f^{(n)}(y) = \frac{d^n x}{dy^n}, and we have: \frac{dy}{dx} = \frac{1}{\left(\frac{dx}{dy}\right)} = f'(y)^{-1}
Furthermore, according to the formula y^{(n)} = y' \frac{dy^{(n-1)}}{dy}, we can continue to find the second and third derivatives: \begin{aligned} \frac{d^2 y}{dx^2} &= \frac{d(f'(y)^{-1})}{dy} \cdot \frac{dy}{dx} = \frac{-f''(y)}{f'(y)^3} \\ \frac{d^3 y}{dx^3} &= \frac{d\left(\frac{-f''(y)}{f'(y)^3}\right)}{dy} \cdot \frac{dy}{dx} = \frac{3f''(y)^2}{f'(y)^5} - \frac{f'''(y)}{f'(y)^4} \end{aligned} \dots
Then we can write: y = y_0 + \frac{x-x_0}{f'(y_0)} - \frac{f''(y_0)}{f'(y_0)^3} \frac{(x-x_0)^2}{2!} + \left(\frac{3f''(y_0)^2}{f'(y_0)^5} - \frac{f'''(y_0)}{f'(y_0)^4}\right) \frac{(x-x_0)^3}{3!} + \dots
Noting that x_0 = f(y_0), we have actually written the recursive formula for the roots of the equation: \begin{aligned} y_{n+1} = y_n &+ \frac{x-f(y_n)}{f'(y_n)} - \frac{f''(y_n)}{f'(y_n)^3} \frac{(x-f(y_n))^2}{2!} \\ &+ \left(\frac{3f''(y_n)^2}{f'(y_n)^5} - \frac{f'''(y_n)}{f'(y_n)^4}\right) \frac{(x-f(y_n))^3}{3!} + \dots \end{aligned}
In practice, there is no need to calculate too many terms; using just the first few is sufficient (computational load increases dramatically with more terms). If we only take the first two terms, it becomes the widely used “Newton’s method.” By taking more terms, we can accelerate convergence and improve stability.
Well, regarding this, Scientific Space has introduced two “new” numerical algorithms for equations (the previous one was the “Tangent Parabola Method”). In the future, I will basically stop researching numerical methods for algebraic equations. BoJone feels that for solving equations, the “Ultimate Algorithm” in this post is already sufficient. To quote Archimedes’ tone: “Give me an equation, and I can pry out its roots!” …
Please include the original address when reposting: https://kexue.fm/archives/590
For more detailed reposting matters, please refer to: Scientific Space FAQ