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

83

Системы линейных уравнений

Системой m линейных уравнений с n неизвестными называется система вида

где a_ij и b_i (i=1,…,m; b=1,…,n) - некоторые известные числа, а x₁,…,x_n - неизвестные. В обозначении коэффициентов a_ij первый индекс iобозначает номер уравнения, а второй j - номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы

,

которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b₁,…,b_m называются свободными членами.

Совокупность n чисел c₁,…,c_n называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c₁,…,c_n вместо соответствующих неизвестных x₁,…,x_n.

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

1. Система может иметь единственное решение.

2. Система может иметь бесконечное множество решений.

3. Например, решением этой системы является любая пара чисел, отличающихся знаком.

4. И третий случай, когда система вообще не имеет решения.

Например, если бы решение существовало, то x₁ + x₂ равнялось бы одновременно нулю и единице.

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

Рассмотрим способы нахождения решений системы.

Матричный метод решения систем линейных уравнений

Матрицы дают возможность кратко записать систему линейных уравнений. Пусть дана система из 3-х уравнений с тремя неизвестными:

Рассмотрим матрицу системы и матрицы столбцы неизвестных и

свободных членов

Найдем произведение

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

или короче A•X=B.

Здесь матрицы A и B известны, а матрица X неизвестна. Её и нужно найти, т.к. её элементы являются решением данной системы. Это уравнение называют матричным уравнением.

Пусть определитель матрицы отличен от нуля |A| ? 0. Тогда матричное уравнение решается следующим образом. Умножим обе части уравнения слева на матрицу A^-1, обратную матрице A: . Поскольку A^-1A = E и E•X = X, то получаем решение матричного уравнения в виде X = A^-1B.

Заметим, что поскольку обратную матрицу можно найти только для квадратных матриц, то матричным методом можно решать только те системы, в которых число уравнений совпадает с числом неизвестных. Однако, матричная запись системы возможна и в случае, когда число уравнений не равно числу неизвестных, тогда матрица A не будет квадратной и поэтому нельзя найти решение системы в виде X = A^-1B.

Примеры. Решить системы уравнений.

1.

Найдем матрицу обратную матрице A.

,

Таким образом, x = 3, y = - 1.

2.

Итак, х₁=4,х₂=3,х₃=5.

3. Решите матричное уравнение: XA+B=C, где

Выразим искомую матрицу X из заданного уравнения.

Найдем матрицу А^-1.

Проверка:

4. Решите матричное уравнение AX+B=C, где

Из уравнения получаем

.

Следовательно,

Правило Крамера

Рассмотрим систему 3-х линейных уравнений с тремя неизвестными:

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

называется определителем системы.

Составим ещё три определителя следующим образом: заменим в определителе D последовательно 1, 2 и 3 столбцы столбцом свободных членов

Тогда можно доказать следующий результат.

Теорема (правило Крамера). Если определитель системы Д ? 0, то рассматриваемая система имеет одно и только одно решение, причём

Доказательство. Итак, рассмотрим систему 3-х уравнений с тремя неизвестными. Умножим 1-ое уравнение системы на алгебраическое дополнение A₁₁ элемента a₁₁, 2-ое уравнение - на A₂₁ и 3-е - на A₃₁:

Сложим эти уравнения:

Рассмотрим каждую из скобок и правую часть этого уравнения. По теореме о разложении определителя по элементам 1-го столбца

.

Далее рассмотрим коэффициенты при x₂:

Аналогично можно показать, что и

.

Наконец несложно заметить, что

Таким образом, получаем равенство:

.

Следовательно,

.

Аналогично выводятся равенства и , откуда и следует утверждение теоремы.

Таким образом, заметим, что если определитель системы Д ? 0, то система имеет единственное решение и обратно. Если же определитель системы равен нулю, то система либо имеет бесконечное множество решений, либо не имеет решений, т.е. несовместна.

Примеры. Решить систему уравнений

Итак, х=1, у=2, z=3.

1. Решите систему уравнений при различных значениях параметра p:

Система имеет единственное решение, если Д ? 0.

. Поэтому .

1. При

2. При p = 30 получаем систему уравнений

3. которая не имеет решений.

4. При p = -30 система принимает вид

