2 Horner's scheme

3 Freeform functions

4 Finding the roots of polynomials

List of used information sources

1 Finding roots of equations (Equation Section 1)

One of the most common methods for finding the roots of equations is Newton's method and its modifications. Let it be required to solve the equation

. We will assume that x is a solution to the equation. Let us expand the function f(x) into a series at the point x0 close to the point x and restrict ourselves to only the first two terms of the expansion.

Since x is the root of the equation, then

. Hence,

Thus, if we know the approximate value of the root of the equation, then the resulting equation allows us to refine it. It is clear that the refinement process can be repeated many times until the value of the function differs from zero by a value less than the specified search accuracy. Next k-th approximation is found by the formula

Restricting the expansion to only the first two terms, we actually replaced the function f(x) with a straight line tangent at the point x0, so Newton's method is also called the method of tangents. It is not always convenient to find an analytical expression for the derivative of a function. However, this is not particularly necessary: ​​since at each step we get an approximate value of the root, we can use the approximate value of the derivative to calculate it.

As a small quantity

you can take, for example, the given calculation accuracy , then the calculation formula will take the form (1.1)

On the other hand, to calculate the derivative, you can use the values ​​of the function obtained in the two previous steps,

(1.2)

In this form, the method is called the secant method. In this case, however, there is a problem with the calculation of the first approximation. It is usually assumed that

, that is, the first step of calculations is carried out using formula (1.1), and all subsequent steps are performed using formula (1.2). It is this computational scheme that is implemented in the Mathcad package. Using the secant method, we cannot guarantee that the root is between the last two approximations. It is possible, however, to calculate the next approximation using the boundaries of the interval on which the function changes sign. This method is called the chord method (falsepositionmethod).

The idea of ​​the secant method is developed in Muller's method. However, in this method, three previous points are used to find the next approximation. In other words, the method uses not linear, but quadratic function interpolation. The calculation formulas of the method are as follows:

The sign before the root is chosen so that the absolute value of the denominator is maximum.

Because the root search ends when the condition is met

, then false roots may appear. For example, for an equation, a false root will appear if the search accuracy is set to less than 0.0001. By increasing the accuracy of the search, you can get rid of false roots. However, this approach does not work for all equations. For example, for an equation that obviously has no real roots, for any, arbitrarily small accuracy, there is a value x that satisfies the criterion for terminating the search. The examples given show that the results of computer calculations should always be treated critically and analyzed for plausibility. To avoid "pitfalls" when using any standard package that implements numerical methods, you need to have at least a minimal idea of ​​what kind of numerical method is implemented to solve a particular problem.

In the case when the interval on which the root is located is known, you can use other methods for finding a solution to the equation.

In the Ridder's method, the value of the function is calculated in the middle of the interval

. Then they look for an exponential function such that Then apply the method of chords, using the values ​​. The next value is calculated by the formula (1.5)

The Brent method combines the speed of the Ridder method with the guaranteed convergence of the bisection method. The method uses inverse quadratic interpolation, that is, it looks for x as a quadratic function of y. At each step, the localization of the root is checked. The formulas of the method are rather cumbersome and we will not present them.

Special methods are used to find the roots of a polynomial. In this case, all roots can be found. After one of the roots of the polynomial is found, the degree of the polynomial can be lowered, after which the search for the root is repeated.

Lobachevsky method, approximate (numerical) solution method algebraic equations, found independently by the Belgian mathematician J. Dandelin, the Russian mathematician N. I. Lobachevsky (in 1834 in the most perfect form), and the Swiss mathematician K. Greffe. The essence of L. m. is to construct the equation f1(x) = 0, the roots of which are the squares of the roots of the original equation f(x) = 0. Then the equation f2(x) = 0 is constructed, the roots of which are the squares of the roots of the equation f1(x) = 0. Repeating this process several times, one obtains an equation whose roots are strongly separated. If all the roots of the original equation are real and different in absolute value, there are simple computational schemes of linear meters for finding approximate values ​​of the roots. In the case of equal in absolute value of the roots, as well as complex roots The computational schemes of L. m. are very complex.

