Newton Raphson root approximation
The Newton Raphson approximation is an approach for finding the (real-valued) roots of nonlinear equations. This is a relative simple, but fast approach. The original function \(f(x)\) as well as the derivate \(f'(x)\) is required. This implementation is designed to only work with polynomial functions, i.e., functions that are built from the addition of the exponentiation of variables to a non-negative integer power: I.e., functions \(P(x)\) with the following definition
with the coefficients \(a_k\) and the variable \(x\). To automatically calculate the derivate, refer to Polynomial derivate calculation. If there are not enough iterations for the approach to converge to the root, the results can be inaccurate. A balance between computational effort (i.e., number of iterations) and accuracy of the results have to be made by the user.
Note
The basic Newton-Raphson method as implemented in this software module returns only one of the (potentially) multiple roots of the polynomial. Which root is returned depends on the polynomial and the initial guess for \(x\), i.e., initial_value
of the uz_newton_raphson_config
struct.
Reference
-
struct uz_newton_raphson_config
Public Members
-
uz_array_float_t coefficients
Array which carries the coefficients of the polynomial (i.e. 14*x³)
-
uz_array_float_t derivate_poly_coefficients
Array which carries the coefficients for the derivate of the polynomial.
They only carry the derivative part, i.e. the scaled value of the original function times the factor from the derivate (x^4 -> 4x^3). The coefficients (a0,a1,a2,a3, etc.) are NOT included in this array.
-
float initial_value
Initial value with which the approximation starts. Should be a reasonable start value, otherwise the algorithm may not converge
-
uint32_t iterations
Number of iterations the algorithm will cycle through
-
float root_absolute_tolerance
Absolute tolerance of the approximated root. An assertion is triggered if the polynomial evaluates to a value outside of the tolerance (-tolerance<f(x_root)<tolerance) for the approximated root x_root. This happens if there are not enough iterations, the given polynomial does not have a real-valued root, or the initial value was not choosen in a way that leads to convergence.
-
uz_array_float_t coefficients
-
float uz_newton_raphson(struct uz_newton_raphson_config config)
Approximates the root of the polynomial.
- Parameters
config – uz_newton_raphson_config struct
- Returns
float root of the polynomial
Description
This function uses the arrays from the UltraZohm Array library. This algorithm uses the Newton Raphson[1] approach to approximate the roots, with \(x_0\) being the initial guess.
Consider this equation:
This can be represented differently:
With the coefficients:
There is a dedicated array for the coefficients (a,b,c,d, etc.) and another one for calculating the coefficients of the derivate based on the coefficients of the polynomial and derivate_poly_coefficients
.
If the coefficients change during runtime, only they have to be updated.
The rest can stay the same.
The coefficients are represented as a vector
which is implemented as arrays:
//float coefficients[5] = {a_0, a_1, a_2, a_3, a_4};
//float derivate_poly_coefficients[4] = {1*x0, 2*x1, 3*x2, 4*x3};
float coefficients[5] = {2.0f, -20.5f, -5.0f, 0.0f, 1.0f};
float derivate_poly_coefficients[4] = {1.0f, 2.0f, 0.0f, 4.0f};
Note that the values for derivate_poly_coefficients
should be calculated using uz_newton_raphson_derivate
(see Polynomial derivate calculation).
Example
Approximate the roots of
The function has two real roots at \(\approx 0.953476\) and \(\approx 3.31653\) (see WolframAlpha solution).
#include "../uz/uz_newton_raphson/uz_newton_raphson.h"
int main(void) {
float derivate_poly_coefficients[4] = {1.0f, 2.0f, 0.0f, 4.0f};
float coefficients[5] = {2.0f, -20.5f, -5.0f, 0.0f, 1.0f};
struct uz_newton_raphson_config config = {
.derivate_poly_coefficients.length = UZ_ARRAY_SIZE(derivate_poly_coefficients),
.derivate_poly_coefficients.data = &derivate_poly_coefficients[0],
.coefficients.length = UZ_ARRAY_SIZE(coefficients),
.coefficients.data = &coefficients[0],
.initial_value = 5.0f,
.iterations = 5U,
.root_absolute_tolerance=0.05f
};
float output = uz_newton_raphson(config);
}
Approximating the root of the polynomial takes \(\approx 2 us\) with 5 iterations (result 3.316525) while 20 iterations take \(\approx 5 us\).
Approximating the root of the following polynomial with 15 iteration takes \(\approx 9 us\):