Решение систем линейных уравнений

Метод Гаусса
Невырожденная матрица NxN.

Метод Гаусса с частичным выбором главного элемента
Невырожденная матрица NxN. Улучшенный вариант предыдущего.

Метод Халецкого
Невырожденная матрица NxN.

Метод Крамера
Невырожденная матрица NxN.

Метод отражений
Невырожденная матрица NxN.

Метод вращений
Невырожденная матрица NxN. Точнее улучшенного Гаусса, но медленнее.

Метод вращений (другой вариант, QR-разложение)
Невырожденная матрица NxN. Точнее улучшенного Гаусса, но медленнее.

Решение набора систем уравнений с общими левыми частями
Невырожденная матрица A размером NxN, M уравнений вида A*x ^(k) = b ^(k)

Метод ортогонализации с минимизацией невязки
Матрица NxN, может быть вырождена. Норма вектора невязки Евклидова.

Метод ортогонализации для прямоугольной матрицы с минимизацией невязки, заданной квадратичной формой
Матрица MxN, ранг любой. Норма вектора невязки задается квадратичной формой.

Поиск фундаментальной системы решений с минимизацией невязки при помощи SVD-разложения для прямоугольной матрицы
Матрица MxN, ранг любой. Норма вектора невязки Евклидова. Ищется общее решение.

Введение

Чаще всего когда говорят о решении системы линейных уравнений, то имеют в виду следующую задачу: дана система из N уравнений с N неизвестными, имеющая одно и только одно решение, которое и надо найти. В матричном виде это записывается, как Ax = b, где A - матрица размером NxN, b и x - вектора с N компонентами. Вектор неизвестных умножается на матрицу коэффициентов и приравнивается в вектору правой части. А говоря о методе решения, в первую очередь думают именно о методе Гаусса.

На самом деле имеет место разнообразие как методов решения задач, так и их постановок. Цель данного введения - провести классификацию задач, связанных с линейными уравнениями, методов их решения и возникающих при этом проблем. Начнем с классификации задач. Подразумевается, что читающий знаком с основными понятиями линейной алгебры.

Классификация задач

Здесь я ограничусь только основными типами задач:

• "Классическая" постановка - число уравнений равно числу неизвестных, определитель матрицы системы не равен нолю (такая система имеет одно и только одно решение).
• Более общий вариант - число неизвестных больше числа уравнений, система строк матрицы коэффициентов линейно-независима (такая система всегда имеет решение, но не всегда одно).
• Задача без ограничений на размер матрицы системы и на её свойства. Возможно отсутствие точного решения (в таком случае можно искать наилучшее приближение к нему).
• Задача с матрицей, имеющей один из специальных видов (скажем, трехдиагональная или симметричная). Решаются специальными методами более эффективно, чем общими.
• Матрица системы разреженная, т.е. число ненулевых элементов относительно мало. Такие задачи почти всегда решают итерационными методами.
• Вместо одной системы - набор систем уравнений с общей матрицей коэффициентов и разными правыми частями. Специальные методы решают такие задачи за один прием, причем быстрее, чем общие методы, решающие системы по одной за раз.

Методы решения систем линейных уравнений

Первую группу методов составляют прямые методы, решающие системы уравнений с невырожденной квадратной матрицей коэффицентов:

• Метод Крамера, как правило, используется только в теоретических исследованиях для доказательства принципиальной разрешимости исследуемых задач. На практике его не используют из-за низкой скорости работы (трудоемкость порядка N ⁴ операций - не шутка).
• Метод Гаусса (обычный и модифицированный) - простейший метод, используемый на практике.
• Методы отражений и вращений - методы, в которых для обнуления элементов матрицы используются линейные преобразования особого вида, что позволяет уменьшить накопление погрешностей в случае плохо обусловленной системы. По скорости они не более, чем в 1.5 раза медленнее Гаусса.
• Немного в стороне стоит модификация метода вращений, которая позволяет решать наборы систем линейных уравнений с общими левыми частями. Разумеется, такое решение можно получить, решая системы из набора по очереди, но есть эффективные методы, позволяющие ускорить процесс решения за счет совпадения условий (левых частей) в поставленных задачах.

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

• Метод ортогонализации. Этот метод решает задачу с произвольной матрицей MxN, а в случае отсутствия точного решения ищет наилучшее приближение к нему. К недостаткам метода можно отнести то, что он работает в 3-4 раза медленнее метода Гаусса, а в случае плохо обусловленной матрицы погрешности в ходе работы накапливаются слишком быстро. Тем не менее, если система хорошо обусловлена или переопределена, но метод Гаусса неприменим, этот метод является неплохим выбором. Также есть обобщение этого метода на случай произвольной нормы вектора невязки.
• Метод сингулярного разложения. Метод решает задачу с произвольной матрицей MxN, а в случае отсутствия точного решения ищет наилучшее приближение к нему. Также ищется фундаментальная система решений, что является просто незаменимым при поиске собственных векторов. Этот метод является самым мощным из известных мне. Он очень устойчив, что выгодно отличает его от метода ортогонализации, хорошо справляется с вырожденными матрицами. Единственный недостаток - этот метод в 10-12 раз медленнее метода Гаусса.

Если нашли ошибку в алгоритме - сообщите!

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU