3.1. Краткие сведения из теории

3.1.1. Обзор методов решения систем решения линейных алгебраических уравнений

С точки зрения обычной математики система линейных алгебраических уравнений (далее – линейных уравнений) всегда является невырожденной (решение существует и оно единственное) или вырожденной (вообще не имеет решения или имеет бесчисленное множество решений). С точки зрения практических вычислений могут существовать почти вырожденные системы, при решении которых получаются недостоверные значения неизвестных (плохо обусловленные системы). Для таких систем найти численное решение трудно, а точность его весьма сомнительна.

Методы решения систем линейных уравнений делятся на две группы: прямые и итерационные. Прямые методы используют конечные формулы для вычисления неизвестных и дают решение после выполнения заранее известного числа операций (метод Гаусса). Итерационные методы – это методы последовательных приближений, позволяющие получать корни системы с заданной точностью путём сходящихся бесконечных процессов (метод Гаусса-Зейделя).

Прямые методы имеют характерные недостатки, что не всегда делает возможным их применение:

• они не учитывают структуру матрицы коэффициентов, что заставляет занимать значительное место в памяти машины нулевыми элементами;

• в процессе вычислений накапливается вычислительная погрешность, что опасно для больших систем, а также для плохо обусловленных систем.

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

Отметим, что метод Гаусса используется не только для решения систем линейных уравнений, но и для вычисления обратной матрицы и определителя прямой матрицы.

3.1.2. Метод Гаусса

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

(3.1)

Необходимо решить систему (3.1), т.е. найти значение неизвестных .

Метод основан на приведении данной системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается из всех последующих уравнений системы. Затем с помощью второго уравнения исключается из третьего и всех последующих уравнений. Этот процесс называется прямым ходом Гаусса. Он продолжается до тех пор, пока в левой части последнего ( -ого) уравнения не останется лишь один член с неизвестным . Необходимо помнить, что к такому виду приводится лишь невырожденная матрица.

Обратный ход метода состоит в последовательном вычислении искомых неизвестных: решая последнее уравнение, находят единственное неизвестное . Далее, используя найденное значение , из предыдущего уравнения вычисляют и т.д. последним вычисляют из первого уравнения.

Данный метод предлагаем дополнять алгоритмом поиска ненулевого ведущего элемента или поиска главного элемента.