2 Теория функционирования рыночной экономики (экономическое равновесие)

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

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

Как такое возможно, чтобы каждый следовал своим интересам и при этом во благо всему обществу? Первым ученым, кто провозгласил такой принцип, был английский экономист

Адам Смит. Вот знаменитая цитата из книги “Богатство народов “ (1776)

“Каждый индивидуум стремится использовать свой капитал так, чтобы достичь наибольшей выгоды. Он обычно не заботится о благе общества … Он стремится только

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

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

он часто гораздо лучше способствует реализации целей общества, чем он в действительности намеревался это сделать. “

Смит не объяснил, однако, что это за невидимая рука.

Первую попытку объяснить такое кооперативное поведение эгоистичных потребителей и составить математическую модель экономики сделал французский экономист Леон Вальрас (1874). Вальрас ввел понятие экономического равновесия. За эти пионерские мысли его выгнали из Франции.

Его идеи слишком опередили свое время. Математические методы того времени не могли решать такие проблемы. Экономисты считали, что математические методы

не применимы.

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

Затем Эрроу, Нэш ( тот самый, про которого фильм “Beautiful Mind”) и другие

развили эти идеи (Эрроу и Нэш получили Нобелевские премии по экономике).

В настоящее время эта теория хорошо развита в части существования равновесия, но

не известно, можем ли мы к нему придти.

3 Финансовая математика

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

- финансовая математика. Эта дисциплина занимается вопросами

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

Каждый грамотный человек в наше время должен знать хотя бы основы теории

финансов – что такое акция, облигация, соотношение между риском и доходностью,

как работает система страхования.

Развитие финансовой математики принято связывать во многом с работами

Г Марковитца и М Кендалла.

Г. Марковитц - основатель теории портфеля ценных бумаг.

Короче, во что вкладывать деньги с наименьшим риском при заданной доходности

(можно вкладывать в акции, облигации, недвижимость). Нельзя вкладывать все деньги в одно место – яйца не должны быть в одной корзине. Как распределить яйца по корзинам с наименьшим риском - это и есть теория Марковитца.

Другое направление финансовой математики - это исследование динамики цен

(Кендалл). Динамика цен крайне сложна. Пионером здесь был французский математик Башелье.

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

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

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

были в забвении. Сейчас эти идеи интенсивно развиваются.

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

Дальнейшая жизнь предпринимателя Иванова, или почему стоит иметь представление о финансовой математике (на основе реальных фактов)

В дальнейшем Иванов, заработав 100000 долларов США, вложил их в 1998

в фондовую биржу США, купив акции. К концу 1999 г., пока рынок быстро рос,

он имел уже акций на сумму около 1000000 долларов.

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

большой налог и от миллиона осталось бы только 600 000. Иванову было жалко 400000.

В конце концов, рынок рухнул в 2000 г. и от состояния Иванова ничего не осталось.

Все же положительный итог есть: Иванов помог заработать на квартиру

своему другу, небогатому, но талантливому русскому математику NN.

Этот пример иллюстрирует сложность проблем, связанных с финансами.

Оценка риска - очень сложная проблема.

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

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

Математическая модель – это некое множество объектов, плюс

описание операций над этими объектами. Мы начнем с элементарной теории матриц.

Матрицы

Матрицы и линейные системы уравнений применяются в:

А) В теории линейного программирования

Б) при расчете конструкций на прочность (сопромат)

В) при расчете динамики сложных систем на компьютере, например, при расчете

технологических процессов

Г) в нейроноподобных компьютерах (так называемых нейронных сетях)

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

и так далее,

Матрицы, они повсюду!

Определение

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

следующего вида

a₁₁ a₁₂ ... a_1n

a₂₁ a₂₂ ... a_2n

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

a_m1 a_m2 ... a_mn

Если таблица имеет такую структуру, говорят о матрице (matrix) размером m  n.

Если m = n, матрица называется квадратной. Если n=1, то матрица вырождается в столбец. Если m =1, матрица вырождается в строку. И то, и другое может быть

рассмотрено как частный случай матрицы. С другой стороны, матрица может быть рассмотрена как набор столбцов (строк)

Отметим также, что если m = n=1, тогда матрица есть просто одно число.

Матрица обозначается также (a_ij) Числа a_ij называются элементами матрицы (entries of matrix).

Возьмем матрицу A = (a_ij ) размером m  n. Поменяем в ней столбцы и строки местами.

Получим новую матрицу размером n  m . Она называется транспонированной

к A и обозначается A^tr .Ее элементы имеют вид (a_ji )

Матрица называется симметричной, если транспонированная к ней совпадает с ней самой ( в этом случае она квадратная, то есть размера n 3 n ). Матрица, транспонированная к строке, есть столбец.

Определим теперь сложение матриц и умножение их на число.

Сложение матриц и умножение их на число

Сумма двух матриц (a_ij) и (b_ij) одинакового размера есть матрица (c_ij) , где каждый элемент есть сумма соответствующих элементов первых двух матриц : c_ij= a_ij + b_ij.

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

Нулевой матрицей будет матрица, все элементы которой равны нулю.

Произведение матрицы (a_ij) на число c есть новая матрица (ca_ij) с элементами c a_ij.

Упрощенно говоря, чтобы умножить матрицу на число, надо все ее элементы

умножить на это число.

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

Множество матриц данного размера естественно обозначить M_mn.

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

Умножение матриц

(! Внимание – это сложное место )

Определение скалярного произведения строки на столбец.

Определим сначала скалярное произведение строки

(a_1, a_2, ... , a_n ) на столбец той же длины (b_1, b_{2 ,} ... b_n ) ^tr формулой

c = a₁ b₁ + a₂ b₂ + ... + a_n b_n .

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

первый элемент строки умножается на первый элемент столбца, второй

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

Определение произведения матриц

Рассмотрим две матрицы A и B размеров m  n и n  p соответственно.

Произведением С двух матриц A и B является матрица размера m  p, элементы которой определены формулой

c_ij = a_i1 b_1j + a_i2 b_2j + ... + a_in b_nj . (1.1)

Это правило вычисления произведения двух матриц может быть объяснено неформально

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

Внимание: Замечание 1

Умножение матриц ассоциативно, но не коммутативно: верно, что

A (B C) = (AB) C,

если произведения определены, но, вообще говоря, неверно, что

A B =BA

(даже для самых маленьких матриц размером 2 на 2! ).

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

[A , B] = A B - BA

(Коммутатор играет большую роль в квантовой механике).

Замечание 2

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

первой матрицы – сомножителя совпадала с длиной столбца второй матрицы –сомножителя.

Для каждого размера n имеется так называемая единичная матрица I. Это квадратная матрица размера n  n , у которой все элементы равны нулю, кроме диагональных элементов, которые равны 1. Если произведение A на I определено, то

A I = A = I A

Единичная матрица имеет такой вид:

1 0 0 0 ... 0

0 1 0 0 ... 0

.... .....

0 0 0 0 ... 1

( на главной диагонали стоят единицы, а остальные элементы равны нулю)

Зададимся вопросом: а деление матриц существует? Напомним, что для обычных чисел

деление это то же самое, что умножение на «обратное» число

a/b =a (1/b) = a b ^-1

По аналогии с этим равенством введем матрицу, обратную к данной матрице A.

Определение

Матрица В называется обратной к А, если выполнены равенства

B A = AB =I. (1.2)

Мы обозначаем матрицу, обратную к А, как А^-1 .Отметим, что матрица, обратная к данной матрице, не всегда существует.

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

Зачем нужна алгебра матриц и, в частности, обратная матрица?

Чтобы объяснить это, рассмотрим такой пример. Возьмем квадратную матрицу А

размером n  n. Возьмем матрицу X размером n  1.

Такая матрица может быть рассмотрена как столбец (она состоит из единственного столбца). Вычислим произведение А на X .

По определению произведения, это будет матрица размером n  1. Обозначим ее

В. Это тоже будет столбец. Мы получили формулу

А X = В. (1.3)

Будем рассматривать эту формулу как уравнение относительно столбца X .

Матрицы А и В будем рассматривать как данные величины. Используем определение (1.1).

Вычислим элемент b₁ . По формуле (1.1) получаем

b₁ = a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n

Эту формулу перепишем в виде

a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n = b₁

Аналогично,

a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n = b₂

и так далее, последнее уравнение, определяющее b_{n ,} принимает вид

