View metadata, citation and similar papers at [Link].

uk brought to you by CORE

provided by Elsevier - Publisher Connector

A Constrained Eigenvalue Problem*

Walter Gander
Znstitut fir Znfonnatik,
ETH Zetltnrm
CH-8092 Ziirich
Switzerland

Gene H. Golub
Department of Computer Science
Stanfurd University
Stanford, Califnnia 94305
and
Urs von Matt
Znstitut fir Znformatik,
ETH Zentrum
CH-8092 Ziirich
Switzerlund

Dedicated to Alan J. Hoffman on the occasion of his 65th birthday.

Submitted by Richard A. Brualdi

ABSTRACT

Let A be a real symmetric matrix. In order to find the eigenvector corresponding

to the smallest eigenvalue of A, we find the minimizer of the expression xTAr subject
to xTx = 1. In many applications, however, it is necessary to introduce linear con-
straints: NTx = t. In this paper we first show how to eliminate these linear constraints.
Then the minimization is tackled by employing Lagrange equations. An analysis of
the solvability of the problem and the sensitivity of the solution x is given. We show
how the problem can be reduced to a so-called secular equation that we solve by a
conventional zero-finding process. Alternatively, we present a second method which
transforms the Lagrange equations into a quadratic eigenvalue problem. The two
approaches are compared to each other.

*This work was in part supported by the National Science Foundation under Grant NSF
CCR-8412314 and by the US Army (DAAL.O3-87-K-0095).

LINEAR ALGEBRA AND ITS APPLEATIONS 114/115:815-839 (1989) 815

0 Elsevier Science Publishing Co., Inc., 1989

655 Avenue of the Americas, New York, NY 10010 0024-3795/89/$3.50
816 W. GANDER, G. H. GOLUB, AND U. VON MATT

1. INTRODUCTION

In this paper we consider the following mathematical and computational

problem. Given the quantities

A: (n + m)-by-( n + m) matrix, symmetric, n > 0,

