Fast computation of the roots of polynomials in the Chebyshev basis

(1)

Dipartimento di Matematica

Corso di Laurea in Matematica

Tesi di Laurea Magistrale

Fast computation of the roots of

polynomials in the Chebyshev basis

Candidato:

Relatori:

Angelo Alberto Casulli

Prof. Dario Andrea Bini

Dott. Leonardo Robol

Controrelatrice:

Prof.ssa Paola Boito

Anno Accademico 2018/2019

(2)

(3)

Introduction

In this work we describe a fast method for computing the roots of a polynomial and the eigen-values of a matrix polynomial expressed in the Chebyshev basis, i.e.,

P (λ) := P0T0(λ) + · · · + PnTn(λ), (1)

where Tk(λ) denotes the Chebyshev polynomial of first kind of degree k, and P0, . . . , Pn are

m × mmatrices, by relying on the structure properties of the companion matrix associated with this representation.

Representing a (matrix) polynomial with respect to the Chebyshev basis is a fundamental step to overcome the ill conditioning of the polynomial roots encountered in many situations as in the case of roots located along a line in the complex plane. On the other hand, Chebyshev poly-nomials share many interesting properties which make them fundamental tools for approximating continuous functions in the infinity norm. Moreover, the process of evaluation/interpolation at the Chebyshev nodes of a continuous function or of a polynomial represented in the Chebyshev basis is a fast and numerically stable operation which can be performed by means of the Fast Cosine Transform. These facts have addressed a great interest to the problem of numerically computing the roots of a polynomial represented in the Chebyshev basis and on the design and analysis of numerical algorithms for the polynomial eigenvalue problem for matrix polynomials represented in the Chebyshev basis.

There is a wide literature concerning the analysis of polynomial root-finding algorithms and of algorithms for solving the polynomial eigenvalue problem. Large part of this literature relies on the reduction to a standard eigenvalue problem associated with a companion matrix which provides a matrix version of a polynomial represented in the power basis.

The key idea at the basis of this approach is the analysis and the exploitation of the matrix structures of the associated companion matrix. The aim is to design specific versions of the QR algorithm of Francis and Kublanovskaia [19] which can fully take advantage of the matrix structure properties.

Bini et al. in [7] developed an explicit QR algorithm that exploits the unitary plus rank-one form of the companion matrix and stores the unitary matrix using quasi-separable representation. In [6] Bini et al. modified the previous algorithm and converted the explicit version in an implicit one. In [9] Boito et al. enhanced and simplified the implicit version, besides they used a compression technique to reduce the number of generators after a QR step.

Chandrasekaran et al. in [12] have been the first one to perform the QR algorithm directly on the QR factorization of the matrix, where the Q is decomposed as product of rotations.

Aurentz et al. [3–5] developed an algorithm that is fast and backward stable if viewed as polynomial rootfinder. They used the unitary plus rank-one structure of the companion matrix decomposing the unitary part as product of rotations and incorporating the rank-one informa-tion in another product of rotainforma-tions. Using this representainforma-tion the algorithm designed in [3–5]

(6)

CONTENTS 5 works only with products among rotations. Moreover the authors used some operations to swap consecutive rotations and to keep the product in the desired form.

Frederix et al. in [20] exploited the unitary plus low rank structure of the companion matrix in monomial basis to perform a structured QR algorithm. The authors observed that after some steps of the QR iteration, the property of being unitary plus low-rank is lost by the matrices of the sequence generated by the algorithm. For this reason, the authors introduce a method to restore this property.

Eidelman et al. in [18] introduced quasiseparable representations and exploited this tool in order to study the eigenstructure of certain matrices as the monomial companion matrix. Then they developed a fast algorithm to solve eigenvalues problem related to the monomial companion matrix.

While several papers have been written concerning the computation of roots of a polynomial expressed in the monomial basis, the literature is lacking of results concerning fast algorithms for computing zeros of polynomials in the Chebyshev basis. The goal of this thesis is to present a fast and backward stable algorithm for this purpose.

For the scalar case (i.e., m = 1) the usual approach for computing zeros of a polynomial expressed in the Chebyshev basis is to find the eigenvalues of the companion pencil L0− λL1,

where L0=        −Pn−1 Pn− Pn−2 −Pn−3 . . . −P0 1 0 1 ... ... ... 1 0 1 1 0        and L1=        2Pn 2 ... 2 1        , (2)

using an eigensolver, such as the QR or the QZ algorithm. This operation has a cubic cost and a quadratic memory storage, with respect to the degree of the polynomial. We develop a method that has a quadratic cost and a linear memory storage.

To this aim, the crucial observation is that the matrix L0is the sum of a Hermitian and a

rank-one matrix. Moreover, supposing without loss of generality Pn > 0, the generalized eigenvalue

problem associated with the pair (L0, L1)can be brought back to the standard eigenvalue problem

associated with

A := (pL1)−1L0(pL1)−1, (3)

where√L1is the diagonal matrix with positive entries such that (

√

L1)2= L1and the matrix A

keeps the Hermitian plus a rank-one perturbation structure. This structure is preserved during a QR step. Indeed applying a unitary similarity transformation on this sum, yields again a Hermitian plus rank one matrix. Moreover if we start with a matrix in Hessenberg form at the end of a QR step we obtain again a Hessenberg matrix. As we will see in Chapter 4, these properties allow us to describe all the entries of the matrix using only 4 vectors, with a consequent advantage in the memory storage and a speed up of the algorithm.

The theoretical discussion of the algorithms is supported form numerical experiments, that show the speed of the algorithm and its stability. Moreover the accuracy of the algorithm used for the approximation of the zeros of smooth functions is numerically tested.

For the matrix polynomial case the fundamental idea is similar. Indeed, to compute the eigenvalues of a matrix polynomial, it is customary to build a linearization, that is a pair of matrices, say L0 and L1, such that ˆλ is an eigenvalue of P (λ) if and only if it is a solution of the

generalized eigenvalue problem associated with the pair (L0, L1).

In this thesis we transform the generalized eigenvalue problem associated with the companion matrices (L0, L1), to a standard eigenvalue problem related to a matrix that is the sum of a

(7)

CONTENTS 6 Hermitian matrix and a rank m matrix (where m is the size of the coefficients Pi). This time

the matrix is not in Hessenberg form, hence we develop a preprocessing stage which consists in reducing the matrix in Hessenberg form by exploiting and taking advantage of the specific structure of the matrix. Numerical experiment are used to study the speed of the algorithm.

The thesis is organized as follows. In Chapter 1 we introduce some terminology, notational conventions and basic results. In Chapter 2 we describe the standard version of the Francis Kublanovskaia algorithm for computing the eigenvalues of a complex matrix. In Chapter 3 we introduce the Chebyshev polynomials, we describe their principal properties and we introduce a Chebyshev companion matrix which has the fundamental property to be the sum of a Hermitian matrix and a rank-one correction. In Chapter 4 we present our algorithm in the case of scalar polynomials; that is, we develop a QR-like algorithm for matrices that are rank one perturbations of Hermitian matrices. Finally in Chapter 5 we generalize our algorithm for solving polynomial eigenvalue problems for matrix polynomials represented in the Chebyshev basis.

(8)

Chapter 1

Notations and preliminary tools

1.1 Notation

Throughout the thesis we use the following notation, unless stated otherwise. A = (aij) A general matrix A with entries aij.

A(i : j, k : l) The submatrix of A consisting of rows i up to j and columns k up to l.

Cn The complex vector space of dimension n. Cn×n The complex vector spaces of n × n matrices. det(A) The determinant of a matrix A.

diag (d) The diagonal matrix having the entries of d ∈ Cn as diagonal

entries.

ei The i-th entry of the canonical basis, i.e., the vector that has 1

in the i-th entry and 0 elsewhere.

fl(A) The result of computing the matrix A in floating point arithmetic. Gi A Givens transformation that acts only on the ith and i + 1th

entries of a vector.

Ik The identity matrix of size k × k.

P The vector space of polynomial.

