Can we use the inverse quadratic interpolation for this equation's non-real roots with these points?

Question

$$f(x)=x^4+2x^3+5x^2+5x-3=0$$

I've chosen these values as guessed values: $$(x,f(x)) --> (-1+4i, 172+116i), (1+2i, -42+2i), (-3+i, 14-69i)$$

Am I doing something wrong or can't we obtain a non-real root with these starting points? What am I missing or what's the problem with these points?

Answer 1

Inverse quadratic iteration was intended to be an improvement of the secant root computation in the secant method, regula falsi, first Dekker method, using a third point to somewhat capture the curvature of the function and thus get closer root approximations. Thus quadratic in the regular sense in Muller's method, inverse quadratic in Dekker's and Brent's method, also hyperbolic curves were explored by them, exponential approximation in Ridders method.

Conceptually, this works best, or only, if a root guaranteed to be inside or close to the convex hull of the 3 sampling points, so that the function approximation is more interpolation than extrapolation. It also helps if the function is almost linear in this region. In the real methods, a bracketing interval (Dekker, Brent) is such a root guarantee. Outside this set, the inverse quadratic and the original polynomial function will be wildly different, so that the value at zero of the inverse quadratic has little to no relationship to any root of the original function.

---

The inverse quadratic iteration can be realized in python as

def f(z): return np.polyval([1,2,5,5,-3],z)

def invquad(z,w): 
    def term(i,j,k): return z[i]*w[j]*w[k]/(w[i]-w[j])/(w[i]-w[k])
    return term(0,1,2)+term(1,2,0)+term(2,1,0)

def invquaditer(z1,z2,z3):
     z = [z1,z2,z3]
     w = [ f(zz) for zz in z ]
     for zz,ww in zip(z,w): print(f"     z = {zz:30.12f},  f(z) = {ww:30.12g}")
     for k in range(30):
         zz = invquad(z[-3:],w[-3:])
         z.append(zz);
         w.append(f(zz));
         if k%5==4: print(f"{k+1:3}: z = {z[-1]: 30.12f},  f(z) = {w[-1]: 30.12g}")

invquaditer(-1+4j,1+2j,-3+1j)

with the (shortened) result

     z = -1.000000000000+4.000000000000j,  f(z) =                       172+116j
     z =  1.000000000000+2.000000000000j,  f(z) =                         -42+2j
     z = -3.000000000000+1.000000000000j,  f(z) =                         14-69j
  5: z =  4.317538320268+0.091310253210j,  f(z) =   619.062884775+43.9929910763j
 10: z =  2.611476826121-0.559031334510j,  f(z) =   107.136336831-77.9195795091j
 15: z =  0.555953546644-0.631985686099j,  f(z) =  -2.14611625211-7.21371931414j
 20: z =  0.404523365865-0.000009492569j,  f(z) = -1.79088680259e-05-9.76961198257e-05j
 25: z =  0.404525105890-0.000000000000j,  f(z) =           0-2.85657089322e-16j
 30: z =  0.404525105890+0.000000000000j,  f(z) = -1.37667655054e-14+4.57051342915e-15j

It is visible that the iteration first moves chaotically away from the starting points. Apparently the iterations for all permutations of the initial points converge to the same real root, which could mean that this root has the largest basin of attraction, or it could just be a coincidence.

Answer 2

I suppose that you are speaking about Brent's method.

For the present case, the process seems to diverge quite fast. Hoping no mistake in my coding, the first iterates are $$\left( \begin{array}{ccc} n & x_n & f(x_n) \\ 1 & -1+4 \,i & 172+116 \,i \\ 2 & 1+2 \,i & -42+2 \,i \\ 3 & -3+ \,i & 14-69 \,i \\ 4 & -0.233501+0.851131 \,i & -6.23677+1.84608 \,i \\ 5 & -0.445646+0.740844 \,i & -6.00227+0.934791 \,i \\ 6 & -0.444457-0.750972 \,i & -6.0374-0.949373 \,i \\ 7 & 1.52232 +10.0378 \,i & 7355.74 -7697.24 \,i \end{array} \right)$$

Changing the values of $(x_1,x_2,x_3)$ the process does converge $$\left( \begin{array}{ccc} n & x_n & f(x_n) \\ 1 & -0.5+ \,i & -6.9375+ \,i \\ 2 & -0.5+2 \,i & -2.4375+2 \,i \\ 3 & -0.5+3 \,i & 45.0625 +3 \,i \\ 4 & -0.0363912+2.38487 \,i & 1.93196 -14.0789\, i \\ 5 & -0.451927+2.10997 \,i & -0.204939+1.01463 \,i \\ 6 & -0.420599+2.12696 \,i & 0.125128 +0.257341\, i \\ 7 & -0.409254+2.12283\, i & -0.0052756+0.00522175 \,i \\ \end{array} \right)$$

As you can see, even when it works, the path to the solution is really chaotic.

I should not recommend to use Brent's mathod for complex roots except if you have very good points to start with and this is very difficult in the complex domain.

For comparison, let us try Newton method $$\left( \begin{array}{cc} n & x_n \\ 0 & -1+4 \,i \\ 1 & -0.836181+3.13317 \,i \\ 2 & -0.687862+2.54836 \,i \\ 3 & -0.543257+2.21764 \,i \\ 4 & -0.432473+2.11769 \,i \\ 5 & -0.408802+2.12256 \,i \\ 6 & -0.409065+2.12308 \,i \end{array} \right)$$