5. и, следовательно, имеет бесконечное множество решений x=y, yОR.

Метод Гаусса

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

Вновь рассмотрим систему из трёх уравнений с тремя неизвестными:

.

Первое уравнение оставим без изменения, а из 2-го и 3-го исключим слагаемые, содержащие x₁. Для этого второе уравнение разделим на а₂₁ и умножим на -а₁₁, а затем сложим с 1-ым уравнением. Аналогично третье уравнение разделим на а₃₁ и умножим на -а₁₁, а затем сложим с первым. В результате исходная система примет вид:

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

Отсюда из последнего уравнения легко найти x₃, затем из 2-го уравнения x₂ и, наконец, из 1-го - x₁.

При использовании метода Гаусса уравнения при необходимости можно менять местами.

Часто вместо того, чтобы писать новую систему уравнений, ограничиваются тем, что выписывают расширенную матрицу системы:

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

К элементарным преобразованиям матрицы относятся следующие преобразования:

1. перестановка строк или столбцов;

2. умножение строки на число, отличное от нуля;

3. прибавление к одной строке другие строки.

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

1. Вернувшись к системе уравнений, будем иметь

1. Выпишем расширенную матрицу системы и сведем ее к треугольному виду.

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

1. Разделим вторую строку матрицы на 2 и поменяем местами первый и третий столбики. Тогда первый столбец будет соответствовать коэффициентам при неизвестной z, а третий - при x.

Вернемся к системе уравнений.

Из третьего уравнения выразим одну неизвестную через другую и подставим в первое.

Таким образом, система имеет бесконечное множество решений.

Матрицы и определители

Определение. Матрицей размера mn, где m- число строк, n- число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа называются элементами матрицы. Место каждого элемента однозначно определяется номером строки и столбца, на пересечении которых он находится. Элементы матрицы обозначаются a_ij, где i- номер строки, а j- номер столбца.

А =

Основные действия над матрицами.

Матрица может состоять как из одной строки, так и из одного столбца. Вообще говоря, матрица может состоять даже из одного элемента.

Определение. Если число столбцов матрицы равно числу строк (m=n), то матрица называется квадратной.

Определение. Матрица вида:

= E,

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

Определение. Если a_mn = a_nm , то матрица называется симметрической.

Пример. - симметрическая матрица

Определение. Квадратная матрица вида называется диагональной матрицей.

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

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

c_ij = a_ij b_ij

С = А + В = В + А.

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

(А+В) =А В

А() = А А

Пример. Даны матрицы А =; B =, найти 2А + В.

2А = , 2А + В = .

Операция умножения матриц

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

AB = C;

.

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

Свойства операции умножения матриц

1)Умножение матриц не коммутативно, т.е. АВ ВА даже если определены оба произведения. Однако, если для каких - либо матриц соотношение АВ=ВА выполняется, то такие матрицы называются перестановочными.

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

Перестановочными могут быть только квадратные матрицы одного и того же порядка.

АЕ = ЕА = А

Очевидно, что для любых матриц выполняются следующее свойство:

AO = O; OA = O,

где О - нулевая матрица.

2) Операция перемножения матриц ассоциативна, т.е. если определены произведения АВ и (АВ)С, то определены ВС и А(ВС), и выполняется равенство:

(АВ)С=А(ВС).

3) Операция умножения матриц дистрибутивна по отношению к сложению, т.е. если имеют смысл выражения А(В+С) и (А+В)С, то соответственно:

А(В + С) = АВ + АС

(А + В)С = АС + ВС.

4) Если произведение АВ определено, то для любого числа верно соотношение:

(AB) = (A)B = A(B).

5) Если определено произведение АВ , то определено произведение В^ТА^Т и выполняется равенство:

(АВ)^Т = В^ТА^Т, где

индексом Т обозначается транспонированная матрица.

6) Заметим также, что для любых квадратных матриц

det (AB) = detAdetB.

Что такое det будет рассмотрено ниже.

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

А = ; В = А^Т=;

другими словами, b_ji = a_ij.

В качестве следствия из предыдущего свойства (5) можно записать, что:

(ABC)^T = C^TB^TA^T,

при условии, что определено произведение матриц АВС.

Пример. Даны матрицы А = , В = , С = и число = 2. Найти А^ТВ+С.

A^T = ; A^TB = = = ;

C = ; А^ТВ+С = + = .

Пример. Найти произведение матриц

А = и В = .

АВ = = .

ВА = = 21 + 44 + 13 = 2 + 16 + 3 = 21.

Пример. Найти произведение матриц А=, В =

АВ = = = .

Определители (детерминанты)

Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле:

det A = , где (1)

М_1к - детерминант матрицы, полученной из исходной вычеркиванием первой строки и k - го столбца. Следует обратить внимание на то, что определители имеют только квадратные матрицы, т.е. матрицы, у которых число строк равно числу столбцов.

Формула (1) позволяет вычислить определитель матрицы по первой строке, также справедлива формула вычисления определителя по первому столбцу:

det A = (2)

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

detA = , i = 1,2,…,n. (3)

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

Определитель единичной матрицы равен 1.

Для указанной матрицы А число М_1к называется дополнительным минором элемента матрицы a_1k. Таким образом, можно заключить, что каждый элемент матрицы имеет свой дополнительный минор. Дополнительные миноры существуют только в квадратных матрицах.

Определение. Дополнительный минор произвольного элемента квадратной матрицы a_ij равен определителю матрицы, полученной из исходной вычеркиванием i-ой строки и j-го столбца.

Свойство1. Важным свойством определителей является следующее соотношение:

det A = det A^T;

Свойство 2

det ( A B) = det A det B.

Свойство 3

det (AB) = detAdetB

Свойство 4. Если в квадратной матрице поменять местами какие-либо две строки (или столбца), то определитель матрицы изменит знак, не изменившись по абсолютной величине.

Свойство 5. При умножении столбца (или строки) матрицы на число ее определитель умножается на это число.

Свойство 6. Если в матрице А строки или столбцы линейно зависимы, то ее определитель равен нулю.

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

Свойство 7. Если матрица содержит нулевой столбец или нулевую строку, то ее определитель равен нулю. (Данное утверждение очевидно, т.к. считать определитель можно именно по нулевой строке или столбцу.)

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

Свойство 9. Если для элементов какой- либо строки или столбца матрицы верно соотношение:

d = d₁ d₂ , e = e₁ e₂ , f = f₁ f₂ , то верно:

Пример. Вычислить определитель матрицы А =

= -5 + 18 + 6 = 19.

Пример:. Даны матрицы А = , В = . Найти det (AB).

1-й способ: det A = 4 - 6 = -2; det B = 15 - 2 = 13; det (AB) = det A det B = -26.

2- й способ: AB = , det (AB) = 718 - 819 = 126 -

- 152 = -26.

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

Определение. Элементарными преобразованиями матрицы назовем следующие преобразования:

1) умножение строки на число, отличное от нуля;

2) прибавление к одной строке другой строки;

3) перестановка строк;

4) вычеркивание (удаление) одной из одинаковых строк (столбцов);

5) транспонирование;

Те же операции, применяемые для столбцов, также называются элементарными преобразованиями.

С помощью элементарных преобразований можно к какой-либо строке или столбцу прибавить линейную комбинацию остальных строк ( столбцов ).

Миноры

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

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

Заметим, что вышесказанное применимо не только к квадратным матрицам, но и к прямоугольным.

Если вычеркнуть из исходной квадратной матрицы А выделенные строки и столбцы, то определитель полученной матрицы будет являться дополнительным минором.

Алгебраические дополнения

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

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

Теорема Лапласа. Если выбрано s строк матрицы с номерами i₁, … ,i_s, то определитель этой матрицы равен сумме произведений всех миноров, расположенных в выбранных строках на их алгебраические дополнения.

Обратная матрица

Определим операцию деления матриц как операцию, обратную умножению.

Определение. Если существуют квадратные матрицы Х и А, удовлетворяющие условию:

XA = AX = E,

где Е - единичная матрица того же самого порядка, то матрица Х называется обратной к матрице А и обозначается А^-1.

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

Рассмотрим общий подход к нахождению обратной матрицы.

Исходя из определения произведения матриц, можно записать:

AX = E , i=(1,n), j=(1,n),

e_ij = 0, i j,

e_ij = 1, i = j .

Таким образом, получаем систему уравнений:

,

Решив эту систему, находим элементы матрицы Х.

