Lecture 13 Nonlinear Systems - Newton’s Method

1 Lecture 13 Nonlinear Systems - Newton s MethodAn ExampleThe LORAN (LOng RAnge Navigation) system calculates the position of a boat at sea using signals fromfixed transmitters. From the time differences of the incoming signals, the boat obtains differences of distancesto the transmitters. This leads to two equations each representing hyperbolas defined by the differences ofdistance of two points (foci). An example of such equations1arex21862 y23002 1862= 1 and(y 500)22792 (x 300)25002 2792= 1.( ) solving two quadratic equations with two unknowns, would require solving a 4 degree polynomial could do this by hand, but for a navigational system to work well, it must do the calculations automat-ically and numerically. We note that the Global Positioning system (GPS) works on similar principles andmust do similar NotationIn general, we can usually find solutions to a system of equations when the number of unknowns matchesthe number of equations.

2 Thus, we wish to find solutions to Systems that have the formf1(x1,x2,x3,..,xn) = 0f2(x1,x2,x3,..,xn) = 0f3(x1,x2,x3,..,xn) = (x1,x2,x3,..,xn) = 0.( )For convenience we can think of (x1,x2,x3,..,xn) as a vectorxand (f1,f2,..,fn) as a vector-valuedfunctionf. With this notation, we can write the system of equations ( ) simply asf(x) =0, we wish to find a vector that makes the vector function equal to the zero Johnston, J. Mathews,Calculus, Addison-Wesley, 20015354 Lecture 13. Nonlinear Systems - NEWTON S METHODAs in Newton s Method for one variable, we need to start with an initial guessx0. In theory, the morevariables one has, the harder it is to find a good initial guess. In practice, this must be overcome by usingphysically reasonable assumptions about the possible values of a solution, take advantage of engineeringknowledge of the problem.

3 Oncex0is chosen, let x=x1 Approximation for Vector FunctionsIn the single variable case, Newton s Method was derived by considering the linear approximation of thefunctionfat the initial guessx0. From Calculus, the following is the linear approximation offatx0, forvectors and vector-valued functions:f(x) f(x0) +Df(x0)(x x0).HereDf(x0) is ann nmatrix whose entries are the various partial derivative of the components off,evaluated atx0. Specifically,Df(x0) = f1 x1(x0) f1 x2(x0) f1 x3(x0).. f1 xn(x0) f2 x1(x0) f2 x2(x0) f2 x3(x0).. f2 xn(x0).. fn x1(x0) fn x2(x0) fn x3(x0).. fn xn(x0) .( )Newton s MethodWe wish to findxthat makesfequal to the zero vectors, so let s choosex1so thatf(x0) +Df(x0)(x1 x0) = (x0) is a square matrix, we can solve this equation byx1=x0 (Df(x0)) 1f(x0),provided that the inverse exists. The formula is the vector equivalent of the Newton s Method formula welearned before.

4 However, in practice we never use the inverse of a matrix for computations, so we cannotuse this formula directly. Rather, we can do the following. First solve the equationDf(x0) x= f(x0).( )SinceDf(x0) is a known matrix and f(x0) is a known vector, this equation is just a system of linearequations, which can be solved efficiently and accurately. Once we have the solution vector x, we canobtain our improved estimatex1byx1=x0+ subsequent steps, we have the following process: SolveDf(xi) x= f(xi) for x. Letxi+1=xi+ xIntroduction to Numerical Methods.. by Young and Mohlenkamp 202155 4 3 2 101234 4 3 2 101234xyx3+y=1, y3 x= 1 Figure : Graphs of the equationsx3+y= 1 andy3 x= 1. There is one and only oneintersection; at (x,y) = (1,0).An ExperimentWe will solve the following set of equations:x3+y= 1y3 x= 1.( )You can easily check that (x,y) = (1,0) is a solution of this system .

5 By graphing both of the equations youcan also see that (1,0) is the only solution (Figure ).We can put these equations into vector-function form ( ) by lettingx1=x,x2=yandf1(x1,x2) =x31+x2 1f2(x1,x2) =x32 x1+ (x) =(x31+x2 1x32 x1+ 1).Now that we have the equation in vector-function form, write the following script program:format long;f = @(x)[ x(1)^3+x(2)-1 ; x(2)^3 -x(1)+1 ]x = [.5;.5]x = fsolve(f,x)56 Lecture 13. Nonlinear Systems - NEWTON S METHODSave this program run it. You will see that the internalMatlabsolving commandfsolveapproximates the solution, but only to about 7 decimal places. While that would be close enoughfor most applications, one would expect that we could do better on such a simple we will implement Newton s Method for this problem. Modify yourmyfsolveprogram to:% mymultnewtonformat long;n=8 % set some number of iterations , may need adjustingf = @(x)[x(1)^3+x(2)-1 ; x(2)^3 -x(1)+1] % the vector function% the matrix of partial derivativesDf = @(x)[3*x(1)^2, 1 ; -1, 3*x(2)^2]x = [.]

6 5;.5] % starting guessfor i = 1:nDx = -Df(x)\f(x); % solve for incrementx = x + Dx % add on to get new guessf(x) % see if f(x) is really zeroendSave and run this program (asmymultnewton) and you will see that it finds the root exactly (to machineprecision) in only 6 iterations. Why is this simple program able to do better thanMatlab s built-in program? (a) Put the LORAN equations ( ) into the function form ( ).(b) Construct the matrix of partial derivativesDfin ( ).(c) Adapt themymultnewtonprogram to find a solution for these equations. By trying differentstarting vectors, find at least three different solutions. (There are actually four solutions.)(d) Think of at least one way that the navigational system could determine the correct solution.