NewtonRaphson root approximation
The NewtonRaphson approximation is an approach for finding the (realvalued) roots of nonlinear equations. This is a relatively 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 nonnegative 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. The results can only be accurate if there are enough iterations for the approach to converge to the root. A balance between computational effort (i.e., the number of iterations) and the accuracy of the results have to be made by the user.
Note
The basic NewtonRaphson 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

bool check_for_absolute_tolerance
If true, the absolute tolerance of the approximated root will be checked. This relates to the root_absolute_tolerance config variable. If another method should be used to check the approximated root, set this to false

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 realvalued 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,
.check_for_absolute_tolerance = true,
.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 iterations takes \(\approx 9 us\):