Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2007
Тип роботи:
Інструкція та методичні настанови
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 5
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № ___ від __________.
Львів – 2007
Метод Ньютона для розв’язування систем нелінійних рівнянь: Інструкція до лабораторної роботи №5 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 11 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Іванюк Віталій Миколайович, асистент.
Відповідальний за випуск: І.Я. Тишик, ст.в.
Рецензент: В.Б.Дудикевич, д.т.н., проф.,
В.В.Хома, д.т.н., проф.
Мета роботи - ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Вступ
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
EMBED Equation.3
Тобто як EMBED Equation.3 функцій EMBED Equation.3 від EMBED Equation.3 невідомих EMBED Equation.3 , причому функції EMBED Equation.3 не обов’язково лінійно залежить від змінних EMBED Equation.3 .
Позначимо вектор змінних через EMBED Equation.3 , а вектор функції через EMBED Equation.3 . Тоді систему (1) можна записати у формі.
EMBED Equation.3
Завдання полягає в тому, щоб знайти розв’язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв’язати питання про існування та число розв’язків системи (2). Їх може не бути зовсім, може бути один, декілька або нескінчена множина [3]. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв’язків не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розробленні методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1. Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем (найчастіше прямими методами).
Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор EMBED Equation.3 і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
EMBED Equation.3
де EMBED Equation.3 - члени другого і вищих порядків.
Вважаючи, що EMBED Equation.3 дуже близьке до EMBED Equation.3 , знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
EMBED Equation.3 (3)
або в іншому вигляді
EMBED Equation.3 (4)
де
EMBED Equation.3 – матриця Якобі (якобіан) системи (1)
Враховуючи, що EMBED Equation.3 є розв'язком системи, згідно з (2) можемо записати:
EMBED Equation.3
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
EMBED Equation.3 (5)
Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора EMBED Equation.3 (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
EMBED Equation.3 (6)
Звідси
EMBED Equation.3 (7)
де EMBED Equation.3 - обернена матриця Якобі; EMBED Equation.3 .
У достатньо широкому околі розв'язку EMBED Equation.3 ітераційний процес (7) збігається, якщо EMBED Equation.3 .
Ітераційний процес закінчується при виконанні умови
EMBED Equation.3 (8)
де Σ - задана гранична похибка уточнень коренів системи (1).
Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
EMBED Equation.3 .
Крок 2. Обчислення елементів матриці Якобі.
Крок 3. Обчислення елементів оберненої матриці Якобі.
Крок 4. Перемноження значень функції (див. формулу (7))
EMBED Equation.3
Крок 5. Одержаний на кроці 4 вектор віднімається від вектора EMBED Equation.3 , у результаті чого одержується покращений вектор розв'язку EMBED Equation.3 .
Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор EMBED Equation.3 і проводиться наступна ітерація, починаючи з кроку 2.
При використанні стандартного методу Ньютона слід мати на увазі наступне.
1. Стандартний метод Ньютона надзвичайно ефективний.
2. Збіжність на початку ітераційного процесу, як правило, лінійна.
3. Починаючи з деякого кроку ( уточнити його попередньо неможливо), збіжність різко прискорюється і стає квадратичною.
4. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом.
Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора EMBED Equation.3 , матриці Якобі EMBED Equation.3 , оберненої матриці Якобі EMBED Equation.3 . Тому на практиці досить часто з метою зменшення витрат машинного часу використовують стандартний метод Ньютона без обертання матриці Якобі.
Позначаючи
EMBED Equation.3 (9)
перепишемо (6) у вигляді
EMBED Equation.3 (10)
Таким чином, задача зводиться до пошуку вектора поправок (приростів) EMBED Equation.3 із системи лінійних алгебраїчних рівнянь (10), у якій матрицею коефіцієнтів при невідомих EMBED Equation.3 є матриця Якобі EMBED Equation.3 , а вектором-стовпцем вільних членів служить вектор значень функції – EMBED Equation.3 . Розв'язуючи цю систему одним із відомих методів (як правило, це представники групи прямих методів – метод Гауса з вибором головних елементів, метод LU – факторизації та ін.) , знаходимо EMBED Equation.3 . Значення EMBED Equation.3 визначаємо із виразу
EMBED Equation.3 (11)
Приклад. Уточнити корені системи нелінійних рівнянь
EMBED Equation.3
стандартним методом Ньютона без обертання якобіана при початкових наближеннях коренів EMBED Equation.3 .
Знайдемо вирази для функцій
EMBED Equation.3
за якими будуть визначатись елементи матриці Якобі:
EMBED Equation.3 EMBED Equation.3
Обчислимо значення функцій та елементів матриці Якобі в точці EMBED Equation.3 :
EMBED Equation.3 EMBED Equation.3
Розв'яжемо згідно з (10) систему лінійних рівнянь відносно приростів EMBED Equation.3
EMBED Equation.3
Уточнені значення коренів визначаються за формулою (11):
EMBED Equation.3
Наступна ітерація проводиться таким чином:
знаходяться значення функцій та елементів матриці Якобі в точці EMBED Equation.3 і розв'язується відповідна система лінійних рівнянь:
EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
Звідси
EMBED Equation.3
Отже,
EMBED Equation.3
2. Метод Ньютона з якобіаном із кінцевих різниць
У цьому методі замість похідних, що входять до складу якобіана, використовуються їхні наближені значення в точці EMBED Equation.3
EMBED Equation.3
де h - фіксоване достатньо мале число, наприклад , EMBED Equation.3 .
3. Модифікований метод Ньютона
При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан EMBED Equation.3 , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення EMBED Equation.3 , де EMBED Equation.3 –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан EMBED Equation.3 заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна EMBED Equation.3 , де EMBED Equation.3 - розв'язок.
Але на практиці користуються компромісним рішенням:
– вибирають за А якобіан в початковій точці EMBED Equation.3 , a ітерації проводять за наступною формулою
EMBED Equation.3
– зберігають А протягом певного числа ітерацій;
– на певній r-й ітерації змінюють А, прирівнюючи її якобіану EMBED Equation.3 і з новим значенням знову виконують певне число ітерацій і т.д.
Отже, якобіан обчислюється тільки час від часу, за рахунок чого досягається економія машинного часу. Однак, збіжність методу при цьому стає практично лінійною.
Завдання
до лабораторної роботи
Розв’яжіть систему нелінійних рівнянь одним із методів, вказаних викладачем, вибираючи за початкові наближення EMBED Equation.3 . Ітерації проводити до збігу двох послідовних наближень з похибкою EMBED Equation.3 .
1) EMBED Equation.3 EMBED Equation.3
2) EMBED Equation.3 EMBED Equation.3
3) EMBED Equation.3 EMBED Equation.3
4) EMBED Equation.3 EMBED Equation.3
5) EMBED Equation.3 EMBED Equation.3
6) EMBED Equation.3 EMBED Equation.3
7) EMBED Equation.3 EMBED Equation.3
8) EMBED Equation.3 EMBED Equation.3
9) EMBED Equation.3 EMBED Equation.3
10) EMBED Equation.3 EMBED Equation.3
11) EMBED Equation.3 EMBED Equation.3
12) EMBED Equation.3 EMBED Equation.3
13) EMBED Equation.3 EMBED Equation.3
14) EMBED Equation.3 EMBED Equation.3
15) EMBED Equation.3 EMBED Equation.3
16) EMBED Equation.3 EMBED Equation.3
17) EMBED Equation.3 EMBED Equation.3
18) EMBED Equation.3 EMBED Equation.3
19) EMBED Equation.3 EMBED Equation.3
20) EMBED Equation.3 EMBED Equation.3
21) EMBED Equation.3 EMBED Equation.3
22) EMBED Equation.3 EMBED Equation.3
23) EMBED Equation.3 EMBED Equation.3
24) EMBED Equation.3 EMBED Equation.3
25) EMBED Equation.3 EMBED Equation.3
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%
Оголошення від адміністратора