Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm told that if the matrix is symmetric positive definitive (as the one below is), pivoting is not required when using Gaussian elimination.

$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}$

So I've been googling around trying to actually get a definition of what pivoting is and I can't find a straightforward answer. I've read that it means to do a row swap. I've read that it means to "make an element above or below leading one into a zero."

I guess what I've always just done is: make $a_{1,1} = 1$, make zeros below. Make $a_{2,2} = 1$, make zeros below. etc.

share|improve this question
    
interestingly, I'm in that class right now –  user2079802 Feb 27 at 4:44
    
But it's dated 2011... –  Nameless Feb 27 at 4:56
    
and the lecture slides haven't changed a bit lol –  user2079802 Feb 27 at 5:04

3 Answers 3

up vote 2 down vote accepted

Think of it as follows.
If you have the following equations $$2x+2y=6\\-x+y=-1$$ The solution is $$x=2\\y=1$$ We get it by(dividing the first equation by 2, add to the second, divide the result by 2, ..)

Now the first two equations could be represented as a matrix $$\pmatrix{2&2&6\\-1&1&-1}$$ and the second two equations could be represented as a matrix also $$\pmatrix{1&0&2\\0&1&1}$$ Pivoting means to take the first matrix to the second matrix using row operations as you do with equations.
For your matrix notice the following
$$A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}\implies \begin{bmatrix} -1 & 2 & -1 \\ 2 & -1 & 0\\ 0 & -1 & 2 \end{bmatrix} \\ \implies \begin{bmatrix} 1 & -2 & 1 \\ 2 & -1 & 0\\ 0 & -1 & 2 \end{bmatrix} \implies \begin{bmatrix} 1 & -2 & 1 \\ 0 & 3 & -2\\ 0 & -1 & 2 \end{bmatrix}$$

share|improve this answer
    
So how could you do Gaussian elimination on my original matrix without using those types of row operations? –  user2079802 Feb 27 at 6:37
    
I have added some new@user2079802 –  Semsem Feb 27 at 6:45

For an invertible matrix $A,$ gaussian elimination is equivalent to constructing an $LU$ factorization of $A$ where $L$ is unit lower triangular and $U$ is upper triangular. There are many algorithms for doing this but if you aren't careful you can get runaway cancellation errors or swamping. By partial pivoting you can keep a lid of sorts on some runaway errors by making sure that at each step of the algorithm you re-order the rows/columns so that any scaling that is done of subsequent rows/columns is by a number of absolute value less than 1. This is not the same idea as reducing a matrix to row echelon form as that is already implicit in performing the $LU$ factorization. Rather partial pivoting refers to a numerical technique in the implementation of an $LU$ (or many other) factorization. This is unnecessary and indeed numerically dubious for a symmetric positive definite matrix since the cholesky factorization can be employed instead.

Pivoting is a more general technique than partial pivoting but the underlying concerns are the same. I would suggest going over your notes or googling the relevant terms and talking with your instructor for more clarification.

share|improve this answer

Pivoting in the word sense means turning or rotating. In the Gauß algorithm it means rotating the rows so that they have a numerically more favorable make-up.

The straight-forward implementation of the LU decomposition has no pivoting. However, it may encounter zeros or near zeros on the diagonal while entries below in the same column have an appreciable size.

So the natural idea is to pick the largest of the remaining entries, call it the pivot (turning axis) and use that row as the basis for the elimination step. To keep constructing the echelon form, rows are swapped or rotated (most efficiently using a row index array), adding permutation steps to the elementary row transformations.

The result of the pivoted Gauß algorithm is a PLU decomposition, where P is a permutation matrix that has in each row and column exactly one entry 1, all other 0.


As to the original matrix, the discretization of minus the second derivative is indeed positive definite. To show that requires an eigenvalue analysis.

For positive definite matrices $A$, the naked LU decomposition without pivoting works, since the diagonal entries that are encountered are quotients of main diagonal minors, and all of them are positive. Symmetry results in $U=D\,L^\top$, so that the $A=LDL^\top$ can be cheaply obtained. If wanted, the square root of $D$ may be distributed to the factors to obtain the Cholesky decomposition.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.