Вступ
Простіматематичні задачі малої вимірності, що вивчаються в курсі вищої математики,допускають можливість отримання аналітичних рішень. Складні математичні моделівеликої розмірності вимагають застосування чисельних методів.
Чисельні методи — це математичний інструментарій, задопомогою якого математична задача формулюється у вигляді, зручному длярозв’язання на комп’ютері. У такому разі говорять про перетворення математичноїзадачі в обчислювальну задачу.При цьому послідовність виконання необхідних арифметичних і логічних операційвизначається алгоритмом їїрозв’язання. Алгоритм повинен бути рекурсивним і складатися з відносноневеликих блоків, які багаторазово виконуються для різних вхідних даних.
Слідзазначити, що з появою швидких та потужних цифрових комп’ютерів роль чисельнихметодів для розв’язання наукових та інженерних задач значно зросла. І хоча аналітичніметоди розв’язання математичних задач, як і раніше, дуже важливі, чисельніметоди суттєво розширюють можливості розв’язання наукових та інженерних задач,не дивлячись на те, що самі рівняння математичних моделей з ускладненнямструктури сучасних виробів стають погано обумовленими та жорсткими, що істотноускладнює їх розв’язування. Узявши виконання рутинних обчислень на себе,комп’ютери звільняють час вченого або інженера для творчості: формулюваннязадач і генерування гіпотез, аналізу та інтерпретації результатів розрахункутощо.
Чисельніметоди забезпечують системний формалізований підхід до розв’язання математичнихзадач. Проте за умов їх ефективного використання окрім уміння присутня і деякачастка мистецтва, що залежить від здібностей користувача, оскільки длярозв’язання кожної математичної задачі існує декілька можливих чисельнихметодів і їх програмних реалізацій для різних типів комп’ютерів. На жаль, дляобрання ефективного способу розв’язання поставленої задачі лише інтуїціїзамало, потрібні глибокі знання і певні навички. Існує декілька переконливихпричин, що мотивують необхідність глибокого вивчення чисельних методівмайбутніми фахівцями у галузі комп’ютерно-системної інженерії та прикладноїматематики.
Чисельніметоди є надзвичайно потужним інструментарієм для розв’язання проблемних задач,що описуються довільними нелінійними диференціально-алгебраїчними рівняннямивеликої розмірності, для яких в даний час не існує аналітичних рішень. Освоївшитакі методи, майбутній фахівець набуває здібностей до системного аналізу черезматематичне моделювання найскладніших задач сучасної науки і техніки.
Усвоїй майбутній професійній діяльності такий фахівець у першу чергу орієнтуватиметьсяна використання пакетів сучасних обчислювальних програм, причому те, наскількиправильно він буде їх застосовувати, безпосередньо залежатиме від знання ірозуміння ним особливостей і обмежень, властивих чисельним методам, що реалізованів пакеті. Може трапитися, що одна й та сама математична задача за допомогоюпевного програмно-технічного комплексу буде одним фахівцем успішно розв’язана,а іншим — ні, оскільки в сучасних пакетах передбачено їх налагоджування підконкретну задачу.
Можез’ясуватися, що низку задач неможливо розв’язати з використанням наявнихпакетів програм. Якщо майбутній фахівець знає чисельні методи і володієнавичками програмування, він буде в змозі самостійно провести розробкунеобхідного алгоритму і програмно його реалізувати, вбудувавши в обчислювальнийкомплекс.
Вивченнячисельних методів стимулює освоєння самих комп’ютерів, оскільки найкращимспособом навчитися програмувати є написання комп’ютерних програм власноруч.Правильно застосувавши чисельні методи, майбутній фахівець зможе пересвідчитисяу тому, що комп’ютери успішно розв’язують його професійні задачі. При цьому вінсам відчує вплив похибок обчислень на результат і навчиться контролювати ціпохибки.
Вивченнячисельних методів сприяє також переосмисленню і більш глибокому розуміннюматематики в цілому, оскільки однією із задач чисельних методів є зведенняметодів вищої математики до виконання простих арифметичних операцій.
Хочаіснує безліч чисельних методів, усі вони (як і алгоритми, що їм відповідають) маютьбагато спільних властивостей і характеристик. Чисельні методи:
передбачають проведення великоїкількості рутинних арифметичних обчислень за допомогою рекурсивнихспіввідношень, що використовуються для організації ітерацій, тобто повторюваних циклів обчислень зі зміненимипочатковими умовами для поліпшення результату;
направлені на локальне спрощення задачі,коли, наприклад, використовувані нелінійні залежності лінеаризуються задопомогою своїх обчислених похідних або похідні замінюються різницевимиапроксимаціями;
значно залежать від близкостіпочаткового наближення (або декількох наближень), необхідного для початкуобчислень до розв’язку, від властивостей нелінійних функцій, яківикористовуються в математичних моделях, що накладає обмеження (длязабезпечення єдиного розв’язку) на їх диференційованість, на швидкість змінифункцій та ін.;
Чисельніметоди характеризуються:
різною швидкістюзбіжності, тобто числомітерацій, виконання яких необхідне для отримання заданої точності розв’язку;
різною стійкістю,тобто збереженням достовірності розв’язку під час подальших ітерацій;
різною точністюотримуваного розв’язку в разі виконання однакового числа ітерацій або циклівобчислень.
Чисельніметоди розрізняються:
за широтою і легкістю застосування,тобто за ступенем своєї універсальностіта інваріантності длярозв’язання різних математичних задач;
за складністюїх програмування;
за можливостями використання у разі їхреалізації наявних бібліотек функцій і процедур, створених для підтримки різнихалгоритмічних мов;
за ступенемчутливості до поганообумовлених (або некоректних) математичних задач, коли малим змінам вхіднихданих можуть відповідати великі зміни розв’язку.
1.Теоретична частина
1.1Метод Гауса
Метод Гауса (абометод послідовного виключення невідомих) застосовний для розв’язання системлінійних рівнянь, в яких число невідомих може бути або рівно числу рівнянь, абовідмінно від нього.
Система т лінійнихрівнянь з п невідомими має вигляд:
/>
x1, x2., xn –невідомі.
ai j-коефіцієнти при невідомих.
bi — вільні члени(або праві частини)
Системалінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною,якщо вона не має розв’язків.
Суміснасистема називається визначеною, якщо вона має єдине розв’язок і невизначеною,якщо вона має незліченну безліч розв’язків.
Двісумісні системи називаються рівносильними, якщо вони мають одну і ту ж множинурозв’язків.
Доелементарних перетворень системи віднесемо наступні:
1. зміна місцями два будь-яких рівнянь;
2. множення обох частин будь-якого з рівнянь на довільне число,відмінне від нуля;
3. збільшення до обох частин одного з рівнянь системи відповіднихчастин іншого рівняння, помножених на будь-яке дійсне число.
Елементарніперетворення переводять систему рівнянь в рівносильну їй.
Дляпростоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьоманевідомими у разі, коли існує єдиний розв’язок:
Данасистема:
/> (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) Записуємо коефіцієнти даної системи в чотирьох рядках і п’ятистовпцях розділу І таблиці 1.
2) Додаємо всі коефіцієнти по рядку і записуємо суму в стовпчик />(стовпчикконтролю), наприклад />.
3) Ділимо всі числа, які стоять в першому рядку, на /> і результати /> записуємо вп’ятому рядку розділу І.
4) Обчислюємо /> і робимо перевірку. Якщообчислення ведуться з постійним числом знаків після коми, то числа /> і /> не повинні відрізнятисяне більше ніж на одиницю останнього розряду. В іншому випадку потрібноперевірити дії пункту 3).
5) По формулам (2.4) обчислюємо коефіцієнти:
/>
Результатизаписуємо в перші три рядки розділу ІІ.
6) Робимо перевірку. Сума елементів кожного рядка /> /> не повинна відрізнятисявід /> більшечим на одиницю останнього розряду (якщо всі обчислення ведуться з постійнимчислом знаків після коми).
7) Ділимо всі елементи першого рядка розділу ІІ на /> і результати записуємов четвертому рядку розділу ІІ.
8) Робимо перевірку, як в пункті 4).
9) За формулами (2.7) обчислюємо />Результати записуємо в перші дварядки розділу ІІІ.
10) Робимо перевірку, як в пункті 6).
11) Ділимо елементи першого рядка розділу ІІІ на /> і знаходимо числа />. Всірезультати записуємо в третьому рядку розділу ІІІ.
12) Робимо перевірку.
13) Обчислюємо />. Результати записуємо в розділіIV.
Оберненийхід.
1) В розділі V записуємо одиниці, як це показано в таблиці 1.
2) Обчислюємо />
3) Для обчислення значення /> використовуємо лише рядкирозділів І, ІІ, ІІІ, що містять одиниці, починаючи з останньої. Так, дляобчислення /> помножимо/> на /> і результати віднімаємоз />. Прицьому одиниці, розставлені в розділі V, допомагають знаходити для />відповіднікоефіцієнти в помічених рядках.
Такимчином,
/>.
4) Обчислюємо />, для чого використовуємо елементипоміченого рядка розділу ІІ:
/>
5) Обчислюємо />, для чого використовуємо елементипоміченого рядка розділу І: />
Аналогічнопроводиться обернений хід в контрольній системі. Розв’язок цієї системи повиненвідрізнятися від розв’язку даної системи на 1 (з точністю до одиниці останньогорозряду): />
Цейконтроль здійснюється за допомогою стовпця />
Такимже чином реалізується компактна схема Гауса для систем з іншим числомневідомих. Компактна схема Гауса особливо потрібна при одночасному розв’язаннідекількох систем, які відрізняються лише стовпцями вільних членів, що маємісце, наприклад, при обчисленні елементів оберненої матриці.
/>
Компактнасхема Гауса для системи (2.12). Таблиця 2.
1.3 МетодГауса з вибором головного елемента
1. Основна ідея методу. Може трапитись, що система
Ax=f (1)
де A- матриця m*m, x = (x1, x2...,xm) — шуканий вектор
f=(f1, f2..., fm) -заданий вектор.
маєєдиний розв’язок, хоча який-небудь з кутового мінору матриці А рівний нулю. Вцьому випадку звичайний метод Гауса виявляється непридатним, але може бутизастосований метод Гауса з вибором головного елементу.
Основнаідея методу полягає в тому, щоб на черговому кроці виключати не наступне пономеру невідоме, а те невідоме, коефіцієнт при якому є найбільшим по модулю.Таким чином, як провідний елемент тут вибирається головний, тобто найбільший помодулю елемент. Тим самим, якщо />, то в процесі обчислень невідбуватиметься ділення на нуль.
Різніваріанти методу Гауса з вибором головного елементу проілюструємо на прикладісистеми з двох рівнянь:
/> (2)
/>
Припустимо,що />. Тодіна першому кроці виключатимемо змінне />. Такий прийом еквівалентний тому,що система (2) переписується у вигляді:
/> (3)
/>
і до(3) застосовується перший крок звичайного методу Гауса. Вказаний спосібвиключення називається методом Гауса з вибором головного елементу по рядку. Вінеквівалентний застосуванню звичайного методу Гауса до системи, в якій накожному кроці виключення проводиться відповідна перенумерация змінних.
Застосовуєтьсятакож метод Гауса з вибором головного елементу по стовпцю. Припустимо, що />. Перепишемосистему (2) у вигляді:
/>
/>
і донової системи застосуємо на першому кроці звичайний метод Гауса. Таким чином,метод Гауса з вибором головного елементу по стовпцю еквівалентний застосуваннюзвичайного методу Гауса до системи, в якій на кожному кроці виключенняпроводиться відповідна перенумерация рівнянь.
Інодізастосовується і метод Гауса з вибором головного елементу по всій матриці, колияк ведучий вибирається максимальний по модулю елемент серед всіх елементівматриці системи.
2. Матриці перестановок. Раніше було показано, щозвичайний метод Гауса можна записати у вигляді:
/> />
де /> --елементарні нижні трикутні матриці. Щоб отримати аналогічний запис методу Гаусаз вибором головного елементу, необхідно розглянути матриці перестановок.
Означення1. Матрицеюперестановок Р називається квадратна матриця, у якої в кожному рядку і вкожному стовпці тільки один елемент відмінний від нуля і рівний одиниці.
Означення2. Елементарноюматрицею перестановок />називається матриця, отримана зодиничної матриці перестановкою к-го і l-го рядків.
Наприклад,елементарними матрицями перестановок третього порядку є матриці:
/>
Можнавідзначити наступні властивості елементарних матриць перестановок, витікаючібезпосередньо з їх визначення.
1) Добуток двох (а отже, і будь-якого числа)елементарних матриць перестановок є матриця перестановок (не обов'язковоелементарною).
2) Для будь-якої квадратної матриці А матрицявідрізняється від А перестановкою к-го і l-го стовпців.
3) Для будь-якої квадратної матриці А матрицявідрізняється від А перестановкою к-го і l-го стовпців.
Застосуванняелементарних матриць перестановок для опису методу Гауса з вибором головногоелементу по стовпцю можна пояснити на наступному прикладі системи третьогопорядку:
/> (4)
Системамає вигляд (1), де
/> (5)
Максимальнийелемент першого стовпця матриці А знаходиться в другому рядку. Тому требапоміняти місцями другий і перший рядки і перейти до еквівалентної системи
/> (6)
Систему(6) можна записати у вигляді
/> (7)
тобтовона виходить з системи (4) шляхом множення на матрицю перестановок
/>
Далі,до системи (6) треба застосувати перший крок звичайного методу виключенняГауса. Цей крок еквівалентний множенню системи (7) на елементарну нижнютрикутну
/>
Врезультаті від системи (7) перейдемо до еквівалентної
/> (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)доведена. Воно означає, що метод Гауса з вибором головного елементу по стовпцюеквівалентний звичайному методу Гауса, застосованому до матриці РА, тобто досистеми, отриманої з початкової системи перестановкою деяких рівнянь.
3. Загальний висновок. Результат, отриманий ранішедля дуже приватного прикладу, справедливий і у разі загальної системи рівнянь(1).
Асаме, метод Гауса з вибором головного елементу по стовпцю можна записати увигляді:
/> (20)
де /> - елементарніматриці перестановок такі, що /> і /> — елементарні нижні трикутніматриці.
Звідси,використовуючи співвідношення перестановленості, аналогічні (19), можнапоказати, що метод Гауса з вибором головного елементу еквівалентний звичайномуметоду Гауса, застосованому до системи
PAx=Pf (21)
де Р- деяка матриця перестановок.
Теоретичнеобгрунтування методу Гауса з вибором головного елементу міститься в наступнійтеоремі.
ТЕОРЕМА1.Якщо /> тоіснує матриця перестановок Р така, що матриця РА має відмінні від нуля кутовімінори.
Наслідок.Якщо/> то існуєматриця престанавок Р така, що справедливе розкладання
РА=LU, (22)
де L-нижня трикутна матриця з відмінними від нуля діагональними елементами і U- верхнятрикутна матриця з одиничною головною діагоналлю. В цьому випадку для розв’язаннясистеми (1) можна застосовувати метод Гауса з вибором головного елементу.
1.4 Алгоритм знаходження рангу матриці
Нехай потрібно обчислити ранг матриці /> розмірів />. Якщо матриця /> нульова, то заозначенням маємо />. В іншому випадку за допомогоюперестановки рядків і стовпців матриці добиваємося того, щоб у лівому верхньомукуті матриці стояв ненульовий елемент. Отже, вважаємо, що />.
Першийрядок залишаємо без змін. До другого рядка додаємо перший, помножений на число />. У результатідругий рядок приймає вигляд: />
Потімдо третього рядку додаємо перший рядок, помножений на число />. У результаті третійрядок приймає вигляд: />
Процеспродовжуємо до тих пір, поки не отримаємо нуль на першому місці в останньомурядку. Перетворена матрицямає вигляд:
/>
Якщо всі рядки, починаючи з другої, вотриманій матриці нульові, то її ранг дорівнює 1, тому що є мінор першогопорядку, відмінний від нуля />. В іншому випадку перестановкою рядків і стовпцівматриці з номерами більше одиниці, домагаємося, щоб другий елемент другогорядка був відмінний від нуля. Отже, вважаємо, що />.
Перший і другий рядки залишаємо без змін. До третього рядка додаємо другий, помножений на число />. В результаті отримаємо, що другий елемент третьогорядка дорівнює нулю. Потім до четвертого рядка додаємо другий, помножений начисло />, і т.д. В результаті отримуємо матрицю:
/>
Якщо всі рядки, починаючи з третього,нульові, то />, так як мінор:
/>
В іншому випадку перестановкою рядків істовпців з номерами, більшими двох, домагаємося, щоб третій елемент третьогорядка був відмінний від нуля. Далі, додаванням третього рядка, помноженого навідповідні числа, до рядків з великими номерами отримуємо нулі в третьомустовпці, починаючи з четвертого елемента, і т.д.
На деякому етапі ми прийдемо до матриці, уякої всі рядки, починаючи з />-ого, дорівнюють нулю (або відсутні при />), а мінор у перших /> рядках і перших /> стовпцях є визначником трикутноїматриці з ненульовими елементами на діагоналі. Ранг такої матриці дорівнює />. З цьогослідує, що />.
Зауваження 1. У запропонованому алгоритмізнаходження рангу матриці всі обчислення повинні здійснюватись без заокруглень.Наскільки завгодно мала зміна хоча б в одному з елементів проміжних матрицьможе призвести до того, що отримана відповідь буде відрізнятися від рангувихідної матриці на кілька одиниць.
Зауваження 2. Якщо у вихідній матриціелементи були цілими числами, то й обчислення зручно проводити без використаннядробів. Тому на кожному етапі доцільно множити рядки на такі числа, щоб приобчисленнях дроби не виникали.
Властивість 1. При транспонування матриці їїранг не змінюється.
Властивість 2. Ранг матриці не змінюєтьсяпри перестановці її стовпців (рядків).
Властивість 3. Ранг матриці не змінюєтьсяпри збільшенні всіх елементів її стовпця (рядка) на відмінне від нуля число.
Властивість 4. Ранг матриці незміниться, якщо до одного з її стовпців (рядка) додати інший стовпець (рядок),помноживши його (її) на деяке число.
Властивість 5. Ранг матриці незміниться, якщо видалити з неї стовпець (рядок), що складається з одних нулів.
Властивість 6. Ранг матриці незміниться, якщо видалити з неї стовпець (рядок), що є лінійною комбінацієюінших стовпців (рядків).
Розділ2. Практична реалізація
2.1 Розв’язаннясистеми рівнянь методом Гауса
Приклад1. Знайдемо розв’язок системи рівнянь методом Гауса:
/>
Сформуєморозширену матрицю:
/>
Прямийхід методу Гауса:
Крок1.
Розділимоперший рядок матриці на />
Отримаємоматрицю наступного вигляду:
/>
Крок2.
Віднімаємовід другого рядка перший рядок, помножений на />
Віднімаємовід третього рядка перший рядок, помножений на />
Отриманамодифікована матриця:
/>
Крок3.
Розділимодругий рядок на />:
/>
Крок4.
Віднімаємовід третього рядка другий рядок, помножений на />
/>
Крок5.
Розділимотретій рядок матриці на />:
/>
Прямийхід метода Гауса закінчено. Обернений хід метода Гауса. Утворюємо нулі вищеголовної діагоналі.
Крок6.
Віднімаємовід другого рядка третій, помножений на /> Віднімаємо від першого рядкатретій, помножений на />:
/>
Крок7.
Віднімаємовід першого рядка другий, помножений на />:
/>
Запишемосистему рівнянь по останній розширеній матриці:
/>
Змінніx1, x2, x3 залишемо в лівій частині рівняння,а х4 перенесимо вправо. Остаточний вигляд системи буде такий:
/>
де х4– вільна змінна.
Данасистема рівнянь має безліч розв’язків.
Приклад2. Розв’яжемо СЛАР методом Гауса в MS Excel:
/>
Цей метод розв'язання систем лінійнихрівнянь придатний для розв'язання систем з будь-яким числом рівнянь іневідомих.
Запишемонашу СЛАР в матричній формі:
/>
/>
Отжемаємо:
/>
Помічений елемент матриці />, оскільки він не дорівнюєнулю отже виключаємо змінну /> і утворюємо нулі нижче />, отримуємонаступну матрицю:
/>
Якщож />, то потрібнопереставляти рядки. Вибираємо перший ненульовий елемент в стовпчику, щознаходиться нижче від розв’язувального елемента і переставляємо цей рядок нарядок з нульовим елементом />
Аналогічнопродовжуємо до отримання розв’язку СЛАР. В результаті отримаємо наступнутабличку:
/>
/>
Отжев результаті отримали:
/>, де /> - небазиснізмінні.
Загальний розв’язок системи буде матинаступний вигляд:
/>, де /> - довільні.
Приклад3. Розв’язання СЛАР з вибором головного елемента в MS Excel:
/>
Сутьданого методу полягає в тому, що на кожному кроці обирається напрямний рядок змаксимальним абсолютним значенням розв’язувального елемента. Його перевагами упорівнянні з методом Гауса є те, що в результаті отримаємо меншу накопиченупохибку за рахунок ділення напрямних рядків на більші елементи, але для поганообумовлених СЛАР похибка як і в методі Гауса може бути суттєвою.
Знаходження розв’язку за допомогою методуголовного елемента описується наступним чином:
/>
/>
/>
Загальний розв’язок системи має вигляд:
/>, де /> - довільні.
Відповідіотриманні при розв’язуванні ідентичні, але кількість кроків виконаних, приреалізації метода головного елемента, дещо більша ніж в методі Гауса.
2.2 Обчисленнярангу матриці
Приклад 4. Знайти ранг матриці:
/>
Розв’язання. Перший рядок залишаємо беззмін. Щоб уникнути появи дробів, помножимо другу, третю та четверту рядки на 2:
/>
Перший рядок помножимо на /> і додамо до другого. Отримаємо рядок />. Перший рядок помножимо на /> і додамо до третього. Отримаєморядок />. Перший рядок помножимо на /> і додамо до четвертого.Отримаємо рядок />. У результаті маємо матрицю:
/>
Другу рядок залишаємо без змін. На третьомурядку додаємо другий, помножений на 2. Отримаємо рядок />. До четвертого рядка додаємо другий. Отримаємо нульовий рядок. Перетворена матриця маєвигляд:
/>
Поміняємо місцями третій і четвертийстовпчики:
/>
Базисний мінор матриці /> стоїть у перших трьох стовпцях і перших трьох рядках,/>. Отже, />.
2.3Опис та інструкція по використанню програми Gauss
Данапрограма реалізована в інтегрованому середовищі програмування Visual Studio2008 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)
privatevoid MakeNullD- утворення нулів нижче розв’язувального елемента в прямому ходіГауса і утворення нулів вище розв’язувального елемента в обереному ході методу.
Списоквикористаних джерел та літератури
1. Тарасов В.Н., Бахарева Н.Ф. Численные методы.Теория, алгоритмы, программы. – Оренбург: ИПК ОГУ, 2003.
2. Курош А.Г., “ Курс высшей алгебры ”, изд. 10, «Наука», Москва,1971 г.
3. Овчинников П.Ф., Яремчук Ф.П., Михайленко В.М… Высшая математика– К.: Вища шк. Главное изд., 1987 г.
4. Копченова Н.В., Марон И.А. Вычислительная математика в примерах изадачах.- М.: Наука
5. Г.Н.Воробьева, А.Н. Данилова. Практикум по вычислительнойматематике – Москва «Высшая школа», 1990.
6. Л.И.Турчак. Основы численных методов – Москва «Наука», 1987.
7. Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи вінформатиці – Київ «Питер», 2006.