Примеры решение слау методом гаусса: Примеры решения системы линейных алгебраических уравнений 3-его порядка методом Гаусса, пример № 1

Примеры решения СЛАУ методом Гаусса

Система линейных алгебраических уравнений

Система уравнений — это условие, состоящее в одновременном выполнении нескольких уравнений относительно нескольких переменных. Системой линейных алгебраических уравнений (далее — СЛАУ), содержащей m уравнений и n неизвестных, называется система вида:

где числа a_ij называются коэффициентами системы, числа b_i — свободными членами, a_ij и b_i (i=1,…, m; b=1,…, n) представляют собой некоторые известные числа, а x₁,…, x_n — неизвестные. В обозначении коэффициентов a_ij первый индекс i обозначает номер уравнения, а второй j — номер неизвестного, при котором стоит этот коэффициент. Подлежат нахождению числа x_n. Такую систему удобно записывать в компактной матричной форме: AX=B.Здесь А — матрица коэффициентов системы, называемая основной матрицей;

— вектор-столбец из неизвестных xj.

— вектор-столбец из свободных членов bi.

Произведение матриц А*Х определено, так как в матрице А столбцов столько же, сколько строк в матрице Х (n штук).

Расширенной матрицей системы называется матрица A системы, дополненная столбцом свободных членов

Метод исключения Гаусса

Сущность метода исключения Гаусса

Классическим методом решения систем линейных алгебраических уравнений является метод последовательного исключения неизвестных — метод Гаусса(его еще называют методом гауссовых исключений). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которого последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

Процесс решения по методу Гаусса состоит из двух этапов: прямой и обратный ходы.

1. Прямой ход.

На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним.

После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

На первом этапе (прямой ход) система приводится к ступенчатому (в частности, треугольному) виду.

Приведенная ниже система имеет ступенчатый вид:,где

Коэффициенты aii называются главными (ведущими) элементами системы.

1-й шаг.

Будем считать, что элемент (если a11=0, переставим строки матрицы так, чтобы a₁₁ не был равен 0. Это всегда возможно, т. к. в противном случае матрица содержит нулевой столбец, ее определитель равен нулю и система несовместна).

Преобразуем систему, исключив неизвестное х1 во всех уравнениях, кроме первого (используя элементарные преобразования системы). Для этого умножим обе части первого уравнения на и сложим почленно со вторым уравнением системы (или из второго уравнения почленно вычтем первое, умноженное на ). Затем умножим обе части первого уравнения на и сложим с третьим уравнением системы (или из третьего почленно вычтем первое, помноженное на ). Таким образом, последовательно умножаем первую строку на число и прибавляем к

i-й строке, для i=2, 3, …, n.

Продолжая этот процесс, получим эквивалентную систему:

Здесь — новые значения коэффициентов при неизвестных и свободные члены в последних m-1 уравнениях системы, которые определяются формулами:

Таким образом, на первом шаге уничтожаются все коэффициенты, лежащие под первым ведущим элементом a₁₁0, на втором шаге уничтожаются элементы, лежащие под вторым ведущим элементом а₂₂⁽¹⁾ (если a₂₂⁽¹⁾0) и т.

д. Продолжая этот процесс и дальше, мы, наконец, на (m-1) шаге приведем исходную систему к треугольной системе.

Если в процессе приведения системы к ступенчатому виду появятся нулевые уравнения, т.е. равенства вида 0=0, их отбрасывают. Если же появится уравнение вида то это свидетельствует о несовместности системы.

На этом прямой ход метода Гаусса заканчивается.

2. Обратный ход.

На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений.

Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (она в нем всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх.

Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Примечание: на практике удобнее работать не с системой, а с расширенной ее матрицей, выполняя все элементарные преобразования над ее строками. Удобно, чтобы коэффициент a11 был равен 1 (уравнения переставить местами, либо разделить обе части уравнения на a11)

Примеры решения СЛАУ методом Гаусса

Пример 1. Решить СЛАУ 3-го порядка.

x + y — 3z = 2,

3x — 2y + z = — 1,

2x + y — 2z = 0.

Решение. Выпишем расширенную матрицу данной системы

и произведем следующие элементарные преобразования над ее строками:

а) из ее второй и третьей строк вычтем первую, умноженную соответственно на 3 и 2:

~ ;

б) третью строку умножим на (-5) и прибавим к ней вторую:

.

В результате всех этих преобразований данная система приводится к треугольному виду:

x + y — 3z = 2,

-5y + 10z = -7,

— 10z = 13.

Из последнего уравнения находим z = -1,3. Подставляя это значение во второе уравнение, имеем y = -1,2. Далее из первого уравнения получим
x = — 0,7.

 

Метод Гаусса

Определение и описание метода Гаусса

Метод преобразований Гаусса (также известный как преобразование методом последовательного исключения неизвестных переменных из уравнения или матрицы) для решения систем линейных уравнений представляет собой классический методом решения системы алгебраических уравнений (СЛАУ). Также этот классический метод используют для решения таких задач как получение обратных матриц и определения ранговости матрицы.

Преобразование с помощью метода Гаусса заключается в совершении небольших (элементарных) последовательных изменениях системы линейных алгебраических уравнений, приводящих к исключению переменных из неё сверху вниз с образованием новой треугольной системы уравнений, являющейся равносильной исходной.

Определение 1

Эта часть решения носит название прямого хода решения Гаусса, так как весь процесс осуществляется сверху вниз.

После приведения исходной системы уравнений к треугольной осуществляется нахождение всех переменных системы снизу вверх (то есть первые найденные переменные занимают находятся именно на последних строчках системы или матрицы). Эта часть решения известна также как обратный ход решения методом Гаусса. Заключается его алгоритм в следующем: сначала вычисляется переменные, находящиеся ближе всего к низу системы уравнений или матрицы, затем полученные значения подставляются выше и таким образом находится ещё одна переменная и так далее.

Описание алгоритма метода Гаусса

Последовательность действий для общего решения системы уравнения методом Гаусса заключается в поочередном применении прямого и обратного хода к матрице на основе СЛАУ. Пусть исходная система уравнений имеет следующий вид:

$\begin{cases} a_{11} \cdot x_1 +…+ a_{1n} \cdot x_n = b_1 \\ . .. \\ a_{m1} \cdot x_1 + a_{mn} \cdot x_n = b_m \end{cases}$

Чтобы решить СЛАУ методом Гаусса, необходимо записать исходную систему уравнений в виде матрицы:

$A = \begin{pmatrix} a_{11} & … & a_{1n} \\ \vdots & … & \vdots \\ a_{m1} & … & a_{mn} \end{pmatrix}$, $b=\begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix}$

Матрица $A$ называется основной матрицей и представляет собой записанные по порядку коэффициенты при переменных, а $b$ называется столбцом её свободных членов. Матрица $A$, записанная через черту со столбцом свободных членов называется расширенной матрицей:

$A = \begin{array}{ccc|c} a_{11} & … & a_{1n} & b_1 \\ \vdots & … & \vdots & …\\ a_{m1} & … & a_{mn} & b_m \end{array}$

Теперь необходимо с помощью элементарных преобразований над системой уравнений (или над матрицей, так как это удобнее) привести её к следующему виду:

$\begin{cases} α_{1j_{1}} \cdot x_{j_{1}} + α_{1j_{2}} \cdot x_{j_{2}}. ..+ α_{1j_{r}} \cdot x_{j_{r}} +… α_{1j_{n}} \cdot x_{j_{n}} = β_1 \\ α_{2j_{2}} \cdot x_{j_{2}}…+ α_{2j_{r}} \cdot x_{j_{r}} +… α_{2j_{n}} \cdot x_{j_{n}} = β_2 \\ …\\ α_{rj_{r}} \cdot x_{j_{r}} +… α_{rj_{n}} \cdot x_{j_{n}} = β_r \\ 0 = β_(r+1) \\ … \\ 0 = β_m \end{cases}$ (1)

Матрица, полученная из коэффициентов преобразованной системы уравнения (1) называется ступенчатой, вот так обычно выглядят ступенчатые матрицы:

$A = \begin{array}{ccc|c} a_{11} & a_{12} & a_{13} & b_1 \\ 0 & a_{22} & a_{23} & b_2\\ 0 & 0 & a_{33} & b_3 \end{array}$

Для этих матриц характерен следующий набор свойств:

1. Все её нулевые строки стоят после ненулевых
2. Если некоторая строка матрицы с номером $k$ ненулевая, то в предыдущей строчке этой же матрицы нулей меньше, чем в этой, обладающей номером $k$.

После получения ступенчатой матрицы необходимо подставить полученные переменные в оставшиеся уравнения (начиная с конца) и получить оставшиеся значения переменных.

Основные правила и разрешаемые преобразования при использовании метода Гаусса

При упрощении матрицы или системы уравнений этим методом нужно использовать только элементарные преобразования.

Таким преобразованиями считаются операции, которые возможно применять к матрице или системе уравнений без изменения её смысла:

• перестановка нескольких строк местами,
• прибавление или вычитание из одной строчки матрицы другой строчки из неё же,
• умножение или деление строчки на константу, не равную нулю,
• строчку, состоящую из одних нулей, полученную в процессе вычисления и упрощения системы, нужно удалить,
• Также нужно удалить лишние пропорциональные строчки, выбрав для системы единственную из них с более подходящими и удобными для дальнейших вычислений коэффициентами.

Все элементарные преобразования являются обратимыми.

Разбор трёх основных случаев, возникающих при решении линейных уравнений используя метод простых преобразований Гаусса

Различают три возникающих случая при использовании метода Гаусса для решения систем:

1. Когда система несовместная, то есть у неё нет каких-либо решений
2. У системы уравнений есть решение, причём единственное, а количество ненулевых строк и столбцов в матрице равно между собой.
3. Система имеет некое количество или множество возможных решений, а количество строк в ней меньше чем количество столбцов.

Исход решения с несовместной системой

Для этого варианта при решении матричного уравнения методом Гаусса характерно получение какой-то строчки с невозможностью выполнения равенства. Поэтому при возникновении хотя бы одного неправильного равенства полученная и исходная системы не имеют решений вне зависимости от остальных уравнений, которые они содержат. Пример несовместной матрицы:

$\begin{array}{ccc|c} 2 & -1 & 3 & 0 \\ 1 & 0 & 2 & 0\\ 0 & 0 & 0 & 1 \end{array}$

В последней строчке возникло невыполняемое равенство: $0 \cdot x_{31} + 0 \cdot x_{32} + 0 \cdot x_{33} = 1$.

Система уравнений, у которой есть только одно решение

Данные системы после приведения к ступенчатой матрице и удаления строчек с нулями имеют одинаковое количество строк и столбцов в основной матрице. Вот простейший пример такой системы:

$\begin{cases} x_1 — x_2 = -5 \\ 2 \cdot x_1 + x_2 = -7 \end{cases}$

Запишем её в виде матрицы:

$\begin{array}{cc|c} 1 & -1 & -5 \\ 2 & 1 & -7 \end{array}$

Чтобы привести первую ячейку второй строчки к нулю, домножим верхнюю строку на $-2$ и вычтем её из нижней строчки матрицы, а верхнюю строчку оставим в исходном виде, в итоге имеем следующее:

$\begin{array}{cc|c} 1 & -1 & -5 \\ 0 & 3 & 10 \end{array}$

Этот пример можно записать в виде системы:

$\begin{cases} x_1 — x_2 = -5 \\ 3 \cdot x_2 = 10 \end{cases}$

Из нижнего уравнения выходит следующее значение $x$: $x_2 = 3 \frac{1}{3}$. Подставим это значение в верхнее уравнение: $x_1 – 3 \frac{1}{3}$, получаем $x_1 = 1 \frac{2}{3}$.

Система, обладающая множеством возможных вариантов решений

Для этой системы характерно меньшее количество значащих строк, чем количество столбцов в ней (учитываются строки основной матрицы).

Переменные в такой системе делятся на два вида: базисные и свободные. При преобразовании такой системы содержащиеся в ней основные переменные необходимо оставить в левой области до знака “=”, а остальные переменные перенести в правую часть равенства.

У такой системы есть только некое общее решение.

Разберём следующую систему уравнений:

$\begin{cases} 2y_1 + 3y_2 + x_4 = 1 \\ 5y_3 — 4y_4 = 1 \end{cases}$

Запишем её в виде матрицы:

$\begin{array}{cccc|c} 2 & 3 & 0 & 1 & 1 \\ 0 & 0 & 5 & 4 & 1 \\ \end{array}$

Наша задача найти общее решение системы. Для этой матрицы базисными переменными будут $y_1$ и $y_3$ (для $y_1$ — так как он стоит на первом месте, а в случае $y_3$ — располагается после нулей).

В качестве базисных переменных выбираем именно те, которые первые в строке не равны нулю.

Оставшиеся переменные называются свободными, через них нам необходимо выразить базисные.

Используя так называемый обратный ход, разбираем систему снизу вверх, для этого сначала выражаем $y_3$ из нижней строчки системы:

$5y_3 – 4y_4 = 1$

$5y_3 = 4y_4 + 1$

$y_3 = \frac{4/5}y_4 + \frac{1}{5}$. 3 = 2\\ 3x_1 + 2x_2 – 3x_3 = 0 \end{cases}$

Запишем нашу систему в виде расширенной матрицы:

$\begin{array}{ccc|c} 4 & 2 & -1 & 1 \\ 5 & 3 & -2 & 2 \\ 3 & 2 & -3 & 0\\ \end{array}$

Теперь для удобства и практичности нужно преобразовать матрицу так, чтобы в верхнем углу крайнего столбца была $1$.

Для этого к 1-ой строчке нужно прибавляем строчку из середины, умноженную на $-1$, а саму среднюю строчку записываем как есть, выходит:

$\begin{array}{ccc|c} -1 & -1 & 1 & -1 \\ 5 & 3 & -2 & 2 \\ 3 & 2 & -3 & 0\\ \end{array}$

Далее к средней строчке прибавим верхнюю, умноженную на $5$, а последнюю строчку преобразуем, умножив первую строчку на 3 и сложив с последней, получаем:

$\begin{array}{ccc|c} -1 & -1 & 1 & -1 \\ 0 & -2 & 3 & -3 \\ 0 & -1 & 0 & -3\\ \end{array}$

Домножим верхнюю и последнюю строчки на $-1$, а также поменяем местами последнюю и среднюю строки:

$\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 0 & 1 & 0 & 3 \\ 0 & -2 & 3 & -3\\ \end{array}$

Далее сложим последнюю строчку с удвоенной средней:

$\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 3 & 3\\ \end{array}$

И разделим последнюю строчку на $3$:

$\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 1\\ \end{array}$

Получаем следующую систему уравнений, равносильную исходной:

$\begin{cases} x_1 + x_2 – x_3 = 1\\ x_2 = 3 \\ x_3 = 1 \end{cases}$

Из верхнего уравнения выражаем $x_1$:

$x1 = 1 + x_3 – x_2 = 1 + 1 – 3 = -1$.

Пример 2

Пример решения системы, заданной с помощью матрицы 4 на 4 методом Гаусса

$\begin{array}{cccc|c} 2 & 5 & 4 & 1 & 20 \\ 1 & 3 & 2 & 1 & 11 \\ 2 & 10 & 9 & 7 & 40\\ 3 & 8 & 9 & 2 & 37 \\ \end{array}$.

В начале меняем местами верхнюю исследующую за ней строчки, чтобы получить в левом верхнем углу $1$:

$\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 11 \\ 2 & 5 & 4 & 1 & 20 \\ 2 & 10 & 9 & 7 & 40\\ 3 & 8 & 9 & 2 & 37 \\ \end{array}$.

Теперь умножим верхнюю строчку на $-2$ и прибавим ко 2-ой и к 3-ьей. К 4-ой прибавляем 1-ую строку, домноженную на $-3$:

$\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 11 \\ 0 & -1 & 0 & -1 & -2 \\ 0 & 4 & 5 & 5 & 18\\ 0 & -1 & 3 & -1 & 4 \\ \end{array}$

Теперь к строке с номером 3 прибавляем строку 2, умноженную на $4$, а к строке 4 прибавляем строку 2, умноженную на $-1$.

$\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 11 \\ 0 & -1 & 0 & -1 & -2 \\ 0 & 0 & 5 & 1 & 10\\ 0 & 0 & 3 & 0 & 6 \\ \end{array}$

Домножаем строку 2 на $-1$, а строку 4 делим на $3$ и ставим на место строки 3.

$\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 11 \\ 0 & 1 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 2\\ 0 & 0 & 5 & 1 & 10 \\ \end{array}$

Теперь прибавляем к последней строке предпоследнюю, домноженную на $-5$.

$\begin{array}{cccc|c} 1 & 3 & 2 & 1 & 11 \\ 0 & 1 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 2\\ 0 & 0 & 0 & 1 & 0 \\ \end{array}$

Решаем полученную систему уравнений:

$\begin{cases} m = 0 \\ g = 2\\ y + m = 2\ \ x + 3y + 2g + m = 11\end{cases}$

$y=2$, $x = 0$.

Метод Гаусса для решения систем линейных алгебраических уравнений общего вида.

Методом Гаусса можно решать системы линейных алгебраических уравнений любого вида без предварительного их исследования на совместность. Процесс последовательного исключения неизвестных переменных позволяет сделать вывод как о совместности, так и о несовместности СЛАУ, а в случае существования решения дает возможность отыскать его.

С точки зрения вычислительной работы метод Гаусса является предпочтительным.

Смотрите его подробное описание и разобранные примеры в статье метод Гаусса для решения систем линейных алгебраических уравнений общего вида.

К началу страницы

Запись общего решения однородных и неоднородных систем линейных алгебраических с помощью векторов фундаментальной системы решений.

В этом разделе речь пойдет о совместных однородных и неоднородных системах линейных алгебраических уравнений, имеющих бесконечное множество решений.

Разберемся сначала с однородными системами.

Фундаментальной системой решенийоднородной системы изpлинейных алгебраических уравнений сnнеизвестными переменными называют совокупность(n – r)линейно независимых решений этой системы, гдеr– порядок базисного минора основной матрицы системы.

Если обозначить линейно независимые решения однородной СЛАУ как X⁽¹⁾, X⁽²⁾, …, X^(n-r)(X⁽¹⁾, X⁽²⁾, …, X^(n-r)– это матрицы столбцы размерностиnна1), то общее решение этой однородной системыпредставляется в виде линейной комбинации векторов фундаментальной системы решений с произвольными постоянными коэффициентамиС₁, С₂, …, С_(n-r), то есть,.

Что обозначает термин общее решение однородной системы линейных алгебраических уравнений (орослау)?

Смысл прост: формула задает все возможные решения исходной СЛАУ, другими словами, взяв любой набор значений произвольных постоянныхС₁, С₂, …, С_(n-r), по формулемы получим одно из решений исходной однородной СЛАУ.

Таким образом, если мы найдем фундаментальную систему решений, то мы сможем задать все решения этой однородной СЛАУ как .

Покажем процесс построения фундаментальной системы решений однородной СЛАУ.

Выбираем базисный минор исходной системы линейных уравнений, исключаем все остальные уравнения из системы и переносим в правые части уравнений системы с противоположными знаками все слагаемые, содержащие свободные неизвестные переменные. Придадим свободным неизвестным переменным значения 1,0,0,…,0и вычислим основные неизвестные, решив полученную элементарную систему линейных уравнений любым способом, например, методом Крамера. Так будет полученоX⁽¹⁾— первое решение фундаментальной системы. Если придать свободным неизвестным значения0,1,0,0,…,0и вычислить при этом основные неизвестные, то получимX⁽²⁾. И так далее. Если свободным неизвестным переменным придадим значения0,0,…,0,1и вычислим основные неизвестные, то получимX^(n-r). Так будет построена фундаментальная система решений однородной СЛАУ и может быть записано ее общее решение в виде.

Для неоднородных систем линейных алгебраических уравнений общее решение представляется в виде , где- общее решение соответствующей однородной системы, а- частное решение исходной неоднородной СЛАУ, которое мы получаем, придав свободным неизвестным значения0,0,…,0и вычислив значения основных неизвестных.

Разберем на примерах.

Пример.

Найдите фундаментальную систему решений и общее решение однородной системы линейных алгебраических уравнений .

Решение.

Ранг основной матрицы однородных систем линейных уравнений всегда равен рангу расширенной матрицы. Найдем ранг основной матрицы методом окаймляющих миноров. В качестве ненулевого минора первого порядка возьмем элемент a_{1 1} = 9основной матрицы системы. Найдем окаймляющий ненулевой минор второго порядка:

Минор второго порядка, отличный от нуля, найден. Переберем окаймляющие его миноры третьего порядка в поисках ненулевого:

Все окаймляющие миноры третьего порядка равны нулю, следовательно, ранг основной и расширенной матрицы равен двум. Базисным минором возьмем . Отметим для наглядности элементы системы, которые его образуют:

Третье уравнение исходной СЛАУ не участвует в образовании базисного минора, поэтому, может быть исключено:

Оставляем в правых частях уравнений слагаемые, содержащие основные неизвестные, а в правые части переносим слагаемые со свободными неизвестными:

Построим фундаментальную систему решений исходной однородной системы линейных уравнений. Фундаментальная система решений данной СЛАУ состоит из двух решений, так как исходная СЛАУ содержит четыре неизвестных переменных, а порядок ее базисного минора равен двум. Для нахождения X⁽¹⁾придадим свободным неизвестным переменным значенияx₂ = 1, x₄ = 0, тогда основные неизвестные найдем из системы уравнений.

Решим ее методом Крамера:

Таким образом, .

Теперь построим X⁽²⁾. Для этого придадим свободным неизвестным переменным значенияx₂ = 0, x₄ = 1, тогда основные неизвестные найдем из системы линейных уравнений.

Опять воспользуемся методом Крамера:

Получаем .

Так мы получили два вектора фундаментальной системы решений и, теперь мы можем записать общее решение однородной системы линейных алгебраических уравнений:, гдеC₁иC₂– произвольные числа.

Пример.

Найдите общее решение неоднородной системы линейных алгебраических уравнений .

Решение.

Общее решение этой системы уравнений будем искать в виде .

Исходной неоднородной СЛАУ соответствует однородная система общее решение которой мы нашли в предыдущем примере.

Следовательно, нам осталось найти частное решение неоднородной системы линейных алгебраических уравнений .

Ранг основной матрицы системы равен двум, ранг расширенной матрицы системы также равен двум, так как все миноры третьего порядка, окаймляющие минор , равны нулю. Также примем минорв качестве базисного, исключим третье уравнение из системы и перенесем слагаемые со свободными неизвестными в правые части уравнений системы:

Для нахождения придадим свободным неизвестным переменным значенияx₂ = 0 и x₄ = 0, тогда система уравнений примет вид, откуда методом Крамера найдем основные неизвестные переменные:

Имеем , следовательно,гдеC₁иC₂– произвольные числа.

Следует заметить, что решения неопределенной однородной системы линейных алгебраических уравнений порождают линейное пространстворазмерности(n – r), базисом которого является фундаментальная система решений.

К началу страницы

2.3.6. Примеры решения задач по теме «Системы уравнений общего вида. Метод Гаусса»

Задача 1.

Указать базисный минор матрицы

Указание

Определите вначале ранг матрицы А, а затем найдите ненулевой минор, порядок которого равен R(A).

Решение

Определим R(A). Вторая и четвертая строки А равны, поэтому после вычитания из 4-й строки 2-й получаем:

Вычислим минор полученной матрицы, составленный из первых трех столбцов:

Таким образом, найден минор максимально возможного (3-го) порядка, не равный нулю. Следовательно, ранг матрицы А равен рангу преобразованной матрицы, то есть равен 3, а рассмотренный минор является базисным.

Ответ:

Задача 2.

Определить количество решений системы линейных уравнений

.

Указание

Сравните ранги матрицы системы и расширенной матрицы.

Решение

Сравним ранги матрицы системы

И расширенной матрицы

.

Для удобства вычислений будем искать ранг матрицы А1, отделив ее последний столбец вертикальной чертой. Тогда столбцы, стоящие слева от черты, образуют матрицу А, и мы одновременно найдем ранги обеих матриц.

А1 ~ .

Вычтем из второй строки удвоенную первую, а из третьей – первую, умноженную на 3:

А1 ~ ~ .

Таким образом, R(A) = 2, a R(A1) = 3, следовательно, система не имеет решений.

Ответ: система несовместна.

Задача 3.

Найти общее решение линейной системы

.

Указание

Убедившись в том, что система совместна, определите базисные и свободные неизвестные и выразите базисные неизвестные через свободные.

Решение

Найдем R(A) и R(A1):

Итак, R = R(A) = R(A1) = 2, а число неизвестных П = 5. Следовательно, R < N, и система имеет бесконечно много решений (совместна, но не определена).

Число базисных неизвестных равно R, то есть двум. Выберем в качестве базисных неизвестных Х1 и Х2, коэффициенты при которых входят в базисный минор преобразованной матрицы А: .

Соответственно Х3, Х4, Х5 – свободные неизвестные.

Запишем систему, равносильную исходной, коэффициентами в которой являются элементы полученной матрицы:

И выразим базисные неизвестные через свободные:

.

Получено общее решение системы. Одно из частных решений можно найти, положив все свободные неизвестные равными нулю: Х3 = Х4 = Х5 = 0. Тогда

Ответ:

Задача 4.

Найти общее решение системы, выразив в ответе первые неизвестные через последние:

Указание

Приведите расширенную матрицу к виду

Решение

Минор, состоящий из первых трех столбцов полученной матрицы,

Поэтому R(A) = R(A1) = 3, выбранный минор является базисным, а Х1, Х2, Х3, коэффициенты при которых составляют базисный минор, – базисными неизвестными. Тогда свободное неизвестное – Х4, и система, равносильная исходной, имеет вид:

Откуда

Ответ:

Задача 5.

Найти фундаментальную систему решений однородной линейной системы

Указание

Количество решений, образующих фундаментальную систему, равно числу

Свободных неизвестных. Задайте свободным неизвестным значения 1,0,0; 0,1,0; 0,0,1 и вычислите соответствующие значения базисных неизвестных.

Решение

Количество решений, образующих фундаментальную систему, равно числу Свободных неизвестных.

Матрица А1 отличается от матрицы А только добавлением нулевого столбца свободных членов, поэтому все ее ненулевые миноры являются минорами матрицы А, то есть R(A) = R(A1). Найдем R(A):

Выберем в качестве базисного минора

Значит, R(A) = 2. Пусть Х4, Х5 – базисные неизвестные, Х1, Х2, Х3 – свободные неизвестные. Запишем для них новую систему:

Откуда

Фундаментальная система решений состоит из трех столбцов. Рассмотрим три набора значений свободных неизвестных:

1) Х1 = 1, Х2 = Х3 = 0.

Тогда Х4 = -0,2, Х5 = 1,2, и решение можно записать в виде столбца

2) Х1 = 0, Х2 = 1, Х3 = 0.

При этом Х4 = 1,2, Х5 = 3,8, и следующее решение системы имеет вид

3) Х1 = Х2 = 0, Х3 = 1. Отсюда Х4 = -0,8, Х5 = -0,2, и последний столбец

Фундаментальная система решений, построенная при таком выборе свободных неизвестных, называется Нормальной. Поскольку столбцы свободных неизвестных , , линейно независимы, это гарантирует линейную независимость решений Х1, Х2, Х3.

Итак, в качестве фундаментальной системы решений можно выбрать

При этом любое решение данной системы имеет вид: Х = с1Х1 + С2Х2 + С3Х3, где С1, С2, С3 – произвольные постоянные. Эта формула задает общее решение системы.

Ответ:

Задача 6.

Составить однородную систему из двух уравнений, для которой столбцы

Образуют фундаментальную систему решений.

Указание

Пусть искомая система имеет вид:

Подставьте вместо Х1, …, Х5 элементы столбцов Х1, Х2, Х3 и решите полученную систему уравнений для коэффициентов Aij.

Решение

Существует бесконечно много систем однородных линейных уравнений, для каждой из которых фундаментальная система решений имеет указанный вид. Число уравнений в таких системах может быть различным. При этом можно указать их наименьшее требуемое количество, а увеличивать их число можно неограниченно.

Определим вначале, из какого наименьшего числа уравнений может состоять такая система.

Число элементов каждого столбца равно пяти, следовательно, в системе пять неизвестных (П = 5). Количество столбцов, составляющих фундаментальную систему, равно трем, то есть N – R = 3, поэтому R = 5 – 3 = 2. Значит, матрица А должна иметь по крайней мере 2 строки. Следовательно, система уравнений с заданной фундаментальной системой решений может состоять из двух и более уравнений.

Пусть искомая система имеет вид:

Подставим вместо Х1, …, Х5 элементы столбцов Х1, Х2, Х3. Получим:

Разобьем полученные 6 уравнений на две системы, одна из которых содержит A1I, а вторая – A2I:

Найдем какое-либо частное решение этой системы. Приведем ее матрицу к треугольному виду:

Откуда

Следовательно,

Выберем А14 = А15 = 4, тогда А11 = 0, А12 = 8, А13 = -4.

2) Так же выглядит общее решение системы для A2I:

Выберем свободные неизвестные так, чтобы получить решение, линейно независимое с предыдущим.

Пусть А24 = 4, А25 = 0, тогда А21 = 5, А22 = 5, А23 = -3.

Итак, используя найденные значения коэффициентов, можно составить линейную однородную систему:

Фундаментальная система решений которой имеет вид, приведенный в условии задачи.

Ответ:

Задача 7.

Найти общее решение неоднородной линейной системы

С помощью фундаментальной системы решений соответствующей однородной системы.

Указание

Убедитесь в том, что система совместна. Затем составьте соответствующую однородную систему и найдите для нее фундаментальную систему решений. Далее используйте то, что общее решение неоднородной системы линейных уравнений является суммой общего решения соответствующей однородной системы и частного решения неоднородной системы.

Решение

Убедимся в том, что система совместна:

Итак, R(A) = R(A1) = 2 – система совместна.

Составим по преобразованной матрице однородную систему:

И найдем для нее фундаментальную систему решений:

Фундаментальная система решений может быть выбрана так:

Общее решение неоднородной системы линейных уравнений является суммой общего решения соответствующей однородной системы и частного решения неоднородной системы.

Теперь найдем какое-нибудь частное решение неоднородной системы

Положим Х3 = Х4 = Х5 = 0, тогда . Следовательно,

и общее решение системы имеет вид:

Х = с1Х1 + С2Х2 + С3Х3 + Хчастн, где С1, С2, С3 – произвольные постоянные.

Ответ:

Задача 8.

Решить систему методом Гаусса:

.

Указание

Поменяйте местами 1-е и 2-е уравнения, чтобы в первом уравнении коэффициент при Х равнялся единице, а затем исключите Х из второго и третьего уравнений.

Решение

Метод Гаусса заключается в последовательном исключении неизвестных из уравнений системы. Для удобства его применения поменяем местами 1-е и

2-е уравнения, чтобы в первом уравнении коэффициент при Х равнялся единице:

Теперь исключим Х из второго и третьего уравнений. Для этого вычтем из второго уравнения первое, умноженное на 3, а из третьего – первое, умноженное на 2:

Далее можно легко исключить Z из третьего уравнения, если прибавить к нему второе:

Из последнего уравнения получаем, что У = 0. Подставляя это значение в первое и второе уравнения, находим остальные неизвестные: Z = 3, Х = 1.

Ответ: Х = 1, У = 0, Z = 3.

При применении метода Гаусса совсем не обязательно приводить систему к «классическому» треугольному виду: . Достаточно, чтобы матрица коэффициентов, например, системы трех уравнений с тремя неизвестными содержала два нуля в одном столбце и одновременно два нуля в одной строке, причем один из нулей стоял на пересечении этих строки и столбца.

Задача 9.

Решить систему методом Гаусса:

Указание

Исключите Х2 из 2-го и 4-го уравнений, используя 1-е уравнение, а затем вычтите из 3-го уравнения 2-е, чтобы исключить Х3.

Решение

Исключим Х2 из 2-го и 4-го уравнений. Для этого из 2-го уравнения вычтем 1-е, а к 4-му прибавим 1-е, умноженное на 2:

Вычтем из 3-го уравнения 2-е, чтобы исключить Х3:

Теперь вычтем из 4-го уравнения удвоенное 3-е:

Из последнего уравнения находим . Тогда из 3-го уравнения Х1 = 0, из 2-го , из 1-го Х2 = 2.

Ответ:

< Предыдущая		Следующая >

Метод Гаусса для решения матриц. Решение системы линейных уравнений методом Гаусса :: SYL.ru

Еще с начала XVI-XVIII веков математики усиленно начали изучать функции, благодаря которым так много в нашей жизни изменилось. Компьютерная техника без этих знаний просто не существовала бы. Для решения сложных задач, линейных уравнений и функций были созданы различные концепции, теоремы и методики решения. Одним из таких универсальных и рациональных способов и методик решения линейных уравнений и их систем стал и метод Гаусса. Матрицы, их ранг, детерминант — все можно посчитать, не используя сложных операций.

Что представляет собой СЛАУ

В математике существует понятие СЛАУ — система линейных алгебраических уравнений. Что же она собой представляет? Это набор из m уравнений с искомыми n неизвестными величинами, обычно обозначающимися как x, y, z, или x₁, x₂… x_n, или другими символами. Решить методом Гаусса данную систему — означает найти все искомые неизвестные. Если система имеет одинаковое число неизвестных и уравнений, тогда она называется системой n-го порядка.

Наиболее популярные методы решения СЛАУ

В учебных заведениях среднего образования изучают различные методики решения таких систем. Чаще всего это простые уравнения, состоящие из двух неизвестных, поэтому любой существующий метод для поиска ответа на них не займет много времени. Это может быть как метод подстановки, когда из одного уравнения выводится другое и подставляется в изначальное. Или метод почленного вычитания и сложения. Но наиболее легким и универсальным считается метод Гаусса. Он дает возможность решать уравнения с любым количеством неизвестных. Почему именно эта методика считается рациональной? Все просто. Матричный способ хорош тем, что здесь не требуется по несколько раз переписывать ненужные символы в виде неизвестных, достаточно проделать арифметические операции над коэффициентами — и получится достоверный результат.

Где используются СЛАУ на практике

Решением СЛАУ являются точки пересечения прямых на графиках функций. В наш высокотехнологический компьютерный век людям, которые тесно связаны с разработкой игр и прочих программ, необходимо знать, как решать такие системы, что они представляют и как проверить правильность получившегося результата. Наиболее часто программисты разрабатывают специальные программы-вычислители линейной алгебры, сюда входит и система линейных уравнений. Метод Гаусса позволяет высчитать все существующие решения. Также используются и другие упрощенные формулы и методики.

