Гаусс ысулы

**Гаусс ысулы** — һыҙыҡлы алгебраик тигеҙләмәләр системаһын (ҺАТС) сығарыуҙың классик ысулы. Немец математигы Карл Фридрих Гаусс хөрмәтенә аталған. Был үҙгәреүсәндәрҙе эҙмә-эҙ бөтөрөү ысулы, элементар үҙгәртеүҙәр ярҙамында тигеҙләмәләр системаһы өсмөйөшлө күренештәге тиң көслө системаға килтерелә, унан эҙмә-эҙ, һуңғыһынан башлап (номеры буйынса), системаның бөтә үҙгәреүсәндәре табыла.

## Тарихы
Хәҙерге ваҡытта был ысул бөтә ерҙә лә Гаусс ысулы тип аталһа ла, ул К. Ф. Гауссҡа тиклем билдәле була. Был ысулдың беренсе билдәле булған тасуирланышы — «Математика в девяти книгах» исемле ҡытай трактатында.

## Ысулдың тасуирламаһы
Башта бирелгән система ошондай күренештә булһын, ти:

: \left\{\begin{array}{lcr}
a_{11}x_1+\ldots+a_{1n}x_n &=& b_1 \\
\ldots & & \\
a_{m1}x_1+\ldots+a_{mn}x_n &=& b_m \\
\end{array}\right.

Уны матрицалы күренештә яҙырға мөмкин:
: Ax = b,
бында
: A=\left( \begin{array}{ccc}
a_{11} & \ldots & a_{1n}\\
\ldots &  &  \\
a_{m1} & \ldots & a_{mn}
\end{array}\right),\quad x = \left( \begin{array}{c}x_1 \\ \vdots \\ x_n \end{array} \right), \quad b = \left( \begin{array}{c}b_1 \\ \vdots \\ b_m \end{array} \right).\quad (1)

A матрицаһы системаның төп матрицаһы тип атала, b — ирекле быуындар бағанаһы.

Ул саҡта, юлдар өҫтөндә элементар үҙгәртеүҙәр үҙсәнлегенә ярашлы, был системаның төп матрицаһын баҫҡыслы күренешкә килтерергә мөмкин (шул уҡ үҙгәртеүҙәрҙе ирекле быуындар бағанаһына ҡулланырға кәрәк):

: \left\{\begin{array}{rcl}
\alpha_{1j_1}x_{j_1}+\alpha_{1j_2}x_{j_2}+\ldots+\alpha_{1j_r}x_{j_r}+\ldots+\alpha_{1j_n}x_{j_n} &=& \beta_1 \\
                     \alpha_{2j_2}x_{j_2}+\ldots+\alpha_{2j_r}x_{j_r}+\ldots+\alpha_{2j_n}x_{j_n} &=& \beta_2 \\
                                                                                               &\ldots& \\
                                                 \alpha_{rj_r}x_{j_r}+\ldots+\alpha_{rj_n}x_{j_n} &=& \beta_r \\
                                                                                                0 &=& \beta_{r+1} \\
                                                                                               &\ldots& \\
                                                                                                0 &=& \beta_m
\end{array}\right.,
бында \alpha_{1j_1},\ldots,\alpha_{rj_r}\neq 0.

Был ваҡытта, төп матрицаның базислы миноры (нуль булмаған иң ҙур тәртиптәге минор) өҫкө һул мөйөштә урынлашҡан тип иҫәпләйбеҙ, йәғни уға x_{j_1},\ldots,x_{j_r} үҙгәреүсәндәренең коэффициенттары ғына инә.

Ул саҡта x_{j_1},\ldots,x_{j_r} үҙгәреүсәндәре *төп үҙгәреүсәндәр* тип аталалар. Бөтә ҡалғандары *ирекле* тип аталалар.

Әгәр бер генә һан булһа ла \beta_i\neq 0 булһа, бында i > r, ул саҡта бирелгән система уртаҡ түгел, йәғни уның бер генә лә сығарылышы юҡ.
Теләһә ниндәй i > r өсөн \beta_i = 0 булһын.

Ирекле үҙгәреүсәндәрҙе тигеҙлек тамғаһының икенсе яғына сығарабыҙ һәм системаның һәр тигеҙләмәһен иң һулдағы x (\alpha_{ij_i},\, i=1,\ldots,r, бында i — юл номеры) алдындағы үҙенең коэффициентына бүләбеҙ:

: \left\{\begin{array}{rcc}
x_{j_1}+\widehat{\alpha}_{1j_2}x_{j_2}+\ldots+\widehat{\alpha}_{1j_r}x_{j_r}&=& \widehat{\beta}_1-\widehat{\alpha}_{1j_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{1j_n}x_{j_n} \\
                     x_{j_2}+\ldots+\widehat{\alpha}_{2j_r}x_{j_r}&=& \widehat{\beta}_2-\widehat{\alpha}_{2j_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{2j_n}x_{j_n} \\
                                                           &\ldots& \\
                                                       x_{j_r}&=& \widehat{\beta}_r-\widehat{\alpha}_{rj_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{rj_n}x_{j_n} \\
\end{array}\right., \qquad \widehat{\beta}_i=\frac{\beta_i}{\alpha_{ij_i}},\quad \widehat{\alpha}_{ij_k}=\frac{\alpha_{ij_k}}{\alpha_{ij_i}}\quad (2), 
бында i=1,\ldots,r,\quad k=i+1,\ldots,n.

Әгәр (2) системаның ирекле үҙгәреүсәндәренә бөтә мөмкин булған ҡиммәттәрҙе биреп һәм яңы системаны аҫтан өҫкә төп үҙгәреүсәндәргә ҡарата сығарһаҡ (йәғни аҫтағы тигеҙләмәнән өҫкөһөнә), ул саҡта беҙ был ҺАТС-тың бөтә сығарылыштарын табырбыҙ. Был система баштағы система (1) өҫтөндә элементар үҙгәртеүҙәр ярҙамында алынғанлыҡтан, элементар үҙгәртеүҙәрҙә эквивалентлыҡ тураһында теорема буйынса (1) һәм (2) системалар эквивалентлы, йәғни уларҙың сығарылыштары күмәклектәре тап киләләр.

### Уртаҡлыҡ критерийы
Бөтә i > r өсөн юғарыла телгә алынған \beta_i= 0 шарты уртаҡлыҡтың кәрәкле һәм етерлек шарты сифатында әйтеп бирелергә мөмкин:

Иҫкә төшөрәбеҙ, уртаҡ системаның рангы тип уның төп матрицаһының рангы атала (йәки киңәйтелгән матрицаһының, сөнки улар тигеҙ).

### Алгоритм
Блок схема һүрәттә бирелгән. Был һүрәт программаны С/С++ телендә, бында a — киңәйтелгән матрица, яҙыуға яраҡлаштырылған, уның һуңғы бағанаһы — ирекле быуындар бағанаһы. Юлдар һаны — n. 

#### Тасуирлау
ҺАТС сығарыу өсөн Гаусс алгоритмы ике этапҡа бүленә.
* Беренсе этапта тура йөрөш тормошҡа ашырыла, юлдар өҫтөндә элементар үҙгәртеүҙәр юлы менән системаны һикәлтәле йәки өсмөйөшлө формаға килтерәләр, йәки система уртаҡ түгел икәнен асыҡлайҙар. Атап әйткәндә, матрицаның беренсе бағанаһының элементтары араһында нулдән айырмалыһын һайлап алалар, уны юлдарҙы алмаштырып ҡуйып өҫтәге иң ситтәге урынға күсерәләр һәм алмаштырып ҡуйғандан һуң килеп сыҡҡан беренсе юлды, һәр юлдың беренсе элементының беренсе юлдың беренсе элементына сағыштырмаһына тигеҙ булған дәүмәлгә ҡабатлап, ҡалған юлдарҙан алалар, шуның менән уның аҫтындағы бағананы нулгә әйләндерәләр. Был үҙгәртеү башҡарылғандан һуң, беренсе юлды һәм беренсе бағананы күңелдән генә сыйып ташлайҙар һәм шундай үҙгәртеүҙәрҙе нуль үлсәмле матрица ҡалғанға тиклем дауам итәләр. Әгәр итерацияларҙың ҡайһыһындалыр беренсе бағананың элементтары араһында нулдән айырмалы элемент булмаһа, артабанғы бағанаға күсәләр һәм шундай уҡ операцияны башҡаралар.
* Икенсе этапта кире йөрөш тормошҡа ашырыла, уның асылы, бөтә килеп сыҡҡан базислы үҙгәреүсәндәрҙе базислы булмағандар аша күрһәтеүҙән һәм сығарылыштарҙың фундаменталь системаһын төҙөүҙән, йәки, әгәр бөтә үҙгәреүсәндәр ҙә базислы булһалар, һыҙыҡлы тигеҙләмәләр системаһының берҙән бер сығарылышын һанлы күренештә күрһәтеүҙән ғибәрәт. Был процедура һуңғы тигеҙләмәнән башлана, унан ярашлы базислы үҙгәреүсәнде (ә ул унда берәү генә) табалар һәм алдағы тигеҙләмәгә ҡуялар, һәм шулай артабан, «һикәлтәләр» буйлап өҫкә күтәрелеп дауам итәләр. Һәр юлға теүәл бер базислы үҙгәреүсән ярашлы, шуға күрә һәр аҙымда, һуңғыһынан башҡа (иң өҫтәге), хәл һуңғы юл осрағын теүәл ҡабатлай.
Гаусс ысулы арифметик операцияларҙың O(n^{3}) булыуын талап итә.

Был ысул таяна:

#### Иң ябай осраҡ
Иң ябай осраҡта алгоритм ошолай күренә: 
: 
\left\{\begin{array}{lcc} 
a_{11} \cdot x_1 + a_{12} \cdot x_2 + \ldots + a_{1n} \cdot x_n & = b_1 & (1) \\ 
a_{21} \cdot x_1 + a_{22} \cdot x_2 + \ldots + a_{2n} \cdot x_n & = b_2 & (2) \\ 
\ldots  & & \\
a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + \ldots + a_{mn} \cdot x_n & = b_m & (m) 
\end{array}\right.


* Тура йөрөш:
: \begin{array}{ccc}
(2)\to (2)-(1) \cdot ( \frac {a_{21}}{a_{11}}) &:& a_{22}^{\prime} \cdot x_2 + a_{23}^{\prime} \cdot x_3 + \ldots + a_{2n}^{\prime} \cdot x_n = b_2^{\prime} \\
(3)\to (3)-(1) \cdot ( \frac {a_{31}}{a_{11}}) &:& a_{32}^{\prime} \cdot x_2 + a_{33}^{\prime} \cdot x_3 + \ldots + a_{3n}^{\prime} \cdot x_n = b_3^{\prime} \\
\ldots & & \\
(m)\to (m)-(1) \cdot ( \frac {a_{m1}}{a_{11}}) &:& a_{m2}^{\prime} \cdot x_2 + a_{m3}^{\prime} \cdot x_3 + \ldots + a_{mn}^{\prime} \cdot x_n = b_n^{\prime} \\
(3)\to (3)-(2) \cdot ( \frac {a_{32}^{\prime}}{a_{22}^{\prime}}) &:& a_{33}^{\prime\prime} \cdot x_3 + \ldots + a_{3n}^{\prime\prime} \cdot x_n = b_3^{\prime\prime} \\
\ldots & & \\
(m)\to (m)-(m-1) \cdot ( \frac {a_{m,n-1}^{(m-2)}}{a_{m-1,n-1}^{(m-2)}}) &:& a_{mm}^{(m-1)} \cdot x_m + \ldots + a_{mn}^{(m-1)} \cdot x_n = b_m^{(m-1)}
\end{array}

* Кире йөрөш. Һуңғы нулдән айырмалы тигеҙләмәнән базислы үҙгәреүсәнде базислы булмағандар аша күрһәтәбеҙ һәм алдағы тигеҙләмәгә ҡуябыҙ. Был процедураны бөтә базислы үҙгәреүсәндәр өсөн ҡабатлап, фундаменталь сығарылышты табабыҙ.

### МИҫал

Нисек Гаусс ысулы менән системаны сығарырға мөмкин икәнен күрһәтәбеҙ:
: \left\{\begin{array}{ccc}2x + y - z &=& 8 \\
-3x - y + 2z &=& -11 \\
-2x + y + 2z &=& -3 \end{array}\right.

Икенсе һәм өсөнсө юлдарҙа x-тың коэффициенттарын нулгә әйләндерәбеҙ. Бының өсөн уларға, ярашлы рәүештә \textstyle\frac{3}{2} һәм 1-гә ҡабатланған беренсе юлды ҡушабыҙ:
: \left\{\begin{array}{rcc}
2x + y - z &=& 8 \\
\frac{1}{2}y + \frac{1}{2}z &=& 1 \\
2y + z &=& 5 \end{array}\right.

Хәҙер өсөнсө юлда, унан 4-кә ҡабатланған икенсе юлды алып, y-тең коэффициентын нулгә әйләндерәбеҙ:
: \left\{\begin{array}{rcc}
2x + y - z &=& 8 \\
\frac{1}{2} y + \frac{1}{2} z &=& 1 \\
-z &=& 1 \\ \end{array}\right.

Һөҙөмтәлә беҙ бирелгән системаны өсмөйөшлө күренешкә килтерҙек, шуның менән алгоритмдың беренсе этабын тамамланыҡ.

Икенсе этапта килеп сыҡҡан тигеҙләмәләрҙе кире тәртиптә сығарабыҙ. Табабыҙ: 
: z = -1 өсөнсөнән;
: y = 3 табылған z-те ҡуйып, икенсе тигеҙләмәнән
: x = 2 табылған z һәм y-те ҡуйып, беренсе тигеҙләмәнән.

Шулай итеп баштағы система сығарылды.

Уртаҡ системала тигеҙләмәр һаны билдәһеҙҙәр һанынан кәм булған осраҡта, яуап сығарылыштарҙың фундаменталь системаһы күренешендә яҙыла.

## Ҡулланылышы һәм модификациялары
ҺАТС аналитик юл менән сығарыуҙан башҡа, Гаусс ысулы ҡулланыла:
* бирелгән матрицаға кире матрицаны табыу өсөн (матрицаға уңдан бирелгән матрица кеүек үк үлсәмдәге берәмек матрица өҫтәп яҙыла: [A|E], унан һуң A Гаусс—Жордан ысулы менән берәмек матрица күренешенә килтерелә; һөҙөмтәлә тәүҙәге берәмек матрица урынына уңда бирелгән матрицаға кире матрица: [E|A^{-1}] хасил була);
* матрица рангын асыҡлау өсөн (Кронекер-Капелли теоремаһынан эҙемтәгә ярашлы матрица рангы уның төп үҙгәреүсәндәре һанына тигеҙ);
* техник ҡушымталарҙа ҺАТС һанлы сығарыу өсөн (иҫәпләүҙәрҙең хатаһын кәметеү өсөн, төп элементты айырып алып, Гаусс ысулы ҡулланыла, уның асылы шунан ғибәрәт, һәр аҙымда төп үҙгәреүсән сифатында, сираттағы юлдарҙы һәм бағаналарҙы һыҙып ташлағандан һуң, тороп ҡалғандар араһында ҡайһыһының алдында модуле буйынса максималь булған коэффициент тора, шул үҙгәреүсән һайлана).

## Ысулдың яҡшы яҡтары
* Сикле үлсәмле матрицалар өсөн, башҡа ысулдар менән сағыштырғанда, әҙерәк хеҙмәт талап итә.
* Система уртаҡмы әллә юҡмы икәнен асыҡларға, һәм әгәр уртаҡ булһа, уның сығарылышын табырға мөмкинлек бирә.
* Максималь һандағы һыҙыҡлы бәйһеҙ тигеҙләмәләр — системаның матрица рангын табырға мөмкинлек бирә .

## Гаусс ысулының тотороҡлолоғо
Насар бәйләнгән коэффициенттар матрицалары өсөн Гаусс ысулы иҫәпләүгә тотороҡһоҙ. Мәҫәлән, Гильберт матрицаһы өсөн ысул был матрицаларҙың ҙур булмаған үлсәмдәре өсөн дә ҙур хаталарға килтерә. Иҫәпләү хатаһын тик шартлы тотороҡло булған, төп элементты айырып алып Гаусс ысулын ҡулланыу ярҙамында ғына кәметергә мөмкин . Гаусс ысулын киң ҡулланыу практикала насар бәйләнгән матрицаларҙың һирәк осрауы менән бәйле.

## Гаусс ысулының ҡулай булмауы
1969 йылда Штрассен, ҙур матрицаларҙы O(n^{\log_2{7}}) = O(n^{2{,}81}) тиклем ваҡытта ҡабатлап була икәнен иҫбат иткән. Ошонан, матрицаларҙы әйләндереүҙе һәм ҺАТС сығарыуҙы Гаусс ысулына ҡарағанда тәртип буйынса асимптотик шәберәк алгоритмдар менән тормошҡа ашырырға мөмкин булыуы килеп сыға. Шулай итеп, ҙур ҺАТС өсөн Гаусс ысулы тиҙлек буйынса оптималь түгел.

## Шулай уҡ ҡарағыҙ
Һыҙыҡлы алгебра
* Гаусс-Жордан ысулы
* Крамер ысулы
* Һыҙыҡлы алгебраик тигеҙләмәләр системаһы
* Кронекер-Капелли теоремаһы
* Сығарыуҙарҙың фундаменталь системаһы
* Матрицаны элементар үҙгәртеүҙәр
Оптимизация ысулдары
* Гаусс ысулы (оптимизация)
* Координаталар иҫәбенсә төшөү ысулы (Гаусс—Зейдель)
Һанлы ысулдар
* Һыҙыҡлы тигеҙләмәләр системаһын сығарыуҙың Гаусс - Зейдель ысулы
* Якоби ысулы

## Иҫкәрмәләр


## Әҙәбиәт

* 
* 
* 
* 
* 
* 
*