Laguerre's method is based on the following relations for polynomials

The sign in front of the root is chosen in such a way as to get highest value denominator.

Another method that is used to find the roots of polynomials is the companion matrix method. It can be shown that the matrix

called the accompanying matrix for the polynomial

, has eigenvalues ​​equal to the roots of the polynomial. Recall that the eigenvalues ​​of a matrix are those numbers  for which the equality or is true. There are very effective methods search for eigenvalues, some of which we will discuss below. Thus, the problem of finding the roots of a polynomial can be reduced to the problem of finding the eigenvalues ​​of the accompanying matrix.

2 Horner's scheme

The calculation according to the Horner scheme turns out to be more efficient, and it does not become very complicated. This scheme is based on the following polynomial representation:

p(x) = ((... ((anx + an-1)x + an-2)x + ... + a2)x + a1)x + a0.

Let's take a general polynomial of the form:

p(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + a0.

We will assume that all coefficients an, ..., a0 are known, constant, and stored in an array. This means that the only input to evaluate the polynomial is the value of x, and the output of the program must be the value of the polynomial at x.

Properties

where - (in the general case, complex) roots of the polynomial, possibly with repetitions, while if among the roots of the polynomial there are equal ones, then their common value is called multiple root.

Finding roots

The method for finding the roots of linear and quadratic polynomials, that is, the method for solving linear and quadratic equations, was already known in ancient world. The search for a formula for the exact solution of the general equation of the third degree continued for a long time (we should mention the method proposed by Omar Khayyam), until they were successful in the first half of the 16th century in the works of Scipio del Ferro, Niccolo Tartaglia and Gerolamo Cardano. Formulas for the roots of quadratic and cubic equations made it relatively easy to obtain formulas for the roots of a fourth degree equation.

That the roots general equation fifth degree and above are not expressed using rational functions and radicals of the coefficients was proved by the Norwegian mathematician Niels Abel in 1826. This does not mean at all that the roots of such an equation cannot be found. First, in particular cases, with some combinations of coefficients, the roots of the equation can be determined with some ingenuity. Secondly, there are formulas for the roots of equations of the 5th degree and higher, which, however, use special functions - elliptic or hypergeometric (see, for example, the Bring root).

If all coefficients of a polynomial are rational, then finding its roots leads to finding the roots of a polynomial with integer coefficients. For rational roots of such polynomials, there are algorithms for finding candidates by enumeration using Horner's scheme, and when finding integer roots, enumeration can be significantly reduced by cleaning the roots. Also in this case, you can use the polynomial LLL algorithm.

To approximate (with any required accuracy) the real roots of a polynomial with real coefficients, iterative methods are used, for example, the secant method, the bisection method, Newton's method. The number of real roots of a polynomial in an interval can be estimated using Sturm's theorem.

see also

Notes

Wikimedia Foundation. 2010 .

• Sewerage
• Glossary of vexillology terms

See what the "Polynomial Root" is in other dictionaries:

Root of an algebraic equation

Root of the equation- The root of the polynomial over the field k is an element that, after substituting it for x, turns the equation into an identity. Properties If c is a root of the polynomial p(x ... Wikipedia

Bringa Root- Check information. It is necessary to check the accuracy of the facts and the reliability of the information presented in this article. There should be explanations on the talk page. In algebra, the Bring root or ultraradical is an analytic function such that for ... ... Wikipedia

Root (disambiguation)- Root: Wiktionary has an entry for "root" Root (in botany) a vegetative axial underground organ of a plant that has a sp ... Wikipedia

Root (in mathematics)- The root in mathematics, 1) K. degree n from the number a ≈ the number x (denoted), the nth degree of which is equal to a (that is, xn \u003d a). The action of finding K. is called root extraction. For a ¹ 0, there are n different values ​​of K. (generally speaking, ... ...

Root- I Root (radix) is one of the main vegetative organs of leafy plants (with the exception of mosses), which serves to attach to the substrate, absorb water from it and nutrients, the primary transformation of a number of absorbed substances, ... ... Great Soviet Encyclopedia

ROOT- 1) K. of degree n from number a number n i degree x n to rogo is equal to a. 2) K. of an algebraic equation over a field K, the element k, after substituting it in place of x, turns the equation into an identity. K. of this equation is called. also K. of the polynomial If is ... ... Mathematical Encyclopedia

