Xreferat.com » Рефераты по математике » Розв'язування систем лінійних рівнянь методом Гауса

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

Вступ


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

Чисельні методи — це математичний інструментарій, за допомогою якого математична задача формулюється у вигляді, зручному для розв’язання на комп’ютері. У такому разі говорять про перетворення математичної задачі в обчислювальну задачу. При цьому послідовність виконання необхідних арифметичних і логічних операцій визначається алгоритмом її розв’язання. Алгоритм повинен бути рекурсивним і складатися з відносно невеликих блоків, які багаторазово виконуються для різних вхідних даних.

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

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

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

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

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

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

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

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

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

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

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

Чисельні методи характеризуються:

 різною швидкістю збіжності, тобто числом ітерацій, виконання яких необхідне для отримання заданої точності розв’язку;

 різною стійкістю, тобто збереженням достовірності розв’язку під час подальших ітерацій;

 різною точністю отримуваного розв’язку в разі виконання однакового числа ітерацій або циклів обчислень.

Чисельні методи розрізняються:

 за широтою і легкістю застосування, тобто за ступенем своєї універсальності та інваріантності для розв’язання різних математичних задач;

 за складністю їх програмування;

 за можливостями використання у разі їх реалізації наявних бібліотек функцій і процедур, створених для підтримки різних алгоритмічних мов;

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


1. Теоретична частина


1.1 Метод Гауса


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

Система т лінійних рівнянь з п невідомими має вигляд:


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


x1, x2., xn – невідомі.

ai j - коефіцієнти при невідомих.

bi - вільні члени (або праві частини)

Система лінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною, якщо вона не має розв’язків.

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

Дві сумісні системи називаються рівносильними, якщо вони мають одну і ту ж множину розв’язків.

До елементарних перетворень системи віднесемо наступні:

зміна місцями два будь-яких рівнянь;

множення обох частин будь-якого з рівнянь на довільне число, відмінне від нуля;

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

Елементарні перетворення переводять систему рівнянь в рівносильну їй.

Для простоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьома невідомими у разі, коли існує єдиний розв’язок:

Дана система:


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


1-й крок методу Гауса.

На першому кроці виключимо невідоме х1 зі всіх рівнянь системи (1), окрім першого. Хай коефіцієнт Розв'язування систем лінійних рівнянь методом Гауса. Назвемо його провідним елементом. Розділимо перше рівняння системи (1) на а11. Отримаємо рівняння:


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

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


Виключимо х1 з другого і третього рівнянь системи (1). Для цього віднімемо з них рівняння (2), помножене на коефіцієнт при х1 (відповідно а21 і а31).

Система прийме вигляд:


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


Верхній індекс (1) указує, що мова йде про коефіцієнтах першої перетвореної системи.

2-ий крок методу Гауса. На другому кроці виключимо невідоме х2 з третього рівняння системи (3).

Хай коефіцієнт Розв'язування систем лінійних рівнянь методом Гауса. Виберемо його за провідний елемент і розділимо на нього друге рівняння системи (3), отримаємо рівняння:


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


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


З третього рівняння системи (3) віднімемо рівняння (4), помножене на Розв'язування систем лінійних рівнянь методом ГаусаОтримаємо рівняння:


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


Припускаючи, що Розв'язування систем лінійних рівнянь методом Гауса знаходимо:


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


В результаті перетворень система прийняла вигляд:


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


Система вигляду (5) називається трикутною.

Процес приведення системи (1) до трикутного вигляду (5) (кроки 1 і 2) називають прямим ходом методу Гауса.

Знаходження невідомих з трикутної системи називають зворотним ходом методу Гауса.

Для цього знайдене значення х3 підставляють в друге рівняння системи (5) і знаходять х2. Потім х2 і х3 підставляють в перше рівняння і знаходять х1.

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

Звідси інша назва методу Гауса – метод послідовного виключення невідомих.

Якщо в ході перетворень системи виходить суперечливе рівняння вигляду 0 = b, де b № 0, то це означає, що система несумісна і розв’язків не має.

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

Трикутна система має вигляд:


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


Така система має єдине рішення, яке знаходиться в результаті проведення зворотного ходу методу Гауса.

Ступінчаста система має вигляд:

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


Така система має незліченну множину розв’язків. Щоб знайти їх, у всіх рівняннях системи члени з невідомими хk+1., xk переносять в праву частину. Ці невідомі називаються вільними і надають їм довільні значення. З отриманої трикутної системи знаходимо х1., xk, які виражатимуться через вільних невідомих.


1.2 Компактна схема Гауса


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


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


Всі результати обчислення будемо записувати в одну таблицю (Таблиця 1)


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

Компактна схема Гауса. Таблиця 1.


Порядок заповнення таблиці.

Прямий хід.

Записуємо коефіцієнти даної системи в чотирьох рядках і п’яти стовпцях розділу І таблиці 1.

