Root refinement methods

After the interval containing the root is found, apply iterative methods refinement of the root with a given accuracy.

Method half division (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). We 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 choose from them 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 exposition of the bisection method algorithm:

1) Calculate x = (a+ b)/2; compute 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 value x;

Example 2.4. Refine by the bisection method with an accuracy of 0.01 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) We copy each formula into the lower cells with a fill marker up to the tenth line, i.e. B 4 - before B 10, C 4 - before C 10, D 3 - before D 10, E 4 - before E 10, F 3 - before 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 interval length values b – a. If the value is less than 0.01, then an approximate value of the root with a given error was found in this line. It took 5 iterations to achieve the required accuracy. The approximate value of the root to within 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) to zero at the next stage. If in example 2.3 we take the segment , then at the first step we get to the root x= 1. Indeed, we write in the cell B 3 value 0.9. Then the table of results 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 in the program excel user-defined functions f(x) and bisect(a, b, eps) to solve the equation by the half division 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 Go To 5

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

If Abs(a - b) > eps Then Go To 1

The function f(x) defines the left side of the equation, and the function
bisect(a, b, eps) bisects the root of the equation f(x) = 0. Note that the function bisect(a, b, eps) uses a call to the function f(x). Here is an algorithm for creating a user-defined function:

1) Execute the menu command "Tools - Macro - Editor Visual Basic". The window " Microsoft Visual Basic". If in given file programs excel macros or user-defined functions or procedures have not yet been created, this window will look like the one shown in Figure 2.4.

2) Execute the menu command "Insert - Module" and enter the texts of the function programs, as shown in Figure 2.5.

Now in the cells of the program sheet excel you can use the created functions in formulas. For example, let's enter in 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, change the description of the function

to 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 the equation by the method of half division in the program Mathcad create a function subroutine 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];

ε is the accuracy of the approximate value of the root.

Solution of the example in the program Mathcad:

1) Run the program Mathcad. We introduce the definition of the function bisec(f, a, b, ε). To do this, using the keyboard and the Greek Symbols toolbar, we type bisec(f, a, b, ε):=. After the assignment sign ":=" on the "Programming" toolbar, click the left button "Add line" with the mouse pointer. A vertical line will appear after the assignment sign. Next, enter the text of the program, which is shown below, using the "Programming" toolbar to enter the "←" sign, the loop operator while, operator break and conditional operator if otherwise.

2) We 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 setpoints:
bisec(f, –0.8,–0.7,0.0001)=. After the “=” sign, the root value calculated by the program will automatically appear -0.7266601563. We calculate the rest of the roots in the same way.

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

We present the program in the language C++ to solve the equation f(x) = 0 by the bisection method:

#include

#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);

The 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 pause to view the result.

Most algorithms for finding the roots of an equation make it possible to find, as a rule, only one root on a given interval. The most well-known methods include methods:

• Method simple iterations
• Newton's method
• Modified Newton's Method
• Rybakov's method
• dichotomy method
• Cascade Approximation Method
• chord method
• Combined secant-chord method
• Aitkin–Steffenson method
• The method of inverse quadratic interpolation - extrapolation, etc.

The number of methods for finding roots is large, as well as various sorting algorithms.

I have considered the dichotomy method taken from the MM6.PDF file. See the example code. It is composed using the old but beloved Go TO operator. From the point of view of structured programming, the use of such an operator is unacceptable, but effective. In the literature, this note is accompanied by several references to specially found materials, including the reference book of Dyakonov's algorithms. Once upon a time, it was my desktop. Old versions of BASIC are full of Go TO statements. Older versions of BASIC also use the LET assignment operator.

There are many versions of BASIC. I once had to often translate programs from one version to another. And for the first time I met one of the versions of BASIC in the year 1980 at the Institute of Geophysics, where we went to visit with a friend of his brother. He was engaged in the method of magnetic nuclear resonance. All calculations for processing the results of experiments were carried out using minicomputers of foreign production and in the BASIC language. Then this language appeared on Iskra-226, which was quite powerful at that time, and on the famous BK-10, which has been used since the mid-80s in classrooms in schools. In 1983-1984 in Kharkov I saw the first PC. She had only 2 floppy drives for 2 different types of floppy disks and a memory capacity of about 560 MB, and Forth was the main programming language. This is the language of stacks, which has been successfully used in the control of radio telescopes. In this language, graphics were simply implemented.

