Точные методы численного решения систем линейных алгебраических уравнений
read (a[i,j]);
writeln;
writeln('Введите свободные коэффициенты:');
writeln;
for i:=1 to n do
readln(d[i]);
writeln;
end;
{Процедура получения двух треугольных матриц, произведение которых равно исходной матрице}
procedure getBnC(var a,b,c:mattype; n:byte);
var k,i,a1,j:byte;
begin
for k:=1 to n do
for i:=1 to n do
begin
if k=i then c[k,i]:=1
else c[k,i]:=0;
b[k,i]:=0;
end;
for a1:=1 to n do
begin
if a1=1 then
begin
for i:=1 to n do
b[i,1]:=a[i,1];
for i:=2 to n do
c[1,i]:=a[1,i]/b[1,1];
end
else
begin
k:=a1;
for i:=a1 to n do
begin
b[i,k]:=a[i,k];
for j:=1 to k-1 do
b[i,k]:=b[i,k]-b[i,j]*c[j,k];
end;
i:=a1;
for k:=i+1 to n do
begin
c[i,k]:=a[i,k];
for j:=1 to i-1 do
c[i,k]:=c[i,k]-b[i,j]*c[j,k];
c[i,k]:=c[i,k]/b[i,i];
end;
end;
end;
end;
procedure otvet(var b,c:mattype; d:mattype1; n:byte);
var x,y,s:mattype1;
i,j,k:byte;
w,q:double;
y1,x1:mattype;
begin
for i:=1 to n do
if i=1 then y[i]:=d[i]/b[i,i]
else
begin
w:=0;
for k:=1 to i-1 do
begin
y1[i,k]:=w+b[i,k]*y[k];
w:=y1[i,k];
end;
y[i]:=(d[i]-w)/b[i,i];
end;
for i:=n downto 1 do
if i=n then x[i]:=y[i]
else
begin
q:=0;
for k:=i+1 to n do
begin
x1[i,k]:=q+c[i,k]*x[k];
q:=x1[i,k];
end;
x[i]:=y[i]-q;
end;
writeln;
writeln('Ответ X:');
writeln;
for i:=1 to n do
writeln('x[',i,']= ',x[i]:1:4);
writeln;
end;
{Основная программа}
var a,a1,c,b:mattype;
d:mattype1;
n:byte;
begin
clrscr;
writeln ('Курсовая работа ');
InputMat(a,d,n); {Ввод матрицы A }
getBnC(a,b,c,n);{ Получение треугольных матриц B u C}
Writeln('Матрица B: ');
writemat(b,n,n);
readln;
Writeln('Матрица C: ');
writemat(c,n,n);
otvet(b,c,d,n);
readln;
end.
3.2 Решение в Excel
Заключение
Первым из алгоритмов, посвященным большому разделу решения систем линейных уравнений, представляем алгоритм Халейкого. Это фактически метод решения систем общего вида, конкурирующий по быстродействию с общеизвестным методом Гаусса-Жордана, но позволяющий более эффективно использовать решение.
Если мы можем разложить матрицу линейной системы A в произведение A=L*U(B*C), где L(B) - нижняя, а U(C) - верхняя треугольные матрицы, то решение системы уравнений с произвольной правой частью производится весьма просто, применением двух обратных подстановок. Более того, в отличие от известного метода Гаусса-Жордана, разложенная матрица позволяет быстро решать серии линейных уравнений с различными правыми частями при одной и той же матрице.
Метод Халецкого позволяет провести LU-декомпозицию матрицы примерно за то же число операций, что и "прямая" часть метода Гаусса-Жордана. Итоговые коэффициенты двух треугольных матриц упаковываются в матрицу того же размера, что и A, и на том же месте в памяти. При этом верхняя матрица U размещается в наддиагональной части и на диагонали; нижняя L в поддиагональной части, а диагональные элементы L считаются все равными 1 (без ограничения общности) и не выводятся.
Метод Халецкого исключительно является точным методом, при этом предполагалось, что арифметические операции выполняются над точными числами. Если же метод реализуется на ЭВМ, то появляется вычислительная погрешность, заметим, что даже результаты точных методов являются приближенными из-за неизбежных округлений. Для итерационных процессов также добавляется погрешность метода.
Схема Халецкого удобна для работы на вычислительных машинах, так как при представлении матрицы А в виде произведения нижней треугольной матрицы L и верхней треугольной матрицы U с единичной диагональю, операцию “накопления” можно проводить без записи промежуточных результатов.
Литература
Б.П. Демидович и И.А. Марон. “Основы вычислительной математики”, Москва, 1963г.
Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. “Численные методы”, Москва, 1987г.
Ю.П. Боглаев. “Вычислительная математика и программирование”, Москва, 1990г.
Приложение
Результаты работы программы:
