ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Чисельне розв’язання систем лінійних алгебраїчних рівнянь

Нехай задана система n лінійних рівнянь з n невідомими:

(1)

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

Запишемо систему (1) в матричній формі:

, (2)

де А - матриця коефіцієнтів при невідомих;

У - вектор-стовпець вільних членів;

Х - вектор-стовпець невідомих.

Вони мають вид:

; ; . (3)

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

прямі методи (метод Крамера, метод Гаусса, метод оберненої матриці);

ітераційні методи (метод простої ітерації, метод Зейделя).

Прямі методи дозволяють одержати точний розв'язок системи за кінцеве число проміжних дій. Ітераційні методи дозволяють одержати приблизний розв'язок системи за кінцеве число наближень (ітерацій) із заданою похибкою результату.

Метод Гаусса

Метод Гаусса застосовується для розв’язання системи лінійних алгебраїчних рівнянь (1). У матричній формі ця система має вид (3).

Використовуємо той факт, що розв’язок системи не зміниться при виконанні кожної з наступних операцій:

а) перестановка двох рівнянь місцями;

б) множення одного з рівнянь на число, яке не дорівнює нулю;

в) віднімання одного рівняння, помноженого на деяке число, від іншого.

Якщо , поміняємо місцями перше рівняння з таким -м рівнянням, що . Тепер коефіцієнт у першому рівнянні при першій невідомій, відмінний від нуля. Позначимо його через і називатимемо ведучим елементом першого кроку. Розділимо перше рівняння на ведучий елемент. Потім віднімемо його від -го рівняння (k=2, 3 ..., п) отриманої системи, заздалегідь помноживши на .

Після таких перетворень перший стовпчик коефіцієнтів рівнянь складатиметься з одиниці на першому місці і нулів на інших місцях.

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

Наступний крок виконуємо для останніх ( ) рівнянь і так далі.

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

........................................... . (4)

З останнього рівняння можна отримати значення невідомої .

Інші можна знайти, послідовно підставляючи значення у рівняння , потім значення і у рівняння з номером та ін.

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

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

Після ряду перетворень система (4) буде зведена до виду:

Розглянемо випадок, коли на черговому кроці не вдається вибрати ведучий елемент. Це відбудеться в тому випадку, коли на черговому r-му кроці всі коефіцієнти при невідомій у рівняннях r, r+1, ..., п виявляться рівними нулю, що є наслідком лінійної залежності рядків вихідної матриці А. У цьому випадку можна умовно вважати ведучий елемент нульовим і продовжити зведення рівнянь до трикутного вигляду. Отримані рівняння будуть відрізнятися від рівнянь (4) тим, що в деяких місцях на діагоналі будуть стояти коефіцієнти, які дорівнюють нулю, а не одиниці. Відзначимо, що в цьому випадку рівняння (1) або не мають розв'язків, або мають нескінченну множину розв'язків.

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

(5)

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

, ( ); , ( ). (6)

Тепер з третього рівняння системи (6) потрібно виключити . Для цього помножимо друге рівняння на і додамо результат до третього. Отримаємо:

; . (7)

Матриця системи (7) має трикутний вигляд. На цьому закінчується прямий хід методу Гауса.

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

Зворотний хід починається з вирішення третього рівняння системи (7):

.

Використовуючи це значення, можна знайти з другого рівняння, а потім з першого:

, .

Аналогічно будується обчислювальний алгоритм для лінійної системи з довільним числом рівнянь.

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

Метод Гаусса-Зейделя

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

Проілюструємо спочатку цей метод на прикладі розв’язання системи:

(8)

Припустимо, що діагональні елементи відмінні від нуля (інакше можна переставити рівняння).

Виразимо невідомі відповідно з першого, другого і третього рівнянь системи (8):

. (9)
. (10)
. (11)

Задамо деякі початкові (нульові) наближення значень невідомих: , :

.

Використовуючи це значення для і наближення для знаходимо з (10) перше наближення для :

.

І нарешті, використовуючи обчислені значення , , за допомогою виразу (11) обчислимо перше наближення для :

.

На цьому закінчується перша ітерація розв’язання системи (9) – (11).

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

Наближення з номером можна обчислити, знаючи наближення з номером , наступним чином:

, , .

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

Приклад.

Розв’язати за допомогою методу Гаусса-Зейделя наступну систему рівнянь:

Легко перевірити, що розв’язок даної системи наступний: .

Розв’язок

Виразимо невідомі відповідно з першого, другого і третього рівнянь:

, , .

У якості початкового наближення (як це зазвичай робиться) приймемо :

, , .

Аналогічно обчислимо наступні наближення:

, , .

Ітераційний процес можна продовжувати до отримання малої різниці між значеннями невідомих в двох послідовних ітераціях.

Розглянемо тепер систему лінійних рівнянь з невідомими. Запишемо її у виді:

, ( ).

Тут також будемо припускати, що всі діагональні елементи відрізняються від нуля. Тоді відповідно до методу Гаусса-Зейделя -е наближення до розв’язку можна представити у виді:

, ( ). (12)

Ітераційний процес продовжується до тих пір, доки всі значення не стануть близькими до . Як критерій завершення ітерацій використовується одна з умов (13) – (15).

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

. (13)
. (14)
при . (15)

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

, ( ). (16)

При цьому хоч би для одного рівняння нерівність повинна виконуватися строго. Ці умови є достатніми для збіжності методу, але вони не є необхідними, тобто для деяких систем ітерації сходяться і при порушенні умов (16).

Завдання для самостійної роботи

Дослідити і, якщо розв’язок існує, розв'язати систему лінійних алгебраїчних рівнянь методом Гаусса та Гаусса-Зейделя. Якщо до заданої системи пропонований метод не можна застосувати, змінити деякі коефіцієнти.

Варіанти завдання надані у вигляді .

№ варіанту

Лабораторна рОбота №4

Тема:Нелінійні рівняння

Теоретичні відомості

Проблема знаходження кореня нелінійних рівнянь виду:

(1)

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

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

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

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

то говорять, що ітераційний процес збігається.

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

Всі можливі випадки при уточненні кореня можна класифікувати за допомогою таблиці 1.

Таблиця 1

№ вар. Схема Нульове набли-ження
метод хорд метод дотичних
I + + +
II +
III + +
IV + +

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

Розглянемо деякі з перелічених вище методів.

Метод хорд

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

Розглянемо випадок, коли перша і друга похідні мають однакові знаки, тобто (рис.1). Як нульове наближення кореня в даному випадку приймається ліва межа інтервалу ізольованого кореня, тобто .

Рисунок 1 – Метод хорд, у випадку коли мають однакові знаки

Перше, друге і інші наближення кореня знаходяться з формули, яка витікає з рівняння хорди. Рівняння хорди АВ записується як рівняння прямої, яка проходить через дві крапки з відомими координатами:

. (2)

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

. (3)

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

(4)

та інше.

1. Якщо мають місце варіанти I і II, тоді на відрізку , то наближені значення корінів знаходитимуться усередині відрізків , , , …, тобто нерухомим кінцем відрізка буде кінець , а наближені значення коренів будуть знаходитися за формулою:

, (5)

при цьому (рис. 1).

2. Якщо мають місце варіанти III і IV, тоді на відрізку , то наближені значення коренів будуть знаходитися усередині відрізків , , …, тобто нерухомим кінцем відрізка буде кінець , а наближені значення коренів будуть знаходитися за формулою:

. (6)

при цьому (рис. 2).

Рисунок 2 – Метод хорд, у випадку коли мають різні знаки

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

. (7)

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

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти