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

Nasty9705 в 07:24, 24 октября 2017

2017-10-24T07:24:59Z

← Предыдущая версия		Версия от 07:24, 24 октября 2017
Строка 38:		Строка 38:

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

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

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	== Литература ==		== Литература ==
	*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.		*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705: /* Вычислительное ядро алгоритма */

2017-10-24T07:22:11Z

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

← Предыдущая версия		Версия от 07:22, 24 октября 2017
Строка 39:		Строка 39:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	Если коротко, то алгоритм сводится к вычислению главного определителя матрицы <math>(Δ)</math>, а затем <math>N</math> дополнительных определителей <math>Δi</math> (для матриц, полученных заменой<math>i</math>-того столбца на столбец свободных членов). После проделанных вычислений <math>i</math>-тый корень можно получить по формуле <math>xi = Δi/Δ</math>.		Если коротко, то алгоритм сводится к вычислению главного определителя матрицы <math>(Δ)</math>, а затем <math>N</math> дополнительных определителей <math>Δi</math> (для матриц, полученных заменой<math>i</math>-того столбца на столбец свободных членов). После проделанных вычислений <math>i</math>-тый корень можно получить по формуле <math>xi = Δi/Δ</math>.

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

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	== Литература ==		== Литература ==
	*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.		*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705: /* Вычислительное ядро алгоритма */

2017-10-24T07:15:58Z

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

← Предыдущая версия		Версия от 07:15, 24 октября 2017
Строка 38:		Строка 38:

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

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	== Литература ==		== Литература ==
	*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.		*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705 в 07:14, 24 октября 2017

2017-10-24T07:14:30Z

← Предыдущая версия		Версия от 07:14, 24 октября 2017
Строка 36:		Строка 36:

	В этой форме метод Крамера справедлив без предположения, что <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>\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>-того столбца на столбец свободных членов). После проделанных вычислений i-тый корень можно получить по формуле xi = Δi/Δ.

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	== Литература ==		== Литература ==
	*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.		*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705 в 10:09, 23 октября 2017

2017-10-23T10:09:45Z

← Предыдущая версия		Версия от 10:09, 23 октября 2017
Строка 39:		Строка 39:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	== Литература ==		== Литература ==
	* [[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.		*[[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705 в 10:09, 23 октября 2017

2017-10-23T10:09:01Z

← Предыдущая версия		Версия от 10:09, 23 октября 2017
Строка 36:		Строка 36:

	В этой форме метод Крамера справедлив без предположения, что <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>\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> состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

			== Программная реализация алгоритма ==
			== Литература ==
			* [[Мальцев, Анатолий Иванович\|''Мальцев А. И.'']] Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

Nasty9705 в 10:04, 23 октября 2017

2017-10-23T10:04:24Z

← Предыдущая версия		Версия от 10:04, 23 октября 2017
Строка 1:		Строка 1:
			== Свойства и структура алгоритма ==

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

Строка 4:		Строка 6:

	Метод Крамера требует вычисления <math>n+1</math> определителей размерности <math>n\times n</math>. При использовании метода Гаусса для вычисления определителей, метод имеет сложность по элементарным операциям сложения-умножения порядка <math>O(n^4)</math>, что сложнее чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным.		Метод Крамера требует вычисления <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> состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Nasty9705: /* Общее описание алгоритма */

2017-10-23T09:55:16Z

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

← Предыдущая версия		Версия от 09:55, 23 октября 2017
Строка 3:		Строка 3:
	Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).		Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).

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

Nasty9705: /* Общее описание алгоритма */

2017-10-23T09:54:02Z

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

← Предыдущая версия		Версия от 09:54, 23 октября 2017
Строка 3:		Строка 3:
	Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).		Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).

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

Nasty9705: /* Общее описание алгоритма */

2017-10-23T09:50:37Z

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

← Предыдущая версия		Версия от 09:50, 23 октября 2017
Строка 3:		Строка 3:
	Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).		Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).

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