Выбор ведущего элемента

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

Выбор максимального по модулю ведущего элемента позволяет к тому же уменьшить вычислительные погрешности, возникающие в силу того, что компьютер работает с числами ограниченной разрядности. Действительно, объединив формулы (4) и (5) и опустив верхние индексы, получим общую формулу преобразований прямого хода

(1.15)

Выражение, выделенное в скобках, называется множителем. Выбирая максимальный по модулю ведущий элемент , получим, что множитель будет меньше единицы, т.е. «новое» значение коэффициента получается из «старого» путем вычитания небольшой поправки, которая не будет вносить значительных искажений.

Можно реализовать несколько путей поиска максимального по модулю элемента. Если этот процесс осуществлять по всем коэффициентам, участвующим в дальнейшем исключении

(1.16)

для то говорят о методе исключения с полным упорядочением. Такой алгоритм достаточно сложен и по трудоемкости сравним с прямым ходом, а поэтому используется редко.

Большую популярность имеют стратегии частичного упорядочения по строкам (или столбцам)

(1.17)

Ищется номер строки m, в которой находится максимальный по модулю элемент и осуществляется обмен строками.

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

Модернизируем процедуру решения СЛАУ, вставив в неё фрагмент с частичным выбором ведущего элемента:

………….

eps:=1.0e-6;

for k:=1 to n do { прямой ход}

begin s:=a[k,k]; m:=k;

for i:=k+1 to n do

begin t:=a[i,k];

if abs(t) > abs(s) { поиск максимального элемента в к-ом столбце}

then begin s:=t; m:=i end

end;

if abs(s)< eps {система плохо обусловлена; ее решение требует специальных приемов}

then begin writeln (‘Error 01’); Exit end;

if m<>k

then for j:=k to n+1 do Swap (a[k,j],a[m,j]); {обмен строками}

for j:=k+1 to n+1 do { нормировка на единицу диагонального элемента }

a[k,j]:=a[k,j]/s;

……………

Здесь Swap (a[k,j],a[m,j]) – процедура обмена двух элементов.

Проведите тестирование подпрограмм, осуществляющих решение систем линейных уравнений методом Гаусса, вычисление определителя и обратной матрицы.

В приведенной выше тестовой матрице последовательно будем уменьшать на порядок диагональные элементы, выбирая их равными 0,4; 0,04; 0,004;…Сравнить результаты, полученные с выбором и без выбора ведущего элемента. Определить, в каком разряде после запятой наблюдаются отклонения.

Уменьшая на порядки величину диагональных элементов, необходимо провести расчеты для матриц разной размерности, например, n=10, 100, 500. Сравнить результаты расчетов с выбором и без выбора ведущего элемента.

Провести расчеты с матрицей, размером 10х10, в которой диагональные элементы, последовательно изменяясь на порядок величины, отличаются на десять порядков. Сравнить результаты расчетов с выбором и без выбора ведущего элемента.

Не нашли, что искали? Воспользуйтесь поиском: