Some numerical methods to calculate the zeros of a polynomial (part 1).
As an example I will examine the equation
x2 - x - 1 = 0
Method 1:
Write the equation in the form
x = 1 + 1/x
Substitute this equation into itself. This yields x = 1 + 1/(1 + 1/x).
Repeat this procedure again and again. This will lead to the supposition
Finite parts (continued fractions) converge to the positive zero of the equation.
Method 2:
Denote the equation in de form x = (1 + x)
Applying the trick of repeated substitution yields the supposition
x = (1 + (1 + (1 + ...)))
Finite parts converge to the positive zero.
The first method is often applicable for polynomials of second degree, the second method is often applicable for polynomials of degree 2 or 3.
The third method may often be used for polynomials of any degree.
Method 3:
Multiply the equation by xn: xn+2 = xn+1 + xn
With Gn = xn this yields Gn+2 = Gn+1 + Gn for each n. n -> xn is not the only function which satisfies the recursion (n -> Fn is another example). Now, we pose the question if it is possible to retrieve the value of the positive zero
by using only the recursion. Well, let us divide the recursion by Gn Gn+2/Gn = Gn+1/Gn + 1 or in other words
(Gn+2/Gn+1)* (Gn+1/Gn) = Gn+1/Gn + 1.
We note that if Gn+1/Gn converges to a, then a2 = a + 1, so a is the required zero.
So, begin with two starting values, e.g. G0 = 1, G1 = 2. Then Gn+1/Gn converges to a zero.
Method 1 is closely related to this method, for the finite continued fractions from method 1 have the form Fn+1/Fn.
Usually we solve the quadratic equation to obtain a formula for the Fibonacci sequence. Here we convert the question and use the Fibonacci sequence to find a numerical solution of a quadratic equation.
This method is often applicable for computing a zero of a polynomial. For example, let us find a zero of the following equation
x3 - 3x2 + 2x - 1 = 0
The corresponding recursion is Gn+3 = 3Gn+2 -2Gn+1 + Gn.
If G1 = 1, G2 = 1, G3 = 0, then G10/G9 = 2,3265. The real zero of the equation is 2,3247.
(1 + x)