«Н. И. Яцкин АЛГЕБРА ТЕОРЕМЫ И АЛГОРИТМЫ Допущено учебно-методическим советом по математике и механике Учебно-методического объединения по классическому университетскому образованию РФ в качестве учебного пособия для ...»

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Ивановский государственный университет

Н. И. Яцкин

АЛГЕБРА

ТЕОРЕМЫ И АЛГОРИТМЫ

Допущено учебно-методическим советом

по математике и механике

Учебно-методического объединения

по классическому университетскому образованию РФ

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

Иваново Издательство «Ивановский государственный университет»

2006 ББК 22.14 Я 936 Яцкин, Н. И.

Алгебра : Теоремы и алгоритмы : учеб. пособие / Н. И. Яцкин. — Иваново :

Иван. гос. ун-т, 2006. — 506 с.

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

введение в линейную алгебру, алгебра комплексных чисел и алгебра многочленов.

Пособие предназначено для студентов вузов, обучающихся по направлению «Математика. Компьютерные науки».

Печатается по решению редакционно-издательского совета Ивановского государственного университета Рецензенты:

доктор физико-математических наук, профессор В. Г. Дурнев (Ярославский государственный университет) доктор физико-математических наук, профессор Б. Я. Солон (Ивановский государственный химико-технологический университет) © Яцкин Н. И., ISBN 5-7807-0562-

ОГЛАВЛЕНИЕ

Предисловие............................. Глава 1. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ И АЛГЕБРА МАТРИЦ............................ § 1. Системы линейных уравнений и их решения. Матрицы и действия над ними......................... 1.1. Развернутая запись системы линейных уравнений........ 1.2. Матрицы........................... 1.3. Матрицы-столбцы (арифметические векторы).......... 1.4. Матричная запись для с.л.у. Множество решений с.л.у....... 1.5. Однородные с.л.у........................ § 2. Законы матричной алгебры................... 2.1. Аксиомы поля........................ 2.2. Алгебраическая система матриц. Операция транспонирования.. 2.3. Законы для алгебраических операций над матрицами...... § 3. Свойства решений систем линейных уравнений........ 3.1. Свойства решений однородных и неоднородных с.л.у........ 3.2. Линейные подпространства пространства Rn.......... 3.3. Подмножества решений однородных и неоднородных с.л.у..... § 4. Равносильные системы линейных уравнений. Элементарные преобразования. Понятие о методе Гаусса........... 4.1. Равносильные с.л.у....................... 4.2. Элементарные преобразования с.л.у............... 4.3. Расширенная матрица с.л.у. Матричное выражение элементарных преобразований над с.л.у................... 4.4. Идея метода Жордана Гаусса (на примере).......... § 5. Метод Жордана Гаусса для матриц............. 5.1. Матрицы ступенчатого вида, вида Жордана Гаусса, модифицированного вида Жордана Гаусса, скелетного вида...... 5.2. Теорема Жордана Гаусса для матриц............. 6.3. Случай квадратной с.л.у. Альтернатива Фредгольма....... § 7. Некоторые типовые задачи: системы линейных уравнений с параметром, линейные матричные уравнения.......... 7.2. Линейные матричные уравнения................

Глава 2. АРИФМЕТИЧЕСКИЕ ЛИНЕЙНЫЕ ПРОСТРАНСТВА И

ИХ ПОДПРОСТРАНСТВА. БАЗИСЫ И РАЗМЕРНОСТИ..