Критерий совместимости СЛАУ

Такую систему можно решить только в том случае, если она совместима. Для понятности представим СЛАУ в виде Ax=b. Она имеет решение, если rang(A) равняется rang(A,b). В этом случае (A,b) – это матрица расширенного вида, которую можно получить из матрицы А, переписав ее со свободными членами. Выходит, что решить линейные уравнения методом Гаусса достаточно легко.

Возможно, некоторые обозначения не совсем понятны, поэтому необходимо рассмотреть все на примере. Допустим, есть система: x+y=1; 2x-3y=6. Она состоит всего из двух уравнений, в которых 2 неизвестные. Система будет иметь решение только в том случае, если ранг ее матрицы будет равняться рангу расширенной матрицы. Что такое ранг? Это число независимых строк системы. В нашем случае ранг матрицы 2. Матрица А будет состоять из коэффициентов, находящихся возле неизвестных, а в расширенную матрицу вписываются и коэффициенты, находящиеся за знаком «=».

Почему СЛАУ можно представить в матричном виде

Исходя из критерия совместимости по доказанной теореме Кронекера-Капелли, систему линейных алгебраических уравнений можно представить в матричном виде. Применяя каскадный метод Гаусса, можно решить матрицу и получить единственный достоверный ответ на всю систему. Если ранг обычной матрицы равняется рангу ее расширенной матрицы, но при этом меньше количества неизвестных, тогда система имеет бесконечное количество ответов.

Преобразования матриц

Прежде чем переходить к решению матриц, необходимо знать, какие действия можно проводить над их элементами. Существует несколько элементарных преобразований:

• Переписывая систему в матричный вид и осуществляя ее решение, можно умножать все элементы ряда на один и тот же коэффициент.
• Для того чтобы преобразовать матрицу в канонический вид, можно менять местами два параллельных ряда. Канонический вид подразумевает, что все элементы матрицы, которые расположены по главной диагонали, становятся единицами, а оставшиеся — нулями.
• Соответствующие элементы параллельных рядов матрицы можно прибавлять один к другому.

Метод Жордана-Гаусса

Суть решения систем линейных однородных и неоднородных уравнений методом Гаусса в том, чтобы постепенно исключить неизвестные. Допустим, у нас есть система из двух уравнений, в которых две неизвестные. Чтобы их найти, необходимо проверить систему на совместимость. Уравнение методом Гаусса решается очень просто. Необходимо выписать коэффициенты, находящиеся возле каждого неизвестного в матричный вид. Для решения системы понадобится выписать расширенную матрицу. Если одно из уравнений содержит меньшее количество неизвестных, тогда на место пропущенного элемента необходимо поставить «0». К матрице применяются все известные методы преобразования: умножение, деление на число, прибавление соответствующих элементов рядов друг к другу и другие. Получается, что в каждом ряду необходимо оставить одну переменную со значением «1», остальные привести к нулевому виду. Для более точного понимания необходимо рассмотреть метод Гаусса на примерах.

Простой пример решения системы 2х2

Для начала возьмем простенькую систему алгебраических уравнений, в которой будет 2 неизвестных.

Перепишем ее в расширенную матрицу.

Чтобы решить данную систему линейных уравнений, требуется проделать всего две операции. Нам необходимо привести матрицу к каноническому виду, чтобы по главной диагонали стояли единицы. Так, переводя с матричного вида обратно в систему, мы получим уравнения: 1x+0y=b1 и 0x+1y=b2, где b1 и b2 — получившиеся ответы в процессе решения.

1. Первое действие при решении расширенной матрицы будет таким: первый ряд необходимо умножить на -7 и прибавить соответственно отвечающие элементы ко второй строке, чтобы избавиться от одного неизвестного во втором уравнении.
2. Так как решение уравнений методом Гаусса подразумевает приведение матрицы к каноническому виду, тогда необходимо и с первым уравнением проделать те же операции и убрать вторую переменную. Для этого вторую строку отнимаем от первой и получаем необходимый ответ — решение СЛАУ. Или, как показано на рисунке, вторую строку умножаем на коэффициент -1 и прибавляем к первой строке элементы второго ряда. Это одно и то же.

Как видим, наша система решена методом Жордана-Гаусса. Переписываем ее в необходимую форму: x=-5, y=7.

Пример решения СЛАУ 3х3

Предположим, что у нас есть более сложная система линейных уравнений. Метод Гаусса дает возможность высчитать ответ даже для самой, казалось бы, запутанной системы. Поэтому, чтобы более глубоко вникнуть в методику расчета, можно переходить к более сложному примеру с тремя неизвестными.

Как и в прежнем примере, переписываем систему в вид расширенной матрицы и начинаем приводить ее к каноническому виду.

Для решения этой системы понадобится произвести гораздо больше действий, чем в предыдущем примере.

1. Сначала необходимо сделать в первом столбце один единичный элемент и остальные нули. Для этого умножаем первое уравнение на -1 и прибавляем к нему второе уравнение. Важно запомнить, что первую строку мы переписываем в изначальном виде, а вторую — уже в измененном.
2. Далее убираем эту же первую неизвестную из третьего уравнения. Для этого элементы первой строки умножаем на -2 и прибавляем их к третьему ряду. Теперь первая и вторая строки переписываются в изначальном виде, а третья — уже с изменениями. Как видно по результату, мы получили первую единицу в начале главной диагонали матрицы и остальные нули. Еще несколько действий, и система уравнений методом Гаусса будет достоверно решена.
3. Теперь необходимо проделать операции и над другими элементами рядов. Третье и четвертое действие можно объединить в одно. Нужно разделить вторую и третью строку на -1, чтобы избавиться от минусовых единиц по диагонали. Третью строку мы уже привели к необходимому виду.
4. Дальше приведем к каноническому виду вторую строку. Для этого элементы третьего ряда умножаем на -3 и прибавляем их ко второй строчке матрицы. Из результата видно, что вторая строка тоже приведена к необходимой нам форме. Осталось проделать еще несколько операций и убрать коэффициенты неизвестных из первой строки.
5. Чтобы из второго элемента строки сделать 0, необходимо умножить третью строку на -3 и прибавить ее к первому ряду.
6. Следующим решающим этапом будет прибавление к первой строке необходимые элементы второго ряда. Так мы получаем канонический вид матрицы, а, соответственно, и ответ.

Как видно, решение уравнений методом Гаусса довольно простое.

Пример решения системы уравнений 4х4

Некоторые более сложные системы уравнений можно решить методом Гаусса посредством компьютерных программ. Необходимо вбить в существующие пустые ячейки коэффициенты при неизвестных, и программа сама пошагово рассчитает необходимый результат, подробно описывая каждое действие.

Ниже описана пошаговая инструкция решения такого примера.

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

• Далее меняются все строки местами, чтобы можно было выразить по главной диагонали единичные элементы.

• И производятся все необходимые арифметические операции, чтобы привести расширенную матрицу к каноническому виду. Необходимо понимать, что не всегда ответ на систему уравнений — это целые числа. Иногда решение может быть из дробных чисел.

Проверка правильности решения

Метод Жордана-Гаусса предусматривает проверку правильности результата. Для того чтобы узнать, правильно ли посчитаны коэффициенты, необходимо всего-навсего подставить результат в изначальную систему уравнений. Левая сторона уравнения должна соответствовать правой стороне, находящейся за знаком «равно». Если ответы не совпадают, тогда необходимо пересчитывать заново систему или попробовать применить к ней другой известный вам метод решения СЛАУ, такой как подстановка или почленное вычитание и сложение. Ведь математика – это наука, которая имеет огромное количество различных методик решения. Но помните: результат должен быть всегда один и тот же, независимо от того, какой метод решения вы использовали.

Метод Гаусса: наиболее часто встречающиеся ошибки при решении СЛАУ

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

Еще одной из главных ошибок может быть неправильное выписывание конечного результата. Нужно четко понимать, что первый коэффициент будет соответствовать первому неизвестному из системы, второй — второму, и так далее.

Метод Гаусса подробно описывает решение линейных уравнений. Благодаря ему легко произвести необходимые операции и найти верный результат. Кроме того, это универсальное средство для поиска достоверного ответа на уравнения любой сложности. Может быть, поэтому его так часто используют при решении СЛАУ.

Метод гаусса примеры с выбором главного элемента

Содержание

1. Материал из MachineLearning.
2. Содержание
3. Постановка задачи
4. Описание метода
5. Анализ метода
6. Способы оценки ошибок
7. Улучшение метода исключения Гаусса
8. Выбор главного элемента
9. Итеративное улучшение результата
10. Числовой пример
11. Программа, реализующая метод на C++
12. Рекомендации пользователю

Московский Государственный Технически Университет

«МАМИ»

Лабораторная работа №3 по курсу «Вычислительная Математика»

«РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»

3. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Справочная информация

Численные методы решения систем линейных алгебраических уравнений

,

записываемых в матричной форме в виде

,

,

делятся на точные и итерационные. Они используются для систем, у которых количество неизвестных равно количеству уравнений и матрица A — не вырождена (её определитель не равен нулю). Точными методами условно называют методы, которые дают решение задачи посредством конечного числа арифметических операций. Итерационные методы позволяют получить решение системы как предел бесконечной последовательности его приближений. При применении итерационных методов существенным вопросом является вопрос об их сходимости.

Точные методы, к которым относятся метод Гауссаи его разновидности, не имеют дополнительных ограничений на свойства матрицы системы.

В основе метода Гаусса лежит идея последовательного исключения неизвестных, приводящая исходную систему с квадратной матрицей к легко разрешимой системе с верхней треугольной матрицей

.

Данное преобразование может быть осуществлено многими способами. Однако все они основаны на свойстве систем, которое заключается в неизменности их решений при умножении любого уравнения на отличную от нуля постоянную или его замене на сумму с любым другим уравнением.

Один из простейших способов исключения состоит в следующем. Первое уравнение системы

,

которое на этом шаге считается ведущим, нормируется – делится на значение диагонального элемента a₁₁

,

.

Если в исходной системе a₁₁= 0, то в качестве первого уравнения следует взять любое другое с ненулевым первым коэффициентом, поменяв их местами. Полученное уравнение умножается на первый коэффициент второго уравнения a₂₁ и вычитается из него. В результате во втором уравнении пропадает слагаемое a₂₁x₁, содержащее первое неизвестное x₁. Такие же операции проводятся со всеми последующими уравнениями. В результате система уравнений принимает вид

.

Далее процесс повторяется. За ведущее берется второе уравнение и исключается неизвестное x₂ из всех уравнений, начиная с третьего

.

Таким образом, за n шагов система уравнений последовательно сводится к треугольному виду, при этом для последнего уравнения выполняется только операция нормирования:

.

Полученная система с верхней треугольной матрицей может быть легко разрешена относительно неизвестных. Последнее уравнение системы определяет значение x_n, что позволяет определить x_n–1 из предпоследнего уравнения как

.

Выполняя аналогичные подстановки найденных неизвестных в вышестоящие уравнения, удается определить все компоненты решения x_n–2. x₂, x₁.

Метод Гаусса даёт точное решение, если все исходные данные точны и все вычисления производятся точно. На практике, при выполнении вычислений, неизбежно проводятся округления. Ошибка округлений вносит погрешность в решение метода Гаусса. Таким образом, при операциях с округленными десятичными числами метод Гаусса даёт не точное решение x_т системы линейных алгебраических уравнений, а некоторое приближённое решение , где

, .

Степень отличия приближённого решения от точного определяется длиной разрядной сетки ЭВМ: чем больше разрядов в ней учитывается, тем это отличие меньше.

При определении погрешности вектора решения необходимо учитывать, что его компоненты в общем случае могут иметь разную погрешность. В силу этого погрешность решения принято оценивать по его норме

или или

,

где двойные модульные скобки обозначают норму вектора.

Для определения величины погрешности полученного решения на практике используют следующий алгоритм вычисления её главной части. Сначала по имеющемуся решению пересчитывается вектор правых частей системы

,

а затем посредством повторного решения системы уравнений

находится вектор погрешностей . С его помощью определяется как реальная абсолютная погрешность полученного решения

или или ,

так и его относительная погрешность

.

Величина погрешности решения системы уравнений, получаемого методом Гаусса, зависит от двух основных факторов. Первый из них, как это было сказано выше – длина разрядной сетки, используемой в процессе вычислений, а второй – обусловленность матрицы системы. Обусловленность матрицы можно рассматривать как степень её чувствительности к накоплению ошибок округления в процессе преобразований. Снижение величины погрешности решения может быть достигнуто увеличением длины разрядной сетки. Повлиять на величину погрешности посредством изменения степени обусловленности матрицы системы невозможно, так как она является одной из её характеристик и изменение степени обусловленности матрицы требует изменения самой матрицы.

Метод Гаусса с выбором главного элемента

Основное накопление погрешностей решения в методе Гаусса происходит на этапе приведения системы к треугольному виду. Механизм накопления основной части этой погрешности заключается в привнесении погрешностей вычисления коэффициентов ведущего уравнения в коэффициенты последующих уравнений при исключении каждого очередного неизвестного. Анализ соотношений метода Гаусса показывает, что погрешности вычисления коэффициентов ведущего уравнения привносятся в соответствующие коэффициенты всех последующих уравнений в долях отношений этих коэффициентов к диагональному (главному) коэффициенту ведущего уравнения. В связи с этим привносимая погрешность будет тем меньше, чем меньше доли этих отношений. Поэтому в методе Гаусса с выбором главного элемента на каждом шаге исключения i-го неизвестного в качестве ведущего используетсяуравнение (с i-го по n-ое), содержащее максимальный по модулю коэффициент – главныйэлемент. При этом в качестве него может использоваться один из коэффициентов i-го столбца, i-ой строки или всей непреобразованной части матрицы. Первый подход называется выбором главного элементапостолбцу, второй – по строке, а третий – по всейматрице. При использовании двух последних происходит перестановка столбцов матрицы системы. Это приводит к изменению порядка следования компонент вектора неизвестных и требует его восстановления по окончании процесса решения.

В качестве примера применения метода Гаусса можно рассмотреть задачу отыскания решения следующей системы уравнений

при ограничении разрядной сетки вычислений до трёх знаков и с оценкой погрешности получаемого решения.

Поставленная задача будет решаться методом Гаусса с выбором главного элемента по столбцу.

а. Выбор главного элемента среди элементов первого столбца

.

б. Нормировка первого уравнения

.

в. Исключение элементов первого столбца

.

г. Выбор главного элемента среди элементов второго столбца второго и третьего уравнений

.

д. Нормировка второго уравнения

.

е. Исключение элементов второго столбца

.

ё. Нормировка последнего уравнения

.

,

.

В итоге получено решение системы уравнений

.

3. Погрешность найденного решения.

а. Пересчёт вектора правых частей системы

б. Формирование системы уравнений, определяющей погрешности решения

,

в. Решение системы относительно погрешностей оно выполняется аналогично пунктам 1 и 2. Прямой ход (пункт 1) даёт следующую систему с верхней треугольной матрицей

,

а обратный ход позволяет получить решение

.

г. Оценка абсолютной и относительной погрешностей решения системы линейных алгебраических уравнений

,

,

.

Реализация описанного метода без нахождения погрешности решения в рамках программы Excel приведена на рис.1.

О выборе метода решения систем уравнений

Каждый из рассмотренных методов имеет свои достоинства и недостатки. В частности, метод Гаусса позволяет получить решение за конечное число шагов. Для этого требуется выполнить n(n 2 + 3n – 1)/3 операций умножения и деления и n(n – 1)(2n + 5)/6 операций сложения и вычитания, количество которых при больших порядках системы (n > 100) можно принять равным n 3 /3 в обоих случаях. Однако его методические ошибки, связанные с размером разрядной сетки вычислений, резко нарастают с увеличением порядка системы и не позволяют применять его для систем высоких порядков без использования специальных приёмов.

Итерационные методы позволяют получать решение систем бóльшего порядка. Для выполнения каждой итерации с их помощью необходимо выполнить n(n + 1) операций умножения и деления и столько же операций сложения и вычитания. При больших порядках системы уравнений (n > 100) их количество можно принять равным n 2 . Из сравнения трудоёмкости итерационных методов и метода Гаусса следует оценка, которой можно руководствоваться при окончательном выборе метода решения системы при необходимости его многократного нахождения. Если количество итераций, требуемое для получения решения системы итерационными методами, не превышает n/3, то выгоднее применять их, а не методы типа Гаусса. Однако здесь следует помнить, что итерационные методы требуют, чтобы матрица системы обладала определёнными свойствами, обеспечивающими их сходимость. Необходимо также отметить, что выполнение этих требований часто не гарантирует высокой скорости их сходимости.

МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.

1. Основная идея метода. Может оказаться, что система

имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.

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

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений

Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что си­стема (2) переписывается в виде

и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения про­водится соответствующая перенумерация переменных.

Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что . Перепишем систему (2) в виде

и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.

Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максималь­ный по модулю элемент среди всех элементов матрицы системы.

2. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде

где -элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.

ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квад­ратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.

ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок на­зывается матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.

Например, элементарными матрицами перестановок третьего по­рядка являются матрицы

Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения .

1) Произведение двух (а следовательно, и любого числа) элементар­ных матриц перестановок является матрицей перестановок (не обязательно элементарной).

2) Для любой квадратной матрицы А матрица отличается от А перестановкой к-й и l-é ñòðîê.

3) Для любой квадратной матрицы А матрица отличается от А перестановкой к-го и l-го столбцов.

Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка:

Система имеет вид (1), где

Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе

Систему (6) можно записать в виде

т.е. она получается из системы (4) путем умножения на матрицу

Далее, к системе (6) надо применить первый шаг обычного метода ис­ключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу

В результате от системы (7) перейдем к эквивалентной системе

или в развернутом виде

Из последних двух уравнений системы (9) надо теперь исключить перемен­ное . Поскольку максимальным элементом первого столбца уко­роченной системы

является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе

которую можно записать в матричном виде как

Таким образом система (12) получена из (8) применением элемен-тар­ной матрицы перестановок

Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу

В результате получим систему

Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением

что эквивалентно умножению (13) на элементарную нижнюю треугольную мат­рицу

Таким образом, для рассмотренного примера процесс исключения Гаусса с вы­бором главного элемента по столбцу записывается в

По построению матрица

является верхней треугольной матрицей с единичной главной диаго­налью.

Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матри­цами могут присутствовать элементарные матрицы перестановок .

Покажем еще, что из (16) следует разложение

где L —нижняя треугольная матрица, имеющая обратную, P – матрица перестановок.

Для этого найдем матрицу

По свойству 2) матрица получается из матрицы переста­новкой второй и третьей строк,

Матрица согласно свойству 3) получается из перестановкой второго и третьего столбцов

т.е. -нижняя треугольная матрица, имеющая обратную.

Из (18), учитывая равенство , получим

Отсюда и из (16) видно, что

где обозначено . Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к мат­рице РА, т. е. к системе, полученной из исходной системы перестанов­кой некоторых уравнений.

3. Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1).

А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде

где — элементарные матрицы перестановок такие, что

и -элементарные нижние треугольные матрицы.

Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к си­стеме

где Р – некоторая матрица перестановок.

Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.

ТЕОРЕМА 1. Если то существует матрица перестано-

вок Р такая, что матрица РА имеет отличные от нуля угловые ми-

Доказательство в п.4.

СЛЕДСТВИЕ. Если то существует матрица престана-

вок Р такая, что справедливо разложение

где L— нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента.

4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А.

Если то утверждение теоремы выполняется при Р=Е, где Е – единичная матрица второго порядка. Если , то , т.к. При этом у матрицы

все угловые миноры отличны от нуля.

Пусть утверждение теоремы верно для любых квадратных матриц порядка m-1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки

Достаточно рассмотреть два случая : и . В первом случае по предположению индукции существует матрица перестановок порядка m-1 такая, что имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок

причем . Тем самым все угловые миноры матрицы РА отличны от нуля.

Рассмотрим второй случай, когда . Т.к. , найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например,

Переставляя в матрице А строки с номерами l и m, получим матрицу , у которой угловой минор порядка m-1 имеет вид

и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.

Материал из MachineLearning.

Содержание

Постановка задачи

Дана система линейных алгебраических уравнений (СЛАУ), состоящая из уравнений с неизвестными :

Предполагается, что существует единственное решение системы, то есть .

В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.

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

Процесс решения системы линейных уравнений

по методу Гаусса состоит из 2х этапов:

• Прямой ход Система (2) приводится к треугольному виду

1. Предполагаем, что . Тогда первое уравнение системы (2) делим на коэффициент , в результате получаем уравнение . Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент . В результате система преобразуются к виду: 2. В предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех последующих уравнений и т.д. 3. Получаем систему уравнений с треугольной матрицей:

• Обратный ход Непосредственное определение неизвестных

1. Из го уравнения системы (3) определяем 2. Из го — определяем и т.д.

Анализ метода

Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные ( матрица и правая часть уравнения — ) заданы точно и вычисление ведется без округлений. Для получения решения требуется умножений и делений, то есть порядка операций.

Условия, при которых метод выдает точное решение, на практике не выполнимы — неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой (1) рассмотрим возмущенную систему:

Пусть введена некоторая норма . — называется числом обусловленности матрицы .

Возможны 3 случая:

Число обусловленности матрицы всегда . Если оно велико ( ) , то говорят, что матрица плохо обусловлена. В этом случае малые возмущения правых частей системы (1), вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей , то погрешность решения будет .

Проиллюстрируем полученные результаты на следующем числовом примере: Дана система

Она имеет решение .

Теперь рассмотрим возмущенную систему:

Решением такой системы будет вектор .

При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения. Объяснить такую «ненадежность» решения можно тем, что матрица почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике:

Такой результат можно было предвидеть в силу плохой обусловленностью матрицы : [1]

Вычисление является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.

Способы оценки ошибок

Составляем контрольный столбец , состоящий из контрольных элементов системы:

При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнеий. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности.

2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.

Задается некоторый ветор с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения [1] . Вычисляется вектор , и на ряду с исходной системой уравнения решается система .

Пусть и — реально получаемые решения этих систем. Суждение о погрешности искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины и , отличаются не в очень большое число раз.

3) Изменение масштабов — прием, применяющийся для получения представления о реальной величине погрешности, возникающей за счет округлений при вычислениях.

Наряду с исходной системой тем же методом решается система

Если бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: . Поэтому при и , не являющихся степенями двойки, сравнение векторов и дает представление о величине вычислительной погрешности [1]

Улучшение метода исключения Гаусса

Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.

Выбор главного элемента

Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая -я строка умножается на коэффициенты .Если коэффициенты 1 » alt= » >1 » />, то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:

Пусть по ходу исключения неизвестных получена система уравнений:

Найдем такое , что и поменяем местами -е и -е уровнения.

Такое преобразование во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.

Итеративное улучшение результата

Если есть подозрение, что полученное решение сильно искажено, то можно улучшить результат следующим образом. Величина называется невязкой. Погрешность удовлетворяет системе уравнений

Решая эту систему, получаем приближение к и полагаем

Если точность данного приближения неудовлетворительна, то повторяем эту операцию.

Процесс можно продолжать до тех пор, пока все компоненты не станут достаточно малыми. При этом нельзя останавливать вычисления только потому, что все компоненты вектора невязки стали достаточно малыми: это может быть результатом плохой обусловленности матрицы коэффициентов.

Числовой пример

Рассмотрим для примера матрицу Вандермонда размером 7х7 и 2 различные правые части:

Данные системы были решены двумя способами. Тип данных — float. B итоге получили следующие результаты:

Способ решения
Номер столбца в
Номер итерации
x1
x2
x3
x4
x5
x6
x7
Абс. погрешность
Отн. погрешность
Невязка

Обычный метод
1		2
1	2	1	2

0.99999110.99999611.0001917.4774e-0052,33e-0080.99840410.99937511.0066710.002637271,12e-0060.98532810.99414911.0158810.006378173,27e-0060.99353810.9973910,0454792,9826e-0060,018188,8362e-0060,0064974,2608e-0070,00454512,209e-0060,0401524,344e-0050,0839382,8654e-006

С выбором ведущего элемента по строке
1		2
1	2	1	2

111111-3. 57628e-0051,836e-0071.0000111.0003110.9999421-0.001332767,16e-0061.0000511.003020,999981.000091-0.00335051,8e-0050.9999111.001390,999990,0002984,3835e-0070,0094395,0683e-0054,2571e-0056,2622e-0080,00235421,2671e-0050,0106229,8016e-0070,294021,4768e-006

Реальные результаты
1	2
—	—

11111111111

Программа, реализующая метод на C++

Gauss_Elimination. zip [30КБ] — В архиве содержится исходный код, exe-файл и пример файла с входными данными

Рекомендации пользователю

• Метод Гаусса удобно применять для систем маленькой и средней размерности (до порядка ). Для больших же размерностей или разреженных матриц более эффективными представляются итерационные методы.

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

• Итерационное улучшение результата стоит провести 2-3 раза, если погрешность уменьшается очень медленно — возможно, матрица плохо обусловлена, тогда метод в любом случае даст не лучшие результаты — лучше попробовать применить итерационные методы.

• Важно, чтобы данные считывались из файла правильно.

При записи данных помните, что, целая и дробная части числа отделяются точкой, а не запятой. В последнем случае данные будут считаны неправильно, но не будет выведено никакого сообщения об ошибке.

• Есть возможность менять точность вычислений (float и double), но в исходниках.

Уловка Гаусса – семинар для персонала

Начало работы

Можете ли вы сложить в уме первые 10 чисел? Как насчет первых 100 или первой тысячи? В твоей голове!

Карл Фридрих Гаусс был специальным математиком. История гласит, что в школе, в возрасте 8 лет, он очень быстро смог сложить первые 100 чисел. Мне нравится думать об учителе, который использовал этот трюк много раз, чтобы занять класс в течение длительного времени, пока он вздремнул. Он знал, что его ждет долгий период тишины, пока класс работает в поте лица. Даже если один из них получил ответ, учитель мог попросить его проверить его, чтобы занять больше времени. Но он не стал торговаться с этим не по годам развитым 8-летним ребенком.

В мгновение ока Гаусс выдал 5050. Но он не только мог так быстро вычислить сумму первых 100 чисел, но и обосновал правильность своего ответа. И то же самое вы сделаете перед тем, как провести этот семинар для персонала.

Вы можете прочитать о Карле Фридрихе на одном из многих веб-сайтов. Было бы неплохо написать кое-что о Гауссе. Например, где он жил, когда жил, какие у него были бытовые проблемы и тому подобное. Стоило бы достать карту современной Германии и показать, где находится Брауншвейг (Брауншвейг). Насколько я помню, это недалеко от Ганновера и старой восточно-западной границы Германии.

Так в чем же хитрость и как с ее помощью произвести впечатление на друзей и коллег?

 Пример 1

Сначала я сложу целые числа от 1 до 10, чтобы вы могли увидеть, как все работает. Предположим, что сумма первых 10 чисел равна S. Тогда

 S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10.

 Интересно, что если сложить числа в другую сторону получаем тот же ответ. Ну очевидно же! Но давайте все же.

S = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1.

И что? Что ж, я облегчу понимание «ну и что», поместив эти два способа написания S друг под другом.

S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10.

S = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +   1.

Теперь просто добавьте S к S. Я знаю, что мы, кажется, уходим все дальше от значения S, которое мы так стремимся получить, но потерпите меня. Что ты видишь? Какие закономерности начинают проявляться?

 К счастью для Гаусса и нас,

 1 + 10 = 2 + 9 = 3 + 8 = 4 + 7 = 5 + 6 = 6 + 5 = 7 + 4 = 8 + 3 = 9 + 2 = 10 + 1 = 11.

 Все эти пары числа в сумме дают 11! Это означает, что

 2S = 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11.

 Таким образом, S = 5 × 11 = 55.

 Но этот трюк нельзя проделывать снова, и снова, и снова. Так что мы будем доить его изо всех сил.

 Пример 2

Давайте сложим числа Гаусса, все целые числа от 1 до 100. Снова пусть S будет этой суммой. Итак, S = 1 + 2 + 3 + 4 + 5 + … + 98 + 99 + 100.

Теперь вы видите, что я поленился и опустил все числа от 6 до 97. Но мы с вами знаем, что они действительно там. Многоточие (…) говорит нам именно об этом.

О очереди!

S = 100 + 99 + 98 + … + 5 + 4 + 3 + 2 + 1.

Теперь давайте сложим эти две величины вместе и посмотрим, что получится.

S =     1 +   2 +   3 + 4 + 5 +       …       + 98 + 99 + 100. равно 101. Каждая пара чисел, расположенная одна над другой, дает в сумме 101. Таким образом, 2S = 101 + 101 + 101 + … + 101 + 101 + 101.

101 есть. Но это не должно быть проблемой. В конце концов, мы начали со 100 чисел, поэтому у нас должно быть 100 сумм, которые в сумме дают 101. Итак, 2S = 100 × 101,

 Это означает, что S = 50 × 101 = 5050.

 И Гаусс опередил нас всего на столетие или два.

 Теперь вы видите, как быстро сложить первые 1000 целых чисел? Как насчет первых 10 000, первых 100 000 или первого миллиона?

 Пример 3

Я сделаю еще один последний пример, прежде чем мы сделаем то, что делает каждый хороший математик, а именно попытаюсь обобщить то, что мы делали. Другими словами, мы попытаемся найти закономерность. А пока давайте сложим первые первые 67 целых чисел.

S =   1 +   2 +   3 + … + 65 + 66 + 67.

S = 67 + 66 + 65 + … +   3 +   2 +   1.

На этот раз ключ 68. В конце концов, 1 + 67 = 68 = 2 + 66 = 3 + 65 = …

Итак, 2S = 68 + 68 + 68 + … + 68 + 68 + 68. находятся. Но мы начали с шестидесяти семи номеров, поэтому у нас должно быть шестьдесят семь 68-х. Таким образом, 2S = 67 × 68, или S = 67 × 34 = 2278.

Есть какие-нибудь предположения относительно общей закономерности?

Обобщение

Думаю, у нас должно быть достаточно информации, чтобы найти сумму первых n целых чисел, где n — любое значение, которое нам нравится. Давайте посмотрим, что у нас есть, чтобы увидеть, можем ли мы сделать предположение, догадку о том, что происходит на самом деле.

 Мы начали с                  n = 10 и получили S = ​​10 × 11 ÷ 2;

затем                                  n = 100 дало нам S = 100 × 101 ÷ 2;

затем                                  n = 67 дало нам S = 67 × 68 ÷ 2,

 Похоже, нам нужно взять число, которое мы хотим суммировать, умножить на это число плюс 1, а затем разделить на 2. Таким образом, мы имеем

  Гипотеза 1: Сумма S первых n чисел равно S = (n x (n +1)) / 2. 

 Можем ли мы обосновать, доказать это?

 Пусть S будет суммой чисел от 1 до n, каким бы ни было n.

 Если ваша алгебра немного заржавела, измените n ниже на «любое число», измените n – 1 на «любое число минус один», измените n + 1 на «любое число плюс один» и так далее.

 Проверенным методом получаем 

 S = 1 +      2     +     3     + … + (n – 2) + (n – 1) + n.

S = n + (n – 1) + (n – 2) + … +     3      +     2     + 1.

 Итак, делая то, что сейчас естественно, мы получаем

 2S = (n + 1) + (n + 1) + (n + 1) + … + (n + 1) + (n + 1) + (n + 1).

Поскольку изначально было n чисел, теперь должно быть n партий (n + 1). Итак,

2S = n × (n + 1).

Таким образом, S = (n x (n+1))/2, 

Похоже, мы угадали с догадкой. Прежде чем продолжить, вы можете подумать над следующими вопросами.

 (i)      Дает ли эта формула правильный ответ, если n = 15?

(ii)     Конечно, S должно быть целым числом, так как мы складываем первые n целых чисел. Но мы делим на 2 в правой части уравнения. Может ли n × (n + 1) иногда быть нечетным и все испортить?

(iii)    Что эта формула говорит словами?

 Ещё немного

Но вам не обязательно складывать только первые несколько чисел. Предположим, мы хотим сложить все числа от 8 до 93. Как мы можем это сделать?

Мне кажется, что мы могли бы сделать это по крайней мере тремя способами, но я не буду возиться с тем, где вы складываете числа вместе по одному.

Метод 1: Мы могли бы записать числа от 8 до 93 в обычном порядке, а затем записать их в обратном порядке, как мы делали в других примерах. Я оставлю вас сделать это, чтобы посмотреть, что вы получите.

Способ 2: С другой стороны, мы могли бы сначала прибавить 1 к 7, а затем 1 к 93, используя нашу формулу. Тогда мы могли бы вычесть меньшее из большего. Вот так:

В 1 + 2 + … + 6 + 7, «любое число», n равно 7, поэтому сумма этих чисел равна (7 x 8) / 2 = 28.  

В 1 + 2 + … + 92 + 93, «любое число», n равно 93, поэтому сумма этих чисел равна (93 x 94)/2 = 4371.

Таким образом, сумма, которую мы ищем, равна 4371 – 28 = 4343.

 Вы можете хотелось бы подумать над следующими вопросами, прежде чем продолжить.

(iv)    Существует ли формула для суммы чисел от любого выбранного вами числа (например, 8) до любого другого выбранного вами числа (например, 93)? Другими словами, можете ли вы обобщить гипотезу?

(v)     Видите, как мы постепенно усложняем ситуацию? Это путь, по которому математика всегда пытается расширить наши знания о мире.

(vi)    В свете мысли в (v), куда нам двигаться дальше? Каков следующий способ расширить то, что мы делаем? Мы пытались перейти от 1 к чему-то, а затем от чего-то к чему-то еще, но шаги от числа к числу всегда были одним. Можем ли мы добиться какого-либо прогресса, если шаги больше, чем один?

(vii)   В конце концов, существует ли только одна формула для ряда сложений, которые не просто складываются из нескольких первых чисел? Какой может быть эта формула на словах?

Семинар

Вам снова придется подумать о том, как лучше представить этот материал для ваших сотрудников, но как насчет следующего?

 Настройте их, задав им вопрос, который задал ему учитель Гаусса. Пусть они поработают над этим некоторое время. Затем дайте им понять, что 8-летний ребенок может сделать это в уме. Это должно привести к поиску закономерностей в числах от 1 до 100, которые могли бы облегчить быстрое суммирование. Например, некоторые группы видят, что 1 + 100 = 2 + 9.9 и так далее. Обычно они не задумываются о том, чтобы сложить вместе два лота по S сумм. Но вы можете быстро складывать числа от 1 до 100 и другим способом.

 Попробуйте их на других примерах. Если вы вооружитесь калькулятором, вы можете предложить им прибавить числа от 1 ко всему, что они выберут, быстрее, чем вы.

 Тогда они должны думать, что вы знаете, чего они не знают? Предложите им сделать несколько примеров и попросите их предположить, что это за закономерность.

 В зависимости от того, насколько хорошо идут дела, вы можете перейти к некоторым арифметическим прогрессиям, где общая разность не равна 1 (см. раздел 8). С заинтересованной группой вы могли бы даже сделать доказательство.

 Но вы должны сказать кое-что о Гауссе и его важности на математической сцене. Вы также должны найти несколько интересных историй о нем в ссылке, которую я дал выше. Немного истории никогда не сбивается с пути.

Ответы на некоторые вопросы

В этом разделе мы завершаем работу, проделанную в разделах со 2 по 6. Конечно, насколько далеко вы продвинетесь с этой задачей, будет зависеть от алгебраической уверенности вашего персонала, хотя вы можете полностью обойти алгебру, если вы думаете, что он лопнет, как свинцовый шарик. В любом случае, постарайтесь немного вытолкнуть их из зоны комфорта, но бросьте им спасательный круг, когда они тонут. Мы оставляем это решение за вами, но здесь должно быть достаточно материала для вашего семинара.

 Теперь я попытаюсь найти формулу для суммы строки чисел, в которой шаг от одного числа к другому всегда одинаков. Я сделаю два примера, а затем решу задачу в целом.

  Первый пример: Сложите числа 2 + 4 + 6 + … + 64 + 66 + 68.

 Это можно сделать несколькими способами. Прямое сложение — это единица, как и деление всех чисел в сумме на 2 по известной нам формуле. Тем не менее, я возвращаюсь к проверенному методу «сначала вперед, потом назад». Итак, пусть S будет суммой, которую мы ищем. Итак, вперед, затем назад у нас есть

 S =   2 +   4 +   6 + … + 64 + 66 + 68.

S = 68 + 66 + 64 + … +   6 +   4 +   2.

 Значит, что 2S = 70 + 70 + 70 + … + 70 + 70 + 70.

Единственная проблема сейчас заключается в том, сколько здесь терминов? Что ж, если бы мы разделили все исходные числа на 2, у нас было бы 1 + 2 + 3 + … + 32 + 33 + 34. Поскольку здесь 34 члена, в S должно быть 34 члена. Таким образом, 2S = 34. × 70 и S = ​​(34 x 70)/2 = 1190.

Вы можете проверить это одним из других методов, но это немного похоже на формулу, которую мы нашли в разделе 5.

Второй пример: Сложите числа 9 + 12 + 15 + … + 54 + 57 + 60.

Это можно сделать несколькими способами. Прямое сложение — это одно, как и деление всех чисел в сумме на 3 по известной нам формуле. Тем не менее, я возвращаюсь к проверенному методу «сначала вперед, потом назад». Итак, пусть S будет суммой, которую мы ищем. Таким образом, вперед и назад имеем

S = 9 + 12 + 15 + … + 54 + 57 + 60.

S = 60 + 57 + 54 + … + 15 + 12 + 9,

Это означает, что 2S = 69 + 69 + 69 + … + 69 + 69 + 69.

 Единственная проблема заключается в том, сколько здесь терминов? Что ж, если бы мы разделили все исходные числа на 3, то получили бы 3 + 4 + 5 + … + 18 + 19 + 20. Поскольку здесь 20 – 2 = 18 терминов, в S должно быть 18 терминов. Таким образом, 2S = 18 × 69 и S = ​​(18 x 69) / 2 = 621.

 Возможно, вы захотите проверить это одним из других способов. Есть ли здесь закономерность? Эти слова кажутся знакомыми?

  Общий пример: Во-первых, можем ли мы догадаться, что мы надеемся найти? Мы хотели бы найти формулу для суммы набора чисел, которые где-то начинаются и где-то заканчиваются, но где шаг между числами всегда одинаков. Из имеющейся у нас информации можем ли мы догадаться, какой может быть формула, прежде чем мы продираемся через алгебраическую путаницу, с которой нам предстоит столкнуться, чтобы получить ответ? В каждом случае, какие два числа мы перемножаем вместе, чтобы получить S?

 Ну, мы знаем, что когда мы прибавляли от 1 к n, числа были n и n + 1. Когда мы прибавляли от 2 к 68, они были 34 и 70; когда мы добавили из 9до 60 они были 18 и 69.

Очевидно, что в каждом случае большее число является общей суммой, которую мы получаем, складывая большие числа с меньшими числами. Эти большие числа являются просто суммой наименьшего и наибольшего чисел.

 А как насчет 34 и 18? И как они соотносятся с n, полученным при сложении первых n чисел. Что у них общего? Разве они не просто количество чисел, которые мы добавляем? Значит ли это, что формула, которую мы должны получить, содержится в следующей гипотезе?

  Гипотеза 2: Если S является суммой любой из этих строк, в которых есть общее различие, S = ( (количество членов)(сумма первого и последнего чисел))/2

 Проверьте формулу для некоторые другие наборы чисел, которые где-то начинаются и увеличиваются на постоянную величину. Другими словами, наборы чисел, в которых есть общая разница между последовательными числами.

 На данном этапе у нас есть предположение, каким может быть ответ. Это довольно сильная гипотеза, потому что она работает для множества примеров. Но можем ли мы доказать, что это работает для любого набора чисел с общим свойством разности? Ну конечно можем. И мы сначала покажем это методом слов, а потом посмотрим, насколько проще то же самое выразить с помощью алгебры.

 Предположим, что набор чисел представляет собой некоторое число, первое число; некоторое число плюс общая разность, второе число; некоторое число плюс общее различие плюс общее различие, третье число; до самого большого числа, последнего числа.

 Тогда сумму S можно записать двумя обычными способами:

 S = первое число +    второе число     + … + предпоследнее число + последнее число

S = последнее число  + предпоследнее число + … +    второе  число    + первое количество.

 Теперь первое число + последнее число = второе число + предпоследнее число. Это потому, что мы идем вверх по общей разности, идущей от первого числа ко второму числу, и вниз по общей разнице, идущей от последнего числа к предпоследнему числу. Итак, как обычно, все отдельные суммы одинаковы. Итак,

 2S = (первое число + последнее число) + (первое число + последнее число) + … + (первое число + последнее число) + (первое число + последнее число).

 Но в скобках есть одна из сумм для каждого члена исходной суммы. Таким образом, 2S = (количество терминов)(первое число + последнее число), и, следовательно, S = (количество терминов)(первое число + последнее число) ÷ 2,9.0005

 Это то, о чем мы догадывались выше. И теперь мы доказали гипотезу, и она верна для любого набора чисел, которые растут одинаковыми шагами. Эти наборы называются Арифметические прогрессии .

 Между прочим, математики работали во многом так же, как мы, до изобретения алгебры. Даже в работах Ньютона вы найдете уравнения со словами. Здесь это не так уж плохо, но может стать очень громоздким. Появление алгебры значительно улучшило математическую жизнь.

 Если вам нужна полная алгебраическая версия, вот она. Пусть первый член равен а, общая разность равна d, а количество членов равно n. Тогда

 S =  a + (a + d) + (a + 2d) + … + [a + (n – 3)d] + [a + (n – 2)d] + [a + (n – 1) )d]

S = [a + (n – 1)d] + [a + (n – 1)d] + [a + (n – 1)d] + …+ (a + 2d) + (a + d) + a

 Таким образом, 2S = [2a + (n – 1)d] + [2a + (n – 1)d] + [2a + (n – 1)d] + … + [2a + (n – 1)d] + [2a + (n – 1)d] + [2a + (n – 1)d]

 или S = n[2a + (n – 1)d] ÷ 2,

 Преимущество этого метода заключается в том, что легче увидеть, что сумма каждой пары соответствующих терминов одинакова. Другой заключается в том, что он записывает ответ с точки зрения первого термина, количества терминов и общей разницы. Единственным недостатком, по-видимому, является то, что он скрывает тот факт, что формула включает «первое число плюс последнее число», записывая это выражение как [2a + (n – 1)d]. И форма, которую мы записали в Гипотезе 2, легче запомнить.

Исключение Гаусса | Загадки любителя SAT 9266 атомов во Вселенной, так что подсчет с помощью этого метода невозможен.

Точный подсчет

Поскольку мы не можем считать 1 на 1, нам остается пытаться считать каким-то более разумным способом. Существует множество методов для точного подсчета, самый простой — сократить проблему на переменной, подсчитать, когда переменная имеет значение True, подсчитать, когда переменная имеет значение False, рекурсивно, и сложить их все. Учитывая кэширование повторяющихся компонентов при «вырезании», это может быть весьма успешным, как это реализовано в sharpSAT (см. статью Марка Терли). 9200 можно сосчитать 1 к 1 за любое разумное время. Однако используемые системы кэширования являются интеллектуальными, сохраняя последние использованные записи, когда кеш необходимо очистить. Однако иногда этот алгоритм очистки может привести к циклическому поведению, которое эффективно имитирует счет 1 на 1.

Приблизительный подсчет

В своей статье Чакраборти, Мил и Варди создали счетчик, который считает не точно, а «вероятно, приблизительно правильно». Этот беспорядок терминов в основном означает: есть определенная вероятность того, что подсчет правильный, в пределах заданного порога. Мы можем улучшить как вероятность, так и порог, учитывая больше времени процессора. С практической точки зрения, вероятность может быть больше 9.(60.3).

Коробка Галтона

Так в чем же хитрость? Как мы можем приблизительно посчитать и дать гарантии по счету? Трюк на самом деле довольно прост. Допустим, вам нужно посчитать мячи, а их тысячи. Один из способов сделать это — считать 1 на 1. Но если у вас есть машина, которая может обрабатывать примерно половину того количества мячей, которое у вас есть, это можно сделать намного быстрее: вы разделяете мячи пополам, а затем проверяете, есть ли у вас хотя бы 5, выполняющих счет 1 на 1. Если вы это сделаете, вы снова разделите их пополам и проверьте, есть ли у вас хотя бы 5 и т. 11 = 6144 шара для начала. В конце концов вам пришлось выполнить счет 1 на 1 только 11 * 5 + 3 + 1 = 59.раз — намного меньше 6144! Эту идею использует ApproxMC.

Приблизительное деление пополам с использованием XOR

Функция «приблизительного деления пополам», используемая ApproxMC, представляет собой простую функцию XOR, заполненную переменными, выбранными с вероятностью 50%. Так, например, если у нас есть переменные v1…v10, мы выбираем каждую переменную с вероятностью 50% и добавляем их в одно и то же XOR. Допустим, мы выбрали v1, v2, v5 и v8. Тогда XOR будет таким: v1⊕v2⊕v5⊕v8=1. Это XOR выполняется, если нечетное количество переменных из набора {v1,v2,v5,v8} равно 1. Это интуитивно запрещает примерно половину решений. «Интуитивной» части, конечно, недостаточно, и если вы прочитаете исходную статью, вы найдете строгое математическое доказательство приблизительного уполовинивания решений, которые дает эта функция XOR.

Итак, все, что нам нужно сделать, это добавить эти XOR к нашей исходной задаче, и все готово! Это звучит просто, но есть небольшое препятствие и большое препятствие, связанное с этим.

Небольшое препятствие состоит в том, что исходная задача представляет собой КНФ, то есть конъюнкцию дизъюнкций, имеющую вид «(v1 ИЛИ v2) И (v2 ИЛИ не v3 ИЛИ не v4) И…». XOR явно не выглядит так. Прямой перевод XOR в CNF является экспоненциальным, поэтому нам нужно добавить некоторые переменные, чтобы уменьшить их. Это не так сложно понять и в итоге добавить все XOR в CNF.

XOR, CDCL и исключение Gauss-Jordan

Большим препятствием является то, что как только XOR находятся в CNF с использованием преобразования, CNF становится экспоненциально трудно решить, используя стандартный CDCL, который используется в большинстве решателей SAT. Это связано с тем, что исключение Гаусса-Жордана экспоненциально сложно для стандартного CDCL, но нам нужно исключение Гаусса-Джордана, потому что исключающие ИЛИ будут взаимодействовать друг с другом, а мы ожидаем, что их будет много. Не имея возможности эффективно разрешать XOR друг с другом и извлекать из них информацию, будет практически невозможно решить CNF.

Решение состоит в том, чтобы тесно интегрировать исключение Гаусса-Жордана в процесс решения. CryptoMiniSat был первым решателем, который сделал эту тесную интеграцию (хотя и только для исключения Гаусса, чего достаточно). Затем последовали другие решатели, в частности работа Теро Лайтинена и работа Ченг-Шен Хана и Цзе-Хонга Роланда Цзяна. CryptoMiniSat в настоящее время использует код Хана и Цзяна после некоторой очистки и обновлений.

Последняя работа над ApproxMC и CryptoMiniSat добавила еще одну вещь помимо тесной интеграции цикла CDCL: теперь она позволяет выполнять внутреннюю и предварительную обработку, пока XOR находятся внутри системы. Это привело к серьезному ускорению, поскольку предварительная и внутренняя обработка являются важными факторами в решении SAT. На самом деле, все современные SAT-решатели сильно зависят от их активности и работы.

Заключительные замечания

Мы прошли путь от того, что такое подсчет моделей, через то, как работает приблизительный подсчет с точки зрения высокого уровня, вплоть до деталей запуска такой системы в современном SAT-решателе. Если вы хотите попробовать это, вы можете сделать это, загрузив готовые двоичные файлы или собрав их из исходного кода.

25 ноября 2018 г. Разработка, исследование, SATИсключение по Гауссу, подсчет моделей, выпуск, XORmsoos

Этот пост в блоге и его основная работа готовились в течение многих лет, и я очень рад возможности поделиться им с вами сейчас. Кулдип Мил и я очень усердно работали над ускорением приблизительного подсчета моделей для SAT, и я думаю, что мы добились реального прогресса. Научная работа, принятая на AAAI-19доступен здесь. Код доступен здесь (выпуск со статическим двоичным файлом здесь). Главный результат заключается в том, что мы можем решить на 90 319 90 320 задач больше, чем раньше. Скорость решения на порядки(!) выше, чем у предыдущей лучшей системы:

Предыстория

Идея приближенного подсчета моделей, первоначально предложенная Чакраборти, Милом и Варди, стала хитом еще в 2013 году, и было опубликовано множество статей. последовали за ним, пытаясь улучшить его результаты. Все они были в основном связаны с CryptoMiniSat, решателем SAT, который я поддерживаю, поскольку все они полагались на ограничения XOR, добавляемые к обычной CNF типичной задачи SAT.

Поэтому имело смысл изучить, что может сделать CryptoMiniSat для повышения скорости приблизительного подсчета. Это время интересно совпало с тем, что я отказался от XOR в CryptoMiniSat. Проблема заключалась в следующем. Было изобретено много новых систем внутренней и предварительной обработки, в основном Армином Бире и др., и я быстро понял, что просто не могу продолжать добавлять их, потому что они не учитывали ограничения XOR. Они отлично справились с CNF, но не с XOR. Поэтому XOR стали бременем, и я удалил их в версиях 3 и 4 CryptoMiniSat. Но потребность была, и Кулдип ясно дал мне понять, что это захватывающая область. Значит, им пришлось вернуться.

Blast-Inprocess-Recover-Destroy

Но как одновременно иметь и не иметь ограничения XOR? Изобретать заново все алгоритмы XOR было нецелесообразно. Решение, которое я придумал, было довольно тривиальным: забыть XOR во время обработки и восстановить их после. CNF всегда будет оставаться источником правды. Извлечение всех XOR после внутренней и предварительной обработки позволило бы мне запустить исключение Гаусса-Джордана для XOR после восстановления. Так что я могу получить торт и съесть его тоже.

Концептуально процесс довольно прост:

1. Разбить все XOR на предложения, которые находятся на входе, используя промежуточные переменные. У меня были все настройки для этого, так как я занимался сложением ограниченных переменных  (тоже от Biere et al.), поэтому мне не нужно было писать код, чтобы «скрыть» эти дополнительные переменные.
2. Выполнить   предварительную или внутреннюю обработку . На самом деле сейчас я занимаюсь только внутренней обработкой (поскольку у нее более быстрое время запуска). Но предварительная обработка — это просто обработка в начале;)
3. Восстановить XOR из CNF. Вокруг были какие-то тривиальные методы. Работали они не так хорошо, как хотелось бы, но об этом позже
4. Запустите код CDCL и Gauss-Jordan одновременно.
5. Уничтожить XOR и перейти к 2.

Эта система позволяет всему быть в форме CNF, поднимая XOR, когда это необходимо, и затем забывая о них, когда это удобно. Все эти шаги достаточно тривиальны, кроме, как я потом узнал, восстановления.

XOR recovery

Восстановление XOR звучит как тривиальная задача. Допустим, у нас есть следующие пункты

 x1 V x2 V x3
-x1 В -x2 В x3
 х1 В -х2 В -х3
-x1 В x2 В -x3
 

Концептуально это эквивалентно XOR v1+v2+v3=1. Таким образом, восстановить это тривиально, и это было сделано раньше, в частности, Хеуле в его докторской диссертации. Проблема с вышеизложенным заключается в следующем: более сильная система, чем приведенная выше, по-прежнему подразумевает XOR, но выглядит иначе. Приведу пример:

 x1 В x2 В x3
-x1 В -x2 В x3
 х1 В -х2 В -х3
-x1 В x2
 

Это почти эквивалентно предыдущему набору предложений, но в одном из предложений отсутствует литерал. Это по-прежнему подразумевает XOR, конечно. Что теперь? И что делать, если отсутствующие литералы означают, что может отсутствовать целое предложение? Алгоритм восстановления XOR в таких случаях нетривиален. Это нетривиально не только из-за сложности того, сколько комбинаций отсутствующих литералов и предложений может быть (это экспоненциально), но и потому, что эту работу нужно выполнять очень быстро, потому что решатели SAT чувствительны ко времени.

Алгоритм, описанный в статье, объясняет всю используемую манипуляцию с битами и кэш-память данных, а также некоторые забавные алгоритмы, которые, я уверен, понравятся некоторым людям. Нам даже удалось использовать встроенные функции компилятора, чтобы использовать целевые инструкции по сборке для расчета веса Хэмминга. Это взрыв. Взглянем.

Результаты

Результаты, как показано выше, говорят сами за себя. Задачи, на решение которых уходили тысячи секунд, теперь могут быть решены менее чем за 20. Причина такого невероятного ускорения в основном заключается в следующем. CryptoMiniSatv2 был слишком неуклюжим и не имел всех забавных вещей, которые есть в CryptoMiniSatv5, плюс обработка XOR была неправильной, теряла XOR и тому подобное. Опубликованный алгоритм решает основную проблему и позволяет выполнять предварительную и внутреннюю обработку CNF независимо от XOR, что позволяет использовать CryptoMiniSatv5 во всей красе. А CryptoMiniSatv5 — быстро, по результатам SAT Competition этого года.

Несколько заключительных слов

Наконец, я хочу поблагодарить Кулдипа Мила, который привел меня в Национальный университет Сингапура, чтобы я выполнил вышеуказанную работу и множество других интересных работ, которые мы надеемся опубликовать в ближайшее время. Я также хотел бы поблагодарить Национальный суперкомпьютерный центр Сингапура, который позволил нам запустить массу тестов на их машинах, используя не менее 200 тысяч часов ЦП для написания этой статьи. Это дало нам возможность отладить все странные пограничные случаи и довести эту систему до скорости, при которой она превосходит лучшие точные счетчики с большим отрывом. Наконец, благодаря всем замечательным людям, с которыми мне довелось встретиться и иногда поработать в NUS, это было действительно приятное время.

6 июля 2016 г. SATcompetition, исключение Гаусса, Releasemsoos

Выпущен

CryptoMiniSat 5.0.0, победивший в инкрементальном треке на SAT Competition 2016 и занявший 3-е место в параллельном треке. Новый решатель содержит ряд важных дополнений. Наиболее важным является то, что решатель теперь можно использовать в качестве препроцессора, и функция исключения Гаусса-Жордана возвращается.
Читать далее Выпущен CryptoMiniSat 5.0.0 →

1 августа 2013 г. Исследования, SATИсключение по Гауссу, XORmsoos

У меня было несколько вопросов о том, почему CryptoMiniSat 3.3 не имеет встроенной поддержки условия XOR. Позвольте мне объяснить, что я думаю о преимуществах и недостатках встроенной поддержки XOR и почему я решил удалить их.

Преимущества

Наиболее тривиальным преимуществом является то, что пользователям не нужно преобразовывать XOR в простую CNF. Хотя трансформация довольно проста, некоторые предпочитают не сталкиваться с хлопотами. Принцип состоит в том, чтобы разрезать XOR на более мелкие XOR, вводя новые переменные, а затем представляя урезанные XOR, запрещая все неправильные комбинации. Например, XOR разрезается на два XOR, а затем представляется как .

Более существенным преимуществом является то, что распространение и генерация конфликтов могут выполняться изначально. Это довольно выгодно, поскольку означает, что при распространении и генерации конфликта UIP необходимо посещать гораздо меньше предложений и переменных. Меньшее количество посещенных переменных и предложений означает меньшее количество промахов в кеше и, благодаря более компактному представлению, меньше накладных расходов на память и, следовательно, даже лучшее использование кеша. (Для поклонников: интересный побочный эффект XOR заключается в том, что заблокированные литералы нельзя использовать для предложений XOR).

Самым большим преимуществом собственных XOR является то, что исключение Гаусса можно выполнять на каждом уровне дерева поиска, а не только на верхнем уровне. Хотя большинство людей, с которыми я разговаривал, по-прежнему считают, что CryptoMiniSat 2 выполняет исключение Гаусса только на верхнем уровне, это не так. Выполнение Гаусса на высшем уровне — это двухдневный хак. Выполнение этого на каждом уровне заняло у меня около полугода (и около 5 тысяч строк кода). Это требует оставления следов прошлых вычислений и вычисления причин распространения и конфликтов, указанных алгоритмом исключения Гаусса. Согласно моему весьма неофициальному подсчету, ровно 2 человека используют метод исключения Гаусса на уровне выше верхнего: Вегард Носсум и Кулдип С. Мил. Из этих двух пользователей только последний указал ускорение. Он ускоряет проблемы с криптографией, но не многие другие, поэтому по умолчанию он полностью отключен.

Недостатки

Основным недостатком собственных предложений XOR наряду с обычными предложениями CNF является потеря простоты и универсальности. Позвольте мне объяснить подробно.

Потеря простоты . Если переменная присутствует как в обычном предложении, так и в предложении XOR, ее нельзя устранить простым способом. Я даже не хочу пытаться выразить оговорки, которые получились бы в результате выполнения варелим в таких случаях — это, вероятно, ужасно запутано. Все алгоритмы в коде теперь должны проверять XOR. Конечно, усиление предложения «на лету» не может усилить XOR обычным предложением. Очистка предложений должна учитывать, что когда 3-длинный XOR сокращается до 2-длинного, это указывает на новый эквивалентный литерал, и это может привести к немедленному UNSAT. Я мог бы продолжать, но список длинный.

Другая проблема заключается в том, что операции XOR усложняют состояние. До сих пор были только предложения формы , иногда специально сохраненные, такие как бинарные предложения. Состояние решателя претерпевает множество преобразований — думайте о них как о прохождении llvm — пока оно обрабатывается и решается. Чем сложнее состояние, тем больше и сложнее код. В то время как простой алгоритм очистки предложений может быть выражен примерно в 20 строках кода без неявных двоичных и третичных предложений, тот же алгоритм раздувается примерно до 100 строк кода с этими оптимизациями. Как только вы добавите предложения XOR, оно увеличится примерно в два раза. Мы только что увеличили наш код в 10 раз. Представьте себе добавление встроенной поддержки, например. максимум-н.

Утрата универсальности . Если переменная представляет собой только предложения XOR, теперь ее можно исключить на уровне XOR. Чистая переменная на уровне XOR указывает на предложение XOR, которое можно удалить и впоследствии всегда выполнять. Включение XOR — это когда XOR включает другое: большее может быть удалено, а их XOR добавлено. Все это реализовано в CMS 2. Однако, вероятно, есть много других. Мы могли бы попытаться реализовать их все, но это целая новая вселенная, которая может открыть врата ада. Хуже всего то, что большинство этих методов на XOR, вероятно, уже смоделированы методами внутренней обработки на уровне CNF. Чистые переменные XOR моделируются путем устранения заблокированных предложений. Исключение переменных на основе XOR не имеет практического смысла на уровне CNF, но его можно смоделировать с помощью обычного исключения переменных, если игнорировать эвристику. Я мог бы продолжить.

Что делает CryptoMiniSat 3.3

Компромисс, который я придумал для CryptoMiniSat 3.0, заключается в том, что я регулярно ищу предложения XOR на верхнем уровне, выполняю исключение Гаусса верхнего уровня и добавляю полученную новую информацию в CNF. Двоичные и унитарные предложения XOR добавить обратно проще всего.

В тесте приложений SAT’11 из 300 задач 256 содержат условие XOR. количество найденных предложений XOR, когда они найдены, составляет в среднем 2905 со средним размером 4,2 литерала. Используя исключение Гаусса, считая только, когда что-то было извлечено, среднее количество извлеченных литеральных эквивалентностей (бинарных XOR) составляет 130, а количество извлеченных унитарных предложений составляет 0,15.

Вот типичный пример вывода:

c Чтение файла «valves-gates-1-k617-unsat.shuffled-as.sat03-412.cnf.gz»
c -- в заголовке указано число переменных: 985042
c -- в заголовке указано количество пунктов: 3113540
[..после примерно 124К конфликтов..]
c Обнаружение XOR Num XOR: 104091 средний размер: 3,0 T: 2,11
c Разрезать XOR на 2185 блоков sum vars: 180818 T: 0,11
c Извлеченная информация XOR. Единицы: 0 Бункеры: 1275 0-назначения глубины: 0 T: 8,34
 

Здесь было найдено около 104 тыс. предложений XOR (с использованием сложного алгоритма) в течение 2.11s, все размером 3. Эти предложения XOR были подвергнуты анализу несвязанных компонентов (в сфере XOR), и было обнаружено, что они принадлежат 2185 компонентам. Важно разбить XOR на группы, потому что исключение Гаусса — это алгоритм, и если мы можем уменьшить n, имея более одной матрицы, скорость значительно возрастет. Затем эти 2185 матриц были исключены методом Гаусса, и было обнаружено, что они содержат 1275 бинарных операторов XOR, которые были быстро помечены как эквивалентные литералы.

Для выполнения исключения Гаусса на верхнем уровне CryptoMiniSat использует превосходную библиотеку m4ri, поддерживаемую моим старым коллегой и другом Мартином Альбрехтом. Это легкая, но чрезвычайно быстрая система исключения Гаусса, использующая всевозможные изящные приемы для выполнения своей работы. К сожалению, для больших матриц это все еще может занять много времени, так как сам алгоритм не из дешевых, поэтому у меня есть отсечка для слишком больших матриц.

Что может сделать будущий CryptoMiniSat 3.x

После того, как мы извлекли XOR, мы могли бы также сохранить их во время поиска и выполнить исключение Гаусса на уровнях ниже верхнего уровня. Это приблизило бы нас к старой системе с точки зрения реальной производительности — нативное распространение (которое было бы недоступно) может дать ускорение только в 1,5-2 раза, а исключение Гаусса на каждом уровне может дать гораздо больше. Мне нужно было бы очистить много кода, и тогда, возможно, это сработало бы. Может быть, я сделаю это однажды. Хотя, потратив на это недели, люди, вероятно, по-прежнему будут верить, что это работает только на высшем уровне. По крайней мере, сейчас это так.

Выводы

Внедрение новой теории, такой как XOR, глубоко в внутренности SAT-решателя не просто и не дает явного преимущества в большинстве ситуаций. Те, кто настаивает на этих нативных теориях, либо не пытались внедрить их в сложный решатель, такой как lingeling/SatELite/CryptoMiniSat/clasp, либо уже укусили пулю, такую ​​как группа застежек, и это, вероятно, ограничивает их в расширении система с новыми методами. Полученное в результате большее внутреннее состояние приводит к пограничным случаям, исключениям и гораздо большему количеству кода.

9 мая 2010 г. SATУстранение Гаусса, Зерно соли, Releasemsoos

В новом CryptoMiniSat версии 2.4.2 теперь по умолчанию скомпилировано исключение Гаусса на лету. Вы можете просто использовать его, выпустив, например.

./cryptominisat --gaussuntil=100 trivium-cipher.cnf

и наслаждайтесь выводами, такими как:
c распространения гаусса: 7823 (24,98 %)
c полезного гаусса: 43,79 %
c конфликтов : 34186 (4073,39/сек)
c решений : 39715 (6,86 % случайных)

Что в основном говорит о том, что исключение гаусса раз из 39 тысяч, а так по сути почти все время работал. Из 31 323 вызовов в 44 % случаев обнаружен либо конфликт, либо распространение. Это очень хороший результат, типичный для шифра Trivium. Trivium можно ускорить до 2 раз с помощью исключения Гаусса. Я выложу много CNF, чтобы вы могли поиграть с ними и (необязательно) проверить эти результаты.

Волшебный параметр «–gaussuntil=100» указывает программе выполнять исключение Гаусса до уровня решения 100 и не ниже. Я не реализовал автоматизацию поиска наилучшей глубины, поэтому использую это (очень) грубое фиксированное число 100. Вероятно, лучших результатов можно было бы достичь с точной настройкой отсечки глубины, но у меня нет время на данный момент, чтобы поиграть с ним. Однако, если вам интересно, вы сможете опробовать разные глубины, разные шифры и т. д. Вскоре я выпущу инструмент под названием «Grain of Salt» для генерации CNF для любого потокового шифра на основе сдвигового регистра, так что вы сможете протестируйте их против CryptoMiniSat или любого другого SAT-решателя.

Надеюсь, вам понравится использовать метод исключения Гаусса на лету в CryptoMiniSat 2.4.2!

Введение в численное интегрирование и точки Гаусса

В ваших моделях конечных элементов вы можете столкнуться с концепцией численного интегрирования и точек Гаусса в нескольких контекстах. В этом сообщении блога мы обсуждаем, где и почему используется численное интегрирование. Кроме того, выделены возможности проверки и изменения схем численного интегрирования в программном обеспечении COMSOL Multiphysics®. Наконец, объясняется использование точечных степеней свободы Гаусса.

Содержание

1. Что такое численное интегрирование?
   • Квадратура Гаусса
   • Примеры гауссовой квадратуры
2. Интеграция слабых вкладов
   • Некоторые тонкости о слабых выражениях
3. Изменение порядка интеграции
4. Объединение операторов связи
5. Интеграция во время постобработки
6. Функции формы точки Гаусса
7. Оператор gpeval

Что такое численное интегрирование?

При вычислении интегралов от нетривиальных функций по общим областям приходится прибегать к численным методам. Численное интегрирование также называют числовой квадратурой . Идея состоит в том, что интеграл заменяется суммой, где подынтегральная функция дискретизируется в ряде дискретных точек. Это можно описать как

\displaystyle \int_{\Omega} f(\mathbf x) dV \приблизительно \sum_i f(\mathbf x_i)w_i

, где x _i — расположение точек интегрирования, а w _i — соответствующие весовые коэффициенты. Точки интегрирования часто называют точками Гаусса , хотя эта номенклатура, строго говоря, верна только для точек интегрирования, определяемых методом гауссовых квадратур . В COMSOL Multiphysics истинная квадратура Гаусса используется для интегрирования в 1D, четырехугольных элементов в 2D и шестигранных элементов в 3D. Другие аналогичные схемы используются для элементов другой геометрии.

Квадратура Гаусса

В квадратурном алгоритме Гаусса расположение точек интегрирования и их веса выбираются таким образом, чтобы можно было точно проинтегрировать многочлен максимально высокой степени. Поскольку многочлен степени N содержит N+1 коэффициентов, а точечное правило Гаусса с M точками содержит 2M параметров (местоположения + веса), наивысший порядок полинома, который можно точно проинтегрировать, равен N = 2M – 1.

Гауссова квадратуры очень эффективны для интегрирования полей, которые можно хорошо аппроксимировать полиномом определенной степени. Точки интегрирования и веса для первых порядков квадратуры Гаусса в 1D показаны в таблице ниже. Интеграл берется по нормализованному интервалу [-1,1].

Заказ (М)	Точность (Н)	Местоположение (х i )	Вес (с и )
1	1	0	2
2	3	±0,577	1
3	5	0, ±0,775	0,889 (= 8/9), 0,556 (= 5/9)
4	7	±0,340, ±0,861	0,652, 0,348
5	9	0, ±0,538, ±0,906	0,569, 0,479, 0,237

В COMSOL Multiphysics порядки интегрирования обозначаются степенью полинома, который можно точно проинтегрировать. Используются только четные числа. Для истинного интегрирования точек Гаусса точность, как показано выше, всегда является нечетной степенью. Порядок интегрирования, обозначенный программным обеспечением как «4», на самом деле будет иметь точность 5 для тех форм элементов, где используется квадратура Гаусса. 9{0,5xy} \cos \left( \dfrac{3 \pi x y}{2} \right )

По квадрату -1 ≤ x ≤ 1, -1 ≤ y ≤ 1 интеграл этой функции равен 1. Как видно на рисунке ниже, функция имеет довольно сложное распределение по области.

Интегрируемая функция.

В таблице ниже показаны результаты различных квадратур Гаусса. Как только функция может быть разумно аппроксимирована полиномом определенной степени, значение интеграла быстро сходится.

Точки интеграции	Точность	Заказ на интеграцию	Значение	Комментарии
1	1	0 (или 1)	2,9958	Использование только значения в центре тяжести явно завышает интеграл
2×2	3	2 (или 3)	0	В правиле 2×2 точки Гаусса расположены в \pm \frac{1}{\sqrt{3}}, где функция косинуса равна 0 (не повезло!)
3×3	5	4 (или 5)	1. 1519
4×4	7	6 (или 7)	0,9887
5×5	9	8 (или 9)	1.0005
6×6	11	10 (или 11)	1.0000
7×7	13	12 (или 13)	1.0000
8×8	15	14 (или 15)	1.0000

Оптимальное поведение квадратуры Гаусса для полиномов, однако, имеет и обратную сторону: метод не очень хорош для интегрирования сильно разрывных функций. Предположим, мы хотим проинтегрировать функцию, которая равна f(x,y) = 1, когда y < -2x – 1, и 0 в другом месте того же квадрата, что и выше. Поскольку функция имеет значение 1 на одной четверти квадрата, а площадь квадрата равна 4, мы сразу видим, что точный интеграл должен равняться 1. Результаты показаны в таблице ниже.

Точки интеграции	Значение	Комментарии
1	0	Только одна точка (0,0), где функция оценивается как 0
2×2	1	Одна из четырех точек оценивается как 1, и ее вес равен 1
3×3	0,8025	Две точки оцениваются как 1, и их веса равны \frac{25}{81}, \frac{40}{81}
4×4	1,2269	Пять баллов дают 1
5×5	1. 0325
6×6	1.0918
7×7	0,9892
8×8	0,9961

Корпус с 4×4 точками интеграции. Оранжевая поверхность — это места, где функция имеет значение 1, а зеленые точки Гаусса — это точки, вносящие вклад в значение интеграла.

Как видно из таблицы, усилия по вычислению точного интеграла этой разрывной функции значительны. По чистой случайности схема интегрирования 2×2 дает точный ответ, но сходимость далека от монотонной.

Почему это важно? При анализе методом конечных элементов вы можете встретить поля с резкими локальными градиентами. Некоторыми примерами являются проблемы с фазовыми превращениями или в начале пластичности в механике твердого тела. Интегралы, вычисляемые по элементам, содержащим скачки такого типа, могут иметь значительные ошибки дискретизации. Кроме того, сходимость решения может быть нарушена. Небольшие изменения в решении могут существенно изменить вычисленные невязки, когда отдельные точки Гаусса изменяют свое состояние.

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

Кроме того, если вы вычисляете интегралы дискретных функций во время постобработки, важно помнить о потенциально медленной сходимости численного интегрирования.

Интегрирование слабых вкладов

В каждом конечном элементе есть различные выражения, которые необходимо интегрировать, чтобы сформировать, например, матрицы жесткости, матрицы масс, векторы нагрузки и невязки. Взяв в качестве примера механику твердого тела, стандартная слабая (или вариационная) формулировка соответствует принципу виртуальной работы : виртуальная работа, совершаемая внутренними напряжениями, действующими на изменение виртуальной деформации, равна виртуальной работе, совершаемой внешними силами, действующими на соответствующую виртуальную вариацию перемещений.

\displaystyle \int\limits_{\quad\Omega} \sigma : \tilde {\varepsilon} \; dV = \int\limits_{\quad\Omega} \mathbf f \cdot \tilde {\mathbf u} \; dV + \int\limits_{ \quad\Gamma} \mathbf t \cdot \tilde {\mathbf u} \; dS

Здесь тильда (~) обозначает виртуальную вариацию. В выражении в COMSOL Multiphysics это представлено оператором test() . Сюда включены объемные силы f и граничные силы тяги t , но могут быть и другие типы вкладов. Левая сторона будет вносить вклад в матрицу жесткости, а правая сторона будет вносить вклад в вектор нагрузки (при условии, что силы не зависят от перемещений).

Для проверки формулировок конечно-элементных реализаций в COMSOL Multiphysics необходимо активировать Equation View .

Включение Equation View .

Если мы посмотрим в Equation View под моделью материала (скажем, Linear Elastic Material ) в интерфейсе Solid Mechanics , там есть раздел с именем Weak Expressions . Там вы можете увидеть выражения, используемые для формирования различных матриц; например, матрица жесткости.

Проверка слабого выражения для Linear Elastic Material в интерфейсе Solid Mechanics в стационарном корпусе.

На рисунке выше вы можете видеть текстовое поле для порядка интегрирования, которое в данном случае имеет значение 4. Число, описывающее порядок интегрирования в COMSOL Multiphysics, представляет собой полином наивысшего порядка, который можно точно проинтегрировать. Порядок интегрирования по умолчанию основан на порядке функций формы, используемых для описания поля (в данном случае перемещений). Здесь используется порядок функции формы по умолчанию — квадратичный, поэтому напряжения и деформации будут иметь линейное изменение по элементу. Таким образом, продукт изменения напряжения и деформации является квадратичным, что указывает на то, что порядок 4 может быть больше, чем необходимо. Почему именно это значение выбрано, будет рассмотрено ниже.

В качестве второго примера рассмотрим Граничная нагрузка в Solid Mechanics .

Слабое выражение для Граничная нагрузка .

Здесь также порядок интегрирования равен 4. Поскольку функции формы смещения являются квадратичными полиномами, это означает, что должна быть возможность точно интегрировать вклад нагрузки, для которого тяговое усилие имеет не более чем квадратичное изменение, поскольку произведение сила тяги и изменение водоизмещения тогда порядка 4.

Некоторые тонкости относительно слабых выражений

Вышеизложенное справедливо только в том случае, если элементы имеют идеальную форму (например, без изогнутых границ). Если вы углубитесь в теорию, интегралы на самом деле также будут содержать локальный масштабный коэффициент (якобиан), возникающий в результате преобразования между фактической геометрией элемента и номинальной геометрией элемента. Если, например, интеграл выполняется по двумерному четырехугольному элементу, числовая оценка выполняется по идеальному квадрату -1 ≤ ξ ≤ 1, -1 ≤ η ≤ 1, 9{1} f(\xi, \eta) \left | \dfrac{\partial \mathbf x}{\partial \boldsymbol \xi} \right | \; d\xi d\eta

Якобиан, вообще говоря, будет рациональной функцией (многочлены как в числителе, так и в знаменателе), поэтому он может даже не быть точно интегрируемым с помощью числовой квадратуры такого типа. Из-за этого разумно иметь некоторый запас в выбранном порядке интегрирования. Между прочим, эффект Якоби — одна из причин, по которой сильно искаженные элементы работают хуже, чем элементы идеальной формы. В этой записи блога о проверке сетки в COMSOL Multiphysics содержится дополнительная информация о качестве сетки.

Даже если функция формы элемента называется «квадратичной», она может (в некоторых случаях) содержать члены более высокого порядка. Порядок функции формы, указанный в пользовательском интерфейсе, показывает самый высокий полный полином в функциях формы. Тот факт, что в полиномах могут присутствовать члены более высокого порядка, является еще одной причиной для использования более точного правила интегрирования, чем это может показаться необходимым на первый взгляд.

Еще одна причина, по которой вы можете увидеть более высокий порядок интеграции, чем ожидалось, в Equation View для определенного вклада заключается в том, что может быть необходимо обеспечить симметрию в матрице жесткости.

Изменение порядка интегрирования

Вы можете изменить порядок интегрирования для любого слабого выражения из Equation View , отредактировав текстовое поле. Есть две основные причины, по которым вы можете захотеть это сделать.

Первый более очевиден: вы хотите повысить точность. Скажем, у вас есть нагрузка (в общем смысле, это может быть сила, тепловой поток, электрический ток и т. д.), которая имеет быстрое изменение по сравнению с размером элемента. Увеличение порядка численного интегрирования повысит точность определения общей силы или потока в области. Однако локальное решение вблизи того места, где применяется граничное условие, все равно не будет хорошим, поскольку оно никогда не может быть лучше, чем то, что могут представлять функции формы элемента.

Есть, правда, еще один интересный случай: уменьшили интеграцию , а это значит, что порядок интеграции по какой-то причине ниже того, что формально нужно. Одной из таких причин является ускорение вычислений. При решении конечно-элементной задачи большая часть времени ЦП тратится на две задачи: формирование матриц элементов ( сборка ) и решение больших систем линейных уравнений. Время, затрачиваемое на решение уравнений, увеличивается быстрее, чем размер модели, часто примерно пропорционально квадрату числа элементов. Время, затрачиваемое на сборку, прямо пропорционально размеру модели (фактически, количеству элементов, умноженному на количество точек интегрирования на элемент). Для очень большой модели решение уравнения всегда будет доминировать, но для нелинейных моделей среднего размера с тяжелыми вычислениями в каждой точке интегрирования может быть целесообразно рассмотреть использование сокращенного интегрирования.

Уменьшенная интеграция также является числовым приемом, который иногда используется для устранения искусственной жесткости, которая может появляться в формулировках некоторых элементов в явлении, часто называемом блокировкой . Один из примеров, где для этой цели используется уменьшенная интеграция, можно найти в интерфейсе Shell в 2D-осевой симметрии. В уравнениях виртуальной работы некоторые члены интегрируются с порядком 2, а другие с порядком 4. Если бы везде использовалось полное интегрирование, элемент на самом деле был бы слишком жестким, когда толщина оболочки становится малой. При использовании сокращенного интегрирования некоторые проблемные члены в энергии деформации намеренно теряются.

Вклады виртуальной работы для осесимметричного интерфейса Shell .

Операторы интеграции

В разделе Определения в построителе моделей можно создавать операторы интеграции. Такие операторы можно использовать для определения глобальных переменных, которые являются частью постановки задачи, но их также можно явно использовать в выражениях во время оценки результатов.

Добавление оператора интегрирования.

При добавлении оператора интегрирования необходимо сделать три основных выбора:

1. Области, границы или ребра, по которым следует брать интеграл.
2. Порядок интеграции — это также дает вам возможность обменять точность на скорость. Обратите внимание, что фактическое подынтегральное выражение — это не только выражение, которое вы вводите, но и то, что оно также умножается на якобиан преобразования идеальной формы элемента в реальную.
3. Фрейм — это становится важным только тогда, когда существуют разные фреймы, например, с подвижной сеткой, деформированной геометрией и геометрической нелинейностью в строительной механике. Проще говоря: следует ли брать интеграл по деформированной или недеформированной геометрии?

Настройки оператора интеграции.

Интеграция во время постобработки

Если вы хотите вычислить интеграл во время постобработки, у вас есть два варианта: использование оператора интегрирования (как описано выше) или добавление узла Интеграция в Производные значения . Во многом выбор произволен. Однако в узле Integration нельзя явно выбрать фрейм для интеграции; это следует из выбора кадра в Набор данных узел.

Добавление узла для интеграции при оценке результатов.

Настройки для набора данных, где можно выбрать фрейм для интерпретации результатов.

Если выбор кадра важен, вам, вероятно, следует полагаться на операторы интеграции, чтобы свести к минимуму риск совершения незаметных ошибок. Если вы добавляете оператора интеграции после решения проблемы, вы должны запустить решение обновления , прежде чем новый оператор станет доступным.

Обновление решения.

Не забудьте выбрать достаточно высокий порядок интегрирования. В частности, будьте осторожны, если интегрируемые выражения сильно нелинейны или разрывны. Типичным частным случаем прерывистых выражений являются булевы выражения. Например, если после анализа теплопередачи вы хотите вычислить объем, в котором температура выше определенного значения, вы можете использовать подынтегральное выражение, например T>1066[K] . Это выражение будет оцениваться как 1 там, где условие выполнено, и 0 в другом месте, поэтому его интегрирование даст объем, где условие выполнено. Однако граница между двумя значениями, как правило, пересекает элементы.

Интегрирование логического выражения с повышенной точностью интегрирования.

Функции формы точки Гаусса

Если вы расширяете свою мультифизическую модель, вам иногда нужно добавить определяемые пользователем степени свободы ( зависимые переменные ). При этом вы должны выбрать тип функции формы, используемой для их представления. Один из вариантов — Данные точки Гаусса . Все остальные варианты дают различные типы полей, которые имеют непрерывное распределение по элементу и могут быть или не быть непрерывными между соседними элементами. Данные точки Гаусса Тип «функции формы» принципиально отличается. Он хранит значение только в каждой точке Гаусса, но не имеет связи со значениями в другом месте элемента.

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

Тип данных точки Гаусса полезен, когда вы хотите сохранить локальное состояние. Такая ситуация возникает, например, в зависимых от истории нелинейных конститутивных моделях, требующих «памяти». Доступ к определяющей модели в основном осуществляется при вычислении матриц жесткости и невязок, поэтому единственными местами в элементе, где она будет фактически оцениваться во время решения, являются точки интегрирования. Таким образом, имеет смысл хранить этот тип данных именно там.

Одним из примеров внутреннего использования данных точек Гаусса является хранение неупругих деформаций в моделях материалов, таких как пластичность и ползучесть в строительной механике.

После того, как вы решили сохранить данные точек Гаусса, вам необходимо выбрать порядок элементов . В случае данных точек Гаусса это то же самое, что и порядок интегрирования, рассмотренный выше. Стоимость (с точки зрения памяти и процессорного времени) хранения данных точек Гаусса пропорциональна выбранному порядку в 1D, его квадрату в 2D и третьей степени в 3D.

Выбор шаблона точки интеграции.

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

Оператор gpeval

Если у вас есть переменные, хранящиеся в точках Гаусса, встроенные или определенные вами, могут возникнуть ситуации, когда вам может понадобиться интерполировать их по элементу. Это особенно важно во время постобработки. По умолчанию значения переменных точки Гаусса просто выбираются из ближайшей точки Гаусса при оценке в другом месте элемента. gpeval() Оператор можно использовать для сопоставления дискретных данных точек Гаусса с непрерывным полем. В самом простом воплощении на оператор ссылаются как gpeval(gporder, expression) , например, gpeval(4,solid. epe) . Дополнительные сведения см. в Руководстве пользователя COMSOL Multiphysics .

В качестве иллюстрации рассмотрим следующий пример: координата x (в диапазоне от 0 до 3) хранится как данные точки Гаусса в небольшой трехэлементной модели. Это делается путем добавления вспомогательной зависимой переменной, как показано ниже.

Сохранение координат x в виде данных точки Гаусса.

Слабый вклад (myX-nojac(X))*test(myX) просто гласит: «Установите переменную myX равной текущему значению X ». Оператор nojac() добавлен в качестве защиты от получения двунаправленной связи между myX и X . Это хорошая практика, когда вы просто хотите присвоить значение зависимой переменной.

Если переменная точки Гаусса myX затем отображается как поверхностный график (без усреднения между элементами), результат будет прерывистым. Внутри каждого элемента переменные точки Гаусса перемещаются к ближайшему углу, а затем интерполируются по элементу. Если вместо этого на график выводится выражение gpeval(2,myX) , мы получаем точное распределение координат x .

Построение графика переменной точки Гаусса (внизу) и экстраполированной переменной точки Гаусса (вверху). Стрелки показывают, как данные точек Гаусса по умолчанию перемещаются в углы во время оценки результатов.

Следующий шаг

Узнайте больше о функциях, доступных в программном обеспечении COMSOL®, нажав кнопку ниже:

Покажите мне COMSOL Multiphysics®

Carl Friedrich Gauss | Биография, открытия и факты

Карл Фридрих Гаусс

Смотреть все СМИ

Дата рождения:

30 апреля 1777 г. Брауншвейг

Умер:

23 февраля 1855 г. (77 лет) Геттинген Ганновер

Награды и награды:

Медаль Копли (1838 г. )

Изобретения:

гелиотроп магнитометр

Известные работы:

«Арифметические исследования»

Просмотреть весь связанный контент →

Популярные вопросы

Чем знаменит Карл Фридрих Гаусс?

Гаусс считается одним из величайших математиков всех времен за его вклад в теорию чисел, геометрию, теорию вероятностей, геодезию, планетарную астрономию, теорию функций и теорию потенциала (включая электромагнетизм).

Каким было детство Карла Фридриха Гаусса?

Гаусс был единственным ребенком бедных родителей. Он был расчетливым вундеркиндом с даром к языкам. Его учителя и преданная мать рекомендовали его герцогу Брауншвейгскому в 179 году.1, который предоставил ему финансовую помощь для продолжения образования на месте, а затем для изучения математики в Геттингенском университете.

Какие награды получил Карл Фридрих Гаусс?

Гаусс получил медаль Копли, самую престижную научную награду в Соединенном Королевстве, ежегодно присуждаемую Лондонским королевским обществом в 1838 году «за свои изобретения и математические исследования в области магнетизма». За изучение карт, сохраняющих угол, он был удостоен премии Датской академии наук в 1823 г.

Какое влияние оказал Карл Фридрих Гаусс?

Гаусс написал первый систематический учебник по алгебраической теории чисел и заново открыл астероид Церера. Он опубликовал работы по теории чисел, математической теории построения карт и многим другим предметам. После смерти Гаусса в 1855 году обнаружение многих новых идей среди его неопубликованных статей распространило его влияние на оставшуюся часть века.

Сводка

Прочтите краткий обзор этой темы

Карл Фридрих Гаусс , настоящее имя Иоганн Фридрих Карл Гаусс , (родился 30 апреля 1777, Брауншвейг [Германия] — умер 23 февраля 1855, Геттинген, Ганновер), немецкий математик, обычно считается одним из величайших математиков всех времен за его вклад в теорию чисел, геометрию, теорию вероятностей, геодезию, планетарную астрономию, теорию функций и теорию потенциала (включая электромагнетизм).

Гаусс был единственным ребенком бедных родителей. Он был редкостью среди математиков тем, что был вундеркиндом и сохранял способность производить сложные вычисления в уме большую часть своей жизни. Впечатленные этой способностью и его даром к языкам, учителя и преданная мать рекомендовали его герцогу Брауншвейгскому в 179 г.1, который предоставил ему финансовую помощь для продолжения образования на месте, а затем для изучения математики в Геттингенском университете с 1795 по 1798 год. Новаторская работа Гаусса постепенно сделала его выдающимся математиком той эпохи сначала в немецкоязычном мире, а затем и за его пределами. , хотя он оставался далекой и отчужденной фигурой.

Викторина «Британника»

Викторина по астрономии и космосу

Что делает планету карликовой? Сколько миль в световом году? Что такое квазар? Отправляйтесь в другие миры, проверяя свои знания о космосе, небесных телах и солнечной системе.

Первым значительным открытием Гаусса, сделанным в 1792 году, было то, что правильный многоугольник с 17 сторонами можно построить с помощью только линейки и циркуля. Его значение заключается не в результате, а в доказательстве, которое основывалось на глубоком анализе факторизации полиномиальных уравнений и открыло дверь более поздним идеям теории Галуа. Его докторская диссертация 1797 г. дала доказательство основной теоремы алгебры: всякое полиномиальное уравнение с действительными или комплексными коэффициентами имеет столько корней (решений), сколько его степени (наибольшей степени переменной). Доказательство Гаусса, хотя и не вполне убедительное, отличалось критикой более ранних попыток. Позже Гаусс дал еще три доказательства этого важного результата, последнее к 50-летию первого, что показывает важность, которую он придавал этой теме.

Узнайте о жизни и карьере математического гения Карла Фридриха Гаусса.

Просмотреть все видео к этой статье. по алгебраической теории чисел, Disquisitiones Arithmeticae . Эта книга начинается с первого описания модульной арифметики, дает подробное описание решений квадратных многочленов от двух переменных в целых числах и заканчивается упомянутой выше теорией факторизации. Этот выбор тем и их естественные обобщения определили повестку дня в теории чисел на протяжении большей части XIX века.веке, и постоянный интерес Гаусса к этому предмету стимулировал множество исследований, особенно в немецких университетах.

Второй публикацией было его повторное открытие астероида Церера. Его первоначальное открытие, сделанное итальянским астрономом Джузеппе Пиацци в 1800 году, вызвало сенсацию, но он исчез за Солнцем до того, как удалось провести достаточно наблюдений, чтобы рассчитать его орбиту с достаточной точностью, чтобы узнать, где он снова появится. Многие астрономы соревновались за честь найти его снова, но Гаусс победил. Его успех основывался на новом методе обработки ошибок в наблюдениях, который сегодня называется методом наименьших квадратов. После этого Гаусс много лет работал астрономом и опубликовал крупную работу по вычислению орбит — числовая сторона такой работы была для него гораздо менее обременительна, чем для большинства людей. Будучи чрезвычайно преданным подданным герцога Брауншвейгского, а после 1807 года, когда он вернулся в Геттинген в качестве астронома, герцога Ганноверского, Гаусс чувствовал, что его работа имеет общественную ценность.

Подобные мотивы побудили Гаусса принять вызов по обследованию территории Ганновера, и он часто отсутствовал в полевых условиях, отвечая за наблюдения. Проект, который длился с 1818 по 1832 год, столкнулся с многочисленными трудностями, но привел к ряду достижений. Одним из них было изобретение Гауссом гелиотропа (прибора, отражающего солнечные лучи в виде сфокусированного луча, который можно наблюдать на расстоянии нескольких миль), что повысило точность наблюдений. Другим было его открытие способа сформулировать понятие кривизны поверхности. Гаусс показал, что существует внутренняя мера кривизны, которая не меняется, если поверхность изгибается, но не растягивается. Например, круглый цилиндр и плоский лист бумаги имеют одинаковую внутреннюю кривизну, поэтому на бумаге можно делать точные копии фигур на цилиндре (как, например, в полиграфии). Но сфера и плоскость имеют разную кривизну, из-за чего невозможно составить абсолютно точную плоскую карту Земли.

Оформите подписку Britannica Premium и получите доступ к эксклюзивному контенту. Подписаться сейчас

Гаусс опубликовал работы по теории чисел, математической теории построения карт и многим другим предметам. В 1830-х годах он заинтересовался земным магнетизмом и участвовал в первом в мире исследовании магнитного поля Земли (для его измерения он изобрел магнитометр). Вместе со своим геттингенским коллегой, физиком Вильгельмом Вебером, он сделал первый электрический телеграф, но некоторая ограниченность помешала ему энергично заняться изобретением. Вместо этого он извлек важные математические следствия из этой работы для того, что сегодня называется теорией потенциала, важной ветви математической физики, возникающей при изучении электромагнетизма и гравитации.

Гаусс также писал о картографии, теории картографических проекций. За свое исследование карт, сохраняющих угол, он был удостоен премии Датской академии наук в 1823 году. Эта работа была близка к предположению, что комплексные функции комплексной переменной обычно сохраняют угол, но Гаусс не сделал этого фундаментального утверждения. ясное понимание, оставив его Бернхарду Риману, который глубоко ценил работу Гаусса. У Гаусса были и другие неопубликованные идеи о природе сложных функций и их интегралов, некоторые из которых он поделился с друзьями.

На самом деле Гаусс часто отказывался публиковать свои открытия. Будучи студентом в Геттингене, он начал сомневаться в априорной истинности евклидовой геометрии и подозревал, что ее истинность может быть эмпирической. Для этого должно существовать альтернативное геометрическое описание пространства. Вместо того чтобы опубликовать такое описание, Гаусс ограничился критикой различных априорных защит евклидовой геометрии. Казалось, он постепенно убедился, что существует логическая альтернатива евклидовой геометрии. Однако, когда венгр Янош Бойяи и русский Николай Лобачевский опубликовали свои отчеты о новой неевклидовой геометрии около 1830 года, Гаусс не смог последовательно изложить свои собственные идеи. Можно объединить эти идеи в впечатляющее целое, в котором его концепция внутренней кривизны играет центральную роль, но Гаусс так и не сделал этого. Одни приписывали эту неудачу его врожденному консерватизму, другие — его непрекращающейся изобретательности, которая всегда влекла его к следующей новой идее, третьи — его неспособности найти центральную идею, которая управляла бы геометрией после того, как евклидова геометрия перестала быть уникальной. Все эти объяснения имеют некоторые достоинства, хотя ни одно из них не может быть исчерпывающим объяснением.

Другой темой, по которой Гаусс в значительной степени скрывал свои идеи от современников, были эллиптические функции. В 1812 году он опубликовал отчет об интересном бесконечном ряду и написал, но не опубликовал отчет о дифференциальном уравнении, которому удовлетворяет бесконечный ряд. Он показал, что ряды, называемые гипергеометрическими рядами, могут использоваться для определения многих знакомых и многих новых функций. Но к тому времени он знал, как использовать дифференциальное уравнение для создания очень общей теории эллиптических функций и полностью освободить теорию от ее истоков в теории эллиптических интегралов. Это был крупный прорыв, потому что, как обнаружил Гаусс в 179 г.0s теория эллиптических функций, естественно, трактует их как комплекснозначные функции комплексного переменного, но современная теория комплексных интегралов была совершенно неадекватна для этой задачи. Когда часть этой теории была опубликована норвежцем Нильсом Абелем и немцем Карлом Якоби примерно в 1830 году, Гаусс заметил своему другу, что Абель прошел одну треть пути. Это было точно, но это печальная мера личности Гаусса, поскольку он все еще воздерживался от публикации.

Гаусс сделал меньше, чем мог бы, и в других отношениях. Геттингенский университет был небольшим, и он не стремился расширить его или набрать дополнительных студентов. К концу его жизни через Геттинген прошли математики калибра Рихарда Дедекинда и Римана, и он был полезен, но современники сравнивали его стиль письма с жидкой кашицей: он ясен и устанавливает высокие стандарты строгости, но ему недостает мотивации и может быть медленным и утомительным, чтобы следовать. Он переписывался со многими, но не со всеми, людьми, достаточно опрометчивыми, чтобы написать ему, но мало что делал, чтобы поддерживать их публично. Редким исключением были случаи, когда Лобачевский подвергался нападкам со стороны других русских за его идеи о неевклидовой геометрии. Гаусс достаточно выучил русский язык, чтобы следить за полемикой, и предложил Лобачевского в Геттингенскую академию наук. Напротив, Гаусс написал Бойяи письмо, в котором сообщил ему, что он уже обнаружил все, что Бойяи только что опубликовал.

После смерти Гаусса в 1855 году обнаружение стольких новых идей в его неопубликованных работах распространило его влияние на оставшуюся часть века. Принятие неевклидовой геометрии произошло не с оригинальными работами Бойяи и Лобачевского, а с почти одновременной публикацией общих идей Римана о геометрии, подробного и строгого изложения ее итальянцем Эудженио Бельтрами, а также частных заметок Гаусса и переписка.

Джереми Джон Грей

5.

5: Закон Гаусса — Интегральная форма

1. Последнее обновление

2. Сохранить как PDF

Идентификатор страницы

3927

• Стивен В. Эллингсон
• Политехнический институт Вирджинии и Государственный университет через Инициативу открытого образования Технологических библиотек Вирджинии

Закон Гаусса — один из четырех фундаментальных законов классической электромагнетики, известных под общим названием Уравнения Максвелла . Прежде чем погрузиться в изучение, читателю настоятельно рекомендуется просмотреть раздел 2.4. В этом разделе закон Гаусса возникает из интерпретации электрического поля как плотности потока. Раздел 2.4 на самом деле не определяет закон Гаусса, но вот он:

Закон Гаусса (уравнение \ref{m0014_eGL}) утверждает, что поток электрического поля через замкнутую поверхность равен заключенному заряду. 9{2}\) = C, которые являются единицами заряда.

Закон Гаусса имеет ряд приложений в электромагнитной теории. Один из них, как будет рассмотрено ниже, представляет собой метод вычисления электрического поля в ответ на распределение электрического заряда. Обратите внимание, что способ сделать это, основанный на законе Кулона, описан в разделах 5.1, 5.2 и 5.4. Закон Гаусса предлагает альтернативный метод, который проще или полезнее в определенных приложениях.

Пример \(\PageIndex{1}\): электрическое поле, связанное с заряженной частицей, согласно закону Гаусса.

В этом примере мы демонстрируем способность закона Гаусса предсказывать поле, связанное с распределением заряда. Сделаем это для максимально простого распределения заряда. Частица с зарядом \(q\), расположенная в начале координат, для которой у нас уже есть ответ (раздел 5.1).

Решение

Закон Гаусса применим к любой поверхности , которая окружает заряд, поэтому для простоты мы выбрали сферу радиуса \(r\) с центром в начале координат. 2\) — константы относительно интегрирования, получаем: 92} \nonumber \]

Вот что вы должны вынести из приведенного выше примера:

Закона Гаусса в сочетании с аргументом симметрии может быть достаточно для определения электрического поля из-за распределения заряда. Таким образом, закон Гаусса может быть более простой альтернативой закону Кулона в некоторых приложениях.

---

Эта страница под названием 5.5: Закон Гаусса — Интегральная форма распространяется в соответствии с лицензией CC BY-SA 4.0 и была создана, изменена и/или курирована Стивеном В. Эллингсоном (Инициатива открытого образования технических библиотек Вирджинии) через исходный контент это было отредактировано в соответствии со стилем и стандартами платформы LibreTexts; подробная история редактирования доступна по запросу.

1. Наверх

• Была ли эта статья полезной?

1. Тип изделия

   Раздел или страница

   Автор

   Стивен В. Эллингсон

   Лицензия

   CC BY-SA

   Версия лицензии

   4,0

   Программа OER или Publisher

   Инициатива открытого образования технических библиотек Вирджинии

   Показать оглавление

   нет

2. Теги

   1. Закон Гаусса
   2. источник@https://doi.org/10.21061/electromagnetics-vol-1

4.5 — Экспоненциальные и логарифмические модели

4.5 — Экспоненциальные и логарифмические модели

Экспоненциальный рост

Функция

y = C e ^кт , k > 0

Характеристики

• Асимптотика y = 0 влево
• Проходит через (0,C)
• C является начальным значение
• Увеличение без привязки к правому

Примечания

Некоторые из вещей, для моделирования которых используется экспоненциальный рост, включают рост населения, роста и сложных процентов.

Если вам посчастливилось получить начальное значение, то есть значение, когда x = 0, то вы уже известно значение константы C. Единственное, что необходимо для завершения модели, это иметь одну дополнительную точку на графике. Подставьте значения x, y и C и найдите k.

В качестве альтернативы, почти как обман, вы можете поместить значения x в список 1, значения y в список 2, и выберите опцию ExpReg на калькуляторе TI-82.

Экспоненциальное затухание (убывающая форма)

Функция

y = C e ^-kt , k > 0

Характеристики

• Асимптотика y = 0 вправо
• Проходит через (0,C)
• C — начальное значение
• Убывающая, но ограниченная снизу y=0

Примечания

Экспоненциальный распад и может быть использован для моделирования радиоактивного распада и амортизации.

Модели экспоненциального распада очень быстро уменьшаются, а затем выравниваются, чтобы стать асимптотический по направлению к оси x.

Как и в модели экспоненциального роста, если известно начальное значение, Остальную часть модели довольно легко завершить.

Экспоненциальный спад (возрастающая форма)

Функция

y = C ( 1 — e ^-kt ), k > 0

Характеристики

• Асимптотика y = C вправо
• Проходит через (0,0)
• C — это верхний предел
• Возрастание, но ограниченное сверху значением y=C

Примечания

Модели экспоненциального затухания этой формы могут моделировать продажи или кривые обучения, где там является верхним предел. Это делается путем вычитания экспоненциального выражения из единицы и умножение на верхний предел.

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

Как и в других экспоненциальных моделях, если известен верхний предел, то остальные модели довольно легко выполнить.

Калькулятор не подходит для возрастающей модели, включающей экспоненциальное затухание. напрямую.

Модель Гаусса

Функция

у = а ехр (-(х-с) / б) ²

exp(x) — это другой способ записи e ^x

Характеристики

• Асимптотика по оси x влево и вправо
• Проходит через (0,а)
• a контролирует высоту кривой
• Центрировано относительно x=c
• b контролирует распространение
• в форме колокола

Примечания

Модель Гаусса довольно часто используется в статистике для моделирования распределения оценок.

Модель Гаусса названа в честь немецкого математика Карла Фридриха Гаусса. Это тот самый Гаусс, который разработал основную теорему алгебры. Он симметричен относительно своего среднее, х = с. Вправо от начала координат она сначала убывает медленно, затем быстрее, а затем выравнивается и становится асимптотическим относительно оси x.

Как и модель экспоненциального затухания, модель Гаусса можно превратить в возрастающую функцию путем вычитания экспоненциального выражения из единицы и последующего умножения на верхний предел.

Модель роста логистики

Функция

y = a / (1 + b e ^-kx ), k > 0

Характеристики

• Асимптотика у = а вправо,
• Асимптотика y = 0 влево,
• Проходит через (0, а/(1+b))
• Медленный рост, за которым следует умеренный рост, с последующим медленным ростом

Примечания

Моя любимая модель логистики начинается с медленного роста, за которым следует период умеренный рост, а затем обратно в период медленного роста. Он имеет верхний предел, который не может быть превышен.

Логистическую модель можно использовать для аппроксимации продаж и рекламы (немного рекламы). приводит к небольшому росту продаж, увеличение количества рекламы приводит к умеренному росту продаж и наконец, наступает точка насыщения, когда дополнительная реклама приносит мало пользы с точки зрения продаж) или рост населения, где нет возможности для неограниченного роста (используйте модель экспоненциального роста, если вам это нужно).

Логарифмическая модель

Функция

у = а + б пер х

Характеристики

• Увеличение без привязки вправо
• Проходит через (1,а),
• Очень быстрый рост, за которым следует более медленный рост,
• Общий журнал будет расти медленнее, чем натуральный журнал
• b контролирует скорость роста

Логарифмическая модель имеет период быстрого роста, за которым следует период, когда рост замедляется, но рост продолжает неограниченно увеличиваться. Это делает модель неподходящей где должна быть верхняя граница. Основное отличие этой модели от модель экспоненциального роста заключается в том, что модель экспоненциального роста начинается медленно, а затем увеличивается очень быстро по мере увеличения времени.

Некоторые физические приложения имеют логарифмические модели. Магнитуда землетрясений, интенсивность звука, кислотность раствора.

Землетрясения

R = журнал I

Шкала Рихтера используется для измерения силы землетрясения. Настоящий модель немного сложнее, но она упрощается до показанного уравнения. R это магнитуда землетрясения по шкале Рихтера. I – интенсивность землетрясения, измеренная относительно эталонного значения. Это опорное значение является наименьшей сейсмической активностью, которую можно измеряется и имеет значение I ₀ = 1.

Каждое увеличение на 1 по шкале Рихтера означает величину землетрясение в 10 раз сильнее.

Интенсивность звука

β = 10 log ( I ​​/ I ₀ )

Уровень звука, измеренный в децибелах, определяется по приведенной формуле. Эталонное значение I ₀ равно наименьшая интенсивность звука, слышимая человеческим ухом и примерно равная 1×10 ^-16 ватт на квадратный сантиметр.

В беле 10 децибел. В то время как бел является фактической единицей, такой как метр, литр или грамм, мы используем децибел для всех практических целей. Увеличение на 10 децибел эквивалентно звуку на 10 децибел.

No related posts.