-
Use of Netwon’s Method to Determine Matrix Eigenvalues
The problem here is to develop a routine that will determine one or more eigenvalues of a matrix using Newton’s method and considering the eigenvalue problem to be that of a nonlinear equation solution problem.
The simplest way to illustrate the problem and its solution is to use a 4
4 matrix.
Let us consider a square matrix
. The definition of an eigenvalue requires that
For our test case writing out the solutions for the left and right hand sides yields
The problem here is that, with the intrusion of the eigenvalue, we
have one more unknown than we have equations for. We can remedy this
by insisting that the values ofbe normalized, or
Let us now construct a vector such that we have a closed system, all on the left hand side:
Since the object of Newton’s method is to arrive at this, we need an intermediate vector
, or
Let us make
the last “
” or
The Jacobian of this vector with respect to the expanded
vector is
Now we can solve the Newton’s method equation iteratively:
It is certainly possible to invert the Jacobian symbolically, but the algebra becomes very complicated, even for a relatively small matrix such as this one. A more sensible solution is to obtain numerical values for both Jacobian and
vector, invert the former using the Gauss-Jordan technique and then multiply this by the
vector before performing the Newton iteration.
Now let us consider the case of the tridiagonal matrix
The eigenvalues of this matrix are
or numerically 3.618033989, 1.381966011, 2.618033989, and .381966011. The FORTRAN 77 code used for this is given at the end of the problem. Although the matrix is “hard coded” into the program, it is only necessary to change one parameter to change the matrix size.
The summary results of Newton’s Method are shown below.
There are two different quantities tracked above:
- The residual, i.e., the Euclidean norm of the entire
vector.
- The error, i.e., the change in the eigenvalue from one step to the next.
Both these are tracked for three different starting places. For convenience,
all of thevector entries were initialized at the same value.
Some comments on the solution are as follows:
- As mentioned earlier, there were four eigenvalues to be determined. The method only returns one eigenvalue for each starting point, and that eigenvalue depends upon the starting point. The eigenvalues determined were 0.381966 (Start = 1 and Start = 2) and 2.6180339 (Start = 3.) Like the power method, this solution determines both an eigenvalue and eigenvector. Unlike the power method, it does not necessarily return the largest and/or smallest eigenvalue or even one easily predictable by the choice of starting value. With Newton’s Method, this is unsurprising; with multiple roots of an equation, which root is found very much depends upon the starting point. However, in the case where the number of roots is (in simple terms) the basic size of the matrix, this correspondence can become very complicated, and in some cases it is possible that certain eigenvalues will be missed altogether.
- As a corollary to the previous point, with some starting values the convergence almost comes apart, especially where Start = 3. With larger values than this, the program generates “nan” values and terminates abnormally. This result is a part of the method; poor initial estimates can led successive iterations “off the track” and thus fail to converge. Thus it is necessary to know the range of eigenvalues before one actually determines them, which to a great extent defeats the purpose of the method.
- The method is better at finding eigenvalues than finding eigenvectors. The residuals of the vector (which include the eigenvector plus the eigenvalue) converge much more slowly than the error. Those runs that were not limited by the termination criterion of the eigenvalue (
) showed a very slow convergence continue with the eigenvectors. For the eigenvectors, the convergence rate is reasonable.
The general impression of this method, therefore, is that under proper circumstances it is capable of producing eigenvalues and (to a lesser extent) eigenvectors, but that it is necessary to a) have some idea of the values of the eigenvectors going in and b) be prepared for the method to collapse with the wrong initial guesses. One possible application (given the convergence limitations discussed above) is to use it in conjunction with, say, the Householder-Givens Method to determine the eigenvectors, which do not come out as a result of this method. The known eigenvalues give excellent starting values.
These results are confirmed when we expand the matrix to 10
10.
We see that all of the errors and residuals go up and down from the initial guesses until convergence was achieved. The eigenvalues determined were 0.6902785 (Start = 1,) 1.7153704 (Start = 2,) and 1.7153703 (Start = 3.) Thus as before with three initial starting values only two eigenvalues were determined. The convergence was more lengthy than with the smaller matrix but not by much. This means that the method may be, to some extent, insensitive to matrix size, which would make it useful with larger matrices.
FORTRAN Code
The code calls several “standard” routines and includes whose significance is as follows:
- matsize.for is an include which includes a parameter statement for the actual matrix size. For the 10
10 matrix, it read as follows:
-
parameter (nn=10, nplus1=nn+1,mcycle=100)
-
- xmtinv is a subroutine to invert a matrix using Gauss-Jordan elimination.
- matvec performs matrix-vector multiplication (in that order).
- veclen computes the Euclidean norm of a vector.
c Determination of Eigenvalue(s) of Tridiagonal Matrix using c Newton's Method include 'matsize.for' dimension a(nn,nn),x(nplus1),f(nplus1),fj(nplus1,nplus1), &xt(nplus1),resid(mcycle),eigerr(mcycle) call tstamp c Define original matrix a do 1 i=1,nn,1 do 1 j=1,nn,1 a(i,j)=0.0 if (i.eq.j) a(i,j) = 2.0 if (abs(i-j).eq.1) a(i,j) = -1.0 1 continue open (unit=2,file='m5610p2d.csv') write(2,*)'Original Matrix' do 2 i=1,nn,1 2 write(2,3)(a(i,j),j=1,nn,1) 3 format(100(g10.3,1h,)) c Make initial guesses of eigenvalues and values of x do 100 mm=1,3,1 vstart=float(mm) write(2,*)'Eigenvalue Results for vstart =',vstart do 4 i=1,nplus1,1 4 x(i)=vstart c Cycle Newton's method do 5 m=1,mcycle,1 eigold=x(nplus1) c Compute Jacobian for current step do 6 i=1,nplus1,1 do 6 j=1,nplus1,1 if(i.eq.nplus1.and.j.eq.nplus1) then fj(nplus1,nplus1)=0.0 goto 6 endif if(i.eq.j) then fj(i,i)=a(i,i)-x(nplus1) goto 6 endif if(j.eq.nplus1) then fj(i,nplus1)=-x(i) goto 6 endif if(i.eq.nplus1) then fj(nplus1,j)=2.0*x(j) goto 6 endif fj(i,j)=a(i,j) 6 continue c Output Jacobian write(2,*)'Jacobian Matrix' do 10 i=1,nplus1,1 10 write(2,3)(fj(i,j),j=1,nplus1,1) c Compute Newton "F" vector do 20 i=1,nplus1,1 if(i-nplus1)21,22,22 21 f(i)=-x(nplus1)*x(i) do 23 j=1,nn,1 f(i)=f(i)+a(i,j)*x(j) 23 continue goto 20 22 f(i)=-1.0 do 24 j=1,nn,1 24 f(i)=f(i)+x(i)**2 20 continue c Invert Jacobian call xmtinv(fj,nplus1,nplus1) c Postmultiply Jacobian by f vector call matvec(fj,f,xt,nplus1,nplus1) c Update Value of x vector and output the result write(2,*)'Result Vector for m = ',m do 7 k=1,nplus1,1 x(k)=x(k)-xt(k) 7 write(2,*)x(k) c Compute norm of residual and error eigerr(m)=abs(x(nplus1)-eigold) call veclen(xt,resid(m),nplus1) if(resid(m).lt.1.0e-07.or.eigerr(m).lt.1.0e-07)goto 30 5 continue c Output residual plot 30 write(2,*)'Residuals and Errors' write(2,101)mm,mm 101 format(27hIteration,Residual (Start =,i2, &16h),Error (Start = ,i2,1h)) do 31 i=1,m-1,1 31 write(2,32)i,resid(i),eigerr(i) 32 format(i3,2(1h,,g10.3)) 100 continue close(unit=2) stop end
- The residual, i.e., the Euclidean norm of the entire
-
Rev. Ian Mitchell: The American Folk Song Mass
(FEL 7401-M) 1967
The 1960’s were a time of ferment and change in the U.S., and, then as now, institutions had a hard time keeping up with them, let along getting ahead.
One attempt to do so was The American Folk Song Mass, performed by the Canterbury Choir at Northwestern University under the direction of Rev. Ian Mitchell. Unlike many of its Catholic counterparts, it’s not trying to define a new style in liturgical celebration but to import in an Aaron Copelandish kind of way existing folk styles of the country. To this end the music he uses folk styles from various traditions, mixed with the 1928 Book of Common Prayer liturgy and his own monologues (another common feature of 1960’s Catholic and Episcopal folk music).
A fair comparison is The Winds of God. In some ways Mitchell was ahead of his California counterparts in breaking from the musical tradition of his own church. On the other hand, Gere boiled his explanatory monologue to one place in the work; Mitchell gets a little verbose, which breaks the flow of the album.
Mitchell’s monologues, however, highlight his social activism, which was a part of his ministry. He was in the Chicago tradition of activist priests and ministers, which included his contemporary Peter Scholtes (more adventurous in his own musical efforts) and of course Jeremiah Wright, whose influence on all of us has yet to be properly assessed. (Mitchell went on to produce a Catholic version of this album.)
His use of different forms of American folk music was of a piece with his social activism, something from the people. His use of Appalachian Scots-Irish style music may have been a miscalculation, given the fact that these people have been at the vanguard of the pushback against the kind of social activism that Mitchell espoused. Although, as was the case with The Winds of God and other contemporary efforts, events and styles were moving in a different direction, it’s a reasonable attempt at meeting a rapidly changing world at least halfway.