a_n1 x₁ + a_n2 x₂ + ... + a_nn x_n = b_n

Что же мы получили? Если собрать все уравнения вместе и записать в виде

a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n = b₂

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

a_n1 x₁ + a_n2 x₂+ ... + a_nn x_n = b_n ,

то можно понять, что мы получили систему n уравнений с n неизвестными.

Тем самым показано, что уравнение (1.3) представляет собой

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

(система линейная, если неизвестные входят только в первой степени, например, нет квадратов и членов вида x₂ x₁) . Напомним, что решить уравнение – это найти

такие значения x_i, что после подстановки этих значений равенства (1.3) становятся верными.

Такие системы важны в прикладных задачах, в вопросах прочности, в

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

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

Ранее это было очень сложной проблемой, теперь компьютеры делают это

быстро с помощью стандартных программ. Матрицы и векторы записываются в память

компьютеров с помощью массивов (arrays).

Решение системы с помощью обратной матрицы

Отметим, что если обратная матрица А^-1 существует, тогда решение

системы (1.3) существует, единственно и также может компактно записано в виде

X= А^-1 В (1.4)

Чтобы доказать эту формулу, достаточно умножить обе части (1.3) слева

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

А X= В  А^-1( А X ) = А^-1 В  (А^-1 А) X= А^-1 В  I X= А^-1 В

 X= А^-1 В.

Формула (1.4) удобна, если надо решить некоторую систему много раз

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

матрицу, и потом умножать ее на различные правые части.

Не всякое число имеет обратное, а лишь не нулевое. Точно также не каждая матрица имеет обратную.

Если обратная матрица не существует, тогда система может не иметь решения,

а может иметь и бесконечно много решений. Системы, не имеющие решений, называются

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

Если обратная матрица не существует, необходимо решать систему другими методами.

Определители

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

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

Если определитель не равен нулю, тогда обратная матрица существует.

Определитель вычисляется только для квадратных матриц.

Определитель – определение с помощью индукции по размеру матрицы n.

Базис индукции.

Определитель матрицы 2 на 2 вида

a₁₁ a₁₂

A =

a₂₁ a₂₂

есть, по определению, выражение вида

Det A = a₁₁ a_{22 -} a₁₂ a_{21 ,} (1.5)

то есть разность между произведением чисел на главной диагонали минус

произведение чисел на второй диагонали.

Используется также обозначение

a₁₁ a₁₂

Det A =

a₂₁ a₂₂

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

Возьмем матрицу A и сопоставим этой матрице таблицу знаков того

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

( например, для n=3)

+ - +

- + -

+ - +

Определение

Минором элемента a_ij называется определитель матрицы, полученный вычеркиванием из данной матрицы i - го столбца и j –ой строки, то есть

столбца и строки, на пересечении которых стоит данный элемент.

Алгебраическое дополнение d_ij элемента a_ij - это его минор, домноженный на (-1) ^i+j

(то есть, неформально говоря, минор, взятый со знаком из таблицы).

Шаг индукции:

Вычисление определителя матрицы размера n  n через определители меньшего размера (n -1) (n-1).

Берем строку, например, первую. Для каждого элемента строки a_1j вычисляем

соответствующий минор и алгебраическое дополнение d_{1j .}

Затем берем сумму произведений элементов на соответствующие дополнения.

Формально, имеем

Det A = a₁₁ d₁₁ + a₁₂ d₁₂ + a₁₃ d₁₃ + _... + a_1n d_1n

Например, для определителя третьего порядка получаем

Det A = a₁₁ (a₁₁ a₂₂ - a₁₂ a₂₁) - a₁₂ (a₁₁ a₃₃ - a₁₃ a₃₁) + a₁₃ (a₃₃ a₂₂ - a₃₂ a₂₃ )_.

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

Определитель квадратной матрицы размером 100 на 100, если его вычислять по определению будет содержать 100! = 100 99 98 97 … 3 2 1 членов.

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

Утверждение 1 (без доказательства)

Определитель может быть разложен по любой строке или столбцу.

Det A = a_i1 d₁₁ + a_i2 d_i2 + a_i3 d_i3 + _... + a_in d_in

Результат не зависит от выбора строки (столбца).

Утверждение 2 (без доказательства )

