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

 

Дана система линейных уравнений:

                  .                                             (1)  

Ортогональные преобразования системы (1) осуществляются посредством левостороннего умножения матрицы системы А и вектора правых частей b матричного уравнения (1)  на ортогональную матрицу ;         . В результате такого умножения система (1) может быть заменена на эквивалентную ей систему: .                                      С помощью определенным образом организованной последовательности таких умножений можно преобразовать исходную систему линейных уравнений к эквивалентной ей системе с верхней треугольной матрицей (прямой ход). Обратный ход осуществляется в этом случае так же, как в схемах Гаусса.

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

                               

где   – единичный вектор (),     – матрица .

Если вектор  получен с использованием элементов –го столбца матрицы  А  по формулам

;  где                      

 (0; 0; ..0; 1; 0; ...; 0)T,  (единица на -м месте);              

(0; 0; ...0; ;  ..... )T;      ,

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

Для решения системы линейных уравнений

                                             (1) 

умножим обе части уравнения на матрицу , получим эквивалентную (1) систему, матрица которой  содержит нули в первом столбце ниже главной диагонали. Затем умножаем обе части уравнения на  и так далее: . В результате умножения матричного уравнения (1) на цепочку матриц

приводим А к верхнему треугольному виду (для этого потребуется  шагов). Перед выполнением k–го шага матрица  имеет вид:

.

 

Поскольку на k–ом шаге обрабатывается только часть матрицы, а именно элементы , ,, то для экономии памяти ЭВМ можно на каждом шаге уменьшать размерность матрицы  и вектора  и строить матрицу отражения  размерности .

Для удобства вычислений используют расширенную матрицу (A÷b), где (n +1)-й столбец – это столбец свободных членов (см. п 4.1.1)

Для  k = 0   считаем        (A÷b).

Для  k = 1   строим матрицу ,  где     (1; 0; ...; 0)T,   – первый столбец матрицы  ,    производим умножение   . Затем исключаем из  1–ю строку и 1–й столбец (получаем  размерности ).

 

Для  k = 2   строим матрицу ,   где   (1; ...; 0)T,    – первый столбец матрицы. (Отметим, что размерность векторов  и  уменьшилась на единицу по сравнению с размерностью векторов  и) Производим умножение  и вновь уменьшаем размерность  на единицу, исключая из нее 1–ю строку и 1–й столбец.

 

Продолжаем процесс для   k = 3, 4, ... Для   строим матрицу   размерности , и осуществляем последнее умножение: . В итоге получим систему  с верхней треугольной матрицей. Обратный ход осуществляется так же, как в других методах. 

 

Для контроля при построении матриц вращения и отражения можно проверять выполнение равенств, справедливых для всех ортогональных матриц :  QT×Q = E   или  Q×QT = E,  где Е – единичная матрица.

 

Общая характеристика.

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