1610841784-4ddd8b6ff40e9cbd93e57c95925d7436 (824186), страница 2

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

Текст из файла (страница 2)

Прямоугольная таблица из m строк и nстолбцов с элементами из F называется матрицей размера m × n надF:c11 c12 . . . c1nc 21 c22 . . . c2n cij ∈ F. . . . . . . . . . . . . . . . . . .cm1 cm2 . . . cmnМножество всех таких матриц обозначается Mm,n(F ).a11x1 + a12x2 + · · · + a1nxn = b1, a x + a x + · · · + a xn = b ,21 122 22n2...am1x1 + am2x2 + · · · + amnxn = bma11 a12 . .

. a1na 21 a22 . . . a2n A= — матрица системы (m × n);. . . . . . . . . . . . . . . . . . . .am1 am2 . . . amn b1b  B =  ..2  — столбец свободных членов (матрица m × 1); . bma11 a12 . . . a1n b1a 21 a22 . . . a2n b2 (A|B) = . . . . . . .

. . . . . . . . . . . . . . . . .am1 am2 . . . amn bm— расширенная матрица системы (размера m × (n + 1)).Для наглядности выделим последний столбец:a11 a12 . . . a1naa22 . . . a2n(A|B) =  21. . . . . . . . . . . . . . . . . . . .am1 am2 . . . amnb1b2 ... bmОбозначения. Пустьc11 c12 . . . c1nc 21 c22 . . . c2n C= ∈ Mm,n(F ).. . . .

. . . . . . . . . . . . . . .cm1 cm2 . . . cmni-я строка матрицы C:Ci = (ci1 ci2 . . . cin) ∈ M1,n(F )c1jc (j)j-й столбец матрицы C:C=  2j ∈ Mm,1(F ) ... cmjТогдаC1C  2C =  ..  = C (1) C (2) . . . C (n) . CmЭлементарные преобразования строк матрицыI типа: Переставить местами i-ю и j-ю строки матрицы (i 6= j)C1 ..  .  Ci  . .

C= . C  j ..  . CmC1 ..  .  Cj  . ′. C = . C  i ..  . CmII типа: Прибавить к i-й строке j-ю (i 6= j), умноженную на константуα∈FЗдесьC1 ..  .  Ci  . . C= . C  j ..  . CmC1...Ci + αCj ′..C =.Cj...CmCi + αCj = (ci1 + αcj1 . . . cin + αcjn)Матрица C ∈ Mm,n(F ) называется ступенчатой (имеет ступенчатый вид),если существуют целые числа r, k1, . . . , kr такие, что• 1 ≤ r ≤ m;• 1 ≤ k1 < k2 < · · · < kr ≤ n;• если i > r, то cij = 0 при всех j = 1, . . . , n;• если i ≤ r, то cij = 0 при всех j < ki, но ciki 6= 0.ИДЕЯ метода Гаусса:при помощи э.п.

превратить данную систему в «хорошую» (ступенчатую),т.е. такую, для которой множество решений легко найти.2. Решение систем линейных уравненийметодом Гаусса(продолжение)a11x1 + a12x2 + · · · + a1nxn = b1, a x + a x + · · · + a xn = b ,21 122 22n2...am1x1 + am2x2 + · · · + amnxn = bma11 a12 . . . a1naa22 . .

