Постановка задачи. Классификация численных методов решения СЛАУ. Точные методы решения СЛАУ. Теорема об LU-разложении. Метод LU-разложений. Итерационные методы решения СЛАУ. Метод простых итераций. Критерии сходимости, достаточные условия сходимости.
Постановка задачи
Требуется найти решение системы m линейных уравнений, которая записывается в общем виде как
Эту систему уравнений можно записать также в матричном виде:
(1*)
Где
A – матрица системы, 
– вектор правых частей, 
– вектор неизвестных.
При известных A и 
– требуется найти такие 
, при подстановке которых в систему уравнений она превращается в тождество.
Необходимым и достаточным условием существования единственного решения СЛАУ является условие det A≠0, т.е. определитель матрицы A не равен нулю. В случае равенства нулю определителя матрица A называется вырожденной и при этом СЛАУ либо не имеет решения, либо имеет их бесчисленное множество.
Классификация численных методов решения СЛАУ.
1. Прямые или точные методы.
Позволяют найти точные решения за конечное число шагов в предположении отсутствия ошибок округления.
Основная идея: приводим матрицу к спец.виду (диагональная) потом начинаем исключать переменные.
2. Итерационные методы
Позволяют найти решение бесконечно единообразного процесса наз. итерацией.
Основная идея: решение находится с заданной точностью, решение ищется из ранее найденного решения
3. Вероятностные методы.
Основываются на аппарате теории вероятности и находят решение лишь с некоторой долей вероятности близкое к точному.
Основная идея: решение находится с некоторой заданной надежностью. Применяются на больших матрицах.
Точные методы решения СЛАУ
Позволяют найти точные решения за конечное число шагов в предположении отсутствия ошибок округления.
Теорема: (об LU – разложений матрицы). Любая квадратная невырожденная матрица А, у которой главные миноры отличные от нуля, может быть представлена в виде произведения двух матриц
А=L 
U (1),
Где
L – нижне-треугольная матрица (лево треугольная матрица);
U – верхне-треугольная матрица (право треугольная матрица).
Причём это разложение единственно с точностью до диагональных членов.
Если мы зафиксируем элементы диагонали, то разложение будет единственно, такое разложение называется разложением с точностью до диагональных членов.
Так как разложение матрицы А представляется в виде произведения, то уравнение (1) преобразуется:
(2).
(3)
(4)
Разложение матрицы А в разложение L и U называется прямым ходом метода Гаусса.
Нахождение вектора х по (3) и (4) называется обратным ходом метода Гаусса.
для этого решим систему уравнений:
(5)
Решим уравнение (4):
(6)
Рассмотрим формулы для получения разложения матриц в виде LU
1) 
, то 
2) 
, то 
, (7)
, 
(8)
На практике часто фиксируются диагональные матрицы U единицами, то есть Uii=1
Снятие неопределённости в (7) и (8) следует из правильного порядка вычисления этих формул.
Счёт по формулам ведётся следующим образом: с помощью пар индексов 
счёт ведётся по строкам обеих матриц сразу.
Нахождения определителя матрицы методом Гаусса.
Согласно теореме об LU разложении: А=L*U, по свойству определителя
Итерационные методы решения систем линейно-алгебраических уравнений.
Итерационные методы решения СЛАУ позволяют находить решения лишь как результат бесконечного итерационного процесса.
Выбирается начальное приближение х(0), а затем строим все последующие. В общем случае приближения строятся по следующей формуле:
(9)
Итерационный процесс называется m – шаговым, если для образования (k+1) – го приближения используются k предыдущих приближений.
X(k+1)=F(k)(x(k), x(k-1), …, x(k-m+1)).
Как правило, используют m=1, 2.
Итерационный процесс называется линейным, если функция F(k) линейная функция.
Итерационный процесс называется стационарным, если функция F(k) не зависит от k.
Канонический вид двухслойной или одношаговой итерационной схемы:
где τk+1 – итерационный параметр (10)
Итерационный процесс называется явным когда для любого номера итерации k оператор 
.
Требованием любого итерационного процесса является то, что точное решение должно быть не подвижной точкой итерационного процесса.
Точка называется неподвижной для итерационного процесса, если начиная с некоторого итерационного номера наши решения совпадают: 
.
Теорема: Если х* - точное решение уравнения (1*), то оно является неподвижной точкой итерационного процесса (10).
Всякий итерационный процесс (1*), для которого х* - неподвижная точка, может быть приведён к виду (10).
Док – во:1)Пусть х* - точное решение (1*)
Ах*=b
х*=А-1b
Пусть х(0)=х*
В(0)х(1)=В(0)х(0)+τ1(b-x(0))=x(1)=x(0)=x*
2)(
)(
)(х(k)=x*)
B(k)x*=Q(k)+b(k)
(B(k)-Q(k))x*=b(k): (*)
С другой стороны х* является решением Ах*=b
τk+1Ax*=τk+1b: (**).
Рассмотрим два уравнения (*) и (**) совместно, т.е.
Q(k)=B(k)-τk+1A 
B(k)x(k+1)=(B(k)-τk+1A)x(k)+τk+1b
B(k)x(k+1)=B(k)x(k)+τk+1(b-Ax(k))
ч.т.д.
