2. Метод Гаусса с выбором главного элемента

Может оказаться так, что система имеет единственное решение, хотя какой либо из миноров матрицы А равен нулю. Заранее неизвестно, что все угловые миноры матрицы А не равны нулю. Избежать этого можно с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т. е. наибольший по модулю элемент.

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений.

1. Выбор главного элемента по строке

Пусть дана система второго порядка

(7)

при а₁₂> а₁₁, тогда на первом шаге вместо неизвестного х₁ исключают х₂:

. (8)

К системе (8) применяем первый шаг прямого хода метода Гаусса. Указан­ный способ исключения называется методом Гаусса с выбором глав­ного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных.

2. Выбор главного элемента по столбцу

Предположим, что а₂₁> а₁₁и переставим уравнения системы (7)

(9)

и к системе (9) применяем первый шаг прямого хода метода Гаусса.

Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к систе­ме, в которой на каждом шаге исключения проводится соответ­ствующая перенумерация уравнений.

2. Выбор главного элемента по всей матрице

Поиск главного элемента по всей матрице заключается в нахождении максимального по модулю элемента среди всех элементов матрицы системы. Всё это приводит к уменьшению вычислительной погрешности.

2. Решение системы линейных алгебраических уравнений с помощью 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.4 Метод простой итерации решения систем линейных алгебраических уравнений

Исходную систему (1) преобразуем к виду:

(12)

где , i=1,2,...,n; , a_ii0.

Перепишем систему (12) в виде одного матричного уравнения:

(13)

Первая сумма равна нулю, если верхний предел суммирования меньше нижнего.

Так (12) при i=1 имеет вид

Итерационный процесс (12) начинается с начальных значений , которые в общем случае задаются произвольно, но предпочтительнее, если за взять свободные члены исходной системы, т.е . Подставляя начальные значения в правую часть выражения (12) и вычисляя полученное выражение находим первое приближение:

.

Подставляя приближение в правую часть системы (12) получим:

.

Продолжая этот процесс получим последовательность , , ,…, ,… приближений вычисляемых по формуле:

, где ` (14)

В развернутой форме записи формула (14) выглядит так:

Условие окончания счета:

,

где i= .

Теорема

Если какая-либо норма матрицы меньше единицы: , то уравнение (13) имеет единственное решение ξ, к которому стремится последовательность итераций (14) при любом выборе начального приближения .

Число итераций для достижения заданной точности ε определяется из неравенства:

. (15)

Неравенство (15) обычно дает завышенную оценку числа итераций k.

Условие, позволяющее принять приближение в качестве решения с точностью ε, представляется в следующей форме:

. (16)