Если определитель квадратной матрицы не равен нулю, то она имеет

обратную. В этом случае система уравнений (1. 3) имеет единственное решение.

Свойства определителей.

0 Определитель, содержащий нулевую строку или столбец, равен нулю.

1 Если переставить две строки или два столбца определителя местами, он поменяет знак

2 Если умножить все элементы строки (или столбца) определителя на некоторое число, то определитель умножается на тоже самое число

3 Если умножить все элементы строки определителя на некоторое число a и прибавить полученную строку к другой строке, определитель сохранит свое значение. То же самое верно и для столбцов. Отсюда и из свойства 0 следует, что определитель с двумя равными столбцами равен нулю (то же для строк).

4 Det A = Det A^tr

5 Det I = 1

6 Det (A B) = Det A Det B

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

не рассматриваем.

Операции над строками (или столбцами), перечисленные в свойствах 1 -3,

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

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

Во многих книгах описывается метод решения систем линейных уравнений на основе

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

Метод (правило) Крамера

Чтобы решить систему (1.3), сначала вычисляем определитель матрицы системы

Det A. Предположим сначала, что он не равен нулю. Обозначим этот определитель

буквой D.

Затем заменяем первый столбец матрицы A на столбец правых частей В.

Определитель полученной матрицы обозначим D₁. После снова берем матрицу системы

A и заменяем второй столбец матрицы A на столбец правых частей В.

Определитель полученной матрицы обозначим D₂ . И так далее, n раз, вплоть

до последнего столбца. Последний определитель будет D_n.

После этого неизвестные можно определить по формулам

x₁ = D₁/ D , x₂ = D₂/ D , ... x_n = D_n/ D

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

D₁, D₂, ... D_n равны нулю, то у системы имеется бесконечно много решений. Если

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

Доказательство корректности правила Крамера

( материал повышенной трудности )

Обозначим столбцы матрицы A через A_1, A_2, … A_n . Запишем систему в виде

x₁ A₁ + x₂ A₂ + … + x_n A_n = B.

Определитель матрицы, составленной из столбцов A_1, A_2, … A_n

обозначим Det(A₁ , A₂ , … , A_n). Заметим, что по свойствам определителей

Det(A_1, A_1, A_3, … A_n ) =0,

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

Вычислим определитель D₁, равный Det(B_, A_2, A_3, … A_n ).

Вместо B подставим его выражение в виде суммы столбцов, приведенное выше

Получим D₁ = Det(x₁ A₁ + x₂ A₂ + … + x_n A_{n ,} A_2, A_3, … _, A_n ). По свойству 3 определителей

D₁ = x₁ Det( A_1, A_2, A_3, … _, A_n ) = x₁ D,

что и доказывает правило Крамера.

Алгоритмы

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

Что такое алгоритм? Это слово арабского происхождения. Точное определение этого понятия не представляется возможным здесь дать ( этому посвящены работы

А Тьюринга, Черча, А А Маркова и других выдающихся математиков)

С интуитивной точки зрения, алгоритм (algorithm) - это формально описанная

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

Например, для задачи о решении системы линейных уравнений входом является

матрица системы А и столбец правых частей B, выход – столбец неизвестных X.

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

Вообще говоря, затруднительно написать программу для решения задачи, не имея предварительно алгоритма ее решения.

Существуют задачи, которые не могут быть решены с помощью алгоритма,

и задачи, для решения которых эффективные алгоритмы неизвестны.

Далее, существуют задачи, где сложность вычислений быстро растет

вместе с размером входа. Много проблем в этой области не решено, и их

решение было крайне полезно для приложений.

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

Метод Гаусса

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

имела бы матрицу А ступенчатого (или треугольного) вида, и следовательно, легко решалась.

Расширенная матрица системы - это матрица системы плюс столбец правых частей.

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

a₁₁ a₁₂ ... a_{1 n-1} a_1n

0 a₂₂ ... a_{2 n-1} a_{2 n}

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

0 0 ... a_{m -1 n-1} a_{m -1 n}

0 0 ... 0 a_mn

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

1 2 3 -1 5 6

0 0 2 0 6 7 (М2)

0 0 0 1 2 5

или как

1 2 3 -1 5 6

0 1 2 0 6 7 (М3)

