Участник:Nasty9705/Метод Крамера решения СЛАУ: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «=== Общее описание алгоритма ===»)
 
 
(не показано 10 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
== Свойства и структура алгоритма ==
 +
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
 +
 +
Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).
 +
 +
Метод Крамера требует вычисления <math>n+1</math> определителей размерности <math>n\times n</math>. При использовании метода Гаусса для вычисления определителей, метод имеет сложность по элементарным операциям сложения-умножения порядка <math>O(n^4)</math>, что сложнее чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным.
 +
 +
=== Математическое описание алгоритма ===
 +
Для системы <math>n</math> линейных уравнений с <math>n</math> неизвестными (над произвольным полем)
 +
: <math>\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}</math>
 +
 +
с определителем матрицы системы <math> \Delta </math>, отличным от нуля, решение записывается в виде
 +
: <math>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}</math>
 +
 +
(i-ый столбец матрицы системы заменяется столбцом свободных членов). <br />
 +
В другой форме правило Крамера формулируется так: для любых коэффициентов c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub> справедливо равенство:
 +
: <math>(c_1x_1+c_2x_2+\dots+c_nx_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}</math>
 +
 +
В этой форме метод Крамера справедлив без предположения, что <math>\Delta</math> отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы <math>b_1,b_2,...,b_n</math> и <math>x_1,x_2,...,x_n</math>, либо набор <math>c_1,c_2,...,c_n</math> состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.
 +
 +
=== Вычислительное ядро алгоритма ===
 +
Если коротко, то алгоритм сводится к вычислению главного определителя матрицы <math>(Δ)</math>, а затем <math>N</math> дополнительных определителей <math>Δi</math>  (для матриц, полученных заменой<math>i</math>-того столбца на столбец свободных членов). После проделанных вычислений <math>i</math>-тый корень можно получить по формуле <math>x_{i} = Δi/Δ</math>.
 +
 +
Что в этом алгоритме может быть выполнено параллельно?
 +
У нас вычисляется <math>N</math> определителей и именно в этой части алгоритма программа находится большую часть времени – очевидно, нет смысла распараллеливать вычисление <math>x_{i}</math> для <math>i=0..(N-1)</math>, имеющее линейную асимптотическую сложность. Очевидно, можно распараллелить алгоритм вычисления определителя, однако он сводится к сведению матрицы к треугольному виду и вычислению произведения элементов диагонали – т.е. целесообразно параллельно выполнять только триангуляцию.
 +
 +
== Программная реализация алгоритма ==
 +
== Литература ==
 +
*[[Мальцев, Анатолий Иванович|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Текущая версия на 10:24, 24 октября 2017

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).

Метод Крамера требует вычисления [math]n+1[/math] определителей размерности [math]n\times n[/math]. При использовании метода Гаусса для вычисления определителей, метод имеет сложность по элементарным операциям сложения-умножения порядка [math]O(n^4)[/math], что сложнее чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным.

1.2 Математическое описание алгоритма

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

[math]\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}[/math]

с определителем матрицы системы [math] \Delta [/math], отличным от нуля, решение записывается в виде

[math]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}[/math]

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

[math](c_1x_1+c_2x_2+\dots+c_nx_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}[/math]

В этой форме метод Крамера справедлив без предположения, что [math]\Delta[/math] отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы [math]b_1,b_2,...,b_n[/math] и [math]x_1,x_2,...,x_n[/math], либо набор [math]c_1,c_2,...,c_n[/math] состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

1.3 Вычислительное ядро алгоритма

Если коротко, то алгоритм сводится к вычислению главного определителя матрицы [math](Δ)[/math], а затем [math]N[/math] дополнительных определителей [math]Δi[/math] (для матриц, полученных заменой[math]i[/math]-того столбца на столбец свободных членов). После проделанных вычислений [math]i[/math]-тый корень можно получить по формуле [math]x_{i} = Δi/Δ[/math].

Что в этом алгоритме может быть выполнено параллельно? У нас вычисляется [math]N[/math] определителей и именно в этой части алгоритма программа находится большую часть времени – очевидно, нет смысла распараллеливать вычисление [math]x_{i}[/math] для [math]i=0..(N-1)[/math], имеющее линейную асимптотическую сложность. Очевидно, можно распараллелить алгоритм вычисления определителя, однако он сводится к сведению матрицы к треугольному виду и вычислению произведения элементов диагонали – т.е. целесообразно параллельно выполнять только триангуляцию.

2 Программная реализация алгоритма

3 Литература

  • Мальцев А. И. Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.