Файл: Маркова Вычислит методы алгебры Практикум.doc

Из линейной алгебры известно, что решение задачи (1) существует и единственно, если детерминант матрицы А отличен от нуля, т.е. (А  невырожденная матрица, называемая также неособенной). Если определитель матрицы системы равен нулю, то система уравнений либо не имеет решения, либо имеет их бесчисленное множество.

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

Обусловленность задачи определяется числом обусловленности , где норма матрицы А, а  норма обратной матрицы. Чем больше это число, тем хуже обусловленность системы.

Число обусловленности характеризует степень зависимости относительной погрешности решения СЛАУ от погрешности исходных данных. Пусть ,,– погрешности коэффициентов матрицы, правой части и вектора решений соответственно, тогда справедливы следующие неравенства [19]:

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

При решении СЛАУ на компьютере из-за погрешностей округлений не всегда удается получить точное равенство определителя нулю, т.е. можем получить . В этом случае малые погрешности вычислений могут привести к существенным погрешностям в решении, как в случае плохо обусловленной системы.

Поясним связь величины определителя матрицы системы с понятием обусловленности на примере двумерной задачи [8].

Имеем систему из двух линейных уравнений:

Точным решением этой задачи является вектор , компоненты которого определяются координатами точки пересечения двух прямых, соответствующих уравнениям (см. рис. 1).

Рис. 1. Точное решение.

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

Рис. 2. Характер обусловленности систем.

Рис. 2 является иллюстрацией возможных вариантов. Если det А существенно отличен от нуля, то точка пересечения пунктирных прямых, смещенных относительно сплошных прямых из-за погрешностей задания А и f, сдвигается несильно. Это свидетельствует о хорошей обусловленности системы.

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

При прямые параллельны или совпадают, тогда решение задачи не существует или оно не единственно.

Условие является необходимым для плохой обусловленности системы линейных уравнений, но не достаточным. Например, система уравненийn-го порядка с диагональной матрицей с элементами не является плохо обусловленной, хотя ее определитель мал.

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

Под прямыми (точными) понимаются такие методы, которые позволяют в предположении отсутствия округлений получить точные значения неизвестных как результат выполнения конечного числа арифметических операций. Результат таких методов может быть выражен аналитической формулой.

К прямым методам относят методы исключения неизвестных (метод Гаусса и его модификации), метод квадратного корня для решения СЛАУ.

В данной группе методов рассмотрим отдельно методы решения систем на основе факторизации, в основу которых положена идея разложения искомой матрицы в виде произведения других матриц специального вида, или матричных разложений (факторизаций). Как правило, после факторизации матрицы, задача решения системы линейных алгебраических уравнений существенно упрощается.

При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми, прежде всего из-за сложности хранения и обработки матриц большой размерности.

Методы, в которых при вычислении последующего приближения решения используются предыдущие, уже известные приближенные решения, называются итерационными. Для начала вычислений итерационные методы требуют задания одного или нескольких начальных приближений, которые задаются произвольно. Окончание итераций определяется либо заданием максимального числа итераций, либо условием Здесь  i-тая компонента вектора приближенного решения, k  номер итерации, – заданная точность для поиска решения.

Условия и скорость сходимости каждого итерационного метода существенно зависят от свойств матрицы системы.

К итерационным методам решения СЛАУ относятся метод простых итераций, метод Зейделя и др.

П 3.1 Метод Гаусса решения систем линейных алгебраических уравнений

Рассмотрим метод Гаусса. Имеем систему линейных алгебраических уравнений:

(1)

или в матричном виде AX = f, (2)

где А – вещественная квадратная матрица порядка n, f – заданный и X – искомый векторы. Будем предполагать, что определитель матрицы отличен от нуля.

Метод Гаусса решения системы (1) реализуется в два этапа: прямой и обратный ход. Первый этап состоит в последовательном исключении неизвестных из системы (1). Предположим, что . Разделим первое уравнение на , получаем:

, (3)

где .

Рассмотрим теперь оставшиеся уравнения системы (1):

.(4)

Умножим (3) на и вычтем полученное уравнение из i-ого уравнения системы (4). В результате получим следующую систему уравнений:

(5)

где (6)

Тем самым осуществили первый шаг метода Гаусса и получили систему (5), в которой матрица системы имеет вид:

т.е. неизвестное содержится только в первом уравнении.

Если , то из системы (5) можно исключить неизвестное и получить систему, эквивалентную (1) с матрицей следующей структуры:

При этом первое уравнение полученной системы остается без изменения.

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

(7)

Матрица системы (7) будет иметь вид верхней треугольной матрицы с единичными элементами на главной диагонали

Получение системы (7) составляет прямой ход метода Гаусса, в котором коэффициенты уравнений преобразуются по следующему правилу [18]:

(8)

Вычисление правых частей системы (7) осуществляется по формулам

(9)

Второй этап, т.е. обратный ход, заключается в нахождении неизвестных из системы (7). Поскольку матрица системы имеет треугольный вид, можно последовательно, начиная с , найти все неизвестные. Общие формулы обратного хода имеют вид [18]