A Bairstows type method for trigonometric polynomials

Numer. Math. 67: 251–259 (1994)

Numerische Mathematik c Springer-Verlag 1994

A Bairstow’s type method for trigonometric polynomials Ion Ichim1 , Ionel Molnar2 1 2

Faculty of Mathematics, University of Bucharest, 14 Academiei, RO-70109 Bucharest, Romania Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, RO-70700 Bucharest, Romania

Received November 11, 1992/Revised version received May 13, 1993

Summary. We construct in this paper an analogous method to Bairstow’s one, for trigonometric polynomials with real coefficients. We also present some numerical examples which illustrate this method. Mathematics Subject Classification (1991): 65H The method of Bairstow for algebraic polynomials with real coefficients is well known and it is used in practice successfully. It is described in many books of numerical analysis and articles, e.g. [5, 6, 1]. In this paper we present an analogous method to that of Bairstow, for trigonometric polynomials with real coefficients. To this purpose, we prove the results which allow both the construction of the method and the elaboration of an algorithm and we also present a few numerical examples which prove the efficiency of the method. e e [x] and R e [x] defined by Let us consider the sets R

Re [x] :=

(

u(x) | u(x) =

i=1

and

Ree [x] :=

 2i − 1 2i − 1 x + bi sin x , ai cos 2 2

n  X

ai , bi ∈ R, ∀i = 1, 2, . . . , n, ∀n ∈ N ( u(x) | u(x) = a0 +

n X

) ∗

(ai cos ix + bi sin ix),

i=1

a0 , ai , bi ∈ R, ∀i = 1, 2, . . . , n, ∀n ∈ N

) ∗

.

We call the elements of these sets trigonometric polynomials in the variable x of odd degree and even degree respectively, with real coefficients. By our method, we intend e e [x] ∪ R e [x]. to determine the second degree divisors for the polynomials from the set R Correspondence to: I. Ichim

252

I. Ichim and I. Molnar

e [x] Note that for this it is sufficient to consider only the polynomials from the set R and to search second degree divisors of the type e e [x], −α cos x − β sin x + γ ∈ R

with

α2 + β 2 = 1.

Theorem 1. Let u be a trigonometric polynomial given by u(x) =

n  X

ai cos

i=1

and let

2i − 1 2i − 1 x + bi sin x 2 2



e [x], ∈R

e e [x], p(x) = −α cos x − β sin x + γ ∈ R

with n ≥ 2, a2n + b2n 6= 0,

with α2 + β 2 6= 0.

Then u(x) = p(x) v(x) + A cos

(1) where v(x) =

n−1 X j=1

x x + B sin , 2 2

2j − 1 2j − 1 x + dj sin x cj cos 2 2



e [x], ∈R

and the coefficients of the quotient and of the remainder after the division of u by p are determined recursively by the relations  2   [γ(αcj+1 + βdj+1 ) − αaj+1 − βbj+1 ] cj = 2   α + β2     1    [(α2 − β 2 )cj+2 + 2αβdj+2 ] − 2  α + β2 (2) 2    dj = 2 [γ(αdj+1 − βcj+1 ) + βaj+1 − αbj+1 ]   α + β2     1    [(α2 − β 2 )dj+2 − 2αβcj+2 ], − 2 α + β2 (j = n − 1, n − 2, . . . , 1) with cn+1 := dn+1 := cn := dn := 0 and  α β    A = a1 + (c1 + c2 ) + (d1 + d2 ) − γc1 2 2 (3)    B = b1 − α (d1 − d2 ) + β (c1 − c2 ) − γd1 . 2 2 Proof . The equality (1) follows from Corollary 23 in [2]. By straightforward calculation of the right hand side of this equality, we obtain u(x) = −

  n−1 2(j − 1) − 1 2(j + 1) − 1 αX x − cos x cj cos 2 2 2 j=1

−

  n−1 αX 2(j − 1) − 1 2(j + 1) − 1 x + sin dj sin x 2 2 2 j=1

A Bairstow’s type method for trigonometric polynomials

−

253

  n−1 2(j − 1) − 1 2(j + 1) − 1 βX x − sin x cj sin 2 2 2 j=1

β − 2 +γ

n−1 X j=1

 dj

n−1 X j=1

+ A cos

2(j + 1) − 1 2(j − 1) − 1 x − cos x cos 2 2

2j − 1 2j − 1 x + dj sin x cj cos 2 2





x x + B sin . 2 2

