Finding all the roots of a function - Numerical methods

Question

I'm trying to find all the roots of a function f(x) without algebraically solving the function.

What I have done so far: I attempted to use a numerical method, more specifically the secant method to find the roots (x=1,2,3) of the function f(x)=x^3-6x^2+11x-6

Say the secant method found a root to be at x=1. Now to prevent the secant method from finding the same root again, I use deflation to remove that root. So the new function without the root at x=1 is g(x)=f(x)/(x-1)

g(x) graph

However the problem is that the secant method will only approximate the root and not find its exact value. So it may find the root is very close to 0.99. Now that is accurate enough for the task so I want to move on to the next root. However the graph h(x)=f(x)(x-0.99) still has a root at x=1 and the secant method may find x=1 as a root again and not move onto the next root.

h(x) graph

How can I find all the roots of the function?

Answer 1

You could try the Durand-Kerner (Weierstraß) method. This would require to use complex numbers in the iterates, since this method approximates all roots of a polynomial simultaneously.

Staying with your method, the deflation in the secant method under inexact roots will still almost certainly succeed since the region where the secant method would converge to the previous root is about as small as the approximation error of the inexact roots.

Answer 2

When you deflate the polynomial of degree $n$, I think that you need to work with the polynomial of degree $n-1$ whatever the accuracy could be for the previous root.

Let us consider your case for which you found a first root (let us name it $a$). Then $$x^3-6x^2+11x-6=(x-a)(x^2+bx+c)$$ and the coefficients are such that $$b+6=a \qquad c=11+ab\qquad ac=6$$ For sure, if $a$ is the exact solution, one of these equations is redundant. So, for simplicity, let us use the first and the third which give $$b=a-6\quad c=\frac 6a$$

Now, depending on the value we retain for $a$, the solutions will be $$\left( \begin{array}{cc} a \\ 0.99000 & \{\{x\to 2.04195\},\{x\to 2.96805\}\} \\ 0.99900 & \{\{x\to 2.00402\},\{x\to 2.99698\}\} \\ 0.99990 & \{\{x\to 2.00040\},\{x\to 2.99970\}\} \\ 0.99999 & \{\{x\to 2.00004\},\{x\to 2.99997\}\} \end{array} \right)$$