|
Applications
© The scientific sentence. 2010
|
Newton-Raphson method
1. The method:
The Newton-Raphson method is, such as bisection or secant methods, a technique
for solving equations numerically. It is based on the linear approximation idea.
Let f(x) the function for which we are going to find a zero, that is
the root of the equation f(x) = 0.
Let's assume that the zero of a function f(x) is near the point (x0, f(x0).
The Taylor expansion for a function f(x) about
the point (x0, y0) can be written as:
f(x) = f(x0) + f'(x0)(x- x0) + (1/2!) f"(x0) (x - x0)2 + ...
Let's stay in the first order, then:
f(x) = f(x0) + f'(x0)(x - x0)
The ratio f'(x0) = [f(x) - f(x0)]/(x - x0) is the tangent at the curve
of the function at the point (x0,y0). It is also equal to the slope of
the tangent line at this point(x0, f(x0)).
Let's write the equation of this line like:
t)x) = f'(x0) x + b (b is the y-intercept of the equation of
the tangent). This line crosses the x-axis at the point x1, then:
t(x) = f'(x0) x1 + b = 0. Therefore:
b = - f'(x0) x1. Thus:
t(x) = f'(x0) x + b = f'(x0) x - f'(x0) x1.
We have then:
At x = x0, t(x0) = f(x0); therefore: f(x0) = f'(x0)( x0 - x1); so
x1 = x0 - f(x0)/f'(x0)
Similarly, if we continue the iterative process until xn+1, we will
get the nth estimate of the solution:
xn+1 = xn - f(xn/f'(xn) (1)
We take then xn as a solution when the following condition
is satisfied:
(xn+1 - xn)/xn) <= E/100.0 2)
Let's consider xn is the root r of the f(x) = 0, then:
xn+1 = xn - f(xn)/f'(xn), thus:
xn = xn. The relationship (2) is satisfied to the maximum.
The more the first member of the inequality (2) is small,
the more one gets near to the root of the function.
This method requires:
1. Guessing a good estimate of x0, the nearest root of f(x) = 0,
2. knowing the derivative of the function f(x).
2. Example in clanguage
// Program: newton-free-fall.c
#include
#include
#include
double g = 9.81;
float y = 500;
// The function
//--------------
float f(float t)
{
return y - (g/2)*t*t;
}
// The derivative of the function
//------------------------------
float f_der (float t)
{
return g*t;
}
float newton (float f(float To)){
float ss = 0;
float c[41];
c[0] = 10.00 ;
float E = 0.05;
int i,n = 40;
for(i=1;i<=n;i++)
{
c[i] = c[i-1] - f(c[i-1])/f_der(c[i-1]);
if (abs((c[i] - c[i-1])/c[i-1]) <= E/100.0 )
{
printf("\nThe solution is T = %1.2f seconds.\n", c[i]);
ss= c[i];
i = n+1;
}
}
return ss;
}
// --------The function main ------
int main()
{
newton(&f);
return 0;
}
-------------
The execution gives:
>newton_free_fall
The solution is T = 9.90 seconds.
>Exit code: 0
|
|
|
