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

Определение 1. Говорят, что норма матрицы  согласована с нормой вектора  , если для любого вектора  выполняется неравенство

(4.5)

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

(4.6)

Такая норма матрицы называется нормой, подчиненной норме вектора.
Справедливы следующие утверждения (см. [5, c. 85–86]):
1) если норма вектора 
,
то подчиненная ей норма матрицы есть

2) если норма вектора 

то подчиненная ей норма матрицы есть

3) если норма вектора 

то подчиненная ей норма матрицы есть

где  – наибольшее собственное значение матрицы  .
Определение 2. Число λ называется собственным значением матрицы  , если существует такой ненулевой вектор  , что справедливо

(4.7)

Из (4.7) следует, что

С другой стороны, по определению нормы матрицы имеем

Тогда

(4.8)

и неравенство (4.8) означает, что любая норма матрицы больше либо равна модулю произвольного своего собственного значения, в том числе

Определение 3. Число

(4.9)

называется числом обусловленности матрицы   (см. [4, с. 127]).
При любой норме матрицы  числоμ , и чем оно больше, тем хуже обусловленность системы (4.1). Как следует из [4, с. 127], если  , то это уже означает плохую обусловленность.
Заметим, что вычисление μ связано с нахождением обратной матрицы, а это не всегда легко сделать.
В дальнейшем будем предполагать, что задача решения системы (4.1) корректно поставлена, что означает выполнение следующих двух условий:
1) решение системы (4.1) существует и единственно в  ;
2) существует непрерывная зависимость решения  от входных данных  и  , т.е. малые изменения во входных данных приводят к малому изменению в решении.
Корректность постановки задачи для систем линейных алгебраических уравнений

выполняется, если:
1) число уравнений системы равно числу неизвестных, т.е.  – квадратная матрица порядка  ,  –  -мерные векторы;
2) 
3) число обусловленности  матрицы  удовлетворяет неравенству

Алгебраической основой методов исключения Гаусса, квадратного корня и схемы Халецкого является LU-теорема:
Пусть дана невырожденная квадратная матрица  порядка  и  – главный минор матрицы, составленный из первых  строк и столбцов.
Предположим, что  для  Тогда существуют единственная нижняя треугольная матрица  , где  , и единственная верхняя треугольная матрица  , такие, что  Более того, 

Пусть дана квадратная матрица A размерности n*n и столбец свободных членов b. Требуется найти решение системы в виде:

(1)
Представим матрицу в виде: , где



Элементы матриц L и U вычисляются по формулам:
l_i1= a_i1
l_ij= a_ij- при 1≤j≤i (2)
остальные l_ij=0

u_1j=

u_ij= - ) при 1Формулы (2) и (3) составляют прямой ход схемы Халецкого

, где
, обозначим
Тогда – исходное уравнение (1), которое можно разбить на систему (4):


Рассмотрим

Отсюда получаем вычислительные формулы для (5):

Решим СЛАУ:

Получаем вычислительные формулы (6):

Далее получим формулу для вычисления определителя матрицы
det A= det (LU)= det(L)*det(U)= det(L)*1= l₁₁*l₂₂*l₃₃*…*l_nn
Теперь осталось вычислить обратную матрицу A^-1. Рассмотрим на примере
По определению матрица называется обратной, если A*A^-1 =E, где E- это единичная матрица. Обозначим X=A^-1



(*)

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