Пример. Дана матрица А = , найти А^-1.

Таким образом, А^-1=.

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

,

где М_ji- дополнительный минор элемента а_ji матрицы А.

Пример. Дана матрица А = , найти А^-1.

det A = 4 - 6 = -2.

M₁₁=4; M₁₂= 3; M₂₁= 2; M₂₂=1

x₁₁= -2; x₁₂= 1; x₂₁= 3/2; x₂₂= -1/2

Таким образом, А^-1=.

Cвойства обратных матриц.

Укажем следующие свойства обратных матриц:

(A^-1)^-1 = A;

2) (AB)^-1 = B^-1A^-1

3) (A^T)^-1 = (A^-1)^T.

При использовании компьютерной версии “Курса высшей математики” возможно запустить программу, которая находит обратную матрицу и подробно описывает весь ход решения для матрицы размера 3х3.

Для запуска программы дважды щелкните на значке

В открывшемся окне программы введите элементы матрицы по строкам и нажмите Enter.

Примечание: Для запуска программы необходимо чтобы на компьютере была установлена программа Maple ( Waterloo Maple Inc.) любой версии, начиная с MapleV Release 4.

Пример. Дана матрица А = , найти А³.

А² = АА = = ; A³ = = .

Отметим, что матрицы и являются перестановочными.

Пример. Вычислить определитель .

= -1

= -1(6 - 4) - 1(9 - 1) + 2(12 - 2) = -2 - 8 + 20 = 10.

= = 2(0 - 2) - 1(0 - 6) = 2.

= = 2(-4) - 3(-6) = -8 + 18 = 10.

Значение определителя: -10 + 6 - 40 = -44.

Базисный минор матрицы

Ранг матрицы.

Как было сказано выше, минором матрицы порядка s называется определитель матрицы, образованной из элементов исходной матрицы, находящихся на пересечении каких - либо выбранных s строк и s столбцов.

Определение. В матрице порядка mn минор порядка r называется базисным, если он не равен нулю, а все миноры порядка r+1 и выше равны нулю, или не существуют вовсе, т.е. r совпадает с меньшим из чисел m или n.

Столбцы и строки матрицы, на которых стоит базисный минор, также называются базисными.

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

Определение. Порядок базисного минора матрицы называется рангом матрицы и обозначается Rg А.

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

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

Надо отметить, что равные матрицы и эвивалентные матрицы - понятия совершенно различные.

Теорема. Наибольшее число линейно независимых столбцов в матрице равно числу линейно независимых строк.

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

Пример. Определить ранг матрицы.

, RgA = 2.

Пример: Определить ранг матрицы.

, Rg = 2.

Пример. Определить ранг матрицы.

, Rg = 2.

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

Элементы матричного анализа

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

Направленным отрезком называется упорядоченная пара (A,B) точек плоскости (пространства), у которой A называется началом, B -- концом. Направленные отрезки (A,B) и (C,D) назовём эквивалентными, если или если и. Знак обозначает сонаправленность: если лучи и либо лежат на одной прямой и дают в пересечении луч, либо лежат на параллельных прямых в одной полуплоскости относительно прямой . Классы эквивалентности по указанному отношению называются векторами.

Векторное пространство (линейное пространство) - множество элементов, называемых векторами, для которых определены операции сложения и умножения на число. Простейший, но важный пример - совокупность векторов a, b, c, ... обычного 3-мерного пространства. Каждый такой вектор - направленный отрезок, задаваемый тремя числами: ; числа называются координатами вектора. При умножении вектора на вещественное число соответствующий отрезок, сохраняя направление, растягивается в раз: . Сумма двух векторов находится по правилу параллелограмма; если и то . Паре векторов a и b сопоставляют также скалярное произведение (см. Векторная алгебра). Непосредственным обобщением З-мерного пространства является n-мерное евклидово пространство. Его элементы - упорядоченные наборы вещественных чисел, Например, , . Сложение и умножение векторов на число определены формулами , , а скалярное произведение - формулой Примером комплексного бесконечномерного векторного пространства может служить совокупность комплексных функций f, заданных на всей оси и квадратично суммируемых (то есть имеющих конечный интеграл ). Многие классы функций, например, полиномы заданного порядка, функции непрерывные, дифференцируемые, интегрируемые, аналитические и тому подобные, также образуют бесконечномерные векторные пространства.

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

