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

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

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

дисциплін

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

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

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

лінійних

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

Виконав:

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

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

Прийняв:

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

Коломия 1999

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

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

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

a₁₁x₁ +a₁₂x₂ + ……+ a_1nx_n = b₁,

a₂₁x₁ +a₂₂x₂ + ……+ a_2nx_n = b₂,

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

a_m1x₁ +a_m2x₂ + …..+ a_mnx_n = b_m,

У цій системі, принаймні, один з коефіцієнтів a_i1 (i = 1,2,...,m) відмінний від нуля, бо в противному paзi система (1) не була б системою з п невідомими. Якщо a₁₁ = 0, а, наприклад, a_s1¹ 0, то переставивши перше is-те рівняння, дістанемо систему, еквівалентну системі (1). У першому piвнянні цієї системи коефіцієнт при невідомому x₁ буде відмінний від нуля. Тому вважатимемо, що в системі (1) а¹¹¹ 0.

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

a₁₁ a₁₂ … a_1n b₁

a₂₁ a₂₂ … a_2n b₂

………………….

a_m1 a_m2 … a_mn b_m

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

Ā' = (a^'_ik|b^'_i) розміру mx (n + 1). Позначимо символом S(Ā') систему лінійних рівнянь, розширеною матрицею якої е ступінчаста матриця

Ā' = (a^'_ik|b^'_i).

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

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

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

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

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

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

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

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

Всі рівняння системи S(Ā'), які мають вигляд 0 •x₁ + 0 •x₂ + ... + 0 •х_n = = 0, відкинемо. Дістанемосистему S(Ā''), еквівалентну системі S(Ā'). Невідомі х₁, x_k, x_k2, ...,х_kr, з яких починаються перше, друге, ..., r-те рівняння системи S(Ā''), назвемо головними, а всі інші (якщо вони є) —вільними.

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

k₂ = 2,k₃ = 3, ...,k_n =n, і система S(Ā'') має вигляд

a'₁₁x₁ + a'₁₂x₂ + … + a'_1(n-1)x_n-1 + a'_1nx_n = b'₁,

a'₂₂x₂ + … + a'_2(n-1)x_n-1 + a'_2nx_n = b'₂,

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

a'_(n-1)(n-1)x_n-1 + a'_(n-1)nx_n = b'_n-1,

a'_nnx = b'_n,

(a₁₁¹ 0, a₂₂¹ 0, …, a_nn¹ 0).

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

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

a'₁₁x₁ + … + a'_1k2x_k2 + … + a'_1krx_kr + … + a'_1nx_n = b'₁,

a'_2k2x_k2 + … + a'_2krx_kr + … + a'_2nx_n = b'₂,

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

a'_rkx_kr + a'_(n-1)nx_n = b'_n-1,

a'_nnx = b'_n,

(a₁₁¹ 0, a₂₂¹ 0, …, a_nn¹ 0).

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

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

аг^іг, — • • • +аих^ =Ьі — ^2, ,е&bsol;

а-г^х^ ==Ьг— І-,г, &bsol;

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

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

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

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

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

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

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

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

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

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

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

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