multiple root- polynomial f (x) = a0xn + a1xn ​​1 +... + an, a number c such that f (x) is divisible without remainder by the second or higher power of the binomial (x c). In this case, c is called the root of multiplicity if f (x) is divisible by (x c) k, but not ... ... Great Soviet Encyclopedia

conjugate root- If some irreducible polynomial over a ring is given and some of its root in the extension is chosen, then the conjugate root for a given polynomial root is any polynomial root ... Wikipedia

Square root of 2- equal to the length of the hypotenuse in a right triangle with legs length 1. The square root of 2 is positive ... Wikipedia

K is an element c ∈ K (\displaystyle c\in K)(or an element of the field extension K) such that the following two equivalent conditions are satisfied: a 0 + a 1 x + ⋯ + a n x n = 0 (\displaystyle a_(0)+a_(1)x+\dots +a_(n)x^(n)=0)

The equivalence of the two formulations follows from Bézout's theorem. IN various sources either one of the two formulations is chosen as the definition and the other is deduced as the theorem.

They say that the root c (\displaystyle c) It has multiplicity m (\displaystyle m) if the considered polynomial is divisible by (x − c) m (\displaystyle (x-c)^(m)) and is not divisible by (x − c) m + 1 . (\displaystyle (x-c)^(m+1).) For example, polynomial x 2 − 2 x + 1 (\displaystyle x^(2)-2x+1) has a single root equal to 1 , (\displaystyle 1,) multiplicity 2. The expression "multiple root" means that the multiplicity of the root is greater than one.

Properties

P (x) = a n (x − c 1) (x − c 2) … (x − c n) , (\displaystyle p(x)=a_(n)(x-c_(1))(x-c_( 2))\ldots (x-c_(n)),) where - (generally complex) roots of the polynomial, possibly with repetitions, while if among the roots c 1 , c 2 , … , c n (\displaystyle c_(1),c_(2),\ldots ,c_(n)) polynomial p (x) (\displaystyle p(x)) are equal, their common value is called multiple root.

Finding roots

The method of finding the roots of linear and quadratic polynomials, that is, the method of solving linear and quadratic equations, was known in the ancient world. The search for a formula for the exact solution of the general equation of the third degree continued for a long time (we should mention the method proposed by Omar Khayyam), until they were successful in the first half of the 16th century in the works of Scipio del Ferro, Niccolo Tartaglia and Gerolamo Cardano. Formulas for the roots of quadratic and cubic equations made it relatively easy to obtain formulas for the roots of a fourth degree equation.

That the roots are common fifth degree equations and above are not expressed using rational functions and radicals of the coefficients, was proven by a Norwegian mathematician

Lesson Objectives:

• teach students to solve equations of higher degrees using Horner's scheme;
• develop the ability to work in pairs;
• to create, together with the main sections of the course, a basis for developing the abilities of students;
• help the student assess his potential, develop interest in mathematics, the ability to think, speak on the topic.

Equipment: cards for work in groups, a poster with Horner's scheme.

Teaching method: lecture, story, explanation, performance of training exercises.

Form of control: verification of problems of independent solution, independent work.

During the classes

1. Organizational moment

2. Actualization of students' knowledge

What theorem allows you to determine whether the number is the root of a given equation (to formulate a theorem)?

Bezout's theorem. The remainder of dividing the polynomial P(x) by the binomial x-c equals P(c), the number c is called the root of the polynomial P(x) if P(c)=0. The theorem allows, without performing the division operation, to determine whether a given number is a root of a polynomial.

