Can we find all roots by using the inverse quadratic interpolation?

Question

Can we find all the real roots of a function by using the inverse quadratic interpolation? How can we do that?

Can we find complex roots?

How can we find any root of a function having roots we have no guess about by using that algorithm, how should we start?

Answer 1

Inverse Quadratic Interpolation (IQI) is described on the Wiki and in Section 4.5. Note some of the pitfalls mentioned there.

Both of the references give the iteration formula. This method can be used to find all roots of a polynomial, whether they are real or complex.

As an example, take $f(x) = 4 x^3-16 x^2+17 x-4$. I usually start by plotting the function to get an idea of where the roots are for each of the three initial points needed to find each one. The plot is

I will also use a professional package like Matlab or Mathematica to find the roots to high precision for comparison purposes (you can also find exact roots using the Cubic Equation). The three real numerical roots are

$ x = 0.32853845861141489597 \\ x = 1.2646582900644196963 \\ x = 2.4068032513241654077$

Using IQI, for the first root, try $x_0 = 2, x_1 = 1, x_2 = 0$ (look at how many iterations it took to converge and compare to Newton-Raphson or Brent's Method)

• $x_0 = 2.0000000000000000$
• $x_1 = 1.0000000000000000$
• $x_2 = 0.0000000000000000$
• $x_3 = 1.8666666666666670$
• $x_4 = 1.7779534353544020$
• $x_5 = -2.3569618956708820$
• $x_6 = 0.4784180205707038$
• $x_7 = 0.9077436276533210$
• $x_8 = -0.6942151494047211$
• $x_9 = -0.6478506170435796$
• $x_{10} = 0.7821913121990205$
• $x_{11} = 0.6535526131045359$
• $x_{12} = -5.0833208694930590$
• $x_{13} = -5.4278849866262590$
• $x_{14} = 0.6414926269507966$
• $x_{15} = 0.6295990778705232$
• $x_{16} = -0.2696592988054403$
• $x_{17} = -0.1734466885955047$
• $x_{18} = 0.4598565766321493$
• $x_{19} = 0.3761056340942091$
• $x_{20} = 0.3197243223248978$
• $x_{21} = 0.3282034018254270$
• $x_{22} = 0.3285391069447241$
• $x_{23} = 0.3285384586194860$
• $x_{24} = 0.3285384586114148$
• $x_{25} = 0.3285384586114150$
• $x_{26} = 0.3285384586114149$
• $x_{27} = 0.3285384586114150$

Using IQI, for the second root, try $x_0 = .4, x_1 = .6, x_2 = .8$

• $x_0 = 0.4000000000000000$
• $x_1 = 0.6000000000000000$
• $x_2 = 0.8000000000000000$
• $x_3 = 1.4655175639021420$
• $x_4 = -0.0269635090089693$
• $x_5 = 1.3587749241884970$
• $x_6 = 1.2072677833794600$
• $x_7 = 1.2757986938031020$
• $x_8 = 1.2645991028116670$
• $x_9 = 1.2646583297719020$
• $x_{10} = 1.2646582900643940$
• $x_{11} = 1.2646582900644190$

Using IQI, for the first root, try $x_0 = .4, x_1 = .6, x_2 = .8$

• $x_0 = 3.0000000000000000$
• $x_1 = 2.8000000000000000$
• $x_2 = 2.6000000000000000$
• $x_3 = 2.4456842900259870$
• $x_4 = 2.4111121815239560$
• $x_5 = 2.4068782724818820$
• $x_6 = 2.4068032896187870$
• $x_7 = 2.4068032513242060$
• $x_8 = 2.4068032513241660$

For a complex example, lets use $f(x) = x^2 + 1$, which has the imaginary roots $x = \pm ~ i$.

Using IQI, for the first root, try $x_0 = .5 + I, x_1 = .6 + I, x_2 = .7 + I$ ($I$ is imaginary)

• $x_0 = 0.5000000000000000+ 1.0000000000000000 I$
• $x_1 = 0.6000000000000000+ 1.0000000000000000 I$
• $x_2 = 0.7000000000000000+ 1.0000000000000000 I$
• $x_3 = -0.0265008880606977+ 0.9324794583256370 I$
• $x_4 = -0.0062809706136977+ 1.0111496938882190 I$
• $x_5 = -0.0002495550153420+ 0.9998210667715290 I$
• $x_6 = 1.1033465890063210 \times 10^{-7}+ 1.0000000998346370 I$
• $x_7 = -2.7745525061489970 \times 10^{-13}+ 0.9999999999999160 I$
• $x_8 = 5.2939559203393770 \times 10^{-23}+ 1.0000000000000000 I$
• $x_9 = 0.0000000000000000+ 1.0000000000000000 I$

Using IQI, for the second root, try $x_0 = .5 - I, x_1 = .6 - I, x_2 = .7 - I$ ($I$ is imaginary)

$ x_ 0 = 0.5000000000000000- 1.0000000000000000 I$
$ x_ 1 = 0.6000000000000000- 1.0000000000000000 I$
$ x_ 2 = 0.7000000000000000- 1.0000000000000000 I$
$ x_ 3 = -0.0265008880606977- 0.9324794583256370 I$
$ x_ 4 = -0.0062809706136977- 1.0111496938882190 I$
$ x_ 5 = -0.0002495550153420- 0.9998210667715290 I$
$ x_ 6 = 1.1033465890063210 \times 10^{-7}- 1.0000000998346370 I$
$ x_ 7 = -2.7745525061489970 \times 10^{-13}- 0.9999999999999160 I$
$ x_ 8 = 5.2939559203393770 \times 10^{-23}- 1.0000000000000000 I$
$ x_ 9 = 0.0000000000000000- 1.0000000000000000 I$

Your last question is not easy to answer because there are pros and cons to any numerical algorithm. Sometimes, it ends up being trial and error due to the problem itself. You might be interested in reviewing the various methods of root finding.