Вступ
Прості математичні задачі малої вимірності, що вивчаються в курсі вищої математики, допускають можливість отримання аналітичних рішень. Складні математичні моделі великої розмірності вимагають застосування чисельних методів.
Чисельні методи— це математичний інструментарій, за допомогою якого математична задача формулюється у вигляді, зручному для розв’язання на комп’ютері. У такому разі говорять про перетворення математичної задачі в обчислювальнузадачу. При цьому послідовність виконання необхідних арифметичних і логічних операцій визначається алгоритмомїї розв’язання. Алгоритм повинен бути рекурсивним і складатися з відносно невеликих блоків, які багаторазово виконуються для різних вхідних даних.
Слід зазначити, що з появою швидких та потужних цифрових комп’ютерів роль чисельних методів для розв’язання наукових та інженерних задач значно зросла. І хоча аналітичні методи розв’язання математичних задач, як і раніше, дуже важливі, чисельні методи суттєво розширюють можливості розв’язання наукових та інженерних задач, не дивлячись на те, що самі рівняння математичних моделей з ускладненням структури сучасних виробів стають погано обумовленими та жорсткими, що істотно ускладнює їх розв’язування. Узявши виконання рутинних обчислень на себе, комп’ютери звільняють час вченого або інженера для творчості: формулювання задач і генерування гіпотез, аналізу та інтерпретації результатів розрахунку тощо.
Чисельні методи забезпечують системний формалізований підхід до розв’язання математичних задач. Проте за умов їх ефективного використання окрім уміння присутня і деяка частка мистецтва, що залежить від здібностей користувача, оскільки для розв’язання кожної математичної задачі існує декілька можливих чисельних методів і їх програмних реалізацій для різних типів комп’ютерів. На жаль, для обрання ефективного способу розв’язання поставленої задачі лише інтуїції замало, потрібні глибокі знання і певні навички. Існує декілька переконливих причин, що мотивують необхідність глибокого вивчення чисельних методів майбутніми фахівцями у галузі комп’ютерно-системної інженерії та прикладної математики.
Чисельні методи є надзвичайно потужним інструментарієм для розв’язання проблемних задач, що описуються довільними нелінійними диференціально-алгебраїчними рівняннями великої розмірності, для яких в даний час не існує аналітичних рішень. Освоївши такі методи, майбутній фахівець набуває здібностей до системного аналізу через математичне моделювання найскладніших задач сучасної науки і техніки.
У своїй майбутній професійній діяльності такий фахівець у першу чергу орієнтуватиметься на використання пакетів сучасних обчислювальних програм, причому те, наскільки правильно він буде їх застосовувати, безпосередньо залежатиме від знання і розуміння ним особливостей і обмежень, властивих чисельним методам, що реалізовані в пакеті. Може трапитися, що одна й та сама математична задача за допомогою певного програмно-технічного комплексу буде одним фахівцем успішно розв’язана, а іншим — ні, оскільки в сучасних пакетах передбачено їх налагоджування під конкретну задачу.
Може з’ясуватися, що низку задач неможливо розв’язати з використанням наявних пакетів програм. Якщо майбутній фахівець знає чисельні методи і володіє навичками програмування, він буде в змозі самостійно провести розробку необхідного алгоритму і програмно його реалізувати, вбудувавши в обчислювальний комплекс.
Вивчення чисельних методів стимулює освоєння самих комп’ютерів, оскільки найкращим способом навчитися програмувати є написання комп’ютерних програм власноруч. Правильно застосувавши чисельні методи, майбутній фахівець зможе пересвідчитися у тому, що комп’ютери успішно розв’язують його професійні задачі. При цьому він сам відчує вплив похибок обчислень на результат і навчиться контролювати ці похибки.
Вивчення чисельних методів сприяє також переосмисленню і більш глибокому розумінню математики в цілому, оскільки однією із задач чисельних методів є зведення методів вищої математики до виконання простих арифметичних операцій.
Хоча існує безліч чисельних методів, усі вони (як і алгоритми, що їм відповідають) мають багато спільних властивостей і характеристик. Чисельні методи:
передбачають проведення великої кількості рутинних арифметичних обчислень за допомогою рекурсивних співвідношень, що використовуються для організації ітерацій, тобто повторюваних циклів обчислень зі зміненими початковими умовами для поліпшення результату;
направлені на локальне спрощення задачі, коли, наприклад, використовувані нелінійні залежності лінеаризуються за допомогою своїх обчислених похідних або похідні замінюються різницевими апроксимаціями;
значно залежать від близкості початкового наближення (або декількох наближень), необхідного для початку обчислень до розв’язку, від властивостей нелінійних функцій, які використовуються в математичних моделях, що накладає обмеження (для забезпечення єдиного розв’язку) на їх диференційованість, на швидкість зміни функцій та ін.;
Чисельні методи характеризуються:
різною швидкістюзбіжності, тобто числом ітерацій, виконання яких необхідне для отримання заданої точності розв’язку;
різною стійкістю, тобто збереженням достовірності розв’язку під час подальших ітерацій;
різною точністюотримуваного розв’язку в разі виконання однакового числа ітерацій або циклів обчислень.
Чисельні методи розрізняються:
за широтою і легкістю застосування, тобто за ступенем своєї універсальностіта інваріантностідля розв’язання різних математичних задач;
за складністюїх програмування;
за можливостями використання у разі їх реалізації наявних бібліотек функцій і процедур, створених для підтримки різних алгоритмічних мов;
за ступенемчутливостідо погано обумовлених (або некоректних) математичних задач, коли малим змінам вхідних даних можуть відповідати великі зміни розв’язку.
1. Теоретична частина
1.1 Метод Гауса
Метод Гауса (або метод послідовного виключення невідомих) застосовний для розв’язання систем лінійних рівнянь, в яких число невідомих може бути або рівно числу рівнянь, або відмінно від нього.
Система т лінійних рівнянь з п невідомими має вигляд:
/>
x1, x2., xn – невідомі.
ai j — коефіцієнти при невідомих.
bi — вільні члени (або праві частини)
Система лінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною, якщо вона не має розв’язків.
Сумісна система називається визначеною, якщо вона має єдине розв’язок і невизначеною, якщо вона має незліченну безліч розв’язків.
Дві сумісні системи називаються рівносильними, якщо вони мають одну і ту ж множину розв’язків.
До елементарних перетворень системи віднесемо наступні:
зміна місцями два будь-яких рівнянь;
множення обох частин будь-якого з рівнянь на довільне число, відмінне від нуля;
збільшення до обох частин одного з рівнянь системи відповідних частин іншого рівняння, помножених на будь-яке дійсне число.
Елементарні перетворення переводять систему рівнянь в рівносильну їй.
Для простоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьома невідомими у разі, коли існує єдиний розв’язок:
Дана система:
/>(1)--PAGE_BREAK--
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.
Обчислюємо /> продолжение
--PAGE_BREAK--
Для обчислення значення />використовуємо лише рядки розділів І, ІІ, ІІІ, що містять одиниці, починаючи з останньої. Так, для обчислення />помножимо />на />і результати віднімаємо з />. При цьому одиниці, розставлені в розділі 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) перейдемо до еквівалентної продолжение
--PAGE_BREAK--
/>(8)
або в розгорненому вигляді:
/>(9)
З останніх двох рівнянь системи (9) треба тепер виключити змінне />. Оскільки максимальним елементом першого стовпця укороченої системи
/>(10)
є елемент другого рядка, робимо в (10) перестановку рядків і тим самим від системи (9) переходимо до еквівалентної системи, яку можна записати в матричному вигляді як:
/>. (12)
Таким чином система (12) отримана з (8) застосуванням элементарної матриці перестановок:
/>
Далі до системи (11) треба застосувати другий крок виключення звичайного методу Гауса. Це еквівалентно множенню системи (11) на елементарну нижню трикутну
/>
В результаті отримаємо систему
/>(13)
або />(14)
Завершальний крок прямого ходу методу Гауса полягає в заміні останнього рівняння системи (14)
/>
що еквівалентно множенню (13) на елементарну нижню трикутну матрицю
/>
Таким чином, для розглянутого прикладу процес виключення Гауса з вибором головного елементу по стовпцю записується так
/>(15)
По побудові матриця
/>(16)
є верхньою трикутною матрицею з одиничною головною діагоналлю.
Відмінність від звичайного методу Гауса полягає в тому, що як співмножники в (16) разом з елементарними трикутними матрицями />можуть бути присутніми елементарні матриці перестановок />.
Покажемо ще, що з (16) слідує розкладання
PA=LU (17)
L -нижняя трикутна матриця, що має обернену, P — матриця перестановок.
Для цього знайдемо матрицю:
/>(18)
Матриця отримується з матриці />перестановкою другого і третього рядків:
/>
Матриця отримується з />перестановкою другого і третього стовпців
/>
тобто />-нижняя трикутна матриця, що має зворотну.т.е.
З (18), враховуючи рівність/>, отримаємо
/>(19)
Звідси і з (16) видно, що
/>
де позначено />. Оскільки Р-матрица перестановок і L-нижняя трикутна матриця, властивість (17) доведена. Воно означає, що метод Гауса з вибором головного елементу по стовпцю еквівалентний звичайному методу Гауса, застосованому до матриці РА, тобто до системи, отриманої з початкової системи перестановкою деяких рівнянь.
Загальний висновок. Результат, отриманий раніше для дуже приватного прикладу, справедливий і у разі загальної системи рівнянь (1).
А саме, метод Гауса з вибором головного елементу по стовпцю можна записати у вигляді:
/>(20)
де /> — елементарні матриці перестановок такі, що />і /> — елементарні нижні трикутні матриці.
Звідси, використовуючи співвідношення перестановленості, аналогічні (19), можна показати, що метод Гауса з вибором головного елементу еквівалентний звичайному методу Гауса, застосованому до системи
PAx=Pf (21)
де Р — деяка матриця перестановок.
Теоретичне обгрунтування методу Гауса з вибором головного елементу міститься в наступній теоремі.
ТЕОРЕМА 1. Якщо />то існує матриця перестановок Р така, що матриця РА має відмінні від нуля кутові мінори.
Наслідок. Якщо />то існує матриця престанавок Р така, що справедливе розкладання
РА=LU, (22)
де L- нижня трикутна матриця з відмінними від нуля діагональними елементами і U- верхня трикутна матриця з одиничною головною діагоналлю. В цьому випадку для розв’язання системи (1) можна застосовувати метод Гауса з вибором головного елементу.
1.4 Алгоритм знаходження рангу матриці
Нехай потрібно обчислити ранг матриці />розмірів />. Якщо матриця />нульова, то за означенням маємо />. В іншому випадку за допомогою перестановки рядків і стовпців матриці добиваємося того, щоб у лівому верхньому куті матриці стояв ненульовий елемент. Отже, вважаємо, що />.
Перший рядок залишаємо без змін. До другого рядка додаємо перший, помножений на число />. У результаті другий рядок приймає вигляд: /> продолжение
--PAGE_BREAK--
Потім до третього рядку додаємо перший рядок, помножений на число />. У результаті третій рядок приймає вигляд: />
Процес продовжуємо до тих пір, поки не отримаємо нуль на першому місці в останньому рядку. Перетворена матриця має вигляд:
/>
Якщо всі рядки, починаючи з другої, в отриманій матриці нульові, то її ранг дорівнює 1, тому що є мінор першого порядку, відмінний від нуля />. В іншому випадку перестановкою рядків і стовпців матриці з номерами більше одиниці, домагаємося, щоб другий елемент другого рядка був відмінний від нуля. Отже, вважаємо, що />.
Перший і другий рядки залишаємо без змін. До третього рядка додаємо другий, помножений на число />. В результаті отримаємо, що другий елемент третього рядка дорівнює нулю. Потім до четвертого рядка додаємо другий, помножений на число />, і т.д. В результаті отримуємо матрицю:
/>
Якщо всі рядки, починаючи з третього, нульові, то />, так як мінор:
/>
В іншому випадку перестановкою рядків і стовпців з номерами, більшими двох, домагаємося, щоб третій елемент третього рядка був відмінний від нуля. Далі, додаванням третього рядка, помноженого на відповідні числа, до рядків з великими номерами отримуємо нулі в третьому стовпці, починаючи з четвертого елемента, і т.д.
На деякому етапі ми прийдемо до матриці, у якої всі рядки, починаючи з />-ого, дорівнюють нулю (або відсутні при />), а мінор у перших />рядках і перших />стовпцях є визначником трикутної матриці з ненульовими елементами на діагоналі. Ранг такої матриці дорівнює />. З цього слідує, що />.
Зауваження 1. У запропонованому алгоритмі знаходження рангу матриці всі обчислення повинні здійснюватись без заокруглень. Наскільки завгодно мала зміна хоча б в одному з елементів проміжних матриць може призвести до того, що отримана відповідь буде відрізнятися від рангу вихідної матриці на кілька одиниць.
Зауваження 2. Якщо у вихідній матриці елементи були цілими числами, то й обчислення зручно проводити без використання дробів. Тому на кожному етапі доцільно множити рядки на такі числа, щоб при обчисленнях дроби не виникали.
Властивість 1. При транспонування матриці її ранг не змінюється.
Властивість 2. Ранг матриці не змінюється при перестановці її стовпців (рядків).
Властивість 3. Ранг матриці не змінюється при збільшенні всіх елементів її стовпця (рядка) на відмінне від нуля число.
Властивість 4. Ранг матриці не зміниться, якщо до одного з її стовпців (рядка) додати інший стовпець (рядок), помноживши його (її) на деяке число.
Властивість 5. Ранг матриці не зміниться, якщо видалити з неї стовпець (рядок), що складається з одних нулів.
Властивість 6. Ранг матриці не зміниться, якщо видалити з неї стовпець (рядок), що є лінійною комбінацією інших стовпців (рядків).
Розділ 2. Практична реалізація
2.1 Розв’язання системи рівнянь методом Гауса
Приклад 1. Знайдемо розв’язок системи рівнянь методом Гауса:
/>
Сформуємо розширену матрицю:
/>
Прямий хід методу Гауса:
Крок 1.
Розділимо перший рядок матриці на />
Отримаємо матрицю наступного вигляду:
/>
Крок 2.
Віднімаємо від другого рядка перший рядок, помножений на />
Віднімаємо від третього рядка перший рядок, помножений на />
Отримана модифікована матриця:
/>
Крок 3.
Розділимо другий рядок на />:
/>
Крок 4.
Віднімаємо від третього рядка другий рядок, помножений на />
/>
Крок 5.
Розділимо третій рядок матриці на />:
/>
Прямий хід метода Гауса закінчено. Обернений хід метода Гауса. Утворюємо нулі вище головної діагоналі. продолжение
--PAGE_BREAK--
Крок 6.
Віднімаємо від другого рядка третій, помножений на />Віднімаємо від першого рядка третій, помножений на />:
/>
Крок 7.
Віднімаємо від першого рядка другий, помножений на />:
/>
Запишемо систему рівнянь по останній розширеній матриці:
/>
Змінні x1, x2, x3залишемо в лівій частині рівняння, а х4перенесимо вправо. Остаточний вигляд системи буде такий:
/>
де х4– вільна змінна.
Дана система рівнянь має безліч розв’язків.
Приклад 2. Розв’яжемо СЛАР методом Гауса в MS Excel:
/>
Цей метод розв'язання систем лінійних рівнянь придатний для розв'язання систем з будь-яким числом рівнянь і невідомих.
Запишемо нашу СЛАР в матричній формі:
/>
/>
Отже маємо:
/>
Помічений елемент матриці />, оскільки він не дорівнює нулю отже виключаємо змінну />і утворюємо нулі нижче />, отримуємо наступну матрицю:
/>
Якщо ж />, то потрібно переставляти рядки. Вибираємо перший ненульовий елемент в стовпчику, що знаходиться нижче від розв’язувального елемента і переставляємо цей рядок на рядок з нульовим елементом />
Аналогічно продовжуємо до отримання розв’язку СЛАР. В результаті отримаємо наступну табличку:
/>
/>
Отже в результаті отримали:
/>, де />— небазисні змінні.
Загальний розв’язок системи буде мати наступний вигляд:
/>, де />— довільні.
Приклад 3. Розв’язання СЛАР з вибором головного елемента в MS Excel:
/>
Суть даного методу полягає в тому, що на кожному кроці обирається напрямний рядок з максимальним абсолютним значенням розв’язувального елемента. Його перевагами у порівнянні з методом Гауса є те, що в результаті отримаємо меншу накопичену похибку за рахунок ділення напрямних рядків на більші елементи, але для погано обумовлених СЛАР похибка як і в методі Гауса може бути суттєвою.
Знаходження розв’язку за допомогою методу головного елемента описується наступним чином:
/>
/>
/>
Загальний розв’язок системи має вигляд:
/>, де />— довільні.
Відповіді отриманні при розв’язуванні ідентичні, але кількість кроків виконаних, при реалізації метода головного елемента, дещо більша ніж в методі Гауса.
2.2 Обчислення рангу матриці
Приклад 4. Знайти ранг матриці:
/>
Розв’язання. Перший рядок залишаємо без змін. Щоб уникнути появи дробів, помножимо другу, третю та четверту рядки на 2:
/>
Перший рядок помножимо на />і додамо до другого. Отримаємо рядок />. Перший рядок помножимо на />і додамо до третього. Отримаємо рядок />. Перший рядок помножимо на />і додамо до четвертого. Отримаємо рядок />. У результаті маємо матрицю: продолжение
--PAGE_BREAK--
/>
Другу рядок залишаємо без змін. На третьому рядку додаємо другий, помножений на 2. Отримаємо рядок />. До четвертого рядка додаємо другий. Отримаємо нульовий рядок. Перетворена матриця має вигляд:
/>
Поміняємо місцями третій і четвертий стовпчики:
/>
Базисний мінор матриці />стоїть у перших трьох стовпцях і перших трьох рядках, />. Отже, />.
2.3 Опис та інструкція по використанню програми Gauss
Дана програма реалізована в інтегрованому середовищі програмування Visual Studio 2008 SP1 мовою програмування С#. Вона дозволяє розв’язувати систему лінійних алгебраїчних рівнянь методом Гауса, записаних в матричній формі, а також методом з пошуком головного елемента, при чому матриці можуть будь-якою вимірністю mxn (m і n – кількість стовпчиків та рядків матриці відповідно). Також ще однією з можливостей програми є обчислення рангу матриці.
Інтерфейс програми має наступний вигляд:
/>
Мал. 1 Інтерфейс програми
Почати роботу з програмою користувач може двома способами:
Вибрати запропоновані варіанти завдань
/>
Мал. 2 Варіанти завдань
Ввести вимірність матриці mxn у відповідних полях програми і натиснути кнопку «Застосувати»
/>
Мал. 3 Поле матриці mxn
Зауваження 1. Якщо ми маємо систему з чотирма рівняннями і чотирма невідомими, тобто матрицю А 4х4, то при введені даних в полях розмірності матриці, вважаємо, що B – це ще один стовпчик матриці А, яке це зображено на малюнку. 3.
Далі робота з програмою проходить наступним чином:
В залежності від того яким методом ми хочемо розв’язати рівняння, натискаємо на кнопку «Метод Гауса», «метод головного елемента», що зображені на малюнку 4.
/>
Мал. 4. Функціональні кнопки пошуку розв’язку
Після натиснення на відповідну кнопку у вікну програми ми отримаємо загальний розв’язок системи, а також ранг матриці, що розглядаємо (малюнок 5)
Далі у користувача буде декілька варіантів продовження роботи:
Завершення роботи програми. Файл à Вихід, або закривши вікно програми, натиснувши на «хрестик».
Збереження результатів програми у файл з послідовним описом кожного виконаного кроку (виключення змінної з розгляду та утворення нулів нижче-вище розв’язувального елемента; переставлення рядків)
Знаходження розв’язку СЛАР при введених нових даних.
/>
Мал. 5 Вікно програми після обчислень
Зауваження 2. Якщо вибране нами СЛАР розв’язку немає, то на екрані з’явиться повідомлення, в якому буде сказано, що методом Гауса розв’язку ми отримати не зможемо, а також буде вказано, який саме ранг буде мати дана матриця (малюнок 6).
/>
Мал. 6 СЛАР розв’язків немає.
Перевіримо коректність роботи програмі на прикладі 6. (пункт 3.1)
Отримаємо розв’язок СЛАР, а також ранг матриці (малюнок 7)
/>
Мал. 7. Обчислення прикладу 6.
Збережемо детальний опис всіх кроків і відповідь у файл Excel з назвою Gauss.xls (малюнок 8). Якщо ж ми хочемо зберегти дані в блокноті, то тоді потрібно змінити розширення файлу на *.txt.
/>
Мал. 8. Збереження результату.
Порівнявши дані результати з розв’язками, які ми отримали, при розв’язанні СЛАР за допомогою MS Excel, можемо стверджувати, що рівняння розв’язано правильно, оскільки відповіді ідентичні.
/>
/>
Опис основних функцій програми
Весь код програми знаходиться в додатках.
Розглянемо основні функції, які були задіяні при написанні програми:
public void Gauss()- функція, яка безпосередньо відповідає за метод Гауса.
public void Gauss2()- функція, яка відповідає за розв’язання методом головного елемента.
public int Rang2()-функція знаходження рангу матриці.
private void Flush(int i, int j)- функція, яка дозволяє переставляти рядки матриці.
private int FindToFlush()- функція пошуку рядка, необхідного для переставлення по методу Гауса.
private int FindToFlush2()- функцію пошуку рядка, необхідного для переставлення по методу головного елемента.
private void ForwDirection(int i, int j)- функція, яка описує прямий хід методу Гауса.
private void BackDirection(int i, int j) – обернений хід методу Гауса.
private void MakeNull(int i)
private void MakeNullD- утворення нулів нижче розв’язувального елемента в прямому ході Гауса і утворення нулів вище розв’язувального елемента в обереному ході методу.
Список використаних джерел та літератури
Тарасов В.Н., Бахарева Н.Ф. Численные методы. Теория, алгоритмы, программы. – Оренбург: ИПК ОГУ, 2003.
Курош А.Г., “ Курс высшей алгебры ”, изд. 10, «Наука», Москва, 1971 г.
Овчинников П.Ф., Яремчук Ф.П., Михайленко В.М… Высшая математика – К.: Вища шк. Главное изд., 1987 г.
Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах.- М.: Наука
Г.Н.Воробьева, А.Н. Данилова. Практикум по вычислительной математике – Москва «Высшая школа», 1990.
Л.И.Турчак. Основы численных методов – Москва «Наука», 1987.
Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці – Київ «Питер», 2006.