Newton-Raphson root approximation

The Newton-Raphson approximation is an approach for finding the (real-valued) 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 non-negative integer power: I.e., functions \(P(x)\) with the following definition

\[\sum^n_{k=0} a_k x^k=a_n x^n+a_{n-1}x^{n-1}+\dots + a_2 x^2 + a_1 x+a_0\]

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 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

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 real-valued root, or the initial value was not choosen in a way that leads to convergence.

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.

\[\begin{split}r &= x_0 + h \approx x_0 - \frac{f(x_0)}{f'(x_0)}\\ x_1 &= x_0 - \frac{f(x_0)}{f'(x_0)}\\ x_2 &= x_1 - \frac{f(x_1)}{f'(x_1)}\\ x_3 &= x_2 - \frac{f(x_2)}{f'(x_2)}\end{split}\]

Consider this equation:

\[\begin{split}f(x) &= x^4 - 5x^2 - 20.5x + 2\\ f'(x) &= 4x^3 - 10x - 20.5\\\end{split}\]

This can be represented differently:

\[\begin{split}f(x) &= a_4 \cdot x^4 + a_3 \cdot x^3 + a_2 \cdot x^2 + a_1 \cdot x + a_0\\ f'(x) &= a_4 \cdot 4x^3 + a_3 \cdot x^2 + a_2 \cdot 2x + a_1\\\end{split}\]

With the coefficients:

\[\begin{split}a_4 &= 1 \\ a_3 &= 0 \\ a_2 &= -5 \\ a_1 &= -20.5 \\ a_0 &= 2\end{split}\]

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

\[\boldsymbol{a}=\begin{bmatrix} a_0 & a_1 & a_2 & a_3 & a_4 \end{bmatrix}\]

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

\[x^4-5.0 \cdot x^2-20.5x+2\]

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\):

\[f(x)= x^{10} - x^8 + 8 \cdot x^6 - 24 \cdot x^4 + 32 \cdot x^2 - 48\]

Sources

1

Newton’s Method for Finding Equation Roots, A. Schlegel

Functions