All people naturally seek knowledge. (Aristotle. Metaphysics)

Numerical Methods: Solving Nonlinear Equations

Problems of solving equations constantly arise in practice, for example, in economics, when developing a business, you want to know when the profit reaches a certain value, in medicine, when studying the effect of drugs, it is important to know when the concentration of a substance reaches a given level, etc.

In optimization problems, it is often necessary to determine the points at which the derivative of a function becomes 0, which is necessary condition local extremum.

In statistics, when constructing estimates by the method least squares or the maximum likelihood method also has to solve nonlinear equations and systems of equations.

So, there is a whole class of problems related to finding solutions non-linear equations, e.g. equations or equations, etc.

In the simplest case, we have a function defined on the segment ( a, b ) and taking certain values.

Each value x from this segment we can match the number , this is functional dependency, a key concept of mathematics.

We need to find such a value at which such are called the roots of the function

Visually, we need to determine the intersection point of the graph of the functionwith the abscissa axis.

Bisection Method

The simplest method for finding the roots of an equation is the bisection method, or dichotomy.

This method is intuitive and everyone would act in a similar way when solving a problem.

The algorithm is as follows.

Suppose we have found two points and such that and have different signs, then between these points there is at least one root of the function .

Divide the segment in half and enter middle point .

Then either , or .

Let's leave that half of the segment for which the values ​​at the ends have different signs. Now we again divide this segment in half and leave that part of it, on the boundaries of which the function has different signs, and so on, to achieve the required accuracy.

Obviously, we will gradually narrow the area where the root of the function is located, and, therefore, we will determine it with a certain degree of accuracy.

Note that the described algorithm is applicable for any continuous function.

The advantages of the bisection method include its high reliability and simplicity.

The disadvantage of the method is the fact that before starting its application, it is necessary to find two points, the values ​​of the function in which have different signs. It is obvious that the method is not applicable to roots of even multiplicity and also cannot be generalized to the case complex roots and systems of equations.

The order of convergence of the method is linear, at each step the accuracy doubles, the more iterations are made, the more accurately the root is determined.

Newton's method: theoretical foundations

Newton's classical method or tangents lies in the fact that if is some approximation to the root of the equation , then the next approximation is defined as the root of the tangent to the function drawn at the point .

The equation of the tangent to a function at a point has the form:

In the tangent equation, let's put and .

Then the algorithm of sequential calculations in Newton's method is as follows:

The convergence of the tangent method is quadratic, the order of convergence is 2.

Thus, the convergence of Newton's tangent method is very fast.

Remember this wonderful fact!

Without any changes, the method is generalized to the complex case.

If the root is a root of the second multiplicity or higher, then the order of convergence drops and becomes linear.

Exercise 1. Using the method of tangents, find the solution of the equation on the segment (0, 2).

Exercise 2. Using the method of tangents, find the solution of the equation on the segment (1, 3).

The disadvantages of Newton's method include its locality, since it is guaranteed to converge for an arbitrary starting approximation only if the condition , otherwise there is convergence only in some neighborhood of the root.

The disadvantage of Newton's method is the need to calculate derivatives at each step.

Visualization of Newton's method

Newton's method (tangent method) is applied if the equation f(x) = 0 has a root , and the following conditions are met:

1) function y= f(x) is defined and continuous for ;

2) f(a)· f(b) < 0 (the function takes values ​​of different signs at the ends of the segment [ a; b]);

3) derivatives f"(x) And f""(x) keep the sign on the segment [ a; b] (i.e. function f(x) either increases or decreases on the segment [ a; b], while maintaining the direction of the convexity);

The main idea of ​​the method is as follows: on the interval [ a; b] such a number is chosen x 0 , under which f(x 0 ) has the same sign as f"" (x 0 ), i.e., the condition f(x 0 )· f"" (x) > 0 . Thus, a point with an abscissa is chosen x 0 , where the tangent to the curve y= f(x) on the segment [ a; b] crosses the axis Ox. For a point x 0 First, it is convenient to choose one of the ends of the segment.

Consider Newton's method on a specific example.

Let us be given an increasing function y \u003d f (x) \u003d x 2 -2, continuous on the interval (0;2), and having f"(x) = 2 x > 0 And f "" (x) = 2 > 0 .

Picture1 . f(x)=x 2 -2

Tangent equation in general view has the representation:

y-y 0 = f" (x 0) (x-x 0).

In our case: y-y 0 \u003d 2x 0 (x-x 0). As a point x 0 choose a point B 1 (b; f(b)) = (2,2). We draw a tangent to the function y = f(x) at point B 1 , and denote the point of intersection of the tangent and the axis Ox dot x 1. We get the equation of the first tangent: y-2=2 2(x-2), y=4x-6.

Ox: x 1 =

Picture2. Result of the first iteration

y=f(x) Ox through a point x 1, we get a point B 2 =(1.5; 0.25). Draw a tangent to the function again y = f(x) at point B 2, and denote the intersection point of the tangent and the axis Ox dot x2.

Equation of the second tangent: y-0.25=2*1.5(x-1.5), y = 3 x - 4.25.

Intersection point of tangent and axis Ox: x 2 =.

Picture3. Second iteration of Newton's method

Then we find the point of intersection of the function y=f(x) and a perpendicular to the axis Ox through the point x 2, we get the point B 3 and so on.

Picture4. The third step of the tangent method

The first approximation of the root is determined by the formula:

= 1.5.

The second approximation of the root is determined by the formula:

=

The third approximation of the root is determined by the formula:

In this way , i-th approximation of the root is determined by the formula:

Calculations are carried out until the decimal places that are needed in the answer match, or the specified accuracy e is reached - until the inequality is fulfilled | xi- xi-1 | < e.

In our case, let's compare the approximation obtained in the third step with the real answer calculated on the calculator:

Figure 5. Root of 2 calculated on a calculator

As you can see, already at the third step we got an error less than 0.000002.

Thus it is possible to calculate the value of the value "square root of 2" with any degree of accuracy. This wonderful method was invented by Newton and allows you to find the roots of very complex equations.

Newton's Method: C++ Application

In this article, we automate the process of calculating the roots of equations by writing a console application in C++. We will develop it in Visual C++ 2010 Express, which is a free and very convenient C++ development environment.

Let's start with Visual C++ 2010 Express. The start window of the program will appear. In the left corner, click "Create Project".

Rice. one. home page Visual C++ 2010 Express

In the menu that appears, select "Win32 Console Application", enter the name of the application "Newton_Method".

Rice. 2. Create a project

// Newton_method.cpp: defines the entry point for the console application #include "stdafx.h" #include using namespace std; float f(double x) //returns the value of the function f(x) = x^2-2 float df(float x) //returns the value of the derivative float d2f(float x) // second derivative value int _tmain(int argc, _TCHAR* argv) int exit = 0, i=0;//exit and loop variables double x0,xn;// computed approximations for the root double a, b, eps;// segment boundaries and required accuracy cout<<"Please input \n=>"; cin>>a>>b; // enter the boundaries of the segment on which we will look for the root cout<<"\nPlease input epsilon\n=>"; cin>>eps; // enter desired accuracy computing if (a > b) // if the user mixed up the boundaries of the segment, swap them if (f(a)*f(b)>0) // if the signs of the function on the edges of the segment are the same, then there is no root cout<<"\nError! No roots in this interval\n"; if (f(a)*d2f(a)>0) x0 = a; // to select a starting point, check f(x0)*d2f(x0)>0 ? xn = x0-f(x0)/df(x0); // count the first approximation cout<<++i<<"-th iteration = "< while(fabs(x0-xn) > eps) // until we reach the required accuracy, will continue to calculate xn = x0-f(x0)/df(x0); // directly Newton's formula cout<<++i<<"-th iteration = "< cout<<"\nRoot = "< cout<<"\nExit?=>"; ) while (exit!=1); // until the user enters exit = 1

Let's see how it works. Click on the green triangle in the upper left corner of the screen, or press F5.

If a compilation error occurs "Error error LNK1123: failure to convert to COFF: file is invalid or corrupted", then this is treated either by installing the first Service pack 1, or in the project settings Properties -> Linker, disable incremental linking.

Rice. 4. Solving the project compilation error

We will look for the roots of the function f(x) =x2-2.

First, let's test the application on the "wrong" input data. There are no roots on the segment, our program should give an error message.

We have an application window:

Rice. 5. Entering input data

We introduce the boundaries of the segment 3 and 5, and the accuracy is 0.05. The program, as it should, gave an error message that there are no roots on this segment.

Rice. 6. Error "There are no roots on this segment!"

