НОУ ІНТУЇТ | лекція | Завдання лінійної алгебри

5.6 Рішення систем лінійних рівнянь

Система m рівнянь з невідомими виду

називається системою лінійних алгебраїчних рівнянь (СЛАР), причому - невідомі, - коефіцієнти при невідомих, - вільні коефіцієнти .

Крім того, система з m лінійних рівнянь з невідомими може бути описана за допомогою матриць: , де - вектор невідомих, - матриця коефіцієнтів при невідомих або матриця системи, - вектор вільних членів системи або вектор правих частин .

матриця , Яка формується шляхом приписування до матриці коефіцієнтів шпальти вільних членів , Називається розширеною матрицею системи.

Якщо все , То мова йде про однорідну системі лінійних рівнянь, інакше говорять про неоднорідною системі.

Сукупність усіх рішень системи , Називається безліччю рішень або просто рішенням системи. Дві системи рівнянь називаються еквівалентними, якщо вони мають однакову безліч рішень.

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

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

ліві частини рівнянь збігаються, а праві різні, тому ніякі значення і не можуть задовольнити обом рівнянням відразу.

Якщо ж система лінійних рівнянь має рішення, то вона називається спільної. Спільна система називається певної, якщо вона володіє одним єдиним рішенням, і невизначеною, якщо рішень більше ніж одне. Так, система:

визначена і має єдине рішення , А система рівнянь:

невизначена, так як має безліч рішень виду , Де число довільно.

Сукупність усіх рішень невизначеної системи рівнянь називається її загальним рішенням, а якесь одне конкретне рішення - приватним. Приватне рішення, отримане із загального при нульових значеннях вільних змінних, називається базисним.

При визначенні спільності систем рівнянь важливу роль відіграє поняття рангу матриці. Нехай дана матриця розміром . Викреслюванням деяких рядків або стовпців з неї можна отримати квадратні матриці -го порядку, визначники яких називаються минорами порядку матриці . Найвищий порядок не рівних нулю миноров матриці називають рангом матриці і позначають . З визначення випливає, що , а , Тільки якщо матриця нульова і для невироджених матриці -го порядку. При елементарних перетвореннях (перестановка рядків матриці, множення рядків на число відмінне від нуля і складання рядків) ранг матриці не змінюється. Отже, якщо мова йде про дослідження системи на спільність, слід пам'ятати, що система лінійних рівнянь з невідомими:

Існує чимало мето дов для практичного відшукання рішень систем лінійних рівнянь. Ці методи поділяють на точні і наближені. Метод відноситься до класу точних, якщо з його допомогою можна знайти рішення в результаті кінцевого числа арифметичних і логічних операцій. У цьому розділі на конкретних прикладах будуть розглянуті тільки точні методи вирішення систем.

Приклад 5.8. Вирішити систему лінійних рівнянь

за допомогою правила Крамера.

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

Отже, для вирішення поставленого завдання необхідно виконати наступні дії:

лістинг 5.9 містить рішення поставленої задачі.

>>> disp ( 'Рішення СЛАР методом Крамера'); >>> disp ( 'Матриця системи:'); A = [2 -1 5; 3 2 -5; 1 + 1 -2] >>> disp ( 'Вектор вільних коефіцієнтів:'); b = [0; 1; 4] >>> disp ( 'Головний визначник:'); D = det (A) >>> disp ( 'Допоміжні матриці:'); >>> A1 = A; A1 (:, 1) = b >>> A2 = A; A2 (:, 2) = b >>> A3 = A; A3 (:, 3) = b >>> disp ( 'Допоміжні визначники:'); >>> d (1) = det (A1); >>> d (2) = det (A2); >>> d (3) = det (A3); >>> d >>> disp ( 'Вектор рішень СЛАР Ax = b'); x = d / D >>> disp ( 'Перевірка Ax-b = 0'); A * x'-b% _______________________________ Рішення СЛАР методом Крамера Матриця системи: A = 2 -1 5 3 2 -5 1 + 1 -2 Вектор вільних коефіцієнтів: b = 0 у середньому 1 4 Головний визначник: D = 6. 0 0 0 0 Допоміжні матриці: A1 = 0 -1 5 1 2 -5 4 1 -2 A2 = 2 0 5 3 1 -5 1 4 -2 A3 = 2 -1 0 3 2 1 1 1 4 Допоміжні визначники: d = -17.000 91.000 25.000 Вектор рішень СЛАР Ax = bx = -2.8333 15.166 74.1667 Перевірка Ax-b = 0 ans = -4.4409e-15 3.5527e-15 8.8818e-16 Лістинг 5.9. Рішення СЛАР методом Крамера (приклад 5.8).

Рішення СЛАР за формулами Крамера виглядає досить громіздко, тому на практиці його використовують досить рідко.

Приклад 5.9. Вирішити систему лінійних рівнянь 5.6 з прикладу 5.8 методом зворотної матриці.

Метод оберненої матриці: для системи з лінійних рівнянь з невідомими , За умови, що визначник матриці не дорівнює нулю, єдине рішення можна представити у вигляді (Виведення формули див. У прикладі 5.7).

Отже, для того, щоб вирішити систему лінійних рівнянь методом оберненої матриці, необхідно виконати наступні дії:

• сформувати матрицю коефіцієнтів і вектор вільних членів заданої системи;
• вирішити систему, представивши вектор невідомих як твір матриці зворотного до матриці системи і вектора вільних членів ( лістинг 5.10 ).

>>> disp ( 'Рішення СЛАР методом зворотної матриці'); >>> disp ( 'Матриця системи:'); >>> A = [2 -1 5; 3 2 -5; 1 + 1 -2] >>> disp ( 'Вектор вільних коефіцієнтів:'); >>> b = [0; 1; 4] >>> disp ( 'Вектор рішень СЛАР Ax = b'); >>> x = A ^ (-1) * b >>> disp ( 'Вектор рішень СЛАР Ax = b за допомогою функції inv (A)'); >>> x = inv (A) * b >>> disp ( 'Перевірка Ax = b'); >>> A * x% ______________________________________ Рішення СЛАР методом зворотної матриці Матриця системи: A = 2 -1 5 3 2 -5 1 + 1 -2 Вектор вільних коефіцієнтів: b = 0 у середньому 1 4 Вектор рішень СЛАР Ax = bx = -2.8333 15.1667 4.1667 вектор рішень СЛАР Ax = b за допомогою функції inv (A) x = -2.8333 15.1667 4.1667 Перевірка Ax-b = 0 ans = -5.3291e-15 1.0000e +00 4.0000e +00 Лістинг 5.10. Рішення СЛАР прикладу 5.8 методом зворотної матриці (приклад 5.9).

Приклад 5.10. Вирішити систему лінійних рівнянь

методом Гаусса.

Рішення системи лінійних рівнянь за допомогою методу Гаусса ґрунтується на тому, що від заданої системи переходять до еквівалентної системи, яка вирішується простіше, ніж вихідна система.

Метод Гаусса складається з двох етапів. Перший етап - це прямий хід, в результаті якого розширена матриця системи шляхом елементарних перетворень (перестановка рівнянь системи, множення рівнянь на число відмінне від нуля і складання рівнянь) приводиться до ступінчастому увазі:

На другому етапі (зворотний хід) ступінчасту матрицю перетворюють так, щоб в перших n шпальтах вийшла одинична матриця:

Останній, стовпець цієї матриці містить рішення системи лінійних рівнянь.

Виходячи з вище викладеного, порядок розв'язання задачі в Octave ( лістинг 5.11 ) Наступний:

>>> disp ( 'Рішення СЛАР методом Гауса'); >>> disp ( 'Матриця системи:'); A = [21 - 51; 1 - 30 - 6; 02 - 12; 14 - 76] >>> disp ( 'Вектор вільних коефіцієнтів:'); b = [8; 9; - 5; 0] >>> disp ( 'Розширена матриця системи:'); C = rref ([A b]) >>> disp ( 'Розмірність матриці C:'); n = size (C) >>> disp ( 'Вектор рішень СЛАР Ax = b'); x = C (:, n (2)) >>> disp ( 'Перевірка Ax-b'); A * xb% _________________________________ Рішення СЛАР методом Гауса Матриця системи: A = 2 1 -5 1 1 -3 0 -6 0 2 -1 2 1 4 -7 6 Вектор вільних коефіцієнтів: b = 8 9 -5 0 Розширена матриця системи: C = 1.00000 0.00000 0.00000 0.00000 3.00000 0.00000 1.00000 0.00000 0.00000 -4.00000 0.00000 0.00000 1.00000 0.00000 -1.00000 0.00000 0.00000 0.00000 1.00000 1.00000 Розмірність матриці С: n = 4 5 Вектор рішень СЛАР Ax = bx = 3.00000 -4.00000 -1.00000 1.00000 Перевірка Ax-b ans = 0.0000e +00 1.7764e-15 -8.8818e -16 -1.6653e -15 Лістинг 5.11. Рішення СЛАР методом Гауса (приклад 5.10).

