1. Решение систем линейных уравнений

1. Метод квадратных корней

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

Пусть A= – симметричная матрица, т.е. . Построим ее разложение в видеA=UU, где

, .

Перемножим матрицы, получим n(n+1)/2 уравнений относительно такого же количества переменных (элементов матрицыU):

		…
		…
		…	……………………

Из первой строки уравнений находим

, (j=2, …,n).

Из второй строки:

, (j=3, …,n).

И наконец:

.

Общий вид формул для вычисления ненулевых элементов матриц U и U:

, i=1, …, n;

(6.1)

, j=2, …,n.

Получив UU-разложение симметричной матрицы A, решение уравнения

UUx=b

сводится к решению системы

. (6.2)

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

1. Uy = b:

Следовательно, yi при i=1, 2, …, n могут быть найдены по формулам:

. (6.3)

2. Ux = y:

,

откуда и вычисляются значения неизвестных xi в обратном порядке i=n, n–1, …, 1 по формулам:

. (6.4)

Решение слау посредством uu-разложения матрицы a по формулам (6.3)–(6.5) называется методом квадратных корней или схемой Холецкого.

2. Метод прогонки решения систем с трехдиагональными матрицами коэффициентов

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

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

, (6.5)

т.е. каждое уравнение связывает три соседних неизвестных:

, i=1, 2, …, n,

. (6.6)

Выразим из первого уравнения x1 через x2:

;

из второго x2 через x3:

 

;

и т.д. Из последнего уравнения:

 

.

Таким образом, для i=1, 2, …, n:

, где (6.7)

, . (6.8)

Так как , и .

Таким образом, решение системы линейных уравнений (6.6) сводится к двум этапам:

1. Вычисление прогоночных коэффициентов Pi, Qi, i=1, 2, …, n по формулам (6.8) – прямая прогонка.

2. Вычисление неизвестных xi при i=n, n–1, …, 1 по формулам (6.7) – обратная прогонка.

Обозначим , тогда , при i=2,…,n.

Непосредственной проверкой можно убедиться, что имеет место представление A=LU, где

.

Таким образом, LU-разложение трехдиагональной матрицыAможет быть выполнено простым алгоритмом, вычисляющимR_i,P_iпри возрастающих значенияхi.

Можно вычислить и определитель матрицы A

det A= . (6.9)