Gaussian elimination

Gaussian elimination is most easily described using a specific example. Consider the linear system 

The idea behind Gaussian elimination is to kill (eliminate) one of the unknowns in the second and third equations (using the first) and then to eliminate another unknown from the third equation (using the second). This leaves the third equation with only one unknown. For the example, if the first equation is subtracted from the second and third equations, the result is 

if the second equation is multiplied by 1/3 and the result added to the third, 

The last equation now contains only x solving gives Xj = -2. Knowing Xj, from the second equation, X2 = -2, and finally from the first equation, knowing Xj and X2 leads to Xj = 4. Therefore, the linear system has one solution 

Going from the last equation to the first while solving for the unknowns is called backsolving or backsubstitution. It is important to see that when multiplying one equation by a scalar and adding the resnlt to another one, equality is maintained. 

The decomposition will be performed by Gaussian elimination. This classical method can easily be understood by solving an example. 

The next pivot will be [A]4 3 = 4.0, thereby interchanging rows 3 an 4. To eliminate xj from equation 3 we need the single multiplier -2.0/4.0 = -0.5, and obtain the matrix in the desired upper triangular form  

Equations (1.49) are very easy to solve. Indeed, x = -1 is already isolated in equation 4. Proceeding with this value to equation 3 gives x = 0. Then we move to equation 2 with x and x known. The procedure is called backsubstitution and gives the solution vector x = (1.0, 2.0, 0.0, -1.0).  

Gauss gave a shorter algorithm that introduces fewer roundings. The method has two parts elimination and backsubstitution. We describe it here for the array a of Eq. (A.3-1) with m = n. 

Find apk, the absolutely largest of the elements akk, , nk-If apk is negligible, stop and declare the matrix singular. Otherwise, accept apk as the pivot for stage k, and (if p k) 

If fc n, eliminate from rows k + 1. n by transforming the array as follows [here denotes element values just before this calculation  

Associating each coefficient Ujj with the corresponding element of x, we get the transformed equation system 

The solution is direct when Eqs. (A.4-4) are applied in the order given, since each right-hand member then contains only quantities already found. 

---

The most important direct solution algorithms used in finite element computations are based on the Gaussian elimination method. 

To describe the basic concept of the Gaussian elimination method we consider the following system of simultaneous algebraic equations... 

The Gaussian elimination method provides a systematic approach for implementation of the described forward reduction and back substitution processes for large systems of algebraic equations. 

To estimate the computational time required in a Gaussian elimination procedure we need to evaluate the number of arithmetic operations during the forward reduction and back substitution processes. Obviously multiplication and division take much longer time than addition and subtraction and hence the total time required for the latter operations, especially in large systems of equations, is relatively small and can be ignored. Let us consider a system of simultaneous algebraic equations, the representative calculation for forward reduction at stage is expressed as... 

SOLUTION ALGORITHMS BASED ON THE GAUSSIAN ELIMINATION METHOD... 

The most frequently used modifications of the basic Gaussian elimination method in finite element analysis are the LU decomposition and frontal solution techniques. 

SOLUTION ALGORITHMS GAUSSIAN ELIMINATION METHOD 205 6.4.2 Frontal solution technique... 

Gaussian Elimination, hi the most elementary use of Gaussian elimination, the first of a pair of simultaneous equations is multiplied by a constant so as to make one of its coefficients equal to the corresponding coefficient in the second equation. Subtraction eliminates one term in the second equation, permitting solution of the equation pair. 

Solving several equations by the method of Gaussian elimination, one might divide the first equation by [ j. obtaining 1 in the [ j position. Multiplying ayi into the first equation makes an ay]. Now subtracting the first equation from the second, a zero is produced in the a2i position. The same thing can be done to produce a zero in the a. ] position and so on, until the first column of the eoefflcient matrix is filled with zeros except for the Un position. 

Note that the matrix from Exercise 2-8 is the matrix of coefficients in this simultaneous equation set. Note also the similarity in method between finding the least equation and Gaussian elimination. 

The triangular matrix A resulting from Gaussian elimination is... 

Gaussian elimination and test it by solving the equation set in Exercise 2-13. 

Procedure. Write a program for solving simultaneous equations by the Gaussian elimination method and enter the absorptivity matiix above to solve Eqs. (2-51). Set up and solve the problem resulting from a new set of experimental observations on a new unknown solution leading to the nonhomogeneous veetor b = 0.327,0.810,0.673. ... 

The LU decomposition is essentially a Gaussian elimination, arranged for maximum efficiency (Ref. 112). The chief reason for doing an LU decomposition is that it takes fewer multiplications than would be needed to find an inverse. Also, once the LU decomposition has been found, it is possible to solve for multiple right-hand sides with little increase in work. The multiphcation count for a.n n X n matrix and m right-hand sides is... 

If a 33 = 0, we have a i3 = 0, and the function 03 is then a linear combination of the functions 0X and 0 2 and should be omitted in the orthogonalization process, which is here simply accomplished by means of the Gaussian elimination technique developed for solving equation systems. The connection between the matrices a and a may be written in the form ... 

Gaussian elimination technique, 291 Gaussian wave function, 276 Gegen ions, 160... 

Numerical solution of this system containing l//i equations requires, for example, during the course of Gaussian elimination operations... 

Then problems (29)"(30) and (31)-(32) can be solved by the alternating direction method in just the same way as was done in Section 1 for problem (46)-(47) using Gaussian elimination along the rows as well as along the columns of the grid W/j. 

In this context, we should focus the reader s attention on the process of specifications of boundary conditions by doing Gaussian elimination along the rows for oj yj and along the columns for When p, happens to be... 

Steady-state solutions are found by iterative solution of the nonlinear residual equations R(a,P) = 0 using Newton s methods, as described elsewhere (28). Contributions to the Jacobian matrix are formed explicitly in terms of the finite element coefficients for the interface shape and the field variables. Special matrix software (31) is used for Gaussian elimination of the linear equation sets which result at each Newton iteration. This software accounts for the special "arrow structure of the Jacobian matrix and computes an LU-decomposition of the matrix so that qu2usi-Newton iteration schemes can be used for additional savings. 

The previous chapter showed how the reverse Euler method can be used to solve numerically an ordinary first-order linear differential equation. Most problems in geochemical dynamics involve systems of coupled equations describing related properties of the environment in a number of different reservoirs. In this chapter I shall show how such coupled systems may be treated. I consider first a steady-state situation that yields a system of coupled linear algebraic equations. Such a system can readily be solved by a method called Gaussian elimination and back substitution. I shall present a subroutine, GAUSS, that implements this method. 

The solution begins with a method called Gaussian elimination that converts the elements on the diagonal to 1 and the elements below the... 

Gaussian elimination has converted the original system of equations into the following system ... 

Program 0GC03 solves the steady state ocean model using Gaussian elimination and back substitution. 

GAUSS Subroutine GAUSS solves a system of simultaneous linear algebraic equations by Gaussian elimination and back substitution. The number of equations (equal to the number of unknowns) is NROW. The coefficients are in array SLEQ(NR0W,NR0W+1), where the last column is the constants. 

The steady-state problem yields a system of simultaneous linear algebraic equations that can be solved by Gaussian elimination and back substitution. I shall turn now to calculating the time evolution of this system, starting from a phosphate distribution that is not in steady state. In this calculation, assume that the phosphate concentration is initially the same in all reservoirs and equal to the value in river water, 10 I 3 mole P/m3. How do the concentrations evolve from this starting value to the steady-state values just calculated ... 

Program DGC04 solves the time-dependent ocean simulation by the reverse Euler method using Gaussian elimination and back substitution, nrow = 5 the number of equations and unknowns... 

---