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

Из пројекта Википедија

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

\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\,\!, који задовољава све једначине истовремено, и да се нађе такав скуп уколико постоји. Постојање скупа решења зависи од једначина, али и од доступних вредности (да ли се ради о целим бројевима, реалним бројевима, и слично).

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

Уопштено, систем са 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 се декомпонује у производ три матрица. Матрице са леве и десне стране су леви и десни сингуларни вектори. Матрица у средини је дијагонална матрица и садржи сингуларне вредности. Матрица тада може бити инвертовања простом заменом редоследа три компоненте, транспоновањем матрица сингуларних вектора, и узимањем реципрочне вредности дијагоналних елемената средишње матрице. Ако је било која од сингуларних вредности сувише близу нуле, и стога близу сингуларности, поставља се на нулу.

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

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