We are not going to leave yet, so the message “Exit?” enter "0".

Now let's test the application on the correct input data. Let's introduce a segment and an accuracy of 0.0001.

Rice. 7. Calculating the root with the required accuracy

As we can see, the required accuracy was already achieved at the 4th iteration.

To exit the application, enter "Exit?" => 1.

The secant method

To avoid calculating the derivative, Newton's method can be simplified by replacing the derivative with an approximate value calculated from the two previous points:

The iterative process looks like:

This is a two-step iterative process, since it uses the previous two to find the next approximation.

The order of convergence of the secant method is lower than that of the tangent method and is equal in the case of a single root.

This wonderful value is called the golden ratio:

We verify this by assuming for convenience that .

Thus, up to infinitesimals of a higher order

Discarding the remainder term, we obtain a recurrence relation, the solution of which is naturally sought in the form .

After substitution, we have: and

For convergence it is necessary that it be positive, therefore .

Since knowledge of the derivative is not required, then with the same amount of calculations in the secant method (despite the lower order of convergence), it is possible to achieve greater accuracy than in the tangent method.

Note that near the root, one has to divide by a small number, and this leads to a loss of accuracy (especially in the case of multiple roots), therefore, choosing a relatively small , one performs calculations until executing and continue them until the modulus of the difference between neighboring approximations decreases.

As soon as growth begins, the calculations are stopped and the last iteration is not used.

This procedure for determining the end of iterations is called the technique Harvick.

Parabola method

Consider a three-step method in which the approximation is determined by the three previous points , and .

To do this, we replace, similarly to the secant method, the function with an interpolation parabola passing through the points , and .

In Newton's form, it looks like:

A point is defined as that of the roots of this polynomial, which is closer in modulus to the point.

The order of convergence of the parabola method is higher than that of the secant method, but lower than that of Newton's method.

An important difference from the previously considered methods is the fact that even if is real for real and the starting approximations are chosen to be real, the parabola method can lead to a complex root of the original problem.

This method is very useful for finding roots of high degree polynomials.

Simple iteration method

The problem of finding solutions to equations can be formulated as a problem of finding roots: , or as a problem of finding a fixed point.

Let be and - compression: (in particular, the fact that - compression, as it is easy to see, means that).

By Banach's theorem, there is a unique fixed point

It can be found as the limit of a simple iterative procedure

where initial approximation is an arbitrary point in the interval .

If the function is differentiable, then a convenient compression criterion is the number . Indeed, by the Lagrange theorem

Thus, if the derivative is less than one, then it is a contraction.

Condition is essential, because if, for example, on , then there is no fixed point, although the derivative is equal to zero. The rate of convergence depends on the value of . The smaller , the faster the convergence.

Let the root of the equation f(x)=0 be separated on the segment , and the first and second derivatives of f’(x) and f""(x) are continuous and of constant sign for хн .

Let the next approximation to the root x n be obtained (chosen) at some step of the root refinement . Then suppose that the next approximation obtained with the help of the correction h n , results in the exact value of the root

x \u003d x n + h n. (1.2.3-6)

Counting h n small value, we represent f(x n + h n) as a Taylor series, limiting ourselves to linear terms

f(x n + h n) "f(x n) + h n f'(x n). (1.2.3-7)

Considering that f(x) = f(х n + h n) = 0, we get f(х n) + h n f ’(х n) » 0.

Hence h n "- f (x n) / f'(x n). Substitute the value h n in (1.2.3-6) and instead of the exact value of the root x we get another approximation

Formula (1.2.3-8) allows you to get a sequence of approximations x 1, x 2, x 3 ..., which, under certain conditions, converges to the exact value of the root x, i.e

Geometric interpretation of Newton's method is as follows
(Fig.1.2.3-6). We take the right end of the segment b as the initial approximation x 0 and at the corresponding point B 0 on the graph of the function y \u003d f (x) we construct a tangent. The point of intersection of the tangent with the x-axis is taken as a new, more accurate approximation x 1 . Repeating this procedure many times allows you to get a sequence of approximations x 0, x 1, x 2 , . . ., which tends to the exact value of the root x.

The calculation formula of Newton's method (1.2.3-8) can be obtained from a geometric construction. So in a right triangle x 0 B 0 x 1 leg
x 0 x 1 = x 0 V 0 / tga. Considering that point B 0 is on the graph of the function f(x), and the hypotenuse is formed by a tangent to the graph f (x) at point B 0, we get

