[PDF] [PDF] Chapter 4 - Solution of Nonlinear Equations - Department of

[PDF] Numerical Methods for Solving Systems of Nonlinear Equations

Lastly, we will study the Finite Difference method that is used to solve boundary value problems of nonlinear ordinary differential equations For each method, a 

Solving Systems of Nonlinear Equations

This appendix describes the most common method for solving a system of nonlinear equations, namely, the Newton-Raphson method This is an iterative method 

[PDF] Chapter 4 - Solution of Nonlinear Equations - Department of

Solving nonlinear equations is also called root-finding 1 Page 3 To “bisect” means to divide in half Once we 

[PDF] Solving Nonlinear Algebraic Equations - CORE

We first consider one algebraic equation in one variable, with our usual emphasis on how to program the algorithms Systems of nonlinear algebraic equations 

[PDF] Solving nonlinear systems of equations with only one - CORE

Any convenient technique for solving one nonlinear equation in one unknown could be used to solve this equation, with the advantage that only estimates of y are 

[PDF] Solution of nonlinear equations

Systems of linear equations can be solved using a fixed, finite number of operations (e g for Gaussian elimination) • Nonlinear equations, in general, • Do not 

[PDF] Solution of Nonlinear Equations

Solution of Nonlinear Equations equation of the form this lecture, we will introduce some elementary iterative methods for finding a root of equation (1),

Solving nonlinear systems of equations with only - ScienceDirect

Any convenient technique for solving one nonlinear equation in one unknown could be used to solve this equation, with the advantage that only estimates of y are 

[PDF] solving pdes in python pdf

[PDF] solving quadratic equations by factoring worksheet answers

[PDF] solving quadratic equations notes pdf

[PDF] solving quadratic equations with complex numbers worksheet answers

[PDF] solving quadratic equations with complex solutions answer key

[PDF] solving quadratic equations worksheet

[PDF] solving quadratics different methods worksheet

[PDF] solving simultaneous equations matrices calculator

[PDF] solving simultaneous equations using matrices 2x2

[PDF] solving simultaneous equations using matrices pdf

[PDF] solving simultaneous equations using matrices worksheet

[PDF] solving simultaneous linear and quadratic equations

[PDF] solving simultaneous linear and quadratic equations graphically

[PDF] solving system of nonlinear equations matlab

[PDF] solving systems of differential equations in matlab

Chapter 4 -Solution of

Nonlinear Equations

4.1 The Bisection Method

In this chapter, we will be interested in solving

equations of the form f(x) = 0: Becausef(x)is not assumed to be linear, it could have any number of solutions, from 0 to1.

In one dimension, iff(x)is continuous, we can

make use of the Intermediate Value Theorem (IVT) to b racket a ro ot;i.e., w ec annd numb ersaandb such thatf(a)andf(b)have dierent signs. Then the IVT tells us that there is at least one magical valuex2(a;b)such thatf(x) = 0.

The numberxis called aro oto rzero of f(x).

Solving nonlinear equations is also called

ro ot-nding 1

To \bisect" means to divide in half.

Once we have an interval(a;b)in which we knowx