§ 8. Системы векторов в пространстве Rn и их линейные оболочки. 8.1. Конечные системы арифметических векторов и соответствующие 8.2. Линейная оболочка конечной с.в................. 8.3. Критерий принадлежности вектора линейной оболочке системы векторов............................ § 9. Линейно зависимые и линейно независимые системы векторов 9.1. Понятие линейно зависимой (линейно независимой) с.в...... 9.2. Критерий линейной зависимости (линейной независимости) с.в... 9.3. Свойства линейно зависимых (линейно независимых) с.в...... 9.4. Примеры линейно независимых с.в................ § 10. Базисы в линейных подпространствах пространства Rn.... 10.1. Понятие базиса в линейном подпространстве арифметического линейного пространства..................... 10.2. Свойство единственности для разложения по базису....... § 11. Равномощность базисов в подпространстве. Понятие размерности подпространства. Ступенчатый ранг матрицы...... 11.1. Теорема о равномощности всех базисов в данном подпространстве 11.2. Понятие размерности для линейного подпространства в пространстве Rn........................... 11.3. Размерность подпространства решений однородной с.л.у..... § 12. Столбцовый и строчный ранги матрицы............ 12.1. Ранг системы векторов и его свойства............. 12.2. Столбцовый и строчный ранги матрицы............ 12.3. Инвариантность столбцового (строчного) ранга при элементарных преобразованиях над строками (столбцами).......... 12.4. Первая теорема о ранге матрицы............... 12.5. Ранг матрицы и исследование с.л.у. (теорема Кронекера Капелли)............................. § 13. Алгоритмы построения базисов и вычисления размерностей и 13.1. Два способа задания линейных подпространств в пространстве Rn 13.2. Базис и размерность для нуль-пространства матрицы...... 13.3. Базис и размерность для линейной оболочки столбцов матрицы. 13.4. Переход от второго способа задания линейных подпространств к 13.5. Вычисление ранга матрицы, зависящей от параметра...... 13.6. Решение задач с арифметическими векторами средствами системы 14.1. Кольцо квадратных матриц заданного размера......... 14.3. Элементарные матрицы и их связь с элементарными преобразованиями............................ 14.4. Обратимость элементарных матриц. Выражение с помощью элементарных матриц приводимости прямоугольной матрицы к скелетному виду........................ 14.5. Невырожденные матрицы. Первая теорема об условиях обратимости матрицы......................... 14.6. Алгоритм Жордана Гаусса вычисления обратной матрицы... § 15. Линейные операторы в арифметических линейных пространствах.............................. 15.1. Линейные отображения арифметических линейных пространств и 15.2. Матрица линейного оператора (относительно естественных базисов 15.3. Теорема об изоморфизме для алгебраической системы линейных операторов в арифметических линейных пространствах и алгебраической системы прямоугольных матриц............ 15.4. Законы для алгебраических действий над линейными операторами 15.5. Линейные операторы в одном пространстве. Обратимые линейные 15.6. Линейные эпиморфизмы и линейные мономорфизмы. Равносильность мономорфности и эпиморфности для эндоморфизмов... § 16. Перестановки и алгебраические действия над ними...... 16.3. Тождественная (единичная) перестановка........... 16.6. Область действия перестановки. Независимые перестановки... 16.8. Отображения левого (правого) сдвига и обращения на группе перестановок......................... § 17. Циклические перестановки. Разложение перестановки в произведение независимых циклов................ 18.4. Вычисление порядка перестановки с помощью ее разложения на § 21. Число инверсий в перестановке. Второй способ определения 21.2. Второй способ определения знака перестановки......... Глава 4. ТЕОРИЯ ОПРЕДЕЛИТЕЛЕЙ............... § 23. Определение определителя квадратной матрицы. Определитель треугольной матрицы. Определитель транспонированной § 24. Определитель квадратной матрицы как полилинейная и антисимметрическая функция ее столбцов (строк)........ 24.1. Функции от векторов-столбцов (векторов-строк) квадратной матрицы............................ 24.2. Полилинейность и антисимметричность функции A det(A).. 24.3. Следствия из свойств полилинейности и антисимметричности определителя.......................... 24.4. Метод Гаусса вычисления определителей............ § 25. Вычисление определителя с помощью разложения по столбцу 25.1. Алгебраические дополнения к элементам квадратной матрицы.. 25.2. Теорема Лапласа о вычислении определителя разложением по строке (столбцу)......................... 25.3. Еще одно свойство алгебраических дополнений......... 25.4. Индуктивный алгоритм вычисления определителя....... § 26. Описание всех полилинейных и антисимметрических функций от столбцов (строк) квадратной матрицы........... 26.1. Теорема о полилинейных и антисимметрических функциях от столбцов (строк) квадратной матрицы............... 26.2. Аксиоматический подход к определению определителя..... § 27. Определитель блочно-треугольной матрицы. Определитель 27.1. Определитель блочно-треугольной матрицы.......... 27.2. Мультипликативное свойство определителя........... § 28. Присоединенная матрица. Выражение обратной матрицы через присоединенную...................... 28.1. Определение и основное свойство присоединенной матрицы... 28.2. Неособые матрицы. Вторая теорема об условиях обратимости матрицы............................ 28.3. Алгоритм вычисления обратной матрицы с помощью присоединенной............................. § 29. Решение квадратных систем линейных уравнений с помощью обратной матрицы и по формулам Крамера......... 29.1. Решение квадратных с.л.у. с помощью обратной матрицы.... 29.2. Решение квадратных с.л.у. по формулам Крамера........ § 30. Минорный ранг матрицы. Вторая теорема о ранге матрицы. 30.4. Метод окаймляющих миноров для вычисления ранга матрицы.. 30a.2. Линейные однородные рекуррентности второго порядка.... 30a.4. Определители некоторых трехдиагональных матриц...... Глава 5. ПОЛЕ КОМПЛЕКСНЫХ ЧИСЕЛ............ 31.1. Интуитивное представление о комплексных числах. Квадратное уравнение с действительными коэффициентами (случай отрицательного дискриминанта)................... 31.2. Алгебраические действия над комплексными числами.

..... 31.3. Комплексные числа как двумерные действительные векторы... 31.5. Вычисления с комплексными числами в алгебраической форме. 32.1. Геометрическое представление комплексного числа. Модуль, аргумент и тригонометрическая форма комплексного числа..... 32.2. Умножение и деление комплексных чисел в тригонометрической 32.3. Извлечение корней из комплексных чисел в тригонометрической 33.2. Первообразные (примитивные) корни из единицы........ 33.3. Использование корней из единицы при вычислении корней из других комплексных чисел.................... § 34. Показательная функция комплексного аргумента. Показательная форма комплексного числа................ 34.1. Основные понятия математического анализа функций комплексного переменного....................... 34.2. Показательная функция (экспонента) комплексного переменного. 35.1. Корни многочленов (с комплексными коэффициентами)..... 35.2. Основная теорема алгебры (формулировка, идеи и этапы доказательства).......................... 35.3. Основная теорема алгебры (подробное доказательство)..... ГЛАВА 6. АЛГЕБРА МНОГОЧЛЕНОВ.............. § 36. Векторная модель кольца многочленов (над полем)..... 36.1. Алгебраическое определение многочлена над полем....... 36.2. Линейное пространство многочленов.............. 36.4. Группа обратимых элементов кольца многочленов....... 36.5. Отношение ассоциированности в коммутативном кольце. Ассоциированные (пропорциональные) многочлены. Нормализованные 36.6. Целостные коммутативные кольца. Целостность кольца многочленов............................. § 37. Деление с остатком и отношение делимости в кольце многочленов (над полем)...................... 37.1. Деление с остатком в кольце многочленов........... 37.2. Отношение делимости в целостном кольце. Делимость (нацело) § 38. Алгоритм Евклида отыскания наибольшего общего делителя 38.1. Понятие наибольшего общего делителя в целостном кольце. Условие Безу........................... 38.2. Существование НОД и алгоритм Евклида для его отыскания в 38.3. Существование НОД и алгоритм Евклида для его отыскания в 38.4. Отыскание линейного представления для НОД в кольце многочленов методом неопределенных коэффициентов.......... 38.5. Взаимно простые элементы в целостном кольце (с условием Безу) 38.7. Наименьшее общее кратное. Связь НОК и НОД........ § 39. Многочлены и полиномиальные функции. Корни многочленов. Теорема Безу....................... 39.1. Полиномиальные функции. Равенство многочленов и равенство 39.3. Оценка количества (различных) корней многочлена....... 39.4. Многочлены и полиномиальные функции над бесконечным полем § 40. Кратность корня. Оценка суммы кратностей корней. Алгебраически замкнутые поля. Разложимость многочленов на линейные множители. Теорема Виета.............. 40.1. Понятие кратности корня многочлена............. 40.2. Оценка суммы кратностей корней многочлена......... 40.4. Разложение многочлена над алгебраически замкнутым полем на 40.5. Вычисление корней многочленов и разложение многочленов на 41.1. Схема Горнера для вычисления значений многочленов..... 41.2. Разложение многочлена по степеням x c (формула Тейлора).. 41.3. Определение кратности корня многочлена с помощью схемы Горнера............................ § 42. Рациональные корни многочленов с рациональными коэффициентами............................ 42.1. Многочлены с рациональными коэффициентами и многочлены с 42.2. Рациональные корни многочлена с целыми коэффициентами... 42.3. Алгоритм отыскания всех рациональных корней для многочлена с § 43. Многочлены с действительными коэффициентами и их разложение на линейные и квадратичные множители....... 43.1. Сопряженные многочлены для многочленов с комплексными коэффициентами........................ 43.2. Комплексные корни для многочленов с действительными коэффициентами.......................... 43.3. Разложение многочлена с действительными коэффициентами на 43.4. Примеры разложения многочленов над полем действительных чисел............................. § 44. Неразложимые элементы в целостном кольце. Простые элементы. Неприводимые многочлены................ 44.1. Понятие неразложимого элемента в целостном кольце...... 44.2. Понятие простого элемента в целостном кольце......... 44.3. Канонические неразложимые (простые) элементы........ 44.4. Неприводимые многочлены.................. 44.5. Неприводимые многочлены над алгебраически замкнутыми полями и над полем действительных чисел............. § 45. Факториальные кольца. Факториальность кольца целых чисел (основная теорема арифметики) и факториальность кольца 45.1. Определение факториального кольца............. 45.2. Свойства факториальных колец................ 45.3. Достаточные условия факториальности кольца. Факториальность 45.5. Факториальность кольца многочленов над полем........ § 46. Факториальность кольца многочленов над факториальным кольцом. Неприводимые многочлены над полем Q и над кольцом Z............................. 46.1. Содержание многочлена над факториальным кольцом. Примитивные многочлены....................... 46.2. Неразложимые элементы в кольце многочленов над факториальным кольцом........................ 46.4. Поле частных целостного кольца............... 46.5. Сохранение неприводимости многочленов над факториальным кольцом при переходе к полю частных............... 46.6. Факториальность кольца многочленов над факториальным кольцом 46.7. Признак Эйзенштейна неприводимости многочлена над факториальным кольцом....................... § 47. Дифференцирование в кольце многочленов. Отделение кратных множителей........................ 47.1. Понятие характеристики поля................. 47.2. Понятие (формальной) производной от многочлена....... 47.3. Высшие производные и формула Тейлора для многочленов... 47.4. Кратность корня многочлена и значения производных...... 47.5. Уменьшение кратности неприводимого множителя многочлена при 47.6. Отделение кратных неприводимых множителей (кратных корней) § 48. Первоначальные понятия теории многочленов от нескольких 48.1. Мультииндексы и их лексикографическое упорядочение..... 48.2. Многочлены от нескольких переменных. Лексикографическое упорядочение одночленов.................... 48.3. Лемма о высшем члене произведения многочленов....... 48.4. Однородные многочлены (формы)............... 48.5. Композиция многочленов (подстановка многочленов в многочлен) 49.1. Определение симметрического многочлена........... 49.2. Лемма о высшем члене симметрического многочлена...... 49.3. Моногенные симметрические многочлены........... 49.4. Основная теорема о симметрических многочленах........ 49.5. Примеры выражения симметрических многочленов через элементарные симметрические.................... 49.6. Значения симметрических многочленов от корней многочлена.. 49.7. Дискриминант многочлена (от одной переменной)........ § 50. Ферро, Тарталья, Кардано, Феррари и другие........ 50.1. Уравнения малых степеней (над полем C)........... 50.2. Метод Ферро Тартальи Кардано решения уравнений третьей 50.3. Метод Феррари решения уравнений четвертой степени..... Приложение 1. Рисунки к главе 5.................. Список рекомендуемой литературы................. Перед вами учебное пособие по курсу алгебры, предназначенное для студентов-первокурсников математического факультета, обучающихся по направлению "Математика. Компьютерные науки" (бакалавриат). В этом пособии излагаются основы теории и даются указания к решению и образцы решения типовых задач по следующим темам (им соответствуют главы предлагаемого издания).

1. Системы линейных уравнений и алгебра матриц.

2. Арифметические линейные пространства.

3. Теория перестановок.

4. Теория определителей.

5. Поле комплексных чисел.

6. Алгебра многочленов.

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

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

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

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

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

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

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

В списке литературы мы указываем только одну (хорошую) книгу [6] по названным системам. Подобные издания выходят из печати во все возрастающем количестве, что свидетельствует о стремительном прогрессе в развитии компьютерной математики. Вы сможете следить за новинками, посещая в Интернете русскоязычный сайт www.exponenta.ru.

Несколько слов о стиле изложения, принятом в математических учебниках, пособиях и т. п. Как правило, эти тексты содержат "выделенные утверждения": теоремы, предложения, леммы.

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

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

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

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

Учебные книги (пособия, курсы лекций и т. п.) всегда содержат больше материала, чем ваши конспекты, поскольку в лекции не удается "втиснуть" все, что хотелось бы донести до слушателей. Так и в настоящем издании отдельные пункты (например, 15.6) отнюдь не являются обязательными для изучения на начальном, минимальном уровне. Но именно они кажутся автору наиболее полезными для заинтересованных, "въедливых" читателей.

Еще раз подчеркнем: данная книга не заменит стандартные руководства.

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

Например, в книгах [1 3, 5] вы найдете много материала, не относящегося напрямую к "чистой" алгебре, но очень ценного для понимания того, где и как применяется эта наука.

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

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

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

Впрочем, для первичного ознакомления с началами теории чисел вам достаточно (и необходимо!) заглянуть в учебник [2] (или в более раннее его издание [1]), где в первой, вводной главе вы найдете параграф, посвященный арифметике в кольце целых чисел.

Тем не менее несколько определений и простейших фактов из целочисленной арифметики мы приведем здесь.

Сводка информации из теории чисел 1. К о л ь ц о Z. Множество Z целых чисел с алгебраическими действиями сложения и умножения является коммутативным кольцом (см. определение кольца в п. 14.1).

Кольцо Z содержит подмножество N = Z+, состоящее из целых положительных (натуральных) чисел.

любого натурального числа m существуют однозначно определенные целые числа q (неполное частное) и r (остаток), такие, что делит число t Z (или же: t делится на s), если существует q Z такое, что Этот факт обозначается:

число. Два целых числа s и t называются сравнимыми по модулю m, если Факт сравнимости обозначается следующим образом:

Сравнимость целых чисел по модулю m равносильна их равноостаточности по модулю m, т. е. факту совпадения остатков от деления этих чисел на m.

общим делителем (двух или нескольких) целых чисел называется такое натуральное число, которое 1) является общим делителем, т. е. делит все данные числа;

