2
$\begingroup$

I'm teaching students about several numeric methods, including scaled pivoting. There's a small section in this subject that I could never find a clear explanation to, either as intuition, or a more formal proof. I tried posting in math.stackexchange.com, to no avail:

In the scaled pivoting version of Gaussian elimination, you exchange rows/columns not only based on the largest element to be found, but rather the largest relative to the entries in its row.

You first calculate the scaling vector $S$ (each element in $S$ is the largest absolute value in its respective row), then start choosing the pivot elements for each iteration based on this same original $S$. I understand that $S$ isn't recalculated in each iteration because "it's not worth it" - meaning the proportions generally stay the same throughout all iterations.

From Numerical Mathematics and Computing:

Notice that the scale factors are not changed after each pivot step. Intuitively, one might think that after each step in the Gaussian algorithm, the remaining (modified) coefficients should be used to recompute the scale factors instead of using the original scale vector. Of course, this could be done, but it is generally believed that the extra computations involved in this procedure are not worthwhile in the majority of linear systems.

I'm looking for a more formal explanation of this - how can one actually see that the amount of computations involved in recalculating the remaining $S$ elements in each iteration is large compared to the increased accuracy that we will get. (Maybe some upper bound on the accuracy, compared to the number of recalculations of $S$?)

$\endgroup$
  • $\begingroup$ It's simple to determine the cost of updating S. But I suspect that a worst-case error bound will be exponentially bad, and that such examples are exponentially rare. $\endgroup$ – David Ketcheson Jun 3 '15 at 16:15
  • $\begingroup$ Shouldn't we be looking at the best case, not the worst? I mean we need an upper bound on the improvement of accuracy. Only that way can I state something like "the best improvement in accuracy is X, and obviously this isn't good enough for making so many recalculations of $S$." Bu tI haven't found any papers that offer anything like that.. it's as though it's so clear to everyone :/ $\endgroup$ – Cauthon Jun 3 '15 at 17:07
  • $\begingroup$ Your best case = my worst case. Just depends on which method is your reference. $\endgroup$ – David Ketcheson Jun 3 '15 at 18:43
  • $\begingroup$ A reference for what? $\endgroup$ – Cauthon Jun 3 '15 at 20:08
  • $\begingroup$ Never mind; I found it. $\endgroup$ – David Ketcheson Jun 4 '15 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.