Which iterative method converges faster? Iteration method

It follows that α ≈ | φ ′ (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Thus, for the method to converge it is sufficient that ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

General algorithm for successive approximations[ | ]

When applied to the general case of operator equations, this method is called method of successive approximations or by simple iteration method. However, the equation can be transformed to a contraction map having the same root in different ways. This gives rise to a number of particular methods that have both linear and higher convergence rates.

In relation to SLAU[ | ]

Consider the system:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+ \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(array))\right.)

For it, the iterative calculation will look like this:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2 ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end (array))\right)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\right )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left( (\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

The method will converge with linear speed if ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Double vertical bars indicate some norm of the matrix.

Solution of the equation f(x)=0 using Newton's method, initial approximation: x 1 =a.

Newton's method (tangent method)[ | ]

One-dimensional case[ | ]

Optimizing the transformation of the original equation f (x) = 0 (\displaystyle f(x)=0) into a compressive display x = φ (x) (\displaystyle x=\varphi (x)) allows us to obtain a method with a quadratic rate of convergence.

For the mapping to be most effective, it is necessary that at the point of the next iteration x ∗ (\displaystyle x^(*)) carried out φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). We will look for a solution to this equation in the form φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), Then:

Let's use the fact that f (x) = 0 (\displaystyle f(x)=0), and we get the final formula for α (x) (\displaystyle \alpha (x)):

Taking this into account, the compression function will take the form:

Then the algorithm for finding a numerical solution to the equation f (x) = 0 (\displaystyle f(x)=0) reduces to an iterative calculation procedure:

1. Let a segment be known that contains one root of the equation f(x) = 0. The function f is a continuously differentiable function on this segment (f(x)ОC 1 ). If these conditions are met, the simple iteration method can be used.

2. Using the function f(x), a function j(x) is constructed that satisfies three conditions: it must be continuously differentiable (j(x)ОC 1 ), such that the equation x = j(x) is equivalent to the equation f(x)=0; should also translate a segment into yourself.

We will say that the function j ( x ) translates the segment [ a , b ] into yourself, if for anyone x Î [ a , b ], y = j ( x ) also belongs[ a , b ] ( y Î [ a , b ]).

The third condition is imposed on the function j(x):

Method formula: x n +1 = j(xn).

3. If these three conditions are met for any initial approximation x 0 О sequence of iterations x n +1 = j(x n) converges to the root of the equation: x = j(x) on the segment ().

As a rule, as x 0 one of the ends is selected.

,

where e is the specified accuracy

Number x n +1 when the condition for stopping the iterative process is met, it is approximate value of the root of the equation f(x) = 0 on the segment , found by simple iteration method with accuracy e .

Construct an algorithm to clarify the root of the equation: x 3 + 5x – 1 = 0 on a segment using the method of simple iteration with accuracy e .

1. Function f(x) = x 3 +5x-1 is continuously differentiable on the interval containing one root of the equation.

2. The greatest difficulty in the simple iteration method is the construction of a function j(x) that satisfies all the conditions:

Consider: .

Equation x = j 1 (x) is equivalent to the equation f(x) = 0, but the function j 1 (x) is not continuously differentiable on the interval.

Rice. 2.4. Graph of function j 2 (x)

On the other hand, therefore, . Hence: is a continuously differentiable function. Note that the equation: x = j 2 (x) is equivalent to the equation f(x) = 0 . From the graph (Fig. 2.4) it is clear that the function j 2 (x) transforms the segment into itself.

The condition that the function j(x) takes the segment into itself can be reformulated as follows: let be the domain of definition of the function j(x), and let be the domain of variation of j(x).

, .

All conditions for the function j(x) are satisfied.

Iterative process formula: x n +1 = j 2(xn).

3. Initial approximation: x 0 = 0.

4. Condition for stopping the iterative process:

Rice. 2.5. Geometric meaning of the simple iteration method

.

If this condition is met x n +1 – approximate value of the root on the segment, found by simple iteration with accuracy e. In Fig. 2.5. The application of the simple iteration method is illustrated.

Convergence theorem and error estimate

Let the segment contains one root of the equation x = j(x), function j(x ) is continuously differentiable on the interval , translates the segment into itself, and the condition is met:

.

Then for any initial approximation x 0 О subsequence converges to the root of the equation y = j(x ) on the segment and the error estimate is fair:

.

Stability of the simple iteration method. When the conditions of the convergence theorem are met, the algorithm of the simple iteration method is stable.

Complexity of the simple iteration method. The amount of computer memory required to implement the simple iteration method is insignificant. At each step you need to store x n , x n +1 , q And e.

