Several classes of quadratically convergent algorithms for solving the matrix equation AX²+BX+C = 0, A,B,C,X Î \mathbb R^n×n have been recently introduced and analyzed in the literature (say, cyclic reduction, logarithmic reduction, Graeffe iteration, invariant subspace iteration). Their high convergence speed is paid with the loss of the self-correcting behavior.

Here we introduce a new family of self-correcting fixed point iterations X_i+1^(k) = F_k(X_i^(k)) depending on a parameter k Î \mathbb N with the property that X^(k)_i+1 is the Schur complement of X^(k)_i in the 2^k×2^k block tridiagonal block Toeplitz-like matrix T having superdiagonal blocks C, lower diagonal blocks A and diagonal blocks equal to B except for the block in position (1,1) which is equal to X^(k)_i.

We show that if det(Al²+Bl+C) has roots x₁,¼,x_2n such that |x₁| £ ¼ £ |x_n| < 1 < |x_n+1| £ ¼ £ |x_2n| (assuming roots at infinity if A is singular) then the sequence {X^(k)_i}_i converges to the minimal solution X with linear speed where the average reduction of the error per step is roughly |[(x_n)/( x_n+1)] |^n2k whatever is the initial matrix X₀^(k).

By using a divide and conquer approach we show that the cost of the iteration as a function of k grows as log₂ k. Moreover the iteration is self-correcting.

From the properties of the Schur complement and from the displacement theory it follows that the cost of this iteration as function of n is reduced to O(nlog² n) if the blocks A,B and C are such that the matrix T is band Toeplitz, where the problem of solving the matrix equation reduces to factoring a polynomial. In fact, for any value of k all the iterates X_i^(k) keep displacement rank bounded by a constant (2 for X₀ = B).

From this class of functional iteration we deduce also a new quadratically convergent iteration which is not self-correcting.

Finally we show how to apply these techniques for the spectral factorization of multivariate polynomials.

Footnotes:

¹ Joint work with Luca GEMIGNANI.