2) делится на любой общий делитель данных чисел.

Для наибольшего общего делителя чисел a1,..., an Z используются обозначения НОД(a1,..., an ) или (a1,..., an ).

Числа a1,..., an называются взаимно простыми, если их наибольший общий делитель равен единице.

общим кратным чисел a1,..., an Z называется такое натуральное число, которое 1) является общим кратным, т. е. делится на все данные числа;

2) делит любое общее кратное данных чисел.

Используются обозначения НОК(a1,..., an ) или [a1,..., an ].

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

И АЛГЕБРА МАТРИЦ

§ 1. Системы линейных уравнений и их решения.

1.1. Развернутая запись системы линейных уравнений.

Одно линейное уравнение с одной неизвестной в множестве действительных чисел R имеет вид где a, b R и неизвестная x также ищется в множестве R.

Множеством решений уравнения (1.1) является следующее подмножество в R:

В развернутой записи система m линейных уравнений (с коэффициентами из поля R) с n неизвестными x1, x2,..., xn выглядит следующим образом:

где aij, bi, xj R; i = 1,..., m; j = 1,..., n.

Развернутая запись (1.2) может быть представлена в более компактной форме с помощью знака суммирования:

Решением системы линейных уравнений (с.л.у.) (1.2) называется набор чисел x0, x0,..., x0, при подстановке которых вместо соответn ствующих неизвестных в уравнения системы (1.2) эти уравнения обращаются в истинные равенства.

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

Общий вид матрицы размера m n таков:

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

Введем обозначение Mat(m, n; R) для множества всех (m n)матриц с элементами из множества R. Две матрицы считаются равными, если одинаковы их размеры и равны все соответствующие элементы.

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

Умножение двух матриц A · B считается возможным, если число столбцов матрицы A равняется числу строк матрицы B, и определяется следующим образом:

матрица-строка, а матрица-столбец ("высота" столбца B равна "длине" строки A), то их произведение полагается равным одноэлементной матрице 2) в общем случае, если A есть (m n)-матрица, B (n p)-матрица, то их произведение C = A · B будет (m p)-матрицей, элемент cik которой определяется как произведение i-й строки матрицы A на k-й столбец матрицы B:

Таким образом, Пример 1.1. Для матриц получим 22 Системы линейных уравнений и алгебра матриц Гл. Современные компьютерные математические системы (упомянутые в предисловии) давно уже "изучили" алгебру матриц. Например, система MATLAB (Матричная лаборатория) любую вводимую переменную считает по умолчанию матрицей и готова провести с ней какие угодно вычисления. Разумеется, и вам, чтобы квалифицированно общаться с такими программными средствами, необходимо как можно скорее освоить "матричную грамоту".

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

Арифметическим линейным пространством (размерности n) мы будем называть совокупность всех матриц-столбцов (арифметических векторов-столбцов) заданного размера n 1. Будет использоваться обозначение Замечание 1.1. Несколько слов о важнейшем в нашей науке термине "линейный". Если этот термин применяется к множеству (см.

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

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

Если он применяется к отображению, то такое отображение должно "переводить сумму в сумму" и также "сохранять" произведения на скаляр (подробности далее, см. п. 15.1).

1.4. Матричная запись для с.л.у. Множество решений с.л.у. Сопоставим с.л.у. (1.2) следующие матрицы:

1) матрицу коэффициентов, размера m n, вида (1.3);

2) матрицу-столбец (вектор), размера m 1, правых частей 3) матрицу-столбец (вектор), размера n1, составленный из неизвестных По правилу умножения матриц (1.6), матрицу A можно умножить на столбец x, при этом получится матрица-столбец размера m 1 :

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

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

24 Системы линейных уравнений и алгебра матриц Гл. Определение 1.1. Решением с.л.у. (1.10) называется такой вектор-столбец x0 Rn, при подстановке которого вместо неизвестного вектора x в (1.10) это уравнение обращается в истинное матричное равенство. Множество решений с.л.у. (1.10) определяется как подмножество в Rn, состоящее из всех решений (1.10):

Решить с.л.у. это значит найти множество L.

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

Определение 1.2. 1. С.л.у. (1.10) называется совместной, если она имеет хотя бы одно решение, т. е. если L =. В противном случае, т. е. если L =, с.л.у. называется несовместной.

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

Пример 1.2. Рассмотрим следующую систему из m = 3 линейных уравнений с n = 4 неизвестными:

Матричная запись этой системы будет иметь вид Проверьте (подставив вектор в матричное уравнение), что является частным решением данной системы (и таким образом, эта система совместна); проверьте еще один вектор и убедитесь, что он также удовлетворяет системе (и следовательно, данная система является неопределенной).

1.5. Однородные с.л.у.

Определение 1.3. С.л.у. (1.10) называется однородной, если вектор-столбец ее правых частей является нулевым: = Однородная с.л.у.

называется соответствующей с.л.у. (1.10).

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

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

2.1. Аксиомы поля. В множестве действительных чисел R заданы две основные алгебраические операции: сложение и умножение. Эти операции удовлетворяют следующим законам:

1 a, b, c [ (a + b) + c = a + (b + c) ] ассоциативность сложения;

2 a, b [ a + b = b + a ] коммутативность сложения;

3 0 a [ a + 0 = a ] существование нуля (единственность нуля выводима из 2, 3 );

4 a b [ a + b = 0 ] существование противоположного элемента (числа) [его единственность выводима из предыдущих законов;

однозначно определенный противоположный элемент обозначается b = a; затем определяется операция вычитания: c a = c + (a)];

5 a, b, c [ (a + b) · c = a · c + b · c ] дистрибутивность умножения относительно сложения;

6 a, b, c [ (a · b) · c = a · (b · c) ] ассоциативность умножения;

7 a, b [ a · b = b · a ] коммутативность умножения;

8 1 a [ a · 1 = a ] существование единицы (единственность единицы выводима из 7, 8 );

9 a = 0 b [ a · b = 1 ] существование обратного элемента (числа) [его единственность выводима из 6 8 ; однозначно определенный обратный элемент обозначается b = a1 ; затем определяется операция деления: c/a = c · a1 ].

Другие свойства операций сложения и умножения (например:

a · 0 = 0; (a b) · c = a · c b · c и т. п.) выводимы из основных Замечание 2.1. Студент-математик должен постепенно "дозреть" до осознания необходимости доказывать свойства алгебраических операций над числами (даже натуральными). Обычно это достигается на старших курсах, где изучается специальная математическая дисциплина "Числовые системы", в которой прослеживается развитие понятия числа, начиная с множества натуральных чисел, с последовательным построением множеств целых, рациональных, действительных чисел и т. д. Но уже в ближайшее время в курсе алгебры нам встретятся другие алгебраические системы, составленные не из чисел, а из каких-либо иных математических объектов и также наделенные алгебраическими операциями (типа сложения и умножения). Для этих операций встанет вопрос о выполнимости законов, аналогичных вышеприведенным законам для R.

Если в алгебраической системе выполняются все законы 1 и, кроме того, 1 = 0, то такая система называется полем. Сами эти законы именуются аксиомами поля.

Помимо поля R, вам уже знакомо поле рациональных чисел Q. А вот множество целых чисел Z полем не является. (Почему?) В этой книге до конца четвертой главы мы будем работать "над полем R";

рассматриваемые матрицы и векторы будут иметь действительные элементы. В пятой главе вводится в обращение поле C комплексных чисел. Однако поскольку все доказываемые результаты и все проводимые вычисления опираются лишь на аксиомы поля 1 9, то они остаются в силе "над любым полем P ". Если вы готовы к такому абстрагированию, то можете всюду в дальнейшем (мысленно) заменять букву R на букву P (где P произвольное поле). В частности, можно рассматривать арифметические линейные пространства P n, матрицы с элементами из поля P и т. д.

Условие 1 = 0 равносильно требованию наличия в поле как минимум двух различных элементов: нулевого и единичного. Существует поле, в котором, кроме этих элементов, никаких других больше нет.

Обозначается это поле F2, и арифметика в нем полностью задается определением 1 + 1 = 0.

(Внимание, компьютерщики! С этим, пока необычным для вас, полем вам предстоит активно работать в теории кодирования.) 2.2. Алгебраическая система матриц. Операция транспонирования. В множестве всех матриц с действительными элементами мы уже ввели три алгебраические операции: сложение матриц (1.4), умножение матрицы на скаляр (1.5) и умножение матриц (1.6).

Обратим внимание на то, что (в отличие от поля R) операции сложения и умножения матриц не всюду определены (т. е. применимы не к любым парам матриц), а также на то, что при умножении матрицы на скаляр сомножители не равноправны (принадлежат различным множествам).

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

Определение 2.1. Матрицей, транспонированной к (m n)-матрице A, называется (nm)-матрица (обозначаемая At ), которая получается из матрицы A превращением строк в столбцы (и наоборот) с сохранением их порядка или, иначе говоря, симметричным отражением матрицы относительно так называемой главной диагонали (составленной из элементов матрицы, для которых номер строки и номер столбца совпадают).

Формулой операцию транспонирования можно задать так:

Пример 2.1 иллюстрирует данное выше определение:

Замечание 2.2. Вектор-строку можно представить как транспонированный вектор-столбец:

Если нам понадобится различать арифметическое линейное пространство векторов-столбцов (1.7) и аналогичное пространство векторов-строк, то для последнего будет использоваться обозначение:

Rn = Mat(1, n; R) = {t = ( x1 x2... xn ); xi R, i = 1,..., n}. (2.3) 2.3. Законы для алгебраических операций над матрицами. Ниже будет сформулирована теорема с перечислением основных законов матричной алгебры. Обращайте внимание на указываемые под символами матриц размеры (числа m, n, p, q и т. д.), которые могут принимать произвольные натуральные значения; скалярные величины обозначаются греческими буквами (, µ и т. д.) и могут принимать произвольные действительные значения.

Теорема 2.1. В множестве всех матриц с элементами из поля R определены: 1) частичная алгебраическая операция (1.4) сложение матриц одинакового размера; 2) операция (1.5) умножение матриц на действительные числа; 3) частичная операция (1.6) умножение матриц согласованных размеров; 4) операция транспонирования матриц (2.1). Эти алгебраические операции удовлетворяют следующим законам:

Доказательство. 1. Прежде всего заметим, что первые восемь законов, (i) (viii), относящиеся к первым двум алгебраическим операциям (сложению матриц и умножению матрицы на число; напомним, что они называются линейными), фактически не требуют доказательства. Причиной этого является поэлементный характер линейных операций. Они производятся отдельно в каждой матричной позиции над располагающимися в этой позиции действительными числами, поэтому можно просто сослаться на аксиомы поля В частности, роль нулевого элемента (в каждом размере) играет, очевидно, матрица, составленная только из нулей, а чтобы найти матрицу, противоположную данной, надо поменять знаки перед всеми элементами данной матрицы. Заметим также, что неравноправность сомножителей при умножении матрицы на число приводит к необходимости отдельной формулировки двух дистрибутивных законов (v) и (vi).

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

Чтобы не вводить новые буквы для промежуточных результатов алгебраических действий, нам будет удобно применять символ извлечения элемента указанной позиции из матрицы; для (m n)матрицы (1.3) положим:

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

где i = 1,..., m; k = 1,..., p.

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

Докажем теперь закон (xi), словесно выражаемый следующим правилом: скалярные множители можно выносить как из первого, так и из второго сомножителя в произведении матриц.

Это правило в сочетании с двумя предыдущими дистрибутивными законами носит специальное название: свойство билинейности для произведения матриц. Само слово "билинейность" понимается как линейность по каждому из двух аргументов (сомножителей).

А линейность, скажем, по первому сомножителю означает (в соответствии с замечанием 1.1), что при фиксированном втором сомножителе B отображение A A·B "сохраняет" суммы и произведения на скаляр.

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

где i = 1,..., m; k = 1,..., p. Внимательный читатель, по-видимому, сам разберется в используемых законах и определениях. Поясним только четвертое равенство в цепочке. Здесь используется дистрибутивный закон в R в форме правила вынесения постоянного множителя из-под знака суммы:

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

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

3. Докажем теперь ассоциативность матричного умножения, т. е.

закон (xii). Ключевым звеном в цепочке преобразований будет перемена порядка суммирования в двойной сумме, которая произвоодится в соответствии со следующим "бухгалтерским" правилом перегруппировки слагаемых в сумме по двум индексам:

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

Понадобится также правило (2.5) и следующее за ним пояснение.

Как обычно, рассуждение начинается с того, что мы убеждаемся в совпадении размеров матриц в левой и правой частях (xii): матрица A · B имеет размеры m p, матрица B · C размеры n q, обе части равенства являются (m q)-матрицами. Проверяем совпадение соответствующих элементов (индексы i, j, k, l будут изменяться в пределах от 1 до m, n, p, q соответственно):

4. Докажем закон (xiii), указав единичные матрицы (обладающие свойствами единиц в матричной алгебре). Такими матрицами являются квадратные матрицы вида Элементы матрицы E имеют специальное обозначение и имя они образуют так называемый символ Кронекера:

где i, j = 1,..., n.

Снова ограничимся доказательством одного из двух равенств, входящих в (xiii). Размеры матриц слева и справа от знака равенства одинаковы; проверим равенство соответствующих элементов:

где i = 1,..., m; k = 1,..., n (поясним, что в сумме, выписанной выше, лишь одно из значений символа Кронекера отлично от нуля, вот почему от этой суммы осталось одно слагаемое).

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

Кстати, последние законы выражают факт линейности отображения транспонирования A At ; см. замечание 1.1.

Обратимся к проверке равенства (xvii). Обе части этого равенства являются матрицами размера pn; проверим равенство соответствующих элементов:

где i = 1,..., m; k = 1,..., p и в цепочке равенств использованы лишь определения умножения и транспонирования матриц, а также (на предпоследнем шаге) коммутативный закон для умножения в поле R (мы переставили числовые множители под знаком суммы).

Замечание 2.3. Как и в случае аксиом поля, основные законы алгебры матриц (i) (xvii) влекут множество других, например:

· O = O ; 0 · A = O (где во втором равенстве "два разных нуля":

0 число и O матрица) и т. п.

Замечание 2.4. Если рассматривать множество Mat(m, n, R) матриц фиксированного размера, то на нем (при m = n) будут определены лишь две операции (сложение и умножение на скаляр). В частности, так будет обстоять дело в случае арифметического линейного пространства Rn. Cовокупность законов, действующих в этой ситуации, сводится к законам (i) (viii).

