Гашков С.В. Современная элементарная алгебра в задачах и решениях

§ 4.13. Системы уравнений

Системы уравнений, встречавшиеся ранее, были в основном симметрическими. Алгоритм их решения был изложен в § 3.10 о симметрических многочленах.

Заметим, однако, что не следует торопится сводить систему к теореме Виета, как рекомендовано в этом параграфе. Иногда проще угадать решение, а потом доказать, что других решений нет.

Упражнение 130. Решите систему

x + y + z + w = 10;x2 + y2 + z2 + w2 = 30;

x3 + y3 + z3 + w3 = 100;

xyzw = 24.

После того как вы угадали одно решение, можно получить и остальные решения, выполнив все 24 перестановки его компонент. Отсутствие других решений вытекает, например, из теоремы Безу о том, что система алгебраических уравнений имеет число решений, не большее произведения степеней ее уравнений, если, конечно, она не является неопределенной и имеющей поэтому бесконечно много решений. Но доказательство этой теоремы сложно, и мы не будем его приводить. Поэтому лучше представим, что мы свели все-таки систему к системе Виета, и заметим, что система Виета n-го порядка имеет не более n! решений, причем имеет ровно n! решений, если соответствующее уравнение не имеет кратных корней. Впрочем, система может не иметь решений, если не все корни уравнения принадлежат рассматриваемому полю.

При решении несимметричных систем часто применяют разнообразные искусственные приемы, например, итерации, как в § 3.7.

Упражнение 131. Решите систему из § 3.7

y = x2 − 1;

z = y2 − 1;x = z2 − 1.

Используют идеи, заимствованные из комплексных чисел, как в § 4.3. Упражнение 132. Решите систему из § 4.3

Применяют неравенства, как в следующей системе.

Упражнение 133. Решите систему

(

x2002 + y2002 = 1;

x2 + y2 = 1.

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

Упражнение 134. Решите систему

(

xyz = 8;

x2 + y2 + z2 = 12.

Иногда помогает разложение на множители.

Упражнение 135. Решите систему

(

2x2 + 3xy − 2y2 − 6x + 3y = 0; 3x2 + 7xy + 2y2 − 7x + y − 6 = 0.

Но наиболее распространенные приемы – это всевозможные замены переменных. Например, этот прием хорошо работает для симметрических систем.

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

Упражнение 136. Решите систему

(

x4 + kx3y − 6x2y2 − kxy3 + y4 = 0; x2 + y2 = 1.

Наличие в системе параметра не должно вас смущать – от него ответ зависеть не будет, хотя в общем случае зависит, и еще как.

Самый простой, но в тоже время и самый важный класс систем уравнений – это системы первой степени, или линейные системы. Большая

часть систем уравнений, которые приходится решать во внематематических приложениях, как раз и составляют линейные системы. Их теория разработана лучше всего и лежит в основе важного раздела алгебры – так называемой линейной алгебры. Изучение элементов линейной алгебры периодически включалось в курсы алгебры в ФМШ МГУ, но в последнее время это делалось очень редко, в основном по причине нежелания дублировать университетский курс. Мы здесь поэтому ограничимся только начальными сведениями о линейных системах.

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

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

Во втором случае получается уравнение с несколькими неизвестными. В этом случае говорят, что система неопределенная, так как она имеет бесконечно много решений. Чтобы их все найти, надо принять все неизвестные из последнего уравнения, кроме одного, за параметры и выразить через них (в виде линейной комбинации) все оставшиеся неизвестные. Если число параметров равно k, то говорят, что система имеет k-мерное

пространство решений.

В третьем случае получается не уравнение, а просто неверное равенство, которое означает, что система не имеет решения (система несов-

местна).

Решать линейные системы научились давно, но этот метод по традиции связывают с именем Гаусса.

Упражнение 137. Решите систему Ямвлиха **

x + y = 2(z + u);

x + z = 3(y + u);x + u = 4(y + z).

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

** Ямвлих – древнегреческий математик, философ и мистик, написавший книгу об Элевсинских мистериях.

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

ине всегда удобен при теоретических исследованиях.

Влинейной алгебре выработаны специальные удобные способы работы с линейными системами. Произвольная система представляется в виде

a1,1x1 + . . . + a1, x = b1;

n n

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

am,1x1 + . . . + am,nxn = bm,

где неизвестные и коэффициенты обозначаются с помощью индексов. Таблица размера n × m, составленная из коэффициентов системы,

!

a1,1 . . . a1,n

. . . . . . . . . . . . . , am,1 . . . am,n

называется матрицей системы.

Метод Гаусса можно переформулировать в терминах элементарных преобразований. Элементарным преобразованием системы называется замена одного из ее уравнений на сумму этого уравнения с другим уравнением системы, умноженным на произвольное число.

Упражнение 138. Докажите, что после элементарного преобразования системы она остается равносильной исходной.

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

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

Удобно еще отнести к числу элементарных преобразований перестановки строк и перестановки столбцов матрицы (им соответствуют перестановки уравнений и переменных в системе).

Упражнение 139. Решите систему

x + y + z + u = 1;

y z v u

+ + + = 5;

x + u + v + z = 2;

x + u + v + y = 4;

v + x + z + y = 8.

Элементарные преобразования можно применять не только к линейным системам. Можно для произвольных систем в определении элементарных преобразований разрешить умножение не на константу, а на произвольное выражение.

Упражнение 140. Решите систему

(

x − y = x2y2;

y3 + x4y + y4x = 0.

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

Система с квадратной матрицей называется треугольной, если в ее матрице m × m все элементы ai,j , i > j, расположенные ниже диагонали,

равны нулю, но a1,1 . . . am,m =6 0.

Система называется трапециевидной, если в ее матрице a1,1 . . . ak,k 6= 6= 0, в строках (k + 1)-й и ниже (если они есть) стоят только нули и ниже диагонали – тоже нули.

Упражнение 141. Если система треугольная, то она имеет единственное решение, которое можно найти за n(n − 1) операций.

Упражнение 142. Если система трапециевидная, то она либо не имеет решений, если нулевой строке матрицы системы соответствует ненулевой коэффициент в правой части соответствующего уравнения, либо в противном случае имеет (n − k)-мерное пространство решений.

Упражнение 143. Сложность алгоритма Гаусса оценивается сверху как Cn3.

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

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

Каждое из уравнений системы второго порядка

(

a1,1x1 + a1,2x2 = b1; a2,1x1 + a2,2x2 = b2

можно представить как прямую линию на плоскости с уравнением

i = 1, 2.

a1,1x1 + a1,2x2 = b1; a2,1x1 + a2,2x2 = b2

нетрудно вывести и явные формулы для решений, именно

если a1,1a2,2 − a2,1a1,2 6= 0. Подобные формулы уже для систем третьего порядка громоздки, а далее становятся просто необозримыми. Поэтому

Лейбниц ввел понятие определителя квадратной матрицы n × n.

Определение 102. Определителем (или детерминантом) матрицы A размера n × n с элементами ai,j называется сумма всех n! произведений вида a1,π (1) . . . an,π (n) , каждое из которых соответствует одной из n! различных перестановок π и берется со знаком ε(π), равным знаку этой перестановки. Сокращенно определитель матрицы обозначается det(A), а иногда и просто |A|.

Формулы Крамера для решения системы уравнений с матрицей A и столбцом свободных членов b, которые мы не будем доказывать, имеют вид

x= det(Ai) , i det(A)

из чисел b1, . . . , bn.

Но чтобы читатель получил все же некоторое представление о теории определителей, предлагаем ему несколько упражнений.

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

Упражнение 145. Напишите явные формулы определителей второго и третьего порядков. Докажите формулы для решения линейных систем второго и третьего порядков.

Упражнение 146. Определитель треугольной матрицы равен произведению диагональных элементов. Определитель трапециевидной матрицы равен нулю.

Упражнение 147. Непосредственное вычисление определителя n-го порядка требует n · n! − 1 умножений и сложений-вычитаний.

Поэтому явную формулу используют для вычислений только при n 6 3 и иногда при n = 4. А вычисляют определители методом Гаусса, преобразовывая матрицу к треугольной (или трапециевидной).

Упражнение 148. Докажите, что определитель n-го порядка можно вычислить за Cn3 арифметических операций в поле, над которым рассматривается матрица.

Формулы Крамера имеют поэтому только теоретическое значение, и при n > 3 для решения систем используется метод Гаусса без предварительного вычисления определителей.

268 Глава IV. Алгебраические уравнения

Определитель можно геометрически интерпретировать как ориентированный объем параллелепипеда, натянутого на ее столбцы (или строки). Мы поясним это утверждение только в двумерном случае. При n = 2

тянутого на вектора (a1,1a1,2), (a2,1a2,2), которая берется со знаком плюс, если первый вектор переходит во второй при повороте против часовой

стрелки.

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

Хотя в основном линейная алгебра была создана в XIX в., ее развитие продолжается и сейчас. Например, немецкий математик Штрассен в 1967 году предложил алгоритм для решения линейных систем n-го порядка и соответствующих определителей со сложностью Cnlog2 7. Этот результат вызвал сенсацию, но, к сожалению, алгоритм Штрассена начинает превосходить алгоритм Гаусса только для матриц порядка нескольких сотен. В дальнейшем оценка Штрассена усилиями его самого и других математиков неоднократно улучшалась и доведена сейчас до оценки Cnτ , где τ < 2,35, однако гипотеза Штрассена о том, что можно получить оценку, в которой τ → 2, еще не доказана, а полученные новые алгоритмы превосходят алгоритм Штрассена только для матриц колоссальных размеров и не имеют практического значения.

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

Упражнение 149. Решите систему yz = 6;

xz = 7.

x1x2 = 1;

= 1;

x2x3

Упражнение 150. Решите систему . . . . . . . . . . .

xn−1xn = 1;

xnx1 = 1.

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

Упражнение 151. Решите систему

x2 = a + (y − z)2;

y2 = b + (z − x)2;z2 = c + (y − x)2.

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

(

f(x, y) = 0; g(x, y) = 0.

Будем рассматривать f(x, y) и g(x, y) как многочлены F(x), G(x), коэффициенты которых являются многочленами от y, переменную y можно рассматривать как параметр. Тогда задача решения системы равносильна задаче нахождения значений параметра, при которых многочлены F(x), G(x) имеют общие корни.

Критерием наличия общих корней у двух многочленов является обращение в нуль их результанта.

i=1 j=1

где y1, . . . , ym – корни многочлена g с учетом кратности.

Из полученных формул сразу следует нужное нам свойство результанта: res (f, g) = 0 f и g имеют общий корень. Но пользы от него никакой, если не уметь вычислять результант, не зная корней многочленов. Оказывается это сделать можно, и многими разными способами.

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

симметрическим многочленом от переменных xi с коэффициентами, зависящими от yj , значит, согласно теореме о симметрических многочленах и теореме Виета, он является многочленом от коэффициентов ai и от корней yj , причем тоже симметрическим относительно этих корней, поэтому он аналогично может быть выражен не через корни yj , а через коэффициенты bj (вместе с коэффициентами ai).

Упражнение 153. Найдите результант

res (x2 + p1x + q1, x2 + p2x + q2).

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

Выражая res (F, G) через коэффициенты ai , bj многочленов F(x), G(x), получаем многочлен от y. Его степень можно оценить сверху как произведение степеней многочленов f(x, y), g(x, y). Находя его корни и подставляя их в оба уравнения системы, получаем два многочлена с общими корнями, которые можно найти, вычисляя вначале их НОД алгоритмом Евклида. Отсюда можно вывести теорему Безу для случая двух неизвестных.

Упражнение 154. Докажите теорему Безу для систем из двух уравнений с двумя неизвестными, а именно, что такая система либо неопределена и имеет бесконечно много решений, либо имеет не более четырех решений.

Но решать системы из двух уравнений с двумя неизвестными лучше следующим приемом. Применяя подходящее элементарное преобразование, устраняем x2 из одного из уравнений, и после этого, выражая x через y и подставляя во второе уравнение, получаем уравнение относительно x не выше четвертой степени.

Задачи и упражнения к § 4.13