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$?)