Нахождения определителя матрицы методом Гаусса

Постановка задачи. Классификация численных методов решения СЛАУ. Точные методы решения СЛАУ. Теорема об 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 единицами, то есть U_ii=1

Снятие неопределённости в (7) и (8) следует из правильного порядка вычисления этих формул.

Счёт по формулам ведётся следующим образом: с помощью пар индексов счёт ведётся по строкам обеих матриц сразу.

Нахождения определителя матрицы методом Гаусса.

Согласно теореме об LU разложении: А=L*U, по свойству определителя

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

Итерационные методы решения СЛАУ позволяют находить решения лишь как результат бесконечного итерационного процесса.

Выбирается начальное приближение х⁽⁰⁾, а затем строим все последующие. В общем случае приближения строятся по следующей формуле:

(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

Пусть х⁽⁰⁾=х^*

В⁽⁰⁾х⁽¹⁾=В⁽⁰⁾х⁽⁰⁾+τ₁(b-x⁽⁰⁾)=x⁽¹⁾=x⁽⁰⁾=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))

ч.т.д.