15. Теория Кронекера-Капелли.

КРОНЕКЕРА - КАПЕЛЛИ ТЕОРЕМА

критерий совместности системы линейных у р а в н е н и н: для совместности системы уравнений 

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

оказательство (условия совместности системы)

Необходимость

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

[править]Достаточность

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

[править]Следствия

• Количество главных переменных системы равно рангу системы.

• Совместная система будет определена (её решение единственно), если ранг системы равен числу всех её переменных.

(условие совместности системы) (Леопольд Кронекер (1823-1891) немецкий математик)

            Теорема: Система совместна (имеет хотя бы одно решение) тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы.

RgA = RgA*.

            Очевидно, что система (1) может быть записана в виде: x1   + x2  + … + xn 

 

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

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

            2) Если RgA = RgA*, то это означает, что они имеют один и тот же базисный минор. Столбец свободных членов – линейная комбинация столбцов базисного минора, те верна запись, приведенная выше.

Пример. Определить совместность системы линейных уравнений:

 

A = 

~   .                              RgA = 2. A* =             RgA* = 3.

Система несовместна.

 

Пример. Определить совместность системы линейных уравнений.

                     А =  ;    = 2 + 12 = 14 не равно 0;    RgA = 2;

A* = 

         RgA* = 2. Система совместна. Решения: x₁ = 1;  x₂ =1/2.

16.Решение систем линейных уравнений методом Гаусса. Формулы Крамера.

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

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

1.1.1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемыйсхемой единственного деления.

Прямой ход состоит из n - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a₁₁ ¹ 0. Будем называть его главным элементом 1-го шага.

Найдем величины

q_i1 = a_i1/a₁₁   (i = 2, 3, …, n),

называемые множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾ ,

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .

a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾ .

в которой a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам

a_ij⁽¹⁾ = a_ij − q_i1a_1j    ,    b_i⁽¹⁾ = b_i − q_i1b₁.

2-й шаг. Целью этого шага является ислючение неизвестного x₂ из уравнений с номерами i = 3, 4, …, n. Пустьa₂₂⁽¹⁾ ≠ 0, где a₂₂⁽¹⁾ ­– коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага

q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾   (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему

            a₁₁x₁ + a₁₂x₂ +      a₁₃x₃ +   … + a_1nx_n =      b₁     ,

                        a₂₂⁽¹⁾x₂ +   a₂₃⁽¹⁾x₃ +          … +         a_2n⁽¹⁾ =     b₂⁽¹⁾        ,

                                        a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n =   b₃⁽²⁾  ,

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                                        a_n3⁽²⁾x₃ +          … +         a_nn⁽²⁾x_n = b_n⁽²⁾        .

Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам

a_ij⁽²⁾ = a_ij⁽¹⁾ – q_i2a_2j⁽¹⁾   ,    b_i⁽²⁾ = b_i⁽¹⁾ – q_i2b₂⁽¹⁾.

Аналогично проводятся остальные шаги. Опишем очередной k-й шаг.

k-й шаг. В предположении, что главный (ведущий) элемент k-го шага a_kk^(k–1) отличен от нуля, вычислиммножители k-го шага

q_ik = a_ik^(k–1) / a_kk^(k–1)   (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на q_k+1,k, q_k+2,k, …, q_nk.

После (n - 1)-го шага исключения получим систему уравнений

            a₁₁x₁ + a₁₂x₂ +      a₁₃x₃ +   … +  a_1nx_n =        b₁        ,

                        a₂₂⁽¹⁾x₂ +   a₂₃⁽¹⁾x₃ +          … +            a_2n⁽¹⁾x_n =            b₂⁽¹⁾        ,

                                        a₃₃⁽²⁾x₃ +          … +            a_3n⁽²⁾x_n =            b₃⁽²⁾        ,

            .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                                                                a_nn^(n–1)x_n =   b_n^(n–1) .

матрица A^(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n–1. Осуществляя обратную подстановку, далее последовательно находимx_n–1, x_n–2, …, x₁. Вычисления неизвестных здесь проводятся по формулам

x_n = b_n^(n–1) / a_nn^(n–1),

x_k = (b_n^(k–1) – a_k,k+1^(k–1)x_k+1 – … – a_kn^(k–1)x_n) / a_kk^(k–1), (k = n – 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk^(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

1.1.2. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k-м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

a_ij^(k) = a_ij^(k–1) − q_ika_kj , b_i^(k) = b_i^(k–1) − q_ikb_k^(k–1) , i = k + 1, …, n.

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

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что |q_ik| ≤ 1 для всех k = 1, 2, …, n – 1 иi = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что наk-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

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

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_i1j1. Первое уравнение системы и уравнение с номером i₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_i1 из всех уравнений, кроме первого.

На k-м шаге метода среди коэффициентов a_ij^(k–1) при неизвестных в уравнениях системы с номерами i = k, …, nвыбирают максимальный по модулю коэффициент a_ikjk^(k-1). Затем k-е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: x_jn, x_jn–1, …, x_j1.

Метод Крамера состоит в том, что мы последовательно находим главный определитель системы (5.3), т.е. определитель матрицы А

 = det (a_{i j})

и n вспомогательных определителей  _i (i= ), которые получаются из определителя  заменой i-го столбца столбцом свободных членов.

Формулы Крамера имеют вид:

  x _i =  _i ( i  =  ).                                                (5.4)

Из (5.4) следует правило Крамера, которое дает исчерпывающий ответ на вопрос о совместности системы (5.3): если главный определитель системы отличен от нуля, то система имеет единственное решение, определяемое по формулам:

x _i =  _i / .

Если главный определитель системы  и все вспомогательные определители  _i = 0 (i=  ), то система имеет бесчисленное множество решений. Если главный определитель системы  = 0, а хотя бы один вспомогательный определитель отличен от нуля, то система несовместна.

Пример 2.14. Решить методом Крамера систему уравнений:

                                               x₁ +   x₂ +  x₃ +      x₄ = 5,

                                               x₁ + 2x₂ -   x₃ +    4x₄ = -2,

                                             2x₁ -  3x₂ -   x₃ -     5x₄ = -2,

                                             3x₁ +   x₂ +2x₃ + 11 x₄ = 0.

Решение. Главный определитель этой системы

 

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

              

                  

Отсюда x₁ =  ₁/ = 1, x₂ =  ₂/ = 2, x₃ =  ₃/ = 3, x₄ =  ₄/ = -1, решение системы - вектор С=(1, 2, 3, -1)^T.