В работе представлена теория по методам решения систем линейных алгебраических уравнений (СЛАУ) и их классификация. Подробно рассмотрен метод Гаусса последовательного исключения неизвестных и метод Гаусса с выбором главного элемента. В приложении приведена программа для решения СЛАУ методом Гаусса с выбором главного элемента, написанная на ЯП Pascal. ...
Обратный ход схемы Гаусса, в котором неизвестные определяются в обратном порядке, проводиться по следующим формулам:
,
.
Вычисления в прямом и обратном ходе схемы Гаусса выполняются по следующему алгоритму:
1) на первом шаге определяют коэффициенты по формуле (13);
2) вычисляют по формуле (14);
3) далее находят по формуле (15);
4) вычисляют коэффициенты с помощью (16);
5) на этом шаге завершается прямой ход схемы Гаусса определением по формуле (17);
6) определяют неизвестную по формуле (17);
7) неизвестную находят по формуле (20);
8) на этом шаге завершается обратный ход схемы Гаусса определением по формуле (21);
Для контроля правильности вычислений коэффициентов в прямом ходе названной схемы можно поступить следующим образом. С помощью элементов исходной расширеннойматрицы системы (1) определяют три следующие суммы:
Далее, на каждом из первых пяти шагов алгоритма находят соответственно и . Заметим, что элементы получаются как суммы элементов . вычисляют по тому же правилу, что и каждый из элементов на соответствующем шаге. Приведем эти формулы для каждого шага:
Если вычисления ведутся с постоянным числом знаков после запятой, то и не должны отличаться друг от друга более, чем на несколько единиц последнего разряда в силу линейности расчетных формул. В противном случае следует проверить правильность проведенных расчетов.
Для контроля правильности полученных значений можно поступить двояко:
1) подставить значения , во все уравнения системы (12) и убедиться, что полученные значения удовлетворяют этой системе;
2) определить неизвестную . Очевидно, что . Далее, если в формулу (20) для вместо подставить , а вместо соответственно , то получиться . Наконец, подставляя в формулу (21) вместо и вместо и , и , определяют , причем .
Замечание. Нетрудно проверить, что вычисления, проводимые в прямом ходе метода Гаусса, требуют арифметических операций.
5. Метод Гаусса с выбором главного элемента
Заметим, что в методе последовательного исключения Гаусса вычисления возможны, если ведущие элементы системы . Добиться выполнения этого условия можно, переставляя элементы строк и столбцов матрицы. Но среди ведущих элементов могут оказаться очень маленькие по абсолютной величине. При делении на такие ведущие элементы получается большая погрешность округления (вычислительная погрешность).
Чтобы избежать сильного влияния вычислительной погрешности на решение, применяется метод Гаусса с выбором главного элемента. Изложим основную идею этого метода.
Рассмотрим систему (12). Запишем расширенную прямоугольную матрицу коэффициентов системы
Среди элементов матрицы выберем наибольший по модулю, называемый главным, элемент. Например, пусть им будет элемент . Строка с номером , содержащая главный элемент, называется главной строкой.
Далее вычисляем множители для всех .
Затем матрица преобразуется так: к каждой -ой, не главной строке, прибавим почленно главную строку, умножив ее на . В результате получим матрицу, у которой все элементы -го столбца, за исключением , равны 0. Отбрасывая этот столбец и главную строку, получаем новую матрицу с меньшим на единицу числом строк и столбцов.
Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Эти преобразования продолжаются до тех пор, пока не получиться матрица, содержащая одну строку из 2-х элементов, которая тоже считается главной. Затем объединяем все главные строки, начиная с последней. После некоторой перестановки они образуют треугольную матрицу, эквивалентную исходной. На этом заканчивается прямой ход метода Гаусса с выбором главного элемента.
Далее находим , решая систему с треугольной матрицей. Это обратный ход.
Контроль правильности вычислений в методе Гаусса с выбором главного элемента осуществляется аналогично ранее описанному в методе последовательного исключения неизвестных.
Приложение.
Необходимо найти решение следующей системы, используя метод Гаусса с выбором главного элемента.
.
unit sxema_Gaussa;
interface
const
n=4;
type
mass=array[1..n] of real;
matr=array[1..n,1..n+1] of real;
var
file_dan,file_res:text;
A:matr;
x:mass;
B,S:real;
Amax:real;
i,j,k,m:integer;
procedure Matrica;
{процедура чтения матрицы из одного файла и запись ее в другой файл }
implementation
procedure Matrica;
{процедура чтения матрицы из одного файла и запись ее в другой файл }
begin {начало процедуры}
for i:=1 to n do
begin {*}
for j:=1 to n+1 do
begin {**}
read (file_dan,A[i,j]);
write (file_res, ' ', A[i,j]:5:3);
end; {**}
readln (file_dan);
writeln (file_res);
end; {*}
end; {конец процедуры}
end. {конец модуля}
program method_of_Gauss;
uses
crt,sxema_Gaussa;
label
finish;
{Основная программа}
begin {начало программы}
assign (file_dan, 'dan.txt');
assign (file_res, 'res.txt');
reset (file_dan);
rewrite (file_res);
writeln (file_res, 'Матрица коэффициентов СЛАУ имеет вид: ');
Matrica;
for k:=1 to n do
begin {1}
{Поиск максимального по модулю элемента в k-ом столбце}
Amax:=abs(A[k,k]);
i:=k;
for m:=k+1 to n do
begin {2}
if Amax<abs(A[m,k]) then
begin {3}
i:=m;
Amax:=abs(A[m,k]);
end; {3}
end; {2}
if Amax<0.000001 then
begin {4}
writeln (file_res, ' Система не имеет решения');
goto finish;
end; {4}
{Перестановка i-ой строки, содержащей главный элемент, с k-ой строкой}
if i<>k then
begin {5}
for j:=k to n+1 do
begin {6}
B:=A[k,j];
A[k,j]:=A[i,j];
A[i,j]:=B;
end; {6}
end; {5}
{Преобразование разрешающей k-ой строки}
Amax:=A[k,k];