Theory of nonlinear equations and the method of bisection.

Half division method

We believe that separating the roots of the equation f(x) = 0 is also carried out on the interval [ a, b] there is one root that needs to be refined with an error of ε. We take the middle of this segment as the initial approximation of the root: c 0= (a+ b) / 2 (Fig. 4):

Rice. 4. Half division method.

Then we examine the value of the function f(x) at the ends of the segments [ a, c 0] And [ c 0, b] . That one of the segments at the ends of which f(x) takes the meaning of different signs, contains the desired root; therefore we accept it as a new segment [ a 1, b 1] (in Fig. 4 this is the segment [ a, c 0]). The second half of the segment [ a, b], on which f(x) does not change sign, discard. As the next approximation of the root we take the middle of the new segment
c 1= (a 1+ b 1) / 2 etc. Thus, k-th approximation is calculated as

After each iteration, the segment on which the root is located is halved, and after k iterations in 2 k once:

The iterative process should be stopped when the specified accuracy is achieved, i.e. when the condition is met |x 0 – c k |< ε

Since the root x 0 belongs to the segment [ a k, b k], A c k is the middle of this segment, then the value |x 0 – c k | will always be less than half the length from cutting [ a k, b k] (see Fig. 4):

Therefore, the condition |x 0 – c k |< ε will be executed if

| b k – a k |< 2ε

Thus, the iterative process must be continued until the condition is met | b k – a k |< 2ε .

Unlike most other refinement methods, the bisection method always converges, i.e. has unconditional convergence. In addition, it is extremely simple, since it only requires calculating the values of the function f(x) and, therefore, can be used to solve any equations.

However, the halving method is quite slow. With each step, the error of the approximate value decreases by half, i.e.

Therefore, this method is a method with linear convergence.

Note. The half division method does not require knowledge of additional information about the function over the entire interval [ a, b]. For example, the function is not required to be differentiable. Even for discontinuous functions, the considered method has guaranteed convergence. If there are several roots of the equation on this interval, one of the roots will definitely be found.

Chord method

The method under consideration, just like the method of halves, is intended to clarify the root on the interval [ a, b f(x) takes values of different signs. Unlike the method of halves, we take the next approximation not in the middle of the segment, but at the point x, where a straight line (chord) drawn through the points intersects the x-axis A And IN(Fig. 5).

Rice. 5. Chord method.

Let us write down the equation of the line passing through the points A And IN:

For the point of intersection of the straight line with the abscissa axis ( x= x 0, y= 0) we get the equation

As a new interval for continuing the iterative process, we select one of the two [ a, x 0] And [ x 0 , b], at the ends of which the function f(x) takes values of different signs. For the case under consideration (Fig. 5), we select the segment [ a, x 0], because
f(a) × f(x 0)< 0 . The next iteration is to define a new approximation x 1 as the intersection points of a chord AB 1 with the x-axis, etc.

We finish the process of refining the root when the distance between successive approximations becomes less than the specified accuracy, i.e.

x k +1 – x k< ε

Note. The chord method and the half division method are very similar. Moreover, the second of them in some cases gives faster convergence of the iterative process. Both methods do not require knowledge of additional information about the function over the entire interval [ a, b]. For example, the function is not required to be differentiable. Even for discontinuous functions, the methods considered have guaranteed convergence.

Newton's method (tangent method)

Newton's method is also intended to refine the root on the interval [ a, b], at the ends of which the function f(x) takes values of different signs. But this method uses additional information about the function f(x). As a result, it has faster convergence, but at the same time, it is applicable to a narrower class of functions, and its convergence is not always guaranteed.

When separating the roots of a function, it should be taken into account that the application of Newton's method requires that the function be monotonic and twice differentiable, with the second derivative f''(x) should not change sign on this interval.

The convergence of the iteration sequence obtained in Newton’s method depends on the choice of the initial approximation x 0. In general, if the interval [ a, b] containing the root, and it is known that the function f(x) is monotonic on this interval, then as an initial approximation x 0 you can select that boundary of the segment [ a, b], where the signs of the function coincide f(x) and second derivative f''(x). This choice of initial approximation guarantees the convergence of Newton's method, provided that the function is monotonic on the root localization segment.

Let us know the initial approximation to the root x 0. Let us draw a tangent to the curve at this point y= f(x) (Fig. 6). This tangent will intersect the x-axis at a point that we will consider as the next approximation.

Laboratory work

NUMERICAL FINDING OF AN ISOLATED ROOT OF A NONLINEAR EQUATION

Solving equations - algebraic or transcendental - is one of the essential problems of applied analysis, the need for which arises in numerous and diverse sections of physics, mechanics, technology and other fields.

Let the equation be given

f (x) = 0. (1)

Any number X*, inverting the function f(x) to zero, i.e. one in which f(X*) = 0, is called the root of equation (1) or the zero of the function f(x).

The problem of numerically finding the real roots of equation (1) usually consists of approximately finding the roots, i.e. finding sufficiently small neighborhoods of the region under consideration, which contains one root value and, further, calculating the roots with a given degree of accuracy.

Function f(x) is continuous on the interval [ a, b] together with its 1st and 2nd order derivatives;
Values f(x) at the ends of the segment have different signs ( f(a) * f(b) < 0).

3. First and second derivatives f"(x) And f ""(x) retain a certain sign throughout the entire segment.

Conditions 1) and 2) guarantee that on the interval [ a, b] there is at least one root, and from 3) it follows that f(x) is monotonic on this interval and therefore the root will be unique.

The problem of finding the root of an equation f(x) = 0 by the iterative method consists of two stages:

1. root separation- finding an approximate value of the root or a segment containing it;

2. refinement of approximate roots- bringing them to a given degree of accuracy.

The process of root separation begins with establishing the signs of the function f(x) in the boundary x=a And x=b points in the region of its existence.

Example 1 . Separate the roots of the equation:

x 3 – 6x + 2 = 0 (2)

Let's make an approximate diagram:

X	- ∞	- 3	- 1				+ ∞
f(x)	–	–	+	+	–	+	+

Consequently, equation (2) has three real roots lying in the intervals [-3, -1], and .

Approximate values of the roots ( initial approximations) can also be known from the physical meaning of the problem, from solving a similar problem with different initial data, or can be found graphically.

Common in engineering practice graphic method determination of approximate roots.

Taking into account that the real roots of equation (1) are the intersection points of the graph of the function f(x) with the x-axis, it is enough to plot the function f(x) and mark the intersection points f(x)with axle Oh, or mark on the axis Oh segments containing one root.

Let the root of equation (1) be isolated on the segment [ a, b]. Iterative process of refining the initial approximation X 0 to an exact solution consists in sequentially obtaining a subsequent approximation from the previous one(s). Each such step is called iteration. The use of a particular method depends on the available initial approximation X 0 to the root, existence and smoothness of derivatives of the function f(x). As a result of iterations, a sequence of approximate root values is found X 1 , X 2 , ..., x n. If these values with increasing number of iterations n approach the true value of the root, then we say that the iterative process converges.

In iterative methods, it is important to choose the end-of-counting criterion. If the function f(x) in the region under consideration changes slowly, i.e. derivative in absolute value is less than unity, then the iterative process should be completed when the condition is met

| x k +1 – x k |< ε ,

Where x k, x k+1 – successive approaches to the root, ε > 0 – specified accuracy of the end of the iterative process. If the function changes quickly, i.e.

| f´(x) | ≥ 1, then the iterative process should be completed when the condition is met

| f(x k) | < ε .

Half division method

This method is one of the simplest iterative methods for calculating the real root of equation (1) on the interval [ α , β ]. It is used when f(x) is continuous on [ α , β ] and at the ends of this segment takes on values of different signs, i.e.

f(α )f(β ) < 0.

Computational scheme of the method. Segment [ α , β ] is divided in half and if f≠ 0, then choose that half , , at the ends of which the function f(x) takes values of different signs (the root is in it). The resulting segment is again divided in half and the described steps are repeated until the root is obtained with the specified accuracy of the iterative process. The process ends when the condition is met

| x k +1 – x k |< ε .

Number of iterations k in the half division method is determined by the formula

k≈ .

Example 1. Use the half division method to calculate the root of the equation

X 3 + 3X 2 – 1 = 0 (2)

with an accuracy of 0.01 on the segment.

We check the conditions for applicability of the method. Function f(x) is a polynomial of the third degree (continuous) and f(0)f(1) < 0.

We sequentially calculate approximations to the root and check them for accuracy:

x 0 = 0		f(0)= – 1	[ –, + ]
x 1 = 1	\|0 – 1\| > 0,01	f(1)=3
x 2 = 0,5	\|1 – 0,5\|> 0,01	f(0,5)= – 0,125
x 3 = 0,75	\|0,5 – 0,75\|> 0,01	f(0,75)≈1,109
x 4 = 0,625	\|0,5 – 0,625\|> 0,01	f(0,625)≈0,416
x 5 = 0,5625	\|0,5 – 0,5625\|> 0,01	f(0,5625)≈0,127
x 6 = 0,53125	\|0,5 – 0,53125\|> 0,01	f(0,53125)≈ – 0,0034
x 7 = 0,546875	\|0,53125 – 0,546875\|> 0,01	f(0, 546875)≈0,0608
x 8 = 0,5390625	\|0,53125 – 0,5390625\|≤ 0,01	f(0, 5390625)≈0,0284

Let us take as the refined value of the root the value

Half division method(other names: bisection method, dichotomy method) to solve the equation f(x) = 0 is as follows. Let it be known that the function is continuous and takes on the ends of the segment
[a, b] values of different signs, then the root is contained in the interval ( a, b). Let's divide the interval into two halves and then we will consider the half at the ends of which the function takes values of different signs. We again divide this new segment into two equal parts and select the one that contains the root. This process continues until the length of the next segment becomes less than the required error value. A more rigorous presentation of the algorithm for the bisection method:

1) Let's calculate x = (a+ b)/2; let's calculate f(x);

2) If f(x) = 0, then go to step 5;

3) If f(x)∙f(a) < 0, то b = x, otherwise a = x;

4) If | b – a| > ε, go to point 1;

5) Output the value x;

Example 2.4. Using the bisection method, refine the root of the equation ( x– 1) 3 = 0, belonging to the segment .

Solution in the program Excel:

1) In cells A 1:F 4 we introduce the notation, initial values and formulas, as shown in Table 2.3.

2) Copy each formula into the lower cells with a fill marker up to the tenth line, i.e. B 4 - up to B 10, C 4 - up to C 10, D 3 - up to D 10, E 4 - up to E 10, F 3 - up to F 10.

Table 2.3

A	B	C	D	E	F
	f(a)=	=(1-B3)^3
k	a	x	f(x)	b	b-a
	0,95	=(B3+E3)/2	=(1-C3)^3	1,1	=E3-B3
	=IF(D3=0,C3; IF(C$1*D3<0;B3;C3))			=IF(C$1*D3>0; E3;C3)

The calculation results are given in table. 2.4. In column F checking the interval length values b – a. If the value is less than 0.01, then an approximate value of the root with a specified error is found in this line. It took 5 iterations to achieve the required accuracy. The approximate value of the root with an accuracy of 0.01 after rounding to three decimal places is 1.0015625 ≈ 1.00.

Table 2.4

A	B	C	D	E	F
	f(a)=	0,000125
k	a	x	f(x)	b	b-a
	0,95	1,025	-2E-05	1,1	0,15
	0,95	0,9875	2E-06	1,025	0,075
	0,9875	1,00625	-2E-07	1,025	0,0375
	0,9875	0,996875	3.1E-08	1,00625	0,0187
	0,996875	1,0015625	-4E-09	1,00625	0,0094
	0,996875	0,9992188	4.8E-10	1,0015625	0,0047
	0,99921875	1,0003906	-6E-11	1,0015625	0,0023
	0,99921875	0,9998047	7.5E-12	1,000390625	0,0012

The above algorithm takes into account the possible case of “hitting the root”, i.e. equality f(x) zero at the next stage. If in example 2.3 we take the segment , then at the very first step we get to the root x= 1. Indeed, let’s write in the cell B 3 value 0.9. Then the results table will take the form 2.5 (only 2 iterations are given).

Table 2.5

A	B	C	D	E	F
	f(a)=	0,001
k	a	x	f(x)	b	b-a
	0,9			1,1	0,2

Let's create it in the program Excel custom functions f(x) and bisect(a, b, eps) for solving equations using the bisect method using the built-in language Visual Basic. Their descriptions are given below:

Function f(Byval x)

Function bisect(a, b, eps)

1 x = (a + b) / 2

If f(x) = 0 Then GoTo 5

If f(x) * f(a)< 0 Then

If Abs(a - b) > eps Then GoTo 1

The function f(x) determines the left side of the equation, and the function
bisect(a, b, eps) calculates the root of the equation using the bisect method f(x) = 0. Note that the function bisect(a, b, eps) uses an access to the function f(x). Here is the algorithm for creating a custom function:

1) Execute the menu command “Tools - Macro - Editor Visual Basic" The window “ Microsoft Visual Basic" If in this program file Excel macros or user functions or procedures have not yet been created, this window will look like that shown in Fig. 2.4.

2) Execute the menu command “Insert - Module” and enter the texts of the program functions, as shown in Fig. 2.5.

Now in the program sheet cells Excel You can use the created functions in formulas. For example, let's enter into a cell D 18 formula

Bisect(0.95;1;0.00001),

then we get the value 0.999993896.

To solve another equation (with a different left side) you need to go to the editor window using the command “Tools - Macro - Editor Visual Basic” and simply rewrite the description of the function f(x). For example, let’s find, with an accuracy of 0.001, the root of the equation sin5 x + x 2 – 1 = 0, belonging to the interval (0.4; 0.5). To do this, let's change the description of the function

for a new description

f = Sin(5 * x) + x^2 - 1

Then in the cell D 18 we get the value 0.441009521 (compare this result with the value of the root of the interval (0.4; 0.5) found in example 2.3!).

To solve an equation using the half division method in the program Mathcad let's create a subroutine function bisec(f, a, b, ε), where:

f- function name corresponding to the left side of the equation f(x) = 0;

a, b- left and right ends of the segment [ a, b];

ε - accuracy of the approximate value of the root.

Solution of the example in the program Mathcad:

1) Launch the program Mathcad. Let us introduce the definition of the function bisec(f, a, b, ε). To do this, using the keyboard and the “Greek Symbols” toolbar, type bisec(f, a, b, ε):=. After the assignment sign “:=” on the “Programming” toolbar, use the mouse pointer to left-click “Add line”. A vertical line will appear after the assignment sign. Next, enter the program text shown below, using the “Programming” toolbar to enter the “←” sign, the loop operator while, operator break and conditional operator if otherwise.

2) Let us introduce the definition of the function f(x):=sin(5*x)+x^2–1, and then calculate the value of the root using the function bisec at given values:
bisec(f, –0.8,–0.7,0.0001)=. After the “=” sign, the root value calculated by the program –0.7266601563 will automatically appear. Let's calculate the remaining roots in the same way.

Below is the sheet Mathcad with function definition bisec(f, a, b, ε) and calculations:

Let's give a program in the language C++ to solve the equation f(x) = 0 by the halving method:

#include

double f(double x);

typedef double (*PF)(double);

double bisec(PF f,double a, double b,double eps);

double a, b, x, eps;PF pf;

cout<< "\n a = "; cin >>a;

cout<< "\n b = "; cin >>b;

cout<< "\n eps = "; cin >> eps;

x = bisec(pf,a,b,eps); cout<< "\n x = " << x;

cout<< "\n Press any key & Enter "; cin >>a;

double f(double x)(

r = sin(5*x)+x*x-1;

double bisec(PF f, double a, double b,double eps)(

do( x = (a + b)/2;

if (f(x) == 0) break;

if (f(x)*f(a)<0) b = x;

)while (fabs(b-a) > eps);

Function in the program f(x) is defined to solve the equation

sin5 x + x 2 – 1 = 0

from example 2.3. The result of the program for determining the root of the interval (0.4; 0.5) with an accuracy of 0.00001 is presented below (computer screen):

Press any key & Enter

The last line is needed to organize a pause to view the result.

Let f(x) – continuous function on [ a; b], .

Newton's method (tangent method)

Let f(x) is a twice continuously differentiable function on the interval [ a; b],
,
And
do not change the sign to [ a; b].

Let us denote by that end of the segment where the signs
And
match. Successive approximations to the exact root c find by formula

For
.

Then
is the exact root of equation (1).

The computing process is usually stopped when
turns out to be less than the specified accuracy ε . However, this condition cannot strictly guarantee that the specified accuracy is achieved. For complete assurance, you can perform an accuracy check as stated at the beginning of this section. If accuracy is not achieved, then you need to repeat the iterations several more times.

Secant method

Let there be some initial approximation . We get one more point using the formula
, Where h– a small number. We will assume that we have completed several steps of the method, and at this point we have two successive approximations And
to the exact root (at the initial stage this is And ). Then we find the next approximation using the formula

The process stops according to the same criterion as in Newton's method.

Iteration method

In the iteration method, the original equation (1) is transformed into the equivalent equation
. The initial approximation is selected . Each subsequent approximation is obtained by the formula
,
The process stops according to the same criterion as in Newton's method. The method will converge, i.e. limit is equal to the exact value of the root if the inequality holds in the neighborhood of the root
and the initial approximation is quite close to the root.

Advantages and disadvantages of methods

The bisection method requires the root to be separated, and the function must be evaluated many times to achieve high accuracy. Achieving the specified accuracy in this method is guaranteed.

Newton's method has very fast convergence (quadratic convergence), i.e.

Where c– exact value of the root; M– some constant depending on the function. Roughly speaking, starting from a certain iteration, the number of correct decimal places will double at each iteration.

To guarantee the convergence of Newton's method, quite a few conditions must be met. Generally speaking, you can start calculations using Newton’s method without checking these conditions, but then convergence may not be observed.

The secant method provides a convergence rate for smooth functions that is close to the convergence rate of Newton's method. It does not require calculating the derivative of a function. If the starting point is taken far from the root, then there may be no convergence.

The iteration method gives a convergence rate significantly lower than Newton's method. If there is convergence, the estimate applies
, Where
– numbers,
,
;c– exact value of the root. Quantities M, q depend on the function and do not depend on the iteration number. If
is close to 1, then q is also close to 1 and the convergence of the method will be slow. Calculation using the iteration method can be started without checking the conditions on
And . In this case, the process may become divergent, and then the answer will not be received.

There are many methods for finding the roots of a nonlinear equation other than those listed. In MATHCAD, the root function is in the format
uses the secant method, and if it does not lead to the desired results, then the Muller method. In the latter, unlike the secant method, at each step two additional points are taken, the graph of the function is replaced by a parabola passing through three points, and the point of intersection of the parabola with the axis is taken as the next approximation Ox. In the root function in the format root( f(x), x, a, b) Ridder and Brent methods are used. To find the roots of a polynomial in MATHCAD, the Laguerre method is used.

Half division method (method also known as Bolzano method or dichotomy method) one from methods for solving nonlinear equations and is based on the sequential narrowing of the interval containing the only root of the equation. The iterative process is carried out until the specified accuracy is achieved.

Let an equation be given and a segment defined such that this segment contains one single root of the equation. Then at the ends of the given segment the function has values opposite in sign: . The opposite signs of the function values at the ends of a segment can be determined in many ways. One of many of these methods is to multiply the values of the function at the ends of the segment and determine the sign of the product by comparing the result of the multiplication with zero:

The segment is called the initial uncertainty interval because it is known that the root belongs to it, but its location is not determined with the required accuracy.

The procedure for clarifying the position of the root consists of constructing a sequence of segments nested within each other, each of which contains the root of the equation. To do this, the middle of the current uncertainty interval , , is found, and the one at the ends of which the function has different signs is selected as the next uncertainty interval from two possible ones.

The process ends when the length of the current uncertainty interval becomes less than a specified value that specifies the accuracy of finding the root. The middle of the last uncertainty interval is taken as an approximate value of the root.

The method has linear but unconditional convergence, and its error for each iteration is reduced by half:

From this relationship we can estimate the number of iterations k to achieve a given accuracy:

From the resulting formula we can conclude that to achieve accuracy from the length of the initial gap, it is necessary to perform approximately ten iterations.

The advantages of the method also include the fact that it allows you to find the simple root of the equation of any continuous functions for any values such that .

The disadvantages of the method are that it does not generalize to systems of nonlinear equations and cannot be used to find roots of even multiplicity.

Algorithm for finding the root of a nonlinear equation using the bisection method.

1. Find the initial uncertainty interval using one of the root separation methods.Set the calculation error (small positive number ) and the initial iteration step () .

2. Find the middle of the current uncertainty interval:

3. It is necessary to find the value of the function at points , and . Next, you need to check two conditions:

If the condition is met , then the desired root is located inside the left segment put, ;

If the condition is met , then the desired root is located inside the right segment accept , .

As a result, a new uncertainty interval is found, on which the desired root of the equation is located:

4. We check the new segment for the specified accuracy, in the case of:

If the length of the new segment is less than the specified accuracy, then the iterative process ends. The approximate value of the root is determined by the formula:

If the length of the new segment does not reach the required accuracy, then it is necessary to continue the iterative process and go to step 2 of the algorithm under consideration.