I have forgotten

• http://facebook.com/
• https://www.google.com/accounts/o8/id
• https://me.yahoo.com COST (GBP) 1.49 0.00 0

# Bernoulli

viewed 2859 times and licensed 112 times
Calculates the zeros of a polynomial using Bernoulli's algorithm.
Controller: CodeCogs Contents  C++

## Bernoulli

 std::vectorbernoulli( const std::vector& polynomial )
Bernoulli's method exploits the connection between a linear difference equation and the zeros of its characteristic polynomial in order to find the zeros of a polynomial without knowing crude first approximations. Given the polynomial the difference equation which has p as its characteristic polynomial is given as

Given any starting values , the corresponding solution of the previous equation can be found numerically using the recurrence relation

If we suppose that the zeros of p all have multiplicity 1 (i.e. distinct zeros) then the solution can be expressed in the form

The coefficients can be computed if the zeros are known. But since these are not known, the coefficients are unknown. However, the quotients using the previous equation, are analytically represented by

If a polynomial p of degree K has zeros , not necessarily distinct, then the zero is called dominant if its modulus is strictly greater than the moduli of the other zeros, i.e. for all . Now suppose the above polynomial p has a single dominant zero, and let this be for our case (this zero will be real if the coefficients of p are real). Also, assume that the starting values of of the solution are chosen so that . It can be shown that this condition is always satisfied if the starting values are chosen so that

Under these assumptions, we may write the quotients as

Furthermore, and it follows that

Having obtained this zero, the polynomial is deflated and the procedure is repeated. Thus this method can only furnishone or two zeros of a given polynomial at a time, and these zeros are those of largest or smallest magnitude. So, if a zero of intermediate modulus is desired, it is necessary to compute all larger (or all smaller) zeros and then remove them from the polynomial by deflation. Also if has nearly the same magnitude as the convergence process is very slow. However, if the zero of largest or smallest magnitude is the zero that is desired and is distinct, Bernoulli's method can be useful.

This algorithm finds the roots of the polynomial given as an array of coefficients and returns them wrapped inside a C++ vector object. The method described above has been used.

## References:

• Claude Nowakowski, "Methodes de calcul numerique", PSI Editions, France, 1981
• Wankere R. Mekwi, "Iterative Methods for Roots of Polynomials", Exeter College, University of Oxford

### Example 1

#include <codecogs/maths/rootfinding/bernoulli.h>

#include <iostream>
#include <iomanip>

int main()
{
double A = { 1, 2, -13, -14, 24 };

std::vector<double> poly(A, A + 5), roots = Maths::RootFinding::bernoulli(poly);

std::cout << "The roots of the polynomial are : " << std::endl << std::endl;
int i;
for (i = 0; i < roots.size(); i++)
{
std::cout << std::setw(5) << "x_" << i << " = ";
std::cout << std::setprecision(12) << roots[i] << std::endl;
}
return 0;
}
Output:
The roots of the polynomial are :

x_0 = -3.99998329472
x_1 = 3.00000133652
x_2 = -2.00001264664
x_3 = 0.999994604828

### Parameters

 polynomial the coefficients of the polynomial given as a C++ vector object

### Authors

Lucian Bentea (August 2005)
##### Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.