Understanding Linear Equation Systems
A linear equation is an equation that does not involve the product or roots of variables, all variables have a power of one and are not independent variables of trigonometric, logarithmic or exponential functions.
Getting to Know Linear Algebra
Examples of some linear equations:
Equation (a) is a linear equation with variables x and y, with coefficients 2 and 3 which are equations of a line. Equation (b) is a linear equation with variables x1, x2 and x3, with coefficients 4, 3 and 2 which are equations of a plane. While Equation (c) is a linear equation with variables xi and coefficients ai and b with i = 1, 2, 3, ...., n.
Examples of some NOT linear equations:
Equation (a) is not a linear equation, because the variable x has a power of two. Equation (b) is not a linear equation, because there is a multiplication of two variables, namely x1x2 and x2 has a power of two, as well as Equation (c).
The solution to a linear equation is to assign values to existing variables such that the equation is true. For example, Equation 1.1, if the variable x is given a value of 0, then the variable y must have a value of 2, or give an arbitrary value to x, then the value of y can be determined later, an arbitrary value for example t, so that;
Likewise for Equation (b) in the linear equation
or by giving other values, for example
Likewise for Equation (b) in the linear equation
While equation (c) in the linear equation will be fulfilled if the variable xi where i = 1, 2, 3, ...., n. is given the appropriate value so that the linear equation is fulfilled, for example x1 = s1, x2 = s2, ...., xn = sn, then the solution to the linear equation is an ordered pair (s1, s2, s3, ...., sn). Because the solution to the equation is not only one, all solutions to the equation are collected in the solution set.
More than one (finite) linear equation and the variables are interrelated, the set of equations is called a system of linear equations or linear system.
Example 1 A linear system consisting of two equations with three variables,
One solution to the linear system is x = 1, y = 2 and z = -1, because these values satisfy both equations, while the other solution, x = 2, y = -1 and z = -1 is not a solution to the system, because these values satisfy the second equation, but not the first equation.
Example 2 A linear system consisting of two equations with two variables,
There is only one solution to the linear system, x = 4 and y = 1, because no other solutions were found.
Example 3 A linear system consisting of two equations with two variables,
The linear system is inconsistent, because if the first equation is multiplied by three, the two equations are inconsistent, so the linear system has no solution.
In general, there are three possible solutions to a system of linear equations, which can be illustrated as two line equations, namely;
Three Types of Solutions to Linear Systems
- A linear system has one solution, if the two lines intersect at one point. See Figure (a)
- A linear system has many solutions, if two lines coincide. See Figure (b)
- A linear system has no solution if the two lines are parallel. See Figure (c)
Any system of linear equations with m equations and n variables can be written as follows:
with xi are variables and aij and bj are constant coefficients with i = 1, 2, 3, ..., m and j = 1, 2, 3, ..., n.
It can also be written in matrix form, namely;
It can also be written in short form, namely;
In the process of finding a solution to the linear system, usually the +, x and = signs are removed so that a shorter matrix is formed, called an augmented matrix, namely matrix A and matrix b are combined into one matrix unit, the result is;
Homogeneous Linear System
A system is said to be linear homogeneous if the matrix b is replaced by the matrix 0, or the system has the form
This system has a trivial solution if x1 = x2 = x3 = ..... = xn = 0 and has a non-trivial solution if the system has a solution other than that.
Problems example
To find the general solution or solution set of a system of linear equations, there are several simple ways, namely substitution (as in high school). Before finding the solution of a system of linear equations, first consider the basic or elementary method that is similar to the substitution method, namely elementary row operations better known as OBE.
Solving Linear Equation Problems
In the substitution method, the steps to eliminate a variable can be done in three steps, namely;
- Multiplying an equation by a non-zero constant
- Exchange the two equations
- Add the multiplication of one equation to another equation.
Meanwhile, in the elementary row operation method, the steps to remove a constant in a certain column can be done in three steps, namely;
- Multiplying a row by a non-zero constant
- Exchange two lines
- Add multiplication from one row to another
EXAMPLE 1 - Consider the following system of linear equations;
To solve using the substitution method, do the first step, namely: multiply Equation 1.10 by 2, so that it becomes
then subtract Equation 1.11 from Equation 1.10, then Equation 1.11 becomes
And 
However, if you use the OBE method, create an enlarged matrix from the linear equation system, then do OBE with the command, reduce the second row by twice the first row, then reduce row one by twice the second row, so that when it is returned to the form of a linear equation system again it becomes: x = 1 and y = 2
1. Reduced Echelon Row
The OBE steps have been studied, as in Example 1.2.1. In this section, the form of a matrix that has row echelon and reduced row echelon properties will be shown as follows:
- If a row does not consist entirely of zeros, then the first non-zero number in the row is a one, called the leading 1.
- If there is a row consisting of all zeros, then move it to the bottom of the matrix.
- If there are two consecutive rows that are not entirely zero, the leading-1 of the lower row is located to the right of the leading-1 of the upper row.
- Each column containing leading-1 has zeros in the other rows.
If a matrix has properties 1, 2 and 3, then the matrix is called a row echelon matrix, while a matrix that has all four properties is called a reduced row echelon matrix.
EXAMPLE 2 - Matrices in row echelon form, as below;
While the matrices in reduced row echelon form are
2. Gauss Elimination Method
Gauss elimination method is a method to find the solution set of a system of linear equations using OBE, such that the matrix has a row echelon form. After the row echelon is formed, return the matrix to the form of a linear system and then do back substitution starting from the bottom.
EXAMPLE 3 - Solve the system of linear equations below using the Gaussian elimination method.
Answer:
Convert the linear system to augmented matrix form,
then do OBE, so that the matrix becomes row echelon form, like
Change back to linear system to
do the reverse substitution, namely
So the solution set is x = 1, y = 2 and z = 3
3. Gauss-Jordan Elimination Method
The Gauss-Jordan elimination method is a method for finding the solution set of a system of linear equations using OBE, such that the matrix has a reduced echelon row form. After the reduced echelon row is formed, return the matrix to the form of a linear system and find it, then do back substitution starting from the bottom.
Using Example 1.2.3, continue the OBE such that the matrix is in reduced row echelon form, that is,
return to the linear system form, namely
So the solution set is x = 1, y = 2 and z = 3
EXAMPLE 4 - Find the solution of the following homogeneous linear system.
Answer:
Convert the linear system into matrix form, then perform OBE so that it becomes a matrix in reduced echelon form, such as;
return to the linear system, so that we get
So the solution is x1 = s, x2 = -2s, x3 = s, x4 = 0
SPL Conclusion
(1) A system of linear equations (SLE) consisting of m equations and n variables can be written in the form of a matrix equation.
AX = B
where A is a real matrix of size mxn, X = (x1, ..., xn)t, and B = (b1, ..., bn)t. If B = 0 the above system is called a homogeneous SPL.
(2) The technique for obtaining an SPL solution is to change the complete matrix (A|B) to row echelon form (A'|B') and perform back substitution. Each column in A' that does not have a leading 1 produces a parameter in the relevant variable.
(3) The number of non-zero rows in a row echelon matrix A' is called the rank of A, denoted by rank(A). In this case we have a theorem that: An SPL AX = B has a solution if and only if rank(A) = rank(A|B).
(4) SPL AX = B with n variables has a single solution if and only if rank(A) = n. If rank(A) < n then SPL has infinitely many solutions with n - rank(A) parameters involved.
(5) Homogeneous SPL AX = 0 where A has size mxn and n > m always has infinitely many solutions. The number of parameters involved is n - rank(A).
(6) In homogeneous SPL AX = 0 where A is nxn, this applies: SPL has a single solution if and only if det(A) ≠ 0. If det(A) = 0 then the SPL above has infinitely many solutions.
Formula for Finding the Roots of Non-Linear Equations Using the Bisection Method
The initial idea of this method is the table method, where the area is divided into N parts. It's just that this bisection method divides the range into 2 parts, from these two parts the part that contains the root is selected and the part that does not contain the root is discarded. This is done repeatedly until the root of the equation is obtained.
Bisection Method
To use the bisection method, first determine the lower limit (a) and the upper limit (b). Then calculate the middle value:
From this x value, it is necessary to check the existence of roots. Mathematically, a range has roots of an equation if f(a) and f(b) have opposite signs or are written:
Once it is known where the root is, the lower and upper limits are updated according to the range of the part that has the root. The rules of the game are:
- If b * f(x) = (-) / negative, >> then the next intermediate value is moved to the upper limit (a).
- If b * f(x) = (+) / positive, >> then the next intermediate value is moved to the lower limit (b).
Bisection Method Algorithm
- Define the function f(x) whose roots are to be found.
- Determine the values of a and b
- Determine the tolerance e and the maximum iteration N.
- Calculate f(a) and f(b)
- If f(a).f(b) > 0 then the process is stopped because there are no roots, otherwise continue.
- Calculate the median value
- Calculate f(x)
- If f(x).f(a) < 0 then b = x and f(b) = f(x), otherwise a = x and f(a) = f(x)
- If |ba| < e or iteration > maximum iteration, then the process is stopped and the root is obtained = x, and if not, repeat step 6. (or use the Rules of the game guideline above).
Case study
The lecturer gave us several questions, including:
- QUESTION 1: f(x) = x 3 + 3x - 5, where xb =1, xa=2 and e = 0.01
- PROBLEM 2: f(x) = 2x 3 + 2x 2 - x + 2, where xb =1, xa=6 and e = 0.01
- QUESTION 3: f(x) =3 (x 3 )+ 2 (x 2 ) + 3, where xb =1, xa=2 and e = 0.01
If we calculate it manually with the help of a calculator, it will certainly take a lot of time and energy. Therefore, I try to simplify the steps by creating a formula using MS Excel, as well as scribbles next to it to verify the data in the main table.
NOTE! Here I use the lower limit (xb) and upper limit (xa) variables.
Completion
Reference:
- http://alfaruqi.lecturer.pens.ac.id/mnumerik/bab3tm.pdf
- Numerical Method Module STMIK EL Rahma Jogja By Suparyanto ST