Pn The vector space of polynomial of degree less or equal than n.

Q A unitary matrix, that is such that QQH_{= Q}H_{Q = I}, where QH

is the transpose conjugate of Q. R An upper triangular matrix.

Rn The real vector space of dimension n. Rn×n The real vector spaces of n × n matrices.

Tril (A, p) The lower triangular part of the matrix A, below and including the subdiagonal p.

Triu (A, p) The upper triangular part of the matrix A, above and including the superdiagonal p.

u = [u1, u2, . . . , un]T A column vector u with entries ui.

u(i : j) A subvector of u, consisting of the entries i up to and including j. A ⊕ B The block diagonal matrixA 0

0 B

(9)

CHAPTER 1. NOTATIONS AND PRELIMINARY TOOLS 8

1.2 Norms

The norms are a useful tool to evaluate the size of a vector or of a matrix by means of a real number. In particular the norms are used to measure the perturbation introduced using a floating point arithmetic.

Definition 1.2.1. An application k·k : Cn

→ R is called vector norm if satisfies the following

properties:

1. kxk ≥ 0, for each x ∈ Cn, and kxk = 0 if and only if x = 0; 2. kαxk = |α|kxk, for each α ∈ C and x ∈ Cn;

3. kx + yk ≤ kxk + kyk for each x, y ∈ Cn.

A widely used norms are the so called Hölder norms defined as follows: kxkp:= n X i=1 |xi|p !1p , p ≥ 1. (1.1)

For p = ∞, kxk∞:= limp→∞kxkp = maxi{|xi|}.

The set of matrices Cn×n is a vector space, hence we could define the norm on this space

using the Definition 1.2.1. However it is convenient to use a stronger definition that imposes some additional properties.

Definition 1.2.2. An application k·k : Cn×n

→ R is called matrix norm if satisfies the following

properties:

1. kAk ≥ 0, for each A ∈ Cn×n, and kAk = 0 if and only if A = 0; 2. kαAk = |α|kAk, for each α ∈ C and A ∈ Cn×n;

3. kA + Bk ≤ kAk + kBk for each A, B ∈ Cn×n; 4. kABk ≤ kAkkBk for each A, B ∈ Cn×n.

An example of matrix norm is the Frobenius norm defined as kAkF =   n X i=1 n X j=1 |ai,j|2   1 2 . (1.2)

Each vector norm induces a matrix norm given by the following: kAk := max

kxk=1kAxk. (1.3)

If we think to a matrix as an operator between two vector spaces, the induced norm measures the maximum stretching that the operator produces transforming a vector.

(10)

1.3 Floating point arithmetic and error analysis

When we work with a computer we have a finite memory, hence we cannot represent a real or complex number using all its digits, since they are often infinite. It is necessary to define a representation for real or complex numbers that uses only a finite number of digits.

Definition 1.3.1. Given the integers B ≥ 2, t ≥ 1, m, M > 0 the set

F (t, B, m, M ) := {0} ∪ {±Bp t

X

i=1

diB−i, d16= 0, 0 ≤ di≤ B − 1, −m ≤ p ≤ M } (1.4) is called set of floating point numbers. When there is no risk of confusion, we denote this set simply by F, dropping the dependence on t, B, m, M.

Usually in the floating point representations implemented on a computer the parameter B is chosen equal to 2. The choice of t, m and M depends on the precision required. For example in the so called “single precision” we have t = 24, m = 126, M = 127 that corresponds to about 7 decimal digits, while in the more used “double precision” we have t = 53, m = 1022, M = 1023 that corresponds to about 16 decimal digits.

When computing with floating point numbers it can happen that the numbers become so big (or small) that they can no longer be represented in floating point arithmetic. That is, it can occur that p becomes bigger than M or smaller than −m. The first case is called overflow, the latter underflow. Clearly, during the construction of an algorithm we have to pay attention to avoid possible overflow or underflow situations.

Let us observe that if a, b ∈ F(t, B, m, M) it is not guaranteed that a op b ∈ F, where op is one of the four arithmetic operations. Hence, to work using only numbers in F we have to introduce an approximate arithmetic in the following way:

a [op] b := trunc(a op b) (1.5) where trunc(x) denotes the truncation of the real (or complex) number x at t digits.

When we work in finite precision arithmetic we have to take into account errors that occur during the computation. Indeed, operations like truncation in representing input data or in performing arithmetic operations generate errors. In general, also the data coming from the real world are affected by errors.

Suppose we have f : Ω ⊆ Cn_{→ C}mand we want to compute f(x) at a certain x ∈ Ω. Before

starting the computation there are already errors in the input data x, hence we are computing f (ˆx), where ˆx is a perturbation of x. This produces a relative error

in:=

f (ˆx) − f (x)

f (x) , (1.6)

defined if f(x) 6= 0. This error is called “inherent”.

Assume we can compute f(x) using only a finite number of operations. Each arithmetic operation produces a relative error bounded in modulus by the machine precision. Hence the value obtained at the end of the computation does not coincide, in general, with f(ˆx). We denote it by ϕ(ˆx). We define the algorithmic error as

alg :=

ϕ(ˆx) − f (ˆx)

(11)

CHAPTER 1. NOTATIONS AND PRELIMINARY TOOLS 10 We call total error

tot:=

ϕ(ˆx) − f (x)

f (x) . (1.8)

It is easy to prove that

tot= in+ alg+ inalg

.

= in+ alg, (1.9)

where .= denotes the equality of the linear parts.

Using the symbol .= allows us to simplify the analysis, in fact we remove nonlinear terms in the errors. This kind of analysis, called first-order analysis, is meaningful in practice, since usually the errors are small and then their products and their powers with exponent greater than one become negligible.

The analysis of the algorithmic error is generally technical and complicated. Another choice that often simplifies the analysis of the error is the so called “backward analysis”. Let us suppose we can compute f(x) using only a finite number of operations and let ϕ(x) be the function that associate to x the value obtained computing f(x) in machine precision. In the backward error analysis we look for a perturbation δx, such that

ϕ(x) = f (x + δx). (1.10) The aim of this analysis is to find an upper bound to the ratio

kδxk

kxk . (1.11)

More precisely we give the following definition.

Definition 1.3.2. Let F be an algorithm for the computing of f(x). Let δx such that the

computed value F (x) is equal to f(x + δx). We say that F is a backward stable algorithm in norm k·k, if

kδxk

kxk = O(u), (1.12)

where u is the machine precision.

Now if f is well conditioned (i.e., at a small relative perturbation on x corresponds a small relative perturbation on f(x)) we can give a meaningful upper bound to the error.

1.4 Stability

When we compute the eigenvalues of a matrix to solve a real-world problem, we can expect to have some errors on the matrix given by the measurement or modelling. Moreover, working in floating point arithmetic we generate errors in the matrix entries during the computation. For these reasons for solving an eigenvalue problem we want that computing the eigenvalues of a perturbed matrix A + E those are close to the unperturbed matrix A ones.

The eigenvalues of A depend continuously on the entries of the matrix [25]. More precisely it would be more useful to have a number κ, called condition number, such that if we perturb the matrix by then the eigenvalues are perturbed by at most κ. If the matrix is diagonalizable we can find a κ using the following theorem.

(12)

Theorem 1.4.1. (Bauer–Fike) Assume we are given matrices A, E ∈ Cn×nwhere A is diagonal-izable, that is, there exists an invertible matrix V and a diagonal matrix Λ such that V−1_{AV = Λ}_. Denote κp(V ) := kV kpkV−1kpthe condition number of V . For any eigenvalue µ of the perturbed matrix A + E there exists an eigenvalue λ of A such that

|λ − µ| ≤ κp(V )||E||p. (1.13)

The Bauer-Fike theorem provides a condition number valid for all the eigenvalues. Sometimes we are interested to estimate the error on a single eigenvalue. In that case a more precise bound is given by the following theorem.

Theorem 1.4.2. Let A ∈ Cn×n. Let λ be an eigenvalue with associated right and left eigen-vectors, x and y, respectively, normalized so that kxk2 = kyk2 = 1. Let s = yHx. If s 6= 0 define

