Систем линеарних једначина

Из Википедије, слободне енциклопедије
Линеарни систем са три променљиве одређује скуп равни. Пресек свих равни је решење.

У математици и линеарној алгебри, систем линеарних једначина је скуп линеарних једначина, као што је


\begin{array}{rcrcrcc}
3x_1 &+& 2x_2 &-& x_3 &=& 1 \\
2x_1 &-& 2x_2 &+& 4x_3 &=& -2 \\
-x_1 &+& \frac{1}{2}x_2 &-& x_3 &=& 0
\end{array}

Стандардни проблем је да се утврди да ли постоји скуп вредности за непознате x_1, x_2, x_3\,\!, који задовољава све једначине истовремено, и да се нађе такав скуп уколико постоји. Постојање скупа решења зависи од једначина, али и од доступних вредности (да ли се ради о целим бројевима, реалним бројевима, и слично). Систем из горњег примера има јединствено решење:

\begin{alignat}{2}
x_1 & = & 1 \\
x_2 & = & -2 \\
x_3 & = & -2
\end{alignat}

Системи линеарних једначина спадају међу најстарије математичке проблеме, и имају многе примене, као што су обрада дигиталних сигнала, процене, предвиђање, као и линеарно програмирање, и апроксимација нелинеарних проблема у нумеричкој анализи. Постоји много начина да се реши систем линеарних једначина. Међутим, међу најефикаснијима су Гаусов поступак и декомпозиција Чолеског.

Уопштено, систем са m линеарних једначина и n непознатих се записује на следећи начин


\begin{array}{rcrcccrcl}
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 \\
a_{m1}x_1 &+& a_{m2}x_2 &+& \cdots &+& a_{mn}x_n &=& b_m
\end{array}

где су x_1,\ x_2,...,x_n непознате, а бројеви a_{11},\ a_{12},...,\ a_{mn} су коефицијенти система. Стављамо коефицијенте у матрицу на следећи начин:


\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} 

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

се назива хомогеним системом линеарних једначина. Скуп свих решења се назива нула простором матрице A.

Посебно у светлу обиља горенаведених примена, неколико ефикаснијих алтернатива Гаус-Жордановој елиминацији је развијено за широк спектар специјалних случајева. Многи од ових побољшаних алгоритама су сложености O(n2) (види: нотација великог О). Неки од најуобичајенијих специјалних случајева су:

  • За проблеме облика Ax' = b', где је A симетрична Теплицова матрица, може се користити Левинсонова рекурзија или нека од њених варијација. Једна од често окришћених варијација је Шурова рекурзија, која се користи у обради дигиталних сигнала.
  • За проблеме облика Ax' = b', где је A сингуларна матрица, или готово сингуларна, матрица A се декомпонује у производ три матрица. Матрице са леве и десне стране су леви и десни сингуларни вектори. Матрица у средини је дијагонална матрица и садржи сингуларне вредности. Матрица тада може бити инвертовања простом заменом редоследа три компоненте, транспоновањем матрица сингуларних вектора, и узимањем реципрочне вредности дијагоналних елемената средишње матрице. Ако је било која од сингуларних вредности сувише близу нуле, и стога близу сингуларности, поставља се на нулу.

Литература[уреди]

  • Ayres, Frank, Schaum's Outline of Modern Abstract Algebra, McGraw-Hill; 1st edition (June 1, 1965). ISBN 0-07-002655-6.

Види још[уреди]

Спољашње везе[уреди]