Numerical methods for approximating roots of degree $n+1$ polynomials

Question

I am wondering how exactly do you use numerical methods to approximate roots of any degree $n+1$ polynomials? Like how would you solve $x^{n+1}+2x^n+1=0$?

Answer 1

It might be helpful if you look at the problem this way. One thing we know how to do for sure is to solve linear equations (and systems of linear equations). It follows from the rules of arithmetic and introduction of rational numbers that:

$$a x=b \quad \Rightarrow \quad x=\frac{b}{a}$$

But what do we do for general nonlinear equations? Well, one thing might be to guess the solution and then try to find the error, assuming it's small. Which usually allows us to reduce the equation to a linear one.

Take your equation for example.

$$x^{n+1}+2x^n+1=0$$

Let's make a guess that: $$x=x_0+\delta$$

$$\delta \ll x_0$$

What does it mean that $\delta$ is small? It means we can drop any terms proportional to $\delta^2, ~ \delta^3, ~ \delta^4$ etc., compared to $x_0$. Because from the above:

$$\frac{\delta}{x_0} \ll 1$$

And you likely know from experience that numbers less than one become smaller and smaller as you raise them to greater and greater powers.

Now we substitute our guess inside the equation:

$$(x_0+\delta)^{n+1}+2(x_0+\delta)^n+1=0$$

From the usual algebra and dropping every small term as stated above, we obtain:

$$x_0^{n+1}+(n+1)x_0^n \delta+2x_0^n+2nx_0^{n-1}\delta+1=0$$

Now look at the equation we got. First, the only unknown here is $\delta$, because we already guessed some value for $x_0$. And this equation is linear in $\delta$! We already know how to solve it!

$$\delta=-\frac{x_0^{n+1}+2x_0^n+1}{(n+1)x_0^n+2nx_0^{n-1}}$$

And from our guess we have:

$$x_1=x_0+\delta=x_0-\frac{x_0^{n+1}+2x_0^n+1}{(n+1)x_0^n+2nx_0^{n-1}}$$

Did we solve the equation? No! Because by dropping the small terms from the equation we introduced another error! Which means we have to repeat the process again with $x_1$:

$$x_2=x_1+\delta_1$$

(Here's where the iterations appear. We can't do without them because our initial guess always contains some error as you can see from the above. The best we can do is to make the error as small as we want).

---

This is in essence Newton's method which was linked in the comments. We are just making the nonlinear problem linear and hope it will lead us to the good approximation after a number of iterations. And usually it does. Surprisingly, the initial guess $x_0$ can be very far from the true one in most cases, and we will still get to the root. Some root! Because in polynomial equations we have several roots and which one we get depends on the initial guess of course.

Answer 2

As said in answer and comments, as soon as $n\geq 4$, you need numerical methods for solving the equation.

However, for shortcut calculations, you can make reasonable aproximations. Considering the root which is close to $-2$, you could make a Taylor expansion of the equation around this value and get $$x_n\approx-2-(-2)^{-n}\tag 1$$ For a better approximation, you could use Padé pproximants and the simplest one would give $$x_n\approx-2-\frac{2}{n+(-1)^n\, 2^{n+1}} \tag 2$$

Checking for a few values of $n$ $$\left( \begin{array}{cccc} n & \text{exact} & (1) & (2) \\ 4 & -2.055967397 & -2.062500000 & -2.055555556 \\ 5 & -1.965948237 & -1.968750000 & -1.966101695 \\ 6 & -2.014942526 & -2.015625000 & -2.014925373 \\ 7 & -1.991964197 & -1.992187500 & -1.991967871 \\ 8 & -2.003846663 & -2.003906250 & -2.003846154 \\ 9 & -1.998029470 & -1.998046875 & -1.998029557 \\ 10 & -2.000971830& -2.000976563 & -2.000971817 \\ 11 & -1.999510402 & -1.999511719 & -1.999510404 \\ 12 & -2.000243784 & -2.000244141 & -2.000243784 \end{array} \right)$$ Notice that both $(1)$ and $(2)$ provide rational numbers. $$\left( \begin{array}{ccc} n & (1) & (2) \\ 4 & -\frac{33}{16} & -\frac{37}{18} \\ 5 & -\frac{63}{32} & -\frac{116}{59} \\ 6 & -\frac{129}{64} & -\frac{135}{67} \\ 7 & -\frac{255}{128} & -\frac{496}{249} \\ 8 & -\frac{513}{256} & -\frac{521}{260} \\ 9 & -\frac{1023}{512} & -\frac{2028}{1015} \\ 10 & -\frac{2049}{1024} & -\frac{2059}{1029} \\ 11 & -\frac{4095}{2048} & -\frac{8168}{4085} \\ 12 & -\frac{8193}{4096} & -\frac{8205}{4102} \end{array} \right)$$