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

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

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

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

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

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

Для системы $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_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}$

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

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

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

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

3 Литература

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