Приклад 5.11. Вирішити систему лінійних рівнянь з прикладу 5.10 за допомогою -разложенія.

Дамо визначення розкладання матриці на множники. Якщо все визначники квадратної матриці відмінні від нуля, то існують такі нижня і верхня трикутні матриці, що :

Якщо діагональні елементи однієї з матриць ненульові, то таке розкладання єдине.

Метод вирішення системи лінійних рівнянь з використанням розкладання матриці коефіцієнтів на множники називають LU-розкладанням або LU-факторизації.

якщо матриця вихідної системи розкладена на витвір трикутних матриць і , То можна записати рівняння: .

Ввівши вектор допоміжних змінних , рівняння можна переписати у вигляді системи: .

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

Звернемо увагу на той факт, що виконання наведених розрахунків можна інтерпретувати як перетворення даної системи до трикутної. Іншими словами, LU-розкладання це інша схема реалізації методу Гаусса.

Виходячи з коштів, якими володіє Octave, рішення поставленого завдання буде виглядати так ( лістинг 5.12 ):

>>> disp ( 'Рішення СЛАР методом LU-розкладання'); >>> disp ( 'Матриця системи:'); A = [21 - 51; 1 - 30 - 6; 02 - 12; 14 - 76] >>> disp ( 'Вектор вільних коефіцієнтів:'); b = [8; 9; - 5; 0] >>> disp ( 'LU-розкладання:'); [L, U, P] = lu (A) >>> Y = rref ([LP * b]) >>> n = size (Y) >>> y = Y (:, n (2)) >> > X = rref ([U y]) >>> n = size (X) >>> x = X (:, n (2)) >>> disp ( 'Перевірка Ax-b'); A * xb% ___________________________________ Рішення СЛАР методом LU-розкладання Матриця системи: A = 2 1 -5 1 1 -3 0 -6 0 2 -1 2 1 4 -7 6 Вектор вільних коефіцієнтів: b = 8 9 -5 0 LU- розкладання: L = 1.00000 0.00000 0.00000 0.00000 0.50000 1.00000 0.00000 0.00000 0.50000 -1.00000 1.00000 0.00000 0.00000 -0.57143 -0.21429 1.00000 U = 2.00000 1.00000 -5.00000 1.00000 0.00000 -3.50000 2.50000 -6.50000 0.00000 0.00000 -2.00000 -1.00000 0.00000 0.00000 0.00000 -1.92857 P = Permutation Matrix 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 Y = 1.00000 0.00000 0.00000 0.00000 8.00000 0.00000 1.00000 0.00000 0.00000 5.00000 0.00000 0.00000 1.00000 0.00000 1.00000 0.00000 0.00000 0.00000 1.00000 -1.92857 n = 4 5 y = 8.0000 5.0000 1.0000 - 1.9286 X = 1.00000 0.00000 0.00000 0.00000 3.00000 0.00000 1.00000 0.00000 0.00000 -4.00000 0.00000 0.00000 1.00000 0.00000 -1.00000 0.00000 0.00000 0.00000 1.00000 1.00000 n = 4 5 x = 3.0000 -4.0 000 -1.0000 1.0000 Перевірка Ax-b ans = 0.0000e +00 0.0000e +00 -8.8818e-16 6.6613e-16 Лістинг 5.12. Рішення СЛАР методом LU-розкладання (приклад 5.11).

Приклад 5.12. Вирішити систему лінійних рівнянь

за допомогою -разложенія.

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

Ідея рішення системи цим методом аналогічна тій, що була описана в попередній задачі:

Ax = b -> QRx = b -> (Qy = b, Rx = y).

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

Як вирішити цю задачу засобами Octave, показано в лістингу 5.13 .