Which statements make it easier to find roots?

a) If the leading coefficient of the polynomial is equal to one, then the roots of the polynomial should be sought among the divisors of the free term.

b) If the sum of the coefficients of a polynomial is 0, then one of the roots is 1.

c) If the sum of the coefficients in even places is equal to the sum of the coefficients in odd places, then one of the roots is equal to -1.

d) If all coefficients are positive, then the roots of the polynomial are negative numbers.

e) A polynomial of odd degree has at least one real root.

3. Learning new material

When solving entire algebraic equations, one has to find the values ​​of the roots of polynomials. This operation can be greatly simplified if calculations are carried out according to a special algorithm called Horner's scheme. This scheme is named after the English scientist William George Horner. Horner's scheme is an algorithm for calculating the quotient and remainder of dividing a polynomial P(x) by x-c. Briefly, how it works.

Let an arbitrary polynomial P(x)=a 0 x n + a 1 x n-1 + ...+ a n-1 x+ a n be given. The division of this polynomial by x-c is its representation in the form P(x)=(x-c)g(x) + r(x). Private g (x) \u003d at 0 x n-1 + at n x n-2 + ... + at n-2 x + at n-1, where at 0 \u003d a 0, at n \u003d sv n-1 + a n , n=1,2,3,…n-1. Remainder r (x) \u003d St n-1 + a n. This calculation method is called the Horner scheme. The word "scheme" in the name of the algorithm is due to the fact that usually its execution is formalized as follows. First draw table 2(n+2). The number c is written in the lower left cell, and the coefficients of the polynomial P (x) are written in the upper line. In this case, the upper left cell is left empty.

	at 0 = a 0	in 1 \u003d sv 1 + a 1	in 2 \u003d sv 1 + A 2		in n-1 \u003d sv n-2 +a n-1	r(x)=f(c)=sv n-1 +a n

The number, which after the execution of the algorithm turns out to be written in the lower right cell, is the remainder of dividing the polynomial P(x) by x-c. The other numbers at 0 , at 1 , at 2 ,… of the bottom row are the coefficients of the quotient.

For example: Divide the polynomial P (x) \u003d x 3 -2x + 3 by x-2.

We get that x 3 -2x + 3 \u003d (x-2) (x 2 + 2x + 2) + 7.

4. Consolidation of the studied material

Example 1: Factorize the polynomial P(x)=2x4-7x 3 -3x 2 +5x-1 with integer coefficients.

We are looking for integer roots among the divisors of the free term -1: 1; -1. Let's make a table:

X \u003d -1 - root

P (x) \u003d (x + 1) (2x 3 -9x 2 + 6x -1)

Let's check 1/2.

					X=1/2 - root

Therefore, the polynomial P(x) can be represented as

P (x) \u003d (x + 1) (x-1/2) (x 2 -8x +2) \u003d (x + 1) (2x -1) (x 2 - 4x +1)

Example 2: Solve the equation 2x 4 - 5x 3 + 5x 2 - 2 = 0

Since the sum of the coefficients of the polynomial written on the left side of the equation is equal to zero, then one of the roots is 1. Let's use Horner's scheme:

						X=1 - root

We get P (x) \u003d (x-1) (2x 3 -3x 2 \u003d 2x +2). We will look for roots among the divisors of the free term 2.

We found out that there are no more whole roots. Let's check 1/2; -1/2.

					X \u003d -1/2 - root

Answer: 1; -1/2.

Example 3: Solve the equation 5x 4 - 3x 3 - 4x 2 -3x + 5 = 0.

We will look for the roots of this equation among the divisors of the free term 5: 1; -1; 5; -5. x=1 is the root of the equation, since the sum of the coefficients is zero. Let's use Horner's scheme:

we represent the equation as a product of three factors: (x-1) (x-1) (5x 2 -7x + 5) \u003d 0. Deciding quadratic equation 5x 2 -7x+5=0, got D=49-100=-51, no roots.