(1.2.3-9)

(1.2.3-10)

This formula coincides with (1.2.3-8) for the nth approximation.

From Fig. 1.2.3-6 it can be seen that the choice of the point a as the initial approximation can lead to the fact that the next approximation x 1 will be outside the segment on which the root is separated x. In this case, the convergence of the process is not guaranteed. In the general case, the choice of the initial approximation is made in accordance with the following rule: for the initial approximation, one should take such a point x 0 н, at which f (x 0) × f '' (x 0)> 0, that is, the signs of the function and its second derivative match.

The convergence conditions for Newton's method are formulated in the following theorem.

If the root of the equation is separated on the segment, and f'(x 0) and f''(x) are different from zero and retain their signs at xo, then if we choose such a point as the initial approximation x 0 О , what f(x 0).f¢¢(x 0)>0 , then the root of the equation f(x)=0 can be calculated with any degree of accuracy.

The error estimate of Newton's method is determined by the following expression:

(1.2.3-11)

where is the smallest value at

Highest value at

The calculation process is terminated if ,

where is the specified accuracy.

In addition, the following expressions can serve as a condition for achieving a given accuracy when refining the root by the Newton method:

The scheme of the Newton method algorithm is shown in fig. 1.2.3-7.

The left side of the original equation f(x) and its derivative f’(x) in the algorithm are designed as separate software modules.

Rice. 1.2.3-7. Algorithm diagram of Newton's method

Example 1.2.3-3. Refine the roots of the equation x-ln(x+2) = 0 using the Newton method, provided that the roots of this equation are separated on the segments x 1 н[-1.9;-1.1] and x 2 н [-0.9;2 ].

The first derivative f'(x) = 1 - 1 / (x + 2) retains its sign on each of the segments:

f'(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 at xО [-0.9; 2].

The second derivative f "(x) \u003d 1 / (x + 2) 2\u003e 0 for any x.

Thus, the convergence conditions are satisfied. Since f "" (x)> 0 over the entire range of permissible values, then to refine the root for the initial approximation x 1 choose x 0 \u003d -1.9 (since f (-1.9) × f ”(-1.9)> 0). We get a sequence of approximations:

Continuing the calculations, we obtain the following sequence of the first four approximations: -1.9; –1.8552, -1.8421; -1.8414 . The value of the function f(x) at the point x=-1.8414 is equal to f(-1.8414)=-0.00003 .

To refine the root x 2 н[-0.9;2], we choose as the initial approximations 0 =2 (f(2)×f”(2)>0). Based on x 0 = 2, we obtain a sequence of approximations: 2.0; 1.1817; 1.1462; 1.1461. The value of the function f(x) at the point x=1.1461 is equal to f(1.1461)= -0.00006.

Newton's method has a high rate of convergence, but at each step it requires the calculation of not only the value of the function, but also its derivative.

chord method

Geometric interpretation of the chord method is as follows
(Fig.1.2.3-8).

Let's draw a straight line segment through points A and B. The next approximation x 1 is the abscissa of the intersection point of the chord with the 0x axis. Let's construct the equation of a straight line segment:

Let's put y=0 and find the value x=x 1 (another approximation):

We repeat the calculation process to obtain the next approximation to the root - x 2 :

In our case (Fig.1.2.11) and the calculation formula of the chord method will look like

This formula is valid when point b is taken as a fixed point, and point a acts as an initial approximation.

Consider another case (Fig. 1.2.3-9), when .

The straight line equation for this case has the form

The next approximation x 1 at y = 0

Then the recursive formula for the method of chords for this case has the form

It should be noted that for the fixed point in the method of chords, choose the end of the segment for which the condition f (x)∙f¢¢ (x)>0 is satisfied.

Thus, if the point a is taken as a fixed point , then x 0 = b acts as an initial approximation, and vice versa.

