Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Інформаційна безпека
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2007
Тип роботи:
Інші
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 5
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № ___ від __________.
Львів – 2007
Метод Ньютона для розв’язування систем нелінійних рівнянь: Інструкція до лабораторної роботи №5 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 11 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Іванюк Віталій Миколайович, асистент.
Відповідальний за випуск: І.Я. Тишик, ст.в.
Рецензент: В.В.Хома, д.т.н., проф..
В.М.Максимович, к.т.н., доц.
Мета роботи - ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Вступ
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
Тобто як функцій від невідомих , причому функції не обов’язково лінійно залежить від змінних .
Позначимо вектор змінних через , а вектор функції через . Тоді систему (1) можна записати у формі.
Завдання полягає в тому, щоб знайти розв’язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв’язати питання про існування та число розв’язків системи (2). Їх може не бути зовсім, може бути один, декілька або нескінчена множина [3]. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв’язків не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розробленні методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1. Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем (найчастіше прямими методами).
Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
де - члени другого і вищих порядків.
Вважаючи, що дуже близьке до , знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
(3)
або в іншому вигляді
(4)
де
– матриця Якобі (якобіан) системи (1)
Враховуючи, що є розв'язком системи, згідно з (2) можемо записати:
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
(5)
Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
(6)
Звідси
(7)
де - обернена матриця Якобі; .
У достатньо широкому околі розв'язку ітераційний процес (7) збігається, якщо .
Ітераційний процес закінчується при виконанні умови
(8)
де Σ - задана гранична похибка уточнень коренів системи (1).
Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
.
Крок 2. Обчислення елементів матриці Якобі.
Крок 3. Обчислення елементів оберненої матриці Якобі.
Крок 4. Перемноження значень функції (див. формулу (7))
Крок 5. Одержаний на кроці 4 вектор віднімається від вектора , у результаті чого одержується покращений вектор розв'язку .
Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор і проводиться наступна ітерація, починаючи з кроку 2.
При використанні стандартного методу Ньютона слід мати на увазі наступне.
1. Стандартний метод Ньютона надзвичайно ефективний.
2. Збіжність на початку ітераційного процесу, як правило, лінійна.
3. Починаючи з деякого кроку ( уточнити його попередньо неможливо), збіжність різко прискорюється і стає квадратичною.
4. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом.
Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора , матриці Якобі , оберненої матриці Якобі . Тому на практиці досить часто з метою зменшення витрат машинного часу використовують стандартний метод Ньютона без обертання матриці Якобі.
Позначаючи
(9)
перепишемо (6) у вигляді
(10)
Таким чином, задача зводиться до пошуку вектора поправок (приростів) із системи лінійних алгебраїчних рівнянь (10), у якій матрицею коефіцієнтів при невідомих є матриця Якобі , а вектором-стовпцем вільних членів служить вектор значень функції – . Розв'язуючи цю систему одним із відомих методів (як правило, це представники групи прямих методів – метод Гаусса з вибором головних елементів, метод LU – факторизації та ін.) , знаходимо . Значення визначаємо із виразу
(11)
Приклад. Уточнити корені системи нелінійних рівнянь
стандартним методом Ньютона без обертання якобіана при початкових наближеннях коренів .
Знайдемо вирази для функцій
за якими будуть визначатись елементи матриці Якобі:
Обчислимо значення функцій та елементів матриці Якобі в точці :
Розв'яжемо згідно з (10) систему лінійних рівнянь відносно приростів
Уточнені значення коренів визначаються за формулою (11):
Наступна ітерація проводиться таким чином:
знаходяться значення функцій та елементів матриці Якобі в точці і розв'язується відповідна система лінійних рівнянь:
Звідси
Отже,
2. Метод Ньютона з якобіаном із кінцевих різниць
У цьому методі замість похідних, що входять до складу якобіана, використовуються їхні наближені значення в точці
де h - фіксоване достатньо мале число, наприклад ,.
3. Модифікований метод Ньютона
При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення , де –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна , де - розв'язок.
Але на практиці користуються компромісним рішенням:
– вибирають за А якобіан в початковій точці , a ітерації проводять за наступною формулою
– зберігають А протягом певного числа ітерацій;
– на певній r-й ітерації змінюють А, прирівнюючи її якобіану і з новим значенням знову виконують певне число ітерацій і т.д.
Отже, якобіан обчислюється тільки час від часу, за рахунок чого досягається економія машинного часу. Однак, збіжність методу при цьому стає практично лінійною.
Завдання
до лабораторної роботи
Розв’яжіть систему нелінійних рівнянь одним із методів, вказаних викладачем, вибираючи за початкові наближення . Ітерації проводити до збігу двох послідовних наближень з похибкою .
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)
2.1. Домашня підготовка до роботи
1. Ознайомитися з основними теоретичними відомостями.
2. Розробити блок-схему алгоритму методу
3.Написати програму, яка забезпечить розв’язок та виведення на екран результатів роботи. Варіанти завдань беруть за вказівкою викладача.
2.2. Робота в лабораторії
1. Ввести в комп'ютер програму згідно з отриманим завданням.
2. Здійснити відладку введеної програми, виправивши виявлені помилки.
3. Виконати програму. Текст відлагодженої програми та отримані результати оформити у звіт з лабораторної роботи.
3. ЗМIСТ ЗВIТУ
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Повний текст завдання.
4. Блок-схема алгоритму програми.
5. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення.
6. Остаточно відлагоджений текст програми згідно з отриманим завданням.
7. Результати виконання програми.
8. Висновок.
Контрольні запитання
Опишіть алгоритм стандартного методу Ньютона.
При виконанні якої умови закінчується ітераційний процес в стандартному методі Ньютона?
Який характер має збіжність на початку ітераційного процесу стандартного методу Ньютона ?
Який основний недолік стандартного методу Ньютона?
Опишіть порядок знаходження коренів системи нелінійних рівнянь методом Ньютона з якобіаном із кінцевих різниць.
Опишіть порядок знаходження коренів системи нелінійних рівнянь модифікованим методом Ньютона.
За рахунок чого досягається економія машинного часу в модифікованому методі Ньютона?
СПИСОК ЛІТЕРАТУРИ
Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с.
Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с.
Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с.
Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с.
Джон Г. Мэтьюз, Куртис Д. Финк Чисельнные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора