Approximate solution of algebraic and transcendental equations

Introduction

Every self-respecting engineer or IT person should be on “you” with computational mathematics and its numerical methods for solving various problems, perhaps even trivial ones, which “lead to the head in order”. In the process of studying I would like to pay more careful attention to the methods of approximate solution of algebraic and transcendental equations, as well as their analysis.

Numerical methods for solving nonlinear equations

I divided the task of the solution into 3 parts:

• Analytical method of root separation
• Numerical Methods for Clarifying Root
• Software implementation of the computational process

The purpose of the article, as I have already called, is the analysis and analysis of numerical methods, therefore I will not consider the analytical method of separating the roots in this article.

The method of dichotomy or half division.

The dichotomy method is the sequential division of a segment. The interval of the function will be selected - it is necessary to separate the roots, for example in a graphical way . Having obtained the interval of the function, its midpoint is calculated and it is determined which segment of the function divided by the midpoint is greater or less than zero; this is necessary to select a further narrowing of the interval. The process of narrowing continues to a certain error, which is set.
The advantages of this method of course is to include its simplicity. They are easy to calculate, both analytically and programmatically. The disadvantages are the costs of reduced iterations, compared with the method of chords and tangents for example.

Combined method or method of chords and tangents

Chord methods and the tangent method give approximations to the root from different sides. The combined use of methods allows for each iteration to find approximate values ​​with a shortage and with an excess, which speeds up the convergence process.
The idea of ​​the method of chords is to replace a function on a segment of a chord, and the idea of ​​the method of tangents or Newton's method is to replace the arc of the curve of the function with its tangent. It should be noted that the initial approximation of the chord method is determined by the end of the interval for which the derivative at a given point multiplied by the double derivative of the same point is less than zero, and for the tangent method it is greater than zero. The process of narrowing is also performed to a specified accuracy. The advantages, as already noted, are the speed of finding and lower costs for the given iterations.
')

Iteration method

It is first necessary to convert the equation f (x) = 0 to the form x = φ (x).
As the initial approximation x0, any point of the interval [a, b] is chosen.
There are 2 iterative methods: ladder and spiral. If the sign of the derivative φ (x) is positive, then use the ladder method and vice versa spirals.


The main and sufficient condition for the convergence of the iterative process is | φ '(x) | <1.
The virtue of the method. Reliability (self-correcting): an error in the calculations, in which x remains within [a, b], does not affect the final result, since erroneous value can be considered as new x0.

Practice. Application of methods.

Take for example the problem from the field of automated control - finding the zeros of the characteristic equation of the transfer function of a high-order closed-loop automatic control system to estimate its stability using the Lyapunov method. The method itself is beyond the scope of this post, but in the direct Lyapunov method, finding zero roots is used to identify the stability of the system. And the methods listed are quite suitable for finding the roots. Which method is more effective? This question is difficult to answer without knowing the specific system to which it will be applied. It is necessary to take into account not only the speed of operations, but also the resources occupied.

Conclusion:

1. The considered methods of root refinement are equally applicable to both algebraic and transcendental equations.
2. The operation of separating the roots is much more difficult for transcendental equations than for algebraic ones.
3. The most productive of the considered is the combined method.

Mat.part of the methods described.

PS: The first post and not yet fully accustomed. I put the post in the algorithms, because I did not find a blog on mathematics.