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

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

1. Решение исключением строк по методу Жордана-Гаусса, .

Матрица формируется из коэффициентов исходной СЛАУ:

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

2. Решение по правилу Крамера, .

Матрица формируется из коэффициентов исходной СЛАУ.

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

3. Матричный подход, или .

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

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

4. LU-разложение, .

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

Треугольные разложения можно выполнить уже рассмотренным ранее методом исключения по Гауссу. Затем мы делаем замену и получаем выражение: . Решив это выражение тем же Гауссом, используем полученные корни для решения и нахождения .

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

5. Разложение Холецкого .

Логика вычислений точь-в-точь повторяет предыдущий пункт, но само разложение выглядит иначе. Правило разложения существует для любой положительно определенной Эрмитовой² матрицы , но также справедливо и для вещественной, следовательно симметричной положительно определенной матрицы: .

6. Итерационный метод Якоби.

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

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

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

В матричном виде метод можно переписать как:

Методы для систем с матрицами специального вида (ленточные, треугольные, положительно-определенные). Существуют специальные методы решения уравнений с определенными свойствами. Вот несколько примеров:

1. Треугольные системы. Треугольная система – это система уравнений, в которой матрица коэффициентов является верхней или нижней треугольной. Эти системы могут быть эффективно решены с помощью прямой или обратной подстановки соответственно. Обе подстановки уже знакомы нам, как промежуточные шаги в решении исключением строк по методу вычитания строк Жордана-Гаусса и в LU-разложении.

2. Положительные определенные системы. Положительно определенная система – это система уравнений, в которой матрица коэффициентов симметрична и положительно определена, т.е. все ее угловые миноры положительны согласно критерию Сильвестра. Такие системы можно решить с помощью разложения Холецкого.

3. Разреженные системы. Разреженные системы – это системы уравнений, в которых большинство записей в матрице коэффициентов равны нулю. Ленточная матрица – это вид разреженной матрица, ненулевые записи которой ограничены диагональной полосой, включающей главную диагональ и несколько побочных диагоналей по обеим сторонам от главной. Для эффективного решения таких систем можно использовать специализированные методы, такие как итерационные методы Якоби или Гаусса-Зейделя. Кроме того, популярным решением является применение параллельных вычислений для вычитания строк по методу Жордана-Гаусса.

¹Разложение или факторизация, уместны оба варианта перевода.

²Эрмитова матрица может рассматриваться как комплексное расширение вещественных симметричных матрицу. Для Эрмитовой матрицы характерно: , где транспонированная комплексно-сопряженная к матрица. Иногда можно встретить обозначение .