Розв язання систем лінійних рівнянь методом Гауса

Коломийський коледж комп’ютерних наук

Кафедра комп’ютерних

дисциплін

Реферат з дисципліни

Алгоритми мови та програмування

Розв’язання систем

лінійних

рівнянь методом Гауса

Виконав:

Студент групи 1-кн-2

Григорчук Володимир

Прийняв:

Яремчук Богдан Ярославович

Коломия 1999

Розв'язування систем лінійних рівнянь методом Гаусса.

а) Зведення системи лнийних рівнянь до ступінчастого вигляду.

Перейдемо до вивчення питания (про розв'язування систем ліній рівнянь. Нехай дано довільну систему т лінійних рівнянь з п невадомими.

a11x1 +a12x2 + ……+ a1nxn = b1,

a21x1 +a22x2 + ……+ a2nxn = b2,

………………………………..

am1x1 +am2x2 + …..+ amnxn = bm,

У цій системі, принаймні, один з коефіцієнтів ai1 (i = 1,2,..., m) відмінний від нуля, бо в противному paзi система (1) не була б системою з п невідомими. Якщо a11 = 0, а, наприклад, as1  0, то переставив­ши перше i s-те рівняння, дістанемо систему, еквівалентну системі (1). У першому piвнянні цієї системи коефіцієнт при невідомому x1 буде відмінний від нуля. Тому вважатимемо, що в системі (1) а11  0.

Випишемо розширену матрицю системи (1), відокремивши для зруч-ності вертикальною рискою стовпець вільних членів:

a11 a12 … a1n b1

a21 a22 … a2n b2

………………….

am1 am2 … amn bm

Застосовуючи елементарні перетворення рядків, зведемо матрицю (2) до ступінчатого вигляду. Дістанемо деяку ступінчасту матрицю.

Ā' = (a'ikb'i) розміру m x (n + 1). Позначимо символом S (Ā') систему лінійних рівнянь, розширеною матрицею якої е ступінчаста матриця

Ā' = (a'ikb'i).

Систему лінійних рівнянь, розширена матриця якої ступінчаста, також називають ступінчастою. Про ступінчасту систему говорять, що вона має ступінчастий вигляд. За теоремою 1.2 ступінчаста система S(Ā') еквівалентна системі(1).

Перетворення системи лінійних рівнянь в еквівалентну їй ступін­часту систему називають зведенням системи лінійних рівнянь до сту­пінчастого вигляду.

Отже, описаним вище способом кожну систему лінійних рівнянь можна звести до ступінчастого вигляду. Всюди далі, говорячи про перетворення системи лінійних рівнянь у ступінчасту систему, ми розумітимемо під цим перетворення лінійної системи в е к в і в а л е н т -

н у їй ступінчасту систему.

б) Розв'язування системи лінійних рівнянь. Система лінійних рівнянь (1) еквівалентна ступінчастій системі S(Ā'). Тому розв'я­зування системи (1) зводиться до розв'язування системи S(Ā'). При цьому можливі такі два випадки:

1. У розширеній матриці Ā' = (a'ib'i) системи S(Ā') є рядок, в якому першим відмінним від нуля елементом є його .останній елемент.