All the main sorting algorithms and computational methods were implemented in most cases for the ALGOL and FORTRAN languages ​​in the mid-50s.

Now for an example. There are solutions to 2 different equations. The first equation is X*X-5*SIN(X). Obviously, the sine changes from -1 to +1. Therefore 5*sine changes from -5 to +5. The X square grows much faster. Therefore, it can be assumed that the roots will be in the range around 0 or 2 for X values ​​around. It is better to plot the graph first to analyze the range in which the roots are located. The graph shows that there should be 2 roots. In the example, we found only one of the roots, because we set one of the intervals.

In the second equation, X*X*X-X+1, we see a cubic parabola with a root near -1.

You can replace your equations in a macro. Is it possible to write programs without GOTO statements? - Of course you can.

a

Question: Finding the roots of an equation by dividing a segment in half

Good afternoon, what's wrong with the 3rd root, it doesn't want to be displayed. Above - 3 roots through the selection of the parameter. Below - by the method of half division. Rounding 0.001 Equation x^3-2*x^2-x+2 Can anyone correct or give useful advice, what is wrong?

Answer: furymaxim, brackets are missing

Question: Playfair decryption in MS Excel

Please tell me how to make a decoder in EXCEL using formulas. Or tell me which formula can be used to generate an alphabet

Answer: In cell A1

Code

1 = CHAR(192 + STRING() - 1 )

And stretch down

Question: Excel spreadsheet file slows down

Good day, dear colleagues!
I really need your help, I have already tried all the methods found and known to me to reduce the size of the file. It seems to have cleaned out everything superfluous there.
Despite this, when working with the table, there are brakes and freezes, and they are variable but stable (sometimes it slows down, sometimes it does not slow down).
It seems to me that this is probably due to the drop-down list with photos, I noticed that as the drop-down lists with photos increase, the brakes also increase. But strangely, the tables are all small, the gallery with pictures is also not big.

Answer: Problem solved! Just installed excel 2016 for mac - no lag at all, so far everything works fine, but not sure if I will not run into this again!
Nevertheless, the problem is relevant, because. the solution is not through installing another version of excel, perhaps someone else will come in handy
p.s. previous version of excel was 2011 for mac

Q: Office 2007 how to install excel 2010

Hi all.
maybe the thread title doesn't really convey the point...
I have win xp sp3 office 2007 and excel 2007.
in excel either 2010 or 2013 there is a chart function in the form of powerview maps of countries or continents or whatever. There are still bin cards used.
Are there any add-ons for excel2007 so that such diagrams can be. if not, which excel has this function and is it possible to install 2 excel on 1 computer. for example 2007 and 2010 on win xp sp3 if the function of charts with country maps is in 2010????
thank.

Answer: so and in 2010 excel it is?? and if so how to install excel 2010 without deleting my office 2007???

Added after 3 hours 10 minutes
schA looked at similar topics. found about libreoffice. a program such as office is only free. MB does anyone have a map of the Republic of Belarus for this program????. there is a geoOOo extension.

Question: Getting a selection from Excel

I need to create a PowerPoint presentation based on data from an Excel file.

Haven't worked with either one before. So check the algorithm (outline):
I get the necessary selections using queries,
I associate the results of the selections with the template (I have not yet read how a presentation is created programmatically)
I'm actually creating a presentation.
And I write all this in a macro.

1. Is the sequence correct?
2. How can I work with the data received using requests? Write them down temporarily; the result of each request on a separate sheet, and after creating the presentation file, close the Excel file WITHOUT CHANGES? Or somehow differently?
3. How to write such a request correctly?
My sketch is not working:

Writing query results from the first sheet to the second.
4. How to run this query

Visual Basic Code

1 DoCmd.RunSQL strSQL

Something like this?

Added after 2 hours 42 minutes
Or is this possible only through a temporary Access database?

Answer: Do you mean here? To the forum? - Please ... It's not about the data, but about the requests (processing methods). In Access I do it, in Excel I can't. For example, calculate sales for 3 manufacturers with the largest sales (TOP 3), and summarize the rest. As far as I understand, this cannot be automated... By hand - Yes, you can do it.

Question: How to add Outlook attachment names to Excel and then save them in a specified folder

Good afternoon to all Excel gurus.

