- •Розділ II.
- •§8. Системи лінійних рівнянь і n-вимірні вектори.
- •8.1. Поняття системи лінійних рівнянь, системи лінійних нерівностей та їх розв’язків.
- •8.2. Поняття n-вимірного вектора і n-вимірного лінійного векторного простору.
- •8.3. Загальні теореми про множину розв’язків систем лінійних рівнянь.
- •8.4. Теорема Крамера для квадратних слр.
- •§9. Лінійні векторні простори.
- •9.1. Загальне поняття лінійного векторного простору.
- •9.2. Підпростори лінійних векторних просторів.
- •9.3. Геометрія лінійних векторних просторів.
- •9.4. Опуклі множини в п-вимірному просторі.
- •§10. Метод Гауса розв’язання систем лінійних рівнянь.
- •10.1. Загальна ідея методу Гауса.
- •10.2. Поняття загального розв’язку слр.
- •10.3. Елементарні перетворення слр .
- •Позначення: ;
- •Позначення: .
- •10.4. Перетворення виключення.
- •10.5. Умова несумісності слр.
- •10.6. Вилучення залежних рівнянь.
- •10.7. Алгоритм методу Гауса.
- •10.8. Матрична форма методу Гауса.
- •§11. Елементи матричної алгебри.
- •11.1. Вступ до матричної алгебри.
- •11.2. Арифметичні операції над матрицями.
- •11.3. Економічне тлумачення операції матричного множення.
- •11.4. Властивості операцій над матрицями.
- •11.5. Мультиплікативна форма методу Гауса
- •11.6.Обернена матриця, її обчислення і застосування.
- •11.7. Застосування оберненої матриці до розв’язання систем лінійних рівнянь.
- •§12. Визначники n-го порядку, їх обчислення та застосування.
- •12.1. Аналіз спільних властивостей визначників 2-го та 3-го порядку.
- •12.2. Поняття визначника n-го порядку.
- •12.3. Обчислення визначників n-го порядку за означенням.
- •Спосіб генерування всіх перестановок чисел 1, 2, …..., n.
- •Перестановки чисел 1, 2, 3, 4
- •Формула для обчислення визначника 4-го порядку
- •12.4. Метод Гауса обчислення визначників.
- •12.5. Розкладення визначника за елементами рядка (або стовпчика).
- •12.6. Детермінантна формула для оберненої матриці.
- •12.7. Властивості визначників.
- •12.8. Теорема Крамера (загальний випадок).
- •12.9. Інтерполяційний многочлен.
- •§13. Лінійна залежність і незалежність n-вимірних векторів.
- •13.1. На підходах до поняття лінійної залежності і незалежності.
- •13.2. Загальне поняття лінійної залежності і незалежності.
- •13.3. Лінійна залежність в ℝ2 і ℝ3.
- •13.4. Властивості лінійно залежних і лінійно незалежних систем n-вимірних векторів.
- •13.5. Базиси n-вимірних векторних просторів.
- •13.6. Фундаментальна система розв’язків системи лінійних рівнянь.
- •Якщо скористатися результатом роботи методу Гаусса
- •13.7. Критерій сумісності систем лінійних рівнянь.
9.4. Опуклі множини в п-вимірному просторі.
Поняття опуклості було суттєвим при розгляді в §4 двовимірної задачі лінійного програмування, тобто задачі пошуку точки мінімуму або максимуму лінійної функції від двох змінних на множині розв’язків системи лінійних нерівностей. Кожна лінійна нерівність визначає півплощину на координатній площині з граничною прямою . Множина розв’язків системи лінійних нерівностей є теоретико-множинним перетином півплощин (множиною спільних точок півплощин), а отже є многокутною множиною, у частинному випадку – многокутником, причому опуклим многокутником. Було геометрично доведено, що лінійна функція на опуклій множині або має одну єдину точку мінімуму (або максимуму), або, якщо таких точок декілька, то й кожна точка відрізку, що сполучає будь-які дві такі точки, є також точкою мінімуму (відповідно, максимуму), іншими словами, оптимальним розв’язком задачі лінійного програмування.
Задача лінійного програмування у своїй повній загальності вивчається в рамках дисципліни під назвою „Математичне програмування”. Там здійснюється аналіз цієї задачі й дається універсальний алгоритм її розв’язання (симплекс-метод). Цей алгоритм є суто алгебраїчним, його основною складовою макрооперацією є використання методу Гаусса розв’язання систем лінійних рівнянь. Розробка й обгрунтування алгоритму стали можливими завдяки дуже природному узагальненню на випадок п-вимірних векторних просторів геометричних понять і такої властивості, як опуклість. Зазначене узагальнення і нашою найближчою метою.
За класичним означенням, геометрична фігура називається опуклою, якщо через будь-яку точку, що належить її границі, можна провести пряму лінію так, що фігура буде повністю лежати по один бік від прямої.
Це означення є, як кажуть, “зовнішнім” означенням, його перевірка вимагає підходити до геометричної фігури ззовні і аналізувати при цьому безліч прямих ліній щодо взаємного розташування їх і фігури. Тому таке означення не є зручним для практичного використання.
На щастя, існує інше, еквівалентне, “внутрішнє”, означення, яке, до того ж, дуже зручне для узагальнення на випадок п-вимірних векторних просторів: геометрична фігура називається опуклою, якщо разом з будь-якими двома її точками цій фігурі повністю належить і весь відрізок з кінцями в цих точках.
Опуклі фігури: Не опуклі фігури:
Вправа. Довести еквівалентність наведених, „зовнішнього” і
„внутрішнього”, означень опуклості.
Для узагальнення на випадок п-вимірних векторних просторів потрібно узагальнити поняття „відрізок”. Як це ми робили вже багато разів, звернімось по допомогу до аналітичної геометрії, до її головного методу – методу координат – й до векторної алгебри, зокрема, до пов’язаних з відповідністю між точками та їх радіус-векторами операцій „число точка” і „точка + точка” (див. §3).
Розглянемо малюнок
Проведемо геометричні міркування і аналітичні перетворення. Точка Х є внутрішньою точкою відрізку АВ. Маємо колінеарні вектори , причому вектор отриманий стисканням вектору , отже
: радіус-вектор є лінійною комбінацією радіус-векторів , а отже точки – кінці цих векторів – утворюють таке саме співвідношення. Придивимось до отриманої лінійної комбінації. Коефіцієнти при векторах і сума цих коефіцієнтів =1; лінійні комбінації з такими властивостями називають опуклими лінійними комбінаціями. Виконані міркування і перетворення є доведенням теореми:
Теорема (про аналітичне подання відрізку).
Будь-який відрізок на координатній площині або в координатному просторі складається з точок – усіх можливих опуклих лінійних комбінацій кінців відрізку:
.
Формулювання цієї теореми дослівно береться за
Означення (відрізку у п-вимірному просторі).
Нехай a і b – точки n-вимірного простору ( n-вимірні вектори); відрізком з кінцями в точках a і b у n-вимірному просторі називається множина усіх можливих опуклих лінійних комбінацій точок a і b:
.
Доведемо тепер, за сформульованим означенням, опуклість деяких „стандартних” множин в ℝп, опуклість яких в ℝ2 і ℝ3 є очевидною.
Теорема (про опуклість гіперплощини в ℝп ).
Довільна гіперплощина в ℝп , тобто множина розв’язків рівняння
,
є опуклою множиною.
Д о в е д е н н я. Нехай і – дві довільні точки гіперплощини, тобто два довільні розв’язки рівняння, що визначає гіперплощину. Треба довести, що й відрізок повністю міститься у гіперплощині. Для цього треба показати, що довільна точка цього відрізку, тобто, довільна опукла лінійна комбінація точок і задовольняє рівняння гіперплощини. Беремо довільне дійсне число , утворюємо опуклу лінійну комбінацію
і підставляємо координати отриманого вектора у ліву частину рівняння гіперплощини; використаємо при цьому (як і при доведенні основних теорем про розв’язки систем лінійних рівнянь) першу векторну форму рівняння, для чого утворимо вектор коефіцієнтів :
.
Теорему доведено.
Теорема (про опуклість гіперпрямої в ℝп ).
Довільна гіперпряма в ℝп , що визначається рівнянням
,
є опуклою множиною.
Д о в е д е н н я – Вправа.
Теорема (про опуклість півпростору в ℝп ).
Довільний півпростір в ℝп , тобто множина розв’язків нерівності
,
є опуклою множиною.
Д о в е д е н н я – Вправа.
Теорема (про опуклість гіперкулі в ℝп ).
Довільна гіперкуля в ℝп , тобто множина розв’язків нерівності
є опуклою множиною.
Д о в е д е н н я. Нехай і – дві довільні точки гіперкулі, тобто два довільні розв’язки нерівності, що визначає гіперкулю. Треба довести, що й увесь відрізок повністю міститься у гіперплощині. Для цього треба показати, що довільна точка цього відрізку, тобто, довільна опукла лінійна комбінація точок і задовольняє нерівність. Беремо довільне дійсне число , утворюємо опуклу лінійну комбінацію
і підставляємо координати отриманого вектора у ліву частину нерівності; знову використаємо при цьому векторну форму нерівності, для чого позначимо :
.
При переході до нерівності ми скористались приналежністю точок і до кулі, а також нерівністю Коші-Буняковського. Остаточно маємо:
.
Теорему доведено.
Завершимо розгляд загального поняття опуклості однією дуже простою і в той же час важливою, як і її наслідки, теоремою.
Теорема (про опуклість перетину).
Перетин будь-яких двох опуклих множин, так само як і будь-якої сукупності будь-яких опуклих множин, є опуклою множиною, за умови, що він не є порожньою множиною.
Д о в е д е н н я. Нехай А і В – дві опуклі множини і С – їх перетин, тобто множина спільних точок А і В
.
Нехай точки і з ℝп належать множині С. Тоді вони належать й кожній з множин А і В . Оскільки множини А і В є опуклими, то разом з точками і кожна з них містить і увесь відрізок з кінцями в цих точках, а отже, відрізок повністю входить до складу перетину .
Теорему доведено.
Наслідок 1. Множина розв’язків будь-якої сумісної системи лінійних рівнянь є опуклою множиною.
Наслідок 2. Множина розв’язків будь-якої сумісної системи лінійних нерівностей є опуклою множиною.
Наслідок 2 разом з міркуваннями з аналітичної геометрії дозволяє узагальнити на випадок п-вимірного векторного простору поняття опуклого многокутника і опуклого многогранника: узагальненим опуклим (гіпер)многогранником в ℝп – поліедром – називається множина розв’язків сумісної системи лінійних нерівностей.