0 0 3 1 2 5

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

Для общего случая ступенчатой системы процесс решения несколько сложнее (см. ниже).

Чтобы свести систему к ступенчатому виду, делаем преобразование расширенной мктрицы следующим образом.

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

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

a_21, из третьей строки вычтем первую, умноженную на a₃₁ и т. д.

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

Если в результате процесса возникла полностью нулевая строка, вычеркиваем ее.

Если возникла строка, которая вся нулевая, кроме последнего столбца, система несовместна.

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

Итак, метод Гаусса состоит в следующем: записывается

расширенная матрица системы;

потом она приводится элементарными преобразованиями (см. Определители,

свойства 1-3) к ступенчатому виду;

после этого система решается ходом снизу вверх.

Если полученная ступенчатая система не треугольная,

(как в случае матриц М2, М3), тогда решений может не быть вовсе или их может быть бесконечно много.

В этом случае можно предложить следующую процедуру решения. Выделим так называемые главные переменные. Они соответствуют главным элементам строк. Элемент строки ступенчатой матрицы называется главным, если он есть самый левый крайний ненулевой элемент. Например, в М2 главные элементы есть a₁₁ , a_{23 ,} a₃₄ . Соответственно, главные переменные есть x_1, x_3, x₄ .

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

Рассмотрим в качестве примера систему с расширенной матрицей

1 2 3 -1 = 5

0 1 2 0 = 6 (М3)

.

0 0 0 1 = 2

Главные переменные x_1, x_2, x_{4 ,} неглавная - x₃ .

Из последнего уравнения следует, что x₄ = 2. Второе уравнение приводится к виду

x₂ = 6 -2 x₃, после чего первое уравнение принимает вид

x₁ = 5 -2 x₂ – 3 x₃ + x₄ .

После подстановки предыдущих формул, имеем окончательно:

x₁ = x₃ - 5, x₂ = 6 -2 x₃ , x₄ = 2.

При этом x₃ может принимать любые значения и система неопределенная - имеется бесконечно много решений.

Метод Гаусса также эффективен для решения нескольких систем уравнений сразу.

Тогда, чтобы уменьшить время вычислений, выгодно в качестве расширенной матрицы

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

Определители матриц большого размера также более удобно подсчитывать с помощью

метода Гаусса.

Нахождение обратной матрицы

Правило нахождения обратной матрицы

Если определитель исходной матрицы A не равен нулю, то сначала образуем матрицу, составленную из алгебраических дополнений элементов матрицы A. Затем транспонируем полученную матрицу и делим все ее элементы на определитель Det A.

Метод Гаусса для нахождения обратной матрицы

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

Получаем матрицу с 2n столбцами и n строками состоящую из двух квадратных

матриц.

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

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

Сравнение эффективности алгоритмов для больших n

(матриц большого размера)

Большую практическую важность имеет вопрос о сравнительной эффективности

различных вычислительных методов. Разработке этих методов было посвящено

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

размера.

Когда компьютеров не было, решение системы 100 уравнений со 100 неизвестными

представлялось неразрешимой задачей. Еще в середине 80-х годов ИБМ 360,

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

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

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

a_{12 .} Для этого прибавим ко второй строке первую строку, умноженную на c= - a_12/ a_11.

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

Мы увидели, что получение одного нуля требует порядка n операций. Нам надо получить порядка 0.5n² нулей. Итого, получаем результат:

Метод Гаусса для решения системы n неизвестных с n уравнениями требует порядка n³ операций.

Таким образом, для решения системы со 100 неизвестными и 100 уравнениями требуется около миллиона операций.

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

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

Для определителя матрицы размером n на n это вычисление требует n! операций.

Для n = 100 это число больше чем 10¹⁰⁰ и оно совершенно грандиозно. Ни один компьютер в мире не справится с таким вычислением даже за миллион лет.

Долго время полагали, что метод Гаусса оптимален (самый быстрый, по крайней мере, для матриц общего вида).

В 1969 немецкий математик В. Штрассен доказал, что это не так. (Его статья так и называлась Gauss elimination is not optimal и произвела сенсацию в математическом мире) Оказывается можно решить систему с n неизвестными и n уравнениями за n^2.87 операций. К 1986 г. этот показатель был улучшен до n^2.37

