INTRODUCTION

The problem of finding the real or complex roots of a nonlinear equation is an old problem. 
This problem is frequently encountered in scientific work. 
A few typical instances are listed below: 
1 ) in the solution of linear differential equations we must often find the zeros of characteristic poly nomials. 
2 ) the stability of a mechanical or electrical sys tem is determined by examining the zeros of an asso ciated polynomial. 
3 ) when finite difference methods are used to solve nonlinear boundary value problems, we must solve simultaneous nonlinear equations. 
In this thesis we review several methods of solution of such equations and we also state and prove some theorems We will want to determine when an iteration method converges, and, if it does converge, how fast it converges. 
that
The convergence or non-convergence will in general depend upon the choice of the initial approximation(s) to the root. 
We will see that if the initial approximation(s) are "close enough" to f then convergence is usually assured. The problem of obtaining a "close enough" initial approximation to a root is a very difficult one about which very little is known. Usually the initial approximation is obtained from the investigators "intuition"which was derived from his "feel" of how the real system (from whence the original nonlinear equation was derived) should behave. Some methods will converge independently of the initial approximation. 
In practice we often begin our computation with a guess at the root and just hope that the iteration process will converge, 
For comparative purposes we will use the concept of order. 
Order is a measure of how fast the method in ques tion converges. 
To define the order of an iterative method we first define the error in the i^^ iterate to he ^1+1 T ■ ^i+1 (0*^) 
Under the assumption that the method will converge we have 
We now ask what is the order of this method assuming that it converges? By reasoning analogous to that used pre viously the error in the secant method is f) 
X f*( Ci.i) 2 [ f '( f )]^^i ^i-1 (1.4) "i+1
It can be shown that the order of the secant method is 
X . = X , - -- f(x.) f*(x.) = X - - -- [f'(x^)]^-f(x^)f"(x^)
The order again is two but note the necessity of the evaluation of the second derivative of f(x). 
In programming these methods it is necessary to "tell" the computer when to stop the iteration. The criterion 
adopted

n -X n n

We see, therefore, that the root-squaring process has broken up the original equation into n linear factors from which the approximate roots can be found with relative ease. We The complex roots are then .3933 ± 1.^5i. 
In the following example we illustrate the applica tion of the root squaring process to an equation with four complex roots. 
^ = Vi 9 r ^ ^^n -l _ a r 0 r ~ " n -2 -^-R = g -^n -1 _ _ a s a s " °n -3 a n d S = + "■'' n-1 = -| ^ + + r = - O n -1 - "■ °n -2 + V l + r -1 -^ = - o . - r o . B s - a s a s - ' " n -2 ^ '"n-3 W e c a n n o w s o l v e f o r A r a n d Ù& s , a n d i n f a c t , °n -2 + °n -3 = V l ( °n -l - V l > ' ^ "■ + °n -2 = " n H a v i n g s o l v e d f o

P R O B L E M 1 C H A P T E R 1 E V A L U A T I O N O F A R E A L R O O T O F T H E F U N C T I O N F I X ) = S I N F ( X ) -X / 2 . B Y T H E N E W T O N -R A P H S O N M E T H O D


INITIAL APPROXIMATION TO


.18954943E+01 THE REAL ROOT IS X = . 18954943E+01 FIX) = -.30000000E-07

Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. . 

P R O B L E M 1 C H A P T E R 1 EVALUATION OF A REAL R O O T O F T H E F U N C T I O N F ( X I = S I N F ( X » -X / 2 . BY THF SECANT M E T H O


APPROX. ROOT -18954946E+01 THE REAL ROOT IS X = 18954946E+01 P R O B L E M 2 C H A P T E R 1 E V A L U A T I O N O F A R E A L R O O T O F T H E F U N C T I O N F(X) = X * * 2 0 -l . B Y T H E N E W T O N -R A P H S O N M E T H O D


INITIAL APPROXIMATION TO


99999940E+64

Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 
•OOOOOOOOE-99 1 •19805873E+00 2 •95997580E-01 3 •11244911E+00 4 •11218236E+00 5 •11218228E+00 REAL IMAGINARY -•56091180E-01 •94183490E+00 -•56091180E-01 -.94183490E+00 •OOOOOOOOE-99 •10837988E+01 •90173020E+00 •88997786E+00 •89019927E+00 •89019935E+00 ITERATE ROOTS 3 4 ROOTS 5 6 •OOOOOOOOE-99 1 •65306290E+00 2 •35247705E+00 3 •24574896E+00 4 •24185552E+00 5 .25340898E+00 6 •25421987E+00 7 •25422081E+00 REAL IMAGINARY 10639999E+01 *00000000E- 13182197E+01 •OOOOOOOOE* •OOOOOOOOE-99 -•65103051E+01 -•34335817E+01 -•19838148E+01 -•14808962E+01 -•14044602E+01 -•14025857E+01 -•14025844E+01 99 99 REAL 18320110E+00 18320110E+00 IMAGINARY •13685389E+01 -•13685389E+01 E X A M P L E C H A P T E R 1 3 ( B J
•OOOOOOOOE-99 1 • 19805873E+00 2 •95997580E-01 3 •11244911E+00 4 •11218236E+00 5 •11218228E+00 6 •1I218228E+00 REAL IMAGINARY i56091140E-01 •94183495E+00 .56091140E-01 -•94183495E+00 •OOOOOOOOE-99 •10837988E+01 •90173020E+00 •88997786E+00 •89019927E+00 •89019935E+00 •89019935E+00 i t e r a t e R •OOOOOOOOE-99 •OOOOOOOOE-99 1 •65306408E+00 -•65103057E+01 2 •35247765E+00 -.34335823E+01 3 •24574921E+00 -•19838I51E+01 4 •24185558E+00 -•14808962E+01 5 •25340902E+00 -•14044601E+01 6 •25421991E+00 -•14025857E+01 7 •25422085E+00 -• 14025844E+01 8 •25422085E+00 -• 14025844E+01 ROOTS REAL 3 •10639989E+01 4 -•13182197E+01 ROOTS REAL 5 •18320156E+00 6 •18320156E+00 IMAGINARY •OOOOOOOOE-99 •OOOOOOOOE-99 IMAGINARY •13685386E+01 -•136853B6E+01 E X A M P L E 1 3 ( C ) C H A P T E



  one or more of the points x^, ,,,, 




  Fig. 1 Illustrates the Fourier conditions. 


(

  Figure3 


Q

  Figure 5 




  figures.The approximate roots listed then are actually 




  program may not be used to find real roots of equal magnitude, since we must consider quadratic factors. The program does however give the coefficients of the qua dratic factors and in the following examples we worked with these factors in determining the roots. The computer pro gram could readily be modified to determine real stopped after six root-squarings since another root-squaring would have made the coeffi cients too large for the computer to handle. The final equation should be broken into one quadratic factor and two linear factors. The quadratic factor is easily de tected by noticing that the second coefficient of this final transformed equation, .5877 x 10^^, is just half 14 the square of the corresponding coefficient, .1085 x 10 , of the proceeding equation. Hence the quadratic factor is y^ + .5877 X lO^^y + .8636 X 10^^ = 0 and since the roots are known to be equal and since their product is equal to the constant term of the quadratic, we have (x^)^^ = x^^® = .8636 X 10^Û sing logarithms we get x = |2.5| and by testing the values 2.5 and -2.5, we see that x^ g -2.5. The approxi mate root +1, with a functional value of zero, is given us by one linear fragment, while the other linear fragment gives us + .5857, neither of which has a negligible func tional value. This presents no problem however. We Just use the relationship between the coefficients and the roots of the original equation, i.e.we are examining a polynomial equa tion with three roots of equal magnitude. No quadratic factors are possible in this case but Graeffe's method is still of great value. Eight root-squaring were performed. As approximate roots we obtain x^ = 1.9999999 , x^ = -1 , x^ = -.99571775, with f(x^) = -.75 X 10"^ , f(xg) = 0, f(x^) = .1 X 10"^. Now the three approximate roots could be removed from the original equation using synthetic division and the remain ing two real roots could be approximated by solving the re sulting quadratic equation. Hence, we can safely say that the Graeffe method gives much valuable information about the roots of polynomial equations regardless of the distribution of these roots, Carvallo [Resolution Numérique des Equations, page 24] has extended Graeffe's method to the solution of trans cendental equations by expanding the equation into a Taylor series, neglecting the remainder term, and then treating the resulting polynomial as an algebraic equation. A more general method of finding the complex roots of a polynomial equation is the Lin-Bairstow method. The 2 procedure is to find a quadratic factor x + ax + 3 of the polynomial by an iterative process. If we divide P^(x) by 2 an initial guess at our factor, say x + rx + s, we obtain, as a quotient, a polynomial Q^_g(x) of degree nand ù > . s are small. Let us use Taylor's expan sion for functions of two variables and neglect second and higher powers of A. r and A s , to obtain R 




  Figure 1. 


Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.

  
				R	2
	BAIRSTOW'S m e t h o d FOR FINDING QUADRATIC FACTORS OF POLYNOMIALS
		P(X) = A(l)*X**N+A(2)*X**N-l+...+A(N)*X+A(N+l)
		THE DEGREE N OF THE POLYNOMIAL P(X) IS	6
		THE COEFFICIENTS A(l) TO A(N+1) ARE AS FOLLOWS
				.32600000E+01
				.OOOOOOOOE-99
				.42000000E+01
				•30800000E+01
				-.71600000E+01
				.19200000E+01
				-.77600000E+01
		EPSILON IS		. lOOOOOOOE-04
		ITERATE		R	S
			.OOOOOOOOE-99	.OOOOOOOOE-99
		1	.19805873E-00	.10837988E+01
		2	.95997548E-01	.90173012E-00
		3	.11244910E-00	.88997783E-00
		4	.11218234E-00	.89019925E-00
		5	.11218227E-00	.89019933E-00
	ROOTS	REAL		IMAGINARY
	1	-.56091172E -01	.94183493E-00
	2	-.56091172E -01	-.94183493E-00
		ITERATE		R	S
			.OOOOOOOOE-99	.OOOOOOOOE-99
		1	.65306317E-00	-.65103047E+01
		2	.35247717E-00	-.34335812E+01
		3	.24574899E-00	-.19838145E+01
		4	.24185551E-00	-.14808960E+01
		5	.25340897E-00	-.14044600E+01
		6	.2S421986E-00	-.14025856E+01
		7	.25422081E-00	-.14025843E+01
	ROOTS	REAL		IMAGINARY
	3	.10639998F+01	.OOOOOOOOE-99
	4	-.13182I97E+0]	.OOOOOOOOE-99
	ROOTS	REAL		IMAGINARY
	5	,183201lOE-00	.13685389E+01
	6	.183201lOE-OO	-. 136853R9E+01

99 99 Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.

  
						EXAMPLE 15
						CHAPTER	2
			ITERATE			R	S
	) ARE AS FOLLOWS .OOOOOOOOE-99 .lOOOOOOOE+01 •12926297E+01 •16664238E+01 •10900000E+03 .60000000E+01 .12926297E+01 •16664238E+01 .15000000E+03 -.50000000E+01 .12925243E+01 •16660050E+01 •7Î900000E+03 .40000000E+01 •13034803E+01 •15911775E+01 .68700000E+03 -.30000000E+01 .16291744E+01 •12888837E+01 •49000000E+03 .OOOOOOOOE-99 .28305900E+01 •11666539E+01 .15130000E+03 -.20000000E+01 .OOOOOOOOE-99 .OOOOOOOOE-99 •OOOOOOOOE-99 .43915078E+02 .21959686E+02 .1098753SE+02 .55172830E+01 •OOOOOOOOE-99 .10133398E+01 .14704039E+01 BAIRSTOW'S METHOD FOR FINDING QUADRATIC FACTORS OF POLYNOMIALS 10 9 8 7 6 5 ITERATE 1 2 3 4 1 2 .13146751E+01 .21107625E+01 PIX) a A(l)*X**N+A(2)*X**N-l+...+A(N)*X+A(N+l) 3 .13354893E+01 .21917771E+01 •10449172E+02 THE DEGREE N OF THE POLYNOMIAL P(X> IS 8 4 .13355030E+01 .21924679E+01 •52530510E+01 THE COEFFICIENTS A U » TO A(N+1) ARE AS FOLLOWS 5 .13355030E+01 .21924679E+01 •27110865E+01 .20400000E+02 •154B4181E+01 •lOOOOOOOE+01 ROOTS
	5 ROOTS	EPSILON IS •64631485E+00 . lOOOOOOOE-04 .111745288+0 REAL IMAGINARY ,68700000E+01
	6	ITERATE •64631485E+00 EPSILON IS ,00001 R	-•11174528E+0	S
	.OOOOOOOOE-99 .15378910E+01 •OOOOOOOOE-99 .OOOOOOOOE-99 REAL IMAGINARY ITERATE ROOTS 7 R S
	ROOTS 1		1 2 3 1 4 2 3 3 6 4 7 5 6 •30460664E +00 -.12500000E+00 -.33026133E+00 .OOOOOOOOF-99 -.69440005E+00 .50713200E+00 -.60706881E+00 -.S0994650E-01 -.609218795+00 ,29452665F+00 -.6092132BF+00 -.16727224E+00 -.60921328E+00 .35399700F-01 REAL .20501505E-01 IMAGINARY 7 -.56442910E-02 .99191475E+00 8 -.56575771E-02	.15000000E+01 , OOOOOOOOE-99 .88502620E+00 , 450OOOOOE-O1 .10784368E+01 12056259E-01 .10696903E+01 , 58640522E-01 .10767151E+01 , 78684068E-01 .10766801E+01 , 10122710E+00 .10766801E+01 , 17233900E+00 , 17012366E+00 17079725E+00
	2		•30460664E+00 9 -.56604909E-02 99191475E+00	,	17079728E+00
	ROOTS 1	ITERATE REAL 28287885E-02	R	IMAGINARY ,41326656E+00	S
	2		.OOOnOOOOF-99 .28287885E-02 -.41326656E+00	.OOOOOOOOE-99
		1 2 ITERATE	,34867614F+01 .26015274E+01	-.24185137E+01 -.19842264E+01
	ROOTS 3 4 3 ROOTS		3 4 5 1 6 2 7 3 8 4 9 5 6 .Î1080156E+01 .19315073E+01 .14045295E+01 .OOOOOOOOE-99 .10336157E+01 .91876182E+00 .88039870E+00 .42300950E+01 .85524766Ë+00 .76635625E+01 .85447464E+00 .78875067E+01 .85447380E+00 .78540419E+01 REAL .78531312F+01 IMAGINARY -. I9624902F+0I -.673787S0E-0I .OOOOOOOOE-.OOOOOOOOF-99 -.17834572E+01 .OOOOOOOOE-99 -.18387089E+01 .60581391E-01 -.20264880E+01 .28963854E+00 -.21434174E+01 .50986716E+00 -.21732008E+01 .52713429E+00 -.21744699E+01 .52466013E+00 -.21744715E+01 .52459383E+00 REAL IMAGINARY .OOOOOOOOE-99 7 •78S31280E+01 .52459362E+00
	4		-.77857520E+01		.OOOOOOOOE-

Reproduced with permission of the copyright owner. Further reproduction prohibited without permission. 

2 X + a ^ = OReproduced with permission of the copyright owner. Further reproduction prohibited without permission. 

T H E P O S S I B L E R E A L R O O T S O F P(X) 

ACKNOWLEDGEMENTS I wish to e]cpress m y appreciation to Professor

Robert P. Banaugh for his guidance and instruction through