Sufficient conditions that ensure the calculation of the root of the equation f(x)=0 using the formula of chords will be the same as for the tangent method (Newton's method), but instead of the initial approximation, a fixed point is chosen. The chord method is a modification of Newton's method. The difference is that the next approximation in the Newton method is the point of intersection of the tangent with the 0X axis, and in the method of chords - the point of intersection of the chord with the 0X axis - the approximations converge to the root from different sides.

The estimate of the error of the chord method is determined by the expression

(1.2.3-15)

Termination condition of the iteration process by the method of chords

(1.2.3-16)

If M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Example 1.2.3-4. Specify the root of the equation e x - 3x = 0, separated on a segment with an accuracy of 10 -4 .

Let's check the convergence condition:

Therefore, a=0 should be chosen as a fixed point, and x 0 \u003d 1 should be taken as the initial approximation, since f (0) \u003d 1> 0 and f (0) * f "(0)> 0.

In the problem of minimizing a function, a good choice of the initial approximation is of paramount importance. Of course, it is impossible to invent general rule, which would be satisfactory for all cases, i.e., for all possible non-linear functions. Every time you have to look for your own solution. Below we propose a set of some methods for finding rough initial approximations, which in practice can serve as a starting point for the search for satisfactory approximations in a particular problem.

9.6.1. Grid search. This method is especially effective for a small number of intrinsically nonlinear parameters. Often, functions are arranged in such a way that when fixing the values ​​of some parameters (which we call actually non-linear), the rest of the parameters become linear.

Given then the lower and upper bounds for the non-linear parameters, with a certain step, it is possible to enumerate the options on the resulting grid of values ​​of these proper non-linear parameters and identify the linear regression that leads to the minimum sum of squares.

As an example, consider the function

Here, the actual non-linear parameter will be . Suppose we know that . Let h be the step for the parameter . Compute Linear Regressions

where and find for each of them the minimum sum of squares. The smallest of them corresponds to the optimal initial approximation. In principle, the step , on which the "density" of the grid depends, can vary, so that by reducing the value of h, the values ​​of the parameters can be found with any accuracy.

9.6.2. Model conversion.

Sometimes, by some transformation, the model can be reduced to a linear one, or the number of intrinsically non-linear parameters can be reduced (see Section 6.2.3). We show how this can be achieved using the example of a logistic curve

Performing an inverse transformation on the corresponding regression equations, we obtain

Denoting we come to a new function, the number of linear parameters of which has increased from one to two . An estimate for a parameter in the new model can be found, for example, using the previous method.

Here it is appropriate to make the following remark about the transformations of regression models. It should be borne in mind that the error , which entered additively into the original equation, after the transformation, generally speaking, will no longer be additive.

Using the expansion in a Taylor series and denoting the transformation through we obtain, neglecting the terms of the order

Hence it follows that

The last equality can be taken as a basis for analyzing the problem with the transformed model.

9.6.3. Splitting the sample into subsamples.

To find the initial approximation, you can divide the entire sample into subsamples (with approximately equal volumes), where is the number of unknown parameters. For each subsample, we find the averages over y and over X, which we denote respectively m. We solve the system of nonlinear equations for

The solution of this system will be the initial approximation of the parameters. Obviously, in order to this method"worked", it is necessary that this system of nonlinear equations be solved quite easily, for example, analytically.

9.6.4. Taylor series expansion in independent variables.

The basis of iterative minimization of the sum of squares is the expansion of the regression function in a Taylor series to linear terms in terms of parameters. To find a rough initial approximation, it is sometimes useful to approximate the regression by expanding it into a Taylor series in independent variables. For simplicity, we will assume that it is one-dimensional. Let - the average value, then approximately

Denote , thus we arrive at a linear model

Let be the least squares estimates of the parameters of this linear regression. As initial approximations, we take the solution of a nonlinear system of equations with respect to

Tormenting at school over solving equations in mathematics lessons, many students are often sure that they are wasting their time, and meanwhile, such a skill will come in handy 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 it is necessary to calculate the time required for a particular business to become profitable.

More often we are talking on the solution of nonlinear equations of various types. To do this as quickly as possible, especially with the use of computers, numerical methods allow. They are well studied and have long proven their effectiveness. Among them is Newton's tangent method, which is the subject of this article.

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, i.e., it is possible to associate a specific number g (x) with each x belonging to (a, b).

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 set to zero. Obviously, these will be the points of intersection of y = g(x) with OX.

In some cases, it is more convenient to replace g(x)=0 with a similar one, g 1 (x) = g 2 (x). In this case, the abscissas (x value) of the intersection points of the graphs g 1 (x) and g 2 (x) act as roots.

The solution of a nonlinear equation is also important for optimization problems, for which the local extremum condition is the conversion of the derivative of the function to 0. 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, such as square or simple trigonometric equations, roots can be found in fairly simple ways. In particular, every student knows the formulas, using which you can easily find the values ​​of the argument 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 certain number of arithmetic operations, you can find the value of the desired roots. Similar methods have been developed for exponential, trigonometric, logarithmic and simple algebraic equations. For the rest, one has to use special numerical methods. They are easy to implement with the help of computers, which 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 17th 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.

Let's consider a segment. If g(x) on it has no discontinuities and takes values ​​of different signs at the end points, then between a and b or in themselves there is at least 1 root of the equation g(x) = 0. For it to be unique, it is required that g(x) was monotonic. As is known, it will have such a property under the condition that g’(x) is of constant sign.

In other words, if g(x) has no discontinuities and monotonically increases or decreases, and its values ​​at the end points do not have the same signs, then there is 1 and only 1 root g(x).

In this case, you should know that this criterion will not work for the roots of equations that are multiple.

Solving the equation by dividing in half

Before considering more complex numerical tangents and its varieties), it is worth getting acquainted with the most in a simple way identifying roots. It is called a dichotomy and refers to the intuitive finding of roots based on the theorem that if for g (x), continuous on, the condition of different signs is satisfied, then on the segment under consideration there is at least 1 root g (x) = 0.

