Реферат
на тему:
Точні методи розв'язання систем лінійних алгебраїчних рівнянь (СЛАР)
Введення
Ця лабораторна робота включає в себе два точних методу рішення систем лінійних алгебраїчних рівнянь (СЛАР):
Метод Гаусса.
Метод Холецкого.
Також дана лабораторна робота включає в себе: опис методу, застосування методу до конкретного завдання (аналіз), код програми вирішення перерахованих вище методів на мові програмування Borland C + + Builder 6. p> Опис методу:
Метод рішення СЛАР називають точним (прямим), якщо він дозволяє отримати рішення після виконання кінцевого числа елементарних операцій. До прямих методів відносять метод Крамера, метод Гаусса, метод Холецкого та інші. Основним недоліком прямих методів є те, що для знаходження рішення необхідно виконати велику кількість операцій.
Спочатку розглянемо найбільш поширений метод рішення СЛАР - метод Гаусса, що складається в послідовному виключенні невідомих. p> Нехай дана система рівнянь
(1)
Процес рішення за методом Гауса складається з двох етапів. На першому етапі (прямий хід) система приводиться до східчастого увазі:
В
де kn, aii 0, i =, АII - головний елемент системи.
На другому етапі (зворотний хід) йде послідовне визначення невідомих з цієї ступінчастою системи.
Прямий хід.
Покладемо а11 0, якщо а11 = 0, то першим в системі запишемо рівняння, в якому а11 0.
Розставимо рівняння системи таким чином, щоб коефіцієнт при х1 мав найбільше значення (іншими словами відсортуємо систему по зменшенням).
Перетворимо систему, виключивши невідоме х1 у всіх рівняннях, крім першого (використовуючи елементарні перетворення системи). Для цього помножимо обидві частини першого рівняння на і складемо почленно з другим рівнянням системи. Потім помножимо обидві частини першого рівняння на і складемо з третім рівнянням системи. Продовжуючи цей процес, отримуємо систему
В
Тут (i, j =) - нові значення коефіцієнтів і правих частин, які виходять після першого кроку.
Аналогічним чином, вважаючи головним елементом 0, виключимо невідоме х2 з усіх рівнянь системи, крім першого і другого, і т.д. Продовжуємо цей процес поки це можливо.
Якщо в процесі приведення системи (1) до східчастого увазі з'являться нульові рішення (рівності виду 0 = 0) їх відкидають. Якщо ж з'явиться рівняння виду 0 = bi, а bi 0, то це говорить про несумісність системи.
Другий етап (зворотний хід) полягає у вирішенні ступінчастою системи. В останньому рівнянні цієї системи виражає перші невідоме xk через інші невідомі (xk +1, ..., Xn). Потім підставляємо значення xk в передостаннє рівняння системи і висловлюємо xk-1 через (Xk +1, ..., xn), потім знаходимо xk-2, ..., x1. p> Тепер розглянемо другий точний метод розв'язання СЛАР - метод Холецкого (метод квадратних коренів). p> Він застосовується у випадку, якщо матриця системи є симетричною і позитивно визначеною. В основі методу лежить алгоритм спеціального LU -розкладання матриці А, де L - нижня трикутна матриця, а U - верхня трикутна матриця (якщо головний мінор НЕ дорівнює 0, то існує розкладання, причому воно єдино). p> Розбиття матриці А = на верхню і нижню наприклад буде виглядати так
L = і U =.
У результаті перетворень матриця А приводиться до увазі A = (де - транспонована матриця). Якщо розкладання отримано, то рішення системи зводиться до послідовного вирішенню двох систем з трикутними матрицями: і. Для знаходження коефіцієнтів матриці L невідомі коефіцієнти матриці прирівнюють відповідних елементів матриці A . Потім послідовно знаходять необхідні коефіцієнти за формулами:
, i = 2, 3, ..., m,
, i = 3, 4, ..., m,
, i = k +1, ..., m,
В
Застосування методу до конкретного завдання (аналіз)
Складаючи задачі на мові програмування Borland C + + Builder 6 для реалізації точних методів розв'язання СЛАР я враховував різну кількість рівнянь в системі (розмірність матриці задавав рівним nxn). Але для перевірки результатів використовував рівняння
(для перевірки рішення методом Гаусса) (2) і
(для перевірки рішення методом Холецкого) (3)
Методи істотно відрізняються один від одного і як описано вище мають різні підходи для вирішення СЛАР. Реалізувавши методи програмним шляхом і зробивши перевірки, я прийшов до висновку, що не всі СЛАР можна вирішити методом Холецкого. Як описано вище метод Холецкого застосовується для розв'язання систем, які є симетричними і позитивно визначеними. У свою чергу методом Гауса вирішуються практично всі системи. Винятки становлять невироджені матриці, тобто ті матриці, визначник яких не дорівн...
