Система лінійних алгебраїчних рівнянь

Система трьох рівнянь (3 площини) з трьома невідомими (тривимірність простору). Розв'язком є точка перетину площин.

Система лінійних алгебраїчних рівнянь (СЛАР) — в лінійній алгебрі система лінійних рівнянь, яка має вигляд:

$\left\{{\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&b_{m}.\\\end{alignedat}}\right.$

Це система m лінійних рівнянь з n невідомими, де

$x_{1},\ x_{2},\ldots ,x_{n}$ є невідомими,

$a_{11},\ a_{12},\ldots ,a_{mn}$ є коефіцієнтами системи,

$b_{1},\ b_{2},\ldots ,b_{m}$ — вільними членами.

Якщо кількість рівнянь співпадає з кількістю невідомих, таку систему лінійних рівнянь називають квадратною.

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

Векторний запис

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

$x_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots \\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots \\a_{m2}\end{bmatrix}}+\cdots +x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots \\a_{mn}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

Що дозволяє переформулювати задачу в термінах векторного простору: рівняння має розв'язок тоді і тільки тоді, коли лінійна комбінація (лінійна оболонка) векторів лівої частини включає вектор правої частини.

Матричний запис

Векторна форма еквівалентна матричній формі запису

$A\mathbf {x} =\mathbf {b}$

де A — матриця m×n, x — вектор з n компонент, b — вектор з m компонент.

$A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}$

Число векторів в базисі лінійної оболонки векторів є рангом матриці.

Множина розв'язків

Розв'язком системи лінійних алгебраїчних рівнянь є будь-яка сукупність дійсних чисел $x_{1},x_{2},...,x_{n}$, яка при підстановці в кожне рівняння системи перетворює його в тотожність.

Якщо система має хоча б один розв'язок, то вона називається сумісною, і несумісною, якщо не має жодного. Відповідь на питання сумісності системи дає теорема Кронекера-Капеллі.

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

Якщо всі вільні члени $b_{i}=0$, система лінійних алгебраїчних рівнянь називається однорідною. Однорідна система має очевидний розв'язок, у якому всі $x_{i}=0$. Цей розв'язок заведено називати тривіальним. Відмінні від тривіального розв'язки існують тільки тоді, коли матриця $A$ вироджена.

Еквівалентні системи лінійних алгебраїчних рівнянь

Системи лінійних алгебраїчних рівнянь називаються еквівалентними, якщо множина їхніх розв'язків збігається, тобто будь-який розв'язок однієї системи є водночас розв'язком іншої, і навпаки.

Систему, еквівалентну даній, можна отримати, зокрема, замінивши одне з рівнянь на це ж рівняння, помножене на будь-яке відмінне від нуля число. Еквівалентну систему можна отримати також, замінивши одне з рівнянь сумою цього рівняння з іншим рівнянням системи. Загалом, заміна рівняння системи на лінійну комбінацію рівнянь дає систему, еквівалентну початковій.

Система лінійних алгебраїчних рівнянь

$A\mathbf {x} \ =\mathbf {b}$

еквівалентна системі

$CA\mathbf {x} \ =C\mathbf {b}$,

де $C$ - невироджена матриця.

Зокрема, якщо сама матриця $A$ - невироджена, і для неї існує обернена матриця $A^{-1}$, то розв'язок системи рівнянь можна формально записати у вигляді

$\mathbf {x} =A^{-1}\mathbf {b}$.

Методи розв'язання

Методи розв'язку систем лінійних алгебраїчних рівнянь можна досить чітко поділити на три групи: точні, ітераційні та ймовірнісні. За Бахваловим (1987 рік), точні методи застосовні до систем з числом змінних до порядку 10⁴, ітераційні — 10⁷.

Точні методи

До точних методів належать методи, що дають точний результат у припущенні ідеальної арифметики (див. IEEE754). Точні методи можна застосовувати й тоді, коли коефіцієнти й вільні члени рівняння задані в аналітичній, символьній формі.

• Метод послідовного виключення. Найпростішим, хоча важким для практичних застосувань, методом розв'язування системи лінійних алгебраїчних рівнянь є метод послідовного виключення невідомих. Суть його в тому, що із першого рівняння змінна $x_{1}$ виражається через інші змінні, й підставляється в усі інші рівняння. Це можна зробити, якщо коефіцієнт $a_{11}$ відмінний від нуля. У випадку, якщо він нульовий, можна вибрати інше рівняння, оскільки перестановка рівнянь у системі дає еквівалентну систему. В результаті утворюється нова система рівнянь, в якій рівнянь на одне менше. З цією системою рівнянь можна поступити так само, отримуючи ще меншу систему рівнянь. Продовжуючи так, отримують одне лінійне рівняння, з якого можна визначити одну із змінних, а інші, виключені, виразити через неї.
• Метод Гауса — метод, найчастіше застосовуваний при ручному розв'язку СЛАР.
  • Метод Гауса-Жордана - модифікація методу Гауса.
