Możesz także przybliżyć funkcję pierwiastka kwadratowego za pomocą metody Newtona . Metoda Newtona jest sposobem przybliżenia, gdzie są pierwiastki funkcji. Jest to również metoda iteracyjna , w której wynik z poprzedniej iteracji jest wykorzystywany w następnej iteracji aż do konwergencji. Równanie metody Newtona do odgadnięcia, gdzie jest pierwiastek z funkcji przy początkowym zgadywaniu x 0, jest zdefiniowane jako:fa( x )x0
x1= x0- f( x0)fa′( x0)
x1( n + 1 )n
xn + 1= xn- f( xn)fa′( xn)
zaza--√x = a--√zax2)- a = 0za--√fa( x ) = x2)- afa′( x ) = 2 x
xn + 1= xn- x2)n- a2 xn
xn + 1= 12)( xn+ axn)
za1x= a--√za--√1x2)- a = 01za√za
xn + 1= xn- f( xn)fa′( xn)
xn + 1= xn- 1( xn)2)- a- 2( xn)3)
xn + 1= 12)( 3 xn- ( xn)3)a )
Jest jednak ostrzeżenie, które powinniśmy rozważyć, patrząc na powyższe równanie. W przypadku pierwiastków kwadratowych rozwiązanie powinno być dodatnie, więc aby iteracje (i wynik) były dodatnie, należy spełnić następujący warunek:
3 xn- ( xn)3)a > 0
3 xn> ( xn)3)za
( xn)2)a < 3
W związku z tym:
( x0)2)a < 3
x0x0x010- 6
Gdy twój tag szuka algorytmu C, napiszmy go bardzo szybko:
#include <stdio.h> // For printf
#include <math.h> // For fabs
void main()
{
float a = 5.0; // Number we want to take the square root of
float x = 1.0; // Initial guess
float xprev; // Root for previous iteration
int count; // Counter for iterations
// Find a better initial guess
// Half at each step until condition is satisfied
while (x*x*a >= 3.0)
x *= 0.5;
printf("Initial guess: %f\n", x);
count = 1;
do {
xprev = x; // Save for previous iteration
printf("Iteration #%d: %f\n", count++, x);
x = 0.5*(3*xprev - (xprev*xprev*xprev)*a); // Find square root of the reciprocal
} while (fabs(x - xprev) > 1e-6);
x *= a; // Actual answer - Multiply by a
printf("Square root is: %f\n", x);
printf("Done!");
}
Jest to dość podstawowa implementacja metody Newtona. Zauważ, że ciągle zmniejszam początkowe domysły o połowę, dopóki warunek, o którym mówiliśmy wcześniej, nie jest spełniony. Próbuję również znaleźć pierwiastek kwadratowy z 5. Wiemy, że jest to mniej więcej równa 2.236. Użycie powyższego kodu daje następujące dane wyjściowe:
Initial guess: 0.500000
Iteration #1: 0.500000
Iteration #2: 0.437500
Iteration #3: 0.446899
Iteration #4: 0.447213
Square root is: 2.236068
Done!
za
Initial guess: 0.015625
Iteration #1: 0.015625
Iteration #2: 0.004601
Iteration #3: 0.006420
Iteration #4: 0.008323
Iteration #5: 0.009638
Iteration #6: 0.010036
Iteration #7: 0.010062
Square root is: 99.378067
Done!
Jak widać, jedyną różnicą jest to, ile iteracji jest wymaganych do obliczenia pierwiastka kwadratowego. Im większa liczba tego, co chcesz obliczyć, tym więcej iteracji zajmie.
Wiem, że ta metoda została już zasugerowana we wcześniejszym poście, ale pomyślałem, że wyprowadzę tę metodę i dostarczę trochę kodu!