Гаусс ысулы

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

Тарихы

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

Ысулдың тасуирламаһы

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

$\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) системалар эквивалентлы, йәғни уларҙың сығарылыштары күмәклектәре тап киләләр.

Эҙемтәләр: 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})$ тиклем ваҡытта ҡабатлап була икәнен иҫбат иткән.Ҡалып:Source-ref Ошонан, матрицаларҙы әйләндереүҙе һәм ҺАТС сығарыуҙы Гаусс ысулына ҡарағанда тәртип буйынса асимптотик шәберәк алгоритмдар менән тормошҡа ашырырға мөмкин булыуы килеп сыға. Шулай итеп, ҙур ҺАТС өсөн Гаусс ысулы тиҙлек буйынса оптималь түгел.

Шулай уҡ ҡарағыҙ

Һыҙыҡлы алгебра

• Гаусс-Жордан ысулы
• Крамер ысулы
• Һыҙыҡлы алгебраик тигеҙләмәләр системаһы
• Кронекер-Капелли теоремаһы
• Сығарыуҙарҙың фундаменталь системаһы
• Матрицаны элементар үҙгәртеүҙәр

Оптимизация ысулдары

• Гаусс ысулы (оптимизация)
• Координаталар иҫәбенсә төшөү ысулы (Гаусс—Зейдель)

Һанлы ысулдар

• Һыҙыҡлы тигеҙләмәләр системаһын сығарыуҙың Гаусс - Зейдель ысулы
• Якоби ысулы

Әҙәбиәт

• Гаусс ысулы — Математической энциклопедии
• Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.
• Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
• Волков Е. А. Численные методы. — М.: Физматлит, 2003.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
• Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Высшая математика для экономистов / Под ред. Н. Ш. Кремера. — 3-е изд. — М.: ЮНИТИ-ДАНА, 2007. — 479 с. — ISBN 5-238-00991-7.

Ҡалып:Методы решения СЛАУ