Розділ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Скачати 172.67 Kb.

Назва	Розділ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Сторінка	1/3
Дата	08.02.2014
Розмір	172.67 Kb.
Тип	Документи

bibl.com.ua > Інформатика > Документи

1 2 3

Розділ 3. РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ

АЛГЕБРАЇЧНИХ РІВНЯНЬ
У цьому розділі розглянемо основні чисельні методи розв’язання задач лінійної алгебри. Наведемо математичне описання, блок-схеми та програми, реалізовані в пакеті Mathcad розв’язання систем лінійних алгебраїчних рівнянь, обчислення визначників та обернення матриць.

3.1. Основні поняття

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

(1)

або

,

де

– невідомі;

– дійсні числа, які називають коефіцієнтами системи;

– вільні члени.

Систему лінійних алгебраїчних рівнянь часто записують у матричній формі

(2)

,

де А – матриця коефіцієнтів системи,

– вектор вільних членів і

– вектор невідомих. Матриця з вимірності

називається прямокутною. У випадку, якщо

, то матрицю називають квадратною матрицею порядку

.

Квадратна матриця

вимірності

називається:

 нульовою, якщо всі елементи дорівнюють нулю:

;

 верхньою трикутною, якщо всі елементи, розташовані нижче головної діагоналі, дорівнюють нулю:

;

 нижньою трикутною, якщо всі елементи, розташовані вище головної діагоналі, дорівнюють нулю:

;

 діагональною, якщо всі елементи, крім головної діагоналі, дорівнюють нулю:

;

 одиничною, якщо всі елементи головної діагоналі дорівнюють одиниці, а всі інші – нулю:

.

Квадратна матриця називається неособливою, якщо її визначник (детермінант) відмінний від нуля. У протилежному випадку матриця називається особливою або виродженою.

Якщо матриця А неособлива, тобто її визначник не дорівнює нулю, то система (2) має єдиний розв’язок. У лінійній алгебрі звичайно використовують спосіб розв’язання системи рівнянь (2), який базується на обчислені оберненої матриці

. Дійсно, якщо помножити обидві частини рівняння (2) на

, розв’язок рівняння (2) отримаємо у вигляді

. (3)

Як відомо, елементи оберненої матриці

можна обчислити за відомою формулою

, де

– алгебраїчні доповнення елемента

матриці А і

визначник цієї матриці. Тоді для знаходження всіх її елементів потрібно обчислити

визначників

-го порядку. Остання задача настільки трудомістка (вимагає велику кількість арифметичних операцій), що розв’язати її навіть при

дуже важко (це задача складності

).

Менш трудомістким є метод Крамера, згідно з яким значення невідомих знаходяться за допомогою формули

, (4)

де матриця

формується з матриці

заміною її j-го стовпця на стовпець вільних членів. Але для розв’язання системи лінійних алгебраїчних рівнянь з

невідомими у такий спосіб потрібно обчислити

визначник порядку

, що знову ж таки вимагає виконання арифметичних операцій порядку

. Уже при

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

У зв’язку з цим наведемо визначення деяких спеціальних матриць. Квадратна матриця

називається:

 симетричною, якщо

;

 кососиметричною, якщо

;

 ортогональною, якщо

;

 ідемпотентною, якщо

;

 інволютивною, якщо

, де Е – одинична матриця.

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

системи (2) є скінченим числом, причому, якщо обчислення виконуються точно (без заокруглень), то розв’язок отримуємо точний. Прикладом прямого методу є також метод Гаусса та його модифікації. Ітераційні методи полягають в тому, що розв’язок

системи (2) знаходять як границю послідовних наближень

, коли

, де

– номер ітерації.

Чисельні методи розв’язання задач лінійних алгебри на сьогодні добре досліджені та описані в літературі. Крім того, є розроблено ряд математичних пакетів (Mathcad, Mathematica, Maple, Matlab), які дають можливість як досліджувати, так і розв’язувати задачі лінійної алгебри. Для ілюстрації обчислень і викладок ми вибрали пакет Mathcad з огляду на можливість виконувати за допомогою цього пакету арифметичні операції як в символьному, так і в числовому вигляді. А наявність нотації запису формул близької до звичайних математичних записів, на нашу думку, буде сприяти кращому розумінню та засвоєнню алгоритмів розв’язання задач лінійної алгебри. Цьому ж буде сприяти і наявність простих засобів програмування та можливостей графічного редактора даного пакету.

3.2. Метод вилучення Гаусса

Найпростішим варіантом методу вилучення Гаусса є схема єдиного ділення. Відповідно до даної схеми алгоритм виключення невідомої

і-те рівняння

, яке називається головним, ділять на провідний коефіцієнт

. Потім отримане таким чином рівняння множать на

і віднімають відповідно із

-го,

-го, і т.д,

-го рядків системи (1). В результаті таких перетворень, при умові, що визначник матриці системи не дорівнює нулю, приходимо до системи з трикутною матрицею з одиничними діагональними елементами, яка є еквівалентна вихідній системі. Якщо провідний елемент на і-му кроці перетворюється в нуль

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