Внедрение этих идей в расчеты позволило фирме Боинг сэкономить

миллионы долларов, но изобретатель не получил ни цента …

Матричная формулировка линейного программирования

Задача линейного программирования также может быть сформулирована

в матричном виде.

Сначала сформулируем определение. Столбец B назовем неотрицательным, если все его элементы b_i неотрицательны

b ₁  0 b ₂ .0, .... b _n  0

Мы скажем, что столбец B не меньше столбца X, если они равного размера и

все элементы B не меньше соответствующих элементов X.:

b ₁  x ₁ b ₂ . x₂, .... b _n  x_n

Рассмотрим теперь следующую задачу линейного программирования

Даны числа a₁₁ , a₁₂ , a₂₁, a₂₂, a₃₁ , a₃₂ , с₁ , с₂ , b₁ , b_{2 .}

Найти неотрицательные числа x₁ , x₂ , такие, что выражение

S= с₁ x₁ + c₂ x₂

было бы максимально, при условиях

(0.1) a₁₁ x₁ + a₁₂ x₂  b₁

(0.2) a₂₁ x₁ + a₂₂ x₂  b₂

(0.3) a₃₁ x₁ + a₃₂ x₂  b₃

Введем столбец B, составленный из чисел (b_{1 ,} b₂ , b₃ ), и столбец неизвестных

(x_{1 ,} x₂ , x₃ ) =X. Введем строку C коэффициентов (c_{1 ,} c₂ , c₃).

Наконец, введем матрицу А вида

a₁₁ a₁₂

А = a₂₁ a₂₂

a₃₁ a₃₂

В этой задаче A, B, C - это входные данные, X - решение (выходные данные)

Тогда наша задача в матричном виде может быть сформулирована в замечательно компактном виде так:

Найти столбец X такой, что целевая функция, равная скалярному произведению С X,

максимальна, при условиях, что X  0 и B  A X.

Контрольные вопросы

1 Почему обратная матрица определена только для квадратных матриц?

2 Приведете пример, показывающий, что произведение матриц не коммутативно

3 Запишите в матричном виде систему

x₁ + x₂ + . x₃ + x₄ = 1

x₁ + 2 x₂ + 4 x₃ + 5 x₄ = 2

x₁ + 3 x₂ + 16 x₄ = 3

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

5 Опишите алгоритм вычисления n факториал

Векторы и операции над ними

Все мы знаем, что сила – это вектор. Рассмотрим математическую

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

к фундаментальному понятию – понятию линейного (векторного пространства)

Определение

Рассмотрим плоскость P. Вектор на плоскости – это упорядоченная пара точек плоскости

(A, B) , где А - начало вектора, В – конец вектора.

Такой вектор обозначают сокращенно просто AB.

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

переноса (см. рис)

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

Можно упрощенно представлять себе вектор

как направленный отрезок AB или, совсем упрощенно, как стрелку на плоскости. Когда человек планирует идти куда-нибудь, он может мысленно планировать свой путь в виде вектора, а если маршрут сложный - в виде совокупности векторов.

Над векторами делают различные операции. Первая операция – сложение.

Cложение векторов

Сумма AB + BC есть, по определению, A C, то есть вектор, идущий из начала первого в конец второго. Чтобы сложить вектор AB и вектор DC, заменяем второй вектор равным ему вектором с началом в конце первого вектора, то есть вектором BE= DC. Получаем AE.

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

Длина вектора AB – это длина соответствующего отрезка |AB|.

Векторы AB и B A называются противоположными. Их сумма равна так называемому нулевому вектору, начало и конец этого вектора совпадают, а длина равна нулю.

Замечание – число ноль и нулевой вектор – разные математические объекты.

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

Далее мы также обозначаем векторы одной буквой ( a , b и так далее).

Длины будем обозначать |a|,| b| . В книгах иногда используют жирный шрифт, либо

ставят стрелку сверху.

Сложение удовлетворяет следующим свойствам:

А1) сложение векторов удовлетворяет тем же свойствам, что и сложение обычных чисел,

а именно, ассоциативности и коммутативности

(a+ b) +c=a + (b+c), a + b = b +a,

А2) Имеется нулевой вектор 0 такой, что

a+0= a для любого a

А3) Для любого вектора a во множестве всех векторов V есть вектор - a,

называемый противоположным к a, такой, что

a+ (-а)=0

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

Умножение вектора на число

Если число . положительно, то произведение числа на вектор a есть новый вектор с длиной  |a| и с тем же направлением, что направление вектора a.

Если число ноль – то результат умножения есть нулевой вектор.

Если число .отрицательно, то результат умножения есть вектор с длиной || |a|

и противоположный по направлению к a.

Свойства умножения на число таковы:

А4) 1 a =a

A5) ( a)= () a

A6) (+) a=  a +  a (дистрибутивность)

A7)  (a +b)=  a +  b (дистрибутивность)

где ,  - числа.

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

Следующая операция - это скалярное произведение векторов a и b.

Результат этой операции - число, равное произведению длин a и b

умножить на косинус угла между ними:

a b = |a| |b | cos .

Эта операция удовлетворяет следующим свойствам:

А8) (a + b) c = ac + b c (дистрибутивность скалярного произведения)

A9) (a b) = (a) b

где  - число

A10) ab =ba (коммутативность)

А11) a а ≥ 0, причем равенство нулю только в случае, если вектор a =0.

Заметим также, что абсолютное значение скалярного произведения двух векторов меньше, либо равно чем произведение их длин:

|a b|  |a| |b|.

Угол между векторами a и b может быть найден по следующей формуле

cos  = a b( |a| |b |)^-1 .

Косинус угла есть скалярное произведение векторов делить на произведение их длин.

Векторная алгебра

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

Квадратом вектора  будет его скалярное произведение самого на себя, то есть  . a .

Как и в обычной алгебре верна формула

(a +b)(a+b)= a a + 2 ab + bb

Длина вектора в квадрате равна его скалярному квадрату |a|= aa

Два вектора будут ортогональными (перпендикулярными), если их скалярное произведение равно нулю (угол между ними тогда есть /2)

Если a и b ортогональны (перпендикулярны), то формула (a +b)(a+b)= a a + 2 ab + bb приобретает вид

(a +b)(a+b)= a a + bb

или

|a|²+ |b|²=|a +b| ².

Вопрос: каков геометрический смысл этой формулы?

Это знаменитая теорема Пифагора (см. рис).

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

Совершенно аналогично определяются векторы в пространстве. Операции те же самые

и обладают теми же свойствами.

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

Векторные (линейные) пространства

( материал повышенной трудности)

Рассмотрим некоторое множество V.

Его элементы мы будем обозначать их буквами a, b ,...

Предположим, что

с элементами из V можно делать две операции:

1. операция сопоставляет двум элементам третий элемент.

2. умножение элемента на число

3) скалярное произведение двух векторов

Итак, первая операция сопоставляет двум элементам a и b третий, называемый их суммой и обозначаемый a + b.

Вторая операция сопоставляет элементу a и числу α новый элемент, обозначаемый α a.

Результат этой операции также вектор.

Наконец, третья операция (скалярное произведение) сопоставляет двум векторам a и b число, обозначаемое a b .

Определение

Множество элементов V, где введены операции сложения и умножения на число, удовлетворяющие свойствам А1 –А7, называется векторным (линейным)

пространством V . Элементы векторного пространства называются векторами.

Рассмотрим векторное пространство, в котором есть третья операция, сопоставляющая двум векторам a и b число, обозначаемое a b .

Если эта операция удовлетворяет свойствам (А8- А11), то

такое множество векторов называется векторным пространством со скалярным произведением (или эвклидовым пространством).

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

Мы видели, что векторы на плоскости образуют векторное пространство

со скалярным произведением (эвклидово пространство). Обозначим его E ² .

Линейное (векторное) пространство – фундаментальная модель во многих приложениях, например, в теории автоматического управления, теории случайных процессов и т. д. Эта модель применима в тех случаях, когда состояние физической (механической) системы мало отклоняется от некоторого «среднего состояния». В случае, когда мы идем дело с экстремальными явлениями, необходимо использовать нелинейные модели.

Идея свести геометрию к абстрактной алгебре векторов оказалось крайне полезной.

Эти идеи принадлежат Г. Вейлю, Дж. Нейману, Д, Гильберту и другим.