Ассоциативность сложения обеспечивает корректность определения сумм более чем двух слагаемых, а вся совокупность законов (i) (viii) обеспечивает возможность образования так называемых линейных комбинаций матриц (векторов), т. е. сумм нескольких матриц (векторов) с числовыми коэффициентами вида Замечание 2.5. Остановимся на вопросе о выполнимости для матричного умножения коммутативного закона. Если матрица A имеет размеры m n, а матрица B размеры n p, то определено произведение A · B, в то время как произведение B · A будет определено лишь при дополнительном условии p = m, причем и в этом случае размеры матриц A·B и B ·A будут, вообще говоря, различными: первая из них будет квадратной (n n)-матрицей, а вторая квадратной (m m)-матрицей. И даже при дополнительном предположении m = n, т. е. при условии, что данные матрицы являются квадратными матрицами одинакового размера, коммутативность умножения не обязана иметь место. Попробуйте сами вычислить и сравнить два произведения A · B и B · A для следующих (2 2)-матриц:

Разумеется, для (1 1)-матриц (которые отождествляются с действительными числами) справедливы все аксиомы поля 1 9.

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

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

Прежде всего, в начале сессии упомянутый пакет надо "подгрузить":

Maple "расскажет" вам, что он "умеет": выведет имена доступных в используемом пакете команд, всего их порядка сотни; по поводу каждой из них можно будет использовать help.

Теперь введем матрицы (из примера 2.1):

Аргументом команды matrix служит массив, вводимый (в круглых скобках) как список списков. Подробнее: (двумерный) массив это список строк, каждая из которых сама является списком. Матрица это особый вид двумерного массива, в котором нумерация строк и столбцов начинается с 1; вместо круглых скобок Maple заключает матрицы и векторы в квадратные.

Вычислим линейную комбинацию матриц A и B:

36 Системы линейных уравнений и алгебра матриц Гл. Обратите внимание на важнейшую команду evalm (вычислить матрицу). Если A (ранее введенная) матрица, то простое присваивание лишь "резервирует имя"; по-настоящему матрица A1 заполняется, если дана команда:

А теперь перемножим матрицы A и C двумя способами (размеры матриц позволяют в данном случае вычислить как A ·C, так и C · A).

Здесь обратите внимание на особый знак некоммутативного умножения &.

Покажем еще операцию транспонирования:

3.1. Свойства решений однородных и неоднородных с.л.у.

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

Рассмотрим с.л.у. (1.10) и соответствующую однородную с.л.у.

(1.10h).

Предложение 3.1. 1. Сумма двух решений однородной системы (1.10h) снова является решением этой системы.

2. При умножении решения однородной системы на любой скаляр снова получается решение этой системы.

3. Сумма решения неоднородной системы (1.10) и решения соответствующей однородной системы (1.10h) является решением (1.10).

4. Разность двух решений системы (1.10) является решением соответствующей однородной системы (1.10h).

Доказательство. 1. Пусть векторы u и v являются решениями системы (1.10h), т. е. A · u = т. е. вектор u + v также является решением (1.10h).

2. Аналогично, если A · u = и R, то т. е. вектор · u является решением (1.10h).

3. Пусть вектор u является решением (1.10), а вектор v нием (1.10h), т. е. A · u = b т. е. вектор u + v является решением (1.10).

т. е. вектор u v является решением (1.10h).

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

В самом деле, если x0 и x (1.10), то их разность x x будет (см. п. 4 предложения 3.1) решением (1.10h), а значит (см. п. 2), при любом R вектор (1 x0 ) будет решением (1.10h). Так как x x = то все такие векторы попарно различны. Таким образом, однородная система уже имеет 38 Системы линейных уравнений и алгебра матриц Гл. бесконечно много решений. Но тогда (см. п. 3) и исходная неоднородная система будет иметь бесконечно много попарно различных решений вида Замечание 3.2. Сделаем (на будущее) оговорку: все сказанное в данном замечании существенно опирается на бесконечность нашего основного поля R. В дальнейшем студентам-компьютерщикам, которые будут изучать теорию кодирования, предстоит знакомство с конечными полями (см. замечание 2.1). В случае конечного поля коэффициентов утверждения замечания 3.1 потеряют силу, поскольку сами арифметические линейные пространства, а следовательно, и их подмножества будут конечными множествами.

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

3.2. Линейные подпространства пространства Rn. Рассмотрим арифметическое линейное пространство Rn.

Определение 3.1. Непустое подмножество V Rn называется линейным подпространством в Rn, если V устойчиво (или, как иначе выражаются, замкнуто) относительно линейных операций (сложения и умножения на скаляр), т. е. справедливы следующие два свойства:

Из определения линейного подпространства следует, что вместе с любым набором векторов оно должно содержать произвольную линейную комбинацию векторов, входящих в этот набор. Кроме того, очевидно, что всякое подпространство должно содержать нулевой вектор пространства Rn (в самом деле, взяв любой вектор a V, получим = 0 · a V ).

