Fibonacci

Some numerical methods for calculating the zeros of a polynomial (part 2).

We have seen in method 1 that the positive zero of the equation x² - x - 1 = 0 can be written in the form of a continued fraction, namely as
.
We will study a method, which produces the largest real zero of a polynomial equation like x³ - 3x² + 2x - 1 = 0 (see previous page) in the form of a continued fraction.
We only consider continued fractions of the following kind: All numerators equal 1 and all denominators are positive integers,
with the exception of the number in front of the continued fraction. That number may be any integer (like e.g. in -3 + 1/7).
When we talk about continued fraction in this context, we allways mean this kind of continued fractions.
It is wellknown that every fraction can be written in the form of a finite continued fraction, and every irrational number as an infinite continued fraction.
When you want to write a number in the form of a continued fraction, the first thing you do is to write the number as in integer plus a remainder. The remainder must be smaller than 1. Then 1/remainder is larger than 1. So this number can be written as in integer plus remainder. Etc. See next example, the fraction 516/125:

The subfractions

are called convergents or approximants.
So the approximants of 516/125 are 4, 29/7, 33/8, 161/39, 516/125.

Now it is time to find the largest real number of the equation x³ - 3x² + 2x - 1 = 0:
When you substitute x=2 into the lefthand side of the equation, then you get -1 and when you substitute x=3, then the result is +5. Thus the zero is 2 + a remainder, with a remainder between 0 and 1. Now write x = 2 + 1/y and substitute this into the equation. This yields the equation: y³ - 2y² - 3y - 1 = 0.
Substitution of y=3 and y=4 shows that y is a little larger than 3. Substitute y = 3 + 1/z.
So x = 2 + 1/(3 + 1/z). It will be clear how this continues.
This yields x = 2 + 1/(3 + 1/(12+...)).
Now 2 + 1/(3 + 1/12) = 2.3243... and that is a good approximation for the real zero 2,3247...
Notice that after 3 iterations the result is much better than after 7 iteration using method 3 of the previous page!