Watch these five (5) videos in order. The total video time is 23 min. Be sure to test your knowledge with the knowledge checks after each video.
Description: This video introduces non-linear equations and how to manipulate the equation to solve for its roots. It also discusses cases with asymptotes and multiple roots.
Hello everyone this is video NLE|VL|01 and it will be an introduction to solving non-linear equations. Let's have a brief introduction of what non-linear equations are first. You may recall that a linear equation is a linear equation is a straight line through a graph.
The general notation for this is y = mx + b where m is the slope of the line and b is the intercept. A non-linear equation, as the name suggests, is an equation that does not follow a straight line. One equation that you might have seen is the quadratic equation where y = ax2 + bx + c. If we want to solve for x when y = 0 then there's an analytical solution that many of you should already know, which is x = -b ±√(b2-4ac)/(2a). Solving for when y = 0 is also known as solving for the roots of an equation and therefore solving non-linear equations is also known as rootfinding. Other equations, even simple ones, such as ex = x2 does not have an analytical solution and must be solved numerically
We will now discuss two general methods for solving non-linear equations. The first are bracketing methods. With these methods two points are needed to bracket the root between an interval, between x1 and x2. The methods then can be used to find the estimate of the root xR. If the root is between the two points, then the interval gets smaller and converges on the root. The other methods are open methods which only requires one initial estimate of the root. Usually, these methods will require the derivative or an estimate of the derivative to be able to solve and can converge very quickly or if the initial point is not great can diverge.
All root finding problems should set the equation equal to zero that is there's some function f(x) and should be equal to zero. X here is the variable that you're looking for. Take for example the equation before, ex is equal to x2. This can be rearranged by moving the x2to the other side to get ex - x2 = 0. Therefore, our function is f(x) = ex -x2. Here is another example where the heat capacity cP is equal to some quadratic function, A + BT + CT2. If you know what the temperature is then the heat capacity is easy to find, but other times you want to go the opposite way and find T. This is a quadratic equation so you could use the quadratic formula or you can use a numerical method by moving cP to the other side of the equation. In this case we will have A + BT + CT2 -cP = 0, which will be our function f(T) that we want to solve. Let's look at the non-linear equation cos x = x it is possible to graph this function as y = cos x and y = x. Where the two lines intersect is the solution to this problem. The issue is where the lines intersect there is a certain value y and we don't know what that is and it would be difficult to predict because each function is different. If we set the function equal to zero then we know that the value we are looking for is when y = 0 and we can do this with a simple numerical test. If we have points x1 and x2 and it crosses the x-axis then f(x1)f(x2) must be less than 0 or negative. Please note if the equation was solved differently where x - cos x = 0 the answer is still true and the condition of f(x1)f(x2)<0 is also true. This test holds true provided that the nonlinear equation crosses the x-axis.
Unfortunately it also holds true with asymptotes where the f(x1)f(x2) will be less than zero; however, as x1 and x2approaches each other the values should be going towards zero if it is a true root and it will be diverging away from zero if it is an asymptote. For many non-linear equations there could be more than one root. Although there are multiple roots in an engineering context, there is typically only one root that makes physical sense. For example, only a positive root would make sense for a length that you're trying to determine or the time. In some cases multiple roots need to be determined for the problem. The methods discussed in this class and in the following videos can solve for multiple roots; you will simply apply each method to solve each root individually and solve as many routes as necessary.
This concludes the video this project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video discusses a simple trial-and-error method for finding find a root to an NLE.
Hello, this is video NL|VL|02 and it will be on the theory of incremental search for solving nonlinear equations. Let's first discuss the principle behind incremental search. Incremental search can be viewed as a trial-and-error approach for finding the root of an equation with the function f(x) known and a starting point x. We take a step of Δx. Now that we have the points x and x+Δx, we can do a simple test. We can ask if f(x)f(x+Δx) is that less than zero. If that product is not negative, then we continue stepping until it turns negative. When it is negative, we know the root is between those two bounds x+Δx. We can stop here because we know where the root is, or we can take a smaller step, for example, half of Δx. We can then check the bounds in this region to see if it crosses as well. If it does, then we would continue stepping in the smaller step size. In the example shown, it does cross the bounds and therefore we can take an even smaller step by step of Δx/4.
To get a better estimate of the root, let's break this down into more graphical steps. Let's start with the function shown here in orange. We now have an interval between x+Δx. We can evaluate if the function crosses the x-axis between this interval. In this case it does not and therefore we will need to take a step and try again. We will continue the stepwise approach until we hit f(x)f(x+Δx) <0. When it is, then instead of stepping forward, you take a small half step from where you are, and you continue this procedure. If it is within the bounds and you take half step and if not, you keep stepping until you find it. With this method, you must be careful of what you choose for your x and Δx. If you take too large of a step, then you might step over the bounds. If you take too small the step, then it might take you a long time to find the bounds, and if you start after the root has happened then you might never find the bounds is a good idea to try to graph the function before using this method. You can also work backwards with a Δx that is negative. If done properly, then eventually you'll get very close to the root and the graph becomes a straight line. When you believe you are close enough to the root, then you take the midpoint between your bounds. That is, your root is XR is equal to x+Δx/2.
Next, we'll look at the algorithm Step one is with an x and Δx. Evaluate f(x)f(x+Δx). Continue stepping until f(x)f(x+Δx)< 0. Decrease your step size by a factor, typically a factor of 2. Repeat steps one to three until you reach some sort of stopping criteria. εa is less than εs. For this case, εa, your approximation of the error, is going to be equal to the following formula. The absolute value of Δx/2 all over the absolute value of x+Δx/2. Once you reach that point, you can set the root to xR = x+Δx/2.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video implements the theory of incremental search in a practice problem in a step-by-step approach.
Hello, this is video NLE|VL|03 and it will be a step by step example of incremental search. First, let's discuss the problem. We will solve the following equation ex = x2. You can stop iterating when the approximation error is less than 1%. We will start with. x = 1 and Δx = -0.5. The first step in any non linear problem is to rearrange it. So we will take the ex = x2 and move the x2 to the other side to get f(x) = ex - x2. We will solve this problem using the following layout. In the top lefthand corner will be a graph representing the graphical solution to this problem. In the top righthand corner will be the important equations used to solve this problem. On the righthand side of this there will be a graph showing the error at the end of each approximation, which should go down the more iterations that occur. At the bottom of this layout will be the steps taking in a data table showing each calculation that's performed. Recall that the specific equation for this problem is f(x) = - x2+ ex. One of the equations you use most often is if f(x)f(x+Δx) <0. And finally we have our approximation of the error, which is Δx/2 over x +Δx/2 and the absolute value of that.
So let us begin. First, we will plot the graph between negative one and one, just to see if it crosses over the x- axis. Will use the initial conditions x = 1 and Δ= -0.5. x+Δx can easily be calculated by adding the two together. Next, we use the function -x2 + ex to calculate values at f(x) and f(x+Δx). Now that we have the f values we can calculate our important criteria to determine if we take a step or not. That is f(x)f(x+Δx). Is it less than zero? In this case it is not. Since it is not we cannot really calculate an error because the root is not between this interval, and since it's not between the interval, we will take a step Δx. Now x becomes x+Δx or 0.5 in this case. Our Δx does not change, so it stays at - 0.5. We are now back to where we started like our first iteration, we can calculate our x+Δx and then calculate our f(x) and f(x+Δx). Then we can test to see if the root crosses between these two points. In this case, again, it does not, and therefore we cannot calculate an error and we will continue on with iteration 3 by taking a step. Iteration 3 also does not have any bounds and therefore will be moving another step. From the graph in the top left hand corner you can see that it looks like the function will be crossing the x-axis, and sure enough it does in iteration 4. This means that an error can be calculated because it is crossing over the x-axis. The error is approximately 33% which is greater than the 1% we are looking for since the function across the x-axis. Instead of taking step Δx will be divided by two. Now we go back to having an x and a Δx, and the steps can be repeated with each iteration that crosses the x-axis. The error should be decreasing until we finally hit our εa is less than 1%. What you'll notice on the right-hand side is that the error is decreasing over the number of iterations and with the graphical plot you'll see that the line is getting straighter and straighter.
At the 13th iteration we finally hit our stopping criteria that εa is less than 1% Once we are below our 1%, we can stop and take our final estimate of the root. In this case the root xR is equal to x+Δx/2 and specifically in this it would be equal to -0.707. This problem is now complete with a solution.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video discusses how to systematically divide a range where the root is present into equal parts, and to decrease the range, until the root is found.
Hello this video is NLE|VL|04 and focuses on the theory of bisection method to solve non-linear equations.
Let's first discuss the principle behind bisection method the root should be between xL, the lower bound and xU, the upper bound. xL represents the smallest number between xL and xU and the estimate of the root known as xR is found by taking the average between xL and xU. This can be done by adding xL and xU together and dividing by two. With xRthe region is now divided into two parts first region between xL and xR and the second region between xR and xU. We are now tasked to determine where the root crosses the x-axis. Is it in the first region between xL and xR or in the second region between xR and xU? This can be done by testing the condition if f(xL)f(xR) <0. If it is then the root is between xL and xR and we change it such that xU is now the xR. If it is not within those bounds then it is in within the other bounds where f(xR)f(xU) < 0 and we will change it so that xL is now the new xR. Now that either xL or xU has been changed. We can repeat the process to find the next xR.
Let's now look at this with graphical steps. Let's start with a function at f(x) = 0 that crosses the x-axis. This will be our first iteration i where we have the bounds xL and xU that crosses the x-axis. We know this because f(xL) f(xU) should be less than zero next we find the first estimate of xR by taking the average of xL and xU in this case xL is equal to 0 and xU is equal to 2 then xR, which is the average would be equal to 1. We have now split the bounds into two regions and we can test which region the function crosses the x-axis. So in this case either f(xL)f(xR) < 0 or f(xR)f(xU) <0. For this example, it crosses in the second region. We now adjust the bounds and finish our first iteration. We now have new xL and xU bounds and the process can be repeated. In the second iteration we do the same thing and find the middle between xL and xU and determine where we will move our bounds. You continue doing multiple iterations until the stopping criteria is met depending on how accurate and precise you want to be. The number of iterations could vary between you know small numbers such as five up to thousands. For this case we'll stop after 10 iterations the estimate of the root would be xR in this case 1.65723. What you'll notice is on the y-axis the value is quite close to 0. This could be one of the stopping criteria.
Let's review the algorithm.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.
Description: This video implements the bisection method to solve a problem in a step-by-step procedure.
Hello, this is video NLE|VL|05 it is a step-by-step example of bisection method for solving non-linear equations. First let's look at the problem. Solve the following equation ex = x2 and stop iterating when your error, εa, is less than 1%. For this problem we will use our bounds as xL = -1 and xU = 1. Step one is to 1st rearrange the equation. We take ex = x2 and put it on the same side. So, we have f(x) = ex - x2, which is of course equal to 0.
Let's now look at the calculations. We will break our solution to different parts. In the top lefthand corner, we will be looking at the graphical solution of bisection method. In the top righthand corner will be the equations we'll use to solve this problem. On the righthand side will be a graph that will show how the error is decreasing over a number of iterations. On the bottom will be the table of iterations, so all the calculations can be shown. Let's look at all the functions we have. First, we have the function f(x) = ex - x2. Next, we have the equation of the root which will be xR = (xL +xU)/2. Finally, we have the estimate of the error and this is εa = |( xRi- xRi-1)/xRi|.
Let's graph the function between our bounds, -1 and 1, well you'll notice from the graph is that the function does cross the x-axis, which means that our bounds is correct. This can be numerically seen by taking the f(x) value at f(xL) and f(xU). You will notice that multiplying f(xL) and f(xU) is less than 0 which means that numerically works as well. Now we can calculate xR, which is the average between xL and xU, in this case the average of -1 and 1 is 0. Once we have xR, we can calculate f(xR) using our formula. Normally we can calculate our error εa at this point, but since we only have one iteration, we cannot do it. Now we can determine where our new bounds are. This is done by testing f(xL)*f(xR) and determining whether it is less than 0. In this case, that is true, and therefore the new bounds will be between xLand xR. This means for our second iteration, xL will be negative one and xU will be zero, which was xR in the previous iteration. Now we can do the same process as before, calculating f(xL) and f(xU), as well as calculate xR. And since we have xR we can now calculate f(xR). And now that we have an estimate of xR we can calculate an estimated error. In this case it would be |(-0.5 – 0)/-0.5| which gives us 100%. Now we can test the bounds again and we can see that the root crosses between xL and xR and so we will move the bounds for iteration 3. So for iteration 3 we will have new bounds. We will have xL = -1 and xU = -0.5. We can now go through the same iterations as before to find the new xR as well as the estimate of the error. And you will see that in this iteration the estimate of error is now reduced down to 33%. Next, we can test the bounds of f(xL)*f(xR) and what you'll notice is that in this case the bounds are between xRand xU since f(xL)*f(xR) > 0, our new bounds will change. xL = -0.75 and xU -0.5 and now we can continue with our iterations, calculating xR as well as the estimate of the error εa, until our error is less than 1% for this question. For this question, this actually occurs after the 9th iteration. You'll notice for a graph on the righthand side of the estimate, the error also decreases significantly down to zero. Since we are less than our error, we can now find our estimate of our root, which is the last estimate of xR. In this case it will be xR = -0.707 and we are now done this question.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.