- Finding the roots of mathematical functions is essential for solving real-world problems in physics, engineering, and economics.
- The Newton-Raphson method, proposed in the 17th century, is still the leading root-finding technique.
- Obtaining the true solution with the Newton-Raphson method depends on the initial guess being sufficiently close to the solution.
- Dr Hirotada Okawa at Waseda University in Japan and his collaborators have developed a new root-finder, the W4 method.
- Their W4 method will find a solution when the initial guess is far away from the solution.
Finding the roots of mathematical functions is an important technique in computational science. When we find the roots of a function, we are finding the solutions to its equation. Root-finding helps us understand the function’s behaviour and its properties, such as where it intersects with the x-axis and which values make it equal zero. For disciplines including physics, engineering, and economics, understanding the solutions to equations is essential for making predictions and solving real-world problems. For instance, those solutions can tell you at what angle you should launch an object to hit a target, or what price to charge your customers to maximise your profit.
Numerical root finding
We can also use root-finding to solve some differential equations that cannot be solved analytically. Using a computer, we prepare a computational grid space and then discretise the function in equations on it. Computational grids represent locations, known as grid points, in space where model quantities are calculated. The distance between these grid points determines which physical quantities can be captured by the model. We use discretisation to convert a continuous equation into its discrete counterpart to calculate numerical solutions. We can even approximate the derivative of a function by evaluating the difference between neighbouring variables on the computational grid and obtain a set of nonlinear equations. Now we can solve a set of nonlinear equations instead of the differential equation.
In the 17th century, Isaac Newton and Joseph Raphson independently proposed a technique to solve such a system of equations. The Newton-Raphson method is an iterative numerical method used to find the roots of a function. This root-finding algorithm requires an initial estimate of the root and, providing this initial guess is sufficiently close to the solution, produces successively better approximations to the roots until it converges on a solution. The idea that the Newton-Raphson method is guaranteed to converge on a solution when the initial guess is already close enough is known as local convergence.
The W4 method can find a solution even when the initial estimate isn’t that close.
Surprisingly, the Newton-Raphson method is still the leading root-finding technique used today. In practice, however, there are two issues with the Newton-Raphson method, namely the heavy computational cost, and the fact that obtaining the true solution depends completely on the initial guess. A number of quasi-Newton methods have been proposed to successfully reduce the computational cost, but the issue concerning the initial estimate has received little attention.
The W4 approach
Dr Hirotada Okawa at Waseda University in Japan and his colleagues have developed a new approach, called the W4 method, that can find a solution even when the initial estimate isn’t that close. They are tackling this issue from a different direction with their innovative root-finding method, inspired by the mathematical property of damped oscillators. A damped oscillation degrades over time; for example, the mechanical energy and amplitude of a swinging pendulum slowly decreases until the pendulum stops.
Okawa describes the W4 method using an analogy of a ball that is connected to a wall by a spring. If we tug the ball, extending the length of the spring, then the ball experiences the force. If we consider friction in this system, then when the ball is released, it will stop at its original position with the spring at its natural length. This should still happen if we have many balls connected by many springs.
So, if we consider the variables in nonlinear equations to be the positions of these balls, and if the balls are in positions other than their true natural positions, as dictated by the natural lengths of their springs, there will be forces driving the movement of the balls. These forces acting on the balls are the nonlinear equations. If these nonlinear system equations contain the friction term, then after some time has passed the balls (the unknown variables) can stop at their true positions. Their W4 method effectively determines the coefficient of the friction term.
Balancing gravity and pressure
The researchers show how their W4 method is an extension of the Newton-Raphson method with the same local convergence. They have successfully applied the W4 root-finding methods to several problems in astrophysics. One such problem involves a spherically symmetrical static star and has more than 100 variables. The star’s structure is determined by the balance between gravity and pressure, as described the Einstein’s and Euler’s equation. Einstein’s equation for gravitational fields and the Euler equation for gas are both complex and highly nonlinear. They often require a reliable root-finding method.
The researchers have successfully applied the W4 root-finding methods to several problems in astrophysics.
The research team have applied the W4 method to this and several other realistic astrophysical problems. They have demonstrated its success as a multi-dimensional root-finder, producing numerical solutions for large systems of nonlinear equations. They also show cases where the W4 method converges on a solution even when the Newton-Raphson method fails and either diverges or oscillates. This suggests that the W4 method has both a wider convergence region and a better global-convergence property, so the W4 method can find a solution even if the initial guess isn’t that close. Moreover, the computational cost of the W4 method is no more than that of the Newton-Raphson method.
Okawa and his collaborators are encouraged by these results and are confident that given its better global-convergence nature, the W4 method will be of benefit to many scientific and engineering fields, especially in areas where the Newton-Raphson method fails to work.
What inspired you to use the mathematical property of damped oscillators in a multi-dimensional root-finder?
We discussed in our previous paper how to solve a Poisson equation for the gravitational field in the Newtonian mechanics. We realised that it was also given as the Newtonian limit (the speed of light can be regarded as infinity) of the Einstein’s equation. Einstein’s equation has the nature of wave equations. This, together with the recent detection of ‘gravitational waves’ from heavy binaries, ignited our interest in the damping effect of such a wave equation modified from the original Poisson equation as the next step. At the same time, I fortunately found it was possible to use this idea for other equations and I thought it could be used for general nonlinear system equations. Thus, a wave equation with friction, which is a kind of damped oscillators, is considered in this work.
What were the most challenging aspects you faced as researchers developing the W4 method?
At the early stage of our research, we were not sure how to choose a damping coefficient in the W4 method, although we were aware of its importance because, for instance, a negative sign of damping terms would mean keeping energy injections to the system, resulting in some instability. When we discussed the local convergence of the W4 method compared to that of the Newton-Raphson method, we actually found our method has more degrees of freedom than that of the Newton-Raphson method. But it took me a while to realise that it could be used to determine the damping coefficient that should produce the difference between those methods. As a matter of fact, we were not entirely confident that our method is completely new and is not the same as others before the comparison. It was also quite tough for me to look for a relevant journal for this research. I got many editor’s rejections indeed before the acceptance.
What advice would you give a young researcher who’s interested in a career in theoretical physics and astrophysics?
I was extremely lucky. I was able to see a lot of active researchers, brilliant colleagues, and kind friends not only in Japan but also in other countries. I wanted to be a specialist using my strong point like them. Indeed I gained many things from them. To solve an astrophysical problem, in fact, we may need knowledge from various fields of science, such as Engineering and Astronomy, but sometimes we do not know what we need when the research begins. I feel very lucky to be a part of this environment. From this experience, I would say it is very important to find a place where you can easily ask any question and discuss your problem. I personally think that nobody knows everything that is connected with their own problem.
What has been the most satisfying aspect of this research?
At first, we just wanted to solve our astrophysical problem by our new method and, to be honest, we did not expect that our method could be regarded as an extension of the Newton-Raphson method. Some textbook states that the setup of problems may not be good if the Newton-Raphson method fails to find the solution and the setup should be reconsidered to be solvable even if the original setup has the solution. This is common sense for researchers solving nonlinear system equations. From the computational point of view, however, I believe we successfully provide a promising alternative even when the existing method fails. The W4 method will also give the motivation to solve nonlinear problems that we’ve not tried to tackle so far because the setup is too complex.