Let us estimate the number of arithmetic operations required to implement the simple iteration method. Let us write down an estimate for the number n 0 = n 0 (e) such that for all n ³ n 0 the inequality holds:

From this estimate it follows that the closer q is to one, the slower the method converges.

Comment. There is no general rule for constructing j(x) from f(x) so that all the conditions of the convergence theorem are satisfied. The following approach is often used: the function j(x) = x + k× f(x) is chosen as the function j, where k – constant.

When programming the simple iteration method, stopping the iterative process often requires the simultaneous fulfillment of two conditions:

And .

All other iterative methods that we will consider are special cases of the simple iteration method. For example, when Newton's method is a special case of the simple iteration method.

The simple iteration method is based on replacing the original equation with an equivalent equation:

Let the initial approximation to the root be known x = x 0. Substituting it into the right side of equation (2.7), we obtain a new approximation , then in a similar way we get etc.:

. (2.8)

Not under all conditions the iterative process converges to the root of the equation X. Let's take a closer look at this process. Figure 2.6 shows a graphical interpretation of a one-way convergent and divergent process. Figure 2.7 shows two-way convergent and divergent processes. A divergent process is characterized by a rapid increase in the values ​​of the argument and function and the abnormal termination of the corresponding program.

With a two-way process, cycling is possible, that is, endless repetition of the same function and argument values. Looping separates a divergent process from a convergent one.

It is clear from the graphs that for both one-sided and two-sided processes, convergence to the root is determined by the slope of the curve near the root. The smaller the slope, the better the convergence. As is known, the tangent of the slope of a curve is equal to the derivative of the curve at a given point.

Therefore, the smaller the number near the root, the faster the process converges.

In order for the iteration process to be convergent, the following inequality must be satisfied in the vicinity of the root:

The transition from equation (2.1) to equation (2.7) can be carried out in various ways depending on the type of function f(x). In such a transition, it is necessary to construct the function so that the convergence condition (2.9) is satisfied.

Let's consider one of the general algorithms for transition from equation (2.1) to equation (2.7).

Let's multiply the left and right sides of equation (2.1) by an arbitrary constant b and add the unknown to both parts X. In this case, the roots of the original equation will not change:

Let us introduce the notation and let's move from relation (2.10) to equation (2.8).

Arbitrary choice of constant b will ensure the fulfillment of the convergence condition (2.9). The criterion for ending the iterative process will be condition (2.2). Figure 2.8 shows a graphical interpretation of the method of simple iterations using the described method of representation (the scales along the X and Y axes are different).

If a function is chosen in the form , then the derivative of this function will be . The highest speed of convergence will be at , then and the iteration formula (2.11) turns into Newton's formula. Thus, Newton's method has the highest degree of convergence of all iterative processes.

The software implementation of the simple iteration method is made in the form of a subroutine procedure Iteras(PROGRAM 2.1).

The entire procedure practically consists of one Repeat ... Until cycle, implementing formula (2.11) taking into account the condition for stopping the iterative process (formula (2.2)).

The procedure has built-in loop protection by counting the number of loops using the Niter variable. In practical classes, you need to make sure by running the program how the choice of coefficient affects b and initial approximation in the process of searching for the root. When changing the coefficient b the nature of the iterative process for the function under study changes. It first becomes two-sided, and then loops (Fig. 2.9). Axis scales X And Y are different. An even larger value of modulus b leads to a divergent process.

Comparison of methods for approximate solution of equations

A comparison of the methods described above for numerical solution of equations was carried out using a program that allows one to observe the process of finding the root in graphical form on the PC screen. The procedures included in this program and implementing the compared methods are given below (PROGRAM 2.1).

Rice. 2.3-2.5, 2.8, 2.9 are copies of the PC screen at the end of the iteration process.

In all cases, the quadratic equation x 2 -x-6 = 0 was taken as the function under study, having an analytical solution x 1 = -2 and x 2 = 3. The error and initial approximations were assumed equal for all methods. Root search results x= 3, presented in the figures, are as follows. The dichotomy method converges the slowest - 22 iterations, the fastest is the simple iteration method with b = -0.2 - 5 iterations. There is no contradiction here with the statement that Newton's method is the fastest.

Derivative of the function under study at the point X= 3 is equal to -0.2, that is, the calculation in this case was carried out practically by Newton’s method with the value of the derivative at the point of the root of the equation. When changing the coefficient b the rate of convergence drops and the gradually convergent process first goes in cycles and then becomes divergent.