It should be noted that now that we have the above circuit in a matrix format we can use (easier) a numerical technique to solve it.

Gaussian Elimination Method

Example:

in a matrix form:

We try to convert A to an upper-triangular first :

3R₁+(-1)R₁

3R₃+(-2)R₁

As you can see the third and second rows do not have x₁ anymore. We need to get ride of x₂ in the third row.

7R₃+4R₂

It can be seen that

-21 x₃ = -42 x₃ = 2

go back now to solve for the rest.

7x₂+7x₃ = 21

x₂+x₃ = 3

x₂ = 1

3x₁-x₂+2x₃=12 3x₁=9 x₁=3

Gauss-Jordan Method

What are the problems with the Gaussian elimination method when doing this elimination on a computer:

In a large set of equations, the multiplication will give very large and unwieldy numbers that may overflow the computer's registers. We may also divide by zero, if division instead of multiplication is used.

To help with the above problems:

A useful strategy to avoid dividing by zero is to rearrange the equations so as to put the coefficient of largest magnitude on the diagonal at each step. This is called pivoting. Complete pivoting may require both row and column interchanges. This is not frequently done. Partial pivoting, which places a coefficient of larger magnitude on the diagonal by row interchanges only, will guarantee a nonzero divisor if there is a solution to the set of equations. This also improves arithmetic precision.

Example:

left most nonzero (LMNZ)

interchange row 1 and row 2

First row: divide by 2 or multiply by :

make sure that these two are zero. Thus add (-2) row 1 to row 3.

now we need to multiply 2nd row by to make -2 (1)

add (5) row 2 to the third row:

multiply row 3 by 2

Now we want to make whatever above leading 1's and zero. Thus, we need to add suitable multiples of each row to make this happen.

Summary: System of equations

Matrices

Gauss-Jordan Elimination

Problems with Gauss-Jordan Elimination:

A zero element is presented on the diagonal.

The element that we divide by is called the Pivot element or Pivot.

Gauss-Jordan elimination with no pivoting is numerically unstable in the presence any round-off error, even when a zero pivot is not encountered

You must never do Gauss-Jordan elimination without Pivoting!

What is Pivoting?

Nothing more than interchanging rows(partial pivoting) or rows and columns (full pivoting), so as to put a particularly desirable element in the diagonal position from which the pivot is about to be selected.

To preserve the identity matrix that we have already built up, we will choose among elements that are both:

i) On rows below (or on) the one that is about to be normalized.

and

ii) On columns to the right (or on) the one we are about to eliminate.

Partial Pivoting is easier than full pivoting, because we don't have to keep track of the permutation of the solution vector.

Example: Partial pivoting

Use Gauss-Elimination to solve:

0.0003x₁ +3.00x₂=2.0001

1.00 x₁ +1.00x₂ =1.000

As it can be seen 0.0003 is very close to zero.

Multiply the equation by

x₁+ 10,000 x₂ =667

Which can be used to eliminate x1 from the second equation:

-999x₂=-666

x₂=2/3

(1) x₁= = =

This however, is very sensitive the number of significant figures carried in the computation.

Note that due to the fact that in (1) we are subtracting two almost-equal numbers, solution of x1 is highly dependent on the number of significant figures.

On the other hand when the equations are solved in reverse order, the row with the larger pivot element is normalized. The equations are ;

Elimination and substitution yield to

x₂ = and x₁=

This case is much less sensitive to the number of significant figure in the computation.

LU Decomposition and its applications

There are two approaches for solving systems of linear algebraic equations:

Elimination methods (Gauss-Jordan) and Iterative methods.

LU decomposition is another class of elimination method. LU decomposition requires pivoting to avoid division by zero.

The equation to be solved can be represented in matrix notation as

[A] {x}= {c} (L1)

which can be arranged to give

[A] {x}-{c}=0 (L2)

suppose we can write this as an upper triangular system with 1's on the diagonal.

This is very similar to what we do in Gauss elimination. This in matrix looks like.

[u] {x}-{D}=0 (L4)

Now, assume that we have a lower diagonal matrix L:

That has a unique property when(L4) is pre-multiplied by it, it will result in (L2).

i.e: [L] {u} {x}- {D}}=[A}{x}-{c} (L6)

if that equations holds then.

[L]{u}={A} (7)

and (rules)

[L] {D}={c} (8)

L7 is what called LU decomposition of [A].

When such thing is accomplished, solutions can be obtained very efficiently by a two-step substitution procedure using [L] and [u]

based on L 8 and L 4.

This process is shown in the following figure.

Gauss Elimination and LU Decomposition.

Gauss elimination can be used to decompose [A] into [L] and [u].

Remember we wanted to reduce the original coefficient matrix [A] to the form.

Which is in the upper triangular format.

Ex.

Multiply row 1 by f₂₁= and subtract the result from the second row to eliminate a12. Similarly, row 1 is multiplied by f₃₁= and the result is subtracted from the third row to eliminate a31. Then we f32= and subtract the result from the third row.

This will give the you original matrix [A] when multiplied by the upper triangular matrix results from forward elimination. So, Gauss elimination can respect LU decomposition of [A].

Example: Perform the LU decomposition based on the Gauss elimination.

factors used were:

Thus:

The result in [L][u] form:

The small difference is due to round off error.