Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютеризовані системи
Кафедра:
Комп'ютеризовані системи автоматики
Інформація про роботу
Рік:
2007
Тип роботи:
Інші
Предмет:
Комп’ютерні методи дослідження систем керування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
СИСТЕМИ НЕЛІНІЙНИХ РІВНЯНЬ.
МЕТОД НЬЮТОНА ТА -АЛГОРИТМ
Інструкція до лабораторної роботи № 4
з курсу “Комп’ютерні методи дослідження систем керування”
для студентів базового напрямку 6.0914
“Комп’ютеризовані системи, автоматика і управління”
та базового напрямку 050201 “Системна інженерія”
Затверджено
на засіданні кафедри
“Комп’ютеризовані
системи автоматики”
Протокол № __ від __.___.2007
Львів 2007
Системи нелінійних рівнянь. Метод Ньютона та -алго ритм: Інструкція до лабораторної роботи № 4 з курсу “Комп’ютерні методи дослідження систем керування” для студентів базового напрямку 6.0914 “Комп’ютеризовані системи, автоматика і управління” та базового напрямку 050201 “Системна інжене рія” / Укл.: У.Ю. Дзелендзяк, А.Г. Павельчак, В.В. Самотий – Львів: НУЛП, 2007. – 40 с.
Укладачі: У.Ю. Дзелендзяк, к.т.н., доцент
А.Г. Павельчак, асистент
В.В. Самотий, д.т.н., професор
Відповідальний за випуск:
А.Й. Наконечний, д.т.н., професор
Рецензент: З.Р. Мичуда, д.т.н., професор
Мета роботи: ознайомитися з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона та екстраполяційним методом – -алгоритмом.
1. Системи нелінійних рівнянь
1.1. Постановка задачі.
Нехай для обчислення невідомих необхідно розв’язати систему нелінійних рівнянь
(1.1)
У векторній формі система (1.1) записується так:
, (1.2)
де , .
Ця задача є значно складнішою, аніж розглянута в лабораторній роботі № 3 задача пошуку коренів нелінійного рівняння з одним невідомим. Але й на практиці вона зустрічається значно частіше, тому що в реальних дослідженням інтерес представляють системи з багатьма параметрами (іноді їх число сягає сотень чи тисяч). Знаходження точного розв’язку системи (1.1), тобто вектора , практично неможливо. Лише в окремих випадках систему (1.1) можна розв’язати безпосередньо. Наприклад, для випадку двох рівнянь іноді вдається виразити одну невідому через іншу й, таким чином, звести задачу до пошуку кореня одного нелінійного рівняння. Тому розв’я зок нелінійних систем шукають переважно лише ітераційними методами. Найпоширеніші серед них: метод простої ітерації, метод Зейделя та метод Ньютона.
Важливим аспектом при розв’язуванні систем нелінійних рівнянь є усвідомлення того, що система може й не мати розв’язку, а у випадку його існування – кількість розв’язків може бути довільною. У загальному випадку складно визначити чи має система розв’язки та скільки їх.
Пояснимо сказане на прикладі такої системи рівнянь
(1.3)
Перше рівняння системи (1.3) задає на площині еліпс, друге рівняння – параболу. Координати крапок перетину цих кривих є розв’язками системи. Якщо значення параметра змінюється від до , то можливі такі варіанти (рис. 1): – система розв’язку немає; – єдиний розв’язок; – два розв’язки; – три розв’язки; – чотири розв’язки.
На рис. 2 зображено трьохмірну ілюстрацію графічного методу пошуку розв’язків системи нелінійних рівнянь (1.3) при . Таким чином, для цієї системи рівнянь будуються поверхні функцій ,
при широкому діапазонові змін , та шукаються крапки перетину цих поверхонь з площиною . Перетини цих функцій на площині і дадуть шукані розв’язки системи нелінійних рівнянь.
1.2. Основні етапи розв’язування.
Як і у випадку рівняння з одним невідомим розв’язування нелінійної системи рівнянь здійснюється у три етапи:
а) локалізація коренів та вибір початкових наближень ;
б) ітераційне уточнення коренів;
в) перевірка умови збіжності ітераційного процесу.
На етапі локалізації для кожного із розв’язків вказують множину, що містить лише цей розв’язок та розміщена в достатньо малій його околиці. Часто в якості такої множини вибирають паралелепіпед чи кулю в -мірному просторі.
Іноді етап локалізації не створює труднощів: відповідні множини можуть бути задані, визначені з фізичних міркувань, зі змісту параметрів чи бути відомими з досвіду розв’язування подібних задач. Однак найчастіше задача локалізації (особливо при великій розмірності ) представляє собою складну проблему, від успішного вирішення якої в основному і залежить можливість пошуку розв’язку системи (1.1). Тому кваліфікація дослідника, розуміння поставленої задачі та досвід розв’язування подібних задач відіграють тут неабияку роль. У більшості випадків етап локалізації вважають завершеним при вдалому виборі початкового наближення .
На другому етапі для пошуку розв’язку із заданою точністю використовують один з ітераційних методів розв’язування нелінійних систем.
Іноді при розв’язуванні нелінійних систем рівнянь вживають додаткових запобіжних заходів. По-перше, щоб мати гарантію, що на кожному кроці ітерацій відбувається наближення до шуканого розв’язку, а по-друге, щоб запобігти використанню великих кроків, які можуть призвести до аварії. Збіжність розв’язку визначається за допомогою значень нелінійних функцій на суміжних ітераціях:
, для . (1.3)
З метою запобігання великих кроків , для накладають обмеження
, для , (1.4)
де – вибраний обмежувач. Якщо модель хороша, то апроксимація буде ефективною при великих значеннях і тому можна вибрати великий обмежувач . Якщо модель погано обумовлена, то апроксимація буде прийнятною лише при малих значеннях і тоді необхідно вибрати мале значення .
2. Метод Ньютона
Узагальнимо метод Ньютона, викладений в інструкції до лабораторної роботи № 3 для уточнення кореня одного нелінійного рівняння, на розв’язування системи нелінійних рівнянь (1.1).
Нехай наближені значення системи (1.1), отримані на попередній ітерації, дорівнюють відповідно . Задача полягає в знаходженні приростів (поправок) до цих значень , завдяки яким наступне наближення до розв’язку системи (1.1) записується у вигляді
. (2.1)
Здійснимо розклад лівих частин рівнянь (1.1) у ряд Тейлора, обмежившись лише лінійними членами відносно приростів (відкинувши члени, що містять другі та вищі похідні)
(2.2)
У правих частинах співвідношень (2.2) значення функцій та їх похідні обчислюються в крапці .
Оскільки у відповідності з (1.1) ліві частини (2.2) повинні перетворюватися в нуль, прирівняємо до нуля і праві частини, тобто знайдемо нове наближення з умови рівності нулю розкладу функцій . У результаті отримаємо таку систему лінійних алгебричних рівнянь відносно приростів
(2.3)
або в матричній формі
, (2.4)
де .
Виразимо з рівняння (2.4) та отримаємо ітераційну формулу методу Ньютона:
, (2.5)
де
(2.6)
матриця Якобі. Метод Ньютона передбачає обертання матриці Якобі.
Наведемо геометричну ілюстрацію методу Ньютона для розв’язування системи рівнянь на прикладі системи (1.3) при . Для цього запишемо рівняння дотичних площин до функцій у крапці
, для . (2.7)
Матриця Якобі (2.6) для системи (1.3) має такий вигляд
. (2.8)
Відповідно рівняння дотичних площин у розгорнутому вигляді будуть мати такий вигляд
або
(2.9)
На рис. 3 зображений випадок невдалого вибору початкового наближення , коли Метод Ньютона закінчується аварією. Дотична площина до функції не має крапок перетину з площиною .
Виберемо інше початкове наближення , зміщене до одного з розв’язків системи.
Перше наближення методу Ньютона (рис. 4) відпо відає крапці перетину між собою усіх трьох площин: двох дотичних площин до функцій , у крапці та площини .
На рис. 5 проілюстровано наступну ітерацію методу Ньютона, на якій отримано наближення . Як бачимо, це наближення приблизилося до шуканого нами одного з розв’язків системи рівнянь.
Збіжність методу Ньютона забезпечується в околиці розв’язку системи рівнянь (1.1) при умові що функції системи , для , є двічі неперервано диферен ційовані, а матриця Якобі цієї системи не вироджена і її детермінант не дорівнює нулю. Випадок, коли детермінант дорівнював нулю, був проілюстрований на рис. 3.
Ітераційний процес методу зупиняють при виконанні умови
, для . (2.10)
Зазначимо, що при обертанні матриці Якобі необхідно використовувати прямі методи розв’язування лінійних алгебричних рівнянь, оскільки ця матриця на кожному кроці методу змінюється, і тому не можна гарантувати, що який-небудь ітераційний метод буде завжди збігатися. Рекомендується використовувати метод Гауса з вибором головного елемента.
Загальний алгоритм методу Ньютона
Ініціалізація одиничної матриці:
для
якщо {}
інакше {}
Обчислення вектора функцій та матриці Якобі :
; …
; … …
для
Метод Гауса
Прямий хід:
для
далі згідно алгоритму методу Гауса
для
для
;
Опис алгоритму
На початку алгоритму задаємо початкове наближення , для , та відносну похибку у відсотках.
Встановлюємо значення для одиничної матриці .
Обчислюємо значення елементів вектора функцій та елементів матриці Якобі .
Здійснюємо обертання матриці Якобі методом Гауса (з вибором головного елемента по рядку, стовпцю чи по всій матриці). Алгоритм обертання матриці методом Гауса наведено в інструкції до лабораторної роботи № 2. Єдиною модифікацією є (замість базової матриці беремо ).
Згідно ітераційної формули обчислюємо наступне наближення , для .
Здійснюємо перевірку умови збіжності. Якщо вона не виконується, то процес уточнення повторюємо (п.3).
Для перевірки вірності роботи алгоритму підставляємо наші знайдені значення в систему рівнянь . Значення функцій , для , мають бути близькими нулю, в залежності від вибраного значення .
3. Модифікації методу Ньютона
3.1. Спрощений метод Ньютона (метод паралельних площин)
Ідея спрощеного методу полягає у тому, що обчислення матриці Якобі та її наступне обертання здійснюємо лише один раз на першій ітерації, а далі використовуємо обернену матрицю Якобі з тими самими значеннями. В результаті отримаємо таку розрахункову формулу для спрощеного методу Ньютона
. (3.1)
У геометричному змісті пошук розв’язку системи здійснюється за допомогою площин паралельних дотичним площинам до функцій системи у крапці початкового наближення .
Загальний алгоритм спрощеного методу Ньютона
Ініціалізація одиничної матриці:
для
якщо {}
інакше {}
Обчислення матриці Якобі :
; … …
для
Метод Гауса
Прямий хід:
для
далі згідно алгоритму методу Гауса
для
Обчислення вектора функцій
; …
для
;
Опис алгоритму
На початку алгоритму задаємо початкове наближення , для , та відносну похибку у відсотках.
Встановлюємо значення для одиничної матриці .
Обчислюємо значення елементів матриці Якобі .
Здійснюємо обертання матриці Якобі методом Гауса (з вибором головного елемента по рядку, стовпцю чи по всій матриці). Алгоритм обертання матриці методом Гауса наведено в інструкції до лабораторної роботи № 2. Єдиною модифікацією є (замість базової матриці беремо ).
Обчислюємо значення елементів вектора функцій .
Згідно ітераційної формули обчислюємо наступне наближення , для .
Здійснюємо перевірку умови збіжності. Якщо вона не виконується, то процес уточнення повторюємо (п.5).
Для перевірки вірності роботи алгоритму підставляємо наші знайдені значення в систему рівнянь . Значення функцій , для , мають бути близькими нулю, в залежності від вибраного значення .
3.2. Метод Ньютона з кінцево-різницевою матрицею Якобі
Часто на практиці обчислення часткових похідних матриці Якобі представляє собою доволі складну, а іноді й нездійсненну задачу. В такому випадку для наближеного обчислення часткових похідних можна спробувати використати формули числового диференціювання. Наприклад, застосувати таку кінцево-різницеву апроксимацію похідної у крапці :
. (3.2)
У найпростішому випадку цього методу кроки , для , не залежать від . Зазначимо, що вибір величини кроків представляє собою не просту задачу. З однієї сторони, вони повинні бути достатньо малими, щоб матриця мала добре наближення, з іншої, вони не можуть бути дуже малими, так як вплив похибок обчислень функцій на похибку формули (3.2) стає катастрофічним (виконується обчислення близьких наближених чисел).
Загальний алгоритм методу Ньютона
з кінцево-різницевою матрицею Якобі
Ініціалізація одиничної матриці:
для
якщо {}
інакше {}
Обчислення вектора функцій та матриці Якобі :
для
для
для
Метод Гауса
Прямий хід:
для
далі згідно алгоритму методу Гауса
для
для
;
Опис алгоритму
На початку алгоритму задаємо початкове наближення , для , та відносну похибку у відсотках.
Встановлюємо значення для одиничної матриці .
Обчислюємо значення елементів вектора функцій та елементів матриці Якобі з кінцевих різниць. Обчислення функцій виконуються у зовнішній програмній процедурі, у яку як вхідні дані поступає вектор невідомих, а вихідними даними служить обчислений вектор функцій.
Здійснюємо обертання матриці Якобі методом Гауса (з вибором головного елемента по рядку, стовпцю чи по всій матриці). Алгоритм обертання матриці методом Гауса наведено в інструкції до лабораторної роботи № 2. Єдиною модифікацією є (замість базової матриці беремо ).
Згідно ітераційної формули обчислюємо наступне наближення , для .
Здійснюємо перевірку умови збіжності. Якщо вона не виконується, то процес уточнення повторюємо (п.3).
Для перевірки вірності роботи алгоритму підставляємо наші знайдені значення в систему рівнянь . Значення функцій , для , мають бути близькими нулю, в залежності від вибраного значення .
3.3. Метод січних
Метод січних ґрунтується на використанні формули (3.2) для обчислення матриці Якобі за кінцево-різницевою схемою, де
, для . (3.3)
Метод січних є двокроковим: для обчислення чергового обчислення використовуються два попередніх наближення та . Перед початком обчислень необхідно задати два початкових наближення та , для .
Наведемо геометричну ілюстрацію методу січних для розв’язування системи рівнянь на прикладі системи (1.3) при . Як початкові наближення візьмемо та . Числові значення матриці Якобі та вектора кроку будуть такими
; . (3.4)
Як видно з рис. 6 січні площини точно перетинають графіки функцій у крапках та . Наближення визначається як крапка перетину одразу трьох площин.
Загальний алгоритм методу січних
Ініціалізація одиничної матриці:
для
якщо {}
інакше {}
Обчислення вектора кроку :
для
Обчислення вектора функцій та матриці Якобі :
для
для
для
Метод Гауса
Прямий хід:
для
далі згідно алгоритму методу Гауса
для
для
; ;
Опис алгоритму
На початку алгоритму задаємо початкове наближення , , для , та відносну похибку у відсотках.
Встановлюємо значення для одиничної матриці .
Обчислюємо значення елементів вектора кроку .
Обчислюємо значення елементів вектора функцій та елементів матриці Якобі з кінцевих різниць. Обчислення функцій виконуються в зовнішній програмній процедурі, у яку як вхідні дані поступає вектор невідомих, а вихідними даними служить обчислений вектор функцій.
Здійснюємо обертання матриці Якобі методом Гауса (з вибором головного елемента по рядку, стовпцю чи по всій матриці). Алгоритм обертання матриці методом Гауса наведено в інструкції до лабораторної роботи № 2. Єдиною модифікацією є (замість базової матриці беремо ).
Згідно ітераційної формули обчислюємо наступне наближення , для .
Здійснюємо перевірку умови збіжності. Якщо вона не виконується, то процес уточнення повторюємо (п.3).
Для перевірки вірності роботи алгоритму підставляємо наші знайдені значення в систему рівнянь . Значення функцій , для , мають бути близькими нулю, у залежності від вибраного значення .
4. Методи екстраполяції
Нехай є скалярною послідовністю, що збігається до границі . Метод екстраполяції полягає в перетворенні цієї послідовності в нову послідовність , шляхом перетворення . Вважають, що перетворення прискорює збіжність послідовності , якщо і тільки якщо
. (4.1)
Тоді ми можемо сказати, що послідовність швидше збігається до ніж .
Найперші методи екстраполяції використовували лінійні перетворення
, (4.2)
де – константи, незалежні від елементів послідовності . Таке лінійне перетворення переважно називають процесом сумування, а його властивості повністю визначені матрицею . Із практичних причин, тільки скінчене число коефіцієнтів відрізняються від нуля для кожного . Серед таких методів – методи Ейлера, Чезара та Холдера. У випадку лінійних методів збіжність послідовності до для будь-якої збіжної послідов ності визначається теоремою сумування Toeplitz.
Приклади таких процесів:
або (4.3)
У другому випадку, послідовність також залежить від другого індексу , і збіжність повинна бути досліджена або коли зафіксовано, а прямує до безмежності, або коли зафіксовано, а прямує до безмежності.
4.1. Скалярний -алгоритм
Алгоритм був отриманий Пітером Віном (Peter Wynn) у 1956 році. Цей алгоритм покращує збіжність послідовності
(4.4)
та складається з ініціалізації та етапу ітерацій:
Ініціалізація: для
(штучно), (4.5)
. (4.6)
Ітерація: для
. (4.7)
Ілюстрація роботи методу зображена на рис. 7.
k = –1
k = 0
k = 1
k = 2
k = –1
k = 0
k = 1
k = 2
k = 3
k = 4
0
…
0
4,000
-0,75
3,167
-28,62
3,142
0
…
0
2,667
1,25
3,133
82,23
0
0
3,467
-1,75
3,145
0
0
2,895
2,25
0
0
3,339
0
Рис. 7. Епсилон-таблиця та її числовий приклад
Як видно з рис. 7 скалярний -алгоритм утворює квадратну матрицю розмірності , де – непарна кількість еле ментів послідовності . Реалізація обчислення цього прикладу алгоритмічною мовою C++ виглядає так:
const int n=5;
double e[n+1][n+1] = {{0, 4}, {0, 2.667}, {0, 3.467}, {0, 2.895}, {0, 3.339}, {0, 0}};
for (int k=1; k<=n-1; k++)
for (int j=0; j<n-k; j++)
e[j][k+1] = e[j+1][k-1] + 1 / (e[j+1][k] - e[j][k]);
4.2. Векторний -алгоритм
Перед тим як узагальнити скалярний епсилон алгоритм для векторного випадку, необхідно визначити інверсію вектора розмірнос ті . Для цього використовують процедуру обертання Самельсона
, для . (4.8)
Після чого, векторний -алгоритм може бути записаний так:
Ініціалізація: для ;
(штучно), (4.9)
. (4.10)
Ітерація: для ;
. (4.11)
Для діючих значень векторний -алгоритм був доведений Маклеодом (McLeod) [5], а для комплексного випадку – Грейвсом-Морісом (Graves-Morris) [6].
Приклад. Послідовність обчислюється таким чином
(4.12)
(позначає транспонування вектора) та є отримана рекурсивно
, , (4.13)
де
.
Границею для (4.13) є вектор , який є розв’язком сис теми лінійних алгебричних рівнянь , де , – оди нична матриця.
На рис. 8 наведено епсилон-таблицю для . Як бачимо, вже при , для , ми отримуємо нашу границю , хоча остаточно обчислення завершуються при , де й отримуємо шукану границю. При збільшенні кількості ітерацій для (4.13) обчислення границі за -алгоритмом завершується аварією. Це свідчить про те, що необхідний правильний вибір кількості членів послідовності , однак на жаль не існує строгого критерію вибору їх кількості, тому тут можливий лише евристичний підхід.
У правій частині рис. 8 наведено графічну ілюстрацію розглянутого прикладу. Промені з крапкою на кінцях відображають координати векторів на площині при різних та .
-0,10
1,50
0,96
1,58
1,00
1,00
0,59
2,35
0,57
1,44
1,00
1,00
1,43
2,08
0,40
0,76
1,00
1,00
1,80
1,11
0,90
0,57
1,54
0,26
1,16
0,64
0,95
0,09
0,51
0,60
Рис. 8. Векторна епсилон-таблиця для розглянутого прикладу
та її графічна ілюстрація
Реалізація обчислення цього прикладу алгорит мічною мовою C++ виглядає так:
const int n=7, m=2;
double G[m][m] = {{0.6, 0.5}, {-1, 0.5}};
double e[n+1][n+1][m], s[n][m] = {{-0.1, 1.5}}, Gs[m], V[m], w;
for (int j=0; j<n+1; j++) //-- задання нулів для k=-1 е-алгоритму--
for (int i=0; i<m; i++)
e[j][0][i] = 0;
for (int j=0; j<n-1; j++) //----- обчислення Sn-послідовності ------
for (int i=0; i<m; i++)
{
Gs[i] = 0;
for (int d=0; d<2; d++)
Gs[i] += G[i][d] * s[j][d];
s[j+1][i] = s[0][i] + Gs[i];
} //-- кінець обчислення Sn-послідовності --
for (int j=0; j<n; j++) //- присвоєння значень для k=0 е-алгоритму-
for (int i=0; i<m; i++)
e[j][1][i] = s[j][i];
for (int k=1; k<=n-1; k++) //-------- e-алгоритм ------------
for (int j=0; j<n-k; j++)
{
for (int i=0; i<m; i++) //----- обертанння Самельсона ------
V[i] = e[j+1][k][i] - e[j][k][i];
w = 0;
for (int i=0; i<m; i++)
w += V[i] * V[i];
for (int i=0; i<m; i++)
V[i] = V[i] / w; //-- кінець обертанння Самельсона --
for (int i=0; i<m; i++)
e[j][k+1][i] = e[j+1][k-1][i] + V[i];
} //------ кінець e-алгоритму -------
4.3. Застосування -алгоритму для лінійних систем
Розглянемо систему лінійних алгебричних рівнянь
, (4.14)
де – невироджена матриця, – вектор вільних членів, – вектор невідомих.
Приведемо систему (4.14) до еквівалентного виду
(4.15)
або
, (4.16)
який відповідає методу простої ітерації
, (4.17)
де , та параметр вибирають так, щоб по можливості зробити мінімальною величину норми
, (4.18)
де – власні числа матриці . Нагадаємо, що число називають власним числом матриці , якщо . Кожна матриця порядку має рівно власних чисел з врахуванням їх кратності.
Відомо, що умова збіжності методу простої ітерації буде виконана, якщо вибрати . Оптимальним є вибір
. (4.19)
Для покращення збіжності ітераційного процесу перетворення системи (4.14) до виду (4.17) можна здійснити також за допомогою спеціальної матриці, яка називається передобумовником. Наприклад, якщо матриця близька до матриці , то перетворена система у такий спосіб
(4.20)
має такий ж розв’язок, що й система (4.14), але власні числа матриці будуть близькими до одиниці.
Тоді у формулі (4.17) вхідні матриця та вектор будуть такими: , .
В якості простого передобумовника можемо використати діагональ з коефіцієнтами вхідної матриці
. (4.21)
Застосування такого передобумовлення здійснюється достатньо просто, хоча з іншої сторони, використання більш складних процедур переважно дає кращі результати.
Приклад застосування передобумовника.
Розглянемо систему рівнянь з матрицею коефіцієнтів
.
Після застосування передобумовника до матриці , отримаємо перетворену матрицю
.
Тепер повернемося до -алгоритму. Починаючи з початкового вектора , для , за допомогою ітераційної формули (4.17) будуємо послідовність
, для ; (4.22)
Якщо лінійний процес (4.22) є збіжним, то з практичної сторони вважається за доцільніше застосовувати методи екстраполяції після визначеного числа початкових ітерацій. З метою зменшення комп’ютерної пам’яті для запам’ятовування значень ітераційних кроків для великих систем рівнянь алгоритм знову повторюється після визначеного числа ітерацій.
Остаточно -алгоритм для розв’язування систем лінійних алгебричних рівнянь виглядає так:
1.Вибираємо та цілі числа та .
2. Початкові ітерації
,
, ;
3. Етап екстраполяції
, ;
якщо , для , тоді процес зупиняємо;
інакше , , ;
обчислюємо наближення векторним -алгоритмом;
переходимо до п.2.
Для малих систем (розмірності системи), тоді .
4.4. Застосування -алгоритму для нелінійних систем
Нехай необхідно знайти розв’язок нелінійної системи (1.1) із заданою точністю . Перетворимо систему (1.1) до такого еквівалентного вигляду (до вигляду, зручного для методу простої ітерації)
(4.23)
У векторній формі система (4.23) записується так:
, (4.24)
де , .
Для методу простої ітерації формула (4.24) записується так
. (4.25)
Запис (4.25) означає, що чергове наближення обчис люється через попереднє наближення таким чином:
(4.26)
Збіжність методу простої ітерації. Якщо в околиці розв’язку функції , для , диференційо вані та виконується нерівність
(4.27)
де
,
то кажуть, що метод збі гається.
Умова (4.27), грубо кажучи, означає, що в околиці розв’язку похідні для всіх та повинні бути «достатньо малими по модулю». Іншими словами, систему (1.1) необхідно перетворити до такого вигляду (4.23), щоб функції слабо мінялися при зміні аргументів, тобто були «майже постійними». Якихось загальних рецептів, як це зробити, у загальному випадку немає.
Тепер нехай є послідовністю векторів, отриманих від початкового наближення , для , таким чином:
, для ; . (4.28)
Як і у випадку систем лінійних алгебричних рівнянь, доцільно застосовувати методи екстраполяції після визначеного числа початкових ітерацій та повторювати алгоритм після визначеного числа ітерацій.
-алгоритм для розв’язування систем нелінійних рівнянь:
1. Вибираємо та цілі числа та .
2. Початкові ітерації
,
, ;
3. Етап екстраполяції
, ;
якщо , для , тоді процес зупиняємо;
інакше , , ;
обчислюємо наближення векторним -алгоритмом;
переходимо до п.2.
Для малих систем (розмірності системи), тоді .
Загальний алгоритм екстраполяційного методу -алгоритму
для розв’язування систем нелінійних рівнянь
Встановлення нулів для k = –1 -3Dматриці:
для ;
початкові ітерації: для
, … ,
Встановлення s0=x: для
Генерування S-послідовності: для
якщо
для
якщо { вихід із циклу }
Екстраполяція: якщо
для ;
для
для
для
для
для
Опис алгоритму
На початку алгоритму задаємо значення цілих чисел (розмірність системи рівнянь), (можемо прийняти ), (розмір послідовності ), (кількість початкових ітерацій).
Задаємо початкове наближення , для , та відносну похибку у відсотках.
Встановлюємо нулі у -матриці для випадку, коли .
Виконуємо початкових ітерацій.
Встановлюємо початкові значення для послідовності.
Генеруємо послідовність. На етапі генерування послідовності здійснюємо перевірку збіжності методу. Використана змінна є логічного типу, відповідно, і операції, що проводяться з нею є ло гічними. Оператор – виконує логічну операцію «або».
На етапі екстраполювання обчислюємо інверсний вектор за допомогою процедури обертання Самельсона та шукаємо границю послідовності, яка відповідає елементу матриці . Присвоюємо знайдену границю вектору невідомих.
Перевіряємо умову завершення ітераційного процесу. Якщо вона не виконується, то процес уточнення повторюємо (п.4).
Для перевірки вірності роботи алгоритму підставляємо наші знайдені значення в систему рівнянь . Значення функцій , для , мають бути близькими нулю, у залежності від вибраного значення .
Зауваження: алгоритм адаптований для алгоритмічної мови С++.
Проілюструємо результати виконання роботи наведеного алгоритму на прикладі розв’язування системи нелінійних рівнянь (1.3). Спершу приведемо систему до вигляду (4.23) так, щоб задовольнялася умова збіжності методу простої ітерації (4.27)
. (4.29)
Виберемо значення: цілих чисел , , , , початкового наближення та значення відносної похибки у відсотках .
Згідно вхідних даних ми одержали такі результати.
Вектор невідомих:
.
Вектор функцій системи рівнянь:
.
Алгоритм виконав 15 ітераційних наближень та 2 стадії пошуку границі послідовності. У той час, коли для методу простої ітерації необхідно було виконати 76 ітераційних наближень.
5. Порядок виконання роботи
Вдома вивчити теоретичні відомості, необхідні для виконання лабораторної роботи.
Згідно варіанту (порядкового номера в журналі викладача) завдання (таблиця 1 та 2), вдома написати програму для реалізації алгоритму вказаного методу, а в лабораторії вписати програмний код та налагодити цю програму.
Отримані на комп’ютері числові результати представити викладачу.
По результатах виконаної роботи оформити звіт та здати його.
Таблиця 1. Завдання до лабораторної роботи
*система нелінійних рівнянь вибирається з таблиці 2
№
п/п
Завдання
(метод та початкові наближення коренів)
відносна похибка у відсотках %,
для -алгоритму: ,
Група 1
Група 2
Група 3
1
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт. матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
2
Спрощений метод Ньютона
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт. матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
3
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт. матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Спрощений метод Ньютона
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
4
-алгоритм
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт. матриці мето дом Гауса з вибор. гол. ел-тів по всій матриці)
Спрощений метод Ньютона
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
5
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
-алгоритм
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
6
Стандартний метод Ньютона
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
-алгоритм
7
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
8
-алгоритм
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
9
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
-алгоритм
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
10
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по стовпцю)
-алгоритм
11
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по по всій матриці )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по стовпцю)
12
-алгоритм
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по по всій матриці )
Метод січних
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку )
13
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
-алгоритм
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по по всій матриці )
14
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
-алгоритм
15
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
16
-алгоритм
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
17
Стандартний метод Ньютона
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по стовпцю )
-алгоритм
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
18
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
-алгоритм
19
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
20
-алгоритм
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку)
21
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
-алгоритм
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по всій матриці)
22
Стандартний метод Ньютона
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
-алгоритм
23
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю )
24
-алгоритм
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
25
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по стовпцю)
-алгоритм
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці)
26
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето-дом Гауса з виб. гол. ел-тів по стовпцю)
-алгоритм
27
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з виб. гол. ел-тів по стовпцю)
28
-алгоритм
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
Метод січних
(оберт.матриці методом Гауса з вибор. гол. ел-тів по рядку )
29
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
-алгоритм
Стандартний метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по всій матриці )
30
Метод Ньютона з кінцево-різницевою матрицею Якобі
(оберт.матриці мето дом Гауса з вибор. гол. ел-тів по рядку)
Спрощений метод Ньютона
(оберт.матриці методом Гауса з вибор. гол. ел-тів по стовпцю)
-алгоритм
Таблиця 2. Системи нелінійних рівнянь
№1
поч. наближення
№2
поч. наближення
№3
поч. наближення
№4
поч. наближення
№5
поч. наближення
№6
поч. наближення
№7
поч. наближення
№8
поч. наближення
№9
поч. наближення
№10
поч. наближення
№11
поч. наближення
№12
поч. наближення
№13
поч. наближення
№14
поч. наближення
№15
поч. наближення
№16
поч. наближення
№17
поч. наближення
№18
поч. наближення
№19
поч. наближення
№20
поч. наближення
№21
поч. наближення
№22
поч. наближення
№23
поч. наближення
№24
поч. наближення
№25
поч. наближення
№26
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора