Studying at school about solving equations in mathematics, many students are often sure that they are wasting time in vain, and yet this skill is useful in life not only for those who decide to follow in the footsteps of Descartes, Euler or Lobachevsky.
In practice, for example, in medicine or economics, there are often situations when a specialist needs to find out when the concentration of the active substance of a particular drug reaches the required level in the patient’s blood or if it is necessary to calculate the time required for a particular business in order to become profitable.
Most often we are talking about solving nonlinear equations of various types. To do this as quickly as possible, especially with the use of computers, allow numerical methods. They are well studied and have long been proven to be effective. Among them is the Newton tangent method, which this article is devoted to.
Formulation of the problem
In this case, there is a function g, which is given on the interval (a, b) and takes certain values on it, that is, it is possible for each x belonging to (a, b) to associate a specific number g (x).
It is required to establish all the roots of the equation from the interval between points a and b (including the ends) for which the function is zeroed. Obviously, these will be the intersection points of y = g (x) with OX.
In some cases, it is more convenient to replace g (x) = 0 with a similar one of the form g 1 (x) = g 2 (x). In this case, the roots are the abscissas (x value) of the intersection points of the graphs g 1 (x) and g 2 (x).
The solution of the nonlinear equation is also important for optimization problems for which the condition for a local extremum is the inversion of the derivative of the function. In other words, such a problem can be reduced to finding the roots of the equation p (x) = 0, where p (x) is identical to g '(x).
Solution methods
For some types of nonlinear equations, for example, square or simple trigonometric equations, one can find the roots in fairly simple ways. In particular, each student knows the formulas, using which you can easily find the argument values of the points where the square trinomial is zeroed.
Methods for extracting the roots of nonlinear equations are usually divided into analytical (direct) and iterative. In the first case, the desired solution has the form of a formula, using which for a number of arithmetic operations one can find the value of the desired roots. Similar methods are developed for exponential, trigonometric, logarithmic, and simplest algebraic equations. For the rest, special numerical methods have to be used. They are easy to implement using computers that allow you to find the roots with the required accuracy.
Among them is the so-called numerical method of tangents. The latter was proposed by the great scientist Isaac Newton at the end of the XVII century. In the following centuries, the method was repeatedly improved.
Localization
Numerical methods for solving complex equations that do not have analytical solutions are usually carried out in 2 stages. First you need to localize them. This operation consists in finding such segments on OX on which there is one root of the equation being solved.
Consider the segment [a, b]. If g (x) does not have gaps on it and takes values of different signs at the endpoints, then at least 1 root of the equation g (x) = 0 is located between a and b or in them themselves. g (x) on [a, b] was monotonic. As you know, it will possess this property under the condition of constant sign g '(x).
In other words, if on [a, b] g (x) has no discontinuities and monotonically increases or decreases, and its values at the endpoints do not have the same signs, then on [a, b] there is 1 and only 1 root g (x )
It should be noted that this criterion will not apply to the roots of equations that are multiple.
Solution of the equation by halving
Before considering more complex numerical methods ( tangent method and its varieties) it is worth getting acquainted with the simplest way to identify the roots. It is called dichotomy and refers to intuitive methods. The algorithm for finding the roots is based on the theorem that if for g (x) continuous on [x 0 , x 1 ] the condition of different sign is fulfilled, then on the considered segment there is at least 1 root g (x) = 0.
To detect it, you need to divide the segment [x 0 , x 1 ] in half and designate the midpoint as x 2 . Then two options are possible: g (x 0 ) * g (x 2 ) or g (x 2 ) * g (x 1 ) are equal to or less than 0. Choose the one for which one of these inequalities is true. We repeat the procedure described above until the length [x 0 , x 1 ] becomes less than some pre-selected value that determines the accuracy of determining the root of the equation on [x 0 , x 1 ].
The advantages of the method are its reliability and simplicity, and the disadvantage is the need to initially identify points at which g (x) takes different signs, so it cannot be used for roots that have even multiplicity. In addition, he does not generalize to the case of a system of equations or if we are talking about complex roots.
Example 1
Suppose we want to solve the equation g (x) = 2x 5 + x - 1 = 0. In order not to look for a suitable segment for a long time, we build a graph using, for example, the famous Excel program. We see that as a segment for localization of the root it is better to take values from the interval [0,1]. We can be sure that at least one root of the desired equation is on it.
g '(x) = 10x 4 + 1, i.e., it is a monotonically increasing function, therefore there is only 1 root on the selected segment.
We substitute the end points in the equation. We have 0 and 1, respectively. At the first step, we take the point 0.5 for the solution. Then g (0.5) = -0.4375. So, the next segment for halving will be [0.5, 1]. Its midpoint is 0.75. In it, the value of the function is 0.226. We take for consideration the segment [0.5, 0.75] and its middle, which is located at 0.625. We calculate the value of g (x) in 0.625. It is -0.11, i.e., negative. Based on this result, we select the segment [0.625, 0.75]. We get x = 0.6875. Then g (x) = -0.00532. If the accuracy of the solution is 0.01, then we can assume that the desired result is 0.6875.
Theoretical base
This method of finding roots by the Newton tangent method is popular because of its very fast convergence.
It is based on the proven fact that if x n is an approximation to the root f (x) = 0, such that f 'C 1 , then the next approximation will be at the point where the equation of the tangent to f (x) is zeroed, i.e. .
Substitute x = x n + 1 and zero out y.
Then the tangent method algorithm looks like this:
Example 2
Let's try to use the classical Newton tangent method and find a solution to some non-linear equation that is difficult or impossible to find analytically.
Suppose you want to identify the roots for x 3 + 4x - 3 = 0 with some accuracy, for example, 0.001. As you know, the graph of any function in the form of an odd degree polynomial must at least once cross the OX axis, i.e., there is no doubt that the roots exist.
Before solving our example by the tangent method, we plot f (x) = x 3 + 4x - 3 pointwise. This is very easy to do, for example, using the Excel spreadsheet processor. From the obtained graph it will be seen that at [0,1] it intersects with the OX axis and the function y = x 3 + 4x - 3 monotonically increases. We can be sure that on [0,1] the equation x 3 + 4x - 3 = 0 has a solution and it is unique.
Algorithm
Any solution of the equations by the tangent method begins with the calculation of f '(x). We have:
Then the second derivative will have the form x * 6.
Using these expressions, we can write a formula to identify the roots of the equation by the tangent method in the form:
Next, you need to choose the initial approximation, that is, to deal with the determination of which point is considered the starting point (vol. X 0 ) for the iterative process . We consider the ends of the segment [0,1]. We will use one for which the condition of the diversity of the function and its second derivative at x 0 is true. As you can see, with the substitution x 0 = 0 it is violated, but x 0 = 1 is quite suitable.
As
then if we are interested in the solution by the tangent method with accuracy e, then the value x n can be considered as satisfying the requirements of the problem, provided that the inequality | f (x n ) / f '(x n ) | <e is satisfied.
At the first step of solving the problem by the tangent method, we have:
- x 1 = x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) = 1 - 0.2857 = 0.71429;
- since the condition is not satisfied, go further;
- we get a new value for x 2 , which is 0.674;
- notice that the ratio of the value of the function to its derivative in x 2 is less than 0.0063, we stop the process.
The tangent method in Excel
The previous example can be solved much easier and faster if you do not perform calculations manually (on a calculator), but use the capabilities of a table processor from Microsoft.
To do this, in "Excel" you need to create a new page and fill its cells with the following formulas:
- in C7 write "= DEGREE (B7; 3) + 4 * B7 - 3";
- in D7 we enter "= 4 + 3 * DEGREE (B7; 2)";
- in E7 write "= (DEGREE (B7; 3) - 3 + 4 * B7) / (3 * DEGREE (B7; 2) + 4)";
- in D7 we enter the expression "= B7 - E7";
- in B8 we enter the formula-condition "= IF (E7 <0.001;" Completion of iterations "; D7)."
Next, you need to “stretch” the formulas in columns C, D and E, first into two rows, and after the values appear in them, do the same with column B.
In a specific task, the inscription “Completion of iterations” will already appear in cell B10, and for solving the problem you will need to take the number written in the cell located one line above. For it, a separate “stretchable” column can be distinguished by entering a formula-condition there, according to which the result will be written there if the contents in one or another cell of column B takes the form “Completion of iterations”.
Pascal implementation
Let's try to get a solution to the nonlinear equation y = x 4 - 4 - 2 * x by the tangent method in Pascal.
We use an auxiliary function that will help to carry out an approximate calculation f '(x) = (f (x + delta) - f (x)) / delta. As a condition for completing the iterative process, we choose the inequality | x 0 -x 1 | <a certain small number. In Pascal, we write it as abs (x0 - x1) <= epsilon.
The program is noteworthy in that it does not require manual calculation of the derivative.
Chord method
Consider another way to identify the roots of nonlinear equations. The iteration process consists in the fact that the values of the points of intersection of the chord with the abscissas of the end points a and b with OX, denoted by x 1 , ..., x n, are taken as successive approximations to the desired root for f (x) = 0. We have:
For the point where the chord intersects the axis OX, the expression is written as:
Let the second derivative be positive for x £ [a, b] (the opposite case reduces to the considered one, if we write –f (x) = 0). In this case, the graph y = f (x) is a curve convex below and located below the chord AB . There can be 2 cases: when the function has a positive value at point a or it is negative at point b.
In the first case, as the fixed one, choose the end of a, and for x 0 we take the point b. Then successive approximations by the formula presented above form a sequence that decreases monotonically.
In the second case, the end of b is fixed at x 0 = a. The values of x obtained at each step of the iteration form a sequence that increases monotonically.
Thus, we can state that:
- motionless in the chord method is that end of the segment where the signs of the function and its second derivative do not coincide;
- the approximations for the root x - x m - lie on the side where f (x) has a sign that does not coincide with the sign f '' (x).
Iterations can be continued until the conditions for the proximity of the roots are satisfied at this and the previous iterative step modulo abs (x m - x m - 1 ) <e.
Modified way
Combined chord and tangent method allows you to set the roots of the equation, approaching them from different angles. Such a value at which the graph f (x) crosses OX allows us to refine the solution much faster than for each of the methods individually.
Suppose we need to find the roots f (x) = 0 if they are on [a, b]. You can apply any of the methods described above. However, it is better to try a combination of them, which will significantly increase the accuracy of the root.
We consider the case with an initial approximation corresponding to the condition of the diversity of the first and second derivatives at a specific point x.
Under such conditions, the solution of nonlinear equations by the tangent method allows one to find an excess root if x 0 = b, and the method using chords with the fixed end b leads to finding an approximate root with a deficiency.
The following formulas are used:
Now, the desired root x must be sought in the interval [a 1 , b 1 ]. In the next step, you need to apply the combined method already to this segment. Acting so on, we obtain formulas of the form:
If there is a difference in the first and second derivatives, then, reasoning in a similar way, to clarify the root, we obtain the following recurrence formulas:
As a condition, the estimated inequality | b n +1 - a n +1 | <e. In other words, in practice, you have to find a solution using two methods, but at each step you need to find out how close the results are.
If the above inequality is true, then as the root of the nonlinear equation on a given interval, take a point that is exactly in the middle between the solutions found at a particular iterative step.
The combined method is easily implemented in the TURBO PASCAL environment. If you wish, you can try to perform all the calculations using the tabular method in the Excel program.
In the latter case, several columns are selected to solve the problem using chords and separately for the method proposed by Isaac Newton.
At the same time, each line is used to record the calculations at a specific iterative step using two methods. Then, on the left side of the solution area, on the active work page, a column is highlighted in which the result of the calculation of the module of the difference in the values of the next iterative step for each method is entered. Another one can be used to enter the results of calculations according to the calculation formula of the logical construct “IF”, used to determine whether the condition is fulfilled or not.
Now you know how to solve complex equations. Tangent method as you have already seen, it is implemented quite simply, both in Pascal and in Excel. Therefore, you can always establish the roots of an equation that is difficult or impossible to solve by means of formulas.