How do you solve equations of any degree?

I have stuck solving this problem of financial mathematics, in this equation: $$\frac{(1+x)^{8}-1}{x}=11$$

I'm stuck in this eight grade equation: $$x^{8}+8x^{7}+28x^{6}+56x^{5}+70x^{4}+56x^{3}+28x^{2}+9x-11=0$$

But I cannot continue past this. This quickly lead me to find a general way of solving equations of any degree, but I couldn't find anything serious on the internet.

Do you know any simple methods to solve equations of any degree?

-
I don't believe there is except for numerical methods.... – user38268 Feb 16 '12 at 12:35
Most of computer algebra software will find you the roots of your polynomial, with any given precision. Don't expect a closed form result. Is this case, there is a single real root near 0.0892863. – Lierre Feb 16 '12 at 12:46
$$\displaystyle\prod_{i=0}^2 \left((x+1)^{2^i}+1\right) = 11$$ – pedja Feb 16 '12 at 12:58
You can ask WA. – lhf Feb 16 '12 at 13:05
@AlbertoFEM: Real-world computer root-finding algorithms are quite complex, since they must deal reliably with most things that are thrown at them. For a general article scan this. There are also special-purpose algorithms to deal with interest rate calculations such as yours. For hand calculations, the Secant Method is pretty good, but even simple Bisection, though slowish, will do the job for you. – André Nicolas Feb 16 '12 at 15:39

In financial mathematics, you're looking at a problem of compound interest rates (over $\mathbf{n}$ compoundment periods), where $100x$ is the percentage interest rate or yield and $\mathbf{x}$ the relative accrual rate per period. When $n$ is the number of compoundment periods per year, $\mathbf{nx}$ is the nominal annual interest rate and $\mathbf{f(x)}$ is a unitless quantity comparing the growth over $\mathbf{n}$ periods with the growth over just one period, and is applicable for example on a fixed-rate mortgage when $n=12$. In this context, $\mathbf{x \cdot f(x)}$ is the equivalent yearly rate, also known as annual percentage rate (APR), annual equivalent rate (AER), and other various combinations of $$\text{annual/-} \quad \text{effective/equivalent/-} \quad \text{interest/percentage/-} \quad \text{rate/yield}$$ (i.e. about 42 different wordings if we require at least one of the words 'annual', 'effective' or 'equivalent' -- to be clear what we're talking about --- but allow their order to be interchanged if using two).

Usually, the problem you are given does not have the $x$ in the denominator, making the problem easily solvable with logarithms and a ratio of future and present values. Most financial calculators have a way to solve this directly. There are surely good web resources as well. Once could program this in Javascript for use offline; someone probably already has. Without such a resource, or if programming it yourself, here's what you'd need (and don't need) to know about $f(x)$.

First some of the many alternate algebraic forms (for $x\in\mathbb{R}$ and $n\in\mathbb{Z}$ both positive): \eqalign{ f(x) &=\frac{(1+x)^n-1}{x} =\sum_{k=1}^n \href{http://en.wikipedia.org/wiki/Binomial_coefficient}{\binom{n}{k}} x^{k-1} } and factorizations (also perhaps of interest to math majors): \eqalign{ f(x) &=\frac{(1+x)^n-1}{(1+x)-1} =\prod_{k=1}^{n-1} \left(x+1- \href{http://en.wikipedia.org/wiki/Root_of_unity}{e^{\frac{2\pi ik}{n}}} \right) =\prod_{1<\href{http://en.wikipedia.org/wiki/Divisibility}{d|n}} \href{http://en.wikipedia.org/wiki/Cyclotomic_polynomial}{\Phi_d} \left(x+1\right) \cr &=\left(x+2\right)^{ \left\lfloor\frac{ n }2\right\rfloor -\left\lfloor\frac{n-1}2\right\rfloor} \prod_{k=1}^{\href{http://en.wikipedia.org/wiki/Floor_function}{ \left\lfloor\frac{n-1}2\right\rfloor}} \left(x^2+\left(2\sin\tfrac{k\pi}{n}\right)^2(x+1)\right) \cr } The first line gives the same form you gave as the starting point for this problem, i.e. the relative growth from $n$ compounding periods compared with the growth from one period. The second formula gives an expression for $f(x)$ as a monic polynomial of degree $n-1$, with the multipliers of the various powers of $x$ known as binomial coefficients.

The second line gives some alternate representations which are quite meaningful in the complex plane and in elementary number theory. These equations say that the roots of the polynomial $f(x)$ lie on a unit circle centered at $-1$ and are equally spaced to form a regular $n$-gon, with the exception of the removed root at $x=0$ in the denominator on the LHS. Each root $e^{\frac{2\pi ik}{n}}-1$ makes an angle of $\frac{2\pi ik}{n}$ with the positive real axis as it extends radially from $-1$. The formula on the RHS says that these roots can be grouped by the denominator of $\frac{k}{n}$ in lowest terms.

The third line performs a different grouping, into quadratic factors corresponding to pairs of complex conjugate roots, except for a linear factor $x+2$ for the root at $-2$ in case $n$ is even; this last optional bit is performed with the expression $\left\lfloor\frac{ n }2\right\rfloor -\left\lfloor\frac{n-1}2\right\rfloor =\href{http://en.wikipedia.org/wiki/Floor_function#Mod_operator}{(n-1)- 2\left\lfloor\frac{n-1}2\right\rfloor}$, which gives the remainder of $n-1$ modulo $2$, i.e. it is $0$ or $1$ depending on whether $n$ is odd or even. All coefficients here are again real, and all factors are irreducible over real fields. An interesting consequence of this, looking at $f(0)$, is that $$\prod_{k=1}^{\left\lfloor\frac{n-1}2\right\rfloor} \sin^2\tfrac{k\pi}{n} =\frac{n}{2^{n-1}}.$$

Next, $f$ is increasing for $x>0$ and $n>1$, as can be seen from its derivative: \eqalign{ f\,'(x) &=\frac{(x+1)^{n-1}\big((n-1)x-1\big)+1}{x^2} =\sum_{k=2}^n \href{http://en.wikipedia.org/wiki/Binomial_coefficient}{\binom{n}{k}} (k-1)x^{k-2} }

Extra notes:

• $f(x)<\frac{e^{nx}-1}{x}$ for $x>-1$. Both sides approach $n$ as $x \rightarrow 0$. The inequality actually holds for all $x>-1$ and is strict for $x\ne0$. This follows from observing that $\ln(1+x)$ is increasing and convex with tangent line $y=x$ at the origin.
• Defining $f(0)=n$ (or taking the binomial power sum as our definition) would make $f$ continuous at $0$, extending the domain to $(-1,\infty)$, since $f(x)$ approaches the derivative of the power function with power $n$ as $x \rightarrow 0$.
• For $n=1$, $f(x)$ is also $1$.
• $\frac{x}{n}f(\frac{x}{n}) \rightarrow e^x-1$ as $n \rightarrow \infty$.
• With $f(0)=0$, the derivative $f\,'(0)=\frac{n(n-1)}{2}$ exists and is continuous.
• $f\,'(x)=1$ for $n=2$.
• Solving $y=f(x)$ for $x$ given $y$ will have one solution for $y>n$ ($y\ge n$ if we allow $x=0$), and no solutions for $y<n$. There are a host of methods for rootfinding, and some specialized ones for polynomials. Newton's method, the simpler bisection method, a combination of bisection and secant resulting in a simplified version of Brent's method (as @JM pointed out), or a matrix method such as @NickAlger mentions could be used to find $x$. For Newton-s method, you would use the target function $F(x)=f(x)-y$, and a starting value such as $$x_0=\frac3{2n}\left(\sqrt{1+\frac83\left(\frac{y}{n}-1\right)}-1\right)$$ to iteratively find the root of $F$ by repeatedly setting $x_{n+1}=x_n+\Delta x_n$ for $$-\Delta x_n=\frac{F(x)}{F\,'(x)}=\frac{f(x)-y}{f\,'(x)}= \frac{x\left[(1+x)^n-(1+xy)\right]}{1-(1+x)^{n-1}\left[1-(n-1)x\right]}$$ (where I have omitted the $n$ subscript after each $x$ and encapsulated the negative sign of $\Delta x_n$ on the LHS for brevity). This may seem more complicated than bisection, but convergence is much more rapid, meaning fewer iterations are needed to get a precise answer. (The value of $x_0$ above comes from using the upper bound $\frac{e^{nx}-1}{x}$ as an estimate for $f(x)$, expanding $e^{nx}$ in a Taylor series, simplifying, and using the quadratic equation on the lowest remaining terms.)

Finally, in your problem, $n=8$, so $f(x)=y=11>8$ has solution $x \approx 0.08928634$, or $8.93$%.

Here is an example solution using Newton's method and sage (online), which is correct to about ten places after the third iteration (and to about a hundred after the seventh!):

n = 8
y = 11
F,f,x = var('F,f,x')
f = ((1+x)^n - 1) / x
F = x - x * ((1+x)^n - (1+x*y)) / (1 - (1+x)^(n-1) * (1-(n-1)*x))
x = 3/2/n * (sqrt(1 + 8/3*(y/n - 1)) - 1) # x_0
x = x.n(digits=100)
for i in range(10):
e = (f(x) - y).n(digits=100) # error
print i, x.n(), e.n()
x = (F(x)).n(digits=100) # next estimate
# i x e:
0 0.0776650429449553 -0.452683820096624
1 0.0895542025788610 0.0106779696847534
2 0.0892864798024252 5.56813083089398e-6
3 0.0892863400500602 1.51628362736157e-12
4 0.0892863400500221 1.12440509060997e-25
5 0.0892863400500221 6.18311776700343e-52
6 0.0892863400500221 -1.71448108692341e-99
7 0.0892863400500221 0.000000000000000
8 0.0892863400500221 -2.28597478256455e-100
9 0.0892863400500221 9.14389913025820e-100

-
Thank you for taking the time to build such a nice answer, I've learned a lot from it. And thanks the computer algorithm, that is one of the things I'm most interested in, related to this kind of problems. – Alberto Fernández Feb 17 '12 at 20:35
I'll just add a note that a hybrid algorithm interleaving Newton-Raphson and interval bisection could be built if deemed necessary; that way, one has the best of both worlds (the speed of NR and the sureness and safety of bisection). If instead of NR, the secant method is used in the hybrid method I described, the result is a simplified version of a famous algorithm due to Richard Brent. – J. M. Feb 18 '12 at 6:46
@JM: Thanks, I added some links for rootfinding, incorporating your note. – bgins Feb 18 '12 at 7:23

As has been pointed out above, from Galois theory in general there is no algebraic solution to polynomials of degree 5+.

But what about numerical solvers? Consider the polynomial $$p(x)=a+bx+cx^2+dx^3+x^4$$ and its companion matrix, $$A(p)=\left[\begin{matrix}0 & 0 & 0 & -a \\ 1 & 0 & 0 & -b \\ 0 & 1 & 0 & -c \\ 0 & 0 & 1 & -d \end{matrix}\right]$$

If you stare at it long enough, hopefully you can convince yourself that the eigenvalues of the companion matrix are exactly the zeros of the original polynomial. (hint, what is $\det(A-xI)$?)

So finding the zeros of a polynomial is equivalent to solving an eigenvalue problem, which is well studied numerically.

If you want to find a single one of the roots, consider using some form of inverse iteration/Rayleigh quotient iteration. If you want to find all the roots, consider using some variant of the QR algorithm (not to be confused with QR decomposition, which is used inside the QR algorithm).

-
"...consider using some form of inverse iteration/Rayleigh quotient iteration." - and this is essentially the Jenkins-Traub algorithm for finding the roots of a polynomial. – J. M. Feb 17 '12 at 0:25
In my experience, students studying financial mathematics have not studied eigenvalues. – Gerry Myerson Feb 17 '12 at 1:49
@J.M. Thanks for that comment! I've heard people casually mention the Jenkins-Traub algorithm, but never looked into it. Cool to see that it's actually something straightforward despite the intimidating name. – Nick Alger Feb 17 '12 at 2:29
@GerryMyerson From what I've seen financial mathematics can go pretty deep. Probability, PDE's, optimal control, convex analysis... Not knowing about eigenvalues seems like bringing a knife to a gunfight.. – Nick Alger Feb 17 '12 at 2:29
@Nick: well, I must say books present it as if it were extremely complex. But one should really look at the original papers by Jenkins and Traub on this, where they explain the intimate connection between their algorithm and Frobenius companion matrices. In this answer, I talk about one of the ancestors of the Jenkins-Traub algorithm, due to Bernoulli. A similar analysis could be done for Jenkins-Traub proper. – J. M. Feb 17 '12 at 2:33

First off, let me say that the polynomial you gave does not match up with your original problem. So, I will solve it based on your original problem and not the polynomial you gave. Perhaps you typed it wrong.

Second off, since this is financial mathematics, there are most likely assumptions that go beyond the pure math. The point is, you don't need to know general methods for solving any polynomial equation. You need methods for very specific types of situations.

$x$ here represents an interest rate. And, it is often assumed that interest rates are positive. This simplifies the solution considerably. But, even without that assumption, I can tell by looking at your equation what your original problem was. Your original problem was that 1 dollar is put into an account at the end of each year for 8 years. The account accumulates at interest rate $x$, or $100x\%$, and the accumulated value at time 8 is 11. Since you end up with more money than you put in, it is definitely reasonable to assume your interest rate is positive. In fact, since all the payments by you were done ahead of the payment at time 8 by the bank of 11, there is guaranteed to be only one real solution, and it is positive clearly from the context.

So, now your job is just to figure out the one and only solution. We use the Intermediate Value Theorem. It says, if a function is continuous on some interval, and if the function is negative at one point and positive at another point, then it must be 0 somewhere in between. So consider

$$f(x) = \frac{(1 + x)^8 - 1}{x} - 11.$$

It is not continuous everywhere, because of division by 0 when $x = 0$, but it is continuous for $x > 0$ and therefore the Intermediate Value Theorem applies if we are only searching for a solution to $f(x) = 0$ for positive $x$.

Plug in a couple small numbers, like 0.05 and 0.2. $f(0.05) = -1.45089$ and $f(0.2) = 5.49908$. Now, we know the solution is between 0.05 and 0.2 by the Intermediate Value Theorem. Pick a number in between, like 0.1. $f(0.1) = 0.435888$. Since this is positive, our root is between 0.05 and 0.1. We're getting close. Try 0.075. $f(0.075) < 0$. This tells us our solution is between 7.5% and 10%. Try 0.09. $f(0.09) > 0$, so our solution is between 0.075 and 0.09. Try 0.08. You get $f(0.08) = -0.363372$. Continue in this manner and you'll eventually narrow down the answer to as many decimal places as you want. Of course, it's slow. This method is basically the bisection method, except I didn't always pick my next number to be right in the middle of the previous bounds. You could also try Newton's method. You'll eventually get x = 0.0892863...

-
At the very least we would assume $1 + x \geq 0$, or $x \geq -1 = -100\%$, because you can't lose more than 100% of your investment. This is enough to guarantee a unique solution, since all the payments by you were equally spaced and were done before the one payment by the bank. This is mentioned in the Wikipedia article Internal rate of return. – Graphth Feb 17 '12 at 14:37
By the way, another way to solve this problem is to just use your financial calculator and the IRR function, if it has it. Or, there are other options, if you don't have a financial calculator. For example, I have a TI-84 which has financial math app or something, and it can do IRR. – Graphth Feb 17 '12 at 14:42
Thanks for this great explanation, I think its a good way of solving the problem without a computer, if you happen to don't have any around. – Alberto Fernández Feb 17 '12 at 20:32

I don't know of a universal method to solve any equation. If you have the luxury to choose any method to solve an equation, and you are not particularly interested in advanced math, you could try to plot the equation either by hand or use free software on the net. to give you at least a starting solution.

$\frac{(1+x)^{8}-1}{x}=11$
Using plots of this sort only shows real solution (not complex ones). In this case $x=.089311$ is a solution to the equation (good for 3 digits after the decimal point).