Solve Gaussian Elimination w/Pivoting: Problem Explained

[fonseh]

Homework Statement

I am asked to solve this question using pivoting technique ... so , in I , I switched the R1 and R2 so that a11 is max , in III , i switched R9 nad R10 , so that a22 is max . But , in IV , i found that the a31 become -2/9 , which is not 0 anymore , what's wrong with my working ?

Homework Equations

The Attempt at a Solution

 

[fonseh]

Can someone edit the title ? change it to gaussian elimination with pivoting . I discovered that pivoting is abit misleading

 

[BvU]

It seems to me you forgot the aim of gaussian elimination: you want to end up with the identity matrix at the left. So the operation ${-a_{41}\over \ a_{11}} ...$ doesn't really fit in that scheme. A better result (namely a 1 in position 11) is obtained with ${-a_{41}\over a_{11}/2}...$

 

[fonseh]

It seems to me you forgot the aim of gaussian elimination: you want to end up with the identity matrix at the left. So the operation ${-a_{41}\over \ a_{11}} ...$ doesn't really fit in that scheme. A better result (namely a 1 in position 11) is obtained with ${-a_{41}\over a_{11}/2}...$

why A better result (namely a 1 in position 11) is obtained with ${-a_{41}\over a_{11}/2}...$ ? why it become a11 divide by 2 ?

 

[fonseh]

It seems to me you forgot the aim of gaussian elimination: you want to end up with the identity matrix at the left. So the operation ${-a_{41}\over \ a_{11}} ...$ doesn't really fit in that scheme. A better result (namely a 1 in position 11) is obtained with ${-a_{41}\over a_{11}/2}...$

Can you explain further ?

 

[BvU]

Sure. I think I was a bit hasty: nothing wrong with a 2 in position 11.

So you are fine with your matrix II and II. I don't see what you want to exchange row 9 and 10, though.
You want $a_{22}$ to have a large value but that's only useful if the preceding $a_{21}$ is zero.

Instead, I would exchange rows 10 and 12 to get a -8 in position 22 preceded by zeroes, and a 3 in position 33 preceded by zeroes -- and without much arithmetic ; after that it's bit messier.

 

[Ray Vickson]

Homework Statement

I am asked to solve this question using pivoting technique ... so , in I , I switched the R1 and R2 so that a11 is max , in III , i switched R9 nad R10 , so that a22 is max . But , in IV , i found that the a31 become -2/9 , which is not 0 anymore , what's wrong with my working ?

Homework Equations

The Attempt at a Solution

I will not read your posted images, but I will tell you how to do Gaussian elimination (with pivoting).
(1) Bring the element with largest $|a_{i1}|$ into position (1,1) by swapping two rows if necessary.
(2) Zero out the (possibly new) elements $a_{21}, a_{31}, \ldots, a_{n1}$ by row operations.
(3) Now in the (new) rows $2, \ldots, n$, swap two rows (if necessary) to bring the largest (new) $a_{2,2}, a_{3,2}, \ldots, a_{n,2}$ into position (2,2).
(4) Zero out the (new) elements $a_{3,2}, \ldots, a_{n,2}$ by row operations, etc.

Note that once you have pivoted in row $i$ (that is, zeroed out the elements below $a_{ii}$), row $i$ is no longer involved in any more operations: no more interchanging row $i$ with some other row again, no more row operations involving the elements in column $i$, etc.

I will look further at your work if you type it out, in accordance with PF standards.

 

[fonseh]

Sure. I think I was a bit hasty: nothing wrong with a 2 in position 11.

So you are fine with your matrix II and II. I don't see what you want to exchange row 9 and 10, though.
You want $a_{22}$ to have a large value but that's only useful if the preceding $a_{21}$ is zero.

Instead, I would exchange rows 10 and 12 to get a -8 in position 22 preceded by zeroes, and a 3 in position 33 preceded by zeroes -- and without much arithmetic ; after that it's bit messier.

Actually I swap row10 and row9 to get the max a22 , which is 9 , compare to a12 , a32 and a42...

 

[fonseh]

I will not read your posted images, but I will tell you how to do Gaussian elimination (with pivoting).
(1) Bring the element with largest $|a_{i1}|$ into position (1,1) by swapping two rows if necessary.
(2) Zero out the (possibly new) elements $a_{21}, a_{31}, \ldots, a_{n1}$ by row operations.
(3) Now in the (new) rows $2, \ldots, n$, swap two rows (if necessary) to bring the largest (new) $a_{2,2}, a_{3,2}, \ldots, a_{n,2}$ into position (2,2).
(4) Zero out the (new) elements $a_{3,2}, \ldots, a_{n,2}$ by row operations, etc.

Note that once you have pivoted in row $i$ (that is, zeroed out the elements below $a_{ii}$), row $i$ is no longer involved in any more operations: no more interchanging row $i$ with some other row again, no more row operations involving the elements in column $i$, etc.

I will look further at your work if you type it out, in accordance with PF standards.

Is it a special rule ? It's not written in my book

 

[BvU]

Keep the goal of the elimination procedure in mind: you want to end up with the identity matrix on the left. Did I mention that already ?

 

[fonseh]

Keep the goal of the elimination procedure in mind: you want to end up with the identity matrix on the left. Did I mention that already ?

Yes , this is one of the method . But , i am asked to reduce it to become upper triangular matrix only

 

[fonseh]

Sure. I think I was a bit hasty: nothing wrong with a 2 in position 11.

So you are fine with your matrix II and II. I don't see what you want to exchange row 9 and 10, though.
You want $a_{22}$ to have a large value but that's only useful if the preceding $a_{21}$ is zero.

Instead, I would exchange rows 10 and 12 to get a -8 in position 22 preceded by zeroes, and a 3 in position 33 preceded by zeroes -- and without much arithmetic ; after that it's bit messier.

So , the way i change the row 9 and row 10 is completely wrong ?

 

[fonseh]

I will not read your posted images, but I will tell you how to do Gaussian elimination (with pivoting).
(1) Bring the element with largest $|a_{i1}|$ into position (1,1) by swapping two rows if necessary.
(2) Zero out the (possibly new) elements $a_{21}, a_{31}, \ldots, a_{n1}$ by row operations.
(3) Now in the (new) rows $2, \ldots, n$, swap two rows (if necessary) to bring the largest (new) $a_{2,2}, a_{3,2}, \ldots, a_{n,2}$ into position (2,2).
(4) Zero out the (new) elements $a_{3,2}, \ldots, a_{n,2}$ by row operations, etc.

Note that once you have pivoted in row $i$ (that is, zeroed out the elements below $a_{ii}$), row $i$ is no longer involved in any more operations: no more interchanging row $i$ with some other row again, no more row operations involving the elements in column $i$, etc.

I will look further at your work if you type it out, in accordance with PF standards.

Do you mean in my working , i have pivoted the row 1 (make the a11 has the largest vaule compared to a21 , a31 and a41), so i can't change ( swap the row 1 with other row) anymore ?
So , in my working , swapping R10 and R9 is wrong ?
Please refer to this one :
https://www.physicsforums.com/attachments/img_20170219_101925_dro-jpg.113417/

 

[Ray Vickson]

Do you mean in my working , i have pivoted the row 1 (make the a11 has the largest vaule compared to a21 , a31 and a41), so i can't change ( swap the row 1 with other row) anymore ?
So , in my working , swapping R10 and R9 is wrong ?
Please refer to this one :
https://www.physicsforums.com/attachments/img_20170219_101925_dro-jpg.113417/

Yes, you should not swap row 1 with anything else anymore.

There is a reason for that: you are ultimately solving a system of equations by eliminating the variables, one-by-one. First you use one of the equations to express one of the variables in terms of the others; for example, if $a_{11} \neq 0$ you can use equation 1 to express $x_1$ in terms of the variables $x_2, x_3, \ldots, x_n$. When you substitute that expression into the other equations $2, 3, \ldots, n$ you get a new system of $n-1$ equations in the $n-1$ variables $x_2, x_3, \ldots, x_n.$ So you have eliminated $x_1$ from the remainder of the problem, hence the word "elimination" in the name of the procedure. To continue that process you again use one of those $n-1$ equations to solve for one of the $n-1$ variables in terms of the other $n-2$, then substitute that expression into the other (unused) $n-2$ equations, etc., etc.

That is how Gaussian elimination works, and how it has been done for hundreds of years before anybody invented matrices. In fact, I firmly believe that you should study the matrix form only after understanding the variable-based, non-matrix version; that will make all the operations much clearer and lead you away from making the type of error you say you did.

What about pivoting? Well, all you are doing is choosing the first variable $x_1$ to eliminate from that equation whose $x_1$ coefficient is numerically the largest (or, in some versions, if not the largest, then at least above a certain threshold). If you do exact arithmetic (either using rational numbers or infinitely many decimals) you do not have to bother with pivoting. Where pivoting can become important is where you use finite word-length floating-point numbers, so you get round-off errors in your numerical computations. Then, experience has shown that it is important to keep round-off effects under control, by pivoting on numerically "large" elements and avoiding pivots on numerically small quantities. In fact, with round-off errors present, you cannot really tell if a small element like $0.1643 \times 10^{-16}$ is truly an actual small number, or is really supposed to be zero, but comes out very small just because of slight errors in the calculations. Pivoting on 0 is impossible---because of the way Gaussian elimination is supposed to work---but pivoting on a very small nonzero value could be done, but would lead to disaster and nonsensical results.