κ = 1 |s| =

1

|yH_x|. (1.14)

Let δA be a perturbation of A such that kδAk2 = , and let λ + δλ be the eigenvalue of A + δA

that approximates λ. Then

|δλ| ≤ κ + O(2). (1.15)

Thus κ is a condition number for the eigenvalue λ. If s = 0 we define κ = ∞, that is, it does not exist an upper bound for |δλ|.

Applying an algorithm in floating point arithmetic generates errors which may substantially affect the computed results.

The Bauer-Fike theorem guarantees that if the condition number κpof the eigenvector matrix

V is small, than a backward stable algorithm applied in floating point arithmetic provides good approximations of the eigenvalues.

1.5 Matrices that create zeros

Given a nonzero vector x ∈ Cn, the goal of this section is to describe efficient techniques to

construct an orthogonal matrix G ∈ Cn×n such that Gx = αe

1for some α ∈ C. Here e1denotes,

as usual, the standard basis vector with a 1 in the first entry and 0 elsewhere. In other words G creates many zeros when applied to x.

1.5.1 Elementary Householder matrices

An elementary Householder matrix is a matrix of the form G = I − βuuH, where u ∈ Cn, β = 0

if u0 = or β = 2/(uH_u) when u 6= 0. It is easy to verify that G is unitary and Hermitian.

Geometrically G is a reflection with respect to the hyperplane u⊥, hence matrices in this family

are also called “Householder reflectors”.

Observe that, relying on the specific structure of G, we can compute the product Gx with only O(n) operations. Moreover only O(n) memory is needed to store G since this matrix is uniquely determined by the vector u.

It is not difficult to construct a Householder matrix that transforms a nonzero vector x in αe1. Indeed we can preliminarily observe that since G is unitary the 2-norm of αe1must be the

same of the 2-norm of x, so α = θkxk2, where |θ| = 1. Now we are ready to compute the vector

u, and then the scalar β = 2/(uH_u). From the condition Gx = αe

1 it can be deduced that

(13)

CHAPTER 1. NOTATIONS AND PRELIMINARY TOOLS 12 This allows to determine the vector u, up to a multiplicative constant, that can be incorporated in β. It can be noticed that all the entries of u, except the first, are equal to the entries of x. The first entry, if x16= 0is

u1= x1− α = x1− θkxk2. (1.17)

To avoid numerical cancellation usually one sets θ =

