коэффициент масштабирования при исключении gaussion

Question

ALGORITHM ForwardElimination (A [1..n, 1..n], b [1..n]) // Применяет гауссово исключение к матрице A коэффициентов системы, // дополнено с вектором b значений правой стороны системы // Вход: матрица A [1..n, 1..n] и вектор-столбец b [1..n] // Выход: эквивалентный верхнетреугольный матрица вместо A с // соответствующие значения правой части в столбце (n + 1) st. для i ← 1 - n do A [i, n + 1] ← b [i] // дополняет матрица для i ← 1 до n - 1 do для j ← i + 1 to n do для k ← i to n + 1 do A [j, k] ← A [j, k] - A [i, k] * A [j, i ]/A [i, i]

Существует два важных замечания относительно этого псевдокода. Во-первых, это не всегда верно: если А [I, I] = 0, мы не можем делить на него и, следовательно, не может использовать ю строку в качестве оси поворота для г-й итерации алгоритма . В этом случае мы должны воспользоваться первой элементарной операцией и обменивать i-ю строку с некоторой строкой ниже нее , которая имеет ненулевой коэффициент в i-м столбце. (Если система имеет единственное решение , что является нормальным случаем для систем под , такая строка должна существовать.) Так как мы должны подготовить для возможности обмена строк, мы можем позаботиться о еще потенциальная трудность: вероятность того, что A [i, i] настолько мала и, следовательно, масштабный коэффициент A [j, i]/A [i, i] настолько велик, что новое значение A [j, k] может стать искаженное ошибкой округления, вызвало вычитанием двух чисел сильно разных величин.3 До избегайте этой проблемы, мы всегда можем найти строку с наибольшим абсолютным значением коэффициента в i-м столбце, обменивать его с i-й строкой, а затем использовать новый A [i, i] как с итерацией стержень. Эта модификация, называется частичными поворотным, гарантирует, что величины коэффициента масштабирования никогда не будет превышать 1.

Моими вопросов по данному тексту являются

1. Что автор подразумевает под "вероятностью того, что A [ i, i] настолько мала и, следовательно, масштабный коэффициент A [j, i]/A [i, i] настолько велик »? Попросите объяснить здесь простой пример.

2. В дополнение к вышеуказанным вопросам то, что автор означает «новое значение A [j, k], может быть искажено погрешностью округления, вызванной вычитанием двух чисел с очень разными величинами»?

Answer 1

Итак, я считаю, что комментарии тезисов полезны только тогда, когда вы хотите запрограммировать его. Проблема с сетью - это способ представления чисел.

Предположим, что A [i, i] reaaally маленький, и что A [j, i]/A [i, i] составляет около 10^12. Само по себе это не проблема, но когда вы хотите манипулировать этим числом, вы не будете манипулировать точно 10^12, а приблизиться к этому числу. В большинстве случаев норма, используемая для представления большого числа, - IEEE 754 (в случае, если вы хотите углубленно).

Главное помнить, что это не точное число, означающее, что 10^12 и 10^12 -1 имеют одинаковое представление. (Вы можете попробовать there, если хотите)

поэтому, если у нас есть большие значения, мы не можем выполнить правильную операцию, потому что мы фактически не будем работать с правильным номером. Я попытался сделать небольшую программу, чтобы проиллюстрировать эти различия вы можете получить:

int main() 
{ 
    float bigOne = 100000000000000; 
    float smallerOne = 99990000000000; 
    float expectedSubstraction = 10000000000; 
    float divisionFactor = 1000000; 
    cout << (bigOne-smallerOne)/divisionFactor << endl; 
    cout<< "expected : " << expectedSubstraction/divisionFactor << endl; 
    return 0; 
} 

Try it there

. Теперь это не большая разница, но она может перерасти из-под контроля после нескольких итераций ...

Таким образом, мы можем иметь разницу между вычисленнойA [я, к] * A [J, я]/а [я, я] и реальныма [I, K] * A [J, I]/а [I, I]

Кроме того, если а [J, K ] довольно мало, и A [i, k] * A [j, i]/A [i, i] по-прежнему очень большой, мы не получим точный val ue, так как мы будем выполнять операцию с точным числом и представлением большого числа. Это не обязательно будет большой разницей, но это может привести к абсурду, если ошибка снежков на нескольких итерациях.

Надеюсь, что помогло!

Answer 2

Чтобы увидеть, что автор имеет в виду, рассмотрим простейший пример исключения Гаусса, когда мы имеем только два линейных уравнений:

ax+by=c 
dx+ey=f 

Я заменил A [I, J] с буквами а, б, д, e и b [k] с буквами c и f, чтобы упростить чтение формул.

Для того чтобы исключить у из первого уравнения, перепишем второе уравнение как

y=(f-dx)/e   /* (1) */ 

выполнить замену, чтобы вычислить x

x=(ce-bf)/(ae-bd) /* (2) */ 

, а затем вернуться, чтобы вычислить y от x.

Теперь рассмотрим, что происходит в (1) выше, когда e в исходном уравнении очень мало, скажем, 10 ^-320. Масштабный коэффициент (то есть число, в котором вы умножаете f-dx для получения y) составляет 1/e или 10 . Умножение на число, в котором большие риски переполняют экспоненту в представлении числа с плавающей запятой. Это то, что автор имел в виду по отрывку, который вы цитируете в первой части вашего вопроса.

Для части два вашего вопроса рассмотрим формулу (2) выше. Когда ce очень мало по сравнению с bf (или bf очень мало по сравнению с ce), в результате вычитания преобладает большее число из-за того, как представлены числа с плавающей запятой.По существу, когда одно число на несколько порядков меньше другого, результат сложения или вычитания идентичен большему числу. Автор хотел упомянуть, что это легко может произойти в процессе вычисления решения с использованием гауссовой элиминации.