N: (n + m>by-m matrix with full rank,
t: vector of dimension m with II( tll < 1.

Determine an x such that

xTAx = min (1)

subject to the constraints

NTx = t, (2)

xTx=l. (3)

Variants of this problem occur in many applications [l, 5, 7, 8, 111. The

problem has been studied previously when t = 0, the null vector (cf. [4, 61).
When t + 0, then the problem becomes more complicated. We now
motivate our assumptions. Suppose N does not have full rank. If t is not in
the range of N ‘, the problem has no solution. If, however, the linear
constraints are consistent, we can deflate the system until we get a submatrix
of full rank. In the extreme case, where N = 0 and t = 0, the problem reduces
to the ordinary eigenvalue problem with an eigenvector corresponding to the
smallest eigenvalue of A as the solution.
Now consider the quantity ]I(NT)+ t/l. As (NT)+ t denotes the unique
solution of NTx = t of minimal norm, we can make the following distinctions:
when lI(Nr)‘tll > 1 there is no solution. In the case of Il(NT)‘tll = 1 the
unique solution is given by x = (N r)’ t. Therefore, the condition I/(N T, + t I(
< 1 is the only interesting case.
Thus when /I(NT)’ tJ( < 1, we can always find an x that satisfies both
constraints, and hence there always exists at least one solution to the
problem.

2. PROBLEM SIMPLIFICATION

In this section we will normalize the problem in order to study its

solvability. These considerations are not only of theoretical interest, but they
also serve as a basis for the numerical calculations.
CONSTRAINED EIGENVALUE PROBLEM 817

2.1. Elimination of the Linear Constraint

In the domain of the transformation NT we can distinguish two funda-
mental subspaces:

Jv( NT): nullity of NT,

J-(W)5 orthogonal complement.

If the transformation NT is restricted on -K(NT) ‘, it acts as a bijection

between JY( N T, ’ and a( NT) with the inverse (NT) +. Thus the general
solution of the first constraint is given by

with an arbitrary E c JY( N T). Now using the singular value decomposition
of NT,

NT= UZVT

with
m

u= * m
[ 1

we can write x as

with an arbitrary z. For the subsequent minimization, we only have to

consider the second constraint (3).
For practical reasons, we can use the QR decomposition of N instead of
the singular value decomposition. To simplify the first constraint (2), we
write

PTN= ; ) (4
[ I

where P denotes an orthogonal matrix, and R is a m-by-m upper triangular

818 W. GANDER, G. H. GOLUB, AND U. VON MATT

matrix. Now the problem can be formulated as

xTAx = xTPPTAPPTx = min,

NTx=[fir O]PTx=t,

xrx = xTPPTx = 1,

We now make the definitions

pT&, =:

[ r cn
B
1 r’ In
(5)

(6)
Note that CT = C. Now

xTAx = [ YT
zT1[; :][:I

= yTBy+yTrTz+zTry+zTCz

= yrBy+2zrry+zTCz,

NTx= [ET O][;]=HTy=t,

xTx = [yl‘ zT I[; 1 =y“y+zTz=l.

So we have reduced the constraint (2) to an ordinary linear system with an

upper triangular matrix. Now

y=RFt (7)

and with the help of the definitions

s2 := 1 - yry > 0, (8)

b:= -ry, (9)

we get the simplified problem

zTCz - 2bTz = min,

(10)
zrz = s2,

This problem has been extensively studied in the literature (cf. [2, 7, 8, lo]).
CONSTRAINED EIGENVALUE PROBLEM 819

2.2. Stationary Points

In order to calculate the stationary points, we set up the so-called
Lagrange principal fin&ion:

Q(z, A) := z*Cz - 2bTz - X(z*z - s2). (11)

Differentiating Cpwith respect to z and X yields the equations

2Cz-2b-2Xz=O,

z*z - ss = 0.

or, normalized,

Cz = Xz+b,
(12)
z*z= s2*
Now let us compare the values zTCz - 2bTz of different tuples (X,z).
Following the proof given in [3, 121, a short calculation shows that the
smallest A is needed in order to minimize the value z*Cz - 2brz. So in place
of the original minimization we can solve the Lagrange equations

Cz = Xz+b,

zTz = ss, (13)

h = min.

3. SOLVABILITY

We will now investigate the solvability of the Lagrange equations (13).

Simultaneously this analysis will point out a first method to solve the
problem.

3.1. Explicit Secular Equation

For our discussion, we need the eigenvalue decomposition

C = QDQ’, (14)
820 W. GANDER, G. H. GOLUB, AND U. VON MAT-T

where

D=diag(S,,...,S,), S,I6,_< ..’ 56,

and

Q'Q = I.

Thus the Lagrange equations (13) are transformed as follows:

QDQ’z = AQQ’z + b

With the definitions

u := QTz, (15)

d := QTb, (16)

this can be simplified to

Du = Xu+d,

UTU= s2, (17)

X = min.

First let us suppose X E A( 0). Then there exist diagonal elements Si with
Si = A. For the ensuing discussion the following index sets turn out to be
useful:

I:= {$3,=X},

I:= {ipi f A} = {l,..., n}\Z.

CONSTRAINED EIGENVALUE PROBLEM 821

If there exists a corresponding u for such a h, it must hold that Wi : 6,ui =

Xui + di with uTu = s2. Then for i E I, it must be true that Xui = Xui + d,,
and this implies d i = 0. And for i E Z, it must hold that

The normalization condition uTu = s2 can only be satisfied if

As a result we have the following three possibilities:

1. There exists no solution u for a given X E X(D) if 3i E I: di + 0, or

2. There exists a unique solution u for a given X E X(D) if Vi E I : d i = 0

and

Then u can be calculated as

di iEi
ui= q-x
i 0 iEZ.

3. There exist several solutions u for a given h E h(D) if Vi E I: d i = 0,

and

<s2.
822 W. GANDER, G. H. GOLUB, AND U. VON MATT

The possible values for u are given by

di
Ui=6,, i E j,

Thus the set of all solutions u constitutes a manifold of dimension III - 1

because the ui with i E Z can be chosen arbitrarily on the given hypersphere.

The second case is given by h e A(D). Then the inverse (D - AZ ) -’

exists and u has the representation

u=(D-XI)-‘d. (18)

For u to solve the normalization condition uru = s2 it must hold that

We define

(19)

as the so-called explicit secular function (see Figure 1). Thereby the La-
grange equations (13) have a unique solution u for a given X e h(D) if and
only if the explicit secular equation

f(h):= ,cl & - ?=o (20)

i 1 i

is satisfied.
If d, = 0 for all i, the secular function (20) degenerated into f(X) =
- s2 -C 0 and therefore possesses no solutions. In this case the desired A lies
CONSTRAINED EIGENVALUE PROBLEM 823

FIG. 1. Graph of the secular function.

in the spectrum h(D). Thus let k be the index of the first di f 0, i.e. d, # 0
and vi < k : d i = 0. So we can write the secular function (19) as

with 6, f 0. For h increasing from - 00 to S,, f(X) increases strictly, since

the derivative

is positive for - 00 < A < 6,. From the limits

it immediately follows that for X < 6, there exists exactly one solution.
824 W. GANDER, G. H. GOLUB, AND U. VON MAlT

Then the desired smallest A can be located either inside or outside the
spectrum X(D). With the help of the index set Z := {i) 6, = 6,) we can
distinguish two alternatives:

1. It holds that Vi E I: d, = 0, and

It follows that for h = S,, there exists a solution of the Lagrange equations
(13). f(X) possesses no more solutions for X < S,, since

Thus with X = 8, we have found the smallest A.

2. Or it holds that 3i E I: d, # 0, or

It follows that f(X) has a singularity for X = 6,, or else

Therefore f(h) has exactly one solution for h < 6,. This solution represents
the desired smallest A.

Hence, in both alternatives, the smallest h always satisfies the condition

x < 8,.

3.2. Implicit Secular Equation

The above discussion on the location of the smallest X that solves the
Lagrange equations (13) can be carried out even without the calculation of
the eigenvalue decomposition (14) of C. This is useful when we want to avoid
this factorization numerically.
CONSTRAINED EIGENVALUE PROBLEM 825

As indicated before, we know that the desired X satisfies X < 6,. So for
A = S, the following cases can be distinguished:
1. The equation Cz = 6,~ + b can be inconsistent, i.e.,

(C-6,Z)(C-G,Z)+b#b.

In this case we have X < S,, and the implicit secular equation

f(X)=bT(C-AZ)-%-s2=0 (21)

must be solved.
2. Now we assume that the equation Cz = 6,z-t b is consistent. The
expression (C - all)+ b represents the solution with smallest norm. If
I](C - 6,Z)+ blJ > s, the normalization condition cannot be satisfied, and we
have to solve again the secular equation (21).
3. If however Il(C - &,I)+ bll = s, we have found the unique solution of
the Lagrange equations (13).
4. Finally it can happen that jl(C - S,Z)+ b(l < s. Let kc’),.. ., e(k) de-
note the k orthonormal eigenvectors corresponding to the eigenvalue 6,.
Since

(C-6,Z)+bIM(C-&I),

5(‘) E JV(c - &I),

every vector

z=(C-8,Z)+b+cJ(‘)+ ... +cJ(~)

with

cl”+ . . . + ck”= s2- Il(C - &I) +b112

solves the Lagrange equations (13). Therefore the set of solutions constitutes
a manifold of dimension k - 1.

3.3. Condition of the Secular Equation

The calculation of the smallest zero X of the secular equation (20), (21) is
a delicate procedure. Even small errors Ah can result in large deviations Ax
of the solution x and A min of the minimal value min. To illustrate the point
826 W. GANDER, G. H. GOLUB, AND U. VON MA-l-T

we will approximately determine the deviation Ax and A min if AX is given.

We will assume that for small AX the quantities Ax and A min are essentially
linearly dependent on AX.
Starting with the smallest zero X of the explicit secular equation (20) x
and min are computed as follows: u := (D - XZ))‘d, z := Qu,

and

min := xrAx = [Y’ z”l[F ;I[;].

If instead of the theoretical zero X, the value X + Ah is used, the result is

as follows:

u+Au= [D-(h+Ah)Z] -‘d

+ 0(Ax2).

From this it follows that Au = (D - AZ)-ad Ax. Now, we have z+ Az =

Q(u+ Au), so AZ = QAu, and

x+Ax=P

implies

Finally,

min + A mm = (x + Ax)rA(x + Ax)

= xTAx+2xTAAx+ AxTAAx,

so that

A min = 2xTA Ax
CONSTRAINED EIGENVALUE PROBLEM 827

Now considering that

2xTA Ax = 2xTPPTAPPT Ax

=2[yT
z’l[F r,‘l[Ll
= 2yTTTAz+2zTCAz

= 2(zTC - bT) AZ,

we get for the deviations Ax and Amin the values

0
Ax=P
Q(D-XZ)-2d I A’

= K(X) AX (22)
and

= K(min) AX. (23)

Here the quantities

1
0
++=P Q(D_Az)-2d , (24)
[

(25)

are the condition vector of x and the condition number of min. In the actual
computation K(X) and K(min) can be calculated as well, and one can get an
estimate of the numerical error.
The value of I\K(x)[\ is bounded as follows:

(26)
828 W. GANDER, G. H. GOLUB, AND U. VON MAT-I

If d happens to be an eigenvector to the eigenvalue 6, of D, then we have an

equality. Similarly, we can bound the condition number of min:

I [Q(D_Ohr)-2d]l
tK(min)t=aTAP

(27)

However, we have a strict inequality now. We can prove this by contradic-

tion. Without loss of generality, let us assume P = Z and Q = I. That is, we
could apply the transformations (4) and (14) beforehand and start right away
with a matrix A, where the trailing n-by-n submatrix is diagonal, and with an
upper triangular matrix N. Suppose that we are given a problem where the
bound on Irc(min)l is attained. This essentially implies that

1x2 W = IlxllIJAIlIIWI.

This equality can only be satisfied if Ax is an eigenvector to the largest

eigenvalue (in absolute value) of A. Furthermore, x and Ax must be parallel,
i.e. x is a multiple of Ax. As the first m elements of Ax are zero, so are the
corresponding elements of x. Equation (6) implies y = 0, and from (9) it
follows that b = 0. But from (16) we have d = 0, so the desired smallest X of
the Lagrange equations (13) lies in the spectrum X(C), and we would not be
solving the secular equation at all.
Thus it is obvious that we have to face large errors if the smallest zero h
of the secular equation (20), (21) is near the smallest eigenvalues 8, of C.
Since the norm of the matrix A is normally bigger than 1, an inaccurately
determined zero affects the minimal value min more than the solution
vector x.

4. ZERO FINDER

Now, we want to calculate the smallest zero of the secular equation (20)
with d, # [Link] will solve it by using an iterative method. Suppose we know
CONSTRAINED EIGENVALUE PROBLEM 829

an approximation Xci). Then we can approximate f(A) with the replacement

function

in such a way that

g( P’) = f( iv),

g’( x(i)) = f( A(i)).

The zero of g(X) will determine the next approximation ti” ‘).
A short calculation yields the values

a= 4 (fW’) + 4”
f2($0) ’

and for the zero 8’ + ‘) = b - G/s of the replacement function g(X) we get

x(i+l)~x(i)__zf(x(‘))+s2 NW=
( i
-1 .

f’( F’) S

It can be shown that this iteration process will yield a strictly decreasing
sequence of approximations xc’). The reader is referred to [9, 121.

4.1. lnitial Value

Now, in order to start the iteration we need to construct an initial value.
For a first guess the reduced secular equation

s2=o
830 w. GANDER, G. H. GOLUB, AND U. VON MA’IT

is useful. This leads to the initial value

p = 6
k
- !!A!
s .

For this A(‘) it is obvious that A@’ < 6, with j-(X0’) > 0.

4.2. Stopping Criterion

In theory, the iteration process yields a strictly decreasing sequence of
approximations h“’ , but this property does not persist in finite arithmetic. It
is therefore reasonable to terminate the iteration when the strict monotonicity
is lost, namely if A” + i) 3 x”‘. This method has the advantage that it is
machine-independent and that it does not need any knowledge of machine
accuracy.

4.3. Implicit Secular Equution

If we do not want to compute the eigenvalue decomposition (14) of C, we
have to consider the evaluation of the implicit secular function

f(A)=br(C-AZ))%--’ (29)

and its derivative

f’(h) = 2br(C- AZ) P3b.

With the definitions

u:=(C-M-lb,

u‘:= (C- XI) -I”,

these values can be expressed as

f(h) = Ju - s2,

f(h) = 2uTu’.

Therefore each iteration step requires the solution of two linear systems with
the matrix C - AZ.
CONSTRAINED EIGENVALUE PROBLEM 831

Again with explicit secular equation, the quantity

jp’= 8
k
- Id,l
s

yields an initial value with f(x”)) >, 0 and A”’ < 6,. If the column vector q,
of Q were known, we could compute the value d,, since (16) implies
d, = qib. If, however, we have an eigenvector 5 with ljElj = 1 corresponding
to the smallest eigenvalue S, of C, it is straigtforward to use the quantity

jp, := 6, lETbl
s

as an initial value. Then it can be shown [12] that f( X0’) >, and x”’ < 6,
holds when tTb f 0.

5. QUADRATIC EIGENVALUE PROBLEM

The two previously mentioned methods have the property that they
reduce the problem to finding the solution of a one-dimensional secular
equation. Considering the problem from another point of view, the Lagrange
equations (13) can be reduced to a quadratic eigenvalue problem. For the
derivation let us assume X P X(C). In this case z can be written as

z=(C-hZ)-‘b.

Taking into account the normalization condition for z, we get the secular
function

f(X)=bT(C-AZ)-%-&

of which the zeros are to be computed. The task looks different if we make
the definition

y:=(C-AZ)-%,
8.32 W. GANDER, G. H. GOLUB, AND U. VON MATT

so that

(C - AZ)2y = b.

Instead of the secular equations, we have to solve the system

bTy - s2 = 0, (30)

(31)

The first condition (30) can also be formulated as

Using this factor 1 as a coefficient of b in (31) we get the quadratic

eigenvalue problem

(C- hZ)‘y = ;bbTy_

Note that the restriction X E X(C) is no longer necessary. Of course, we must

face the fact that the set of solutions for h has been extended by these
manipulations, for two equations cannot be formulated as a single one
without consequences. Subsequently we will compare the solutions of the
quadratic eigenvalue problem (32) with those of the Lagrange equations (13).

5.1. Solvability
We show the following. Assume h and z fulfill the Lagrange equations

Cz=hz+b,

THEOREM 5.1. The quadratic eigenvalue probkm

has a solution for this A.

CONSTRAINED EIGENVALUE PROBLEM 833

Proof. In our proof, we have to distinguish whether X lies in the

spectrum A(C) or not.

Case 1: X E X(C). Let y be an eigenvector of C with the eigenvalue

A. Then b =(C- hZ)z implies bry = zr(C- AZ)Y = 0. From this it follows
that

(C-AZ yy = 0,

;bbTy=O,

and hence y satisfies the eigenvalue equation.

Case 2: h B A(C). With the definition

y:=(C-AZ)%

it follows that

(C-AZ)“y=(C-XZ)z=b,

= ;bzTz = b,

and again y satisfies the eigenvalue equation.

Therefore, we can construct a solution y of the quadratic eigenvalue problem

(32) in both cases. H

Conversely, we can assume that X and y fulfill the quadratic eigenvalue

equation

(C- hZ)ey = ;bbry, x E X(C).

834 W. GANDER, G. H. GOLUB, AND U. VON MAT-I-

THEOREM 5.2. X and z := (C - Al)- ‘b jdfill the Lagrange equations

Cz=Xz+b,

zTz= s2.

Proof. Obviously the first equation is satisfied. Multiplying the quadratic

eigenvalue equation (32) by (C - AZ) 2, we get

1
y=-$bry)(C-hZ)p%+O.

This implies b’y f 0 and

The square of the norm of z becomes

z=z= b=( C - Al) “b = bTgy = 92 = s2,

with which the second equation is satisfied too. n

Finally, we assume that h and y fulfill the quadratic eigenvalue equation

(C- XI)‘y = ;bb’y, h E X(C).

We define u := (C - XI)+ b.

THEOREM 5.3. For the solvability of the Lagrange equations

Cz=hz+b,

zTz = s2

we can make the following distinction: If the Lagrange equations are

inconsistent, i.e. (C - XI )u + b, or if uTu > s2, then there is no solution fm
CONSTRAINED EIGENVALUE PROBLEM 835

this X. On the other hand, if the equutions are consistent, we have a unique
solution z = u fm uTu = s2, and several solutions fm uTu < s'.

Proof. If (C-XI)u=(C-XZ)(C-AZ)+b#b, then bg%‘(C-hl),

and the Lagrange equations have no solution for this X. Let b E 9( C - AI)
in the following. Then (C - hI)u = (C - XZ)(C - hI)+ b = b, and the first
Lagrange equation is satisfied.
The vector u denotes the solution with smallest norm of the equation
Cu = Xu+ b. Therefore, if IJuJj > s, the normalization constraint zTz = s2
cannot be satisfied, and we have no solution of the Lagrange equations for
this A. In the case of ((~(1= s, the vector u denotes the unique solution.
Finally, let us assume that j(u(J < s. The vectors f$‘), . . . , tck’ are chosen as
k orthonormal eigenvectors corresponding to the eigenvalue X. As

uL4-(C-AZ),

EC’)E Jv(C - AZ),

all the vectors

z = u + Clip + . . . + ckp

with

c,2+ ... + ck”= s2- l1ul12

are solutions of the Lagrange equations. Therefore, the set of solutions

constitutes a manifold of dimension k - 1. n

Discussing the solvability of the Lagrange equations (13) we derived the

result that the solution with the smallest h must satisfy A < 6,, where 6 1
denotes the smallest eigenvalue of C. Let X be hereafter the smallest
eigenvalue of the quadratic eigenvalue equation (32). With the aforemen-
tioned theorems we can make the following distinction:

1. It can hold that h < 6,. Then h lies outside the spectrum X(C), and
z := (C - AZ) - ‘b fulfills the Lagrange equations (13). The solution is unique.
2. Now let X = 8,. The vector u := (C - Xl)+ b must satisfy the equa-
tion Cu = Xu+ b. If uTu = s2, then z := u is the unique solution of the
Lagrange equations (13).
8.36 W. GANDER, G. H. GOLUB, AND U. VON MAT-T

3. Finally, if uTu < s2, we must find an eigenvector 5 to the eigenvalue

X of C with 4’6 = s2 - uTu. Then, z := u + E represents one of the many
solutions of the Lagrange equations (13).

5.2. Solving the Quudratic Eigenvalue Problem

The quadratic eigenvalue problem (32) can be reduced to an ordinary
eigenvalue problem by properly chosen transformations. With the definition

q:= (C- XZ)y (33)

the following equations can be established:

CY-q=b,

Cq - ;bbTy = hq.

In matrix terms this leads to

i
-$bbT ,’I[:I =Gl (34)

Thus we have transformed the original quadratic eigenvalue problem into an

equivalent linear one that can be solved with traditional methods.

6. NUMERICAL RESULTS

Finally we present some results of the numerical experiments. All calcula-

tions were carried out on a VAX 6600 with floating point accelerator (single
precision, 32bit reals) under VMS 4.6. The IMSLLibrary Edition 10.0,’
Version 1.0 served for the basic computations. The input data were produced
by a random number generator. As a reference solution we employed an
CONSTRAINED EIGENVALUE PROBLEM 837

TABLE 1
n = 10, Ilrc(x)ll = 0.104, Qmin) = - 0.282
Time
Algorithm h min Norm Error (set)
Reference solution - 4.220885 - 0.677439 [Link]
Explicit secular
equation - 4.220886 - 0.677439 1.OOOOOO2.0 X 1O-7 0.05
Implicit secular
equation - 4.220886 -0.677439 1.OOOOOO6.5~10~~ 0.10
Quadratic eigenvalue
problem - 4.220890 - 0.677438 l.OOOOOO5.4X lo-’ 0.23

implementation in double precision. Tables 1 to 3 summarize the results. The

columns have the following meaning:

A: Smallest zero of the secular equation

min: Minimum
Norm: Norm of the solution x
Error: Norm of the difference x - x reference
so,ution
Time: CPU time

Furthermore the caption contains the dimension n of the problem together

with the condition numbers (24), (25) of the solutions.

TABLE 2
n = 45, II~(r)jl = 930.8, x(min) = - 13131
Time
Algorithm x min Norm Error (set)
Reference solution - 7.054650 - 7.054494 [Link]
Explicit secular
equation - 7.054657 - 7.052025 0.999825 1.8x 10m4 1.16
Implicit secular
equation - 7.054650 - 7.060933 1.000456 4.6x 1O-4 2.60
Quadratic eigenvalue
problem - 7.055462 - 2.290894 0.569900 4.3 x10-l 10.4
838 W. GANDER, G. H. GOLUB, AND U. VON MAT-l-

TABLE 3
n = 100, II~(r)ll= 6.019, rc(min) = - 125.2
Time
Algorithm h min Norm Error (set)
Reference solution - 11.48939 - 11.07225 1.060666
Explicit secular
equation - 11.48939 - 11.07225 1900600 5.3 x lo-” 990
Implicit secular
equation - 11.48939 - 11.07230 1900002 2.2 x 10 mti 24.5
Quadratic eigenvalue
problem - 11.48976 - 11.02595 0.997983 2.2 x 10 -j 104.0

Based on the numerical calculations, the three solutions can be judged as

follows:

Explicit secular equation. The zero of the secular equation (20) is

determined to machine precision. The accuracy that can be expected from
the condition numbers (24), (25) is achieved.
Zmplicit secular equation. This method achieves the same accuracy as
the first one. However, the calculation of an eigenvalue decomposition (14) is
replaced by the determination of a generalized inverse, which is in no way
cheaper than the former operation.
Quadratic eigenvalue problem. It turns out that the smallest eigenvalue
of the general matrix (34) can be calculated only very inexactly. We suppose
that the transformation into a quadratic eigenvalue problem (32) impairs the
condition of the problem. With large condition numbers (24) (25) all decimal
places can be incorrect.

We wish to thank Professor A. M. Lesk, who stimulated the research

described in this paper through a personal communication.

REFERENCES

N. R. Draper, “Ridge analysis” of response surfaces, Techrwmetrics 5:469-479

WV.
G. E. Forsythe and G. H. Golub, On the stationary values of a seconddegree
polynomial on the unit sphere, SZAMZ. A&. Math. 13:10%1068 (1963).
W. Gander, Least squares with a quadratic constraint, Numer. Math. 36:291-307
(1981).
C. H. Golub, Some modified matrix eigenvahre problems, SZAMReo. 15:318-334
(1973).
CONSTRAINED EIGENVALUE PROBLEM 839

5 G. H. Golub, M. Heath, and G. Wahba, Generalized cross-validation as a method

for choosing a good ridge parameter, Technomehics 21:215-223 (1979).
6 6. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins U.P.,
Baltimore, 1983.
7 J. J. Mor&, The Lever&erg-Marquardt algorithm: Implementation and theory,
in Proceedings of the Biennial Conference Held at Dundee (A. Dold and
B. Eckmann, Eds.), Springer-Verlag, 1978, pp. 105-116.
8 J. J. Mor(! and D. C. Sorensen, Computing a trust region step, SlAM J. Sci.
Statist. Cutnput. 4553-572 (1983).
9 Chr. H. Reinsch, Smoothing by spline functions, II, Numer. Math. 16:451-454
(1971).
10 E. Spjetvoll, A note on a theorem of Forsythe and Golub, SIAM J. Appl. Math.
23:307-311 (1972).
11 E. Spjotvoll, Multiple comparison of regression functions, Ann. Math. Statist.
43: 1076- 1088 (1972).
12 U. von Matt, A Constrained Eigenvalue Problem, Diploma Thesis, Abteilung fiir
Informatik, ETH Ztich, 1988.

Received 30 September 1988; final manuscript accepted 6 October 1988