Calculating the approximate solution to a nonlinear equations of the form
is an important computational task in its own right. This problems cannot be solved via direct methods. Iterative methods are required.
A root of Equation 1.2 of is a number such that . This lesson considers the case of a differentiable real function of a single real variable x such as the one given by Fermat's principle in Equation 1.1.
Newton's method should be familiar from calculus. Consider the situation in Figure 1.2. Approximate the function by a straight line tangent to at the most recent approximation . The next approximation is the root of .
Equivalently, Newton's method can be derived by approximating by the first order Taylor's expansion about ,
This suggests solving
for to approximate if . Hence,
This iteration needs to be stopped when two consecutive iterations are within acceptable tolerance (x-convergence), or when the function value is sufficiently small (f-convergence). These convergences are set through input tolerance parameters.. The method can be summarized in the following Algorithm.
This algorithm requires also a way to calculate the function and its derivative which bring us again to the original problem: Fermat's principle of least time traveled.