>>> disp ( 'Рішення лінійної системи за допомогою QR-розкладання'); >>> A = [3,1, -1,2; -5,1,3, -4; 2,0,1, -1; 1, -5,3, -3] >>> b = [6; - 1 | 2; 1; 3] >>> [Q, R] = qr (A) >>> y = Q '_ b >>> X = rref ([R y]) >>> x = X (1: 4, 5: 5 )% ____________________________________ Рішення лінійної системи за допомогою QR-розкладання A = 3 1 -1 2 -5 1 3 -4 2 0 1 -1 1 -5 3 -3 b = 6 -12 1 3 Q = 0.480384 0.303216 0.358483 0.740797 -0.800641 0.020214 0.545518 0.246932 0.320256 0.070750 0.735670 -0.592638 0.160128 -0.950077 0.180800 0.197546 R = 6.24500 -1.12090 -2.08167 3.36269 0.00000 5.07381 -3.02205 3.30505 0.00000 0.00000 2.55614 -2.74318 0.00000 0.00000 0.00000 0.49386 y = 13.2906 -1.2028 -3.1172 1.4816 X = 1.00000 0.00000 0.00000 0.00000 1.00000 0.00000 1.00000 0.00000 0.00000 -1.00000 0.00000 0.00000 1.00000 0.00000 2.00000 0.00000 0.00000 0.00000 1.00000 3.00000 x = 1.00000 -1.00000 2.00000 3.00000 Лістинг 5.13. Рішення СЛАР методом QR-розкладання (приклад 5.12).

Приклад 5.13. Дослідити систему на спільність і якщо можливо розв'язати цю проблему:

Для вирішення завдання ( лістинг 5.14 ) Введемо вихідні дані, тобто матрицю коефіцієнтів системи і вектор правих частин. Потім виконаємо обчислення рангів матриці коефіцієнтів і розширеної матриці системи.

У разі а) ранги матриць рівні і збігаються з кількістю невідомих , Значить, система сумісна і має єдиний розв'язок. Обчислення рангів матриці системи і розширеної матриці системи б) показує, що ранг розширеної матриці більше рангу матриці системи , Що означає несумісні системи. В процесі обчислень для системи в) з'ясовується, що ранг розширеної матриці дорівнює рангу матриці системи , Але менше, ніж кількість невідомих системи . Значить, система сумісна, але має безліч рішень.

disp ( 'Дослідження системи на спільність'); disp ( 'Введіть матрицю системи:'); A = input ( 'A ='); disp ( 'Введіть вектор вільних коефіцієнтів:'); b = input ( 'b ='); disp ( 'Розмірність системи:'); [N, m] = size (A) disp ( 'Ранг матриці системи:'); r = rank (A) disp ( 'Ранг розширеної матриці:'); R = rank ([A b]) if r == R disp ( 'Система сумісна.'); if r == m disp ( 'Система має єдине рішення.'); disp ( 'Рішення системи методом зворотної матриці:'); x = inv (A) _ b disp ( 'Перевірка Ax-b = 0:'); A_ x_b else disp ( 'Система має нескінченно багато рішень.') End; else disp ( 'Система не сумісна'); end; % Дослідження системи а) Дослідження системи на спільність Введіть матрицю системи: A = [1 2 5; 1 -1 3; 3 -6 -1] Введіть вектор вільних коефіцієнтів: b = [- 9; 2; 25] Розмірність системи: n = 3 m = 3 Ранг матриці системи: r = 3 Ранг розширеної матриці: R = 3 Система сумісна. Система має єдине рішення. Рішення системи методом зворотної матриці: x = 2.0000 -3.0000 -1.0000 Перевірка Ax-b = 0: ans = 0.0000e +00 8.8818e-16 3.5527e-15% Дослідження системи б) Дослідження системи на спільність Введіть матрицю системи: A = [ 1 -5 -8 1; 3 1 -3 -5; 1 0 -7 2; 0 11 20 -9] Введіть вектор вільних коефіцієнтів: b = [3; 1; - 5; 2] Розмірність системи: n = 4 m = 4 Ранг матриці системи: r = 3 Ранг розширеної матриці: R = 4 Система не сумісна% Дослідження системи в) Дослідження системи на спільність Введіть матрицю системи: A = [4 1 -3 -1 ; 2 3 1 -5; 1 -2 -2 4] Введіть вектор вільних коефіцієнтів: b = [0; 0; 0] Розмірність системи: n = 3 m = 4 Ранг матриці системи: r = 3 Ранг розширеної матриці: R = 3 Система сумісна. Система має безліч рішень. Лістинг 5.14. Дослідження системи на спільність (приклад 5.13).