Steffensen (Eitken-Steffensen) method for solving nonlinear equations

Аннотация

Solving nonlinear equations is more complicated and is a perfectly unresolved problem in computational mathematics. This iterative algorithm is called the Steffensen method in numerical methods. The Steffensen method has a quadratic approximation. This method requires calculating the value of the function twice in each iteration, in which case the Steffensen method is less efficient than the cutters method. Keywords: Steffensen method, iterative algorithm, approximation, Eitken, Newton method, sequence, limit, linear approximation. To increase the approximation speed of the test method x +1 = 𝜑(x ) n = 0,1,2, … (1) n n In the expression 𝑓′(x ) Abbreviation of words that bring the harvest n closer: 𝑓′(x ) ≈ 𝑓 (xn+1 )−𝑓 (xn ) (2) n xn+1−xn If (1) is a left-handed approximation, then (2) is a right-handed approximation. (2) shows that in which it has not yet been determined x +1 n To calculate the presence of an unknown limit, we use a simple iteration (1.2): x = 𝑔(x ) = x + 𝑓(x ). n+1 n n n 82 Scientific research results in pandemic conditions (COVID-19) As a result, we have the following approximation: 𝑓′(x ) ≈ 𝑓 (xn+𝑓(xn ) )−𝑓(xn ) . n 𝑓(xn ) Using this expression in Newton's method, we get a new iterative algorithm: x = x − 𝑓(xn ) 𝑓(x ). (3) n+1 n n 𝑓 (xn+𝑓(xn ) )−𝑓(xn ) This iterative algorithm is called the Steffensen method in numerical methods. The Steffensen method has a quadratic approximation, but here in addition 𝑓 (x +𝑓(x ) ) a high approximation speed is achieved by n n calculating the value of the expression. .The iterative algorithm above (3) can also be derived from the method of accelerating the convergence of linear convergent sequences proposed by Eitken. To do this, consider the following sequence: z = 𝑧+𝐶𝑞𝑛 (4) n This is a sequence |𝑞| < 1 to z limit approached. Find the limit value of z using simple reflections {z } three in a row z ,z 𝑎𝑛𝑑 z in series n n−1 n n+1 zn−𝑧 = 𝑞 and zn+1−𝑧 = 𝑞 this from two equations (z −𝑧)(z −𝑧) = n+1 n−1 zn−1−𝑧 zn−𝑧 ((z −𝑧)2 equality. This leads to the following expression for z: n z = zn+1zn−1− zn 2 . zn+1−2zn −zn−1 Based on this result, let us consider the following Eitken proposition to replace the {z } sequence with another sequence: n ξ = zn+1zn−1− zn 2 . (5) n+1 zn+1−2zn +zn−1 If this substitution is in any sequence in the form (4) if we use, then at any value of n ξ = 𝑧− lim 𝑧𝑛 equality is n appropriate. If the approximation type of the sequence {z } is close to (4), n then substitution (5) gives z a new sequence that approximates z faster than the original (even if it does not give its limit at an arbitrary value of n). 1-for example. This 𝑥3 −𝑥2 −8𝑥 +12 = 0 approximate the double root of the equation x = 2 using Newton's r method and the Eitken accelerator. Solution. The results of the calculations are presented in the table below with the elements of the corresponding sequences (see columns three and four). 83 Scientific research results in pandemic conditions (COVID-19) In the third column of this table, the approximation velocity is assumed to be a = 1, and the values of the variable C in equation (4) for each iteration are given. The results in the table show that C changes very little during the iterative process and is very close to C = 0.5. As a result, the hypothesis that the rate of approach of the Newtonian method to the multiple root is linear is proved. Using the linear approximation {x } sequence (5) to the accelerating n formula, we obtain the values of the s in the fourth column of the table ξ . n By comparing the values in the second and fourth columns of the table, we make sure that we have reached the approximation speed. Indeed, the result obtained in the fourteenth iteration of the Newtonian method can be seen by applying the Newtonian method and the Eitken accelerator q to the same result in its seventh iteration. The results in the fifth column of this table show that such an effective result was achieved not by increasing the convergence velocity index a, but by reducing the variable C to 0.25. First of all iterative for this x = 𝑔(x ) n+1 n let's spread the right side of the formula to Taylor's row, that is 𝑔(x ) = 𝑔(x +(x −x )) = x +𝑔′(x )(x −x )+𝑂((x −x )2), n r n r r r n r n r According to this x −x = 𝑔′(x )(x −x )+𝑂((x −x )2), n+1 r r n r n r And so, e = x −x The following approximate equation can be n n r written for each iteration with square accuracy: x −x = 𝑔′(x )(x −x ). n+1 r r n r Here the sequence {x } can be expressed by the following formula: n x ≈ x + [𝑔′(x )]𝑛(x −x ) n r r n r 84 Scientific research results in pandemic conditions (COVID-19) The approximation type of this sequence is the same as that of the sequence (4). This means that the approximation sequence to the root in simple iteration is suitable for applying the approximation acceleration procedure. In order to ensure that each improvement value calculated using the approximation acceleration procedure is taken into account in subsequent calculations,