Алгебраических уравнений
Рассмотрим задачу решения системы уравнений вида:
(11)
( 
)
или 
, где 
- матрица коэффициентов системы, 
- вектор неизвестных, 
- вектор правых частей.
Известно, что система (11) имеет единственное решение, если ее матрица невырожденная (т. е. определитель матрицы отличен от нуля). В случае вырожденности матрицы система может иметь бесконечное число решений (если ранг матрицы и ранг расширенной матрицы, полученной добавлением к столбца свободных членов равны) или не иметь решений вовсе (если ранг матрицы и расширенной матрицы не совпадают)
Известно, что решение системы линейных уравнений можно выразить по формулам Крамера через отношение определителей. Но вычисление определителя не проще, чем решение исходной системы. Для решения системы порядка n необходимо вычислить (n+1) определитель, т. е. вычисление решения по формулам Крамера в (n+1) раз более трудоемко, чем решение системы другим методом, например методом Гаусса.
Метод Гаусса основан на приведении путем эквивалентных преобразований исходной системы (11) к виду с верхней треугольной матрицей.
(12)
Тогда из последнего уравнения сразу определяем
.
Подставляя его в предпоследнее уравнение, находим
и т. д.
Общие формулы имеют вид
, k=n, n-1,..., 1. (13)
При вычислениях по формулам (13) потребуется выполнить примерно 1/2n2 арифметических действий.
Приведение системы (11) к виду (12) можно выполнить, последовательно заменяя строки матрицы системы их линейными комбинациями.
Первое уравнение не меняется. Вычтем из второго уравнения системы (11) первое, умноженное на такое число, чтобы обратился в нуль коэффициент при 
. Затем таким же образом вычтем первое уравнение из третьего, четвертого и т. д. Тогда исключатся все коэффициенты первого столбца, лежащие ниже главной диагонали.
Затем при помощи второго уравнения исключим из третьего, четвертого и т. д. уравнений коэффициенты второго столбца. Последовательно продолжая этот процесс, исключим из матрицы все коэффициенты, лежащие ниже главной диагонали.
Запишем общие формулы процесса. Пусть проведено исключение коэффициентов из k-1 столбца. Тогда остались такие уравнения с ненулевыми элементами ниже главной диагонали:
(14)
Умножим k-ю строку на число
(15)
и вычтем из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам
(16)
Производя вычисления по этим формулам при всех указанных индексах, исключим элементы k-го столбца. Будем называть такое исключение циклом процесса. Выполнение всех циклов называется прямым ходом исключения.
Запишем треугольную систему, получающуюся после выполнения всех циклов. При приведении системы к треугольному виду освободятся клетки в нижней половине матрицы системы (11). Получим
(17)
Треугольная система (17) легко решается обратным ходом по формулам (13).
Исключение по формулам (15) нельзя проводить, если в ходе расчета на главной диагонали оказался нулевой элемент 
Но в первом столбце промежуточной системы (14) все элементы не могут быть нулями: это означало бы, что det A = 0. Перестановкой строк можно переместить ненулевой элемент на главную диагональ и продолжить расчет.
Для уменьшения вычислительной погрешности можно каждое повторение внешнего цикла начинать с выбора максимального по модулю элемента в k-том столбце (главного элемента) и перестановки уравнения с главным элементом так, чтобы он оказался на главной диагонали. Этот вариант называется методом Гаусса с выбором главного элемента.
В качестве одной из характеристик эффективности того или иного алгоритма используют вычислительные затраты, измеряемые количеством элементарных операций, которые необходимо выполнить для получения решения.
Для прямого хода метода Гаусса число арифметических операций, в соответствии с формулами (15), (16), равно
Для обратного хода по формулам (13) число арифметических операций равно
Общие вычислительные затраты метода Гаусса:
Таким образом, 
Выполнение прямого хода метода Гаусса позволяет также вычислить значение определителя матрицы системы.
При замене строк матрицы их линейными комбинациями значение определителя не меняется. Знак меняется при каждой перестановке строк. Для треугольной матрицы величина определителя равна произведению элементов, стоящих на главной диагонали. Поэтому определитель вычисляется по формуле:
Метод Гаусса может быть использован для нахождения обратной матрицы. Обозначим ее элементы через 
. Тогда соотношение 
можно записать так:
Видно, что если рассматривать j-й столбец обратной матрицы как вектор, то он является решением линейной системы вида (11) с матрицей и специальной правой частью (в которой на 
месте стоит единица, а на остальных нули).
Таким образом, для обращения матрицы надо решить 
систем линейных уравнений с одинаковой матрицей и разными правыми частями. Приведение матрицы к треугольной делается при этом только один раз, а правые части преобразуются по формулам (15)-(16).
Преобразование матрицы требует порядка 
операций. Действия по преобразованию правых частей систем и обратный ход метода Гаусса повторяются раз, а однократное преобразование правых частей и обратный ход требуют порядка 
операций. Следовательно, суммарные вычислительные затраты на обращение матрицы составляют: 
.
Таким образом, преобразование матрицы требуется порядка 2/3n3 операций. Для преобразования правых частей и для обратного хода требуется порядка 3/2n2 операций. Всего таких преобразований n, получаем суммарные затраты
2/3n3 + 3/2n2n = 13/6n3.
Обращение матрицы сводится к решению 
систем линейных уравнений, но требует лишь примерно втрое больше действий, чем решение одной системы уравнений. Это объясняется тем, что при решении линейной системы большая часть вычислений связана с приведением матрицы к треугольному виду, а это при обращении матрицы делается только один раз. Обратный ход и преобразование правых частей выполняются много быстрее.
Вообще говоря, метод Гаусса применим для решения любых систем линейных уравнений, так как он позволяет получить решение системы, если оно существует (включая случай, когда часть неизвестных является свободной и решений бесконечно много) и обнаружить отсутствие решения (когда система несовместна). В последнем случае после очередного k-го шага прямого хода обнаруживается ситуация, когда все элементы матрицы системы ниже k-ой строки равны нулю, а среди соответствующих компонент вектора 
есть ненулевые значения.
[О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах]
[Home|Кафедра|ПетрГУ]2.3. Итерационные методы. Общая схема
Рассмотрим общее описание метода итераций для системы линейных алгебраических уравнений с квадратной матрицей В этом случае по некоторому алгоритму, начиная с выбранного вектора 
строится последовательность векторов 
.
При этом вектор 
выражается через известные предыдущие вектора 
Если при вычислении 
используется только вектор 
, то итерационный метод называется одношаговым (или двухслойным) методом.
Общий вид линейного одношагового метода
(18)
Важную роль играет запись итерационных методов в единой (канонической) форме.
Она имеет вид:
, (19)
где A - матрица исходной системы уравнений (1),
- некоторая последовательность невырожденных матриц,
- итерационные параметры, 
Связь между записью итерационного метода в виде (18) и в виде (19) выражается формулами:
Выбирая различным образом и 
, можно получить разные варианты итерационных методов, которые различаются скоростью сходимости, сложностью реализации.
Если 
- единичная матрица, то метод называют явным: находится по явной формуле
(20)
В общем случае, при 
, метод называют неявным итерационным методом: для определения надо решать систему уравнений
(21)
Естественно требовать, чтобы объем вычислений для решения системы (21) был меньше, чем объем вычислений для исходной системы (1).
Точность метода характеризуется величиной погрешности 
, т.е. разностью между решением уравнения (19) и точным решением 
исходной системы линейных алгебраических уравнений. Подстановка 
в (19) приводит к системе уравнений для погрешности:
(22)
Говорят, что итерационный метод сходится, если 
при 
.
В случае, когда 
и 
( и 
- соответственно) не зависят от номера итерации k, итерационный метод называется стационарным (иначе - нестационарным).
Критерий сходимости стационарного линейного одношагового итерационного метода
(23)
формулируется в теореме 1.
Теореме 1. Метод (23) сходится для любого начального приближения тогда и только тогда, когда все собственные числа матрицы перехода S по модулю меньше единицы.
Доказательство.
Необходимость. Пусть некоторое собственное число 
матрицы перехода по модулю больше единицы. Возьмем в качестве начального приближения вектор 
, где s - собственный вектор, соответствующий собственному числу 
.
Тогда 
,
при .
Если 
, то 
при .
Достаточность. Пусть матрица S имеет n линейно независимых собственных векторов (т.е. является матрицей простой структуры): 
, соответствующих собственным числам 
, каждое из которых по модулю меньше единицы. Разложим погрешность начального приближения 
по базису из собственных векторов.
Тогда
где 
(спектральный радиус). Так как 
, то 
при , т.е. метод сходится.
Замечание. В общем случае, когда система собственных векторов матрицы S не является полной, доказательство достаточности проводится с использованием жордановой формы матрицы.
В качестве следствия из теоремы 1 можно получить легко проверяемые на практике достаточные условия. Норма матрицы S, согласованная с векторной нормой удовлетворяет неравенству 
для любого вектора x. Так как для максимального по модулю собственного числа матрицы S и соответствующего собственного вектора y выполняется равенство 
, то для любой согласованной нормы матрицы 
.
Примерами легко вычисляемых согласованных норм являются:
, 
.
Таким образом, выполнение любого из неравенств 
, 
достаточно для сходимости итерационного метода.
Достаточные условия сходимости для итерационного метода, записанного в канонической форме, содержатся в следующей теореме, которая приводится без доказательства.
Теорема 2. Пусть A - симметричная положительная матрица и выполнено условие
(24)
Тогда метод итераций
(25)
сходится.
Напомним, что матрица положительная, если для любого ненулевого вектора x (Ax,x)>0.
Неравенство (24) означает, что для любого ненулевого вектора x матрица 
положительна.
не стремится к нулю при 
.
[О комплексе|Теория|Практикум|Справочник по MathCAD'у|Об авторах]
[Home|Кафедра|ПетрГУ]
Варианты итерационных методов