Хорошо известно, что LU-разложение (эквивалентно фазе сокращения строк при устранении Гаусса без поворота) полной матрицы NxN A требует ~ 2N³ / 3 умножений и делений. Эта операция выполняется даже при частичном повороте.
Арифметика с плавающей запятой может повлечь за собой ошибки округления на каждом шаге. «Прямой» анализ ошибок на этапах исключения не дает полезной оценки точности, поскольку в худшем случае ошибки округления могут накапливаться в геометрической прогрессии. Однако J.H. Уилкинсон показал, что "анализ обратных ошибок может дать реалистичные оценки, например, для положительно определенных или диагонально доминирующих матриц, в которых вычисленное решение путем исключения Гаусса с полным поворотом является точным решением" скромного "возмущения система, которая должна быть решена (как правило, так же, как и при частичном повороте). Размер остаточной ошибки можно затем оценить по величине возмущения и числу условий матрицы, обычно определяемому как отношение нормы A к обратному A. Если A сингулярно, это бесконечно, а если A близко к единственному, то произвольно велико. Если число условия достаточно велико, чтобы усилить размер возмущения (обычно машинный эпсилон операций с плавающей запятой) в остаточные ошибки, превышающие допустимые, мы говорим, что матрица плохо обусловлена, в противном случае мы говорим, что матрица А хорошо обусловлена.
Конечно, идея состоит в том, чтобы избежать ошибок округления арифметики с плавающей запятой, используя вместо этого точную арифметику, целочисленную или рациональную.
Но точная целочисленная арифметика обычно приводит к быстрому росту записей и, следовательно, к переполнению, даже если матрица хорошо обусловлена в вышеприведенном смысле. Различные стратегии были предложены для минимизации роста записей, начиная с Иордании (имя которого часто связано с Гауссом в версии исключения, которая вычисляет обратную матрицу вместо решения линейной системы). У. Кахан дает особенно краткий отчет . Целочисленная (или рациональная) реализация с произвольной точностью решит эту проблему.
Однако представляется сомнительным, что такие точные методы могли бы конкурировать с арифметикой с плавающей запятой на плотных матрицах. Если прямой метод, такой как исключение Гаусса, не достигает желаемой точности, что проверяется путем вычисления остатка (умножение матрицы A на вычисленное решение и вычитание его из вектора правых частей), а затем повторное решение для поправочного члена с линейная система с той же матрицей A, но правой частью, соответствующей невязке. Если фаза редукции устранения Гаусса была фактически выполнена как факторизация LU, то для решения итеративных поправок необходима только фаза обратного растворения.
В тех случаях, когда из доступной точности с плавающей запятой следует выбирать наилучшую точность, полезны прямые методы, основанные на ортогональных матрицах (см. Преобразования Household и Givens ).
Суть в том, что решением линейных систем является часто переизобретенное колесо , и вряд ли можно представить более веские аргументы в пользу повторного использования программного обеспечения. См. третий слайд этой презентации : «Как писать программы для числовой линейной алгебры - НЕ! По возможности, полагайтесь на существующие зрелые библиотеки программного обеспечения для выполнения численных вычислений линейной алгебры».