Thanks to this forum, I managed to set up workflow in Excel (more precisely, registration of incoming and outgoing letters) in a more or less automated form.
The attached file contains the following main macros:
1. "First_MailSave" - ​​prescribes letters from the Outlook inbox
2. "Second_to_template" - returns the incoming number and outputs the data in a specific template (approved by the management in terms of readability)
3. "Completion_Print" - saves the template sheet in pdf format in the folder with the incoming number and starts printing.
Those. there is happiness, now the full processing of 10 letters takes 3-4 minutes, not 30-40.

Attachment handling issue:
1. How not to prescribe manually number of investments in the letter, but automatically with the output to cell E4 of the "data" sheet of the amount + 1 (the letter itself)
2. How to list all in the "Template" sheet in B5 attachments by name
3. What to add to the "Finish_Print" macro so that attachments were saved into the newly created folder with the letter itself.

All data is taken from the letter, but with the attachment I have not figured out how (see code)

Visual Basic Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 Sub First_MailSave() Application.EnableEvents = False Dim oOutlook As New Outlook.Application Dim oNamespace As Outlook.Namespace Dim myFolder As Outlook.Folder Dim myMail As Outlook.Items Dim myItem As Outlook.MailItem Dim r Set oNamespace = oOutlook.GetNamespace(" MAPI" ) "folder in Outlook where we save emails "if letters are needed from a subfolder, then it is written in the following form: Set myMail = myFolder.Items Cells.Clear Cells(3, 2) = "From" "Cells(1, 2) = "E-mail" "Cells(1, 3) = "To" Cells(3, 3) = "Subject" Cells(3, 1) = "Date" Cells(3, 4) = "Mail body" Cells(3, 5) = "Number of Pages" r = 4 For Each myItem In myMail On Error Resume Next Cells(r, 2) = myItem.SenderName " Cells(r, 3) = myItem.To Cells(r, 3) = myItem.Subject Cells(r, 1) = myItem.CreationTime Cells(r, 4) = myItem. Body On Error GoTo 0 r = r + 1 Next Application.EnableEvents = True "disable event handling end sub

Searches on the Internet all refer to macros for outlook, but I register and create the necessary directories in excel, respectively, all the variables in it.
On the one hand, I have three different questions, but it seems to me that it would be better to implement all three questions in one macro.

Best regards, Leo

Answer: The result is a complete and automated workflow.
To transfer letters with attachments to excel and acc. folders

Visual Basic Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Sub Ïåðâîå_MailSave() Application.EnableEvents = False Dim oOutlook As New Outlook.Application Dim oNamespace As Outlook.Namespace Dim myFolder As Outlook.Folder Dim myMail As Outlook.Items Dim myItem As Outlook.MailItem Dim r Set oNamespace = oOutlook .GetNamespace("MAPI") "GЇG*GЇGЄG* Gў Outlook, G®GІGЄGіG¤G* G±G®GµG°G*G*GїGҐG¬ GЇGЁG±GјG¬G* Set myFolder = oNamespace.GetDefaultFolder(olFolderInbox) "åñëè ГЇГЁГ±ГјГ¬Г* Г*ГіГ¦Г*Г» ГЁГ§ âëîæåГ*Г*îé ГЇГ*ГЇГЄГЁ, ГІГ® Г§Г*ГЇГЁГ±Г» GўG*GҐGІG±Gї Gў G±G«GҐG¤GіGѕG№GҐG¬ GўGЁG¤GҐ: ".Folders("webley").Folders("test") Set myMail = myFolder.Items destinationFolder = "E:\temp\test\Att\" Êîëè÷åñÏâî = 0 ÏîÈìåГ*Г*Г¬ = "" Cells.Clear Cells (3, 2) = "Cells(1, 2) = "E-mail" "Cells(1, 3) = "Êîìó" Cells(3, 3) = "Y'YYY*" Cells(3, 1) = "Y„Y*YY*" Cells(3, 4) = "G‘G®G¤GҐG°G¦G*G*GEGG" Cells(3, 5) = "GEG®G"-GўG® G±GІG°G*G*GЁG¶" Cells(3, 6) = "G‚G"G®G¦GҐG*GЁGї" r = 4 For Each myItem In myMail On Error Resume Next ""<<<<<<<<<<<<<<< 3 Гў îäГ*îì >>>>>>>>>>>>>> Set colAttachments = myItem.Attachments colAttachments = colAttachments.Count + 1 For Each objAttachment In colAttachments MkDir (destinationFolder & myItem.SenderName) destinationFolder1 = (destinationFolder & myItem.SenderName) objAttachment.SaveAsFile (destinationFolder "/" & objAttachment.Filename) ÏîÈìåГ*Г*Г¬ = ÏîÈìåГ*Г*Г¬ & objAttachment.Filename & "; " Next ""<<<<<<<<<<<<<<<>>>>>>>>>>>>>> Cells(r, 2) = myItem.SenderName " Cells(r, 2) = myItem.SenderEmailAddress" Cells(r, 3) = myItem.To Cells(r, 3) = myItem.Subject Cells(r, 1) = myItem.CreationTime Cells(r, 4) = myItem.Body Cells(r, 5) = GEG® G«ГЁГ·ГҐГ±ГІГўГ® Cells(r, 6) = ÏîÈìåГ*Г*Г¬ On Error GoTo 0 r = r + 1 Next Application.EnableEvents = True "îòêГ"ГѕГ·Г*ГҐГ¬ îáðГ*áîòêó ñîáÔòèÿ end sub

Answer: Strictly in book module ThisWorkbook(ThisBook) personal macro workbook Personal.xls(xlsb)

Visual Basic

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Private Declare Function LoadKeyboardLayout _ Lib "user32.dll" Alias ​​"LoadKeyboardLayoutA" (_ ByVal pwszKLID As String , _ ByVal flags As Long ) As Long Private WithEvents xlApp As Application Private Sub Workbook_Open() Set xlApp = Application End Sub Sub Private xlApp_WorkbookOpen( ByVal Wb As Excel.Workbook) If LCase(Wb.Name) = "workbookname.xls" Then LoadKeyboardLayout "00000409" , &H1 Else LoadKeyboardLayout "00000419" , &H1 End If End Sub

MINISTRY OF EDUCATION AND SCIENCE OF THE RUSSIAN FEDERATION

FEDERAL STATE BUDGET

EDUCATIONAL INSTITUTION

HIGHER PROFESSIONAL EDUCATION

«SAMARA STATE

ARCHITECTURAL AND CONSTRUCTION UNIVERSITY»

Department of Applied Mathematics and Computer Engineering

excelandMathcad

METHODOLOGICAL INSTRUCTIONS

for laboratory work

in the discipline "Computational mathematics"

Solution not linear equations inExcel andMathcad: Method. decree. / Comp. , - Samara: SGASU, 20p.

Methodical instructions are developed in accordance with the State educational standard for studying the discipline "Computational Mathematics".

The implementation of numerical methods for solving nonlinear equations and systems of equations in Excel and MathCad is considered. Variants of tasks for individual performance and questions for self-control and testing are given.

Designed for students of specialty 230201 - "Information systems and technologies" of all forms of education.

Reviewer Ph.D. n.

Ó , compilation, 2012

ã SGASU, 2012

1.2 Separation of roots
1.5 Chord method
1.6 Newton's method (tangents)
1.7 Combined method
1.8 Iteration method
2.2 Solving systems of nonlinear equations by Newton's method
3 Tasks for laboratory work
Laboratory No. 1. Root separation and standard tools for solving a nonlinear equation
Laboratory No. 2. Comparison of methods for refining the roots of a nonlinear equation
Laboratory No. 3. Solving systems of nonlinear equations
Laboratory No. 4. Programming methods for solving nonlinear equations and systems
4 Questions and tests for self-control

1 Solving a non-linear equation

1.1 General information about the solution of a nonlinear equation

As a rule, non-linear equations of general form f(x)=0 cannot be solved analytically. For practical problems, it suffices to find an approximate value x, which in a certain sense is close to the exact solution of the equation khtochn.

In most cases, the search for an approximate solution involves two stages. On the first stage separate roots, i.e., find such segments, inside which there is exactly one root. On the second stage clarify root on one of these segments, i.e., find its value with the required accuracy.

The achieved accuracy can be evaluated either “by function” (at the found point x, the function is sufficiently close to 0, i.e., the condition | f(x)|≤ef, where ef the required accuracy along the y-axis), or “by argument” (a sufficiently small segment was found [ a,b], inside which there is a root, i.e. | b–a|≤ex, where ex required accuracy on the x-axis).

1.2 Separation of roots

Root separation can be done by a combination graphic and analytical function research. Such a study is based on the Weierstrass theorem, according to which for a continuous on a segment [ a,b] functions f(x) and any number y, which meets the condition f(a)≤y≤f(b), there is a point on this segment x, in which the function is equal to y. Therefore, for a continuous function, it suffices to find a segment at the ends of which the function has different signs, and you can be sure that this segment has a root of the equation f(x)=0.

For a number of refinement methods, it is desirable that the segment found at the first stage contains only one equation root. This condition is satisfied if the function on the interval is monotonic. Monotonicity can be checked either by the graph of the function, or by the sign of the derivative.

Example Find up to integers all roots of the nonlinear equation y(x)=x3-10x+7=0 a) by constructing a table and b) by constructing a graph. Find the root of the equation on the selected segment using the "Parameter selection" and "Search for a solution" options.

Decision Let's create a table in Excel containing the arguments and values ​​of the function and build on it scatter plot . Figure 1 is a snapshot of the solution.

The graph shows that the equation has three roots belonging to the segments [-4, -3], and . These segments can also be identified by observing the change of signs of the function in the table. According to the constructed graph, we can conclude that on the indicated segments the function f(x) is monotone and, therefore, each of them contains only one root.

The same analysis can be performed in the Mathcad package. To do this, it is enough to type the definition of the function f(x) , using the assignment operator (:=) and natural conventional notation for mathematical operations and standard functions, set up a loop to change the argument, for example, and then display the table of function values ​​​​(located on the same line with commands x= f(x)= ) and graph. The cycle can be specified, for example, with the command x:=-5,-4.5…5 . The cycle step is formed by setting the initial and following values ​​of the variable, and before the final value of the variable, a semicolon is placed, which will be visually displayed on the screen as an ellipsis.

https://pandia.ru/text/78/157/images/image002_56.jpg" width="640" height="334">

Figure 1 - Table and graph for separating the roots of a non-linear equation

1.3 Refinement of roots using standard Excel and Mathcad tools

In all methods of refining the roots, it is necessary to set the initial approximation, which will then be refined. If the equation has several roots, one of them will be found depending on the chosen initial approximation. With an unsuccessfully chosen initial approximation, the solution may not be found. If, as a result of the first stage of calculations, a segment containing a single root of the equation has already been selected, any point of this segment can be taken as an initial approximation.

In Excel, to refine the values ​​of the roots, you can use the "Parameter selection" and "Search for a solution" options. An example of designing a solution is shown in Figures 2 and 3.

https://pandia.ru/text/78/157/images/image004_31.jpg" width="501" height="175 src=">

Figure 3 - The results of using the means of solving the equation inexcel

In Mathcad, to refine the roots of an equation, you can use the function root(….) or decision block. An example of using the root(...) function is shown in Figure 4, and a decision block in Figure 5. Note that in the decision block (after the block header Given) between the left and right sides of the equation should be bold equal sign(identities), which can be obtained by selecting from the corresponding tool palette, or by simultaneously pressing the key ctrl and = .

243" height="31">

Figure 5 - Solving the equation using the solve block inMathcad

As you can see, each standard tool finds a solution to the equation with a certain accuracy. This accuracy depends on the method used in the package and, to some extent, the settings of the package. Controlling the accuracy of the result here is quite difficult, and often impossible.

At the same time, it is very easy to build your own table or write a program that implements one of the root refinement methods. Here you can use the calculation accuracy criteria specified by the user. At the same time, an understanding of the calculation process is also achieved without relying on the principle of Mitrofanushka: "There is a driver, he will take you."

Below are some of the more common methods. Note the obvious point: for other equal conditions that method refinement of the roots will be more efficient, in which the result with the same error is found with smaller the number of function evaluations f(x)(this also achieves maximum accuracy at the same number function calculations).

1.4 Bisection method

In this method, at each step, the segment is divided into two equal parts. Then, the signs of the function at the ends of each of the two halves are compared (for example, by the sign of the product of the values ​​of the functions at the ends), the one that contains the solution is determined (the signs of the function at the ends must be different), and. narrow the segment, transferring its boundary to the found point ( a or b). The termination condition is the smallness of the segment containing the root (“accuracy in x”), or the proximity to 0 of the function value in the middle of the segment (“accuracy in y”). The solution of the equation is the middle of the segment found at the last step.

Example. Build a table to refine the root of the equation x3 –10 x+7=0 on the segment [-4, -3] by dividing the segment in half. Determine how many steps need to be taken by dividing the segment in half and what accuracy is achieved in this case. X, to achieve accuracy in y equal to 0.1; 0.01; 0.001.

Decision For solution, you can use spreadsheet processor Excel that allows you to automatically continue lines. At the first step, we enter the values ​​​​of the left and right ends of the selected initial segment into the table and calculate the value of the middle of the segment with=(a+b)/2, and then we introduce a formula for calculating the function at a point a (f(a)) and stretch (copy) it to calculate f(c) and f(b). In the last column we calculate the expression ( b-a)/2 characterizing the degree of calculation accuracy. All typed formulas can be copied to the second row of the table.

At the second step, you need to automate the process of finding that half of the segment that contains the root. To do this, use the logical function IF ( Menu: InsertFunctionBoolean). For the new left edge of the segment, we check the truth of the condition f(a)*f(c)>0, if it is true, then we take the number as the new value of the left end of the segment c a, c a. Similarly, for the new right edge of the segment, we check the truth of the condition f(c)* f(b)>0, if it is true, then we take the number as the new value of the right end of the segment c(because this condition shows that the root on the interval [ c, b] no), otherwise leave the value b.

The second line of the table can be continued (copied) for the required number of subsequent lines.

The iterative process ends when the next value in the last column becomes less than the specified accuracy ex. In this case, the value of the middle of the segment in the last approximation is taken as an approximate value of the desired root of the nonlinear equation. Figure 6 shows a snapshot of the solution. To build a similar process in Mathcad, you can use a form similar to that shown in Figure 7. The number of steps N can vary until the required accuracy is achieved in the results table. The table will automatically lengthen or shorten.

So, one of the three roots of the nonlinear equation x 3 – 10x+ 7=0 found with precision e=0.0001 is x= - 3.46686. As we can see, it really belongs to the segment [-4; -3].

https://pandia.ru/text/78/157/images/image018_6.jpg" width="563" height="552 src=">

Figure 7 - Refinement of the root by dividing the segment in half inMathcad

1.5 Chord method

In this method nonlinear function f(x) on the separated interval [ a, b] is replaced by a linear one - the equation of a chord, i.e., a straight line connecting the boundary points of the graph on the segment. The condition for the applicability of the method is the monotonicity of the function on the initial segment, which ensures the uniqueness of the root on this segment. The calculation by the chord method is similar to the calculation by the method of dividing the segment in half, but now at each step new point x inside the segment [ a, b] is calculated using any of the following formulas:

(x) > 0 ), or its right boundary: x0 = b(if f (b) f "(x)> 0). Calculation of a new approximation in the next step i+1 produced by the formula:

https://pandia.ru/text/78/157/images/image021_4.jpg" width="596" height="265 src=">

Figure 8 - Refinement of the root by the tangent method in Excel

Calculations in Mathcad are performed in a similar way. At the same time, a significant relief is provided by the presence in this package of an operator that automatically calculates the derivative of a function.

The most time-consuming element of Newton's calculations is the calculation of the derivative at each step.

Can be used under certain conditions simplified Newton's method, in which the derivative is calculated only once - at the starting point. In this case, a modified formula is used

.

Naturally, the simplified method, as a rule, requires more steps.

If the calculation of the derivative is associated with serious difficulties (for example, if the function is given not by an analytical expression, but by a program that calculates its values), it is used modified method Newton, called secant method. Here, the derivative is approximately calculated from the values ​​of the function at two consecutive points, that is, the formula is used

.

In the secant method, it is necessary to specify not one, but two starting points - x0 and x1 . Dot x1 usually given by a shift x0 to the other boundary of the segment by a small amount, for example, by 0.01.

1.7 Combined method

It can be shown that if on the initial segment of the function f(x) the signs of the first and second derivatives remain unchanged, then the methods of chords and Newton approach the root from different points. AT combined method uses both algorithms at the same time to increase efficiency at each step. In this case, the interval containing the root is reduced on both sides, which leads to another condition for terminating the search. The search can be stopped as soon as in the middle of the interval obtained at the next step, the value of the function becomes modulo less than the predetermined error ef.

If, in accordance with the rule formulated above, Newton's method is applied to the right boundary of the segment, the following formulas are used for calculations:

https://pandia.ru/text/78/157/images/image025_10.gif" width="107" height="45 src=">.

If Newton's method is applied to the left boundary, - in the previous formulas, the designations are reversed a and b.

1.8 Iteration method

To apply this method, the original equation f(x)=0 converted to the form: x=y(X). Then choose the initial value x0 and substitute it on the left side of the equation, getting, in general case, x1 = y(x0)¹ x0¹ y(x1), insofar as x0 taken arbitrarily and is not a root of the equation. Received value x1 considered as another approximation to the root. He is again framed in right side equations and get next value x2=y(x1)). The calculation is continued according to the formula xi+1=y(xi). The resulting sequence is: x0, x1, x2, x3 x4,... converge to the root under certain conditions khtochn.