lies, a systematic way to proceed is to samplef(a+b2

Iff(a+b2

) = 0, thenx=a+b2 , and we are done!

Otherwise, the sign off(a+b2

)will either agree with the sign off(a), or it will agree with the sign off(b).

Suppose the signs off(a+b2

)andf(a)agree.

Then we are no longer guaranteed thatx2(a;a+b2

but we are still guaranteed thatx2(a+b2 ;b).

So we have narrowed down the region wherexlies.

Moreover, we can repeat the process by setting

a+b2 to a(or tob, as applicable) until the interval containing x is small enough.

SeebisectionDemo.m

Interval bisection is aslow-but-surealgorithm for

nding a zero off(x), wheref(x)is a real-valued function of a single real variable. 2

We assume that we know an interval[a;b]on which a

continuous functionf(x)changes sign.

However, there is likely no

oating-point number (or even rational number!) wheref(x)is exactly 0.

So our goal is:

Find a (small) interval (perhaps as small as 2 successive oating-point numbers) on whichf(x)changes sign.

Sadly,

bisection is slow!

It can be shown that bisection only adds 1 bit of

precision per iteration. Starting from 0 bits of accuracy, it always takes 52 steps to narrow the interval in whichxlies down to 2 adjacent oating-point numbers.

However,

bisection is completely foolproof. Iff(x)is continuous and we have a starting interval on whichf(x)changes sign, then bisection is guaranteed to reduce that interval to two successive oating-point numbers that bracketx. 3

4.2 Newton's Method

Newton's method for solvingf(x) = 0works in the

following fashion.

Suppose you have a guessxnfor a rootx.

Find the tangent line toy=f(x)atx=xnand

follow it down until it crosses thex-axis; call the crossing pointxn+1.

This leads to the iteration

x n+1=xnf(xn)f

0(xn):

Oftenxn+1will be closer toxthanxnwas.

Repeat the process until we are close enough tox.

SeenewtonDemo.m

When Newton's method works, it is really great!

4 In fact,the generalization of the ab ovedescription of Newton's method is the only viable general-purpose method to solve systems of nonlinear equations But, as a general-purpose algorithm for nding zeros of functions, it has 3 serious drawbacks. 1.

The function f(x)must be smooth.

2.

The derivative f0(x)must be computed.

3.

The sta rtingguess must b e\suciently accurate".

Iff(x)is not smooth, thenf0(x)does not exist, and

Newton's method is not dened.

Estimating or approximating derivative values at points of non-smoothness can be hazardous.

Computingf0(x)may be problematic.

Nowadays, the computation off0(x)can (in principle) be done using automatic dierentiation 5

Suppose we have a functionf(x)and some computer

code (in any programming language) to evaluate it.

By combining modern computer science parsing

techniques with the rules of calculus (in particular the chain rule), it is theoretically possible to automatically generate the code for another function,fprime(x), that computesf0(x). You may be able to use software that estimatesf0(x) by means of nite dierences ; e.g., f

0(x)f(x+)f(x)2:

If we could takelim!0of the right-hand side, then

we would precisely havef0(x).(Why can't w e?) But it still may be expensive or inconvenient depending on your computing environment.

Ifx0is not suciently accurate, Newton's method

will diverge (often catastrophically!). 6 The local convergence properties of Newton's method are its strongest features.

Letxbe a zero off(x), and leten=xxnbe the

error in thenth iterate.

Assume

f0(x)andf00(x)exist and are continuous. x0is suciently close tox.

Then it is possible to prove that

e n+1=12 f 00()f

0(xn)e2n;

whereis some point betweenxnandx.

In other words,

the new erro ris roughly the size of the squareof the old error. (In this case we sayen+1=O(e2n).) 7

This is calledquadratic convergence :

For nice,

1smooth functions, oncexnis close enough

tox, the error goes down roughly by its square with each iteration. =)The number of correct digits approximately doubleswith each iteration! (This is much faster than bisection, which on lyhas linear convergence

The behaviour we saw for computing

pxis typical.

Beware!When the assumptions underlying the local

convergence theory are not satised, Newton's method might not work. Iff0(x)andf00(x)are not continuous and bounded, or ifx0is not \close enough" tox, then the local theory does not apply! !We might get slow convergence, or even no convergence at all.1 By \nice", here we meanf(x)such thatf00(x)is bounded and f0(x)6= 0. 8

4.3 Bad Behaviour of Newton's Method

As we have indicated, Newton's method does not

always work. Potentially bad behaviour of Newton's method includes convergence to an undesired root, periodic cycling, catastrophic failure. 9 It is easy to see geometrically how Newton's method can converge to a root that you were not expecting.

Letf(x) =x21.

This function has 2 roots:x=1andx= 1.

From the graph off(x)and the geometric

interpretation of Newton's method, we see that we will get convergence tox=1for anyx0<0and to x= 1for anyx0>0. (Newton's method is undened in this case forx0= 0.) 10 To see how Newton's method can cycle periodically, we have to cook up the right problem. Suppose we want to see Newton's method cycle about a pointa.

Then the iteration will satisfy

x n+1a=axn:

Therefore, we write

xf(x)f

0(x)a=ax;

and solve this equation for the evilf(x): dff =dx2(xa): 11

Integrating both sides,

lnjf(x)j=12 lnjxaj+C; whereCis an arbitrary constant, or jf(x)j=Apjxaj; whereA=eC. Noting f(x) =Apjxaj; we can chooseA= sgn(xa). 12 Here is a plot of thef(x)and the cyclic behaviour for a= 2andx0= 3or1.00.511.522.533.54 -1.5 -1 -0.5 0 0.5 1 1.5 xsign(x-2) sqrt(abs(x-2))

Of course,x=a.

What goes wrong?

The local convergence theory for Newton's method

fails for this problem becausef0(x)is unbounded as x!a. 13

Newton's method can fail completely.

When it does, it is usually in a catastrophic fashion; i.e., the iteratesxnbecome numerically unbounded in only a few iterations. (And if you are watching the iterates as they are computed, it becomes clear within an iteration or two that things aren't going to work.)

This bad behaviour is much more common when

solving systems of nonlinear equations, so we defer more discussion until the end of this chapter.

What this tells us however is that having a good

guess is even more important when solving a system of nonlinear equations. (Unfortunately, it is also much harder to obtain one!) For scalar equations, the problem of catastrophic failure generally stems from havingf0(xn)\point in the wrong direction". 14

In practice, to enhance theglobal convergence

properties of Newton's method, only part of the

Newton \step" is taken whenxnis \far" fromx:

The iteration is modied to

x n+1=xnnf(xn)f

0(xn):

A computation is performed to compute a scaling

factorn2(0;1]that tells us what fraction of the

Newton correction

to tak e.

Asxn!x,n!1;

i.e., as we approach the solution, we tend to take the whole Newton step (and get quadratic convergence).

This is called the

damp edNew tonmetho d The idea is that far from the root, you would not take the whole Newton step if it is bad (and hence avoid catastrophic failure). 15 Some other safeguards that are also added to software in practice to allow for graceful termination of the algorithm:

Specify a maximum number of iterations allowed.

Check that the Newton correctionf(xn)=f0(xn)is

not too large (or alternativelynis not too small). 16

4.4 The Secant Method

One of the greatest shortcomings of Newton's method is that it requires the derivativef0(x)of the function f(x)whose root we are trying to nd. The secant method replaces the derivative evaluation in

Newton's method with a

nite dierence app roximation based on the two most recent iterates. Geometrically, instead of drawing a tangent tof(x) at the current iteratexn, you draw a straight line (secant) through the two points(xn;f(xn))and (xn1;f(xn1)). The next iteratexn+1is again the intersection of this secant with thex-axis. The iteration requires two starting values,x0andx1. 17

The subsequent iterates are given by

s n=f(xn)f(xn1)x nxn1; x n+1=xnf(xn)s n:

It should be clear that the slope of the secantsn

approximatesf0(xn)in Newton's method.

SeesecantDemo.m

The convergence properties of the secant method are similar to those of Newton's method. Assumingf0(x) andf00(x)are continuous, it can be shown that e n+1=12 f

00()f0(n)f0(n1)f

0()3enen1;

wheren,n1are points betweenxn,xn1, andx; is a point in the interval inxcorresponding to the interval inyspanned byf(xn1); f(xn), and0. 18 This is not quadratic convergence, but it issup erlinear convergence.

It can be shown that

e n+1=O(en); where= (1 +p5)=21:6is thegolden ratio .

In other words, whenxngets close tox, the number

of correct digits is multiplied bywith each iteration.

That's almost as fast as Newton's method!

It is a great deal faster than bisection.

Typically, the secant method is very popular because although the convergence rate is not as fast as that of Newton's method (and so you need a few more iterations to reach a given accuracy), a secant iteration is usually much cheaper than a Newton iteration.

This means that ultimately the secant method is

actuallyfasterthan Newton's method to nd a root to a given accuracy. 19

4.5 Inverse Quadratic Interpolation

A typical train of thought in numerical analysis is the following.

We notice that the secant method uses 2 previous

pointsxn,xn1in determining the next one,xn+1. So we begin to wonder: is there anything to be gained by using 3 points?

Suppose we have 3 values,xn,xn1, andxn2, and

their corresponding function values,f(xn),f(xn1), andf(xn2). We could interpolate these values by a parabola and takexn+1to be the point where the parabola intersects thex-axis. Problem:The parabola might not intersect thex-axis! (This is because a quadratic function does not necessarily have real roots.) 20

Note:This could be regarded as an advantage!

In fact an algorithm known as

Muller's metho d

uses the complex roots of the quadratic to produce approximations to complex zeros off(x). Unfortunately, we have to avoid complex arithmetic. So instead of a quadratic inx,we interpolate the 3 points with a quadratic function iny!

This leads to asidewaysparabola,P(y), determined

by the interpolation conditions x n=P(f(xn)); xn1=P(f(xn1)); xn2=P(f(xn2)): Note:We are reversing the traditional roles of the dataxandyin this process!

A sideways parabola always hits thex-axis (y= 0).

So,xn+1=P(0)is the next iterate.

21

This method is known asinverse quadratic

interpolation (IQI). The biggest problem with this \pure" IQI algorithm is that polynomial interpolation assumes thexdata (also called the abscissae ), which in this case aref(xn), f(xn1), andf(xn2), to bedistinct. Doing things as we propose, we have no guarantee that they will be!

For example, suppose we want to compute

p2using f(x) =x22.

If our initial guesses arex0=2; x1= 0; x2= 2,

thenf(x0) =f(x2)andx3is undened! Even if we start near this singular situation, e.g., with x

0=2:001; x1= 0; x2= 1:999, thenx3500.

Cleve likens IQI to an immature race horse: It moves very quickly when it is near the nish line, but its overall behavior can be erratic. !It needs a good trainer to keep it under control. 22

4.6 The Zero-in Algorithm

The zero-in algo rithmis a hyb rid algo rithmthat combines the reliability of bisection with the speed of secant and IQI.

The algorithm was rst proposed by Dekker in the

1960s. It was later rened by Brent (1973).

The steps of the algorithm are as follows.

23

Start with pointsa,bso thatf(a),f(b)have

opposite signs,jf(b)j jf(a)j, andc=a.

Use a secant step to giveb+betweenaandb.

Repeat the following steps untiljbaj< machinejbj

orf(b) = 0. {Setaorbtob+in such a way that f(a)andf(b)have opposite signs; j f(b)j jf(a)j;

Setcto theoldbifb=b+; else setc=a.

{Ifc6=a, consider an IQI step. {Ifc=a, consider a secant step. {If the result of the IQI or secant step is in the interval[a;b], take it as the newb+. {If the step is not in the interval, use bisection to get the newb+. 24
This algorithm is foolproof: It maintains in a shrinking interval that brackets the root.

It uses rapidly convergent methods when they are

reliable; but it uses a slow-but-sure method when necessary to maintain a bracket for the root and guarantee convergence.

This is the algorithm implemented inMatlab'sfzero

function. See fzeroDemo .mquotesdbs_dbs17.pdfusesText_23