Watch these four (4) 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 discusses the principles of the Gauss-Seidel iterative method and also discusses relaxation techniques to help the solution converge.
Hello, this is video SOE|VL|10 and is the theory of Gauss-Seidel for solving systems of equations.
First let us look at the theory. Unlike the previous methods that we saw before that use elimination techniques to solve for the x-values, Gauss-Seidel uses an iterative approach to converge onto a final solution. You assume a certain guess and you iterate through until that solution solved. We started off with our system of equations in the equation form. What we can do here is rearranged each one of these equations so that one of the xi terms is explicitly defined, for example, x1 = b1 - a12x2, etc. And then the second equation will be used for x2. And we have it for all our equations and we can solve with using these. Once we have the equations, we can take some guesses of the values. And we can use the equations to start iterating through and hopefully that it converges. We can also test to see if it's converging with the following formula, which is an estimate of the error εa,j and j here is the equation number. This will equal to the absolute value of (xji -xji-1)/xji. What you'd want is that all the equations go up towards 0. Now, since it's an iterative process, there is a chance that the solution diverges and we'd never actually attain a final solution. And this could be dependent on your initial guesses. However, there is a chance that the system will converge. This happens when the magnitude of the values in the diagonal is greater than the sum of all the other values in that row, their magnitudes. So this would be called a diagonally dominant system. And in that case there, no matter what initial guests that you use, it will converge. It may take longer to converge depending on the initial guesses, but it will converge. Luckily, in a lot of engineering problems, the system is diagonally dominant and can help with convergence. Here is an example of a system of equations that can be rearranged to become diagonally dominant. The equations are, the first one is x1 + 3x2 -4x3 + x4 = 2. The second equation is 5x1 + 2x2 - x3 - x4 = 3. The third equation is 3x1 + 3x2 - 2x3 - 6x4 = 1. And the last equation is 2x1 +4x2 - x3 +2x4 = 5. Now if we were to take the first equation and represent that equal to x1 and the second equation for x2, etc., our solution would likely diverge unless we're very close to the actual answer. However, if we look at this, we can try to rearrange these equations to be as diagonally dominant as possible. So, what we've done here is we've moved the red row up, which starts with 5x1 to be the first one because 5 is greater than the other coefficients in that first row, five is greater than two plus one plus one. We do the same for the other ones were trying to do, the next row would be green and work your way through to be as diagonally dominant as possible. Now if we start close, we can actually converge onto the answers.
There are some advantages to Gauss-Seidel. One, it is actually very useful for solving large systems of equations that have a sparse matrix. So what is a sparse matrix? Sparse matrix is when the many coefficients in the [A] matrix are essentially equal to 0. And that means that you might have lots of equations, but they're not all interrelated with each other, which is great. As mentioned before, the diagonally dominant matrices can converge very easily. And this happens in a lot of engineering problems. That round-off error that happens in elimination steps is actually avoided because we're always continuing iterating to find a better solution. This method is very efficient for large systems without accounting for a lot of memory constraints if you've ever solved it with a computer, because you don't have to, you'll only have to account for one set of values, associate a 100 equations, you only need to store a 100 values. Whereas if you were doing it in matrix format, you would need to have a full matrix, which would be a 100 by a 100 or 10 000 values and it can add up quite quickly in terms of memory constraints.
Let's look at 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 theory of the Gauss-Seidel method in a practice problem in a step-by-step approach.
Hello, this is video. SOE|VL|11 and is a step-by-step example of Gauss-Seidel use for solving systems of equations.
Let's look at the problem. Solve the following equations using Gauss-Seidel with initial guesses x2 = x3 = 5. We have three equations. The first equation is 5.6x1 + 3.3x2 +2x3 = 68.98. The second equation is 1.2x1 + 4.2x2 + 2.3x3 = 58.22. The final equation is 4.1x1 + 1.8x2 + 6.2x3 = 90.46. Before we do anything, we can look at these equations and we'll notice that they actually are already set to be diagonally dominant. That is, 5.6 is greater than 3.3 + 2.24. And the second equation 4.2 is greater than 1.2 + 2.3, and 6.2 is greater than 4.1 + 1.8. So it's definitely dominant, which means that any value that we choose should converge. Since this system of equations is already diagonally dominant, we can use equation 1 to represent an equation for x1, equation 2 to represent an equation for x2, and equation 3 to represent an equation for x3. we have x1 = (68.98 – 3.3x2 - 2x3)/5.6 of the equation. x2 = (58.22 -1.2x1 -2.3x3)/4.2. And finally, we have x3 = (90.46 - 4.1x1 -1.8x2)/6.2.
Now that we have the equations, we can set up an iterative table. This is done with six columns. In this case we have column i, x1, x2, x3, εa1, εa2, and εa3, all representing the estimate of the error for each of these functions. At iteration i, we will assume that x2 and x3 are equal to 0 as per the problem statement. And we don't need an initial guess for x1. For iteration one, we're going to start with the equation of x1, and we'll plug it in to find a guess of x1 using our initial guesses of x2 and x3. Next, we'll move on x2. And in this case here we'll use still that initial guess of x3 = five, but we'll use the estimate of x1 that was just calculated. Finally, we'll do x3, and this will use any kind of new values that we have for before. So, we'll have x1 = 7.59 and x2 = 8.96. We move on to the next iteration. It will start with x1 again and these will use the newest values of x2 and x3. We can calculate x2 in the similar fashion than x3. In this case here we can now estimate the approximate error for each functions. And you'll notice that there's still quite a bit of error with εa1 being 66.7%. And so we'll have to continue iterating for a bit. So, I'll move on to step 3, and we will find our values for step 3. The error is now slowly decreased. We can continue going through our examples. You'll notice that the estimate of the error for the third equation is getting relatively smaller. Which is great. And these numbers are starting to converge a bit. So x1 is close to 4 something, equation 2 is close to 7 something, and x3 is close to 9. Once we get to our 10th iteration, what you'll notice is that first the answers have started to converge close to two decimal places, x1 is close to 4.60, x2 is close to 7.40 and x3, close to 9.40. If you look at the estimate of the error, these are all very close as 0% within one decimal place. And so we can see that the answer has converged to these values, x1 = 4.6, x2= 7.4 and x3 = 9.4. We have solved the problem.
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 what a system of non-linear equation is, and how it differs from systems of linear equations. Newton-Raphson’s method for solving systems of non-linear equations is introduced..
Hello, this is video SOE|VL|12 and is the theory of Newton-Raphson method for solving systems of non-linear equations.
Let's look at the general theory of Newton-Raphson method. First, we'll start with what the difference is between a system of linear equations and a systems of non-linear equations. System of linear equations will have all its unknowns, x1, x2, and x3, in this case, all separate from each other and they are not connected. A system of non-linear equations; however, you cannot isolate for x1, x2, and x3 and they are sometimes multiplied together or in different functions. And this becomes non-linear and we cannot use the methods that we've seen already. To solve this, we have to do a little bit of manipulation and iterate. What we can do is we can start with the generalized Taylor series expansion of functions f. What we do here is we can actually combine it into the following formula. That is, the sum of j = 1 to n of the partial derivative, which is ∂fk,i/∂xj *(xj+1,i – x,i), which is equal to -fk,i. In this case here, k represents the different functions you have. That would be each separate equation. So if you had three equations, k would range from one to three. j represents the number of unknowns. So that would also range from one to three, since we will still need three equations and three unknowns. And i is the iterations that we have.
This can also take the form of a matrix, that is matrix [J], which represents the Jacobian matrix, times the matrix of [∆X] is equal to the matrix of [-F]. If we expand that out, what we get here is the partial derivatives of each of the functions, which is again called the Jacobian matrix, times some ∆xj values. For each value we have it is equal to the negative f functions that we have before. And in this case here, the f function should be equal to 0, as such done for non-linear equation solving. The ∆x1, ∆x2, etc., actually represents the change in x between one iteration to the next. What we can do here is we can take an initial guess. We can plug it into the partial derivatives to calculate a Jacobian matrix, we can find our -f1, -f2 values using the same initial guesses. And what we have is a system that is behaving like a normal linear system. We can solve it using methods we've seen before including Gauss elimination, LU decomposition, Gauss-Seidel and we'll solve for is the ∆x values. And what we could do then is we can update it to our new values.
Here is the algorithm for Newton-Raphson method.
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 the Newton-Raphson method in a practice problem in a step-by-step approach.
Hello, this is video SOE|VL|13 and it is a step-by-step example of using Newton-Raphson method for solving a system of nonlinear equations.
First, let's look at the problem. Solve the following equations using Newton-Raphson method with initial guesses of x1= 0.5, x2 = 2, x3 = 1. The three equations that we have here are for equation 1, x12x3 + 2x22 = 13. Second equation is x1x2x3 – x12x33 = 1.125. And the third and final equation is 4x1x2 + 2x1x3 = 11. The first step is to rearrange the equations so that one side is equal to 0, and those will be our f functions. For example, f1 = x12x3 + 2x22 – 13.. Now, it should be equal to 0. f2 = x1x2x3 – x12x33 - 1.125, which will equal to 0. And finally, the final equation, f3 = 4x1x2 + 2x1x3 = 11, and that should also be equal to 0. Recall for the Newton-Raphson method, we'll need to calculate the Jacobian as well as the [-F] matrices to be able to solve this problem. The Jacobian is all the partial derivatives with respect to each variable for each of the functions. And the [-F] is pretty straightforward and we'll just take the negative of the f-values we just calculated previously. So let's look at taking the partial derivatives for f1, ∂f1/∂x1 2x1x3, ∂f1/∂x2 = 4x2, ∂f1/∂x3 = x12. Next, we'll do f2, ∂f2/∂x1 = x2x3+2x1x33, ∂f2/∂x2 = x1x3, ∂f2/∂x3 = x1x2 – 3x12x32. Finally, we'll do the third equation, ∂f3/∂x1 = 4x2 + 2x3, ∂f3/∂x2 = 4x1, ∂f3/∂x2 = 2x1. So these are the values that we can use to calculate our Jacobian. Now that we have our Jacobian and original values, we have this sort of matrix like this, and we can plug our estimates of x1, x2, and x3 into it. And what you'll notice is we get a system of equations that we can solve for ∆x1, ∆x2, and ∆x3. In this case, we'll have the rows 1, 8, 0.25, and 1, 0.5, 0.75, and 10, 2, 1. And that will be equal to 4.75, 0.375, 6. Once we've found our delta values, we can update our iteration and come back into the formulas again and replace them and solve again. So just as a reminder, we'll start off with a table of what we've have here, our initial values of the xjs, that is 0.5. 2, 1. We use that actually to calculate the [-F] as well as the Jacobian. And now we can use any solver we'd like to solve it, for example, a Gauss elimination to give us our ∆xj's. And so this is representing the change in the values that we have. In this case, we can actually determine an estimate of the error and there's still quite a bit of an error associated with this. We’ll move on to our second iteration. And what we'll do here is update our xj column with the formula xj,i+1 = xj,I + ∆xj that we have here. So we're going to do here is 0.5 + 0.516, 2 + 0.53, 1 - 0.234. You'll see these are new values. Once we have a new values, we can calculate both our Jacobian and a [-F] functions. And we can continue on to get our change as well. This will keep going until our ∆ change will go down. Looking at the next iteration for i = 3. Applying the same formula, we're getting some values that are a little bit closer. We calculate the Jacobian and the [-F] matrix and get new values. Again. What you'll notice is that our estimate of the error is decreasing significantly for equations 1 and 2 as it is 0.9% and 0.2%, but equation 3 is still quite high at 10%. So we will continue on through our iterations. We've done already iteration 4 in a similar fashion. It's slowly going down still. We can do our iteration number 5 the same way. Calculating through our ∆xj is decreasing. We can do our iteration 6. OK so now we're at 4% for that last equation. With iteration 7, we use something similar again. We're down to 2.3%. With iteration 8, down to 1.2% for the last one on the other two are practically 0. With iteration 9 we’re down to 0.6%. And let's do one more iteration. With this last iteration of iteration 10, we can see what our answers are converging to. And so our error is very small and our final answers are, x1 = 1, x2 = 0.5, and x3 = 0.5 based off of iteration ten in the xj column.
This concludes the video. This project could not have been completed without the support of eCampusOntario and the University of Ottawa.