1. любой паре элементов х и у из L сопоставлен единственный элемент z, называемый их суммой z=x+y и принадлежащий L;

2. для любого числа и любого элемента x из L определен элемент z, который называется их произведением и принадлежащий L;

3. операции сложения и умножения на число являются ассоциативными и дистрибутивными.

Сложение допускает обратную операцию, то есть для любых х и у из L существует единственный элемент w из L такой, что x+w=y. Кроме того, имеют место формулы . Если все числа вещественны (комплексны), говорят о вещественном (комплексном) векторном пространстве; множество чисел называют полем скаляров L. Понятие векторного пространства можно ввести и для произвольного поля, например, поля кватернионов.

Если - элементы векторного пространства L, то выражение вида называется их линейной комбинацией; совокупность всех линейных комбинаций элементов подмножества S из L называют линейной оболочкой S. Векторы из L называют линейно независимыми, если условие ( - любые элементы поля скаляров) может выполняться только при . Бесконечная система векторов называется линейно независимой, если любая ее конечная часть является линейно независимой. Множество элементов подмножества S из L называется системой образующих S, если любой вектор х из S можно представить в виде линейной комбинации этих элементов. Линейно независимая система образующих S называется базисом S, если разложение любого элемента S по этой системе единственно. Базис, элементы которого каким-либо образом параметризованы, называется системой координат в S. Базис векторного пространства всегда существует, хотя и не определяется однозначно. Если базис состоит из конечного числа n элементов, то векторное пространство называется n-мерным (конечномерным); если базис - бесконечное множество, то векторное пространство называется бесконечномерным. Выделяют также счетномерные векторные пространства, у которых имеется счетный базис.

Подмножества векторного пространства L, замкнутые относительно его операций, называются подпространствами L. По любому подпространству S можно построить новое векторное пространство L/S, называемое фактор-пространством L по S: каждый его элемент есть множество векторов из L, различающихся между собой на элемент из S. Размерность L/S называется коразмерностью подпространства S в L; если размерности L и S равны соответственно n и k, то коразмерность S в L равна n-k. Если J - произвольное множество индексов i и S_i - семейство подпространств L, то совокупность всех векторов, принадлежащих каждому из S_i, есть подпространство, называется пересечением указанных подпространств и обозначаемое . Для конечного семейства подпространств S₁, ..., S_s совокупность всех векторов, представимых в виде

, x_i из S_i,

есть подпространство, называемое суммой S₁, ..., S_s и обозначаемое S₁+ ... +S_s. Если для любого элемента суммы S₁+ ... +S_s представление в виде (*) единственно, эта сумма называется прямой и обозначается . Сумма подпространств является прямой тогда и только тогда, когда пересечение этих подпространств состоит только из нулевого вектора. Размерность суммы подпространств равна сумме размерностей этих подпространств минус размерность их пересечения. Векторное пространство L₁ и L₂ называют изоморфным и, если существует взаимно однозначное соответствие между их элементами, согласованное с операциями в них; L₁ и L₂ изоморфны тогда и только тогда, когда они имеют одинаковую размерность.

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

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

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

Система векторов, которая не является линейно зависимой, называется линейно независимой.

Справедливо следующее утверждение.

Система векторов линейного пространства линейно независима тогда и только тогда, когда из равенства следует равенство нулю всех коэффициентов .

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

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

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

Это означает, что все  -мерные линейные пространства “устроены” одинаково -- как пространство векторов-столбцов из действительных чисел, т.е. что все они изоморфны пространству .

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

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

Например, доказано, что система векторов   из  

, ,...,

образует базис в тогда и только тогда, когда отличен от нуля определитель матрицы, со столбцами :

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

Пусть и -- два базиса в . Матрицей перехода от базиса к базису называется матрица , столбцами которой являются координаты векторов в базисе :

...	...

    ,

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

Основные определения и задачи линейного программирования.

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

Определение 1. 2. Функция (1) называется целевой функцией (или линейной формой) задачи (1)-(4), а условия (2)-(4) - ограничениями данной задачи.

Определение 1. 3. Стандартной ( или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k=m и l=n.

Определение 1. 4. Основной ( или канонической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1. 1) при выполнении условий (3) и (4), где k=0 и l=n.

Определение 1. 5. Совокупность чисел X=(x₁, x₂, ..., x_n) , удовлетворяющих ограничениям задачи (2)-(4), называется допустимым решением задачи (или планом).

Определение 1. 6. План X=(x₁^*, x₂^*, ..., x_n^*), при котором целевая функция задачи принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции при плане X будем обозначать через F(X). Следовательно, X* - оптимальный план задачи, если для любого X выполняется неравенство F(X)<=F(X^*) (соответственно F(X)>=F(X^*))

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

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

1. В том случае, когда требуется найти минимум функции F=c₁x₁ + c₂x₂ + +. . . + c_nx_n , можно перейти к нахождению максимума функции F₁=F=c₁x₁ + c₂x₂ +. . . + c_nx_n, поскольку функция F принимает минимальное значение в той же точке, в которой функция F₁ принимает максимальное значение.

2. Ограничение-неравенство исходной задачи линейного программирования, имеющие вид “<=“, можно преобразовать в ограничения-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида ”>=” - в ограничение равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение неравенство

a_i1x₁+a_i2x₂+…+a_inx_n<=b_i

преобразуется в ограничение-равенство

a_i1x₁+a_i2x₂+…+a_inx_n+x_n+1=b_i

а ограничение-неравенство

a_i1x₁+a_i2x₂+…+a_inx_n>=b_i

преобразуется в ограничение-равенство

a_i1x₁+a_i2x₂+…+a_inx_n-x_n+1=b_i

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

3. Если переменная xk не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными uk и vk, приняв xk=uk-vk.

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

Перепишем эту задачу в векторной форме: найти максимум функции

F=c₁x₁ + c₂x₂ + +. . . + c_nx_n

при условиях

x₁P₁+x₂P₂+. . . +x_nP_n=P₀,

x_j>=0 (j=1,n),

где P₁, . . . , P_n и P₀ - m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

Определение 1. 7. План X=(x₁, x₂, . . . , x_n) называется опорным планом основной задачи линейного программирования, если положительные коэффициенты (x_j>0) стоят при линейно-независимых векторах P_j.

Так как векторы P_j являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m.

Определение 1. 8. Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным.

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

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

Пусть требуется найти максимальное значение функции

F=c₁x₁ + c₂x₂ + +. . . + c_nx_n

при условиях

Здесь a_ij, b_i и c_j (i=1,m; j=1,n) - заданные постоянные числа (m_i>0).

Векторная форма данной задачи имеет следующий вид: найти максимум функции

при условиях

x₁P₁+x₂P₂+. . . +x_mP_m+. . . +x_nP_n=P₀ (6)

x_j>=0 (j=1,l; l<=n) (7)

где

так как

b₁P₁+b₂P₂+. . . +b_mP_m=P₀

то по определению опорного плана X=( b₁, b₂, . . . , b_m, 0, . . . , 0) является опорным планом данной задачи (последние n-m компонент вектора X равны нулю). Этот план определяется системой единичных векторов P₁, P₂, . . . , P_m, которые образуют базис m-мерного пространства.

Найдем

Теорема 1. 1. (признак оптимальности опорного плана). Опорный план X=(x₁^*, x₂^*, …, x_m^*,0,0,…,0) задачи (5)-(7) является оптимальным, если _j>=0 для любого j (j=1, …, n)

Теорема 1. 2. Если _k<0 для некоторого j=k и среди чисел a_ik (i=1, …m) нет положительных (a_ik <=0), то целевая функция (5) задачи (5)-(7) не ограничена на множестве ее планов.

Теорема 1. 3. Если опорный план X задачи (5)-(7) невырожден и _k<0, но среди чисел a_ik есть положительных (не все a_ik <=0), то существует опорный план X₁ такой, что F(X₁)>F(X).

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

Теоремы (1-3) позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

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

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

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

В симплекс таблице первые от строк определяются исходными данным задачи, а показатели (от m+1)-й строки вычисляют. В этой строке i столбце вектора Р₀ записывают значение целевой функции, котора она принимает при данном опорном плане, а в столбце вектора P_j значение _j = Z_j - C_j. Значение z_j находится как скалярное произведение вектора P_j на вектор C₆

Значение F₀ равно скалярному произведению вектора P₀ на вектор С_б:

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

В первом случае на основании признака оптимальности исходный опрный план является оптимальным.

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

В качестве вектора, вводимого в базис, можно взять любой из акторов P_j, имеющий индекс j, для которого _j< 0. Пусть, например, _j<0 и решено ввести в базис вектор P_k.

Для определения вектора, подлежащего исключению из базиса, [находят min (b_i/a_ik) для всех a_ik> 0]. Пусть этот минимум достигается при i = r. Тогда из базиса исключают вектор Р_r, а число a_rk называется разрешающим элементом.

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

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

Базис	Сб	P0	c1	…	cm	cm+1	…	ck	…	cn
			P1	…	Pm	Pm+1	…	Pk	…	Pn
P1	c1	b1	1	…	0	a1m+1	…	a1k	…	a1n
…	…	…	…	…	…	…	…	…	…	…
Pr	cr	br	0	…	0	arm+1	…	ark	…	arn
…	…	…	…	…	…	…	…	…	…	…
Pm	cm	bm	0	…	1	amm+1	…	amk	…	amn
			0	…	0	m+1	…	k	…	n

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

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

Элементы векторов Р₀ и Р_j в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце С_б в строке вводимого вектора проставляют величину с_к, где k - индекс вводимого вектора.

Остальные элементы столбцов вектора Р₀ и Р_j новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

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

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

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

После заполнения новой симплекс-таблицы просматривают элементы (m+1)-й строки. Если все z_j- c_j > 0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо получают оптимальный план задачи, либо устанавливают ее неразрешимость.

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

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

f(x₁, x₂, …, x_n)

При условии, что переменные удовлетворяют соотношениям

где f и g_i - некоторые известные функции n переменных, а b_i - заданные числа.

В результате решения задачи будет определена точка X^*=(x₁^*, x₂^*, …, x_n^*), координаты которой удовлетворяют соотношениям.

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

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

Если определена область допустимых решений, то нахождение решения задачи сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f(x₁, x₂, …, x_n)=h. Указанная точка может находиться как на границе области допустимых решений, так и внутри нее.

Элементы аналитической геометрии на прямой плоскости и в трехмерном пространстве.

Уравнение линии на плоскости

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

Определение. Уравнением линии называется соотношение y = f(x) между координатами точек, составляющих эту линию.

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

Характерный пример - траектория движущейся точки. В этом случае роль параметра играет время.

Уравнение прямой на плоскости

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

Ах + Ву + С = 0,

причем постоянные А, В не равны нулю одновременно, т.е. А² + В² 0. Это уравнение первого порядка называют общим уравнением прямой.

В зависимости от значений постоянных А,В и С возможны следующие частные случаи:

C = 0, А 0, В 0 - прямая проходит через начало координат

А = 0, В 0, С 0 { By + C = 0}- прямая параллельна оси Ох

В = 0, А 0, С 0 { Ax + C = 0} - прямая параллельна оси Оу

В = С = 0, А 0 - прямая совпадает с осью Оу

А = С = 0, В 0 - прямая совпадает с осью Ох

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

Функции и ее свойства

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

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

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

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

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

Для обозначения принадлежности элемента некоторому множеству используется знак . А для обозначения не принадлежности используется знак .

Обозначения некоторых числовых множеств

N Ї множество натуральных чисел.

Z Ї множество целых чисел.

Q Ї множество рациональных чисел.

R Ї множество действительных чисел.

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

Например:

1. |А| = 5, где А = {стул, стол, кресло, диван, секретер}.

2. |С| = 2, где С = {3,88).

Могут существовать множества, число элементов которых бесконечно. Кроме того, можно говорить о счетных и o несчетных множествах.

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

Если множества равны по мощности, т.е. имеют одинаковое число элементов, то их можно сравнивать по отношению равенства. При этом два множества равны, если они равны по мощности и все элементы одного множества совпадают с элементами другого. Обозначается: А = В или B = A. Соответственно можно говорить, что некоторые множества не равны, если они различаются хотя бы одним элементом. (А ? В). Кроме того множества могут находиться и в некоторых других отношениях друг с другом.