Systém lineárních algebraických rovnic

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. ledna 2021; kontroly vyžadují 7 úprav .

Soustava lineárních algebraických rovnic ( lineární systém , používají se i zkratky SLAE , SLUE ) je soustava rovnic , ve které je každá rovnice lineární algebraickou rovnicí prvního stupně.

V klasické verzi jsou koeficienty u proměnných, volných členů a neznámých považovány za reálná čísla , ale všechny metody a výsledky jsou zachovány (nebo přirozeně zobecněny) na případ libovolných polí , například komplexních čísel .

Řešení systémů lineárních algebraických rovnic je jedním z klasických problémů lineární algebry , který do značné míry určoval její objekty a metody. Navíc lineární algebraické rovnice a metody jejich řešení hrají důležitou roli v mnoha aplikovaných oblastech, včetně lineárního programování , ekonometrie .

Lze zobecnit na případ nekonečné množiny neznámých .

Konvence a definice

Celkový pohled na soustavu lineárních algebraických rovnic:

{\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\tečky +a_{1n}x_{n}=b_{1}\\a_{21}x_ {1}+a_{22}x_{2}+\tečky +a_{2n}x_{n}=b_{2}\\\tečky \\a_{m1}x_{1}+a_{m2}x_{ 2}+\tečky +a_{mn}x_{n}=b_{m}\\\end{cases}}

Zde je počet rovnic a počet proměnných, jsou neznámé, které mají být určeny, koeficienty a volné členy jsou považovány za známé. Indexy koeficientů v soustavách lineárních rovnic ( ) se tvoří podle následující konvence: první index ( ) označuje číslo rovnice, druhý ( ) je číslo proměnné, na které tento koeficient stojí [1] . $m$ $n$ $x_{1},x_{2},\tečky ,x_{n}$ ${\displaystyle a_{11},a_{12},\tečky ,a_{mn))$ ${\displaystyle b_{1},b_{2},\tečky ,b_{m))$ $a_{{ij}}$ $i$ $j$

Systém se nazývá homogenní , pokud jsou všechny jeho volné členy rovny nule ( ), jinak je heterogenní . $b_{1}=b_{2}=\dots =b_{m}=0$

Kvadratická soustava lineárních rovnic je soustava, ve které se počet rovnic shoduje s počtem neznámých (). Systém, ve kterém je počet neznámých větší než počet rovnic, je podurčený , takové systémy lineárních algebraických rovnic se také nazývají obdélníkové . Pokud existuje více rovnic než neznámých, pak je systém přeurčen . $m=n$

Řešením systému lineárních algebraických rovnic je množina čísel taková, že jejich odpovídající nahrazení namísto do systému změní všechny jeho rovnice na identity . $n$ ${\displaystyle c_{1},c_{2},\dots ,c_{n))$ $x_{1},x_{2},\tečky ,x_{n}$

Systém se nazývá kompatibilní , pokud má alespoň jedno řešení, a nekonzistentní, pokud nemá žádná řešení. Řešení se považují za odlišná, pokud se alespoň jedna z hodnot proměnných neshoduje. Společný systém s jediným řešením se nazývá určitý , pokud existuje více než jedno řešení - podurčeno .

Maticový formulář

Systém lineárních algebraických rovnic může být reprezentován ve formě matice jako:

\begin{pmatrix} 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{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}

nebo:

sekera = b

Zde je matice systému, sloupec neznámých a sloupec volných členů. Pokud je k matici vpravo přiřazen sloupec volných výrazů, pak se výsledná matice nazývá rozšířená. $A$ $X$ $b$ $A$

Kronecker-Capelliho teorém zakládá nezbytnou a postačující podmínku pro kompatibilitu systému lineárních algebraických rovnic prostřednictvím vlastností maticových reprezentací: systém je konzistentní právě tehdy, když se hodnost jeho matice shoduje s hodností rozšířené matice.

Ekvivalentní soustavy lineárních rovnic

Soustavy lineárních rovnic se nazývají ekvivalentní , pokud je množina jejich řešení stejná, to znamená, že jakékoli řešení jedné soustavy je také řešením jiné soustavy a naopak. Rovněž se předpokládá, že systémy bez řešení jsou ekvivalentní.

Systém ekvivalentní dané soustavě lze získat zejména nahrazením jedné z rovnic touto rovnicí vynásobenou libovolným nenulovým číslem. Ekvivalentní systém lze také získat nahrazením jedné z rovnic součtem této rovnice jinou rovnicí systému. Obecně platí, že nahrazením rovnice systému lineární kombinací rovnic vznikne systém, který je ekvivalentní původnímu.

Systém lineárních algebraických rovnic je ekvivalentní systému , kde je nesingulární matice . Zejména, pokud je matice sama o sobě nesingulární a existuje pro ni inverzní matice , pak řešení soustavy rovnic lze formálně zapsat jako . $A\mathbf {x} \ =\mathbf {b}$ $CA\mathbf {x} \ =C\mathbf {b}$ $C$ $A$ $A^{-1}$ $\mathbf {x} =A^{-1}\mathbf {b}$

