Численные методы линейной алгебры. Численные методы решения СЛАУ. Метод Гаусса. Метод прогонки

Страницы работы

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.

Фрагмент текста работы

1. ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ

В разделе «Численные методы линейной алгебры» рассматриваются численные методы решения систем линейных алгебраических уравнений (СЛАУ)  и численные методы решения задач на собственные значения и собственные векторы матриц.

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

1.1. Численные методы решения СЛАУ

Из прямых методов решения СЛАУ рассмотрим методы Гаусса и прогонки.

1.1.1. Метод Гаусса

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

Пусть дана СЛАУ

a11x1 + a12x2 +...+ a1n xn = b1 a21x1 + a22x2 +...+ a2n xn = b2

................................

an1x1 + an2x2 +...+ ann xn = bn

Запишем расширенную матрицу системы:

                                                         x1         x2                x3 L xn             b

Ведущаястрока →     a11       a12             a13 L a1n        b1 (− a21a11);(− a31a11);K;(− an1a11)

                                                 a21       a22             a23 L a2n             b2 

                                              a31       a32             a33 L a3n           b3         1−й шаг→        

 L L L L L L 

                                              an1       an2             an3 L ann           bn 

Ведущийстолбец

На первом шаге алгоритма Гаусса выберем диагональный элемент a11 ≠ 0(если он равен 0, то первую строку переставляем с какой-либо нижележащей строкой) и объявляем его ведущим, а соответствующую строку и столбец, на пересечении которых он стоит - ведущими. Обнулим элементы a21,...,an1 ведущего столбца. Для этого сформируем числа (− a21a11);(− a31a11);...;(− an1a11). Умножая ведущую строку на число (− a21a11), складывая со второй и ставя результат на место второй строки, получим вместо элемента

a21 нуль, а вместо элементов a2 j, j = 2,n , b2  – соответственно элементы a12 j = a2 j + a1j (− a21 a11), j = 2,n , b21 = b2 + b1(− a21a11) и т.д. Умножая ведущую строку на число (− an1 a11), складывая с n-ой строкой и ставя результат на место n-ой строки, получим вместо элемента an1 нуль, а остальные элементы этой строки будут иметь вид: a1nj = anj + a1j (− an1a11), bn1 = bn + b1(− an1a11). Сохраняя ведущую строку неизменной, получим в результате 1-го шага алгоритма Гаусса следующую матрицу:

                                                      x1         x2                x3 L xn             b


a11

a12

a13 L a1n                     b1

0

a122

a123 L a12n               b21

0

L

0

a321

L

a1

a331 L a31n               b31

L L L L

a1 L a1                         b1



Ведущаястрока →                                  (− a132 a122);K;(− a1n2 a122)

                                                                                                2−йшаг→   






                                                         n2           n3                       nn           n

Ведущийстолбец

На втором шаге алгоритма Гаусса в качестве ведущего элемента выбирается элемент a221 ≠ 0 (если он равен нулю, то вторую строку взаимно меняем на нижележащую строку).

Формируются числа − aa3211 ;...;aa1n1222 , которые ставятся около ведущей строки. 22

Умножая ведущую строку на число − aa132122 и складывая результат с третьей строкой,

получим вместо элемента a321 нуль, а вместо элементов a31 j , j = 3,n, b31, Σ13 – элементы

a32j = a31 j + a12 j − aa132122 ,         j = 3,n, b32 = b31 + b21− aa132122  ,. И так далее. Умножая ведущую 

строку на число − aa1n1222  , складывая результат с n-ой строкой и ставя полученную сумму 

на место n-ой строки, получим вместо элемента a1n2 нуль, а вместо элементов a1nj , bn1 , Σ1n - элементы anj2 = a1nj + a12j− aa1n1222 ,           j = 3,n, bn2 = bn1 + b21− aa1n1222  . Сохраняя 1-ую и 2-ую строки матрицы неизменными, получим в результате второго шага алгоритма Гаусса следующую матрицу: 

                                                        x1         x2                x3 L xn             b

a11

0

a12 a122

a13 a123

L an1               b1

L a12n           b21

0

0

a332

L a32n           b32

L

0

L

0

L

a2

L L L

L a2                 b2







Ведущаястрока →                                    3−й шаг→L (n−1)−й шаг→



                                                                 n3                       nn         n 

Ведущийстолбец

После (n-1)-го шага алгоритма Гаусса получаем следующую расширенную матрицу, содержащую верхнюю треугольную матрицу СЛАУ:

                      x1       x2             x3 xn              b                                     

                  a11      a12             a13 L a1n                b1              

                 00 a0122 aa133232 LL aa1322nn            bb3212                             

                                                                 

L L L L L L L

                  0     0         0 L annn−1         bnn−1         

Прямой ход алгоритма Гаусса завершен.

В обратном ходе алгоритма Гаусса из последнего уравнения сразу определяется x n , из предпоследнего - x n1 и т.д. Из первого уравнения определяется x1.

annn1xn = bnn1                             ⇒ x n

an−2 xn−1 + ann−−12nx n = bnn−−12        ⇒ x n−1  n− −1n 1

...................................

         a x11 1+...+a x1n n = b1                  ⇒ x1

Замечание 1. Если элементы какой-либо строки матрицы системы в результате преобразований стали равными нулю, а правая часть не равна нулю, то СЛАУ несовместна, поскольку не выполняются условия теоремы Кронекера-Капелли.

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

Замечание 3. В результате прямого хода метода Гаусса можно вычислить определитель матрицы A исходной СЛАУ: 

det A = (−1) p a11a122a332 ⋅...⋅annn−1

При этом с помощью множителя (−1) p , где p - число перестановок строк в процессе прямого хода,  учитываются соответствующие перемены знаков вследствие перестановок строк. 

Замечание 4. Метод Гаусса можно применить для обращения невырожденной (det A ≠ 0) матрицы. 

Действительно, пусть требуется обратить невырожденную матрицу A = [aij ], i, j =1,n . Тогда, сделав обозначение A−1 = X , X = [xij ], i, j =1,n , можно выписать

1

0

матричное уравнение AX = E , где E - единичная матрица E = ...

 0 которого можно записать цепочку СЛАУ 

                x11  1      x12   0        x1n   0

0

1

...

0

...

...

...

...

0

0 , на основе

...

1

A⋅xx...21n1  = ...00,       Axx...n222  = ...10,        … A⋅xxnn    ...10 ,  

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

x1n x2n ... xnn ... ... ... ...

             x12        x22       ...    xn2

             x11        x21       ...    xn1 b1        b2        .    bn

a11               a12            ...         a1n   1          0          ...         0 a21               a22            ...         a2n   0          1          ...         0

... ... ... ... ... ... ... ... ... an1 an2 ... ann 0 0 ... 1

        В результате применения (n −1)-го шага метода Гаусса получаем:

При этом первый столбец (x11 x21 ... xn1)T обратной матрицы определяется в обратном ходе метода Гаусса

Похожие материалы

Информация о работе

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.