By reordering the terms in the above relation, we obtain u(x) =

 n  X αcj+1 βdj−1 βdj+1 αcj−1 2j − 1 − + − + γcj cos x − 2 2 2 2 2 j=2  n  X αdj+1 βcj−1 βcj+1 αdj−1 2j − 1 − − + + γdj sin x − + 2 2 2 2 2 j=2   αc1 αc2 βd1 βd2 x + − − − − + γc1 + A cos 2 2 2 2 2   αd2 βc1 βc2 x αd1 − − + + γd1 + B sin . + 2 2 2 2 2

By identification of the coefficients of the two polynomials in the last equality, we get for (cj , dj ), j = n − 1, n − 2, . . . , 1, the systems of linear equations (

αcj − βdj = 2γcj+1 − αcj+2 − βdj+2 − 2aj+1 βcj + αdj = 2γdj+1 − αdj+2 + βcj+2 − 2bj+1 .

Each of them has the determinant α2 + β 2 6= 0. Solving recursively these systems we obtain the relations (2). Then we also obtain, for the coefficients A and B of the remainder, the relations (3).  We want to determine those values of α, β and γ for which p is a divisor of u, or equivalently the remainder after the division of u by p is the zero polynomial. Therefore, if in the relation (1) we consider A and B as functions of α, β and γ, the problem is reduced to the one of solving the system of nonlinear equations  A(α, β, γ) = 0     B(α, β, γ) = 0 (4)     2 α + β 2 − 1 = 0. Let us now notice two characteristic aspects of Bairstow’s method. The first one is the solution of the system (4) by Newton’s method. Therefore, it is necessary to introduce the Jacobi matrix JA,B (α, β, γ) of this system, i.e.

254

I. Ichim and I. Molnar

 (5)

   JA,B (α, β, γ) =   

∂A (α, β, γ) ∂α ∂B (α, β, γ) ∂α 2α

∂A (α, β, γ) ∂β ∂B (α, β, γ) ∂β 2β

∂A (α, β, γ) ∂γ ∂B (α, β, γ) ∂γ 0

    ,  

and to establish the conditions under which it is nonsingular. The second aspect concerns the calculation of these matrix elements; they are determined from the remainders after the division of u and v by p. Lemma. Let α, β and γ real numbers, with α2 + β 2 = 1. If z1 and z2 are the roots of the polynomial −α cos x − β sin x + γ, then α = ± cos

(6)

z1 + z2 , 2

β = ± sin

z1 + z2 , 2

γ = ± cos

z 1 − z2 . 2

Theorem 2. Let us suppose that v(x) = p(x) w(x) + C(α, β, γ) cos

(7) Then

(8)

(9)

x x + D(α, β, γ) sin . 2 2

 1 ∂A 2    ∂α (α, β, γ) = α2 + β 2 [(αγ + β )C(α, β, γ) + β(γ − α)D(α, β, γ)]  1 ∂B   (α, β, γ) = 2 [(αγ − β 2 )D(α, β, γ) − β(γ + α)C(α, β, γ)], ∂α α + β2  γ−α ∂A    ∂β (α, β, γ) = α2 + β 2 [βC(α, β, γ) − αD(α, β, γ)]  ∂B γ+α   (α, β, γ) = 2 [βD(α, β, γ) + αC(α, β, γ)] ∂β α + β2

and (10)

∂A (α, β, γ) = −C(α, β, γ), ∂γ

∂B (α, β, γ) = −D(α, β, γ). ∂γ

Proof . Derivation of (1) with respect to α, β and γ results in  ∂v ∂A x ∂B x    0 = p(x) ∂α (x) − v(x) cos x + ∂α (α, β, γ) cos 2 + ∂α (α, β, γ) sin 2     ∂A x ∂B x ∂v (α, β, γ) cos + (α, β, γ) sin 0 = p(x) (x) − v(x) sin x + (11)  ∂β ∂β 2 ∂β 2       0 = p(x) ∂v (x) + v(x) + ∂A (α, β, γ) cos x + ∂B (α, β, γ) sin x . ∂γ ∂γ 2 ∂γ 2 Let us denote the roots of the polynomial p by z1 and z2 . Firstly, we consider the case when z1 6= z2 . Substituting these roots into (7) and (11), then combining the obtained relations, we find for the derivatives equations:

∂B ∂A ∂B , ,..., the following systems of linear ∂α ∂α ∂γ

A Bairstow’s type method for trigonometric polynomials

255

 z1 ∂B z1  z1 z1  ∂A   (α, β, γ) cos + (α, β, γ) sin = C cos + D sin cos z1  ∂α 2 ∂α 2 2 2      ∂A (α, β, γ) cos z2 + ∂B (α, β, γ) sin z2 = C cos z2 + D sin z2 cos z2 , ∂α 2 ∂α 2 2 2  z1 ∂B z1  z1 z1  ∂A    ∂β (α, β, γ) cos 2 + ∂β (α, β, γ) sin 2 = C cos 2 + D sin 2 sin z1  ∂A z2 ∂B z2  z2 z2    (α, β, γ) cos + (α, β, γ) sin = C cos + D sin sin z2 ∂β 2 ∂β 2 2 2 and  z1 ∂B z1 z1 z1 ∂A    ∂γ (α, β, γ) cos 2 + ∂γ (α, β, γ) sin 2 = −C cos 2 − D sin 2  z2 ∂B z2 z2 z2 ∂A   (α, β, γ) cos + (α, β, γ) sin = −C cos − D sin . ∂γ 2 ∂γ 2 2 2 z2 − z1 6= 0. For exemple, let us Each of these systems has the determinant ∆ := sin 2 ∂A . Solving the first of the above systems and using the relations (6), we determine ∂α obtain 1 h z1 z1  z2 z2  z2  ∂A (α, β, γ) = C cos + D sin cos z1 sin − C cos + D sin ∂α ∆ 2 2 2 2 2 z2 z2 z1 i 1 h z1 z1 × cos z2 sin = (cos z1 − cos z2 ) sin sin D + C cos z1 cos sin 2 ∆ 2 2 2 2   z1 i 1 z1 − z2 z1 + z2 z2 −C cos z2 cos sin = cos − cos (cos z1 − cos z2 )D 2 2 2∆ 2 2     z1 − z2 z1 − z2 z1 + z2 z1 + z2 +C cos z1 sin − sin − C cos z2 sin + sin 2 2 2 2    1 z1 + z2 z1 − z2 z1 − z2 z1 + z2 z1 + z2 =− D sin sin cos − cos + C sin ∆ 2 2 2 2 2  z1 − z2 z1 − z2 z1 + z2 z1 − z2 z 1 + z2 sin + C sin cos cos × sin 2 2 2 2 2 1 z1 − z2 =− 2 sin [(αγ + β 2 )C + β(γ − α)D]. 2 (α + β 2 )∆ Similarly, we can obtain the other partial derivatives of A and B. It remains to prove the statement when z1 = z2 . In this case p has a double root, therefore z1 is also the root of its derivative. Let us derive (7) and (11) with respect to ∂B ∂A ∂B , ,..., x. Substituting z1 and combining the obtained relations, we find for ∂α ∂α ∂γ the following systems of linear equations:

256

I. Ichim and I. Molnar

  z1 ∂B z1 z1 z1  ∂A   (α, β, γ) sin − (α, β, γ) cos = 2 C cos + D sin sin z1   ∂α 2 ∂α 2 2 2     z1  z1 cos z1 + C sin − D cos  2 2         ∂A (α, β, γ) cos z1 + ∂B (α, β, γ) sin z1 = C cos z1 + D sin z1 cos z1 , ∂α 2 ∂α 2 2 2   z1 ∂B z1 z1 z1  ∂A   (α, β, γ) sin − (α, β, γ) cos = −2 C cos + D sin cos z1  ∂β  2 ∂β 2 2 2      z1 z1 sin z1 + C sin − D cos 2 2       z1 ∂B z1 z1 z1  ∂A   (α, β, γ) cos + (α, β, γ) sin = C cos + D sin sin z1 ∂β 2 ∂β 2 2 2 and

 z1 ∂B z1 z1 z1 ∂A    ∂γ (α, β, γ) sin 2 − ∂γ (α, β, γ) cos 2 = −C sin 2 + D cos 2  ∂A z1 ∂B z1 z1 z1   (α, β, γ) cos + (α, β, γ) sin = −C cos − D sin . ∂γ 2 ∂γ 2 2 2

Each of the above systems has the determinant cos2 systems we also obtain the solutions (8)–(10).

z1 z1 + sin2 6 0. Solving these = 2 2



Theorem 3. Let α, β and γ be real numbers, with α2 + β 2 6= 0. The Jacobi matrix JA,B (α, β, γ) introduced in (5) is nonsingular if and only if the polynomial −α cos x − β sin x + γ and the polynomial v defined by (1) have no common root, i.e. are relative prime. Proof . Expanding the determinant of the matrix JA,B (α, β, γ) and using the relations (8)–(10), we have     ∂A ∂B ∂A ∂B ∂A ∂B ∂A ∂B − + 2β − det(JA,B (α, β, γ)) = 2α ∂β ∂γ ∂γ ∂β ∂γ ∂α ∂α ∂γ 2 = 2 [(γ + α)C 2 + 2βCD + (γ − α)D2 ]. α + β2 Using now the relations (6) between the coefficients α, β, γ and the roots z1 , z2 of the polynomial −α cos x − β sin x + γ, we get   z1 + z 2 2 z1 − z2 + cos C2 cos det(JA,B (α, β, γ)) = p 2 2 α2 + β 2    z 1 − z2 z1 + z2 z1 + z2 4 + cos − cos D2 = p +2CD sin 2 2 2 α2 + β 2 h z2  z1 z2 z1 z2  z2 i z1 z1 CD + D2 sin sin × C 2 cos cos + sin cos + cos sin 2 2 2 2 2 2 2 2  4 z1   z2 z2  4v(z1 )v(z2 ) z1 =p C cos + D sin = p . C cos + D sin 2 2 2 2 α2 + β 2 α2 + β 2

A Bairstow’s type method for trigonometric polynomials

257

Consequently, the matrix JA,B (α, β, γ) is nonsingular if and only if we have v(z1 ) v(z2 ) 6= 0, and thus results the theorem.  Remark . From the above theorems it follows that by applying the Newton’s method we can determine for the trigonometric polynomial u(x) second degree divisors of the type −α cos x − β sin x + γ with α2 + β 2 = 1 that are relatively prime to v(x). Using the local convergence theorem for Newton’s method [6] we conclude that the sequence (α(k) , β (k) , γ (k) ) produced by Bairstow’s method will converge (quadratically) to (α, β, γ), the solution of the system (4), on condition that the initial approximation (α(0) , β (0) , γ (0) ) to be sufficiently closed to (α, β, γ). In the following, we present some numerical examples obtained by application of the method described above. Given a trigonometric polynomial u(x), the algorithm starts with initial approximation (α(0) , β (0) , γ (0) ), then the next approximations (α(k) , β (k) , γ (k) ) and the errors err1(k) := |A(k) | + |B (k) |, (k) (k) 2 (k) 2 err2 := (α ) + (β ) − 1 are computed. The algorithm stops when k, the number (k) of the accomplished iterations, exceeds kmax or when err (k) 1 ≤ err and err 2 ≤ err (kmax = 100 and err = 10−13 ). Finally, the roots z1 , z2 of the obtained second degree factor −α(k) cos x − β (k) sin x + γ (k) are also computed. Example 1. Let us consider as a model problem the polynomial 7 7 5 5 3 3 u(x) = 3 cos x − 3 sin x + 13 cos x + 13 sin x − 13 cos x + 13 sin x 2 2 2 2 2 2 1 1 − 3 cos x − 3 sin x. 2 2 For different initial approximations (α(0) , β (0) , γ (0) ), the following three numerical experiments illustrate the convergence of the algorithm when the roots z1 , z2 of the polynomial u(x) are distinct, equal or complex. k

α(k)

β (k)

γ (k)

err1(k)

err2(k)

0 1 2 3 4 5 6

1.0000000000 0.8126026409 0.8016487367 0.7082985201 0.7071216318 0.7071067813 0.7071067812

−2.0000000000 −1.0936986796 −0.7102761124 −0.7120608504 −0.7071102399 −0.7071067812 −0.7071067812

3.0000000000 0.9024482161 0.7967004114 0.7095748320 0.7071245807 0.7071067812 0.7071067812

2.0 · 10+02 3.2 · 10+01 1.6 · 10+01 5.9 · 10−01 2.6 · 10−03 5.3 · 10−09 1.4 · 10−14

4.0 · 10+00 8.6 · 10−01 1.5 · 10−01 8.7 · 10−03 2.6 · 10−05 2.3 · 10−10 −2.0 · 10−17

z1 = 0.0000000000,

z2 = 4.7123889804

k

α(k)

β (k)

γ (k)

err1(k)

err2(k)

0 1 2 3 4 5 6

1.0000000000 0.0975077052 −0.0260094300 0.0016876821 −0.0000053291 0.0000000000 0.0000000000

2.0000000000 1.4512461474 1.0751778319 1.0029836870 1.0000058668 1.0000000000 1.0000000000

3.0000000000 1.4730971678 1.0693683461 1.0033592890 1.0000046812 1.0000000000 1.0000000000

2.8 · 10+01 4.3 · 10+00 1.6 · 10+00 1.1 · 10−01 3.4 · 10−04 1.8 · 10−09 1.1 · 10−15

4.0 · 10+00 1.1 · 10+00 1.6 · 10−01 6.0 · 10−03 1.2 · 10−05 6.3 · 10−11 0.0 · 10+00

258

I. Ichim and I. Molnar

z1 = 1.5707963268,

z2 = 1.5707963268

k

α(k)

β (k)

γ (k)

err1(k)

err2(k)

0 1 2 3 4 5 6

0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000

2.0000000000 1.2500000000 1.0250000000 1.0003048780 1.0000000465 1.0000000000 1.0000000000

3.0000000000 2.4750000000 1.7644981403 1.6712861271 1.6667004959 1.6666666691 1.6666666667

6.0 · 10+00 2.9 · 10+01 3.3 · 10+00 2.2 · 10−01 1.8 · 10−03 1.3 · 10−07 7.9 · 10−15

3.0 · 10+00 5.6 · 10−01 5.1 · 10−02 6.1 · 10−04 9.3 · 10−08 2.2 · 10−15 0.0 · 10+00

z1 = 1.5707963268 + 1.0986122887 i,

z2 = 1.5707963268 − 1.0986122887 i

Therefore, we obtain the following decomposition of the given polynomial: 

1 1 1 u(x) = − √ cos x + √ sin x + √ 2 2 2 √ e [x]. where q(x) = 24 2 cos x2 ∈ R





5 (− sin x + 1) − sin x + 3

 q(x),

Example 2. Let us consider the polynomial 19 17 15 13 1 21 x + cos x + 10 cos x + 2 cos x + 9 cos x + 3 cos x 2 2 2 2 2 2 7 5 3 1 9 + 8 cos x + 4 cos x + 7 cos x + 5 cos x + 6 cos x. 2 2 2 2 2

u(x) = 11 cos

k

α(k)

β (k)

0 1 2 3 4 5 6 7 8 9 10

1.0000000000 0.5848351737 0.4415194069 0.4089533825 0.3897567492 0.3651379903 0.3414150913 0.3329329079 0.3323423154 0.3323395777 0.3323395777

2.0000000000 1.2075824132 0.9456312389 0.9136944962 0.9211480569 0.9313345782 0.9402542593 0.9429926432 0.9431590332 0.9431597983 0.9431597983

γ (k)

err1(k)

3.0000000000 6.6 · 10+04 1.5937250841 9.8 · 10+03 1.1505401090 2.3 · 10+03 1.0534988126 7.1 · 10+02 1.0190504759 2.3 · 10+02 0.9996121526 6.7 · 10+01 0.9923383599 1.4 · 10+01 0.9907559944 8.4 · 10−01 0.9906333591 3.8 · 10−03 0.9906327854 8.3 · 10−08 0.9906327853 2.5 · 10−14

z1 = 1.3689940994,

err2(k) 4.0 · 10+00 8.0 · 10−01 8.9 · 10−02 2.1 · 10−03 4.2 · 10−04 7.1 · 10−04 6.4 · 10−04 7.9 · 10−05 3.8 · 10−07 8.1 · 10−12 5.1 · 10−17

z2 = 1.0950324172

In fact, the polynomial u(x) has exactly 21 distinct real roots in the interval [0, 2π) and it was studied and used in [4] to construct certain Gaussian quadratures of the trigonometric type.

A Bairstow’s type method for trigonometric polynomials

259

References 1. Fiala, T., Krebsz, A. (1987): On the Convergence and Divergence of Bairstow’s Method. Numer. Math. 50, 477–482 2. Ichim, I. (1992) Sur les polynˆomes trigonom´etriques. Bull. Math. Soc. Sci. Math. Roumanie, tome 36(84), no.2 3. Ichim, I.: Propri´et´es de divisibilit´e des polynˆomes trigonom´etriques. Bull. Math. Soc. Sci. Math. Roumanie (to appear) 4. Ichim, I. (1993): Les polynˆomes trigonom´etriques orthogonaux et les quadratures de type Gauss. Rev. Roumaine Math. Pures Appl. (to appear in no.4) 5. Schmeißer, G., Schirmeier, H. (1976): Praktische Mathematik. Berlin: Walter de Gruyter 6. Stoer, J., Bulirsch, R. (1980): Introduction to Numerical Analysis. New York, Heidelberg, Berlin: Springer Verlag

This article was processed by the author using the LaTEX style file pljour1 from Springer-Verlag.