Розглянемо цей алгоритм детальніше. Нехай маємо систему

рівнянь з

невідомими (1).

Будемо реалізовувати метод Гаусса шляхом еквівалентних перетворень системи. Для зручності записів введемо позначення:

.

Тоді системи (1) запишемо у вигляді

(5)

Метод виключення Гаусса, прийнято реалізовувати за два ходи: прямого і зворотного. На прямому ході, за допомогою еквівалентних перетворень, систему (5) зводять до верхнього трикутного вигляду, а на зворотному ході, з одержаної системи знаходять, значення невідомих, тобто розв’язок системи.

Прямий хід методу Гаусса. Нехай

. Тоді перше рівняння залишимо без зміни

(6)

і використаємо його для виключення невідомого

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

із другого рівняння додамо до нього перше, помножене на

. Потім, помноживши перше рівння на

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

і т.д. В результаті одержимо системи рівнянь вигляду

(7)

де

.

Нехай

. Тоді друге рівняння залишимо без зміни

, (8)

і використаємо його для виключення невідомого

із всіх рівнянь системи (5), починаючи з третього. Для цього до третього і наступних рівняннь системи (7) додамо рівняння (8), помножене на

. В результаті одержимо систему вигляду

(9)

де

Продовжуючи процес за даною схемою далі, на n-1-му кроці одержимо систему трикутного вигляду

(10)

На цьому закінчується прямий хід методу Гаусса.

Зворотний хід. На зворотному ході методу Гаусса знаходимо значення невідомих в оберненому порядку.

З останнього рівняння системи (10) маємо, що

. Тоді з передостаннього рівняння системи (10) знаходимо:

т.д. Нарешті з першого рівняння знаходимо:

.

У загальному випадку під час прямого ходу методу Гаусса коефіцієнти системи та праві частини обчислюються за наведеними нижче формулами:

;

(11)

(12)

(13)

. (14)

Якщо коефіцієнти

і праві частини

зберігаються в пам’яті ЕОМ, то зворотний хід здійснюється за формулами:

або

. (15)

Основним обмеженням методу Гаусса є припущення про те, що всі ведучі елементи

відмінні від нуля. Слід мати на увазі, що якщо якийсь ведучий елемент не дорівнює нулю, а просто близький до нього, то в процесі обчислень може відбутись значне накопичення похибок. У такому разі, як уже відмічалось, у відповідній системі достатньо буде переставити місцями (перенумерувати) рівняння для продовження процесу вилучення. Уникнути цього дозволяє метод Гаусса з вибором головного елемента.

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

, то в процесі обчислень не відбудеться ділення на нуль.

На практиці, для зменшення похибок заокруглення, здебільшого, роблять так. Серед елементів першого стовпця

кожної проміжної матриці з номером

вибирають найбільший за модулем елемент в і-му стовпці

і роблять його ведучим, проводячи при цьому перестановка і-го і

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

1 2 3

Схожі:

“Ітераційні методи розв’язання систем лінійних рівнянь” Мета роботи: Вивчення ітераційних методів розв’язання систем лінійних рівнянь і набуття навичок їх реалізації за допомогою математичного...	Урок №73 Тема. Системи двох лінійних рівнянь із двома змінними та... Ня щодо залежності кількості розв'язків системи лінійних рівнянь від співвідношення коефіцієнтів a, b, c цих рівнянь; вироблення...
Урок №80 Тема. Розв'язування задач за допомогою систем лінійних рівнянь Мета: відпрацювати навички застосування схеми розв'язання текстових задач на складання системи лінійних рівнянь із двома змінними...	“Чисельні методи розв’язання нелінійних рівнянь” Мета роботи: Вивчення методів розв’язання алгебраїчних і трансцендентних рівнянь і набуття навичок їх реалізації за допомогою математичного...
Графічний спосіб розв’язування систем лінійних рівнянь із двома змінними Учитель Сьогодні на уроці ми продовжимо вивчати тему «Розв’язування систем лінійних рівнянь з двома змінними графічним способом»....	УРОК №71 Тема уроку. Системи рівнянь Мета уроку: формування понять: «система рівнянь з двома змінними»; «розв'язки системи лінійних рівнянь з двома змінними»; «ознайомлення...
УРОК №75 Тема уроку. Спосіб додавання Мета уроку: ознайомлення учнів із розв'язуванням систем лінійних рівнянь способом додавання; засвоєння алгоритму розв'язування систем...	УРОК №76 Тема уроку. Розв'язування вправ на розв'язування систем... Мета уроку: формування вмінь учнів розв'язувати системи лінійних рівнянь з двома змінними способом додавання
ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ Ужгород –... Мета роботи: Вивчення методів розв’язання систем нелінійних рівнянь і набуття навичок їх реалізації за допомогою математичного пакету...	УРОК №72 Тема уроку. Розв'язування систем рівнянь графічним способом Мета уроку: формування вмінь учнів розв'язувати системи лінійних рівнянь графічним способом

Додайте кнопку на своєму сайті:
Портал навчання