Решение системы линейных алгебраических уравнений с помощью LU-разложения
LU-метод основан на том, что если главные миноры матрицы А отличны от нуля, тогда матрицу А можно представить, причем единственным образом, в виде произведения
А=LU,
где L–нижняя треугольная матрица с ненулевыми диагональными элементами и U–верхняя треугольная матрица с единичной диагональю.
Рассмотрим СЛАУ Ax=f.
A=LU
где
или
,
Окончательно запишем
Полагая 
получим следующие рекуррентные формулы для вычисления элементов матрицы L и U
(11)
Если найдены матрицы L и U, то решение исходной системы A=LU сводится к последовательному решению двух систем уравнений с треугольными матрицами
LU – метод позволяет вычислить определитель матрицы А
.
В среде MathLab разложение матрицы А на треугольные матрицы L и U осуществляется с помощью команды
[L,U,P]=lu(A),
которая кроме нижней треугольной матрицы L и верхней треугольной матрицы U порождает и матрицу перестановок Р.
Метод простой итерации решения систем линейных алгебраических уравнений
Исходную систему (1) преобразуем к виду:
(12)
где 
, i=1,2,...,n; 
, aii¹0.
Перепишем систему (12) в виде одного матричного уравнения:
(13)
Первая сумма равна нулю, если верхний предел суммирования меньше нижнего.
Так (12) при i=1 имеет вид
Итерационный процесс (12) начинается с начальных значений 
, которые в общем случае задаются произвольно, но предпочтительнее, если за взять свободные члены исходной системы, т.е 
. Подставляя начальные значения в правую часть выражения (12) и вычисляя полученное выражение находим первое приближение:
.
Подставляя приближение 
в правую часть системы (12) получим:
.
Продолжая этот процесс получим последовательность 
, 
, 
,…, 
,… приближений вычисляемых по формуле:
, где 
` (14)
В развернутой форме записи формула (14) выглядит так:
Условие окончания счета:
,
где i= 
.
Теорема
Если какая-либо норма матрицы меньше единицы: 
, то уравнение (13) имеет единственное решение , к которому стремится последовательность итераций (14) при любом выборе начального приближения .
Число итераций для достижения заданной точности определяется из неравенства:
. (15)
Неравенство (15) обычно дает завышенную оценку числа итераций k.
Условие, позволяющее принять приближение 
в качестве решения с точностью , представляется в следующей форме:
. (16)
Метод вращения
Метод вращения, как и метод Гаусса состоит из прямого и обратного ходов.
Прямой ход метода. Исключаем неизвестное 
из всех уравнений, кроме первого. Для исключения из 2-го уравнения вычисляют числа
, 
,
где a и b такие, что 
, 
.
Первое уравнение системы заменяем линейной комбинацией первого и второго уравнений с коэффициентами 
и 
,а второе уравнение такой же комбинацией с 
и - 
. В результате получим систему
. (17)
Здесь
где j= 
.
Преобразование системы (1) к системе (17) эквивалентно умножению матрицы A и вектора B слева на матрицу С12 вида
.
Аналогично для исключения 
из третьего уравнения вычисляем числа
и 
,
такие, что 
.
Затем первое уравнение системы (17) заменяем линейной комбинацией первого и третьего уравнений с коэффициентами 
, 
, а третье уравнение системы (17) тоже заменяем линейной комбинацией с ,– . Это преобразование эквивалентно умножению слева на матрицу
.
Исключая неизвестное х1 из всех последующих уравнений получим систему
А(1) х=В,
где матрица A(1)=C1m…C13C12A, , а вектор правых частей 
.
Здесь и далее через Сkj обозначена матрица элементарного преобразования, отличающаяся от единичной матрицы Е только четырьмя элементами. Действие матрицы Сkj на вектор x эквивалентно повороту вектора x вокруг оси перпендикулярной плоскости 
на угол 
такой, что
, 
.
Операцию умножения на матрицу Сkj называют плоским вращением или преобразованием Гивенса.
Первый этап состоит из m-1 шагов, в результате чего получается система
(18)
В матричной форме А(1) х=В(1).
На втором этапе, состоящем из m-2 шагов, из уравнений системы (2.7) с номерами 3,4,…,m исключают неизвестное х2. B результате получим систему
В матричной форме получаем 
, где 
, 
.
После завершения (m-1)-го шага придем к системе с верхней треугольной матрицей вида
,
где 
.
Обратный ход метода вращения проводится точно также как и для метода Гаусса.
Метод отражения
Метод отражения основан на преобразованиях Хаусхолдера. Алгоритм Хаусхолдера приводит n´n симметричную матрицу к трехдиагональной форме, за n–2 ортогональных преобразований. Каждое преобразование обнуляет необходимые части выбранного столбца и соответствующей строки. В этом методе QR-разложение матрицы A системы уравнений Ax = b
производится при помощи матриц отражения, которые имеют вид
U = E 2wwT .
Здесь E – единичная матрица; w – n-мерный вектор единичной длины,
(w,w) = 1, а wwT – квадратная симметричная матрица:
.
Следовательно, и матрица отражения U является симметричной, U =UT. Более того, матрица U ортогональна, то есть UT =U 1 , действительно:
UUT = (E 2wwT )(E 2wwT )T = E 2wwT 2wwT + 4wwT wwT = E ,
поскольку wTw = (w,w) = 1.
Так как U симметрична и ортогональна, U2 =UUT = E , собственные числа матрицы U удовлетворяют условию 
, то есть 
, причем отрицательному собственному значению = 1 соответствует собственный вектор w:
Uw = w = Ew 2wwT w = w 2w = w = (1)w = 1.
Положительному собственному значению = 1 соответствуют все векторы, ортогональные вектору w. Если произвольный вектор v ортогонален вектору w, то есть (v,w) = 0, то
Uv = Ev 2wwT v = v 2w(w,v) = v .
Рассмотрим действие матрицы U на произвольный вектор y, который представим в виде суммы двух ортогональных компонент: y = z + v . Компонента z направлена вдоль вектора w и является проекцией y на w:
z = dw, d = (y,w), а компонента v ортогональна этому вектору: (v,w) = 0, и равна v = y (y,w)w. Тогда
Uy =U(z + v) = E(z + v) 2wwT(z + v) = z + v 2wwT z 2wwTv =
= z + v 2wwTdw = z + v 2z = z + v .
Таким образом, вектор Uy является зеркальным отражением вектора y относительно плоскости, ортогональной вектору w. Используя это свойство матрицы отражения, можно подобрать вектор w таким, чтобы исходный вектор y 0 в результате отражения Uy получил направление некоторого заданного единичного вектора e. В результате отражения получается вектор
Uy =e или Uy = e , = (y,y), (19)
поскольку при ортогональных преобразованиях длины векторов сохраняются (U – ортогональная матрица). Направление, перпендикулярное к плоскости отражения, будет определяться вектором (y e) или вектором (y +e).
Таким образом, векторы
или 
, (20)
где 
, 
, являются требуемыми компонентами матрицы отражения. Если векторы y и e параллельны, то отражения делать не надо (при этом 
или 
будут равны нулю).
Покажем, что произвольную квадратную матрицу можно представить в виде произведения ортогональной и правой (верхней) треугольной матриц.
Пусть A – квадратная матрица порядка n.
Приведем ее к правой треугольной форме путем последовательного умножения слева на ортогональные матрицы отражения. На первом шаге приведения в качестве вектора y рассмотрим первый столбец матрицы A:
.
Если 
(i= 2,3,…,n), следует перейти к следующему шагу приведения, положив A(1) = A; U = E1 и обозначив 
. В противном случае умножим матрицу A слева на матрицу отражения U1=En2w1w1T, где w1 подбирается таким образом, чтобы вектор U1y1 стал параллелен вектору e1= [1, 0, 0, , 0]T, то есть в соответствии с формулами (19), (20). Здесь En – единичная матрица порядка n, а e1, y1 – n–мерные векторы. В результате такого преобразования в первом столбце матрицы A(1) все элементы, кроме первого, станут равными нулю.
На втором шаге приведения преобразуемым вектором является второй
столбец матрицы A(1) без первого члена
.
Преобразование отражения выполняется умножением матрицу A(1) слева на матрицу
,
где Sn-1=En-1-2wn-1wn-1T – (n 1) -мерный вектор, вычисляющийся по формулам (19), (20). Тем самым обнуляются элементы второго столбца, расположенные ниже главной диагонали матрицы A(2) =U2 A(1).
Последующие шаги процесса приведения матрицы A проводятся аналогично. После выполнения k-го шага получается матрица A(k), все элементы которой, находящиеся ниже главной диагонали вплоть до k-го столбца матрицы, равны нулю: 
при i>j, j=1,2,…,k.
Для выполнения (k +1) -го шага приведения преобразуем вектор
.
Если компоненты вектора 
для (для i =(k+2), (k +3),…,n), получаем A(k+1) = A(k ); Uk+1 = En и переходим к следующему шагу. В противном случае строим матрицу отражения
Sk+1=En-k-2wk+1wk+1T
(вектор wk+1 и матрица Sk+1 порядка ( n k )) для преобразования вектора yk+1 в вектор, параллельный вектору ek+1= [1, 0, 0, , 0]T (длины ( n k )), и переходим от матрицы A(k ) к матрице A(k+1):
A(k+1) = Uk+1A(k ), где 
Процесс этот всегда осуществим, и после (n 1) -го шага приходим к матрице
,
имеющей правую треугольную форму. Обозначив через U произведение матриц вращения 
, это выражение можно записать в виде A(n1)=UA, или A = QR, где Q =UT – ортогональная матрица, а R = A(n1) – правая треугольная матрица.
Решение системы Ax = b посредством метода отражения выполняется следующим образом. Умножив систему слева на последовательность матриц
отражения, сводим ее к виду с верхней треугольной матрицей
UAx =Ub Þ Rx =Ub, или A(n1)x =Ub.
Если все диагональные элементы матрицы A(n1) отличны от нуля, то неизвестные xi для i = n, (n 1),…,1 находятся, как и в методе Гаусса, обычным обратным ходом. Если же хотя бы один из диагональных элементов
матрицы равен нулю, то система A(n1)x =Ub вырождена, и в силу эквивалентности вырождена и исходная система.
Этот метод в настоящее время считается одним из наиболее устойчи-
вых к вычислительной погрешности, но более трудоемок в сравнении с методом Гаусса. Для получения QR-разложения квадратной матрицы A порядка n общего вида требуется около (4 / 3)n3 арифметических операций.
Метод квадратного корня
Метод квадратного корня по своему идейному содержанию близок к LU-методу. Основное отличие в том, что он дает упрощение для симметричных матриц.ID_1
Этот метод основан на разложении матрицы А в произведение
где S–верхняя треугольная матрица с положительными элементами на главной 
(22)
Из условия (2) получаются уравнения
Так как матрица А симметричная, не ограничивая общности, можно считать, что в системе (23) выполняется неравенство ij. Тогда (23) можно переписать в виде
В частности, при i=j получится
(24)
Далее, при i<j получим
По формулам (24) и (25) находятся рекуррентно все ненулевые элементы матрицы S.
Обратный ход метода квадратного корня состоит в последовательном решении двух систем уравнений с треугольными матрицами.
Решения этих систем находятся по рекуррентным формулам
Всего метод квадратного корня при факторизации A=STS требует примерно 
операций умножения и деления и m операций извлечения квадратного корня.