The songs:
- Introduction To The Mass
- Lord, Have Mercy Upon Us
- Introduction to The Nicene Creed
- I Believe In One God
- The Elements Of The Eucharist
- Lift Up Your Hearts – Holy, Holy, Holy
- The Lord’s Prayer
- The Priesthood of Christ
- O Lamb of God
- The Communion
- Glory Be To God On High
- The Close
- Jerusalem My Happy Home
- Alleluia Sing To Jesus
- A Home In That Rock
- Scarlet Ribbons
Music Pages
-
The Fading Glory Problem Affects the Prediction of Hurricane Sandy
A few months ago I ran a piece entitled Fading Glory, where I made the following observation re the place where I’m working on my PhD in Computational Engineering:
One of the things my advisor oriented us about were the substantial computer capabilities that the SimCentre has. “Substantial” is a relative term; at one point we were in the top 500 computers in the world for power, but he chronicled our falling ranking which eventually left us “off the charts”…What has happened to the SimCentre was not that the computer cluster there had deteriorated; it has just not kept up with the ever-larger supercomputers coming on-line out there.
That’s pretty much the cause of the success of the European model–and the failure of the American one–to predict Sandy’s landfall:
Forecast models require some serious computational horsepower, which can only be supplied by supercomputers. The ECMWF, for example, utilizes an IBM system capable of over 600 teraflops that ranks among the most powerful in the world, and it’s used specifically for medium-range models That, fundamentally, is the reason their model frequently outperforms the American one. The US National Weather Service’s modeling center runs a diversity of short-, medium-, and long-term models, all on a much smaller supercomputer. The National Weather Service has to do more with less.
I’ve lamented the way we’ve allowed our transportation infrastructure to deteriorate, but that also applies to other parts of our infrastructure, which includes simulation (as opposed to the statistical extrapolations which are so popular). At the root the United States, for all the blessings it has been endowed with, has a broad-based “fading glory” problem based on its dysfunctional political system, and that in turn is based on its dysfunctional society.
People in the business routinely talk about computational routines being “expensive” but in reality it’s nothing compared to the damage of an unexpected hurricane. Of course, we might have some more breathing room if we wouldn’t overdevelop our coastal areas, but that’s another post.
-
The Christmas Story, from the Cofraternity Version
Now it came to pass in those days, that a decree went forth from Caesar Augustus that a census of the whole world should be taken. This first census took place while Cyrinius was governor of Syria. And all were going, each to his own town, to register.
And Joseph also went from Galilee out of the town of Nazareth into Judea to the town of David, which is called Bethlehem–because he was of the house and family of David–to register, together with Mary his espoused wife, who was with child. And it came to pass while they were there, that the days for her to be delivered were fulfilled. And she brought her firstborn son, and wrapped him in swaddling clothes, and laid him in a manger, because there was no room for them in the inn.
And there were shepherds in the same district living in the fields and keeping watch over their flock by night. And behold, an angel of the Lord stood by them and the glory of God shone round about them, and they feared exceedingly. And the angel said to them, “Do not be afraid, for behold, I bring you good news of great joy which shall be to all the people; for today in the town of David a Savior has been born to you, who is Christ the Lord. And this shall be a sign to you: you will find an infant wrapped in swaddling clothes and lying in a manger”. And suddenly there was with the angel a multitude of the heavenly host praising God and saying, “Glory to God in the highest, and on earth peace among men of good will”.
And it came to pass, when the angels had departed from them into heaven, that the shepherds were saying to one another, “Let us go over to Bethlehem and see this thing which has come to pass, which the Lord has made known t us”. So they went with haste, and they found Mary and Joseph, and the babe lying in a manger. And when they had seen, they understood what had been told them concerning this child. And all who heard marvelled at the things told them by the shepherds. But Mary kept in mind all of these things, pondering them in her heart. And the shepherds returned, glorifying and praising God for all that they had heard and seen, even as it was spoken to them. (Luke 2:1-20)
The Cofraternity New Testament (Cofraternity coming from the Cofraternity of Christian Doctrine or CCD, well-known to Roman Catholics) was produced in 1941. It was a modernisation of the Douai-Rheims-Challoner New Testament translation which English-speaking Roman Catholics had used since before King James’ translation. It remained the “modern” Roman Catholic English translation of the New Testament (there was, of course, Knox’ version) until 1964, and was ultimately superseded by the New American Bible in 1970.
-
Peter Giardina: Song of Solomon
(Music Mountain MMP-PG-1001) 1975Every now and then an album comes along which, at least in part, takes your breath away, and this is one of them. It is skillfully done, laced with the mellotron, that 1960’s and 1970’s instrument that’s at once the product of technology and yet difficult to digitize, and profoundly spiritual. Although all the tracks aren’t on the highest plane, when they are, they are. His opening, the title track, gets off to a slow start, but then takes off. “Dance Song,” his rendition of the old liberal favorite, is the best I know of. And the closing, “One More Mile to Go”, is the absolute best “homecoming” song I know of. Southern Gospel cannot touch it; only this comes close.
Although the album says it was made in Indiana, Pete Giardina is a son of the Gulf Coast. His father was a New Orleans jazz musician and he was raised in the Dallas area. He is still an active musician in the Dallas area.
- Song Of Solomon
- Darkness Before The Dawn
- Never Alone
- Dance Song
- Christ Of Galilee
- Billows And Waves
- One More Mile To Go
As mentioned earlier, this album features a mellotron. If you’re interested in how these worked, you can watch the video below by someone who restored one.
See our Music Page




Watched by millions of viewers on network television over the course of three months, the sessions introduced Sen. Inouye to the public as an undaunted questioner of top White House aides, including H.R. Haldeman and John D. Ehrlichman (right).