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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Система трьох рівнянь (3 площини) з трьома невідомими (тривимірність простору). Розв'язком є точка перетину площин.

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


\left\{
\begin{alignat}{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{alignat}
\right.

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

x_1,\ x_2,\ldots ,x_n є невідомими,
a_{11},\ a_{12},\ldots, a_{mn} є коефіцієнтами системи,
b_1,\ b_2,\ldots ,b_m — вільними членами[1].

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

Векторний запис[ред.ред. код]

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


 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\bold{x}=\bold{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
\bold{x}=
\begin{bmatrix}
x_1 \\ x_2 \\ \vdots \\ x_n
\end{bmatrix},\quad
\bold{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 \bold{x} \ = \bold{b}

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

  C A \bold{x} \ = C \bold{b} ,

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

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

 \bold{x} = A^{-1} \bold{b} .

Методи розв'язання[ред.ред. код]

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

Точні методи[ред.ред. код]

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

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

Ітераційні методи[ред.ред. код]

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

 \bold{x} = A^\prime \bold{x} + \bold{b}^\prime ,

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

 \bold{x}_{n+1} = A^\prime \bold{x}_n + \bold{b}^\prime .

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

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

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

Програмне забезпечення[ред.ред. код]

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

Зовнішні посилання[ред.ред. код]

Див. також[ред.ред. код]

Джерела[ред.ред. код]

Виноски[ред.ред. код]

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