Подмножество O = { состоящее из одного нулевого вектора, является наименьшим из подпространств пространства Rn ; само это пространство является своим подпространством, причем наибольшим из всех подпространств.

§3 Свойства решений систем линейных уравнений Замечание 3.3. При изучении с.л.у. нам встретятся также "сдвинутые подпространства", т. е. подмножества в Rn следующего вида:

(Сумма подпространства V и вектора x0, стоящая в правой части равенства, определяющего M, понимается как подмножество в Rn, состоящее из всевозможных векторов вида y + x0, где вектор y пробегает все V.) При x0 V оказывается, что V + x0 = V. (Докажите!) А при x V подмножество M линейным подпространством уже не является. (Почему?) У математиков для "сдвинутых подпространств" имеется особый термин аффинные подпространства. Так называются подмножества в R, содержащие вместе с любыми двумя векторами x0 и x произвольную их аффинную комбинацию (1 ) + (ср. с замеx x чанием 3.1).

3.3. Подмножества решений однородных и неоднородных с.л.у. Вернемся к с.л.у. (1.10) и (1.10h).

Предложение 3.2. 1. Подмножество L0 решений однородной системы (1.10h) является линейным подпространством в Rn.

2. Подмножество L решений совместной неоднородной системы (1.10) имеет вид где x произвольное решение системы (1.10).

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

2. Равенство (3.3) это равенство множеств. Всякое равенство множеств M1 = M2 равносильно одновременному выполнению двух включений: M1 M2 и M2 M1.

Каждое из включений можно проверять "на элементах", доказывая утверждения: (x M1 ) (x M2 ) и (x M2 ) (x M1 ).

40 Системы линейных уравнений и алгебра матриц Гл. Так мы и поступим при доказательстве (3.3).

Пусть вектор x принадлежит левой части (3.3), т. е. является решением (1.10). Пусть x0 еще одно (произвольное) решение этой системы. [Заметьте, что именно в этом месте доказательства используется непустота L, т. е. совместность системы (1.10).] Тогда, в силу п. 4 предложения 3.1, разность x x0 будет решением (1.10h), т. е.

правой части (3.3).

Пусть теперь x принадлежит правой части (3.3), т. е. представляется в виде x = y + x0, где y подпространству L. Тогда, в силу п. 3 предложения 3.1, вектор x принадлежит L, т. е. левой части (3.3).

Равенство (3.3) доказано.

Замечание 3.4. Вспоминая о понятиях частных и общего решений с.л.у. (см. замечание 1.1), мы можем трактовать подпространство L (или формулу, описывающую это подпространство) как общее решение однородной системы (1.10h) (о.р.о.), а сдвинутое подпространство L (или формулу, его описывающую) как общее решение неоднородной системы (1.10) (о.р.н.); вектор x0 трактуется как некоторое частное решение неоднородной системы (ч.р.н.).

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

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

Замечание 3.5. В случае определенности системы (1.10) множество ее решений состоит из единственного вектора: L = {0 }. Из формулы (3.3) немедленно следует в этом случае (см. п. 1.5), что однородная система (1.10h) будет иметь лишь тривиальное решение, т. е. подпространство L0 будет состоять из одного нулевого вектора.

§ 4. Равносильные системы линейных уравнений.

Элементарные преобразования.

4.1. Равносильные с.л.у. Рассмотрим две с.л.у. (с одним и тем же неизвестным вектором x):

Пусть L и L подмножества их решений (оба они содержатся в арифметическом линейном пространстве Rn ).

Определение 4.1. Говорят, что с.л.у. (4.2) является следствием с.л.у. (4.1), если всякое решение (4.1) является также решением (4.2), т. е. если L L. Две с.л.у. (4.1) и (4.2) называются равносильными (или эквивалентными), если каждая из них является следствием другой, т. е. если эти системы имеют одинаковые множества решений: L = L.

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

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

4.2. Элементарные преобразования с.л.у. Рассмотрим следующие четыре типа преобразований над с.л.у. вида (4.1).

I. Перестановка двух уравнений системы. Символически это действие выражаться записью: iур k ур, где i, k номера уравнений, i = k.

II. Прибавление к одному из уравнений системы другого уравнения, домноженного на некоторое число. Символическое выражение:

iур + k ур · c. При этом действии к уравнению с номером i (почленно) прибавляется уравнение с номером k (где i = k), домноженное (почленно) на число c, остальные же уравнения (в том числе и уравнение с номером k) остаются неизменными.

42 Системы линейных уравнений и алгебра матриц Гл. III. Почленное домножение одного из уравнений системы на ненулевое число. Символически: iур · c, где c R, c = 0.

IV. Удаление из системы (включение в систему) тривиального уравнения, все коэффициенты которого, а также его правая часть равны нулю.

Определение 4.2. Описанные выше преобразования называются элементарными преобразованиями типов I IV над с.л.у.

Предложение 4.1. Под действием элементарных преобразований с.л.у. переходит в равносильную с.л.у.

Доказательство. Характерной особенностью преобразований I IV типов является их обратимость. В самом деле, преобразование типа I является "самообратным", т. е. его повторное применение возвращает систему к исходному виду. Обратимость преобразования типа IV заложена в самом его определении. Преобразованием, обратным к преобразованию типа II, является преобразование (такого же типа) iур + k ур · (c). Аналогично, обратным к III будет преобразование типа III: iур · c1.

Далее заметим, что всякий арифметический вектор x, являющийся решением исходной системы, останется решением и для преобразованной системы. В самом деле, вектор x обращает все уравнения системы в истинные равенства, а преобразования типов I III, будучи произведены над истинными равенствами, снова приводят, очевидно, к истинным равенствам. Что касается преобразования типа IV, то оно удаляет из системы (добавляет к системе) "уравнение" вида 0·x1 +· · ·+0·xn = 0, которое является "абсолютным тождеством" (т. е. справедливо для любых значений неизвестных) и поэтому "содержит нуль информации": его исключение (добавление) никак не отражается на множестве решений с.л.у.

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

4.3. Расширенная матрица с.л.у. Матричное выражение элементарных преобразований над с.л.у. Производить элементарные преобразования над с.л.у. (4.2) удобнее используя вспомогательную матрицу B размера m (n + 1), получающуюся слиянием матрицы коэффициентов (1.3) и столбца правых частей (1.8).

Определение 4.3. Матрица называется расширенной матрицей с.л.у. (4.1).

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

преобразование типа II, например, будет выражаться записью:

iстр + k стр · c и т. п.

Далее мы убедимся, что при практическом решении с.л.у. часто бывает удобным переставлять неизвестные. Поэтому, чтобы "не потерять" истинные имена неизвестных, нам придется приписывать их над столбцами матрицы A. Матрица (4.3) будет в этом случае выглядеть следующим образом:

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

Замечание 4.1. Ясно, что однородная с.л.у. под действием элементарных преобразований снова переходит в однородную с.л.у. Поэтому для "слежения" за преобразованиями не нужна расширенная матрица системы B: достаточно преобразовывать матрицу A.

4.4. Идея метода Жордана Гаусса (на примере). Сейчас мы вернемся к с.л.у. из примера 1.2, выпишем для нее расширенную матрицу системы, подвергнем эту матрицу элементарным преобразованиям и приведем ее сначала к так называемому ступенчатому виду, а затем к виду Жордана Гаусса. Восстановим по полученной матрице с.л.у. (она, в силу предложения 4.1, будет равносильна исходной с.л.у.) и решим вновь полученную систему.

Пример 4.1. Решим следующую систему из трех линейных уравнений с четырьмя неизвестными.

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

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

Запишем с.л.у., отвечающую полученной матрице:

Эту систему уже можно решать "снизу вверх", выражая главные неизвестные (в данном случае это x1 и x3 ) через свободные неизвестные (x2 и x4 ):

и т. д.

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

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

Выразим из этой системы главные неизвестные через свободные.

Кроме того, поскольку (по определению 1.1) решение с.л.у. представляет собой вектор-столбец, включающий выражения для всех неизвестных, учтем в записи решения свободные неизвестные, включая в ответ "тавтологические" равенства x2 = x2 ; x4 = x4.

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

Обозначив три вектора-столбца в правой части последнего равенства f2, f4 и x0, получим краткую запись ответа:

При любых конкретных значениях свободных неизвестных (фигурирующих в качестве скалярных множителей перед векторами f2 и f4 ) мы получаем конкретное частное решение с.л.у. Таким образом, эта система (как мы уже знаем из примера 1.2) является неопределенной. Из всего (бесконечного) множества L решений с.л.у. можно выделить одно особое, которое получается, если положить равными нулю все свободные неизвестные: x2 = x4 = 0. Это решение x = x принято называть опорным (оно также уже встречалось нам в примере 1.2).

Проясним теперь смысл векторов-столбцов f2 и f4. Представьте себе, что в правых частях исходной системы стоят нули, т. е. с.л.у.

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

если положить x2 = 1, а x4 = 0, то останется x = f2, при противоположном выборе значений свободных неизвестных получится x = f4.

Таким образом, векторы, стоящие при свободных неизвестных в общем решении исходной системы, являются решениями соответствующей однородной системы. То, почему эти решения заслуживают названия базисных, будет строго объяснено в § 10. Пока вы можете заметить, что всякое решение однородной системы является линейной комбинацией (см. замечание 2.4) базисных решений. Еще раз возвратившись к примеру 1.2, заметьте, что указанное там решение x1 получается из найденного выше общего решения при x2 = 0, При решении практических примеров настоятельно рекомендуется делать проверку: опорное решение следует проверять, подставляя во все уравнения исходной системы, а каждое из базисных решений подставляя во все уравнения соответствующей однородной системы.

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

А пока задумаемся над тем, как в ходе применения алгоритма Жордана Гаусса мы можем обнаружить, что исходная система является несовместной. Представьте себе, что в системе, рассмотренной в примере 4.1, в правой части третьего уравнения, вместо числа 1 стоит, скажем, число 5. Тогда в момент достижения ступенчатого вида (т. е. на втором шаге преобразований матрицы B) мы вместо последней нулевой строки получили бы строку с четырьмя нулями и с числом 6 в последнем столбце (это число было бы последней ступенькой в ступенчатом виде матрицы B). Такая строка соответствовала бы противоречивому уравнению 0·x1 +0·x2 +0·x3 +0·x4 = 6, что свидетельствовало бы о несовместности исходной с.л.у.

И в общем случае (см. § 6) с.л.у. будет несовместной, если последняя ступенька в ступенчатом виде расширенной матрицы этой системы будет приходиться на последний столбец.

Для совместной с.л.у. возможны две ситуации:

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

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

48 Системы линейных уравнений и алгебра матриц Гл. Замечание 4.3. Говоря о выборе главных (свободных) неизвестных, необходимо отметить, что такой выбор далеко не однозначен.

Так, в разобранном примере в качестве главных могли бы фигурировать неизвестные x1, x4 или x2, x3, но не x1, x2. (При изучении следующих глав вы должны будете разобраться в причинах этого явления, а также понять, почему, несмотря на неоднозначность в определении ступенчатого вида для данной матрицы, "количество ступенек" в ступенчатом виде определено однозначно; см. понятие ранга матрицы.) И еще: может быть, это покажется вам непривычным, но некоторые неизвестные могут в системе вообще отсутствовать. Такие неизвестные неизбежно попадают в разряд свободных: если о них ничего не говорится ("нуль информации"), то их значения совершенно произвольны.

Например, система из одного уравнения будучи рассмотрена в пространстве R4, дает такой результат: неизвестные x1, x4 свободны в силу невхождения в уравнение; в качестве еще одной свободной неизвестной можно (по произволу) выбрать либо x2, либо x3. Если выбрано x2, то ответ будет таким:

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

Замечание 4.5. Немного информации о решении с.л.у. в системе Maple.

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

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

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

Разумеется, мы не имеем здесь возможности углубляться в подробности синтаксиса системы Maple, однако надеемся, что будущие компьютерщики сами прочитают нужные "help’ы" или изучат руководства.

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

Можно, например, "слить" матрицу A и вектор b, составив расширенную матрицу системы B = (A|b) с помощью команды Решение системы A · x = b находится с помощью команды Поясним, что означают два последних (необязательных) аргумента функции linsolve. Третий аргумент ’r’ резервирует имя для переменной "ранг матрицы A" (количество ступенек в ступенчатом виде этой матрицы). По дополнительному запросу значение ранга выводится:

Четвертый аргумент определяет обозначения для свободных неизвестных. Судя по ответу, свободными являются неизвестные x1 и x4. Maple обозначил их (предписанной) буквой t и занумеровал посвоему. (По умолчанию свободные неизвестные обозначаются именно буквой t, но с "системным префиксом": t1, t2.) Решение, выведенное системой в строчку, можно при желании конвертировать в столбец:

Можно попросить Maple проверить результат:

Подсчитанная "невязка" оказалась нулевым вектором, значит решение найдено верно. Может понадобиться не сразу получить ответ, а остановиться на этапе достижения вида Жордана Гаусса. Тогда применяем к расширенной матрице B команду gaussjord:

Именно такой вид Жордана Гаусса у нас получился при решении вручную; свободными неизвестными здесь будут x2 и x4. Можно догадаться, что алгоритм, реализующий команду linsolve, не столь "прямолинеен" (поскольку приводит к другому, равносильному ответу).

5.1. Матрицы ступенчатого вида, вида Жордана Гаусса, модифицированного вида Жордана Гаусса, скелетного вида Определение 5.1. 1. Матрицу A Mat(m, n; R) будем называть матрицей ступенчатого вида, если где символы обозначают ненулевые элементы (именуемые ключевыми), обозначают произвольные элементы, а на пустых местах подразумеваются нули.

2. Будем говорить, что ступенчатая матрица (5.1) имеет вид Жордана Гаусса (Ж. Г.), если все ключевые элементы равны единице и нули в ключевых столбцах стоят не только ниже, но и выше ключевых элементов, т. е. если матрица имеет вид 3. Если все ключевые столбцы матрицы (5.2) сгруппированы в начале этой матрицы, т. е.

то будем говорить, что матрица A имеет модифицированный вид Жордана Гаусса.

4. Если в матрице (5.3), кроме нескольких единиц, расположенных в начале главной диагонали, нет других ненулевых элементов, т. е.

то говорят, что матрица A имеет скелетный вид.

Замечание 5.1. Модифицированный вид Ж. Г. и скелетный вид матрицы могут быть описаны с помощью так называемых блочных матриц. Простейшим вариантом блочной матрицы является матрица, разбитая на четыре прямоугольных блока следующим образом:

Обозначив буквой r количество ступенек в матрице (5.3), мы можем представить эту матрицу в блочном виде:

где E единичная матрица (см. п. 2.3), H произвольная матрица.

Скелетная матрица (5.4) имеет блочное представление 5.2. Теорема Жордана – Гаусса для матриц. В этом пункте будет сформулирована и доказана основная теорема метода Ж.

Г. для матриц. В § 4 были определены элементарные преобразования для с.л.у. и соответствующие элементарные преобразования над строками расширенных матриц этих систем. Однако при изучении элементарных преобразований для матриц (безотносительно к системам линейных уравнений) принято рассматривать преобразования, 54 Системы линейных уравнений и алгебра матриц Гл. сохраняющие размеры матриц, т. е. преобразования типа IV исключаются из рассмотрения. С другой стороны, при изучении "матриц вообще" строки и столбцы совершенно равноправны, поэтому наряду с элементарными преобразованиями (типов I III) над строками следует рассматривать аналогичные преобразования над столбцами матриц. (Ниже, в § 6, мы снова вернемся к матрицам, происходящим из с.л.у., и докажем соответствующую теорему, учитывающую специфику таких матриц.) Теорема 5.1. Рассмотрим произвольную матрицу A с действительными элементами.

1. С помощью элементарных преобразований типов I II над строками матрица A может быть приведена к ступенчатому виду.

2. Если дополнительно разрешить элементарные преобразования типа III (над строками), то матрицу можно привести к виду Жордана Гаусса.

3. Если дополнительно разрешить элементарные преобразования типа I над столбцами, то матрицу можно привести к модифицированному виду Жордана Гаусса.

4. Если дополнительно разрешить элементарные преобразования типа II над столбцами, то матрицу можно привести к скелетному виду.

Доказательство. 1. Пусть дана (m n)-матрица (1.3). Если A = O, то нечего доказывать: нулевую матрицу можно рассматривать как ступенчатую (с числом ступенек, равным нулю). Если матрица ненулевая, то будем просматривать столбцы этой матрицы, начиная с первого, до тех пор, пока нам не встретится ненулевой столбец. Этот столбец мы примем за первый ключевой. С помощью перестановки строк (т. е. элементарных преобразований типа I) добьемся того, чтобы верхний элемент ключевого столбца стал ненулевым, и примем этот элемент за первый ключевой элемент. Допустим, он равен a.

С помощью элементарных преобразований типа II (над строками) сделаем нули под ключевым элементом. Если, скажем, в i-й строке под ключевым элементом стоит число c, то оно "обнуляется" преобc разованием iстр + 1стр · ( a ).

После завершения этого этапа мы получим:

Обозначим A блок полученной матрицы, расположенный справаснизу от ключевого элемента. Повторим описанный выше шаг алгоритма применительно к строкам, начиная со второй, т. е. фактически применительно к матрице A (поскольку очевидно, что при преобразованиях над этими строками ранее полученные нули "не портятся"). Далее работа алгоритма продолжается и следует оговорить условия "останова". Алгоритм заканчивает работу, если либо достигнута последняя строка матрицы (и тогда получается ступенчатый вид (5.1) для A с числом ступенек r, равным числу строк m);

либо на некотором шаге (с номером r) достигнут последний столбец матрицы (и тогда, после обнуления элементов ниже последнего ключевого, строки, начиная с (r + 1)-й, окажутся нулевыми);

либо после получения r-го ключевого элемента снизу-справа от него образуется нулевая подматрица (и тогда получается ступенчатый вид (5.1) с числом ступенек r < m ).

2. Получив ступенчатый вид (5.1), мы продолжим вычисления с применением элементарных преобразований над строками типа III.

Можно сначала превратить все ключевые элементы в единицы. Если, скажем, в i-й строке ключевым является элемент a, то, применяя преобразование iстр · a, мы сделаем этот элемент единичным. Далее, если в столбце над i-й ключевой единицей (в строке с номером k) находится ненулевой элемент c, то мы его можем обнулить с помощью преобразования типа II: k стр + iстр · (c). Так мы придем к виду Ж. Г. (5.2).

3. Если разрешается переставлять столбцы матрицы, то мы можем все ключевые столбцы матрицы (5.2) собрать в начале матрицы и получить модифицированный вид Ж. Г. (5.3). При этом в левом верхнем углу матрицы сформируется единичная подматрица (блок) E размера r r [см. (5.3a)], где r количество ступенек.

4. Если разрешены элементарные преобразования над столбцами типа II, то мы можем обнулить оставшиеся ненулевыми столбцы (в зоне блока H). Скажем, j-й столбец матрицы (5.3), "пересекающий" блок H обнуляется одним "комбинированным" действием Таким образом мы получим скелетный вид (5.4).

Замечание 5.2. К ступенчатому виду матрицы можной прийти "разными путями" (с помощью различных последовательностей элементарных преобразований). И сам этот вид определен не однозначно. В последствии, однако, в п. 11.4, будет установлено, что "количество ступенек" r инвариантно (не зависит от способа приведения матрицы к ступенчатому виду). Это количество будет важнейшей числовой характеристикой матрицы и получит имя ранг матрицы.

Скелетный вид матрицы, поскольку он полностью определяется числом r, также будет инвариантным.

6.1. Теорема Жордана Гаусса для с.л.у. В этом пункте мы применим результаты теоремы 5.1 к матрице, являющейся расширенной матрицей с.л.у. Данный случай имеет следующие особенности:

1) элементарные преобразования типов I III, безусловно, можно производить лишь над строками матрицы;

