Метод на Гаус

Идея за алгоритъма

Методът на Гаус на най-интуитивният, когато се решават ленейни системи. А именно — идеята е да се достигне такът вариант на матрицата $A$ чрез еквиваленти преобрзувания, че да се получи еквиваленто на началното уравнение $Ax = b$ от вида $Ux = \hat{b}$ и $U$ е долнотриъгълна матрица.

Алгоритъм 1

За по-нагледно разглеждаме случая при $n = 2$. Тогава $A = \begin{pmatrix} a_{1,1} & a_{1,2}\\ a_{2,1} & a_{2,2} \end{pmatrix}$ и $b = \begin{pmatrix} b_{1}\\ b_{2} \end{pmatrix}$.

Прав ход

Образуваме разширената матрица $( A | b ) = \begin{pmatrix} a_{1, 1}\ a_{1,2} & b_1 \\ a_{2,1}\ a_{2,2} & b_2 \end{pmatrix}$. Умножаваме пърия ред по $- l_{2,1} = \frac{a_{2,1}}{a_{1, 1}}$ и го събираме с втория ред.
Тогава $(A^{(1)} | b^{(1)}) = \begin{pmatrix} a_{1,1} & a_{1,2} & b_1\\ 0 & a_{2,2}^{(1)} & b_2^{(1)} \end{pmatrix}$, където $a_{2,2}^{(1)} = a_{2,2} - l_{2,1}a_{1,2}$ и $b_2^{(1)} = b_2 - l_{2,1}b_1$.

Означаваме $U = \begin{pmatrix} u_{1,1} & u_{1,2}\\0 & u_{2,2} \end{pmatrix} = \begin{pmatrix} a_{1,1} & a_{1,2}\\ 0 & a_{2,1}^{(1)} \end{pmatrix}$ и $\hat{b} = \begin{pmatrix} \hat{b_1}\\ \hat{b_2} \end{pmatrix} = \begin{pmatrix} b_1\\ b_2^{(1)} \end{pmatrix}$.

Тъй като преобразуванията не променят решенията на началното уравнение, то $Ax = b \iff Ux = \hat{b}$

Обратен Ход

Решаваме $Ux = \hat{b}$.
$\begin{array}{cc} u_{1,1}x_1 + & u_{1,2}x_2 & = & \hat{b_1}\\ & u_{2,2}x_2 & = & \hat{b_2} \end{array} \iff \begin{array}{cc} x_ 1 & = & \frac{\hat{b_1} - u_{1,2}x_2}{u_{1,1}}\\ x_2 & = & \frac{\hat{b_2}}{u_{2,2}} \end{array}$

И $x = (x_1, x_2)^{T}$ е решение на $Ax = b$.

Алгоритъм 1 (псевдо код)

Прав ход

Обратен ход

Сложност на алгоритъма на Гаус (алгоритъм 1)

Под "сложност" на алгоритъм ще считаме порядъка на броя умножения, необходими при изпълнението на алгоритъма.
За правия ход Алгоритъм 1 е ясно, че порядъка на броя умножения зависи от стъпка 3. Там броят на умноженията е следния:

(1)
\begin{align} \sum_{k = 1}^{n - 1} (n - k)^2 = 1^2 + 2^2 + \dots + (n - 1)^2 = \frac{(n-1)n(2n - 1)}{6} = \frac{n^3}{3} + O(n^2) \end{align}

За обратния ход:

(2)
\begin{align} um_{k = 1}^{n-1} (n - k) = 1 + 2 + \dots + (n - 1) = \frac{(n-1)n}{2} = \frac{n^2}{2} + O(n) \end{align}

Свързани задачи /за Алгоритъм 1/

При положение, че сме решили системата $Ax = b$ възниква въпросът какво може да си помогне това за решаването на някои други задачи. След изпълнението на Алгоритъм 1 разполагаме с матриците $U$ и $L$

Намиране детерминанта на квадратна матрица

Тъй като матрицата $U$ е получена от марицата $A$ чрез операциите умножение на ред с число и прибавянето му към друг ред, е изпълнено, че
$\mathrm{det} A = \mathrm{det} U = u_{1,1} u_{2,2} \dots u_{n,n}$, тъй като $U$ е горнотриъгълна матрица.

Т.е необходими са $n$ допълнителни умножения, за да получим детерминантата на $A$.

Решаване на Ax = d

Разсъждавайки аналогично, ясно е, че $Ax = d \iff Ux = \hat{d}$, където $\hat{d}$ е получено след преобразуванията, на които е подложена матрицата $A$ за да се получи $U$.
Или, казано по друг начин, заместваме $b$ с $d$ в 4-тата стъпка и обратния ход на Алгоритъм 1 (не е необходимо да извършваме наново всичките операции).
Сложността в този случай ще е
$\frac{n^2}{2}$ за правия ход и $\frac{n^2}{2}$ за обратния ход, т.е общо $n^2$ допълнителни умножения.

Намиране на обратната матрица

Алгориъм 2 /метод на Гаус с избор на главен елемент/ (псевдо код)

Свързани задачи /за Алгоритъм 2/

Намиране детерминанта на квадратна матрица

Решаване на Ax = d

Намиране на обратната матрица

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License