Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Метод Гаусса



План:


Введення

Метод Гаусса [1] - класичний метод рішення системи лінійних алгебраїчних рівнянь (СЛАР). Це метод послідовного виключення змінних, коли за допомогою елементарних перетворень система рівнянь приводиться до равносильной системі ступеневої (або трикутного) виду, з якого послідовно, починаючи з останніх (за номером) змінних, знаходяться всі інші змінні [2].


1. Історія

Хоча в даний час даний метод повсюдно називається методом Гаусса, він був відомий і до К. Ф. Гаусса. Перше відоме опис даного методу - у китайському трактаті " Математика в дев'яти книгах ", складеному між I ст. до н.е. і II ст.н.е..

2. Опис методу

Нехай вихідна система виглядає наступним чином

\ 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. \ iff Ax = b, \ quad 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., \ qquad \ alpha_ {1j_1}, \ ldots, \ alpha_ {rj_r} \ neq 0.

При цьому будемо вважати, що базисний мінор (ненульовий мінор максимального порядку) основної матриці знаходиться у верхньому лівому кутку, тобто в нього входять лише коефіцієнти при змінних x_ {j_1}, \ ldots, x_ {j_r} \! [3].

Тоді змінні x_ {j_1}, \ ldots, x_ {j_r} \! називаються головними змінними. Всі інші називаються вільними.

Якщо хоча б одне число \ Beta_i \ neq 0 \! , Де i> r , То розглянута система несовместна.

Нехай \ Beta_i = 0 \! для будь-яких i> r .

Перенесемо вільні змінні за знаки рівностей і поділимо кожне з рівнянь системи на свій коефіцієнт при самому лівому 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) еквівалентні, тобто безлічі їх рішень збігаються.

Logo arte.jpg Наслідки:
1: Якщо у спільній системі всі змінні головні, то така система є визначеною.

2: Якщо кількість змінних в системі перевершує число рівнянь, то така система є або невизначеною, або несумісною.


2.1. Умова спільності

Згадане вище умова \ Beta_i = 0 \! для всіх i> r \! може бути сформульовано в якості необхідного і достатнього умови спільності:

Нагадаємо, що рангом спільної системи називається ранг її основної матриці (або розширеної, так як вони рівні).

Logo arte.jpg Теорема Кронекера-Капеллі.
Система сумісна тоді і тільки тоді, коли ранг її основної матриці дорівнює рангу її розширеної матриці.

Наслідки:

  • Кількість головних змінних дорівнює рангу системи і не залежить від її рішення.
  • Якщо ранг спільної системи дорівнює числу змінних даної системи, то вона визначена.

2.2. Алгоритм

2.2.1. Опис

Алгоритм рішення СЛАУ методом Гауса підрозділяється на два етапи.

  • На першому етапі здійснюється так званий прямий хід, коли шляхом елементарних перетворень над рядками систему призводять до ступінчастою або трикутній формі, або встановлюють, що система несумісна. А саме, серед елементів першого стовпця матриці вибирають ненульовий, переміщують його на крайнє верхнє положення перестановкою рядків і віднімають вийшла після перестановки перший рядок з решти рядків, домножити її на величину, рівну відношенню першого елемента кожної з цих рядків до першого елементу першого рядка, обнуляючи тим самим стовпець під ним. Після того, як зазначені перетворення були здійснені, перший рядок і перший стовпець подумки викреслюють і продовжують поки не залишиться матриця нульового розміру. Якщо на якійсь із ітерацій серед елементів першого стовпця не знайшовся ненульовий, то переходять до наступного колонку і проробляють аналогічну операцію.
  • На другому етапі здійснюється так званий зворотний хід, суть якого полягає в тому, щоб висловити все отримані базисні змінні через небазисних і побудувати фундаментальну систему рішень, або, якщо всі змінні є базисними, то виразити в чисельному вигляді єдине рішення системи лінійних рівнянь. Ця процедура починається з останнього рівняння, з якого висловлюють відповідну базисну змінну (а вона там всього одна) і підставляють в попередні рівняння, і так далі, піднімаючись по "сходинках" наверх. Кожному рядку відповідає рівно одна базисна змінна, тому на кожному кроці, крім останнього (самого верхнього), ситуація в точності повторює випадок останнього рядка.

Метод Гаусса вимагає порядку O (n 3) дій.

Цей метод спирається на:

Logo arte.jpg Теорема (про приведення матриць до східчастого виду).
Будь-яку матрицю шляхом елементарних перетворень тільки над рядками можна привести до східчастого вигляду.

2.2.2. Найпростіший випадок

У простому випадку алгоритм виглядає так:
\ 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}

  • Зворотний хід. З останнього ненульового рівняння виражаємо базисну змінну через небазисних і підставляємо в попередні рівняння. Повторюючи цю процедуру для всіх базисних змінних, отримуємо фундаментальне рішення.

2.3. Приклад

Покажемо, як методом Гаусса можна вирішити наступну систему:

\ 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.

Тепер обнулив коефіцієнт при y \! у третьому рядку, вирахувавши з неї другий рядок, помножену на 4 \! :

\ 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 \! .

Таким чином вихідна система вирішена.

У випадку, якщо число рівнянь у спільній системі вийшло менше числа невідомих, то тоді відповідь буде записуватися у вигляді фундаментальної системи рішень.


3. Застосування і модифікації

Крім аналітичного рішення СЛАУ, метод Гаусса також застосовується для:

  • знаходження матриці, оберненої до даної (до матриці справа приписується одинична такого ж розміру, що і початкова: [A | E] \! , Після чого A \! приводиться до виду одиничної матриці методом Гаусса-Жордана; в результаті на місці початкової одиничної матриці справа виявляється зворотна до вихідної матриця: [E | A ^ {-1}] \! );
  • визначення рангу матриці (згідно слідству з теореми Кронекера-Капеллі ранг матриці дорівнює числу її головних змінних);
  • чисельного рішення СЛАР в обчислювальній техніці (зважаючи похибки обчислень використовується Метод Гаусса з виділенням головного елемента, суть якого полягає в тому, щоб на кожному кроці в якості головної змінної вибирати ту, при якій серед залишилися після викреслювання чергових рядків і стовпців варто максимальний по модулю коефіцієнт ).

4. Переваги методу

  • Менш трудомісткий в порівнянні з іншими методами.
  • Дозволяє однозначно встановити, совместна система чи ні, і якщо совместна, знайти її рішення.
  • Дозволяє знайти максимальне число лінійно незалежних рівнянь - ранг матриці системи [4].

Примітки

  1. Гаусс, Карл Фрідріх ( 1777 - 1855) - німецький математик, фізик і астроном
  2. Н. Ш. Кремер, 2.3. "Метод Гаусса", стр. 44
  3. Такого розташування мінору можна домогтися перестановкою стовпців основної матриці і відповідної перенумерацію змінних.
  4. Н. Ш. Кремер, 2.4. "Система m лінійних рівнянь з n змінними", стор 49

Література

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


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Метод Гаусса - Жордана
Метод Гаусса - Зейделя
Метод Гаусса (оптимізація)
Ряд Гаусса
Премія Гаусса
Гармата Гаусса
Дискримінант Гаусса
Постійна Гаусса
Кривизна Гаусса
© Усі права захищені
написати до нас
Рейтинг@Mail.ru