• Метод Крамера (за формулами Крамера) — чисто теоретичний метод, непридатний до практичного використання через обчислювальну складність і малу точність, оскільки вимагає обчислення визначників, а тільки в одному визначнику $n!$ доданків. Метод Крамера може застосовуватися для матриць 2×2, або, щонайбільше, 3×3.
• Матричний метод (за допомогою оберненої матриці) - певна теоретична абстракція всіх інших точних методів.
• Метод квадратного кореня — квадратичний метод, який вимагає симетричної матриці системи.
• Метод прогонки зручний для розв'язку систем з тридіагональною матрицею, які часто виникають в задачах математичної фізики.

Ітераційні методи

Ітераційні методи встановлюють процедуру уточнення певного початкового наближення до розв'язку. При виконанні умов збіжності вони дозволяють досягти будь-якої точності просто повторенням ітерацій. Перевага цих методів у тому, що часто вони дозволяють досягти розв'язку з наперед заданою точністю швидше, а також розв'язувати більші системи рівнянь. Суть цих методі полягає в тому, щоб знайти нерухому точку матричного рівняння:

$\mathbf {x} =A^{\prime }\mathbf {x} +\mathbf {b} ^{\prime }$,

еквівалентного початковій системі лінійних алгебраїчних рівнянь. При ітерації $\mathbf {x}$ в правій частині рівняння заміняється, наприклад, у методі Якобі (метод простої ітерації) на наближення, знайдене на попередньому кроці:

$\mathbf {x} _{n+1}=A^{\prime }\mathbf {x} _{n}+\mathbf {b} ^{\prime }$.

Збіжність ітераційної процедури досягається вибором матриці $A^{\prime }$, що залежить від задачі. Умови збіжності конкретні для кожного конкретного методу.

Серед ітераційних методів можна відзначити найпопулярніші:

• Метод Якобі (метод простої ітерації);
• Метод Зейделя (інколи називають метод Гауса-Зейделя);
• Метод релаксації;
• Багатосітковий метод;
• Метод Монтанте;
• Метод Абрамова (використовується для розв'язування невеликих систем);
• Метод узагальнення мінімальних лишків;
• Метод біспряжених градієнтів;
• Стабілізований метод біспряжених градієнтів;
• Квадратичний метод спряжених градієнтів;
• Метод квазі-мінімальних лишків.

Системи лінійних нерівностей

Поряд з рівняннями суттєву роль у всіх розділах сучасної математики грають нерівності. Розв'язання багатьох задач зводиться до розв'язання нерівностей або їхніх систем.

Нерівність $F(x_{1},x_{2},...,x_{n})\lor \Phi (x_{1},x_{2},...,x_{n})$ (1) називають алгебраїчною, якщо функції $F(x_{1},x_{2},...,x_{n})$ та $\Phi (x_{1},x_{2},...,x_{n})$ - многочлени відповідно степеня m з n невідомими. Зокрема, якщо $F(x_{1},x_{2},...,x_{n})$ та $\Phi (x_{1},x_{2},...,x_{n})$ - лійнійні функції, тобто многочлени першого степеня, то нерівність (1) називається лінійною. Інакше кажучи, лінійними називають нерівності, у яких невідомі тільки першого степеня. Такими, наприклад, є нерівності $x+2,32y-z-{\sqrt {3}}\geqslant 0$ та $9097580232x+98052y-89512\leqslant 0$. Перше з них - лінійна нерівність з трьома невідомими, друга - з двома.

Лінійна нерівність з n невідомими у загальному вигляді записується так:

$a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}-a\leqslant 0.$

Програмне забезпечення

Методи розв'язання систем лінійних алгебраїчних рівнянь входять до складу численних математичних програм на зразок Mathematica, Maple, Matlab та інших. Окремими незалежними бібліотеками підпрограм, що надають такі можливості, є, зокрема Linpack та LAPACK. Відповідний модуль є також у GNU Scientific Library, IMSL, NAG.

Посилання

• Системи лінійних рівнянь // Вища математика в прикладах і задачах / Клепко В.Ю., Голець В.Л.. — 2-ге видання. — К. : Центр учбової літератури, 2009. — С. 30-33. — 594 с.
• WebApp, що розв'язує системи лінійних алгебраїчних рівнянь різними методами з поясненнями процедури розв'язку^{[недоступне посилання з травня 2019]}
• Онлайновий розв'язувач
• Ще один онлайновий розв'язувач
• Онлайновий калькулятор для систем лінійних рівнянь

Див. також

• Обернена матриця
• Псевдообернена матриця
• Теорема Кронекера-Капеллі

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)
• Гельфанд И. М. Лекции по линейной алгебре. — 5-е. — Москва : Наука, 1998. — 320 с. — ISBN 5791300158.(рос.)
• Мальцев А. И. Основы линейной алгебры. — 3-е изд. — Новосибирск : Наука, 1970. — 400 с.(рос.)
• Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.