To find it, you need to divide the segment 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. We choose the one for which one of these inequalities is true. We repeat the procedure described above until the length becomes less than a certain, pre-selected value that determines the accuracy of determining the root of the equation on .

The advantages of the method include its reliability and simplicity, and the disadvantage is the need to initially identify the points at which g (x) takes on different signs, so it cannot be used for roots with even multiplicity. In addition, it does not generalize to the case of a system of equations or when it comes to complex roots.

Example 1

Let 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 well-known Excel program. We see that it is better to take values ​​from the interval as a segment for localizing the root. We can be sure that at least one root of the desired equation exists on it.

g "(x) \u003d 10x 4 + 1, i.e. this is a monotonically increasing function, therefore there is only 1 root on the selected segment.

Substitute the endpoints into the equation. We have 0 and 1 respectively. At the first step, we take the point 0.5 as the solution. Then g(0.5) = -0.4375. So, the next segment for dividing in half will be. Its midpoint is 0.75. In it, the value of the function is 0.226. We take for consideration the segment and its midpoint, which is located at the point 0.625. Calculate the value of g(x) to 0.625. It is equal to -0.11, i.e. negative. Based on this result, we choose the segment . 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 using Newton's 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 a 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) vanishes, i.e.

Substitute x = x n+1 and set y to zero.

Then the tangent looks like this:

Example 2

Let's try to use classical method Newton's tangents and find a solution to some non-linear equation that is difficult or impossible to find analytically.

Let it be required to reveal 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 a polynomial of odd degree must cross the OX axis at least once, i.e., there is no reason to doubt the existence of roots.

Before solving our example using the tangent method, we plot f (x) \u003d x 3 + 4x - 3 point by point. This is very easy to do, for example, using an Excel spreadsheet. From the resulting graph, it will be seen that it intersects with the OX axis and the function y \u003d x 3 + 4x - 3 monotonically increases. We can be sure that the equation x 3 + 4x - 3 = 0 has a solution and it is unique.

Algorithm

Any solution of equations by the tangent method begins with the calculation of f "(x). We have:

Then the second derivative will look like x * 6.

Using these expressions, we can write a formula for identifying the roots of the equation using the tangent method in the form:

Next, it is required to choose an initial approximation, i.e., to determine which point to consider as the starting point (rev. x 0) for the iterative process. We consider the ends of the segment. The one for which the condition of the function and its 2nd derivative at x 0 is true is suitable for us. As you can see, when substituting x 0 = 0, it is violated, but x 0 = 1 is quite suitable.

then if we are interested in the solution by the method of tangents with accuracy e, then the value of x n can be considered as satisfying the requirements of the problem, provided that the inequality |f(x n) / f’(x n)|< e.

At the first step of tangents we have:

• x 1 \u003d x 0 - (x 0 3 + 4x 0 - 3) / (3x 0 2 + 4) \u003d 1- 0.2857 \u003d 0.71429;
• since the condition is not met, we go further;
• we get a new value for x 2 , which is equal to 0.674;
• we 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.

Tangent Method in Excel

You can solve the previous example much easier and faster if you do not make calculations manually (on a calculator), but use the capabilities of a spreadsheet processor from Microsoft.