. a2n(A|B) =  21. . . . . . . . . . . . . . . . . . . .am1 am2 . . . amnb1b2 ... bm— расширенная матрица системы (размера m × (n + 1)).Элементарные преобразования строк матриц:I типа: Переставить местами i-ю и j-ю строки (i 6= j);II типа: Прибавить к i-й строке j-ю (i 6= j), умноженную на константуα ∈ F.Предложение.Если расширенная матрица системы (2) получается из расширеннойматрицы системы (1) при помощи цепочкиэлементарных преобразований I и II типа,то системы (1) и (2) эквивалентны.Доказательство.Достаточно показать, что множество решений не меняется при одномэлементарном преобразовании (э.п.)1) Пусть (2) получается из (1) э.п. I типа.(?) Множества решений этих систем совпадаютЕсли (c1, .

. . , cn) — решение (1), то (c1, . . . , cn) — решение (2).Обратное очевидно.2) Пусть (2) получается из (1) э.п. II типа.(?) Множества решений этих систем совпадаютДопустим, (c1, . . . , cn) — решение системы (1).Система (2) отличается от (1) только в одном уравнении:i-е уравнение системы (2) имеет вид(ai1 + αaj1)x1 + · · · + (ain + αajn)xn = bi + αbjЕсли i-е и j-е уравнения системы (1) выполнены, т.е.ai1c1 + · · · + aincn = bi,aj1c1 + · · · + ajncn = bj ,то (∗∗) также выполнено при xi = ci.Значит, (c1, .

. . , cn) — решение системы (2).(∗∗)Мы доказали, что если (2) получается из (1) э.п. II типа,то множество решений системы (1) содержится в множестве решенийсистемы (2).Обратное вложение вытекает из следующего наблюдения:ВСЕ Э.П. ОБРАТИМЫ(1)(2) ⇒ (2)(1)(i) + α(j)»,Например, если (2) получено из (1) э.п. «(i)(i) − α(j)».то (1) получается из (2) э.п. «(i)Напомним, что матрица C ∈ Mm,n(F ) называется ступенчатой (имеетступенчатый вид), если существуют целые числа r, k1, . . . , kr такие, что• 1 ≤ r ≤ m;• 1 ≤ k1 < k2 < · · · < kr ≤ n;• если i > r, то cij = 0 при всех j = 1, . . .

, n;• если i ≤ r, то cij = 0 при всех j < ki, но ciki 6= 0.Теорема 1. Любая матрица C ∈ Mm,n(F ) над полем F , содержащая хотьодин ненулевой элемент, может быть приведена к ступенчатому видупоследовательностью э.п. строк I и II типа.(«Прямой ход» метода Гаусса)Доказательство.Индукция по m.m = 1: C = (c11 . . .

c1n)Есть хоть одно ненулевое c1j ,выбираем k1 = минимальному такому j (r = 1).m − 1 → m:Если есть хоть одна нулевая строка (содержащая только 0), то:1. Ставим ее на последнее место преобразованием I типа;2. Применяем предположение индукции – приводим матрицу, состоящуюиз первых m − 1 строк к ступенчатому виду.Получаем ступенчатую матрицу.Поэтому полагаем, что КАЖДАЯ строка матрицы C содержит хоть одинненулевой элемент.Для каждого i = 1, . . . , m обозначимni = min{j : cij 6= 0},1 ≤ ni ≤ nПусть k = min{ni | i = 1, .

. . , m}.Выберем i, у которого ni = k.Применяя преобразование I типа, поставим i-ю строку на 1-е место.Обозначим полученную матрицу C ′C0 . . . 0 c′1k . . . . . . . . .0 . . . 0 c′.........′2kC =,. . . . . . . . . . . . . . . . . . . . . . . . . . . .0 . . . 0 c′mk . . . . . . . . .c′1k = cik 6= 0Для каждого j = 2, . .

. , m выполним следующее преобразование II типа:c′jkк j-й прибавим 1-ю, умноженную на − ′c1kC′0 c′1kc′1 k+1c′′2 k+10 ...... ...0...00......C ′′ = . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .0 . . . 0 0 c′′m k+1 . . . . . .Для каждого j = 2, .

. . , m выполним следующее преобразование II типа:c′jkк j-й прибавим 1-ю, умноженную на − ′c1kC′0 . . . 0 c′1k c′1 k+1 . . . . . .′′0...00c......2 k+1C ′′ = . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .′′0 . . . 0 0 cm k+1 . . . . . .Если k = n, то доказательство завершено: C ′′ имеет ступенчатый вид(r = 1, k1 = k = n).Если k < n, то по индукции приведем «маленькую» матрицу (m − 1) ×(n − k) к ступенчатому виду — те же э.п.

строк приведут C ′′ к искомомувиду.Определение. Система линейных уравнений называется ступенчатой(имеет ступенчатый вид), если расширенная матрица этой системыимеет ступенчатый вид.Следствие.Любая нетривиальная система линейных уравнений над полем F можетбыть приведена к ступенчатому виду последовательностью э.п. I и II типа.a x + · · · + a1nxn = b1, 11 1...am1x1 + · · · + amnxn = bmma11 . .

