Hubert Schwetlick
Department of Mathematics
Dresden University of Technology

History of Newton Techniques for Eigenvalue Computations:
The Contribution of Heinz Unger (1914 -- 2007)

It seems that Heinz Unger was the first (after Jacobi, who much earlier did something like a linearization of the eigenvalue equation) who used Newton techniques for solving eigenvalue problems. In his groundbreaking short paper

Heinz Unger: Nichtlineare Behandlung von Eigenwertaufgaben (Nonlinear Treatment of Eigenvalue Problems)
Z. Angew. Math. Mech. 30 (1950), pp. 281--282

he considered the eigenvalue equation

M( λ ) x = ( Ax - λ I ) x = 0     (EE)

with a real (n x n)-matrix A and added to it the normalization condition

wTx = 1        (NC)

where w = em is an appropriately chosen coordinate vector, i.e., he required the m-th component of x being equal to 1:   xm = 1. Without restriction of generality Unger sets m = 1, i.e., x1 = 1, so that (EE) reduces to the nonlinear (n x n)-system

g( λ,y) = g( λ,x2, ... ,xn) = M( λ )( 1 ,x2, ... ,xn)T = m1( λ ) 1 + m2( λ ) x2 + ... + mn( λ ) xn = 0      (REE)

for the unknowns v = ( λ,y ) = ( λ,x2, ... ,xn)T where mj( λ ) = M( λ ) ej denotes the j-th collumn of M( λ ). Then he applied Newton's method

( λ(k),y(k) )  --->  ( λ(k+1) = λ(k)+ μ(k), y(k+1)= y(k)+ t(k) )

to the reduced system (REE) which leads to the correction equations

g( λ(k),y(k) ) + g'( λ(k),y(k) ) (μ(k),t(k)T )T = 0

for the corrections ( μ(k),t(k) ) where g ' ( λ(k),y(k) ) = ( - x(k), m2( λ(k) ), ... ,mn( λ(k) ) ) is the Jacobian of g at the current iterate.

This is equivalent to applying Newton's method to the extended (n+1)x(n+1)-system

(A - λ I) x = 0
  wTx - 1 = 0

with respect to (λ,x) when using w = e1 and starting with an initial appoximation ( λ(0),x(0) ) with wTx(0) = x1(0) = 1.

It turns out that the Newton step yields the new eigenvector approximation

x(k+1) = (A - λ(k) I) -1 x(k) μ(k)

where μ(k) plays the role of a scaling factor, i.e., the direction of the Newton successor to x(k) is the same as the direction obtained by performing one step of inverse iteration with shift λ(k) to x(k) , cf. formula (31) on page 165 of the German textbook

Rudolf Zurmühl: Praktische Mathematik für Ingenieure und Physiker
Springer, Berlin 1953

which only three years later presented Unger's idea. By the way, I learned some parts of numerical linear algebra from this widely used book when I studied Mathematics at TH Dresden in the early sixties of the last century.

Unger pointed out in his 1950 paper that his approach can also be used for general linear eigenproblems

M( λ ) x = ( Ax - λ B ) x = 0

and for general nonlinear eigenproblems

M( λ ) x = 0

with a nonlinear matrix valued mapping M( λ ), e.g., for quadratic eigenproblems

M( λ ) x = ( A λ2 + B λ + C ) x = 0.

Unger's approach is also described by Lothar Collatz in subsection 19.4: Das Newtonsche Verfahren bei Eigenwertaufgaben (Newton's Method for Eigenvalue Problems) of his monograph

Lothar Collatz: Funktionalanalysis und numerische Mathematik
Springer, Berlin 1964

There instead of Ax = λ x the general linear eigenvalue problem Ax = λ Bx is considered. Moreover, since the eigenvalue equation is bilinear in x and λ, hence the second F-derivative is constant, applying the third order Euler-Tschebyscheff method which uses second derivatives is proposed there.

Unfortunately, the English speaking numerical linear algebra community did not recognize Unger's basic paper. For instance, also Peters and Wilkinson did not mention it in their famous survey

Peters, G. and Wilkinson, J. H.: Inverse Iteration, Ill-Conditioned Equations and Newton's Method
SIAM Rev. 21 (1979), pp. 339 -- 360

For colleagues who are interested in this early source I include here

A short CV of Heinz Unger

[Homepage Schwetlick]