2) над столбцами (кроме последнего, состоящего из правых частей уравнений) можно производить лишь преобразования типа I, причем для того чтобы не забыть, какой неизвестной отвечает тот или иной столбец, приходится ставить над столбцами метки (знаки неизвестных); последний столбец никуда переставлять нельзя;

3) преобразования над столбцами типов II III в этой ситуции применять нельзя, поскольку они "смешивают" неизвестные;

4) можно использовать преобразования над строками типа IV, выбрасывая нулевые строки.

Теорема 6.1. Пусть B расширенная матрица (4.3), соответствующая с.л.у. (1.10); B = (A | ) r количество ступенек в матрице A. Тогда в матрице B ступенек либо столько же, либо на одну больше.

1. Если количество ступенек для B равно r + 1, то последняя ступенька приходится на последний, (n + 1)-й столбец B и с.л.у.

(1.10) несовместна.

2. Если количество ступенек для B равно r, то с.л.у. (1.10) совместна и возможны следующие два случая.

2а. Если количество ступенек r равняется числу неизвестных n, то с.л.у. (1.10) является определенной. Приводя в этом случае матрицу B к виду Ж. Г. (и вычеркивая нулевые строки), мы получим матрицу последний столбец которой определяет единственное решение системы (1.10): x0 =.