Card 1

1. Factor the polynomial: x 4 +3x 3 -5x 2 -6x-8
2. Solve the equation: 27x 3 -15x 2 +5x-1=0

Card 2

1. Factor the polynomial: x 4 -x 3 -7x 2 + 13x-6
2. Solve the equation: x 4 +2x 3 -13x 2 -38x-24=0

Card 3

1. Factorize: 2x 3 -21x 2 + 37x + 24
2. Solve the equation: x 3 -2x 2 +4x-8=0

Card 4

1. Factorize: 5x 3 -46x 2 + 79x-14
2. Solve the equation: x 4 +5x 3 +5x 2 -5x-6=0

5. Summing up

Testing knowledge when solving in pairs is carried out in the lesson by recognizing the method of action and the name of the answer.

Homework:

Solve the equations:

a) x 4 -3x 3 +4x 2 -3x + 1 \u003d 0

b) 5x 4 -36x 3 +62x 2 -36x+5=0

c) x 4 + x 3 + x + 1 \u003d 4 x 2

d) x 4 + 2x 3 -x-2 \u003d 0

Literature

1. N.Ya. Vilenkin et al., Algebra and the Beginnings of Analysis Grade 10 (in-depth study of mathematics): Enlightenment, 2005.
2. U.I. Sakharchuk, L.S. Sagatelova, Solution of equations of higher degrees: Volgograd, 2007.
3. S.B. GashkovNumber systems and their application.

If the function f(x) is a polynomial, then all its roots can be determined using the built-in function

where v is a vector composed of the coefficients of the polynomial.

Since the nth degree polynomial has exactly n roots (some of them may be multiples), the vector v must have n+1 elements. The result of the polyroots() function is a vector composed of n roots of the considered polynomial. In this case, there is no need to enter any initial approximation, as for the root () function. An example of searching for the roots of a fourth degree polynomial is shown in Fig. 4.6:

Rice. 4.6. Finding the root of a polynomial

The coefficients of the polynomial considered in the example are written as a column vector starting from the free term and ending with the coefficient at the highest degree x n .

For the polyroots() function, you can choose one of two numerical methods - the Lugger polynomial method (it is installed by default) or the pair matrix method. To change the method, you need to call the context menu by right-clicking on the word polyroots and select either LaGuerre (Lagger) or Companion Matrix (Pair matrix) in the upper part of the context menu. Then you need to click outside the action of the polyroots function - and if the automatic calculation mode is enabled, the polynomial roots will be recalculated in accordance with the newly selected method.

In order to leave the choice of the solution method to Mathcad, you need to check the AutoSelect checkbox by selecting the item of the same name in the same context menu.

Solving systems of nonlinear equations

Consider the solution of the system n nonlinear equations with m unknowns

f 1 (x 1,..., x m) = 0,

f n (x 1 ,..., x m) = 0,

Here f 1 (x 1 ,... ,х m) , ..., f n (x 1 ,... ,х m) are some scalar functions of scalar variables x 1 ,... ,х m and possibly , from any other variables. Equations can be either more or less than the number of variables. Note that the above system can be formally rewritten as

where x is a vector composed of variables x 1 ,..., x m , and f (x) is the corresponding vector function.

To solve systems, there is a special computing unit, consisting of three parts, going sequentially one after another:

given- keyword;

A system written using Boolean operators as equalities and possibly inequalities;

Find(x 1 ,... ,x m) is a built-in function for solving the system with respect to variables x 1 ,... ,x m .

The Given/Find block uses iterative methods to find a solution, so, as for the root() function, it is required to specify initial values ​​for all x 1 ,..., x m . This must be done before writing the Given keyword. The value of the Find function is a vector made up of the solution for each variable. Thus, the number of vector elements is equal to the number of Find arguments.

Consider an example. Solve a system of two equations with two unknowns:

with an accuracy of 0.01. Separate the roots graphically.

