21 Численные методы решения систем линейных уравнений (слау): постановка задачи.

Постановка задачи и ее качественное исследование.

Рассмотрим систему m линейных уравнений с n переменными:

(7.1)

Систему (7.1) можно записать короче в виде одного матричного уравнения AX=B,

где Х -столбец длины n, B -столбец длины m, А -матрица размерами mхn.

TEOРЕМА 1. Если ранг матрицы А совпадает с рангом расширенной матрицы (А|B), то в этом случае существует решение системы (7.1) и наоборот.

ТЕОРЕМА 2. В случае, когда количество уравнений совпадает с числом неизвестных и определитель A отличен от 0, существует единственное решение системы(7.1).

m=n и det(А)<>0 => решение (7.1) существует и единственно.

Если n>m, то решений (7.1) обычно бесконечное множество (линейное пространство размерности n-rang(A)). Если m>n, то обычно решений нет.

Далее мы ограничимся рассмотрением частного случая: m=n и det(А)<>0, т.е. случай, когда решение существует и единственно, хотя метод Гаусса, например, носит универсальный характер.

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

К прямым методам относятся, кроме метода Гаусса, метод квадратного корня для симметричных матриц (или компакт-метод для произвольных), метод Крамера. Последний метод обычно изучается в теории систем линейных уравнений в виду возможности кратко записать решение системы. Пусть D-определитель квадратной матрицы А системы линейных уравнений: D=det(A)0. Пусть D(i)-определитель матрицы, у которой на i-ом месте находится столбец В, а остальные столбцы совпадают с соответствующими столбцами матрицы А. Тогда координаты вектора решения находятся по формулам: Х(i)=D(i)/D.

22 Численные методы решения систем линейных уравнений (СЛАУ): проверка корректности постановки задачи.

23 Численные методы решения систем линейных уравнений (слау): метод Гаусса

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

Рассмотрим задачу решения системы уравнений вида:

(3.1)

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

Систему (3.1) можно записать в матрично-векторной форме А Х = В,

где А - матрица коэффициентов системы, содержащая n строк и n столбцов;

В - заданный вектор правых частей;

Х - искомый вектор.

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

Рассмотрим систему уравнений размера . Алгоритм гауссова исключения состоит из нескольких шагов. Если система записана в виде (3.1), то первый шаг состоит в исключении из последних n-1 уравнений. Это достигается вычитанием из второго уравнения первого, умноженного на , из третьего уравнения первого, умноженного на , и т.д. Этот процесс приводит к преобразованной системе уравнений:

(3.2)

где

, , i, j=2,….,n.

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

, (3.3)

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

(3.4)

При этом все диагональные коэффициенты должны быть отличны от нуля.