[PDF] ECE 3040 Lecture 12: Numerical Solution of Nonlinear Equations II

View - Download ECE 3040 Lecture 12: Numerical Solution of Nonlinear Equations II

Previous PDF

Next PDF

ECE 3040

Lecture 12: Numerical Solution of Nonlinear Equations II

© Prof. Mohamad Hassoun

This lecture covers the following topics:

ethod method

Secant method

nonlinear equations

Bisection method

Matlab built-in numerical solvers: fzero and fsolve

Matlab built-in symbolic solver: solve

Comparison of the different root finding methods

Appendix I: Proof

d for Computing the Square-root -Raphson method) uses information about the interpretation for this method. First, we start from an initial estimate ݔ଴ of the root. The point at which this line intersects the ݔ-axis is considered as the next search on until a convergence criterion is met. The first two iterations of this method are depicted in the following figure. The following is a mathematical description of The equation of a The point of intersection of this straight line with the ݔ-axis is obtained by setting

ݕൌ-ǡ and leads to

equation leads to the following equation for the ݔ-intercept (ݔ௞ାଵ) at the ݇th

iteration of the search method

The above formula

Solving for ݔଵ we obtain

Because of the approximation, ݔଵ is not necessarily the desired root ݔכ

be closer to it than ݔ௢ is. So, we may substitute ݔଵ in the right had side of the above

It is interesting t-point

The above formulation implies that we may use the fixed_point function (from problem since the derivative is relatively easy to obtain. Numerical approximation of the derivative may also be employed in the algorithm (this leads to the secant method discussed in the next section). It is obvious from the above formulation that leads to numerical overflow.

It can be shown (refer to Appendix I) that is

quadratic near a root ݔכ That is, the error at step ݇൅ͳ is proportional to the square of the previous error at small in the vicinity of the root. is slower than quadratic. At a double root, the convergence is linear. The following figure depicts three cases where : (a) Diverges, (b) oscillates, and (c) converges to a root far away from the initial guess. Most of the time, these complications can be avoided by simply starting closer to the root. (Figure courtesy Applied Numerical Methods with Matlab,

Steven C. Chapra, 2nd edition (McGraw Hill, 2008)

యെ-ൌ-. Compare the results ଷቇ. The numerical solution may be obtained employing the fixed_point function developed in Lecture 11, compared to 18 iterations for the fixed-point iteration method using the formulation s method. The following is function fixed_point Care must be taken when the function has a root at zero. Here, the relative error convergence criteria is problematic (could lead to division by zero). For example, must be used. method as follows. Starting with and taking advantage of the convergence criterion for the fixed-point method, namely given by The absolute value of the derivative of ݃ே is given by: the neighborhood of all roots. Therefore, the three roots when a proper initial guess ݔ଴, close to one of the roots, is used.

A particularly interesting application of

algorithm for computing the square root of a number. One of the programming examples (recall Matlab function sqrt_newt) in Lecture 6 dealt with an algorithm iterative formula: ݔ௞ାଵൌଵ method as follows. (Refer to Appendix II for additional insights.) fixed-point ௫ቁ. Therefore, the iterative formula for ܽ or ห௫మି௔ห This result suggests that convergence is guaranteed if the initial search point satisfies the condition ݔ଴א always converge to ξܽ convergence for ܽ this iterative formula for the square root converges from any positive initial search

Secant Method

The secant method is similar to , but it employs a simple forward Upon substituting the above approximation for the derivative formulation we obtain the recursion formula for the secant method, namely

The secant method requires two initial guesses (ݔ௔ൌݔ଴ and ݔ௕ൌݔିଵ) near the

root. secant is a function that implements the secant method. The input to this The iterative secant formula for this function is given by [again, ݔ௞ؠ

The first two iterations result in,

The following is the solution employing the secant function: Note that the initial search points ݔ௔ and ݔ௕ need not enclose the root. However, generally speaking, convergence would be faster if they do. Also, the computation the previous iteration. Your turn: The following nonlinear equation has the obvious solution ݔכൌߨ the other solutions (accurate to 10 decimal places) to find the root. Repeat employing the secant method.

Nonlinear Equations

method used for solving a single equation introduced earlier. The fixed_point2 function introduced in Lecture 11 can be employed to implement the numerical solution, but after proper adaptation method for a system of two equations and two unknowns. Given

The ܬ

Note: The term డ௙భ

treated as a constant), and డ௙మ Your turn: Show that the above formulation in (1) and (2) can be expressed as Example. Solve the following system of nonlinear equa method.

First, the equations are rewritten as,

Next, graph the two equations to arrive at a reasonable initial guess, From the graph, a good initial guess is ݔ଴ൌͳ and ݕ଴ൌͳ. The Newton formulation is obtained by generating the recursion pair:

First, compute all partial derivatives:

The Jacobian is

leading to formulations,

The formulation is as follows,

Now, solve using fixed_point2 to arrive at a 14 significant digit approximation:

Alternatively, we could solve the first equation for ݕ to get ݕൌ-ݔെ݁ି௫ and then

a fixed-point iteration problem with (Converged in 94 iterations) Solution of the single equation employing the secant method with initial search points - and ͳ: (Converged in 8 iterations) The secant method converged in ͺ iterations for this problem. It is faster than New the formulation of the secant method. It turns out that (in many situations) the approximate derivative leads to larger steps in the search point towards the solution as can be seen in the following plot (generated for the above solutions). The Newton method oscillates as it converges to the solution, but the secant method does not.

Your turn:

Bisection Method

The bisection method is a method that capitalizes on the fact that for a continuous opposite sign of the function to the right of the root. So, the idea is to start with an divide the interval into two equal halves. Then, determine the interval that contains the root and continue with this interval, repeating the previous step. Let us call the half-point of the original interval ݔ௥ൌ௫೗ା௫ೠ The bisection algorithm is depicted graphically in the following figure: (Figure courtesy Applied Numerical Methods with Matlab,

Steven C. Chapra, 2nd edition (McGraw Hill, 2008)

యെ-ൌ-. Assume the initial search interval [0 6]. The following are the first three iterations: divide the interval into two half intervals, [0 3] and [3 6]. Evaluating the product of the function at the lower limit and upper limit for each interval reveals: the interval [3 6]. Dividing the new [3 6] interval into two equal intervals, [3 4.5] for intervals [3 3.75] and [3.75 4.5] leads to the root inside [3 3.75], and so on.

Convergence Rate of the Bisection Method

Since the search interval is halved after every iteration, and since the root is located inside one of the intervals, we are then guaranteed that the absolute error between any point inside the interval and the root ݔכ Similarly, the absolute error after the second iteration is less than the third iteration it is less than ௕ି௔ know the desired absolute error and the starting interval, then we may solve for the sufficient number of iterations required by the bisection method. Example. Estimate the number of iterations required by the bisection method to guarantee that you find the root of a function to within an absolute error of

We have ௕ି௔

Matlab Built-in Numerical Solvers: fzero and fsolve -in fzero can be used to solve (numerically) a single nonlinear reliable bisection method and the efficient secant method. Here is a brief description help: the function call fzero(f,x0), where x0 is an initial guess. Here is an example: Alternatively, we may define the function inside the fzero call: Matlab has a yet more advanced numerical solver, fsolve, that can solve a single nonlinear equation or a system of nonlinear algebraic equations: fsolve is a very sophisticated function. One nice feature is that it allows the learn more about it: https://www.mathworks.com/help/optim/ug/fsolve.html fsolve is designed to primarily solve a system of nonlinear equations. Here is an example of solving two equations and two unknowns (which we had solved earlier in the form ܨ Next, define the system of equation as a user defined Matlab function as follows, Function fsolve is called as follows (the initial guess x0 is a vector): fsolve(@system_f,[0;3]) or fsolve(@system_f,[0,3]) or fsolve(@system_f,[0 3]) [x,f]=fsolve(@system_f,[0;3]) An alternative (more compact) set of instructions for solving the above problem is: Your turn: Employ fsolve to solve the following system of equations Your turn: A projectile of mass ݉ fired (from ground level), at an angle ߠ initial velocity ݒ௢, follows the trajectory

Let ܥ

resistance, the projectile equations of motion reduce to (note independence from ݉) value of ߠ the same location had there been no air resistance and with a launch angle, ߠ ͹ͷ୭. Plot the two projectile trajectories to verify your answer. For how long does the projectile stay in the air for each model? with air resistance and with ߠ projectile solution trajectories.

Matlab Built-in Symbolic Solver: solve

Matlab also provides the user a powerful symbolic-based equation solver named solve. It can handle single and multiple nonlinear algebraic equations. It attempts to generate an (exact) analytical solution if possible. If no analytical solution is found and the number of equations equals the number of dependent variables, a numeric solution is attempted. The variables must be declared as symbolic variables using the syms command. Initial conditions are not required. An equation like Function solve can generate the real and the complex solutions.

Examples:

The following is the solve function solution of the system of two nonlinear equations that we solved earlier (note the level of accuracy in the solutions): The answers provided by function solve defaults to 32 decimal digit accuracy. Obviously, this is not a floating-point representation (which would have been restricted to 15 or 16 digits as we discussed in Lecture 10). The symbolic toolbox of Matlab attempts to represent numbers in exact symbolic form. For example it retains the representation of the ݊th root exactly, as we saw above when solving for the roots of ݔଷെͳൌ-. But, when it has to use a decimal representation, then it uses a variable-precision arithmetic (vpa) format. The vpa digit accuracy is set using the digits by itself returns the current set value of digits. The instruction vpa(A) uses vpa arithmetic to compute each of the elements of A to at least d decimal digits of accuracy, where d is the current setting of digits. On the other hand, vpa(A,d) computes the values to at least d significant (non-zero) digits, instead of the current setting of digits. The quantity A can be specified as a symbolic object, string, or numeric expression. The double(A) instruction converts from vpa representation to double-precision representation. Here are few examples,

We may convert vpa double:

Your Turn: Solve the following system of nonlinear equations (this system was encountered in connection with solving for the complex roots of the equation ݁௭െ solve. Compare the solutions obtained to those obtained in Lecture 11 using solve_poly. built in symbolic function jacobian(f,v) to the end of the next section.

Comparison of the Different Root Finding Methods

Fixed-point method

Advantage. Forms the theoretical recursive and secant methods. Advantage. Very fast convergence when near solution. Disadvantage. It often requires a good initial guess. It also requires the analytic per iteration.

Secant method

Advantage. Fast convergence; requires only one function evaluation per iteration. Disadvantage. It often requires a good initial guess.

Bisection method

Advantage. Guaranteed convergence.

Disadvantage. Slow convergence. In general, you can't expect to hit the solution exactly. What happens if the initial search interval includes an even number of roots? Odd number of roots?

Taylor series-based solve_poly

Advantage. Very useful when solving for multiple roots, including complex ones. Disadvantage. Very slow because of the overhead needed to compute the Taylor roots. It requires the initial guess to be very close to the root. Potentially sensitive to machine round-off error. Notes: Convergence is guaranteed for functions that do not fluctuate sharply in the vicinity of the root being sought.

Summary

For general use, the bisection method is far too slow. The Newton and secant methods are fast enough in general, but care must be taken to prevent divergence. advantage. The secant method is regarded as the best general purpose method. These methods are designed to find real roots. solve_poly is convenient as a quick way to obtain multiple moderate accuracy roots (real and complex). A hybrid method would be preferred: Bisection method used to narrow down the search interval around the root, followed by the secant method. This is what Matlab uses for its built-in function fzero. roots will generate all roots (including complex roots) without the need for initial guesses. It should be noted here that, since the Taylor series expansion (at any point ܽ polynomial is the polynomial itself, solve_poly is equivalent to the roots function

Did you know?

It can be shown that the roots of a polynomial are the eigenvalues of an easily formed special matrix called the . The companion Matlab can generate this matrix from the polynomial coefficient vector p using matrix is formed as, The following is an example of using the function compan. Matlab has a very powerful eigenvalue function, eig, which is based on linear algebraic principles. The function eig computes the eigenvalues of a square matrix. The eig function operates on the polynomial companion matrix to generate the roots. So, eig(compan(p)) is equivalent to roots(p), as illustrated below.

Did you know?

The Matlab built-in symbolic function jacobian(f,v) computes the Jacobian matrix is డ௙೔

డ௩ೕ. Note that if f and v are scalars, then the Jacobian is equivalent to diff(f,v). The

following are examples:

Did you know?

You can take advantage of Matlab symbolic differentiation function diff (or function newton(f, x0, tol) (refer to Problem 10 in Assignment 8). The function can then generate the derivative dfdx internally using: dfdx=matlabFunction(diff(sym(f))). Try it.

Appendix I

formula with vicinity.

Subtracting ݔכ

The last term in the above expression represents the sum of all terms in the series above the

ݔ௞ as

which, upon substituting in Equation (2), leads to or, Therefore, the error at a given iteration is proportional to the square of the error at the previous iteration; i.e.hod is quadratically convergent for ȁݔ௞െݔכ

Appendix II: -Root

A numerical method for computing ξܽ

idea is to formulate the problem such that ξܽ -. The equation can be readily determined by writing ݔൌξܽ difference equation): or

We may select and any ݔ଴്- to start the iterative process. (Selecting ݔ଴൐- leads

number. For an example, click here: link . Check out this video of an interesting retro relay-based calculator that computes the square-root of a number. This is a digital circuit that employs relays as opposed to transistors. solution is ݔൌξܽ

ξͳ͸ǡ with

An interesting analog electronic circuit for computing the square-root employs feedback, as is shown below. The following is a Multisim simulation of the square root circuit.

Continuous-

A continuous-

the derivative ௗ௫ ௛, where h is a small constant. transforms into the first-order nonlinear differential equation: Hence, the square-root problem becomes the solution of the nonlinear differential The above differential equation is of a special form that allows for an analytic solution. The following is its symbolic (analytic) solution using the online

WoframAlpha.com portal,

Matlab gives identical solution (and in addition it gives േξܽ built-in dsolve (symbolic) function:

So, one solution is,

quotesdbs_dbs21.pdfusesText_27

[PDF] fsr ac ma

[PDF] fsr cours

[PDF] fsr inscription

[PDF] fssc 22000 pdf francais

[PDF] fssm marrakech+inscription en ligne

[PDF] fssm master 2017

[PDF] fssm uca ma

[PDF] fst beni mellal

[PDF] fst beni mellal 2017

[PDF] fst beni mellal bcg

[PDF] fst beni mellal cycle d'ingenieur

[PDF] fst beni mellal inscription 2017 2018

[PDF] fst beni mellal inscription 2017/2018

[PDF] fst beni mellal inscription en ligne

[PDF] fst beni mellal licence professionnelle