Using iterative algorithm to solve problems , The following three aspects need to be done well ： One , Determine iteration variables
In the problem that can be solved by iterative algorithm , We can make sure that there is at least one variable that can continuously deduce the new value from the old value directly or indirectly , This variable is the iteration variable . Two , Establish an iterative relationship
So called iterative relation , A formula for deriving the next value from the previous value of a variable （ Or relationship ）. The establishment of iterative relation is the key to solve the iterative problem , Usually, it can be done recursively or reversely .
Three , Control the iterative process
When does the iteration process end ? This is a problem that must be considered when writing iterative programs . We can't let the iterative process go on endlessly . The control of iterative process can be divided into two cases ： One is that the number of iterations required is a certain value , It can be calculated ; The other is that the number of iterations required cannot be determined . For the former case , A fixed number of cycles can be constructed to control the iterative process ; In the latter case , Further analysis is needed to determine the conditions that can be used to end the iteration process .
next , I introduce a typical case of iterative algorithm ---- Newton - Raphson （ Raffson ） method
Newton - Raphson （ Raffson ） method , also called
Newton iterative method , Also known as Newton tangent method ： First, arbitrarily set a value close to the real root x0 As the first approximation root , from x0 reach f(x0), too (x0,f(x0)) Do it f(x) Tangent of , hand over x Axis on x1, Take it as the second approximation root , By x1 reach f(x1), too (x1,f(x1)) Do it f(x) Tangent of , hand over x Axis on x2,…… Go on like this , Until it's close enough （ such as |x- x0|<1e-6 Time ） Real roots x* until .
and f '(x0)=f(x0)/( x1- x0)
therefore x1= x0- f(x0)/ f ' (x0).
Let's look at a picture we found on the Internet :
next , Let's take an example :
Let's just go straight to the code :
example : Newton iteration method is used to solve the following equation, where the value is equal to 2.0 Nearby roots ：2x3-4x2+3x-6=0.
#include <stdio.h> #include <math.h> int main(void) { float x,x0,f,f1; x =
2.0; do{ x0=x; f=2*x0*x0*x0-4*x0*x0+3*x0-6; f1=6*x0*x0-8*x0+3; x=x0-f/f1;
// function fabs： Find floating point number x Absolute value of // explain ： calculation |x|, When x Return if not negative x, Otherwise return -x }while(fabs(x-x0)>=1e-5);
printf ("%f\n",x); return 0 ; } results of enforcement :
When x=1.5 Time , equation 2x3-4x2+3x-6=0. Nearby roots are 2.000000 .
Technology