(

−x1/|x1| if x16= 0

−1 if x1= 0.

(1.18) With this convention we have

u1= ( x1(1 + _|x1 1|kxk2) if x16= 0 kxk2 if x1= 0, (1.19) and β = 1/(kxk2₂+ |x1|kxk2). (1.20)

The application of a Householder matrix to annihilate many entries in a vector requires the computation of only one square root, therefore that is a cheap way to annihilate entries in a full matrix. We avoid the use of this kind of matrices when there exist zeros in the vector that we wish to preserve: generically multiplying a sparse matrix by a Householder reflector destroys the sparsity.

1.5.2 Givens rotators

Rotators are another important class of unitary transformations. We begin by considering the 2 × 2case. Let c and s be two complex numbers satisfying |c|2_{+ |s|}2_{= 1}, denote ¯s, ¯c the complex

conjugate of s and c, respectively, and define the 2 × 2 matrix G = ¯c s¯

−s c

. (1.21)

One may easily check that G is unitary. If c and s are real then G is a plane rotation, therefore we will refer to this class of transformations as rotators.

Given a nonzero vector x =a_bwith kxk2= r > 0, it is easy to build a rotator such that

¯c s¯ −s c a b =r 0 , (1.22)

simply taking c = a/r and s = b/r. Zero-creating rotators of this type are called Givens rotators. Now let us consider n × n matrices. An n × n matrix G is called a plane rotators acting in the (i, j) plane if it has the form

G =       Ii−1 ¯ c s¯ Ij−i−1 −s c In−j       , (1.23)

(14)

CHAPTER 1. NOTATIONS AND PRELIMINARY TOOLS 13 where |c|2_{+ |s|}2_{= 1}. Given any x ∈ Cn, the transformation x → Gx leaves all the entries of x

unchanged except xi and xj which undergo the transformation

xi xj → ¯c s¯ −s c xi xj . (1.24)

Thus, one can easily construct a rotator in the (i, j) plane that transforms xj to zero, while

leaving all other entries of x, except xi, fixed. It follows that we can build a zero-creating matrix

Gfrom a product of n − 1 Givens rotators. Given a nonzero vector x ∈ Cn let G

n−1be a Givens

rotator acting in the (n, n − 1) plane such that Gn−1x has zero in the n-th position. Then let

Gn−2 be a Givens rotator acting in the (n − 2, n − 1) plane such that Gn−2Gn−1xhas a zero

in position n − 1. The zero in n-th position is preserved by this transformation. Continuing in this manner we can construct a product of plane rotators G = G1G2. . . Gn−2Gn−1 such that

Gx = αe1where |α| = kxk2.

Contrarily to the use of Householder matrix, if we use a product of Givens rotator to annihilate many entries in a full vector, we have to compute one square root for each entry we want to annihilate. For this reason the use of Givens rotators is more expensive if compared to Householder matrices. However, the Givens rotators are better suited to keep the structure of a sparse matrix, since the application of a Givens rotator to a given matrix A only involves 2 rows (or columns) of A.

1.6 Schur decomposition

Among the available different canonical forms of a matrix, the Schur form is particularly useful since is obtained by a similarity transformation using unitary matrices. Computing products using unitary matrices is a backward stable operation, that is, if A, Q, U ∈ Cn×n with Q and U

unitary, then

fl(QAU ) = Q(A + ∆A)U, with k∆AkF ≤ kAkFu, (1.25)

where fl(QAU) is the computed product in floating point arithmetic, and u is the machine precision (we assume to perform the matrix multiplication in the standard way, as described in [24, Section 3.5]).

Theorem 1.6.1. (Schur normal form) For any A ∈ Cn×n there exist an upper triangular matrix

T ∈ Cn×n and a unitary matrix U ∈ Cn×n, such that

UHAU = T. (1.26)

If A is real, then in general is is not true that also U and T are real matrices. However, there exists a real version of the Schur form which we report below.

Theorem 1.6.2. (Real Schur normal form) For any A ∈ Rn×nthere exist an orthogonal matrix

U ∈ Rn×n and a block triangular matrix

T =      T11 T12 · · · T1k 0 T22 · · · T2k ... ... ... 0 0 · · · Tkk      , (1.27)

where Tii∈ R, or Tii∈ R2×2 with a complex conjugate pair of eigenvalues, such that

(15)

1.6.1 Ordered Schur form

Let A ∈ Cn×n. Let U ∈ Cn×n be an unitary matrix and T an upper triangular matrix such that

A = UHT U (1.29)

is a Schur decomposition of A.

The aim of this section is to describe a way to compute another Schur decomposition of A, where the diagonal of T is sorted according to a given ordering. Clearly, it is sufficient to describe how to swap two consecutive diagonal values of T .

Let’s start by considering the 2 × 2 case:

T =t1,1 t1,2 0 t2,2

. (1.30)

We begin by swapping in the crudest imaginable way. Applying a similarity transformation by 0 1 1 0 , (1.31) we obtain t2,2 0 t1,2 t1,1 (1.32) which has the diagonal blocks in the desired places but is no longer block upper triangular. To annihilate the entry t1,2 it is sufficient to compute a Givens rotator, G, such that G

t2,2− t1,1 t1,2 is a multiple of e1. Indeed " 1 0 − t1,2 t2,2−t1,1 1 # t2,2 0 t1,2 t1,1 " ₁ ₀ t1,2 t2,2−t1,1 1 # =t2,2 0 0 t1,1 , (1.33) and " 1 0 t1,2 t2,2−t1,1 1 # = GHR, (1.34)

where R is upper triangular. Hence using (1.34) in (1.33) we obtain Gt2,2 0 t1,2 t1,1 GH=t2,2 ∗ 0 t1,1 , (1.35)

that is, the searched Schur form.

For the general case we only need to compute a Givens transformation Gi such that

Gi ti,i ti,i+1 0 ti+1,i+1 GH_i =ti+1,i+1 ∗ 0 ti,i , (1.36)

indeed computing the product GiT GHi (with the usual convention for the application of a Givens

transformation), yields an upper triangular matrix that has the same diagonal of T , except for ti,i and ti+1,i+1 that are swapped.

(16)

1.7 Hessenberg matrix

Suppose we have a matrix A ∈ Cn×n. We are going to study algorithms that compute the

eigenvalues of A using floating-point arithmetic on a digital computer.

To compute the eigenvalues of A numerically we will compute its Schur form. Since this task is equivalent to compute the roots of the characteristic polynomial of A it needs to be an iterative process. On the other hand a common preprocessing step is to transform the matrix to an almost triangular form, which in contrast can be computed in a finite number of operations: the Hessenberg form.

Recall that a matrix B is upper Hessenberg if its entries below the first subdiagonal are all zero, that is, bi,j = 0if i > j + 1. Pictorially, portraying the case n = 6, this means that B has

the form _        × × × × × × × × × × × × × × × × × × × × × × × × × ×         . (1.37)

The entries that are marked with the symbol × can take on any values, while those that are left blank are all zeros. A lower Hessenberg matrix is a matrix that is the transpose of an upper Hessenberg matrix. We will seldom mention lower Hessenberg matrices. For the sake of simplicity, we use the term Hessenberg matrix in place of upper Hessenberg matrix.

1.8 The QR factorization

One of the most used factorization of a matrix is certainly the QR factorization. Given a matrix A ∈ Cn×n it consists to find a unitary matrix Q and an upper triangular matrix R such that

A = QR.

In the general case the construction of this factorization proceeds as follows: let Q1 be a

Householder matrix such that Q1Ae1 is a multiple of e1 and let A(1) = Q1A. Recursively, for

i = 1, . . . , n − 2, let ˆQi+1∈ Cn−i×n−ibe a Householder matrix such that ˆQi+1A(i)(i + 1 : n, i + 1 :

n)e1is a multiple of e1; we define Qi+1:= Ii⊕ ˆQi+1and A(i+1):= Qi+1A(i).For construction the

matrix R := Qn−1Qn−2· · · Q1A is upper triangular, hence if we define Q := QH1 · · · QHn−2QHn−1

we obtain the desired QR factorization. It can be proved that this factorization in unique up to a unitary diagonal matrix, that is, if Q, ˜Qare two unitary matrices and R, ˜R are two upper triangular matrices such that A = QR = ˜Q ˜R then there exists a diagonal unitary matrix, F , such that ˜Q = QF and ˜R = FHR.

The previous construction simplifies if A is in Hessenberg form. Indeed, in that case, each Qi

has to annihilate only a single entry of A. Hence we can use as Qi a Givens rotator instead of a

Householder matrix.

Using the previous algorithm the cost of computation for the QR factorization for a full matrix is O(n3₎, where n is the size of the matrix, while if the matrix is in Hessenberg form the

cost is O(n2₎.

1.9 The generalized eigenvalue problem

Consider an ordinate pair (A, B) of matrices in Cn×n such that det(A − λB) is not identically

(17)

CHAPTER 1. NOTATIONS AND PRELIMINARY TOOLS 16 not both zeros, such that

µAv = νBv. (1.38)

The scalars µ and ν are not uniquely determined by v, but their ratio is. If µ 6= 0, (1.38) is equivalent to

Av = λBv, (1.39)

where λ = ν/µ. The scalar λ is then called an eigenvalue of the pair (A, B) associated with the eigenvector v. If (1.38) holds with ν 6= 0 and µ = 0, then (A, B) is said to have an infinite eigenvalue: the eigenvalue of (A, B) associated with v is ∞.

This is the generalized eigenvalue problem. In the case B = I it reduces to the standard eigenvalue problem. Moreover if B is invertible the generalized eigenvalue problem associated with (A, B) is equivalent to the standard eigenvalue problem associated with the matrix AB−1_.

(18)

Chapter 2

The QR algorithm

The QR algorithm is a numerically backward stable method for computing the eigenvalues of a real or complex matrix. Developed by Francis in the beginning of the 1960’s, the QR algorithm is still the most used method for small-medium size matrices. The purpose of this chapter is to provide an overview of this algorithm.

2.1 The standard QR algorithm

Let A ∈ Cn×n. In this section we will analyze algorithms for computing the eigenvalues of A.

The QR algorithm is an iterative method that generates a sequence of matrices {A(i)_}

ob-tained by a similarity transformation from A.

Let ρ(z) be a polynomial called shift polynomial We will describe how to choose this poly-nomial in Section 2.4. Given A(i), using techniques seen in Section 1.8, we compute a unitary

matrix Q(i) and an upper triangular matrix R(i) such that

ρ(A(i)) = Q(i)R(i), (2.1) and we define

A(i+1):= (Q(i))HA(i)Q(i). (2.2) Under suitable hypotheses this sequence converges to an upper triangular matrix (a Schur form of A) which has on the diagonal the eigenvalues of A. More information about this convergence can be found in [4, Chapter 2].

In this general version, the algorithm looks expensive. Indeed, just the computation of the QRfactorization of a full matrix has a cost which is cubic with respect to the size n (see Section 1.8). Moreover if ρ(x) is a polynomial of degree greater than 1, the computation of ρ(A) costs O(n3₎operations. If we assume a linear convergence for the method, where at least one iteration

is needed for each eigenvalue as it happen in practice, we have to do O(n4₎operation to find all

the eigenvalues and that is too much.

To solve this problem, the matrix is reduced in Hessenberg form using a preprocessing step that we describe in Section 2.2. The Hessenberg structure is preserved after an iteration of the QR algorithm and the QR factorization of a Hessenberg matrix can be computed with a lower computational cost with respect to the QR factorization of a full matrix, as we have seen in Section 1.8. Moreover, if the starting matrix is in Hessenberg form, an alternative formulation of the QR algorithm, which goes under the name of implicit QR, described in Section 2.3, is preferable.

(19)

CHAPTER 2. THE QR ALGORITHM 18

2.2 Hessenberg reduction

In this section, we describe a preprocessing step that brings a full matrix in Hessenberg form by means of a unitary similarity transformation. With this transformation the eigenvalues are preserved and the eigenvectors can be easily related to the ones of the original problem.

Given a full matrix A ∈ Cn×n we compute, using similarity transformations, a new matrix

in Hessenberg form unitarily similar to A. Let Q1 ∈ Cn−1×n−1 be a Householder matrix (or a

product of Givens rotators) such that

Q1A(2 : n, 1) = αe1, (2.3) where α ∈ C. Let ˆQ1 = 1 Q1 . The matrix A(1) _{:= ˆ}_Q

1A ˆQH1 has zero entries of indices

(3, 1), (4, 1), . . . , (n, 1). Indeed when we apply the matrix ˆQ1on the left we annihilate them and

when we apply ˆQ1 on the right we leave the first column unchanged. Now we can do the same

operation on the submatrix A(1)_{(2 : m, 2 : n)} obtained by removing the first row and the first

column from A(1), yielding a matrix ˆ_Q

2such that A(2):= 1 ˆ Q2 A(1)1 _ˆ QH 2

has zeros in the entries of indices (3, 1), (4, 1), . . . , (n, 1) and (3, 2), (4, 2), . . . , (n, 2). Now we iterate the method on the submatrix A(2)_{(3 : n, 3 : n)} and so on. At the end of the process, after n − 2 steps,

we obtain a unitary matrix, Q, such that QAQH is in Hessenberg form where Q is obtained

by multiplying the unitary matrices generated at each step. Since the Hessenberg matrix is obtained by similarity transformation from A, it has the same eigenvalues of A. Furthermore the similarity can be used to compute the eigenvectors of A from the ones of QAQH. Moreover,

since the similarity transformation is built by using a unitary matrix, this process is backward stable, as we seen in Section 1.6. The cost of this reduction for a full matrix is O(n3₎.

2.3 The implicit QR (Francis’ algorithm)

Francis’ algorithm is by far the most popular and effective algorithm for computing all the eigenvalues of an upper Hessenberg matrix A.

Without loss of generality, we may assume that the matrix A is not just upper Hessenberg but unreduced upper Hessenberg. This means that all of the subdiagonal entries of A are nonzero: aj+1,j 6= 0 for j = 1, 2, . . . , n − 1. Indeed, if A is not properly upper Hessenberg, then we can

clearly decompose the problem into two or more subproblems that can be solved separately. That is, if there exists j such that aj,j+1= 0, then the eigenvalues of A are equal to the union

of the eigenvalues of A(1 : j, 1 : j) and the eigenvalues of A(j + 1 : n, j + 1 : n). We will therefore assume that A is unreduced Hessenberg from the outset.

An iteration of Francis’ algorithm begins by picking a shift polynomial ρ. Let m be the degree of ρ. In principle m can be any positive integer, but in practice it should be fairly small. We do not actually compute ρ(A), as this would be too expensive. Francis’ algorithm just needs the first column x = ρ(A)e1. The computation is especially cheap because A is upper Hessenberg.

It is easy to check that ρ(A)e1 has nonzero entries only in its first m + 1 positions. The next

step is to build a unitary matrix Q0 whose first column is proportional to x, i.e., Q0βx = βe1

for some nonzero scalar β. We can do that by constructing a product of m Givens rotators as we did in Section 1.5.2. Now we use Q0to perform a similarity transformation: A(1)= Q0AQH0 .

This transformation modifies the Hessenberg form, but only slightly since Q0 acts only on the

first m + 1 rows, and QH

(20)

CHAPTER 2. THE QR ALGORITHM 19 gets filled in by this transformation. Below row m + 2, we have a big block of zeros, and these remain zero. The total effect is that there is a bulge in the Hessenberg form.

In the case m = 2 and n = 6, the matrix A(1) looks like1

        × × × × × × × × × × × × + × × × × × + + × × × × × × × × ×         . (2.4)

The next step is called bulge chasing and consists to bring back the matrix in Hessenberg form by unitary similarity transformations. This begins with a transformation Q1that acts only

on rows 2 through m + 2 and creates the desired zeros in the first column. As we did previously we can construct Q1as product of Givens rotators. By applying a similar transformation Q1we

obtain a new matrix A(2)_{:= Q}

1A(1)QH1 that has the first column spanned by e1 and e2and the

bulge has been pushed one position to the right and downward. Pictorially, for n = 6 and m = 2 , A(2) looks like         × × × × × × × × × × × × × × × × × + × × × × + + × × × × ×         . (2.5)

This establishes the pattern for the process. The next transformation will push the bulge over and down one more position, and so on. For large n, we see that a long sequence of such transformations will chase the bulge down through the matrix until it is finally pushed off the bottom. At this point, the Hessenberg form will have been restored and the Francis iteration will be complete. For this reasons, Francis’ algorithm is known as a bulge chasing algorithm.

An iteration of Francis’ algorithm of degree m can be summarized briefly as follows. 1. Pick a shifts polynomial ρ of degree m.

2. Compute x = ρ(A)e1.

3. Compute a unitary matrix Q0whose first column is proportional to x.

4. Perform a similarity transformation Q0AQH0 creating a bulge.

5. Return the matrix to upper Hessenberg form by chasing the bulge to the bottom. Denoting ˆAthe final result of the Francis iteration, we have

ˆ

A = Qn−2· · · Q0A(Qn−2· · · Q0)H, (2.6)

where Q0is the transformation that creates the bulge, and Q1, . . . , Qn−2are the transformations

that chase it. Letting Q := Qn−2Qn−3· · · Q0, we have

ˆ

A = QAQH. (2.7)

(21)

CHAPTER 2. THE QR ALGORITHM 20 Recall that Q0 was built in such a way that Q0ρ(A)e1= βe1. It is easy to check that all of the

other Qi leave e1invariant: Qie1= e1, i = 1, . . . , n − 2. We conclude that

Qρ(A)e1= Qn−2· · · Q1Q0ρ(A)e1= βe1. (2.8)

We summarize these findings in a theorem.

Theorem 2.3.1. A Francis iteration of degree m with shift polynomial ρ performs a unitary

similarity transformation

ˆ

A = QAQH (2.9)

where ˆA is upper Hessenberg and QH_e

1 = βρ(A)e1, for some nonzero β. In words, the first column of QH is proportional to the first column of ρ(A).

Actually Francis’ algorithm and the standard QR algorithm are equivalent in the sense spec-ified by the following theorem.

Theorem 2.3.2. (Implicit Q theorem) Let Q, W ∈ Cn×n be unitary matrices with

QAQH = H and W AWH = G, (2.10)

where H ad G are unreduced Hessenberg matrices. If QH_e

1= WHe1, then there exist a unitary, diagonal matrix F such that G = F HFH.

A proof of this theorem can be found in [4, Chapter 2].

2.3.1 Eigenvalues deflation

The sequence of matrices A(i)gererated by the implicit QR algorithm tends to an upper

trian-gular matrix. Since the matrices A(i)are in Hessenberg form the subdiagonal entries of A(i)tend

to zero.

Usually, not all the subdiagonal entries tend to zero with the same convergence rate. Typically one or more entries converge to zero rapidly, allowing the problem to be deflated to a smaller size. Therefore it is convenient, using shift polynomials, to adjust the algorithm in such a way that some entry in the subdiagonal converges to zero much faster than the others.

In the practice of floating point computation, we assume that a subdiagonal entry a(i) k+1,k of

A(i)= (a(i)_j,k)can be considered zero if

This criterion is backward stable, indeed if we call E the matrix such that Ek,k+1 = a (i) k,k+1

and zero elsewhere, we substitute the matrix A(i)with

(22)

CHAPTER 2. THE QR ALGORITHM 21 Moreover, since we use only unitary transformations during the algorithm and the Frobenius norm is invariant under those transformations, to introduce a small perturbation at the ith step corresponds to introduce a small perturbation at the starting matrix.

When the subdiagonal entry a(i)

k,k+1 becomes zero, we can bring back the problem of finding

the eigenvalues of A(i) to the problem of finding the eigenvalues of the two smallest matrices

A(i)_{(1 : k, 1 : k)}and A(i)_{(1 : k + 1, 1 : k + 1)}. The algorithm terminates when all the subdiagonal

becomes zero.

2.4 Shift polynomials

The main role of the shift polynomial is to improve the speed of convergence. Let us consider a matrix A ∈ Cn×n with eigenvalues λ

1, . . . , λn, where

|λ1| ≥ |λ2| ≥ · · · ≥ |λn|. (2.15)

The QR algorithm can be seen as a generalization of the power method [44, Chapter 4]. Given a nonzero starting vector x ∈ Cn the power method generates a sequence of vectors

x, Ax, A2x, A3x, . . . (2.16) that, if the choice of the starting vector is not unlucky, converges to the eigenvector relative to the largest modulus eigenvalue (assuming that there is only one largest modulus eigenvalue), and the speed of this convergence depends on the ratio |λ2/λ1|. Similarly the QR algorithm,

generating a sequence of unitary matrices, computes invariant subspaces, that are Sj ∈ Cn×j

for a j ∈ 1, . . . , n − 1 such that ASj ⊆ Sj. The speed of convergence to the invariant subspace

Sj depends on |λj+1/λj|: small ratios imply rapid convergence. When an invariant subspace is

found the problem can be subdivided in 2 small problems and the algorithm can be repeated on two small matrices. In practice, during the implicit QR algorithm, an invariant subspace is found when the equation (2.11) is satisfied for some k.

If we know an approximation, say α, of an eigenvalue, say λi, we can start the algorithm

on the matrix ˆA = A − αI. Now we can suppose that the eigenvalue ˆλn := λi− α is small

in modulus, that is we can suppose (if we are not unlucky) that |ˆλn/ˆλn−1| is small, so we can

rapidly deflate the eigenvalue ˆλn and then find λi= ˆλn+ α.

In particular if λ is an eigenvalue and we use it as shift we have, in exact arithmetic, a deflation of λ in a single step. Without loss of generality we can assume A = (ai,j) ∈ Cn×n to

be in unreduced Hessenberg form, that is, a Hessenberg matrix with all the subdiagonal entries nonzero.

Remark 2.4.1. If λ is an eigenvalue of A, let Q be a unitary matrix and let R be a upper

triangular matrix such that A − λI = QR. Then the entry (n, n − 1) of QH_AQ is zero. So we can deflate an eigenvalue and that eigenvalue is λ.

Proof. It is easy to prove that the matrix Q is upper Hessenberg and since A − λI is singular

the entry (n, n) of R is zero. Observing that

QHAQ = QH(QR + λI)Q = RQ + λI, (2.17) and computing the last row of RQ completes the proof.

If we have m shifts µ1, . . . , µmthat approximate m eigenvalues of A we can start the algorithm

(23)

CHAPTER 2. THE QR ALGORITHM 22 is theoretically analogous to apply consecutively the single shift algorithm using the shifts µi,

but using a shift polynomial of degree m we can deflate m eigenvalues in a single step.

Unfortunately, in practice, the use of shift polynomials of high degree incurs in serious conver-gence difficulties caused by roundoff errors. This phenomenon is called shift blurring. Watkins in [43] related this problem to the conditioning of the eigenvalues of the pencil B0− λN, where

B0=        x1 a1,1 a1,2 . . . a1,m x2 a2,1 a2,2 a2,m x3 0 a3,2 a3,m ... ... ... xm+1 0 0 am+1,m        , N =          0 1 0 1 ... ... 0 1 0 1 0          , (2.18)

and xi are the first m entries of the vector ρ(A)e1. Numerical experiments have shown that this

problem is often ill conditioned for large m. The simplest way to avoid shift blurring is to use steps with low degree shift polynomials. If one wishes to perform a QR iteration of multiplicity 30, say, one can instead perform 15 iterations of degree 2. This gives the same result in principle, but much better results in practice. With this observation, one can see an important opportunity to speed up the efficiency of computation in a parallel architecture. We study more deeply this fact in Section 4.3.

Usually, to improve the speed of convergence, we compute new shifts at each iteration of the algorithm. We have to compute as shifts, an approximation of the eigenvalues of A. A typical choice is to use as shifts the smallest eigenvalues of a bottom submatrix of A. For example the famous Wilkinson shift, takes the eigenvalue of smallest modulus of the 2 × 2 bottom matrix

an−1,n−1 an−1,n

an,n−1 an,n

. (2.19)

In [45] Wilkinson proved the global convergence of the QR algorithm that uses the Wilkinson shift, for symmetric matrices. We will see another choice of shift in Section 2.5.

Another important role of the shift polynomials is to preserve some symmetry of the eigen-values. Recall that a matrix with real entries has eigenvalues which are either real or complex. In the latter case they come in pairs (λ, ¯λ). So it is a good idea to use a degree 2 real shift polynomial that has as roots a complex conjugate pair. With this choice, at the end of the iteration we have again a real matrix, so we can use a real arithmetic in the whole algorithm.

2.5 Aggressive early deflation

Braman, Byers and Mathias in [11] developed a method for deflating eigenvalues that, combined with standard deflation, improves the convergence speed.

If λ is an eigenvalue of A, for the Remark 2.4.1, when we perform an iteration of the single shift QR algorithm using λ as shift we should have the deflation of the eigenvalue λ (in exact arithmetic). The authors of [11] noticed that when a large number of shifts is used for chasing many small bulges, it often happens that we have shifts that are equal to eigenvalues in machine precision, but the algorithm does not deflate them. Surely they will be deflated in the next one or two iterations, but it is natural to find a strategy to avoid to do more iterations if we just have the eigenvalue.

Suppose we are going to compute a large number s of shifts (1 < s n) to use them in the next sequence of bulge chasing. Pick a number k > s, for example k = d1.5se. Let A(1) _{= (a}(1)

(24)

CHAPTER 2. THE QR ALGORITHM 23 denote the matrix obtained at the end of the QR iteration, and consider the partition

A(1) = " A(1)₁₁ A(1)₁₂ A(1)₂₁ A(1)₂₂ # , (2.20) where A(1) 22 ∈ C

k×k. Since A(1)is upper Hessenberg A(1)

21 has only one nonzero entry, a (1)

n−k+1,n−k.

Let A(1)

2,2 = QT QH be the Schur decomposition of A (1)

2,2. Using the matrix In−k⊕ Q we can

transform by similarity the matrix A(1), obtaining

" A(1)₁₁ A(1)₁₂Q QH_A(1) 21 T # . (2.21) Since A(1)

21 has only one nonzero entry in the top rightmost corner, then the matrix Q H_A(1)

21 has

nonzeros only in the last column. We call that column x.

For illustration, the bottom portion of the transformed matrix has the following structure (in the case k = 5):           h h h h h h h h h h h h h h x1 t11 t t t t x2 t22 t t t x3 t33 t t x4 t44 t x5 t55           . (2.22)

From the illustration it is easy to see that if, for example, the last three entries of x are zero, we can deflate three eigenvalues. Of course the entries of x are never exactly zero, but numerically, we may assume them equal to zero if it holds that

|xj| < u min{|an−k+1|, |tjj|}. (2.23)

As we do for the inequality (2.11), it can be proved that setting xj to zero when it satisfies (2.23)

produces a relative backward error of the order of the machine precision, hence does not destroy the backward stability of the algorithm.

The aggressive early deflation procedure is roughly as follows. Check |xk|, if it is small enough

(as in (2.23)) set it equal to zero, then check |xk−1|and so on. Keep going until we find an xk−m

that is not enough small in modulus to be set to zero. In this case we swap rows of the matrix by similarity transformation since we bring the entry tk−m,k−m to the top of T . This swap

operation is described in Section 1.6.1. We continue this procedure until all the eigenvalues of T are inspected for deflatability.

At the end of this procedure we have to bring back the matrix in Hessenberg form. This operation has only a linear cost in the size of A(1), because the upper portion of the matrix is

still upper Hessenberg and we have just to return in upper Hessenberg form the bottom k × k part of the matrix. The linear cost of this Hessenberg reduction, with respect to the dimension of A(1), follows by the fact that when applying a matrix on the right we have to multiply that

matrix for all the last k columns of A(1) and not only the k × k bottom part.

If the eigenvalues of T that are not deflatable are more than s, we choose the s of them that have smallest modulus and we use them as shift for the next QR iteration. Instead, if the eigenvalues of T that are not deflatable are less than s we try again an aggressive deflation procedure on the matrix. We iterate the aggressive deflation until we have at least s eigenvalues that are not deflatable.

(25)

CHAPTER 2. THE QR ALGORITHM 24 Kressner in [27] developed a correspondence between the single shift QR algorithm enhanced with aggressive early deflation and a Krylov subspace method. In particular he used this corre-spondence to show that the use of aggressive early deflation improves convergence speed of the QRalgorithm.

(26)

Chapter 3

Chebyshev polynomials

Chebyshev polynomials play a fundamental role in approximation theory, in numerical linear algebra and in related applications. Moreover they satisfy many interesting properties which make them a powerful tool of theoretical analysis. For example they are fundamental to prove convergence results of the conjugate gradient method [13], and they are often used to design filters in signal processing [36].

A recent application, which is a representative example of their good numerical properties, is the Matlab package “Chebfun” [23, 37, 41], which allows to numerically work with smooth functions (for example to compute zeros, integrals, intersections, etc.). The approach used in Chebfun is to interpolate smooth functions at the Chebyshev points and to write the interpolant polynomial in the Chebyshev basis. This technique has good stability properties ad can be done in a fast way by using inverse cosine transforms. In such a context, finding roots of a polynomial in the Chebyshev basis becomes a fundamental task, for example to find zeros of functions or to solve optimization problems.

The main idea used to find the roots of a polynomial is to build a linearization matrix, usually called companion matrix, and find the eigenvalues of that matrix. This is what the Matlab command roots does for computing the roots of a polynomial of degree n expressed in monomial (or Chebyshev if we use Chebfun) basis. This method computes the roots of a polynomial using O(n2₎ memory storage and O(n3₎ operations, where n is the polynomial

degree.

To reduce this cost, the structure of the companion matrix can be exploited. There is a broad literature concerning the analysis of the rootfinding problem for polynomials represented in the power basis. In particular [3,4] use the structure of unitary plus a rank-one perturbation to build an algorithm that uses a linear memory storage and has a quadratic cost.

The approach pursued in this thesis is to exploit the structure of the companion matrix. For polynomials expressed in the Chebyshev basis, the companion linearization is endowed with a symmetric plus a rank-one structure. This fact will allow to design a fast and backward stable rootfinding algorithm based on the QR iteration. The key observation is that the symmetric plus rank-one structure is preserved by the QR iterations, and can be leveraged to efficiently approximate the matrices througout the algorithm. In fact, the overall computation cost of this algorithm is O(n2₎ arithmetic operations with O(n) memory storage, where n is the degree of

the polynomial.

(27)

CHAPTER 3. CHEBYSHEV POLYNOMIALS 26

3.1 Orthogonal polynomials

In the following we denote with P the vector space of polynomials with real coefficients and with Pn the vector subspace of P made by all polynomials with degree less or equal than n. We call

monomial basis, or power basis, the basis {1, x, x2_{, . . . }}of P.

Definition 3.1.1. Given a scalar product h·, ·i on P, a set of polynomials {pi(x) ∈ Pi, i =

0, 1, . . . } such that deg(pi) = i and hpi, pji = 0 if i 6= j is called set of orthogonal polynomials with respect to the scalar product h·, ·i.

If in addition hpi, pii = 1 for all i the set is called orthonormal.

Using the Gram-Schmidt process it is always possible to construct a set of orthogonal poly-nomials.

Let ω(x) : [a, b] → R ∪ {±∞} a function such that ω(x) ∈ R, ω(x) > 0 for all x ∈ (a, b) and there exists finite´b

af (x)ω(x)dxfor all f(x) ∈ P(x). It is easy to prove that

hf, gi := ˆ b

a

f (x)g(x)ω(x)dx, (3.1) is a scalar product.

A useful relation valid for orthogonal polynomials is given by the following

Theorem 3.1.1. (Three term recurrence) Let pi(x), i = 0, 1, . . . , a set of orthogonal polynomials on [a, b] with respect to the scalar product (3.1). There exist Ai, Bi, Ci∈ R such that

pi+1(x) = (xAi+1+ Bi+1)pi(x) − Cipi−1(x), i ≥ 1, Ai+1, Ci6= 0. (3.2)

3.1.1 Chebyshev polynomials

The Chebyshev polynomials of the first kind are ortogonal polynomials, with respect to the scalar product (3.1), where

ω(x) = (1 − x2)−12, (3.3)

and [a, b] = [−1, 1]. We denote these polynomials by using the letter T (i.e., T0(x), T1(x), . . .).

It can be proved that the three-term recurrence for Chebyshev polynomials is Tn+1(x) = 2xTn(x) − Tn−1(x),

T0(x) = 1, T1(x) = x.

(3.4) Another useful property is given by the following:

Proposition 3.1.1. For Chebyshev polynomials of the first kind it holds

Tn(cos(θ)) = cos(nθ), (3.5) for all θ ∈ [0, 2π] and for all n.

It is well known that the three-term recurrence and property (3.5) are equivalent conditions for the orthogonality with respect the weight (3.3) on [−1, 1].

(28)

CHAPTER 3. CHEBYSHEV POLYNOMIALS 27

3.2 Companion matrix in Chebyshev basis

Let {T0, . . . , Tn} be the basis of the vector space Pn formed by the first n + 1 Chebyshev

poly-nomial (of the first kind). Let us consider a polypoly-nomial

P (λ) := P0T0(λ) + · · · + PnTn(λ), (3.6)

where P0, . . . , Pn ∈ C. Our goal is to design effective algorithms for computing the roots of P ,

given P0. . . , Pn.

By relying on the following proposition we can transform the rootfinding problem to an eigenvalue problem.

Proposition 3.2.1. The roots of P are equal to the λ ∈ C such that

det(L0− λL1) = 0, (3.7) where L0=        −Pn−1 Pn− Pn−2 −Pn−3 . . . −P0 1 0 1 ... ... ... 1 0 1 1 0        , L1=        2Pn 2 ... 2 1        . (3.8)

In particular the rootfinding problem for P is equivalent to the generalized eigenvalue problem associated with the pair (L0, L1).

Proof. Let λ ∈ C be a root of P and let xk := Tk(λ) for k ∈ {0, . . . , n}. Then we obtain the

following identity in λ

P0x0+ · · · + Pnxn= 0. (3.9)

From the three term recurrence of Chebyshev polynomials we have

x1= λx0 and xk= 2λxk−1− xk−2, for all k ∈ {2, . . . , n}. (3.10)

Relying on (3.10) we can delete xdfrom the equation (3.9), obtaining

P0x0+ · · · + Pn−3xn−3+ (Pn−2− Pn)xn−2+ Pn−1xn−1+ 2λPnxn−1= 0. (3.11)

Putting together (3.10) and (3.11), we obtain that if λ is a root of P (x) then it is a solution of the generalized eigenvalue problem (3.7). On the other hand, if λ is a solution of the generalized eigenvalue problem (3.7), there exists a vector

y =      yd yd−1 ... y0      ∈ Cm, y 6= 0, (3.12) such that (L0− λL1)y = 0. (3.13)

From the last row of (3.13) it follows that

(29)

CHAPTER 3. CHEBYSHEV POLYNOMIALS 28 and from the ith row of (3.13) it follows that

yi−2+ yi− 2λyi−1= 0, (3.15)

for i = 2, . . . , n − 1. Hence the entries of y satisfy the three-terms recurrence evaluated at λ. Therefore yi= y0Ti(λ)for i = 0, . . . , n. Considering the first row of (3.13) we have

0 = P0y0+ · · · + Pn−3yn−3+ (Pn−2− Pn)yn−2+ Pn−1yn−1+ 2λPnyn−1

= y0(P0T0(λ) + · · · + Pn−3Tn−3(λ) + (Pn−2− Pn)Tn−2(λ) + Pn−1Tn−1(λ) + 2λPnTn−1(λ))

= y0(P0T0(λ) + · · · + Pn−3Tn−3(λ) + Pn−2Tn−2(λ) + Pn−1Tn−1(λ) + PnTn(λ)).

(3.16) We conclude that λ is a root of P (x). Note that y06= 0, indeed if y0= 0then all the vector y is

equal to 0.

Without loss of generality, we may assume Pn > 0 and rewrite the generalized eigenvalue

problem (3.7) as the standard eigenvalue problem det p L1 −1 L0 p L1 −1 − λI = 0, (3.17)

where we denote by√L1the diagonal matrix with positive entries such that

√ L1 2 = L1. Let A := √L1 −1 L0 √ L1 −1. We notice that A = F + uvH (3.18) where F : =pL1 −1 TpL1 −1 , where T =   0 1 1 0 1 ... ... ... 1 0 1 1 0  , u : =pL1 −1 e1= [1/ p 2Pn, 0, . . . , 0]T, v : =pL1 −H [−Pn−1, Pn− Pn−2− 1, −Pn−3, . . . , −P0]H. (3.19)

In particular F is real symmetric and A is in Hessenberg form. In Chapter 4 we will design and analyze a suitable algorithm to compute the eigenvalues of matrices in this form.

3.3 Chebyshev points and interpolants

In this section we describe how to construct good polynomial interpolants for functions defined on a compact interval. Any interval [a, b] can be scaled to [−1, 1], so we just consider [−1, 1] for simplicity.

Definition 3.3.1. Given n ∈ N, we define Chebyshev points associated with n the set x0, . . . , xn, where xj := cos πj n . (3.20)

(30)

CHAPTER 3. CHEBYSHEV POLYNOMIALS 29 Let {fj}, 0 ≤ j ≤ nbe a set of numbers which may come from evaluation of a function f(x)

at the Chebyshev points. Then there exists a unique polynomial pn ∈ Pn that interpolates these

data, i.e., pn(xj) = f (xj)for each j. We call this polynomial the Chebyshev interpolant.

Recall that the interpolation problem at equidistant points is a very ill-conditioned problem, where the condition number, expressed by the Lebesgue constant, grows exponentially with the degree. On the other hand the interpolation problem at the Chebyshev points is well conditioned. In fact, the Lebesgue constant in this case grows just logarithmically with the degree. An example of difficulty encountered with equispaced points is the Runge phenomenon, described in [42, Chapter 13].

Another interesting feature of Chebyshev polynomials is given by their approximation prop-erties as expressed by the following

Theorem 3.3.1. For n ≥ 1 let pn ∈ Pn be the Chebyshev interpolant of f. If f(x) ∈ Ck([−1, 1]),

k ≥ 1then there exist γ ∈ R, γ > 0 such that ||f − pn||∞≤ γ log(n) nk (2 + 2 πlog(n + 1)), (3.21) and so lim n→∞||f − pn||∞= 0. (3.22)

It is a good idea to represent Chebyshev interpolants in the Chebyshev basis, indeed this can be done with low computational cost and in a stable way.

We denote C :=        T0(x0) T1(x0) . . . Tn−1(x0) Tn(x0) T0(x1) T1(x1) . . . Tn−1(x1) Tn(x1) ... ... ... ... ... T0(xn−1) T1(xn−1) . . . Tn−1(xn−1) Tn(xn−1) T0(xn) T1(xn) . . . Tn−1(xn) Tn(xn)        , (3.23)

the matrix that has as entries the entries of the Chebyshev basis of Pnevaluated at the Chebyshev

points, f :=        f (x0) f (x1) ... f (xn−1) f (xn)        , (3.24)

the vector that has as entries the function f evaluated at the Chebyshev points and y the vector of Chebyshev interpolant coefficients. To compute the coefficients, in the Chebyshev basis, of the interpolant polynomial we have to solve the linear system

Cy = f . (3.25)

The matrix C defines the discrete cosine transform and, using the orthogonality of Chebyshev polynomials, it can be proved that

CTC = n      1 1 2 ... 1 2      , (3.26)

(31)

CHAPTER 3. CHEBYSHEV POLYNOMIALS 30 so the system (3.25) can be solved in O(n log(n)) operations using similar techniques of fast Fourier transform, that are backward stable with respect to f. That is the computed vector y contains the coefficients of the Chebyshev interpolant of a function ˆf such that

ˆ

f (xi) = f (xi) + δi for i = 0, . . . , n, (3.27)

where

kδk2

kf k = O(u), (3.28)

where u is the machine precision. Another good reason to use Chebyshev interpolants is related to their stability properties. It is well known that if p is a polynomial expressed in monomial basis, then its roots are equal to the eigenvalues of a certain companion matrix formed from its coefficients. Indeed the command roots of Matlab computes the roots of p by using this property. This method of zerofinding is numerically backward stable in matrix sense, but it can be very sensitive to perturbations in the coefficients as Wilkinson has pointed out in [46].

There is an exception to this difficult situation. Finding roots of a polynomial represented in the power basis is a well conditioned problem in the special case of polynomials with roots on or near the unit circle. The trouble is that most applications are not of this kind. More often, the roots of interest lie in or near the real interval, and in such case the rootfinding problem becomes ill conditioned and the representation in the monomial basis should be avoided. This is not the case of representation in the Chebyshev basis for polynomials having roots close to the real axis [42].

(32)

Chapter 4

The Algorithm for scalar

polynomials

4.1 Structured QR

4.1.1 Vector representation

In this section we describe a QR algorithm to compute eigenvalues of a matrix, in Hessenberg form, that can be written as a Hermitian matrix plus a rank one perturbation. Here we follow the ideas developed by Eidelman et al. in [17].

Let Fn ∈ Cn×n be the class of n × n upper Hessenberg matrices A := (ai,j) ∈ Cn×n of the

form

A = F + uvH, (4.1)

where F = (fi,j)is Hermitian and u, v ∈ Cn. We observe that any matrix of the form Hermitian

plus a rank one perturbation can be brought back, by unitary similarity transformations, to a matrix in Fn by using the Hessenberg reduction algorithm described in Section 2.2. Another

important observation is that if we perform a QR iteration on a matrix in Fn we obtain again

a matrix in that class. As we have shown in Section 2.3, the Hessenberg form is preserved by QR iteration and and it is easy to notice that acting by congruence, using a unitary matrix, on a matrix in Fn we obtain again a Hermitian matrix plus a rank-one correction. That is, if

A = F + uvH _{∈ F}

n and Q is unitary, then

QAQH = QF QH+ (Qu)(Qv)H, (4.2) and if F is Hermitian then QF QH is Hermitian too. This is a crucial observation which allows

us to reduce the computational cost of the algorithm.

Let d ∈ Cn and β ∈ Cn−1be the vectors whose entries are the diagonal and the subdiagonal

entries of A, respectively. Using the structure of A we can compute every entry of A storing only d, β, u, v. Since A is a Hessenberg matrix the lower triangular part is completely determined by β and d. To compute the upper triangular part of A we notice that since F is Hermitian we get for all i, j ∈ {1, . . . , n} ai,j = fi,j+ uivHj = f H i,j+ uivjH= (aj,i− ujviH) H_{+ u} ivjH. (4.3)

So we can compute the entries in the upper triangular part of A only using the lower triangular part of A and the vectors u and v.

(33)

CHAPTER 4. THE ALGORITHM FOR SCALAR POLYNOMIALS 32 Since the structure of the matrix is preserved after a QR iteration we can represent every matrix A(i), obtained after a QR step, by means of four vectors d(i)_{, β}(i)_{, u}(i)_{, v}(i). Hence, to

compute the eigenvalues of a matrix in Fn, we can use a structured version of the QR iteration

that at every step updates only the vectors d(i)_{, β}(i)_{, u}(i)_{, v}(i). In particular using the structured

QRthe memory storage is linear, in contrast to the quadratic cost of the standard QR algorithm. The following observation is crucial in order to improve the stability of the structured algo-rithm. We observe that applying equation (4.3) to the diagonals entries dk= ak,kwe obtain the

equalities

dk− ¯dk= −vkuHk + ukvHk , k ∈ {1, . . . , n}

or equivalently

dk= <(dk− ukvkH) + ukvkH, k ∈ {1, . . . , n}. (4.4)

In practice the condition (4.4) may be violated because of errors in computation of dk. During

the algorithm we force that condition.

4.1.2 Stability of vector representation

Let us now prove that the vector representation is stable, i.e., a small perturbation on the generators corresponds to a small perturbation on the whole matrix. This is important because during the algorithm updating the vectors produces small errors on them. The stability of vector representations guarantees us that those errors produce a small perturbation on the starting matrix, hence if the algorithm updates the generators in a backward stable way, than it is backward stable in terms of the whole matrix too.

Let A = F + uvH _{∈ F}

n. Let d, β, u, v be generators of A. Let d + ∆d, β + ∆β, u + ∆u, v + ∆v

be perturbed generators. We suppose ||∆d||2 ||d||2 = O(), ||∆β||2 ||β||2 = O(), ||∆u||2 ||u||2 = O() ||∆v||2 ||v||2 = O(). (4.5) Let ∆A the difference of the matrix constructed using perturbed generators and the matrix A. We want to prove that,

||∆A||F

||A||F

= O(), (4.6)

where || · ||F is the Frobenius norm. As additional hypothesis we suppose that

||u||2||v||2