Metody řešení

Přímé metody dávají algoritmus, kterým lze nalézt přesné řešení soustav lineárních algebraických rovnic. Iterační metody jsou založeny na použití iteračního procesu a umožňují získat řešení jako výsledek postupných aproximací.

Některé přímé metody:

Gaussova metoda
Gauss-Jordanova metoda
Cramerova metoda
Maticová metoda
Metoda rozmítání (pro tridiagonální matice )
Choleského rozklad nebo metoda druhé odmocniny (pro pozitivně definitní symetrické a hermitovské matice)

Iterační metody stanoví postup pro zpřesnění určité počáteční aproximace k řešení. Když jsou splněny podmínky konvergence, umožňují dosáhnout jakékoli přesnosti pouhým opakováním iterací. Výhodou těchto metod je, že často rychleji dosáhnou řešení s předem stanovenou přesností a také umožňují řešit rozsáhlé soustavy rovnic. Podstatou těchto metod je nalezení pevného bodu maticové rovnice

{\displaystyle \mathbf {x} =A^{\prime }\mathbf {x} +\mathbf {b} ^{\prime ))

ekvivalentní počáteční soustavě lineárních algebraických rovnic. Při iteraci na pravé straně rovnice, například v Jacobiho metodě (metoda jednoduché iterace), je nahrazena aproximace nalezená v předchozím kroku: $\mathbf {x}$

{\displaystyle \mathbf {x} _{n+1}=A^{\prime }\mathbf {x} _{n}+\mathbf {b} ^{\prime ))

Iterační metody jsou rozděleny do několika typů v závislosti na použitém přístupu:

Na základě rozdělení: $(MN)\mathbf {x} =\mathbf {b} \Šipka doleva M\mathbf {x} =N\mathbf {x} +\mathbf {b} \Šipka doprava M\mathbf {x} ^{n+ 1 }=N\mathbf {x} ^{n}+\mathbf {b}$
Typ variace: $A\mathbf {x} =\mathbf {b} \Rightarrow \|A\mathbf {x} -\mathbf {b} \|\rightarrow \min$
Typ projekce: $A\mathbf {x} =\mathbf {b} \Rightarrow (A\mathbf {x} ,\mathbf {m} )=(\mathbf {b} ,\mathbf {m} )\forall \mathbf { m}$

Mezi iterativní metody:

Jacobiho metoda ( jednoduchá iterační metoda )
Gauss-Seidelova metoda
Relaxační metoda
Multigrid metoda
Montante metoda
Abramovova metoda (vhodná pro řešení malých SLAE)
Metoda zobecněných minimálních reziduí
Metoda bikonjugovaného gradientu
Metoda stabilizovaného bikonjugátového gradientu
Kvadratická metoda bikonjugovaných gradientů
Metoda kvazi-minimálních reziduí ( QMR )
Metoda rotace [2]

Poznámky

↑ Ilyin V. A., Poznyak E. G. Lineární algebra: Učebnice pro univerzity. - 6. vyd., vymazáno. — M.: Fizmatlit, 2004. — 280 s.
↑ Verzhbitsky V. M. Základy numerických metod. - M . : Vyšší škola , 2009. - S. 80-84. — 840 s. — ISBN 9785060061239 .

Odkazy

Kuksenko SP, Gazizov TR Iterační metody řešení soustavy lineárních algebraických rovnic s hustou maticí. - Tomsk: Tomsk State University , 2007. - 208 s. - ISBN 5-94621-226-5 .
Forsythe J., Moler K. Numerické řešení soustav lineárních algebraických rovnic. - Moskva: Mir , 1969. - 166 s.

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava

Vektory a matice

vektory

Základní pojmy	Vektor v geometrii Základ Ortogonální základ Vektorové souřadnice Kolinearita Ortogonalita Lineární závislost Prostor sloupců
Druhy vektorů	Jednotkový vektor Axiální vektor izotropní vektor Normální Kolinearita Nulový vektor Vektor poloměru Vlastní vektor
Operace s vektory	Skalární součin vektorový produkt smíšený produkt Pseudoskalární produkt Dvojitý křížový produkt
Typy prostoru	vektorový prostor afinní prostor Euklidovský prostor Pseudoeuklidovský prostor Normovaný prostor Minkowského prostor

matrice

Základní pojmy	Maticové násobení Transponovaná matice Hermitovská konjugovaná matice Symetrická matice inverzní matice Vlastní hodnota Charakteristický polynom matice
Speciální matrice	Matice identity Nulová matice Diagonální matice lambda matrice
Maticové rozklady	LU rozklad Choleský rozklad QR rozklad rozklad LUP singulární rozklad hodnoty Spektrální rozklad matice

jiný