2. У матриці Ā' такого рядка немає. У першому випадку в системі S(Ā') міститься рівняння вигляду 0 • x1 + 0 • x2 + … + 0 • хn = b, b  0 (скорочено його записують 0 = b). Оскільки жодна система чисел (l1,l2, …, ln) не може задовольняти рівняння 0 = b (b  0), то система рівнянь S(Ā') несумісна.

Розглянемо другий випадок. Нехай ступінчаста матриця S(Ā') містить r ненульових рядків і перші ненульові елементи цих рядків знаходяться в стовпцях з номерами k1 = 1, k2,k3, …,kr. З означення ступінчастої матриці випливає, що 1 = k1 < k2 < … < kr < n.

Всі рівняння системи S(Ā'), які мають вигляд 0 • x1 + 0 • x2 + ... + 0 • хn = = 0, відкинемо. Дістанемо систему S(Ā''), еквівалент­ну системі S(Ā'). Невідомі х1, xk, xk2, ..., хkr, з яких починаються перше, друге, ..., r-те рівняння системи S(Ā''), назвемо головними, а всі інші (якщо вони є) —вільними.

Припустимо спочатку, що вільних невідомих немає. Тоді r = п, k1 = 1,

k2 = 2, k3 = 3, ..., kn = n, і система S(Ā'') має вигляд

a'11x1 + a'12x2 + … + a'1(n-1)xn-1 + a'1nxn = b'1,

a'22x2 + … + a'2(n-1)xn-1 + a'2nxn = b'2,

…………………………………………………………

a'(n-1)(n-1)xn-1 + a'(n-1)nxn = b'n-1,

a'nnx = b'n,

(a11  0, a22  0, …, ann  0).

З останнього рівняння системи (3) знаходимо ділком певне зна­чення невідомого xп. Підставивши його в передостаннє рівняння

системи (3), знайдемо відповідно одне значення невідомого xn-1. Тоді таким же способом послідовно дістанемо єдині значення невідомих xп-2, xп-з, …, х2, x1. Добуті таким чином значення невідомих x1, x2, …, xn cтановлять, очевидно, єдиний розв'язок системи (3). Отже, в розглядуваному випадку система S(Ā''), а також і система S(Ā'), сумісні й визначені. Припустимо тепер, що вільні невідомі є. Тоді система має вигляд

a'11x1 + … + a'1k2xk2 + … + a'1krxkr + … + a'1nxn = b'1,

a'2k2xk2 + … + a'2krxkr + … + a'2nxn = b'2,

…………………………………………..……

a'rkxkr + a'(n-1)nxn = b'n-1,

a'nnx = b'n,

(a11  0, a22  0, …, ann  0).

Позначимо символом б( суму всіх членів і'-го рівняння системи (4), що містять в}льні невідомі. Перенісши члени з вільними неві­домими в праві частини рівнянь, дістанемо систему

а[іх^ + а^хь, + ••• +а'іі,^=Ь[—і^,

аг^іг, — • • • + аих^ = Ьі — ^2, ,е\

а-г^х^ ==Ьг— І-,г, \

еквівалентну системі (4). У системі (5) коефіцієнти а\\, аг»,, азіг,, ... ...аг відмінні від нуля. Надамо вільним невідомим у системі (5) довіль­но вибраних числових значень: дістанемо систему вигляду (3). Роз­в'язавши її описаним вище способом, дістанемо єдині значення голов­них невідомих Хц х^, Хі:,, ..., х^. Сукупність знайдених значень го­ловних невідомих і вибраних нами значень Д вільних невідомих, очевидно, задовольняє кожне рівняння системи (5), тобтоє цілком визначеним розв'язком цієї системи, а отже, і еквівалентної їй систе­ми 5 (Л'), що відповідає вибраним значенням вільних невідомих. ^Оскільки значення вільних невідомих можна вибирати довільно, то множина різних наборів цих значень нескінченна. Тому множина розв'язків системи (5) і еквівалентної їй системи 5 (А') нескінченна. Таким чином, система 5 (Л') сумісна, але невизначена.

Зауважимо, що при всіх можливих виборах значень вільних невідо­мих за допомогою системи (5) щойно описаним способом буде знайдено всі розв'язки системи 5 (Л'). Іншими словами, кожен розв'язок системи 5 (Л') можна дістати описаним способом при відповідному виборі значень вільних кевідо?»ійх. -

Нехай (г'і, ід, ..., і'„) — довільно вибраний розв'язок системи 5 (Л'). Тоді він є розв'язком також і системи (5), еквівалентної системі 5 (Л').

Отже, ^, 4ц ^*.» ••• •к єтими єдиними'значеннями головних невідомих, які дістаємо за допомогою системи (5), якщо вільним невідомим на­дати значень, що є компонентами розв'язку (/і, /д, ..., 1^).

З викладеного вище випливає справедливість таких тверджень.

Теорема 1. Система лінійних рівнянь сумісна тоді і тільки то­ді, коли вона перетворюється'на ступінчасту систему, в якій немає рівнянь вигляду 0 == ^' (Ь Ф 0).

Теорема 2. Сумісна система лінійних рівнянь є визначеною тоді і тільки тоді, коли в ступінчастій системі, в яку вона перетворюєть­ся, число рівнянь г дорівнює числу невідомих п.

З цих теорем випливають такі наслідки.

Наслідок 1. Система п лінійних рівнянь з п невідомими е визна­ченою тоді і тільки тоді, коли вона перетворюється на ступінчасту систему, в якій а\\ =^0, 0:22 ^ 0, ..., Опп ^ 0.