Let us represent the equations of the system in the form of the following functions of one variable:

Let's pick discrete values variables:

Let's find the roots of the equation using the Given - Find() block:

On fig. 4.7 shows another example of solving a system of two equations:

Rice. 4.7. Solving a system of equations

At first fig. 4.7, functions are introduced that define a system of equations. Then the variables x and y, with respect to which it will be decided, are assigned initial values. This is followed by the Given keyword and two Boolean equality operators expressing the system of equations in question. The computational block is terminated by the Find function, whose value is assigned to the vector v. After that, the content of the vector v is printed, i.e., the solution of the system. The first element of the vector is the first argument of the Find function, the second element is its second argument. At the end, the correctness of the solution of the equations was checked. Note that the equations can be defined directly inside the computational block.

Graphical interpretation of the considered system is presented in fig. 4.8. Each of the equations is shown on the xy plane by a graph. The first equation is shown as a curve, the second as a solid line. Two points of intersection of the curves correspond to the simultaneous fulfillment of both equations, i.e., to the desired real roots of the system. As is easy to see, in Fig. 4.7, only one of the two solutions is found - located in the lower right part of the graph. To find the second solution, you should repeat the calculations, changing the initial values ​​so that they lie closer to another point of intersection of the graphs, for example x=-1, y=-1.

Rice. 4.8. Graphical solution of a system of two equations

An example of a system of two equations and the same number of unknowns was considered, which occurs most often. However, there are cases when the number of equations and unknowns may not coincide. Moreover, additional conditions in the form of inequalities can be added to the computational block. For example, introducing a restriction to search for only negative values ​​of x in the above example will lead to finding another solution, as shown in Fig. 4.9:

Rice. 4.9. Solving a system of equations and inequalities

Despite the same initial values ​​as in Fig. 4.8, in fig. 4.9 another root is obtained. This happened precisely due to the introduction of an additional inequality, which is defined in the Given (x< 0).

If an attempt is made to solve an incompatible system, Mathcad will give an error message that no solution was found, and you need to try changing the initial values ​​or the error value.

The calculation unit uses the CTOL constant as an estimate of the error in solving the equations entered after the Given keyword. For example, if CTOL=0.001, then the equation x=10 will be considered fulfilled both at x=10.001 and at x=9.999. Another constant TOL defines the condition for terminating iterations by the numerical algorithm. The value of CTOL can be set by the user in the same way as TOL, for example, CTOL:=0.01. The default is CTOL=TOL=0.001, but you can override them if you wish.

Particular care should be taken when solving systems with more unknowns than the number of equations. For example, one of the two equations can be removed from the Fig. 4.7 by trying to solve the only equation g(x, y)=0 with two unknowns x and y. In this formulation, the problem has an infinite number of roots: for any x and, accordingly, y \u003d -x / 2, the condition that determines the unique equation is satisfied. However, even if there are infinitely many roots, the numerical method will only perform calculations until the logical expressions in the computational block are fulfilled (within the margin of error). After that, iterations will be stopped and a solution will be issued. As a result, only one pair of values ​​\u200b\u200b(x, y) will be found, which was found first.

The computational unit with the Find function can also find the root of an equation with one unknown. The Find action in this case is exactly the same as the examples already discussed in this section. The problem of finding the root is considered as a solution to a system consisting of one equation. The only difference will be the scalar rather than the vector type of the number returned by the Find() function. An example of solving the equation from the previous section is shown in fig. 4.10.

Rice. 4.10. Finding the root of an equation with one unknown using the Find() function.

Mathcad offers three different kinds of gradient methods for solving a system of nonlinear equations using the Given – Find() block. To change the numerical method, you must:

Right-click on the name of the Find function;

Select the item Nonlinear (Nonlinear) in the context menu that appears;

Choose one of three methods: Conjugate Gradient (Conjugate gradients, installed by default), Quasi-Newton (Quasi-Newtonian) or Levenberg-Marquardt (Levenberg).