It can be shown that the iterative process converges under the condition
|y’ (x) | < 1 на [a, b].

Exist various ways equation transformations f(x)= 0 to kind y(X) = X, and in a specific case, some of them will lead to a convergent, and others to a divergent process of computation.

One way is to apply the formula

https://pandia.ru/text/78/157/images/image027_10.gif" width="188" height="44 src=">

where M= max | y’ (x)| on the [ a, b].

2 Solving systems of nonlinear equations

2.1 General information about solving systems of nonlinear equations

system n nonlinear equations with n unknown x1, x2, ..., xn are written in the form:

where F1, F2,…, fn are functions of independent variables, among which there are non-linear ones.

As in the case of systems of linear equations, the solution of the system is such a vector X*, which, when substituted, simultaneously turns all the equations of the system into identities.

https://pandia.ru/text/78/157/images/image030_8.gif" width="191" height="56">

Initial values x0 and y0 defined graphically. To find each successive approximation (xi+1 , yi+1 ) use a vector of function values ​​and a matrix of values ​​of their first derivatives calculated at the previous point (xi, yi) .

https://pandia.ru/text/78/157/images/image032_5.gif" width="276" height="63 src=">

To calculate new approximations in step i+1 the matrix formula is used

https://pandia.ru/text/78/157/images/image034_4.gif" width="303" height="59 src=">.

The above formulas are especially easy to write in Mathcad, where there are operators for calculating derivatives and operations with matrices. However, when correct use matrix operations these formulas are quite simply written in Excel. True, here it is necessary to obtain formulas for calculating derivatives in advance. Mathcad can also be used to calculate derivatives analytically.

2.3 Solving systems of nonlinear equations by iteration methods

To implement these methods, the original system of equations must be algebraic transformations explicitly express each variable in terms of the others. For the case of two equations with two unknowns new system will look like

https://pandia.ru/text/78/157/images/image036_5.gif" width="114" height="57 src=">.

If one of the solutions of the system and the initial values x0 and y0 lie in the area D given by the inequalities: a ≤ x ≤ b, c ≤ y ≤ d, then the calculation by the method of simple iterations converges when performed in the region D ratios:

https://pandia.ru/text/78/157/images/image038_5.gif" width="75 height=48" height="48">< 1.

AT Seidel iteration method for each calculation, the most accurate values ​​already found for each variable are used. For the considered case of two variables, such logic leads to the formulas

0 "style="border-collapse:collapse;border:none">

Tool (option)

Initial approximation

Rootx

f(x)

3. Sort the results by the accuracy of the solution.

Spreadsheet Microsoft excel . Means and methods for solving equations.

Objective: Master the numerical method for solving equations and the built-in tools for solving equations.

Content

1 Numerical method for solving nonlinear equations. 1

1.1 Root localization area. 1

1.2 Criteria for convergence in solving equations. 2

1.3 Dichotomy method (half division) 3

An example of solving an equation using the dichotomy method . 4

2 Solving Equations Using “Select Parameter”. 6

2.1 An example of solving an equation using “Sampling” . 6

3 Solving equations and systems of equations using the add-in “Search for a solution”. 9

3.1 An example of solving an equation using the add-in “Search for a solution” . 10

Task 1. Solving equations by numerical method.. 12

Tasks 2. Solving equations with built-in tools “Parameter selection” and “Search for a solution” 12

test questions.. 13

1 Numerical method for solving nonlinear equations

1.1 Root localization area

AT general view it is customary to write any equation of one variable like this, while the root (solution) is such a value x *, which turns out to be a true identity. An equation can have one, several (including an infinite number), or no roots. As it is easy to see, for real roots, the problem of finding a solution to the equation is easily interpreted graphically: the root is the value of the independent variable at which the graph of the function on the left side of the equation intersectsf( x ), with the abscissa axis.

for example , we perform a transformation for the equation and bring it to the form f(x)=0 those. . The graph of this function is shown in Figure 1. Obviously, this equation has two real roots - one on the segment [-1, 0], and the second -.

Figure 1. Graph of a function

Thus, it is possible to roughly determine root localization area equations. Note that the root can be separated in more than one way: if the root is separated on some segment, then any smaller segment containing this root is also suitable. Generally speaking, than less cut, the better, but we should not forget that the separation of the root on smaller segments also takes computational effort, and, perhaps, very significant. Thus, to begin with, one is often content with a very wide segment on which the root is separated.

Some types of equations admit an analytical solution. For example, power algebraic equations of degree n at n≤ 4. However, in general, analytical solution is usually absent. In this case, apply numerical methods . All numerical methods for solving equations are successive approximation to the root of the equation. That is, the initial approximation to the root is chosenx0 and then, using the iterative formula, the sequence is generatedx 1 , x 2 , …, x k converging to the root of the equation .

1.2 Criteria for convergence in solving equations

Ø Absolute error - absolute change in approximation at adjacent iteration steps

Ø Relative error - relative change in approximation at adjacent iteration steps

Ø The proximity to zero of the calculated value of the left side of the equation (sometimes called inviscidequations, since the residual for the root is zero)

1.3 Half division method(dichotomy method)

The bisection method is based on the sequential division of the segment of the root localization in half.

For this, an initial approximation to the segment is chosen. [ a , b], such thatf( a) × f( b)<0 , then the sign of the function is determined at the point - the middle of the segment [a , b]. If it is opposite to the sign of the function at the point a, then the root is localized on the segment [a , c], if not, then on the interval [c , b]. The scheme of the dichotomy method is shown in Fig.at nke 2.

Figure 2. Sequential division of the segment in half and approach to the root

The algorithm of the dichotomy method can be written as follows:

1. present the equation to be solved in the form

2. choose a, b and calculate

3. iff(a)× f(s)<0, то a=a; b = c otherwisea = c; b=b

4. if the convergence criterion is not met, then go to step 2

An example of solving an equation dichotomy method

Find the solution of the given equation by the dichotomy method with an accuracy of 10 -5 .

An example of creating a calculation scheme based on the dichotomy method using the equation as an example: on the segment

This method consists in checking the condition at each iteration:

iff( a) × f(s)<0 and selecting the appropriate segment for the next iteration.

a)

b)

Figure 3. Sequence of iterations dichotomy method when searching for the root of the equation on the segment

a) calculation scheme (dependent cells); b) formula display mode;

For our example, the iterative sequence for finding a solution takes the form:

Accuracy to the fifth significant digit is achieved in 20 iterations.

The convergence rate of this method is linear.

When the initial condition is satisfied, it always converges to the solution.

The bisection method is convenient for solving physically real equations, when the interval of localization of the solution of the equation is known in advance.

2 Solving equations , using “Parameter selection ”

Using the capabilities of Excel, you can find the roots of a nonlinear equation of the form f(x)= 0 in the allowed scope of the variable. The sequence of operations for finding roots is as follows:

1. The function is tabulated in the range of probable existence of roots;

2. According to the table, the nearest approximations to the values ​​of the roots are fixed;

3. Using the Excel tool Parameter selection, the roots of the equation are calculated with a given accuracy.

When selecting a parameter, Excel uses an iterative (cyclic) process. The number of iterations and precision are set in the menu Tools/Options/Calculations tab. If Excel is performing the complex task of selecting a parameter, you can click Pause in the dialog window Parameter selection result and abort the calculation, and then press the button Step to perform the next iteration and view the result. When solving a task in step-by-step mode, a button appears P continue- to return to the normal parameter selection mode.

2.1 An example of solving an equation using “Sampling”

for example , find all the roots of the equation 2x 3 -15sin(x)+0.5x-5=0 on the interval [-3 ; 3].

To localize the initial approximations, it is necessary to determine the intervals of X values, within which the value of the function intersects the abscissa axis, i.e. function changes sign. To this end, we tabulate the function on the segment [–3; 3] with a step of 0.2, we obtain tabular values ​​of the function. From the resulting table, we find that the value of the function crosses the X axis three times, therefore, the original equation has all three roots on a given segment.

Figure 4. Search for approximate values ​​of the roots of the equation

Execute a menu command Service/Parameters, tab Computing set the relative calculation error E=0.00001, and the number of iterations N=1000, check the box Iterations.

Execute a menu command Service/Selection. In the dialog box (Figure 9), fill in the following fields: