Решение системы линейных уравнений методом Крамера - Pascal(Паскаль) - Справочник юного программиста Pascal/Delphi

Описание метода

Для системы $n$ линейных уравнений с $n$ неизвестными (над произвольным полем)

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}=b_{2}\\\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\a_{n1}x_{1}+a_{n2}x_{2}+\ldots +a_{nn}x_{n}=b_{n}\\\end{cases}}$

с определителем матрицы системы $\Delta$ , отличным от нуля, решение записывается в виде $x_{i}={\frac {1}{\Delta }}{\begin{vmatrix}a_{11}&\ldots &a_{1,i-1}&b_{1}&a_{1,i+1}&\ldots &a_{1n}\\a_{21}&\ldots &a_{2,i-1}&b_{2}&a_{2,i+1}&\ldots &a_{2n}\\\ldots &\ldots &\ldots &\ldots &\ldots &\ldots &\ldots \\a_{n-1,1}&\ldots &a_{n-1,i-1}&b_{n-1}&a_{n-1,i+1}&\ldots &a_{n-1,n}\\a_{n1}&\ldots &a_{n,i-1}&b_{n}&a_{n,i+1}&\ldots &a_{nn}\\\end{vmatrix}}$

(i-ый столбец матрицы системы заменяется столбцом свободных членов).
В другой форме правило Крамера формулируется так: для любых коэффициентов c₁, c₂, …, c_n справедливо равенство:

$(c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n})\cdot \Delta =-{\begin{vmatrix}a_{11}&a_{12}&\ldots &a_{1n}&b_{1}\\a_{21}&a_{22}&\ldots &a_{2n}&b_{2}\\\ldots &\ldots &\ldots &\ldots &\ldots \\a_{n1}&a_{n2}&\ldots &a_{nn}&b_{n}\\c_{1}&c_{2}&\ldots &c_{n}&0\\\end{vmatrix}}$

В этой форме метод Крамера справедлив без предположения, что $\Delta$ отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы $b_{1},b_{2},...,b_{n}$ и $x_{1},x_{2},...,x_{n}$ , либо набор $c_{1},c_{2},...,c_{n}$ состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Пример

Система линейных уравнений с вещественными коэффициентами:

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+a_{23}x_{3}=b_{2}\\a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}=b_{3}\\\end{cases}}$

Определители:

${\textstyle \Delta ={\begin{vmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{vmatrix}},\ \ \Delta _{1}={\begin{vmatrix}b_{1}&a_{12}&a_{13}\\b_{2}&a_{22}&a_{23}\\b_{3}&a_{32}&a_{33}\\\end{vmatrix}},\ \ }$

$\Delta _{2}={\begin{vmatrix}a_{11}&b_{1}&a_{13}\\a_{21}&b_{2}&a_{23}\\a_{31}&b_{3}&a_{33}\\\end{vmatrix}},\ \ \Delta _{3}={\begin{vmatrix}a_{11}&a_{12}&b_{1}\\a_{21}&a_{22}&b_{2}\\a_{31}&a_{32}&b_{3}\\\end{vmatrix}}$

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

Решение:

$x_{1}={\frac {\Delta _{1}}{\Delta }},\ \ x_{2}={\frac {\Delta _{2}}{\Delta }},\ \ x_{3}={\frac {\Delta _{3}}{\Delta }}$

Пример:

${\begin{cases}2x_{1}+5x_{2}+4x_{3}=30\\x_{1}+3x_{2}+2x_{3}=150\\2x_{1}+10x_{2}+9x_{3}=110\\\end{cases}}$

Определители:

$\Delta ={\begin{vmatrix}2&5&4\\1&3&2\\2&10&9\\\end{vmatrix}}=5,\ \ \Delta _{1}={\begin{vmatrix}30&5&4\\150&3&2\\110&10&9\\\end{vmatrix}}=-760,\ \$

$\Delta _{2}={\begin{vmatrix}2&30&4\\1&150&2\\2&110&9\\\end{vmatrix}}=1350,\ \ \Delta _{3}={\begin{vmatrix}2&5&30\\1&3&150\\2&10&110\\\end{vmatrix}}=-1270.$

$x_{1}=-{\frac {760}{5}}=-152,\ \ x_{2}={\frac {1350}{5}}=270,\ \ x_{3}=-{\frac {1270}{5}}=-254$

Вычислительная сложность

Метод Крамера требует вычисления $n+1$ определителей размерности $n\times n$ . При использовании метода Гаусса для вычисления определителей метод имеет сложность по элементарным операциям сложения-умножения порядка $O(n^{4})$ , что сложнее, чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным. Однако в 2010 году было показано, что метод Крамера может быть реализован со сложностью $O(n^{3})$ , сравнимой со сложностью метода Гаусса.

Программа на Pascal

uses crt;
type
 Tmass=array[1..20] of real;
 Tmatrix=array[1..20] of Tmass;
{процедура перестановки строк}
procedure Per(k,n:integer;var a:Tmatrix;var p:integer);
var z:Real;j,i:integer;
begin
z:=abs(a[k,k]);
i:=k;
p:=0;
for j:=k+1 to n do
  begin
   if abs(a[j,k])>z then
    begin
     z:=abs(a[j,k]);
     i:=j;
     p:=p+1;{счетчик перестановок}
    end;
  end;
if i>k then
for j:=k to n do
  begin
   z:=a[i,j];
   a[i,j]:=a[k,j];
   a[k,j]:=z;
  end;
end;
{определение знака определителя по числу перестановок}
function Znak(p:integer):integer;
begin
if p mod 2=0 then
Znak:=1 else Znak:=-1;
end;
{нахождение определителя}
procedure Opr(n:integer;a:tmatrix;var det:real);
var k,i,j,p:integer;r:real;
begin
det:=1.0;
for k:=1 to n do
  begin
   if a[k,k]=0 then Per(k,n,a,p);{перестановка строк}
   det:=znak(p)*det*a[k,k];{вычисление определителя}
   for j:=k+1 to n do {пересчет коэффициентов}
    begin
      r:=a[j,k]/a[k,k];
      for i:=k to n do
       begin
        a[j,i]:=a[j,i]-r*a[k,i];
       end;
    end;
  end;
end;
var a:Tmatrix;
    c:array[1..20] of Tmatrix;
    b,x:Tmass;
    det,det1:real;
    n,k,j,i:integer;
begin
clrscr;
write('Порядок системы n=');
readln(n);
writeln('Введите коэффициенты уравнений:');
for i:=1 to n do
 begin
  writeln('Уравнение ',i);
  for j:=1 to n do
  read(a[i,j]);
 end;
readln;
writeln('Введите свободные члены:');
for i:=1 to n do
read(b[i]);
readln;
clrscr;
writeln('Расширенная матрица системы:');
for i:=1 to n do
 begin
  for j:=1 to n do
  write(a[i,j]:7:2);
  write(b[i]:9:2);
  writeln;
 end;
Opr(n,a,det);{определитель системы}
for i:=1 to n do
 begin
  for k:=1 to n do
   begin
    for j:=1 to n do
    c[i][k,j]:=a[k,j];
    c[i][k,i]:=b[k];
   end;
  Opr(n,c[i],det1);
  if(det=0)and(det1=0) then
    begin
     writeln('Система не определена!');
     readln;
     exit;
    end;
  if(det=0)and(det1<>0) then
    begin
     writeln('Система не имеет решений!');
     readln;
     exit;
    end;
  x[i]:=det1/det;
 end;
writeln('Корни сиcтемы:');
for i:=1 to n do
writeln('x',i,'=',x[i]:7:3);
readln
end.

Тестирование на сайте https://www.onlinegdb.com/

Расширенная матрица системы:
   2.00   5.00   4.00    30.00
   1.00   3.00   2.00   150.00
   2.00  10.00   9.00   110.00
Корни сиcтемы:
x1=-152.000
x2=270.000
x3=-254.000

Решение системы линейных уравнений методом Крамера — Pascal(Паскаль)

Описание метода

Пример

Вычислительная сложность

Похожие записи/страницы:

Leave a Comment