Додаємо всі коефіцієнти по рядку і записуємо суму в стовпчик Розв'язування систем лінійних рівнянь методом Гауса(стовпчик контролю), наприклад Розв'язування систем лінійних рівнянь методом Гауса.

Ділимо всі числа, які стоять в першому рядку, на Розв'язування систем лінійних рівнянь методом Гауса і результати Розв'язування систем лінійних рівнянь методом Гауса записуємо в п’ятому рядку розділу І.

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

По формулам (2.4) обчислюємо коефіцієнти:


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


Результати записуємо в перші три рядки розділу ІІ.

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

Ділимо всі елементи першого рядка розділу ІІ на Розв'язування систем лінійних рівнянь методом Гауса і результати записуємо в четвертому рядку розділу ІІ.

Робимо перевірку, як в пункті 4).

За формулами (2.7) обчислюємо Розв'язування систем лінійних рівнянь методом ГаусаРезультати записуємо в перші два рядки розділу ІІІ.

Робимо перевірку, як в пункті 6).

Ділимо елементи першого рядка розділу ІІІ на Розв'язування систем лінійних рівнянь методом Гауса і знаходимо числа Розв'язування систем лінійних рівнянь методом Гауса. Всі результати записуємо в третьому рядку розділу ІІІ.

Робимо перевірку.

Обчислюємо Розв'язування систем лінійних рівнянь методом Гауса. Результати записуємо в розділі IV.

Обернений хід.

В розділі V записуємо одиниці, як це показано в таблиці 1.

Обчислюємо Розв'язування систем лінійних рівнянь методом Гауса

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

Таким чином,


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


Обчислюємо Розв'язування систем лінійних рівнянь методом Гауса, для чого використовуємо елементи поміченого рядка розділу ІІ:


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


Обчислюємо Розв'язування систем лінійних рівнянь методом Гауса, для чого використовуємо елементи поміченого рядка розділу І: Розв'язування систем лінійних рівнянь методом Гауса

Аналогічно проводиться обернений хід в контрольній системі. Розв’язок цієї системи повинен відрізнятися від розв’язку даної системи на 1 (з точністю до одиниці останнього розряду): Розв'язування систем лінійних рівнянь методом Гауса

Цей контроль здійснюється за допомогою стовпця Розв'язування систем лінійних рівнянь методом Гауса

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


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

Компактна схема Гауса для системи (2.12). Таблиця 2.


1.3 Метод Гауса з вибором головного елемента


Основна ідея методу. Може трапитись, що система


Ax=f (1)


де A - матриця m*m, x = (x1, x2...,xm) - шуканий вектор

f =(f1, f2..., fm) -заданий вектор.

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

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

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


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

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


Припустимо, що Розв'язування систем лінійних рівнянь методом Гауса. Тоді на першому кроці виключатимемо змінне Розв'язування систем лінійних рівнянь методом Гауса. Такий прийом еквівалентний тому, що система (2) переписується у вигляді:


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

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


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

Застосовується також метод Гауса з вибором головного елементу по стовпцю. Припустимо, що Розв'язування систем лінійних рівнянь методом Гауса. Перепишемо систему (2) у вигляді:

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

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


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

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

Матриці перестановок. Раніше було показано, що звичайний метод Гауса можна записати у вигляді:


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


де Розв'язування систем лінійних рівнянь методом Гауса -- елементарні нижні трикутні матриці. Щоб отримати аналогічний запис методу Гауса з вибором головного елементу, необхідно розглянути матриці перестановок.

Означення 1. Матрицею перестановок Р називається квадратна матриця, у якої в кожному рядку і в кожному стовпці тільки один елемент відмінний від нуля і рівний одиниці.

Означення 2. Елементарною матрицею перестановок Розв'язування систем лінійних рівнянь методом Гаусаназивається матриця, отримана з одиничної матриці перестановкою к-го і l-го рядків.

Наприклад, елементарними матрицями перестановок третього порядку є матриці:

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


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

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

Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.

Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.

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


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


Система має вигляд (1), де


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


Максимальний елемент першого стовпця матриці А знаходиться в другому рядку. Тому треба поміняти місцями другий і перший рядки і перейти до еквівалентної системи

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


Систему (6) можна записати у вигляді


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


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


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


Далі, до системи (6) треба застосувати перший крок звичайного методу виключення Гауса. Цей крок еквівалентний множенню системи (7) на елементарну нижню трикутну


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


В результаті від системи (7) перейдемо до еквівалентної


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

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


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


З останніх двох рівнянь системи (9) треба тепер виключити змінне Розв'язування систем лінійних рівнянь методом Гауса. Оскільки максимальним елементом першого стовпця укороченої системи


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


є елемент другого рядка, робимо в (10) перестановку рядків і тим самим від системи (9) переходимо до еквівалентної системи, яку можна записати в матричному вигляді як:


Розв'язування систем
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: