В данном случае помимо соблюдения требования a kk 0 при реализации формул (6) накладываются дополнительные требования, чтобы ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы имел максимальное по модулю значение. Это также достигается перестановкой строк матрицы.
Пример . В качестве иллюстрации преимущества модифицированного метода Гаусса, рассмотрим систему третьего порядка:
Прямой ход метода Гаусса
Исключаем х 1 из второго и третьего уравнений. Для этого первое уравнение умножаем на 0,3 и складываем со вторым, а затем умножаем первое уравнение на (–0,5) и складываем с третьим. В результате получаем
(б
)
Замена второго уравнения третьим не производится, т.к. вычисления выполняются в рамках точной арифметики.
Умножая второе уравнение на 25, и складывая с третьим, получим
(в
)
Обратный ход метода Гаусса
Выполняем вычисления, начиная с последнего уравнения в полученной системе:
Подставляя полученное решение в исходную систему, убеждаемся в его истинности.
Теперь изменим коэффициенты системы таким образом, чтобы сохранить прежнее решение, но при вычислении будем использовать округления в рамках арифметики с плавающей точкой сохраняя пять разрядов. Этому будет соответствовать следующая система
(г
)
Прямой ход метода для системы (г ) повторим по аналогичной технологии с исходной системой (а ).
(д
)
После исключения х 2 третье уравнение примет вид (остальные – без изменения)
15005 х 3 = 15004. (е )
Выполняя обратный ход, получим
Очевидно, что полученные решения и [–0,35; –1,4; 0,99993] различны. Причиной этого является малая величина ведущего элемента во втором уравнении преобразования в (д ). Чтобы это исключить, переставим в (д ) вторую и третью строки
(ж
)
Для данной системы после исключения х 2 из третьего уравнения, оно примет следующий вид
6,002 х 3 = 6,002. (з )
В данном случае, выполняя обратный ход
мы получим решение системы (г ) , которое в точности совпадает с решением исходной системы.
Решая систему (г ) мы использовали модифицированный метод Гаусса, в котором на диагонали должен был находиться максимальный в текущем столбце элемент.
Рассмотрим блок-схему модифицированного метода Гаусса (рис. 2.1).
Рис. 2.1. Блок-схема модифицированного метода Гаусса
Проведем анализ предложенной схемы на примере системы n =3 (=0,001)
(8)
;
.
(*)
Блок 1. Ввод исходных данных:n – порядок системы,A – матрица коэффициентов при неизвестных,b – вектор свободных членов.
Блок 2.I-й цикл прямого хода (дляk , изменяющегося от 1 до предпоследнего значения, т.е. доn –1) обеспечивает исключение из главной диагонали матрицыА элементаa kk =0 благодаря поиску максимального элементаa kk в текущем столбце, осуществляемому в блоках 36 с помощью циклаII.
Затем реализуются расчеты по формулам (6) прямого хода Гаусса в блоках циклов IVиV.
Проведем поблочный анализ в среде рассмотренных циклов IVна примере (8).
Блок 3p =k = 1
Вход в цикл II
Блок 4m =k +1 = 2 доn = 3
Блок 5a 11 = 2 <a 21 = 4 из (*)
Блок 6p = 2
Блок 4m = 2+1 = 3
Блок 5a 21 = 4 <a 31 = 6 из (*)
Блок 6p = 3
Выход из цикла IIи вход в циклIII, блоки 710 выполняют перестановку строк матрицыА поэлементно
Блок 7j = 1 (j от 1 до 3)
Блок 8 r = a 11 = 2 из (*)
Блок 9 a 11 = a 31 = 6
Блок 10 a 31 = r
Блок 7 j = 2
Блок 8 r = a 12 = 1
Блок 9 a 12 = a 32 = 5
Блок 10 a 32 = r = 1
Блок 7j = 3 и по аналогииr =a 13 ;a 13 =a 33 ;a 33 =r = −1.
Выход из цикла IIIи вход вБлок 11 и далее 1213 выполняют аналогичную перестановку значений свободных членов
r =b 1 = 1;b 1 = b 3 = 14;b 3 =r= 1.
Вход в цикл IVс измененной системой
;
;
(**)
для пересчета b
2 вектора
m =k +1 = 1+1 = 2 доn = 3
c = a mk / a kk = a 21 / a 11 = 4/6 из (**)
b 2 =b 2 –c b 1 = 6 – 4/614 = −20/6 из (**)
Вход во вложенный цикл Vдля пересчета второй строки
i = 1 (i от 1 до 3); a 21 = a 21 – с a 11 = 4 – 4/6 6 = 0;
i = 2; a 22 = a 22 – с a 12 = 6 – 4/6 5 = 16/6;
i = 3; a 23 = a 23 – с a 13 = 2 – 4/6 8 = −20/6.
Выход из цикла Vи вход в циклIV
m = 3;c =a 31 /a 11 = 2/6.
Вход в Блок 16
b 3 =b 3 –c b 1 = 1 – 2/614 = −22/6.
Выход из цикла IVи вход в циклVи вход вБлок 17
i = 1 (i от 1 до 3); a 31 = a 31 – с a 11 = 2 – 2/6 6 = 0;
i = 2; a 32 = a 32 – с a 12 = 1 – 2/6 5 = −4/6;
i = 3; a 33 = a 33 – с a 13 = −1 – 2/6 8 = −22/6.
Выход из цикла Vс преобразованной системой
;
;
(***)
и вход по линии А в циклI
k = 2;p =k = 2;m =k +1 = 3; вход вБлок 5
| a 22 | < |a 32 | = | 16/6 | > | 4/6 | из (***).
Выход из цикла IIи вход в циклIII
j = 2 (j от 2 до 3);
r = a kj = a 22 = 16/6; a 22 = a 22 ; a 22 = r = 16/6; из (***)
r =a 23 = −20/6;a 23 =a 23 ;a 23 =r = −20/6; из (***)
В данном случае на диагонали оказался максимальный элемент, поэтому перестановка 2-ой и 3-ей строк не выполняется.
Выход из цикла IIIи вход в циклIвБлок 11
r =b 2 ;b 2 = b 2 ;b 2 =r= −20/6.
Свободный член b 2 остается на своем месте.
Вход в цикл IV
m =k +1 = 2+1 = 3;
c = a mk / a kk = a 32 / a 22 = (–4/6) / (16/6); из (***)
b 3 =b 3 –c b 2 = −22/6 – (–1/4)(–20/6) = −27/6 из (***)
Выход из цикла IVи вход в циклV
i = 2 (i от 2 до 3); a 32 = a 32 – с a 22 = −4/6 – (–1/4) 16/6 = 0;
i = 3;a 33 =a 33 –с a 23 = −22/6 – (–1/4)(–20/6) = −27/6.
Выход из цикла Vи выход из циклаI.
Обратный ход метода Гаусса
В Блоках 1924 реализуются формулы (7).
В Блоке 19 из последнего уравнения находится значениеx n (n = 3)
x 3 =b n / a nn =b 3 / a 33 = (–27/6) / (–27/6) = 1.
Вход в цикл VI(Блок 20), в котором значение переменной циклаk изменяется отn –1 до 1 с шагом (–1)
Блок 21s= 0
Вход в цикл VII(Блок 22)
i = k +1 = 2+1 = 3; n = 3; s = s + a ki x i = 0 + a 23 x 3 = −20/6 1 = −20/6.
Выход из цикла VIIнаБлок 24 в циклVI:
k = 2; x 2 = (b k – s)/ a nn = (b 2 – s)/ a 22 = (–20/6 +20/6)/ a 22 = 0.
k =k –1 = 2–1 = 1;
i = k + 1 = 2; s = 0 + a 12 x 2 = 5 0 = 0;
i = k + 1 = 3; s = 0 + a 13 x 3 = 8 1 = 8;
x 1 = (b 1 –s)/ a 11 = (14 – 8) / 6 = 1.
Выход из последнего цикла VII.
В Блоке
25 (цикл опущен) выполняется
вывод на экран полученного решения СЛАУ
– вектора
т.е.x
i
,i
=1, ...,n
.
В нашем случае (1; 0; 1).
(СЛАУ), состоящая из уравнений с неизвестными:
Предполагается, что существует единственное решение системы, то есть .
В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.
Процесс решения системы линейных уравнений
по методу Гаусса состоит из 2х этапов:
1. Предполагаем, что . Тогда первое уравнение системы делим на коэффициент , в результате получаем уравнение . Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент . В результате система преобразуются к виду: 2. В предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех последующих уравнений и т.д. 3. Получаем систему уравнений с треугольной матрицей:Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные (матрица и правая часть уравнения - ) заданы точно и вычисление ведется без округлений. Для получения решения требуется умножений и делений, то есть порядка операций.
Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой рассмотрим возмущенную систему:
Пусть введена некоторая норма . - называется числом обусловленности матрицы .
Возможны 3 случая:
Число обусловленности матрицы всегда . Если оно велико () , то говорят, что матрица плохо обусловлена. В этом случае малые возмущения правых частей системы , вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей , то погрешность решения будет .
Проиллюстрируем полученные результаты на следующем числовом примере: Дана система
Она имеет решение .
Теперь рассмотрим возмущенную систему:
Решением такой системы будет вектор .
При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения. Объяснить такую "ненадежность" решения можно тем, что матрица почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике:
Такой результат можно было предвидеть в силу плохой обусловленностью матрицы :
Вычисление является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.
Составляем контрольный столбец , состоящий из контрольных элементов системы:
При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнеий. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности.
2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.
Задается некоторый ветор с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения . Вычисляется вектор , и на ряду с исходной системой уравнения решается система .
Пусть и - реально получаемые решения этих систем. Суждение о погрешности искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины и , отличаются не в очень большое число раз.
3) Изменение масштабов - прием, применяющийся для получения представления о реальной величине погрешности, возникающей за счет округлений при вычислениях.
Наряду с исходной системой тем же методом решается система
, где и - числаЕсли бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: . Поэтому при и , не являющихся степенями двойки, сравнение векторов и дает представление о величине вычислительной погрешности
Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.
Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая -я строка умножается на коэффициенты .Если коэффициенты 1%20" alt=" >1 ">, то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:
Пусть по ходу исключения неизвестных получена система уравнений:
, .Найдем такое , что и поменяем местами -е и -е уровнения.
Такое преобразование во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.
Если есть подозрение, что полученное решение сильно искажено, то можно улучшить результат следующим образом. Величина называется невязкой. Погрешность удовлетворяет системе уравнений
.Решая эту систему, получаем приближение к и полагаем
.Если точность данного приближения неудовлетворительна, то повторяем эту операцию.
Процесс можно продолжать до тех пор, пока все компоненты не станут достаточно малыми. При этом нельзя останавливать вычисления только потому, что все компоненты вектора невязки стали достаточно малыми: это может быть результатом плохой обусловленности матрицы коэффициентов.
Рассмотрим для примера матрицу Вандермонда размером 7х7 и 2 различные правые части:
Данные системы были решены двумя способами. Тип данных - float. B итоге получили следующие результаты:
| Обычный метод | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 0.999991 | 1 | 0.999996 | 1 |
| 1.00019 | 1 | 7.4774e-005 | 2,33e-008 |
| 0.998404 | 1 | 0.999375 | 1 |
| 1.00667 | 1 | 0.00263727 | 1,12e-006 |
| 0.985328 | 1 | 0.994149 | 1 |
| 1.01588 | 1 | 0.00637817 | 3,27e-006 |
| 0.993538 | 1 | 0.99739 | 1 |
| 0,045479 | 2,9826e-006 | 0,01818 | 8,8362e-006 |
| 0,006497 | 4,2608e-007 | 0,0045451 | 2,209e-006 |
| 0,040152 | 4,344e-005 | 0,083938 | 2,8654e-006 |
| С выбором ведущего элемента по строке | |||
|---|---|---|---|
| 1 | 2 | ||
| 1 | 2 | 1 | 2 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | -3.57628e-005 | 1,836e-007 |
| 1.00001 | 1 | 1.00031 | 1 |
| 0.999942 | 1 | -0.00133276 | 7,16e-006 |
| 1.00005 | 1 | 1.00302 | 0,99998 |
| 1.00009 | 1 | -0.0033505 | 1,8e-005 |
| 0.99991 | 1 | 1.00139 | 0,99999 |
| 0,000298 | 4,3835e-007 | 0,009439 | 5,0683e-005 |
| 4,2571e-005 | 6,2622e-008 | 0,0023542 | 1,2671e-005 |
| 0,010622 | 9,8016e-007 | 0,29402 | 1,4768e-006 |
Систему уравнений (1.1) представим в виде
Известно большое число схем метода исключения, приспособленных для ручного или машинного счета матриц общего или специального вида.
Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее - к единичной (обратный ход). Очевидно, что если матрица единичная, то x t = b r
Пусть матрица системы (1.3) - верхняя треугольная, поэтому a tj = 0 при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем х п. Подставляя х п в предпоследнее уравнение, находим х а _ х и т. д. Общие формулы имеют вид
При k > I коэффициенты а ы = 0.
Приведем матрицу системы (1.3) к верхней треугольной. Вычтем из второго уравнения системы (1.3) первое, умноженное на такое число, при котором коэффициент при х х обратится в нуль. То же проделаем со всеми остальными уравнениями. В результате все коэффициенты первого столбца, лежащие ниже главной диагонали, обратятся в нуль. Затем, используя второе уравнение, обратим в нуль соответствующие коэффициенты второго столбца. Последовательно продолжая этот процесс, приведем матрицу системы к верхней треугольной форме.
Запишем общие формулы метода Гаусса. Пусть проведено исключение коэффициентов из (А - 1)-го столбца. Тогда останутся уравнения с ненулевыми элементами ниже главной диагонали:
Умножим k-ю строку на число с тк = т > k и вычтем
из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам
Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-ro столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (1.4) называют ОБРАТНЫМ ХОДОМ метода.
Обратный ход можно совершить иначе, если обратить в нуль и все коэффициенты, лежащие выше главной диагонали. Например, элементы п -го столбца обращаются в нуль, если ej^| умножить на (-a^V ax t = б| 2л) , где Ь^ п) - коэффициенты правой части i-го уравнения после указанных преобразований.
На некотором шаге прямого хода может оказаться, что коэффициент aj*" * 0, но мал по сравнению с остальными элементами матрицы системы и, в частности, мал по сравнению с элементами первого столбца. Деление коэффициентов системы на малую величину может привести к значительным ошибкам округления.
Для уменьшения ошибок округления поступают следующим образом. Среди элементов первого столбца а ^ каждой промежуточной матрицы выбирают наибольший по модулю (главный) элемент и путем перестановки i-й строки со строкой, содержащей главный элемент, добиваются того, что главный элемент становится ведущим. Такая модификация метода исключения Гаусса называется методом Гаусса с выбором главного элемента. Случай появления нулевых элементов обходится при этом сам собой.
Для реализации метода требуется примерно п 3 /3 операций типа умножения и п 3 /3 операций типа сложения . Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно п 2 операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ах = b с одной и той же матрицей и различными правыми частями, то общее число операций при решении S систем будет оцениваться величиной (2/3)п 3 + Sn 2 . В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.
При решении системы уравнений
простейшим вариантом метода Гаусса имеют место большие погрешности. Причина заключается в появлении больших коэффициентов, при округлении которых получается большая абсолютная погрешность D ~ 0.5. В свою очередь, большие коэффициенты получаются после деления на маленький ведущий коэффициент 
.
Вывод: для уменьшения влияния ошибок округления надо выбирать ведущий элемент не просто отличный от 0, но и достаточно большой.
Первая модификация метода Гаусса – поиск по строкам. В алгоритме ведущий элемент надо выбирать из условия .
Недостаток модификации. Предположим х i найден с погрешностью D. Тогда при поиске какого-либо х s надо, согласно формуле обратного хода, умножать . При этом погрешность D также умножится на . Если значение велико, то погрешность возрастет.
Вывод: надо обеспечить, чтобы ведущий элемент был не просто большим, а самым большим по модулю в своей строке. Тогда при нормировке ведущей строки все прочие коэффициенты, согласно формуле (5), будут по модулю меньше 1, и ошибки будут уменьшаться .
Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы .
Внимание. При такой замене меняется нумерация неизвестных x i . Чтобы обеспечить такую замену, надо при программировании ввести массив p 1 ,…p n с настоящими номерами неизвестных. В начале прямого хода все p i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p k и p r . При обратном ходе по формуле (7) вычисляются перенумерованные x i . После вычисления всех неизвестных надо положить y]:=x[i] , и массив y[i] будет окончательным решением задачи.
Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p k и p r , а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.
Применение метода Гаусса для решения различных задач линейной алгебры
1. Обращение матриц. Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А –1 . Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен
(1 стоит на i-м месте). Пусть х (i) – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х (i) = e (i) . Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:
Ах = е (1) ; Ах = е (2) ; …; Ах = е ( n ) . (2.1)
Решив эти системы, получим, что найденные решения х (1) , х (2) , …, х (n) являются столбцами матрицы А –1 .
2. Вычисление определителей. В процессе преобразования матрицы А к треугольному виду методом Гаусса мы выполняли с ней следующие действия:
1) переставляли строки или столбцы в зависимости от модификации метода;
2) делили ведущую строку на ненулевой ведущий элемент;
3) к строкам матрицы прибавляли ведущую строку, умноженную на некоторое число.
Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:
1) изменяет знак;
2) делится на тот же элемент;
3) не меняется.
После прямого хода матрица А будет приведена к верхнему треугольному виду с единицами на главной диагонали. Определитель такой матрицы равен, очевидно, 1. С учетом тех изменений, которые претерпевал определитель матрицы А в процессе преобразований, имеем следующую формулу:
det A = (–1) s × a 11 × a 22 ×…× a n n ,
где a j j – ведущие элементы, s – число перестановок строк и/или столбцов при поиске ведущих элементов.
КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ
1. Вручную реализовать метод Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) для данной системы уравнений
и выполнить следующие задания
1) Решить эту систему уравнений
2) Вычислить определитель матрицы данной системы (методом Гаусса – см. п 2 ).
3) Обратить матрицу этой системы (методом Гаусса – см. п 1 ).
В дальнейшем используйте результат решения данной задачи в качестве тестового примера.
2. Составить программу решения линейной системы методом Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) и выполнить обращение матриц с использованием этой программы.
Итак, метод Гаусса применим к любой системе линейных уравнений, он идеально подходит для решения систем, содержащих больше трех линейных уравнений. Метод Гаусса решения СЛАУ с числовыми коэффициентами в силу простоты и однотипности выполняемых операций пригоден для счета на электронно-вычислительных машинах.
Достоинства метода:
a) менее трудоёмкий по сравнению с другими методами;
b) позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение;
c) позволяет найти максимальное число линейно независимых уравнений - ранг матрицы системы.
Существенным недостатком этого метода является невозможность сформулировать условия совместности и определенности системы в зависимости от значений коэффициентов и свободных членов. С другой стороны, даже в случае определенной системы этот метод не позволяет найти общие формулы, выражающие решение системы через ее коэффициенты и свободные члены, которые необходимо иметь при теоретических исследованиях.
Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:
a) нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего приводится к виду единичной матрицы методом Гаусса-Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица:);
b) определения ранга матрицы (согласно следствию из теоремы Кронекера-Капелли ранг матрицы равен числу её главных переменных);
c) численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).
Существуют и другие методы решения и исследования систем линейных уравнений, которые лишены отмеченных недостатков. Эти методы основаны на теории матриц и определителей.
Комбинаторика.
Сколькими способами трое мальчиков - Алмас, Болат, Сабыр - могут стоять в одном ряду? - Это не трудно, напишем все возможные случаи (комбинации): АБС, АСБ, БАС, БСА, САБ, СБА. Всего шесть комбинаций.
Допустим к ним присоединился еще один мальчик Даурен. Каковы будут способы расположения в этом случае? В возможных шести случаях Даурен может стоять первым, вторым, третьим и последним:
ДАБС, ДАСБ, ДБАС, ДБСА, ДСАБ, ДСБА;
АДБС, АДСБ, БДАС, БДСА, СДАБ, СДБА;
АБДС, АСДБ, БАДС, БСДА, САДБ, СБДА;
АБСД, АСБД, БАСД, БСАД, САБД, СБАД.
Всего 24 разных способов. А если еще увеличить количество детей? Каждый раз писать и выводить общее количество трудно. Нам нужно определить число способов, а не виды способов. Нет ли других методов для определение этого число? - Есть. И в теории вероятностей нас больше интересует количество способов расположения, чем виды расположения. Раздел математики, называемый комбинаторикой, дает возможность сразу определить количество таких способов. Ознакомимся с основными понятиями комбинаторики, необходимыми для решения задач теории вероятностей. Это - перестановка, размещение и сочетания. Остановимся на каждом в отдельности.
1. Перестановка. Рассмотрим число случаев в предыдущей задаче. Мы переставили местами буквы А, Б, С и посчитали число всевозможных комбинаций, оно равнялось 6. А когда число мальчиков увеличилось на единицу, переставь местами буквы А, Б, С, Д, мы нашли число всевозможных комбинаций, оно равнялось 24.
ОПРЕДЕЛЕНИЕ. Перестановкой из n различных элементов называются комбинации, которые состоят из n элементов и отличаются друг от друга только порядком их расположения.
Число перестановок из n различных элементов обозначают P n и подсчитывают по формуле:
здесь n! (читается "эн факториал") означает произведение всех натуральных чисел от 1 до n:
Понятно, что один факториал равен единице, 1! = 1, вместе с этим, в математике принято считать что и ноль факториал равен единице. И так 0! = 1.
Вернемся к примеру. Здесь n=3. Следовательно, можно найти искомое число перестановок по формуле (1): P 3 =3!=1 2 3=6. Аналогично, число перестановок из четырех букв равно: P 4 =4!=1 2 3 4=24
Пример 7. Найдем значение выражения с факториалами 8!/6! 2!
Сначала преобразуем 8!=1 2 3 4 5 6 7 8=6! 7 8
Это преобразование подставим в выражение и упростим. 8!/6! 2=6! 7 8/6! 2=7 8/2=28
2. Размещения. Рассмотрим пример. Сколько двузначных чисел (цифры не повторяются) можно записать с помощью цифр 7, 8, 9. Это можно сделать в двух этапах: первый этап - определение количество подбора разрядов десятков числа, он равен 3 (любая из данных 3 цифр может занять разряд десятков); второй этап - определение количество подбора разрядов единиц числа, он равен 2 (любая цифра из оставшихся двух может занять разряд единиц). По правилу умножения из трех чисел можно составить всего 3 2=6 различных двузначных чисел. Действительно, можно в этом убедиться непосредственно записывая эти числа 78, 79, 87, 89, 97, 98, При решении задачи мы расположили по два элемента из трех, причем эти комбинации отличаются либо составом (78, 98), либо порядком их расположения (78, 87).
ОПРЕДЕЛЕНИЕ. Размещением из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающихся друг от друга либо самими элементами, либо порядком их расположения.
Число размещений из n элементов по m элементов обозначают и читают так: "А из эн по эм". Чтобы найти используют формулу:
(15)
Рассмотрим еще один пример. В 5 классе изучают 10 предметов. Сколькими способами можно составить расписание, если в этот день должно быть 4 различных урока?
Чтобы найти число способов расположения 10-ти предметов по четыре предмета, воспользуемся формулой (15) нахождения числа размещений из 10 элементов по 4 элемента:
Итак, 10 предметов по 4 предмета можно расположить 5040 различными способами.
3. Сочетания. Пример. Нужно составить произведения двух различных чисел из данных трех чисел 7, 8, 9.
Учитывая переместительное свойство умножения, имеем: 7 8=56, 7 9=63, 8 9=72. При решении задачи мы отобрали по два элемента из трех, причем эти комбинации отличаются только составом (78, 98), а их расположения не влияют на произведение.
ОПРЕДЕЛЕНИЕ. Сочетанием из n элементов по m элементов (m n) называются комбинации, состоящие из m элементов, взятых из данных n различных элементов, отличающиеся друг от друга только составом.
Число сочетаний из n элементов по m элементов обозначают и читают так: "це из эн по эм". Чтобы найти используют формулу:
(16)
В нашем примере n=3, а m=2. Тогда 
Рассмотрим еще пример. В классе 25 учеников, из них 12 мальчиков. а) Нужно составить дежурство по два человека, причем пары должны состоят либо из мальчиков, либо из девочек. б) Сколько можно создать групп для дежурства, из двух мальчиков и одной девочки?
Решение. а) При решении этой задачи воспользуемся правилом сложения и формулой сочетания. Сначала посчитаем сколько пар можно создать из мальчиков (m 1) и из девочек (m 2), после найдем их сумму (m=m 1 +m 2).
Чтобы определить сколько пар можно создать из 12 мальчиков воспользуемся формулой для подсчета числа сочетаний из 12 элементов по 2 элемента
Из девочек можно создать 78 различных пар. Тогда по два мальчика и по две девочки всего можно создать m=66+78=144 различных пар.
б) При решении этой задачи воспользуемся правилом умножения и формулой сочетания. В группе два мальчика и одна девочка. Сначала посчитаем сколькими способами можно выбрать из 12 мальчиков по два мальчика (m 1) и из 13 девочек одну девочку (m 2), затем перемножим полученные результаты (m=m 1 m 2).
Из 12 мальчиков 2 мальчика можно выбрать 66 различными способами. А из 13 девочек 1 девочку можно выбрать следующим образом:
Тогда группу из двух мальчиков и из одной девочки можно создать m=66 13=856 различными способами.
Определение матрицы. Определители второго и третьего порядков, их основные свойства. Миноры и алгебраические дополнения, разложение определителя по строке (столбцу). Методы вычисления определителей. Понятие об определителе n-го порядка.
Определение 1.1 . Матрицей называется прямоугольная таблица чисел.
Обозначения: А – матрица, - элемент матрицы, номер строки, в которой стоит данный элемент, номер соответствующего столбца; m – число строк матрицы, n – число ее столбцов.
Определение 1.2 . Числа m и n называются размерностями матрицы.
Определение 1.3. Матрица называется квадратной , если m = n. Число n в этом случае называют порядком квадратной матрицы.
Каждой квадратной матрице можно поставить в соответствие число, определяемое единственным образом с использованием всех элементов матрицы. Это число называется определителем.
Определение 1.4. Определителем второго порядка называется число, полученное с помощью элементов квадратной матрицы 2-го порядка следующим образом:
.
При этом из произведения элементов, стоящих на так называемой главной диагонали матрицы (идущей из левого верхнего в правый нижний угол) вычитается произведение элементов, находящихся на второй, или побочной, диагонали.
1. 
2.
Определение 1.5 . Определителем третьего порядка называется число, определяемое с помощью элементов квадратной матрицы 3-го порядка следующим образом:
А` , называемая транспонированной по отношению к матрице А , элементы которой связаны с элементамиА соотношением a` ij = a ji .
