Систем линеарних једначина
Из пројекта Википедија
У математици и линеарној алгебри, систем линеарних једначина је скуп линеарних једначина, као што је
Стандардни проблем је да се утврди да ли постоји скуп вредности за непознате
, који задовољава све једначине истовремено, и да се нађе такав скуп уколико постоји. Постојање скупа решења зависи од једначина, али и од доступних вредности (да ли се ради о целим бројевима, реалним бројевима, и слично).
Системи линеарних једначина спадају међу најстарије математичке проблеме, и имају многе примене, као што су обрада дигиталних сигнала, процене, предвиђање, као и линеарно програмирање, и апроксимација нелинеарних проблема у нумеричкој анализи. Постоји много начина да се реши систем линеарних једначина. Међутим, међу најефикаснијима су Гаусов поступак и декомпозиција Чолеског.
Уопштено, систем са m линеарних једначина и n непознатих се записује на следећи начин
где су
непознате, а бројеви
су коефицијенти система. Стављамо коефицијенте у матрицу на следећи начин:
Ако представимо сваку матрицу словом, ово постаје
где је A а m×n матрица, x је вектор колона са n чланова, а b је вектор колона са m чланова. Гаус-Жорданова елиминација се примењује на све ове системе, чак и ако су коефицијенти из неког произвољног поља.
Ако је поље бесконачно (као у случају реалних или комплексних бројева), могућа су само следећа три случаја (тачно један ће бити тачан) за сваки дати систем линеарних једначина:
- систем нема решења (систем је противречан)
- систем има тачно једно решење
- систем има бесконачно много решења
Систем облика
се назива хомогеним системом линеарних једначина. Скуп свих решења се назива нула простором матрице A.
Посебно у светлу обиља горенаведених примена, неколико ефикаснијих алтернатива Гаус-Жордановој елиминацији је развијено за широк спектар специјалних случајева. Многи од ових побољшаних алгоритама су сложености O(n2) (види: нотација великог О). Неки од најуобичајенијих специјалних случајева су:
- За проблеме облика Ax = b, где је A симетрична Теплицова матрица, може се користити Левинсонова рекурзија или нека од њених варијација. Једна од често окришћених варијација је Шурова рекурзија, која се користи у обради дигиталних сигнала.
- За проблеме облика Ax = b, где је A сингуларна матрица, или готово сингуларна, матрица A се декомпонује у производ три матрица. Матрице са леве и десне стране су леви и десни сингуларни вектори. Матрица у средини је дијагонална матрица и садржи сингуларне вредности. Матрица тада може бити инвертовања простом заменом редоследа три компоненте, транспоновањем матрица сингуларних вектора, и узимањем реципрочне вредности дијагоналних елемената средишње матрице. Ако је било која од сингуларних вредности сувише близу нуле, и стога близу сингуларности, поставља се на нулу.