•< Нехай дану систему п лінійних рівнянь з п невідомими перетво­рено на ступінчасту систему, в якій ац Ф 0, а^з Ф 0, ..., а'пп Ф 0. У такій ступінчастій системі, очевидно, немає рівнянь вигляду 0 == = Ь' (Ь' -ф. 0) і число рівнянь дорівнює числу невідомих. Тому, за теоремою 1, дана система лінійних рівнянь сумісна, а за теоремою 2, вона визначена. Навпаки, якщо дана система п лінійних рівнянь з п невідомими визначена, то за теоремою 1, у ступінчастій системі, на яку вона перетворюється, немає рівнянь вигляду 0 = Ь', (Ь' ^= 0) і, за теоремою 2, число рівнянь у ступінчастій системіїдорівнює п. Отже, в ступінчастій системі а\\ ^ О, агч ^ 0, ..., а'пп Ф 0. >•

Наслідок 2. Сумісна система т лінійних рівнянь з п невідомими Їіри т <п є невизначеною.

•^ Справді, сумісна система т лінійних рівнянь з п невідомими при т •< п перетворюється на .ступінчасту систему, в якій число рівняньг менше, ніж число невідомих п, і тому, за теоремою 2, вона є невизна­ченою. ^

Лінійне рівняння -, . і—.йй а^+а,х,+ ... +а^==6 ^: °0'

називається однорідним, якщо його вільний член Ь дорівнює нулю. Система лінійних рівнянь називається однорідною лінійною системою або системою лінійних однорідних рівнянь, якщо всі її рівняння однорідні, тобто якщо всі її вільні члени дорівнюють нулю.

Застосуємо одержані вище результати до однорідної лінійної системи. Нехай дано довільну систему лінійних однорідних рівнянь

йц^і + аі2^2 + • • • + ащХп =0, 021-^1 + 022^2 4- •-• • + а2пХп = 0, ^

Ог.Л^ -т- ОтіХг — • • • + СІтпХп =-- 0. ,

Ця система сумісна, оскільки вона має нульовий розв'язок (О, О, ,.., 0).-Це узгоджується й з доведеною вище теоремою 1. Справді, оскільки всі вільні члени системи (6) дорівнюють нулю, то вона пе­ретворюється на ступінчасту систему, в якій немає рівнянь вигляду 0=о (&^0). ' - '

Якщо система (6) перетворюється на ступінчасту ,-истему,. в якій число рівнянь /• дорівнює числу невідомих п, то за теоремою2, вона має єдиний розв'язок — нульовий. Якщо ж система (6) перетворю­ється на ступінчасту систему, в якій число рівнянь ,'• у.енше, ніж число невідомих п, то множина її розв'язків нескінченна, і, отже, вона має ненульові розв'язки, тобто розв'язки, в яких деякі (а можливо й усі) компоненти відмінні від нуля.

Множина ненульових розв'язків буде нескінченною.

Теорема 3. Система лінійних однорідних рівнянь, в якій число , рівнянь менше, ніж число невідомих, має ненульові розв'язки. •

За наслідком 2, така система невизначена, тобто має нескінченну множину розв'язків, серед яких є і розв'язки, відмінні від нульового.

Приклади. 1. Розв'язати систему

х,+ х^+2х^-=- 1,

2жі+4А-2+5.їд=—8, ——

«Ї+ЗX2-^5А:3=—7. ЗА-і4-7-«-2+9^3=—15-

Р о з в'я за н н я. Зведемо розширену матрицю цієї системи /І 1 2-1 \ | 2 4 5 —8 | | 1 3 5 —7 | \3 7 9 —15/

до ступінчастого вигляду. Перший рядок, помножений відповідно на 2, 1, 3, відні­мемо від другого, третього і четвертого рядків, дістанемо

/І 1 2 1\ 1021—61 І 0 2 3—6 1

\0 4 3 —12/

Другий рядок, помножений відповідно на 1, 2, віднімемо від третього і чет­вертого рядків, матимемо

/112-^

-•--—•—•------— [02 1 —6| -...-_^і1_ : ,

' ; ' ґ " - :•' /<:; '"^ "1002 0 |" • \- • .•^-.-і-.- . -.-

\0 0 1 О/

Третій рядок, помножений на 1/,, віднімемо від четвертого рядка, дістанемо

/1;1 2-1\ ; , 1 0 2 1 —6 1

і 0 0 2 01 .

д—»-— \о о о- • о/ • . .

/ Звідси випливає, що задана система ;;ікіі1них різн-таь перетворюється (після ц вилучення рівняння вигляду 0 == 0) на ступі:-:часту систему

- ^І-г ^3 + 2А'я =—1,1

2х,- х^-6,}

-\: _ 2^- 0. ] Ця система, а отже, і задана система мають єдиний розв'язок (2, —3, 0).

І, , •

2. Розв'язати снетегу " "' '

: г 2хі+3^+5^-^Х^ 5, • • : Зл:і+4^+2хз+&»;4==—2, Хї+2.^+8хз- ^= 8, 7^+°-ї2+ ^+8Х4= 0. Розв'язання. Зведемо розширену матрицю до ступінчастого вигляду

(235 2 5\ /128 —1 8\ 342 3—2І(342 3 — 2 1 1 2 8 —1 8 І ""І 2 3 5 2 5 } ^791 8 О/ \7 9 1 80/

(1 2 8—1 8\ /1 2 81 8\ 0—2—22 6 —2б| |0 —2 —22 6 — 26 \ "^ 0 —1—11 4—11 і|о О 01 2}' 0 —5 —55 15 —56/ \0 О 00 9/

Отже, задана система лінійних рівнянь перетворюється на ступінчасту систему, в якій міститься рівняння 0=9, тому вона несумісна.

3. Розв'язати систему

*і+2^+3<з+ 4^+ 5х,=0, \ 2л:і+3^+4^+ 5г,+ ^,=0, | 3^+4л;24-5хз+ ^4+^=0,

•»:1+3л:г4-5.»;з+12^4+ 9^=0, ЗХі+бх^-{-9х,+17х^+10х^=0.

Розв'язання. Розширену матрицю цієї системи зведемо до ступінчастого вигляду

~1 2 3 4 5 0~ '"1 2 3 4 5 0~ 234510 0—1—2—3—90 345 1 20 ->• 0—2—^—11—130-»-1 3 5 12 9 0 0128 40

_3 69 17 10 0 00 о 5 —50 ''

~1 23 45 0~ "'1 2 3 ' 4 "5 0'"' ' -

0—1—2—3—90 012 390 ^ 0 0 0 —5 5 0 ->- 000—1 1 0 , -1-

0 0 0 5—50 000 000 _0 О 05—50 000 000

Отже, задана система лінійних однорідних рівнянь перетворюється на ступін­часту

^+2^-3^+4^+5^=0, ) ," ^.+2^з+3^+9^=0, - ^

— *-4+ •<'5=0. )

Вважати-мемо невідомі х^, х,., х^ основними, а невідоміХу, х^ — вільними. Нехай Хз '= 'х, х, = р. ?- .останньої системи знаходимо х^ == v. -+• 15р, х, == —2а— 12р, 4= Р.^ , ., ^ , : ,•,,

Викладений вище метод розв'язування систем лінійних рівнянь називається методом Гаусса, або методом послідовного виключення невідомих. Цей метод досить зручний для розв'язування вручну систем лінійних рівнянь з невеликою кількістю невідомих. Він з ус­піхом може бути використаний також для розв'язування лінійних систем на ЕОМ, проте часто для цього ефективнішими виявляються інші методи, наприклад, ітераційні (послідовних наближень). Так, зокрема, буває тоді, коли коефіцієнти і вільні члени системи є дійсні числа, знайдені вимірюванням деяких фізичних величин, і, отже, відомі наближено, з певним ступенем точності, тоді й розв'язки систе­ми, природно, знаходимо також з певним ступенем точності.

Однак метод Гаусса поряд з простотою і ефективністю має істотний недолік: він не дає змоги сформулювати в термінах коефіцієнтів і вільних членів лінійної системи умови її сумісності та визначеності, а також знайти формули, які б виражали компоненти розв'язку су­місної системи через її коефіцієнти і вільні члени, тобто давали змогу відразу знаходити розв'язки системи. Проте при розгляді різних теоретичних питань необхідно мати саме такі формулювання і фор­мули. Тому теорію систем лінійних рівнянь доводиться розвивати іншими методами, — на основі теорії визначників.

Список використаної літератури:

1) Бойков М.С. "Лабиринты математики", Москва, 1984р.

2) Шапов С.К. "Математика, теорія і практика", Київ, 1989р.

3) Белов К.М. "Вища математика", Київ, 1978р.

4) Оллер О.П. "В мире математики", Москва, 1983р.