Решение СЛАУ с помощью LU – разложения

Если матрица исходной системы уравнений

(5.2)

разложена на произведение двух треугольных матриц или , значит можно записать эквивалентное уравнение

Введем в рассмотрение матрицу-столбец промежуточных неизвестных:

тогда решение системы с исходной матрицей (5.2) сводится к решению системы двух матричных уравнений:

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

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

, ,

, ;

. (5.3)

Решаем систему , получим:

; (5.4)

. (5.5)

Отметим, что выполнение расчетов по формулам (5.3,5.5) представляет собой преобразование системы (5.2) к треугольной системе (5.4), которая полностью совпадает с результатом прямого хода метода Гаусса. Таким образом, решение линейных систем с помощью LU-разложения является просто другой реализацией метода Гаусса. Схему LU-разложения еще называют схемой Холецкого (1875-1918 – французский математик-геодезист). Однако в применяемых математических пакетах, таких как MathCad, схемой Холецкого называют метод решения систем с симметричной матрицей (метод квадратного корня).

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

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

Итерационные методы

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

Рассмотрим метод простой итерации. Пусть требуется решить систему

. (5.6)

Прежде чем применять метод итерации систему (5.6) следует привести к равносильной системе вида

. (5.7)

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

Пусть нам известно некоторое начальное приближение ( о его выборе скажем позже). Подставим в правую часть равенства (5.7), получим следующее приближение:

затем поступим с аналогично, получим и так далее:

;

. (5.8)

Таким образом строится последовательность матриц -столбцов .

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

Можно доказать, что если последовательность имеет предел , то этот предел является решением системы (5.7), а следовательно, и (5.6). Если формально в равенстве (5.8) перейти к пределу при , то т. к. , то равенство (5.8) примет вид , т. е. предел является решением системы (5.7). Выясним условия, при которых последовательность имеет предел.

Рассмотрим последовательность решений системы (5.7)

Получается в скобках сумма конечного числа матриц:

при получим матричный ряд

. (5.9)

Лемма. Для того, чтобы необходимо и достаточно, чтобы все собственные числа матрицы были бы по модулю меньше единицы: .

Допустим, что все собственные числа матрицы различны, тогда существует невырожденная матрица , такая, что , где – диагональная матрица

тогда матрица может быть преобразована к диагональному виду:

Возведем в степень обе части по правилам действия с матрицами

;

Здесь

Для того, чтобы , необходимо и достаточно, чтобы , а для этого необходимо и достаточно, чтобы .

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

Теорема.Для того, чтобы , достаточно, чтобы какая-нибудь из норм матрицы была меньше единицы.

На основании свойств нормы можно записать . Т. к. , это и означает, что .

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

Теорема.Для того, чтобы ряд сходился, необходимо и достаточно, чтобы , при этом сумма ряда равна .

Необходимость условия очевидна. Докажем достаточность. Пусть , следовательно, , значит, нет ни одного собственного числа, равного единице, тогда и существует обратная матрица . Обозначим сумму сходящегося ряда

Рассмотрим выражение:

тогда

, .

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

Необходимость. Пусть , тогда является решением системы (5.7), следовательно,

, .

Вычтем из первого равенства второе, получим:

К разности можно применить аналогичные рассуждения:

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

Достаточность. Пусть . Перейдем в равенстве

к пределу при , тогда , , следовательно , а это решение системы (5.7), а значит и системы (5.6).

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

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

– апостериорная;

– априорная.

Априорная оценка, как правило, грубее апостериорной.

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

относительно : , т. к. , .

Апостериорной оценкой удобно пользоваться непосредственно в процессе вычислений и останавливать этот процесс, как только выполнится неравенство .

Отметим, что неравенство будет гарантией того, что только, если .

Обычно за принимают вектор – матрицу-столбец свободных членов системы (5.7), если неизвестно какое-нибудь близкое решение. Если , то априорная оценка имеет вид:

– при любом .

Дополнительно отметим, что процесс итераций сходится, если все элементы , где – число неизвестных.

Метод Якоби

Чтобы решить систему

(5.10)

методом простой итерации, необходимо привести ее к виду

. (5.11)

После того, как мы выяснили, каким условиям должна удовлетворять матрица для сходимости метода, следует выяснить как привести систему (5.10) к виду (5.11), чтобы это условие сходимости выполнялось.

Представим матрицу системы (5.10) в виде:

где – диагональная, и – левая и правая строго треугольные (т.е. с нулевой диагональю) матрицы. Тогда система (5.10) может быть записана в виде:

Если на диагонали исходной матрицы нет нулей, то эквивалентной (5.10) задачей вида (5.11) будет

, (5.12)

т. е.

, .

Метод простых итераций, основанный на таком приведении системы (5.10) к виду (5.11), называется метод Якоби . Тогда последовательность приближений по методу простой итерации имеет вид:

Здесь – обратная к матрице – диагональная матрица

, ,

поэтому представление системы в виде (5.12) равнозначно выражению диагональных неизвестных:

;

Теперь для записи итерационного процесса в развернутом виде следует расставить номера итераций:

;

; (5.13)

Достаточный признак сходимости метода Якоби к решению системы (5.10) сформулирован в следующей теореме.

Теорема. В случае диагонального преобладания в матрице системы (5.10) метод Якоби (5.13) сходится.

Диагональное преобладание означает, что: .

Тогда в матрице

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

Метод Зейделя

Под методом Зейделя понимают такое видоизменение метода простых итераций (5.12) решения систем линейных уравнений, приведенных к виду (5.11), при котором при подсчете i-ой компоненты приближения к искомому используются уже найденные на этом шаге новые значения первых компонент, т. е. приближения к решению системы (5.11) по методу Зейделя определяются выражениями: