際際滷

際際滷Share a Scribd company logo

Nl eqn lab

Alvin Setiawan
Alvin Setiawan

The document provides details on using the bisection method to find the root of a nonlinear equation. It begins with an overview of the bisection method and how it iteratively searches for the root between two initial guesses. It then describes how to check if the initial guesses validly bracket a root by evaluating the product of the function values at the guesses. If the product is negative, a root is known to exist between the guesses. The method is then explained step-by-step, showing how the range is bisected in each iteration until converging on the root. An example problem is provided and solved over 12 iterations to demonstrate the convergence of the bisection method.

1 of 6
Download to read offline
1 Lab notes In this lab, you will be developing 3 VB codes. You are pretty much on your own to build these codes. The codes are: 1) Bisection method (detailed notes and algorithm are given below, please read this before you come to the lab lecture). 2) Direct substitution method (you should have covered this in the class) 3) Newton Raphson method (covered this in the lab). Make sure you use two subprogramsone for the function and one for its derivative when coding this. Here is the template to use Input xold guess, iter (no of iterations), and tol (tolerance level) For i = 1 to iter Call myfx(x, fx) Call mydfx(x,dfx) xnew = xold (fx/dfx) err = abs((xnew-xold)/xold)*100 output xnew, fx, dfx, and error If (err < tol) Then Exit for End if Next i **Write your myfx sub here ** **Write your mydfx sub here** Root finding using the Bisection Method One of the basic numerical approaches to find the root of a nonlinear equation ( )f x is the bisection method. The method can be derived from a graphical point of view. Consider a function ( )f x shown in Figure 1. By definition, the root of the equation ( )f x is nothing but the value of x when the function ( )f x becomes zero. As shown in the figure, to employ bisection method the user should provide two initial guess values XL and XU that bound the root of the function. Note, the root need not be at the midpoint, but it has to be in-between these two guess values. The method uses these two guess values to iteratively search for the root in a systematic manner.
03.03.2 2 Figure 1 The root should be bound by the two initial guess values Before we learn the search algorithm, we will consider the following question: how can one verify whether a root is present in-between the two arbitrary guess values XL and XU. Figure 2 shows a case where the user has provided two valid guess values. Under this condition, as shown in the figure, the value of function corresponding to XL, which is f (XL) will be negative, and the value of function corresponding to XU, which is f (XU), will be positive, hence the value of the product f (XL) *f (XU) will be negative, therefore ( ) ( ) 0L Uf X f X < . On the other hand, Figure 3 shows two instances where the user had provided invalid guesses for XL and XU values, which are not bounding a root. Under this condition, as shown in the figures, the value of the two functions f(XL) and f(XU), corresponding to XL and XU, respectively, will be of the same sign (either negative or positive); therefore, the value of the product f (XL) *f (XU) will always be positive, hence ( ) ( ) 0L Uf X f X > . Therefore, it can be concluded that the equation 0)( =xf , where )(xf is a real continuous function, has a root between XL and XU if the product ( ) ( ) 0L Uf X f X < . On the other hand, if ( ) ( ) 0L Uf X f X > then there may not be a root between the two guess values. The validity of above arguments is the central basis of the bisection method. Note, these arguments also assume that the function is monotonic and has only one root between XL and XU. . f (x) XL XU x
3 f (x) XL XU x f (xU) is +ve f (xL) is -ve Figure 2 If ( ) ( ) 0L Uf X f X < (or negative) then there is a root in between to guess values the product f (x) XL XU x f (xU) is -ve f (xL) is -ve f (x) XL XU x f (xU) is -ve f (xL) is -ve f (x) XL XU x f (xU) is +ve f (xL) is +ve f (x) XL XU x f (xU) is +ve f (xL) is +ve Figure 3 If ( ) ( ) 0L Uf X f X > (or positive) then there will not be a root in between to guess values Logic for Checking the Validity of the Initial Guesses for the Bisection Method The concepts illustrated in Figures 2 and 3 can be summarized in a computer algorithm to first identify whether the guess values are bracketing the roots or not. The algorithm can be written as:
03.03.4 4 1. Read the values of XL and XU from the spreadsheet 2. Compute f(XL) and f(XU) and evaluate the value of their product P = f (XL) *f (XU) 3. If P < 0 then it is a valid guess and the root lies between XL and XU, else stop the program and prompt the user invalid guesses, provide another values. The Details of the Bisection Procedure Now that we have verified (using the above algorithm) that a root is present somewhere in the region between the guess points XL and XU, we will first find a mid-point, XM = (XL + XU)/2. We will use this midpoint to divide the region into two new intervals: 1) (XL and XM) and 2) (XM and XU). Now we need to figure out whether the root is between XL and XM or XM and XU? We know for sure that one of these intervals is a valid interval that can be used as guess values of the next iteration and the other one should be abandoned. Well, we will once again employ the logic discussed in steps 2 & 3. We will first find the sign of ( )* ( )L Mf X f X and if it is negative [or if ( ) ( ) 0L Uf X f X < ] then the root should be in between XL and XM, otherwise, it has to be between XM and XU. Therefore, with a single test we can narrow the original range by half. By repeating this process, the width of the interval can be made smaller and smaller and we can eventually find the root. Figure 4 shows conceptual diagram of the progression of this search algorithm. As show in the figure, initially (before iteration-1) we start with XL and XU, which envelops a wide range. With every iteration, the range will become smaller and smaller and eventually you will land on the exact root. Note, as the solution converge the difference between the values of XL and XU will be small and also the value of the function f(x) will be close to zero. You can use one of them as a criterion to check for convergence. f (x) XL XU x XM XU (next iteration) f (x) XL XU x XM Iteration-1;here, XM become Xu for the next iteration Iteration-2;here XM become XL for the next iteration XL (next iteration) Figure 4 Progression of bisection algorithm. Detailed Computer Algorithm The complete computer algorithm for the bisection method can be summarized as follows:
5 1. Read the values of XL and XU from the spreadsheet 2. Compute f(XL) and f(XU) and evaluate the product Ptest = f (XL) *f (XU). Note we can use a subprogram to efficiently compute the function values. 3. If Ptest < 0 then we have valid guess values and the root lies between the original guess values XL and XU, else stop the program and ask them to provide another guess vales. 4. Iterate n time (where n is the number of iterations given by the user) 5. Estimate XM = (XL + XU)/2 6. Evaluate P = f (XL) *f (XM) IF (P < 0), Then (note the root must be between XL and XM) Set XU = XM ELSE Set XL = XM END IF 7. IF ABS[f(XM)] < 0.001 (some small value) you have found the root so exit iteration 8. Iterate and go to step 4 9. Output the latest value of XM as your best estimate of the root PROBLEMS 1) Find the root of the following non-linear equation and evaluate the value of x using the Bisection method [ ] 667 ( ) 40 1 exp( 0.15 )f x x x = + Perform five iterations by hand and assume initial guess value of for XL = 12 and XU = 16. Report the updated new values of XL and XU at the end of each of the iteration. 2) Plot the results of your hand calculations XL, XU and XM values for each iteration and develop figures similar to Figures 4 and explain the working of the convergence process for this test problem. 2) Develop VB program for solving the above problem using the Bisection method. Systematically output the XL and XU values at the end of each of the iteration and verify the values against the hand calculated results. Initial guess of 12 and 16 Iter # XL f(XL) XU f(XU) XM f(XM) P 1 12 -2.0943 16 -2.0943 14 1.808683 11.56738 2 14 -2.0943 16 -2.0943 15 -0.22009 -0.39806 3 14 -0.22009 15 -0.22009 14.5 0.774025 1.399966 4 14.5 -0.22009 15 -0.22009 14.75 0.272025 0.210554 5 14.75 -0.22009 15 -0.22009 14.875 0.024748 0.006732 6 14.875 -0.22009 15 -0.22009 14.9375 -0.09797 -0.00242 7 14.875 -0.09797 14.9375 -0.09797 14.90625 -0.03669 -0.00091 8 14.875 -0.03669 14.90625 -0.03669 14.89063 -0.00599 -0.00015
03.03.6 6 9 14.875 -0.00599 14.89063 -0.00599 14.88281 0.009375 0.000232 10 14.88281 -0.00599 14.89063 -0.00599 14.88672 0.001692 1.59E-05 11 14.88672 -0.00599 14.89063 -0.00599 14.88867 -0.00215 -3.6E-06 12 14.88672 -0.00215 14.88867 -0.00215 14.8877 -0.00023

More Related Content

Nl eqn lab

  • 1. 1 Lab notes In this lab, you will be developing 3 VB codes. You are pretty much on your own to build these codes. The codes are: 1) Bisection method (detailed notes and algorithm are given below, please read this before you come to the lab lecture). 2) Direct substitution method (you should have covered this in the class) 3) Newton Raphson method (covered this in the lab). Make sure you use two subprogramsone for the function and one for its derivative when coding this. Here is the template to use Input xold guess, iter (no of iterations), and tol (tolerance level) For i = 1 to iter Call myfx(x, fx) Call mydfx(x,dfx) xnew = xold (fx/dfx) err = abs((xnew-xold)/xold)*100 output xnew, fx, dfx, and error If (err < tol) Then Exit for End if Next i **Write your myfx sub here ** **Write your mydfx sub here** Root finding using the Bisection Method One of the basic numerical approaches to find the root of a nonlinear equation ( )f x is the bisection method. The method can be derived from a graphical point of view. Consider a function ( )f x shown in Figure 1. By definition, the root of the equation ( )f x is nothing but the value of x when the function ( )f x becomes zero. As shown in the figure, to employ bisection method the user should provide two initial guess values XL and XU that bound the root of the function. Note, the root need not be at the midpoint, but it has to be in-between these two guess values. The method uses these two guess values to iteratively search for the root in a systematic manner.
  • 2. 03.03.2 2 Figure 1 The root should be bound by the two initial guess values Before we learn the search algorithm, we will consider the following question: how can one verify whether a root is present in-between the two arbitrary guess values XL and XU. Figure 2 shows a case where the user has provided two valid guess values. Under this condition, as shown in the figure, the value of function corresponding to XL, which is f (XL) will be negative, and the value of function corresponding to XU, which is f (XU), will be positive, hence the value of the product f (XL) *f (XU) will be negative, therefore ( ) ( ) 0L Uf X f X < . On the other hand, Figure 3 shows two instances where the user had provided invalid guesses for XL and XU values, which are not bounding a root. Under this condition, as shown in the figures, the value of the two functions f(XL) and f(XU), corresponding to XL and XU, respectively, will be of the same sign (either negative or positive); therefore, the value of the product f (XL) *f (XU) will always be positive, hence ( ) ( ) 0L Uf X f X > . Therefore, it can be concluded that the equation 0)( =xf , where )(xf is a real continuous function, has a root between XL and XU if the product ( ) ( ) 0L Uf X f X < . On the other hand, if ( ) ( ) 0L Uf X f X > then there may not be a root between the two guess values. The validity of above arguments is the central basis of the bisection method. Note, these arguments also assume that the function is monotonic and has only one root between XL and XU. . f (x) XL XU x
  • 3. 3 f (x) XL XU x f (xU) is +ve f (xL) is -ve Figure 2 If ( ) ( ) 0L Uf X f X < (or negative) then there is a root in between to guess values the product f (x) XL XU x f (xU) is -ve f (xL) is -ve f (x) XL XU x f (xU) is -ve f (xL) is -ve f (x) XL XU x f (xU) is +ve f (xL) is +ve f (x) XL XU x f (xU) is +ve f (xL) is +ve Figure 3 If ( ) ( ) 0L Uf X f X > (or positive) then there will not be a root in between to guess values Logic for Checking the Validity of the Initial Guesses for the Bisection Method The concepts illustrated in Figures 2 and 3 can be summarized in a computer algorithm to first identify whether the guess values are bracketing the roots or not. The algorithm can be written as:
  • 4. 03.03.4 4 1. Read the values of XL and XU from the spreadsheet 2. Compute f(XL) and f(XU) and evaluate the value of their product P = f (XL) *f (XU) 3. If P < 0 then it is a valid guess and the root lies between XL and XU, else stop the program and prompt the user invalid guesses, provide another values. The Details of the Bisection Procedure Now that we have verified (using the above algorithm) that a root is present somewhere in the region between the guess points XL and XU, we will first find a mid-point, XM = (XL + XU)/2. We will use this midpoint to divide the region into two new intervals: 1) (XL and XM) and 2) (XM and XU). Now we need to figure out whether the root is between XL and XM or XM and XU? We know for sure that one of these intervals is a valid interval that can be used as guess values of the next iteration and the other one should be abandoned. Well, we will once again employ the logic discussed in steps 2 & 3. We will first find the sign of ( )* ( )L Mf X f X and if it is negative [or if ( ) ( ) 0L Uf X f X < ] then the root should be in between XL and XM, otherwise, it has to be between XM and XU. Therefore, with a single test we can narrow the original range by half. By repeating this process, the width of the interval can be made smaller and smaller and we can eventually find the root. Figure 4 shows conceptual diagram of the progression of this search algorithm. As show in the figure, initially (before iteration-1) we start with XL and XU, which envelops a wide range. With every iteration, the range will become smaller and smaller and eventually you will land on the exact root. Note, as the solution converge the difference between the values of XL and XU will be small and also the value of the function f(x) will be close to zero. You can use one of them as a criterion to check for convergence. f (x) XL XU x XM XU (next iteration) f (x) XL XU x XM Iteration-1;here, XM become Xu for the next iteration Iteration-2;here XM become XL for the next iteration XL (next iteration) Figure 4 Progression of bisection algorithm. Detailed Computer Algorithm The complete computer algorithm for the bisection method can be summarized as follows:
  • 5. 5 1. Read the values of XL and XU from the spreadsheet 2. Compute f(XL) and f(XU) and evaluate the product Ptest = f (XL) *f (XU). Note we can use a subprogram to efficiently compute the function values. 3. If Ptest < 0 then we have valid guess values and the root lies between the original guess values XL and XU, else stop the program and ask them to provide another guess vales. 4. Iterate n time (where n is the number of iterations given by the user) 5. Estimate XM = (XL + XU)/2 6. Evaluate P = f (XL) *f (XM) IF (P < 0), Then (note the root must be between XL and XM) Set XU = XM ELSE Set XL = XM END IF 7. IF ABS[f(XM)] < 0.001 (some small value) you have found the root so exit iteration 8. Iterate and go to step 4 9. Output the latest value of XM as your best estimate of the root PROBLEMS 1) Find the root of the following non-linear equation and evaluate the value of x using the Bisection method [ ] 667 ( ) 40 1 exp( 0.15 )f x x x = + Perform five iterations by hand and assume initial guess value of for XL = 12 and XU = 16. Report the updated new values of XL and XU at the end of each of the iteration. 2) Plot the results of your hand calculations XL, XU and XM values for each iteration and develop figures similar to Figures 4 and explain the working of the convergence process for this test problem. 2) Develop VB program for solving the above problem using the Bisection method. Systematically output the XL and XU values at the end of each of the iteration and verify the values against the hand calculated results. Initial guess of 12 and 16 Iter # XL f(XL) XU f(XU) XM f(XM) P 1 12 -2.0943 16 -2.0943 14 1.808683 11.56738 2 14 -2.0943 16 -2.0943 15 -0.22009 -0.39806 3 14 -0.22009 15 -0.22009 14.5 0.774025 1.399966 4 14.5 -0.22009 15 -0.22009 14.75 0.272025 0.210554 5 14.75 -0.22009 15 -0.22009 14.875 0.024748 0.006732 6 14.875 -0.22009 15 -0.22009 14.9375 -0.09797 -0.00242 7 14.875 -0.09797 14.9375 -0.09797 14.90625 -0.03669 -0.00091 8 14.875 -0.03669 14.90625 -0.03669 14.89063 -0.00599 -0.00015
  • 6. 03.03.6 6 9 14.875 -0.00599 14.89063 -0.00599 14.88281 0.009375 0.000232 10 14.88281 -0.00599 14.89063 -0.00599 14.88672 0.001692 1.59E-05 11 14.88672 -0.00599 14.89063 -0.00599 14.88867 -0.00215 -3.6E-06 12 14.88672 -0.00215 14.88867 -0.00215 14.8877 -0.00023