Numerical Methods for Solving Systems of Nonlinear …

1 Numerical Methods for Solving Systems ofNonlinear EquationsbyCourtney RemaniA project submitted to the Department ofMathematical Sciences in conformity with the requirementsfor Math 4301 (Honour s Seminar)Lakehead UniversityThunder Bay, Ontario, Canadacopyrightc (2012-2013) Courtney RemaniAbstractThis Honours Seminar Project will focus on the Numerical Methods involved in solv-ing Systems of Nonlinear equations. First, we will study Newton s method for solvingmultivariable Nonlinear equations, which involves using the Jacobian matrix. Second, wewill examine a Quasi-Newton which is called Broyden s method; this method has beendescribed as a generalization of the Secant Method. And third, to s solve for nonlin-ear boundary value problems for ordinary differential equations, we will study the FiniteDifference method.

2 We will also give an application of Newton s method and the FiniteDifference method. using the computer program matlab , we will solve a boundary valueproblem of a Nonlinear ordinary differential would like to acknowledge and thank everyone who has been involved with thisproject. I would like to express my sincere gratitude to my supervisor Dr. Liping her knowledge, direction, guidance, and all of her help, this project would nothave been achieveable. I would also like to show a great deal of appreciation to my projectcoordinator, Dr. Adam Van Tuyl. He has been a great professor to me over the years. Iwould also like to acknowledge how thankful I am for my Mom and Dad. Without theirunconditional love and support, and always believing in me throughout the years, I wouldnot have been able to achieve a lot of my goals here at Lakehead 1.

3 Introduction2 Chapter 2. Preliminaries3 Chapter 3. Newton s Method7 Chapter 4. Broyden s Method15 Chapter 5. Finite-Difference Method18 Chapter 6. matlab Application24 Chapter 7. Conclusion29 Appendix31 Bibliography35iiiCHAPTER 1 IntroductionOver the years, we have been taught on how to solve equations using various al-gebraic Methods . These Methods include the substitution method and the eliminationmethod. Other algebraic Methods that can be executed include the quadratic formulaand factorization. In Linear Algebra, we learned that Solving Systems of linear equationscan be implemented by using row reduction as an algorithm. However, when these meth-ods are not successful, we use the concept of Numerical Methods are used to approximate solutions of equations when exactsolutions can not be determined via algebraic Methods .

4 They construct successive ap-proximations that converge to the exact solution of an equation or system of Math 3351, we focused on Solving Nonlinear equations involving only a single vari-able. We used Methods such as Newton s method, the Secant method, and the Bisectionmethod. We also examined Numerical Methods such as the Runge-Kutta Methods , thatare used to solve initial-value problems for ordinary differential equations. However theseproblems only focused on Solving Nonlinear equations with only one variable, rather thannonlinear equations with several goal of this paper is to examine three different Numerical Methods that areused to solve Systems of Nonlinear equations in several variables. The first method wewill look at is Newton s method. This will be followed by Broyden s method, which issometimes called a Quasi-Newton method; it is derived from Newton s method.

5 Lastly, wewill study the Finite Difference method that is used to solve boundary value problems ofnonlinear ordinary differential equations. For each method, a breakdown of each numericalprocedure will be provided. In addition, there will be some discussion of the convergenceof the Numerical Methods , as well as the advantages and disadvantages of each a discussion of each of the three Methods , we will use the computer program Matlabto solve an example of a Nonlinear ordinary differential equation using both the FiniteDiffference method and Newton s 2 PreliminariesIn this section, we present the definitions and terms that will be used throughout theproject will be presented. A system of Nonlinear functionf:Rn Ris defined as beingnonlinearwhen it doesnot satisfy thesuperposition principlethat isf(x1+x2+..)6=f(x1) +f(x2) +.

6 Now that we know what the termnonlinearrefers to we can define asystem of non-linear of Nonlinear equationsis a set of equations as the following:f1(x1,x2,..,xn) = 0,f2(x1,x2,..,xn) = 0,..fn(x1,x2,..,xn) = 0,where (x1,x2,..,xn) Rnand eachfiis a Nonlinear real function,i= 1,2,.., is an example of a Nonlinear system from Burden and Faires in[3]:3x1 cos(x2x3) 12= 0x21 81(x2+ )2+ sinx3+ = 0( )e x1x2+ 20x3+10 33= 0In this article we will use the termrootorsolutionfrequently to describe the finalresult of Solving the a system of equationsf1,f2,..,fninnvariables is apoint (a1,..,an) Rnsuch thatf1(a1,..,an) = =fn(a1,..,an) = 2. Preliminaries3 Because Systems of Nonlinear equations can not be solved as nicely as linear Systems ,we use procedures callediterative methodis a procedure that is repeated over and overagain, to find the root of an equation or find the solution of a system of a real function fromD RntoRn.

7 IfF(p) =p, for somep D, thenpis said to be afixed pointofF. ConvergenceOne of the things we will discuss is the convergence of each of the say that a sequenceconvergesif it has a a sequence that converges top, wherepn6=p. If constants , >0 exist such thatlimn |pn+1 p||pn p| = .Then it is said thatpnconverges topof order with a constant .There are three different orders of sequencepnis said to belinearly convergentifpnconverges topwith order = 1, for a constant <1 such thatlimn |pn+1 p||pn p| = sequencepnis said to bequadratically convergentifpnconvergestopwith order = 2 such thatlimn |pn+1 p||pn p| = sequencepnis said to besuperlinearly convergentiflimn |pn+1 p||pn p|= 0 Chapter 2. value of measures how fast a sequence converges. Thus thehigher the value of is, the more rapid the convergence of the sequence is.

8 In the caseof Numerical Methods , the sequence of approximate solutions is converging to the root. Ifthe convergence of an iterative method is more rapid, then a solution may be reached inless interations in comparison to another method with a slower convergence Jacobian MatrixTheJacobian matrix, is a key component of Numerical Methods in the next matrixis a matrix of first order partial derivativesJ(x) = f1 x1(x) f1 x2(x) f1 xn(x) f2 x1(x) f2 x2(x) f2 xn(x).. fn x1(x) fn x2(x) fn xn(x) . we take the system from Example we are able to obtain thefollowing Jacobian Matrix:J(x) = 3x3sin(x2x3)x2sin(x2x3)2x1 162(x2+ )cosx3 x2e x1x2 x1e x1x220 Hessian MatrixTheHessian matrix, will be discussed in a future matrixis a matrix of second order partial derivativesH=[ 2f xi xj]ijsuch thatH(x) = 2f1 x21 2f1 x1 x2 2f1 x1 xn 2f2 x2 x1 2f2 x22 2f2 x2.

9 2fn xn x1 2fn xn x2 2fn x2n . Norms of VectorsLetx Rnwherex= .Chapter 2. normonRnis a function,|| ||, fromRnintoRthat hasthe following properties:(1)||x|| 0 for allx Rn,(2)||x||= 0 if and only ifx=0,(3)|| x||=| |||x||for all Randx Rn,(4)||x+y|| ||x||+||y||for allx,y RnThere are two types of vector norms we will discuss, thel2andl for the vectorxis called theEuclidean normbecauseit represents the length of the vector denoted by||x||=||x||2= x21+x22+ + norm represents the absolute value of the largest componentin the vectorx. It is denoted by||x|| = max1 i n|xi|.The following is an example demonstrating the vector vectorx= 2 113 has vector norms||x||2= ( 2)2+ ( 1)2+ (1)2+ (3)2= 15||x|| = max (| 2|,| 1|,|1|,|3|) = 3In the next couple of sections, we will examine three different Numerical methodsthat will apply the terms we discussed in this section.

10 These Methods include: Newton smethod, Broyden s method, and the Finite Difference 3 Newton s MethodNewton s method is one of the most popular Numerical Methods , and is even referredby Burden and Faires [3] as the most powerful method that is used to solve for the equationf(x) = 0. This method originates from the Taylor s series expansion of the functionf(x)about the pointx1:f(x) =f(x1) + (x x1)f (x1) +12!(x x1)2f (x1) + ( )wheref, and its first and second order derivatives,f andf are calculated atx1. If wetake the first two terms of the Taylor s series expansion we have:f(x) f(x1) + (x x1)f (x1).( )We then set ( ) to zero ( (x) = 0) to find the root of the equation which gives us:f(x1) + (x x1)f (x1) = 0.( )Rearranging the ( ) we obtain the next approximation to the root, giving us:x=x2=x1 f(x1)f (x1)( )Thus generalizing ( ) we obtain Newton s iterative method:xi=xi 1 f(xi 1)f (xi 1), i N( )wherexi x(asi ), andxis the approximation to a root of the functionf(x).