Greedy Algorithm For Egyptian Fractions - Approximation of Polynomial Roots

Approximation of Polynomial Roots

Stratemeyer (1930) and Salzer (1947) describe a method of finding an accurate approximation for the roots of a polynomial based on the greedy method. Their algorithm computes the greedy expansion of a root; at each step in this expansion it maintains an auxiliary polynomial that has as its root the remaining fraction to be expanded. Consider as an example applying this method to find the greedy expansion of the golden ratio, one of the two solutions of the polynomial equation P₀(x) = x2 - x - 1 = 0. The algorithm of Stratemeyer and Salzer performs the following sequence of steps:

1. Since P₀(x) < 0 for x = 1, and P₀(x) > 0 for all x ≥ 2, there must be a root of P₀(x) between 1 and 2. That is, the first term of the greedy expansion of the golden ratio is 1/1. If x₁ is the remaining fraction after the first step of the greedy expansion, it satisfies the equation P₀(x₁ + 1) = 0, which can be expanded as P₁(x₁) = x₁2 + x₁ - 1 = 0.
2. Since P₁(x) < 0 for x = 1/2, and P₁(x) > 0 for all x > 1, the root of P₁ lies between 1/2 and 1, and the first term in its greedy expansion (the second term in the greedy expansion for the golden ratio) is 1/2. If x₂ is the remaining fraction after this step of the greedy expansion, it satisfies the equation P₁(x₂ + 1/2) = 0, which can be expanded as P₂(x₂) = 4x₂2 + 8x₂ - 1 = 0.
3. Since P₂(x) < 0 for x = 1/9, and P₂(x) > 0 for all x > 1/8, the next term in the greedy expansion is 1/9. If x₃ is the remaining fraction after this step of the greedy expansion, it satisfies the equation P₂(x₃ + 1/9) = 0, which can again be expanded as a polynomial equation with integer coefficients, P₃(x₃) = 324x₃2 + 720x₃ - 5 = 0.

Continuing this approximation process eventually produces the greedy expansion for the golden ratio,

(sequence A117116 in OEIS).