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

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

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

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

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

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

где су непознате, а бројеви су коефицијенти система. Стављамо коефицијенте у матрицу на следећи начин:

Ако представимо сваку матрицу словом, ово постаје

где је A а m×n матрица, x је вектор колона са n чланова, а b је вектор колона са m чланова. Гаус-Жорданова елиминација се примењује на све ове системе, чак и ако су коефицијенти из неког произвољног поља.

Ако је поље бесконачно (као у случају реалних или комплексних бројева), могућа су само следећа три случаја (тачно један ће бити тачан) за сваки дати систем линеарних једначина:

  • систем нема решења (систем је противречан)
  • систем има тачно једно решење
  • систем има бесконачно много решења

Систем облика

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

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

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