ltwood (ltwood) wrote in numpro,
ltwood
ltwood
numpro

Простой оценщик числа обусловленности

Все те, кто занимается численными задачами, знают о важности оценки числа обусловленности CD при решении систем линейных уравнений. В то же время, линейные системы решает множество людей, если и слышавших про число обусловленности, то не имеющих возможности его оценить. Этому есть множество причин:
1. Качественные библиотеки численных алгоритмов для многих все еще остаются недоступными.
2. Алгоритм Гаусса описан во многих источниках, пренебрегающих описанием алгоритмов оценки CD.
3. Написать программу для качественного алгоритма оценки CD все же сложнее, чем реализовать сам метод Гаусса.
4. Многие продолжают верить, что если все ведущие элементы в методе Гаусса оказались существенно ненулевыми, то получаемое решение устойчиво по отношению в возмущениям системы.
Поэтому алгоритм, позволяющий легко оценивать CD, может оказаться полезным, даже если получаемая оценка будет не очень точной. Ниже я описываю совсем простой алгоритм оценки CD. Этот алгоритм принадлежит фольклору вычислителей, но я не знаю ссылки на источник, в котором он был впервые описан.

В первую очередь скажу то самое главное, что нужно знать про CD: Число CD можно рассматривать как коэффициент чувствительности решения к ошибкам в коэффициентах системы и ее правых частях. Если имеется погрешность d, то в решении будут ошибки порядка CD*d. Величина log10(CD) дает число десятичных знаков, которые теряются при решении системы. Если log10(CD) превосходит значение 15 для арифметики double (или 6 для арифметики float), то в полученном решении нет ни одной верной цифры.

Предлагается следующий алгоритм оценки CD:
1. Для заданной матрицы A формируем вектор b правых частей таким образом, чтобы полученная система имела решение (1, 1, ..., 1) т.е. вектор b полагаем равным сумме столбцов матрицы A.
2. Решаем полученную систему и получаем вектор решения x.
3. Находим величину m = max |x[j] - 1.0|.
4. В качестве оценки числа обусловленности выбираем число CDE = 10*(x/e) + 1, где e — машинное эпсилон для используемой арифметики (т.е. DBL_EPSILON для арифметики double и FLT_EPSILON для арифметики float).

Коэффициенты в формуле CDE = 10*(...)+1 являются эмпирическими. Полученная оценка CDE числа обусловленности обычно отличается от истинного значения CD не более чем в 5 или (очень редко) 10 раз, чего обычно достаточно для практики.
  • Post a new comment

    Error

    Comments allowed for members only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 7 comments