. a1n. . . . . . . . . . . . . .am1 . . . amn ′′ x = b′ ,x+···+aa111n n 11... ′am1x1 + · · · + a′mnxn = b′mmb1... bma′11 . . . a′1n. . . . . . . . . . . . . .a′m1 . . . a′mn′b1... b′m(«Обратный ход» метода Гаусса)Лемма. Любая ступенчатая матрица C ∈ Mm,n(F ) над полем F припомощи некоторой последовательности э.п. строк I и II типа может бытьпревращена в ступенчатую матрицуT = tijразмера m × nс теми же r, k1, .

. . , kr , в которойtikj = 0приi 6= jtjkj = cjkj 6= 0(i = 1, . . . , m, j = 1, . . . , r)приj = 1, . . . , r.Доказательство. Индукцией по r (r = 1 — тривиально)r − 1 → r:00 ...0C=00 ...0... 0c1k1 . . . c1k2 . . . . . . . . .. . . . . . . . . 0 c2k2 . . . . . . . .

.c1kr−1c2kr−1. . . c1kr. . . c2kr... ... ...... ...... ... ... ...... ... ...... ...... ... 0... ... ...... ...cr−1 kr−1 . . . cr−1 kr... ... ... ...0 crkr... ... ...... ...... ... ... ...... ...... ... ...... ...... ... ... ...... ...... ... ...... ...... ... ... ...... ...ciki 6= 0 при всех i = 1, . . . , rПрименим э.п. строк II типа «(i)... ....... . ..

. .. . .. . .0 . . .0c(i) − ikr (r)» для i = 1, 2, . . . , r − 1crkrПолучимC00 ...0′C =00 ...0C ′,... 0c1k1 . . . c1k2 . . . . . . . . .. . . . . . . . . 0 c2k2 . . . . . . . . .c1kr−1... 0c2kr−1... 0∗∗∗. . . . . . ∗∗∗... 0∗∗∗0 crkr . . .

... ... 0 ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... 0... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...cr−1 kr−1∗∗∗... ... 0ПолучимC00 ...0′C =00 ...0C ′,... 0c1k1 .

. . c1k2 . . . . . . . . .. . . . . . . . . 0 c2k2 . . . . . . . . .c1kr−1... 0∗∗∗c2kr−1... 0∗∗∗... ... ...... ...... ... ... ...... ... ...... ...... ... 0... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...cr−1 kr−1. . . . . . ∗∗∗... 0∗∗∗0 crkr . . . ... ...

0 ... ... ...... ... 0и применим предположение индукции к «маленькой» матрице:ПолучимC00 ...0′C =00 ...0C ′,... 0c1k1 . . . c1k2 . . . . . . . . .. . . . . . . . . 0 c2k2 . . . . . . . . .c1kr−1... 0c2kr−1... 0∗∗∗. . . . . . ∗∗∗∗∗∗... 00 crkr .

. . ... ... 0 ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... 0... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...... ... ...... ...... ... ... ...cr−1 kr−1∗∗∗... ... 0и применим предположение индукции к «маленькой» матрице:при э.п. первых r − 1 строк kr -й столбец не изменяется.Алгоритм решения системы линейных уравнений(метод исключения неизвестных, метод Гаусса)Исходная система (нетривиальная):a11x1 + a12x2 + · · · + a1nxn = b1, a x + a x + · · · + a xn = b ,21 122 22n2...am1x1 + am2x2 + · · · + amnxn = bm• Шаг 1: Записываем расширенную матрицу исходной системыa11 a12 .

. . a1naa22 . . . a2n(A|B) =  21. . . . . . . . . . . . . . . . . . . .am1 am2 . . . amnb1b2 ... bm• Шаг 2: Приводим (A|B) к ступенчатому виду э.п. строк(A|B)0 . . . 0 c1k1 . . . . . . . . . . . . . .0 . . . . . .0 c2k2 . . . . . . . .. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .0 crkr . . .0 . . . . . . . . . . . .(C|D) = 0 . . . . . . . . . . . . . . . . . . . . . . . 00 . . . . . . . . . . . . . . . . . . . . . . . 0. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .0 .......................Напомним, что ciki 6= 0 для i = 1, . . . , r.0d1d2...drdr+10 ... 0• Шаг 2: Приводим (A|B) к ступенчатому виду э.п. строк(A|B)0 . . . 0 c1k1 . . . . . . . . . . . . . .0 . . . . . .0 c2k2 . . . . . . . .. . . .

Характеристики

Список файлов лекций