2б. Если r < n, то с.л.у. (1.10) является неопределенной и ее общее решение содержит n r свободных неизвестных, принимающих произвольные значения. Для отыскания общего решения приведем матрицу B к модифицированному виду Ж. Г. (и вычеркнем нулевые строки), получим матрицу вида В качестве свободных неизвестных можно выбрать неизвестные, приходящиеся на зону матрицы H. Если предположить, что порядок неизвестных в ходе преобразований не был изменен, то в качестве свободных неизвестных будут фигурировать а общее решение системы (1.10) будет иметь следующую структуру:

58 Системы линейных уравнений и алгебра матриц Гл. где вектор x0 является частным решением системы (1.10), которое получается, если положить все свободные неизвестные равными нулю, а векторы fj (j = r+1, r+2,..., n) являются частными решениями однородной системы (1.10h), отвечающей данной системе (1.10), причем вектор fj получается, если положить xj = 1, а остальные свободные неизвестные приравнять нулю.

Доказательство. Может быть, у читателей сложилось впечатление, что сформулированная выше теорема чрезвычайно сложная и что вообще таких теорем "не бывает". Действительно, математики обычно стремятся к лаконичным формулировкам. И теорему 6.1 тоже можно было бы сформулировать гораздо короче, указав только условия, когда существует хотя бы одно решение и когда ровно одно. Мы же, ориентируясь на практические вычисления, предпочли в каждом из случаев указать явный способ отыскания и структуру решения. К тому же при таком подходе доказательство будет не намного длиннее формулировки.

Итак, в соответствии с теоремой 5.1, матрицу B можно с помощью элементарных преобразований типов I II над строками привести к ступенчатому виду B. Если последняя, (r + 1)-я ступенька в B (с ключевым элементом a = 0) приходится на последний столбец, то (r + 1)-я строка этой матрицы будет соответствовать уравнению 0 · x1 + · · · + 0 · xn = a, что будет свидетельствовать о несовместности с.л.у., отвечающей матрице B, а значит, и исходная система несовместна.

В противном случае число ступенек в матрицах A и B одинаково (и равно r).

Если r = n, то ступеньки в A идут подряд по главной диагонали, а все строки матрицы B, начиная с (n + 1)-й (если они есть), являются нулевыми и их можно вычеркнуть. Продолжая преобразования до достижения вида Ж. Г., мы приведем эту матрицу к виду (6.1). Теперь нам остается "считать" из последнего столбца ответ единственное решение с.л.у. (1.10).

Если r < n, то ступеньки в матрице B не будут идти все подряд и неизвестные разделятся на два класса: главные (те, которые приходятся на ключевые столбцы) и свободные (все остальные). Нумерация неизвестных есть фактор не слишком важный, и, хотя в практических примерах это будет не всегда так, ничто не мешает нам при теоретическом анализе считать, что главными являются первые r неизвестных. (Мы их занумеровали мы и перенумеровать можем!) Удаляя нулевые строки в матрице, представляющей собой вид Ж. Г. для матрицы B, мы получим матрицу B вида (6.2). Запишем систему, соответствующую этой матрице:

Решим полученную систему относительно главных неизвестных и добавим к ответу тавтологические уравнения xj = xj для каждой свободной неизвестной. (Эти тавтологии выражают тот факт, что свободные неизвестные совершенно произольны.) Будем иметь:

x1 = h1(r+1) xr+1 h1(r+2) xr+2.... h1n xn +1 ;

x2 = h2(r+1) xr+1 h2(r+2) xr+2.... h2n xn +2 ;

xr = hr(r+1) xr+1 hr(r+2) xr+2.... hrn xn +r ;

или, в векторной форме:

x = xr+ Обозначая n r + 1 векторов в правой части последнего равенства символами fr+1, fr+2,..., fn, x0, получим формулу (6.3).

Проанализируем смысл введенных векторов. Если приравнять нулю все свободные неизвестные, то в ответе останется только последний вектор x0. Следовательно, этот вектор представляет собой частное решение неоднородной системы. (В примерах § 4 этому вектору уже присвоено было наименование опорное ч.р.н.) 60 Системы линейных уравнений и алгебра матриц Гл. Далее, как уже отмечалось в замечании 4.1, если бы данная система была однородной, то она осталась бы таковой и под действием элементарных преобразований. Для однородной с.л.у. мы получили бы x0 = и следовательно, первые n r слагаемых в (6.3) дают не что иное, как общее решение для однородной системы (1.10h), соответствующей исходной неоднородной системе (1.10).

Каждое слагаемое в о.р.о.

разъясняется следующим образом: если в (6.3h) положить одну из свободных неизвестных xj = 1, а все остальные приравнять нулю, то в правой части останется только вектор fj. Таким образом, векторы fj (j = r+1,..., n) являются частными решениями (1.10h). (Ранее, в примерах, они тоже получили специальное наименование базисные ч.р.о.) Этим и завершается доказательство теоремы.

Здесь читателю можно посоветовать еще раз просмотреть "опередивший теорию" пример 4.1 и последующие замечания. Изложенная в § 4 идея метода Ж. Г. получила в теореме 6.2 детальное обоснование. Кроме того, получило подтверждение и дополнительное уточнение правило (3.6): в качестве ч.р.н. в этой формуле может быть выбрано опорное частное решение неоднородной системы, а о.р.о.

может быть расписано как линейная комбинация базисных ч.р.о.

6.2. Случай однородной с.л.у.

Предложение 6.1. Однородная с.л.у. (1.10h) имеет ненулевое решение тогда и только тогда, когда количество ступенек в ступенчатом виде матрицы A меньше числа неизвестных n. В частности, если число уравнений m < n, то однородная система имеет ненулевое решение.

Доказательство. Первое утверждение немедленно следует из теоремы 6.1, а второе из того факта, что количество ступенек r не превосходит количества уравнений m.

Заметьте, что у нас уже есть формула (6.3h) для общего решения системы (1.10h). А только что доказанное (практически тривиальное) предложение 6.1 выделено особо, т. к. в последующих главах на него придется неоднократно ссылаться.

6.3. Случай квадратной с.л.у. Альтернатива Фредгольма Определение 6.1. С.л.у. (1.10) называется квадратной, если является квадратной матрица A, т. е. если число уравнений m равняется числу неизвестных n.

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

Предложение 6.2. Для квадратной с.л.у. (1.10) и соответствующей однородной с.л.у. (1.10h) выполняется одно (и только одно) из следующих утверждений:

1) либо система (1.10h) имеет только нулевое решение, и тогда система (1.10) является определенной при любой правой части b;

2) либо (1.10h) имеет нетривиальное решение, и тогда, в зависимости от система (1.10) может быть либо несовместной, либо неопределенной.

Доказательство. Пусть система (1.10h) имеет только нулевое решение. Тогда, по предложению 6.1, число ступенек r в ступенчатом виде A матрицы A равняется числу неизвестных n. А поскольку система предполагается квадратной (m = n), то эти ступеньки идут подряд и имеются в каждой строке матрицы A. При переходе к расширенной матрице (4.3), отвечающей неоднородной с.л.у. (1.10), мы замечаем, что вне зависимости от правой части дополнительная ступенька в последнем столбце появиться не может (на нее просто "не хватит строк"). Значит, по теореме 6.1, система (1.10) будет совместной и определенной.

Если же система (1.10h) имеет ненулевое решение, то, по предложению 6.1, r < n. В силу теоремы 6.1, система (1.10) будет неопределенной, если окажется совместной. Но она может оказаться и несовместной, ибо для последней, (r + 1)-й ступеньки в последнем столбце теперь "есть место" и она может появиться.

62 Системы линейных уравнений и алгебра матриц Гл. § 7. Некоторые типовые задачи:

системы линейных уравнений с параметром, линейные матричные уравнения 7.1. С.л.у. с параметром. Рассмотрим с.л.у. вида (1.10), но в которой матрица A и вектор зависят от некоторого параметра (дейb ствительного числа) :

Задача с параметром это всегда "исследовательская" задача.

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

Пример 7.1. Решим при всех значениях параметра с.л.у.