To do this, in Excel, you need to create new page and fill its cells with the following formulas:

• in C7 we write "= POWER (B7; 3) + 4 * B7 - 3";
• in D7 we enter "= 4 + 3 * DEGREE (B7; 2)";
• in E7 we write "= (POWER (B7; 3) - 3 + 4 * B7) / (3 * POWER (B7; 2) + 4)";
• in D7 we enter the expression "= B7 - E7";
• in B8 we enter the formula-condition “= IF (E7< 0,001;"Завершение итераций"; D7)».

In a specific task, already in cell B10, the inscription “Completion of iterations” will appear, and for solving the problem you will need to take the number written in the cell located one line above. For it, you can also select a separate “stretchable” column by entering a conditional formula there, according to which the result will be written there if the content in one or another cell of column B takes the form “Completion of iterations”.

Implementation in Pascal

Let's try to get the solution of the non-linear equation y = x 4 - 4 - 2 * x using the tangent method in Pascal.

We use an auxiliary function that will help to carry out an approximate calculation f "(x) \u003d (f (x + delta) - f (x)) / delta. As a condition for completing the iterative process, we will choose the fulfillment of the inequality | x 0 -x 1 |< некого малого числа. В Паскале его запишем, как abs(x0 - x1)<= epsilon.

The program is remarkable 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 as successive approximations to the desired root for f(x)=0, the values ​​​​of the intersection points of the chord with the abscissas of the end points a and b with OX are taken, denoted as x 1 , ..., x n . We have:

For the point where the chord intersects with the OX axis, the expression will be written as:

Let the second derivative be positive for x £ (the opposite case is reduced to the one under consideration if we write f(x) = 0). In this case, the graph y \u003d f (x) is a curve convex at the bottom and located below the chord AB. There can be 2 cases: when the function is positive at point a or it is negative at point b.

In the first case, we choose the end a as the fixed one, and take the point b for x 0. Then successive approximations according to the formula presented above form a sequence that decreases monotonically.

In the second case, the end b is fixed at x 0 = a. The x values ​​obtained at each iteration step form a sequence that is monotonically increasing.

Thus, we can state that:

• fixed in the method of chords is that end of the segment where the signs of the function and its second derivative do not coincide;
• approximations for the root x - x m - lie from it on the side where f (x) has a sign that does not coincide with the sign of f "" (x).

Iterations can be continued until the conditions for the proximity of the roots are satisfied at this and the previous iteration step modulo abs(x m - x m - 1)< e.

Modified method

The combined method of chords and tangents allows you to establish the roots of the equation, approaching them from different sides. Such a value, at which the f(x) graph intersects OX, allows you to refine the solution much faster than using each of the methods separately.

Suppose we need to find the roots f(x)=0 if they exist on . You can use 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 that the first and second derivatives have different signs at a particular point x.

Under such conditions, the solution of nonlinear equations by the tangent method allows finding a root with an excess if x 0 =b, and the method using chords at a fixed end b leads to finding an approximate root with a disadvantage.

Formulas used:

Now the desired root x must be sought in the interval. At the next step, you need to apply the combined method already to this segment. Proceeding like this, we get formulas of the form:

If there is a difference in sign between the first and second derivatives, then, arguing in a similar way, to refine the root, we obtain the following recursive formulas:

As a condition, the estimated inequality | b n +1 - a n +1 |< e. Иными словами, на практике приходится находить решение при помощи двух методов, но на каждом шаге требуется выяснять, насколько полученные результаты близки друг другу.

If the above inequality is true, then a point is taken as the root of the nonlinear equation on a given interval, which is exactly in the middle between the solutions found at a particular iteration step.

The combined method is easily implemented in the TURBO PASCAL environment. With a strong desire, you can try to carry out all the calculations using the tabular method in the Excel program.

In the latter case, several columns are selected for solving the problem using chords and separately for the method proposed by Isaac Newton.

In this case, each line is used to record calculations at a specific iterative step for two methods. Then, in the left part of the solution area, on the active working page, a column is highlighted in which the result of calculating the module of the difference in the values ​​of the next iteration step for each of the methods is entered. Another one can be used to enter the results of calculations according to the calculation formula of the logical construction "IF", used to find out whether the condition is met or not.

Now you know how to solve complex equations. The tangent method, as you have already seen, 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 using formulas.