Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Метод Ньютона для розв’язування систем нелінійних рівнянь
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра захисту інформації
Інформація про роботу
Рік:
2010
Тип роботи:
Інші
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
„ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
Кафедра захисту інформації
З В І Т
До лабораторної роботи №5
з курсу:
„ Комп’ютерні методи дослідження
інформаційних процесів та систем ”
на тему:
«Метод Ньютона для розв’язування систем
нелінійних рівнянь»
Варіант 19
Львів- 2010
Мета роботи:
Ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Вступ
Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
Тобто як функцій від невідомих , причому функції не обов’язково лінійно залежить від змінних .
Позначимо вектор змінних через , а вектор функції через . Тоді систему (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. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом.
Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора , матриці Якобі , оберненої матриці Якобі .
3. Модифікований метод Ньютона
При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення , де –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна , де - розв'язок.
Але на практиці користуються компромісним рішенням:
– вибирають за А якобіан в початковій точці , a ітерації проводять за наступною формулою
– зберігають А протягом певного числа ітерацій;
– на певній r-й ітерації змінюють А, прирівнюючи її якобіану і з новим значенням знову виконують певне число ітерацій і т.д.
Отже, якобіан обчислюється тільки час від часу, за рахунок чого досягається економія машинного часу. Однак, збіжність методу при цьому стає практично лінійною.
2. ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ
Розв’язати систему нелінійних рівнянь модифікованим методом Ньютона, вибираючи за початкові наближення . Ітерації проводити до збігу двох послідовних наближень з похибкою .
19)
Блок схема програми
Список індентифікаторів, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення
class Program – клас, в якому оголошений метод Main;
class Metods –клас, в якому оголошені методи J, A, F, Obchusl;
public void J – метод обчислення Якоб’яна;
public void A – метод обчислення обертання Якоб’яна;
public void F – метод обчислення функції в при х[1], x[2];
public void Obchusl – метод обчислення значення х[1], x[2];
static void Main(string[] args) – головна функція;
I – клас типу Methods;
j, a масиви 2х2 типу Double;
x1, x2, E, delta_xk1, delta_xk2, xk1, xk2 змінні типу double;
p – змінна типу int;
f,r – лінійні масиви типу Double.
Текст програми:
using System;
using System.Collections.Generic;
using System.Text;
namespace Njuton
{
class Program
{
static void Main(string[] args)
{
Metods I = new Metods();
I.Obchusl();
Console.ReadKey();
}
}
class Metods
{
Double[,] j = new Double[2, 2];
Double[,] a = new Double[2, 2];
double x1, x2, E = 0.00001, delta_xk1, delta_xk2, xk1, xk2;
int p;
Double[] f = new Double[2];
Double[] r = new Double[2];
public void J(double x1, double x2)
{
j[0, 0] = 1 - 2 * x1;
j[0, 1] = -2 * x2;
j[1, 0] = -2 * x2;
j[1, 1] = 1 - 2 * x1;
}
public void A(double x1, double x2)
{
J(x1, x2);
double det = Math.Pow(1 - 2 * x1, 2) - Math.Pow(2 * x2, 2);
a[0, 0] = (1 / det) * j[1, 1];
a[0, 1] = (1 / det) * j[1, 0];
a[1, 0] = (1 / det) * j[0, 1];
a[1, 1] = (1 / det) * j[0, 0];
}
public void F(double x1, double x2)
{
f[0] = x1 - Math.Pow(x1, 2) - Math.Pow(x2, 2) - 0.1;
f[1] = x2 - 2 * x1 * x2 + 0.1;
}
public void Obchusl()
{
x1 = Convert.ToDouble(Console.ReadLine());
x2 = Convert.ToDouble(Console.ReadLine());
int k = 0;
A(x1, x2);
do
{
p = 0;
k++;
if (k % 5 == 0) A(x1, x2);
F(x1, x2);
r[0] = a[0, 0] * f[0] + a[0, 1] * f[1];
r[1] = a[1, 0] * f[0] + a[1, 1] * f[1];
xk1 = x1 - r[0];
xk2 = x2 - r[1];
delta_xk1 = Math.Abs(xk1 - x1);
delta_xk2 = Math.Abs(xk2 - x2);
if (delta_xk1 < E) p = 1;
if (delta_xk2 < E) p = 1;
x1 = xk1; x2 = xk2;
}
while (p != 1);
Console.WriteLine("\n\n{0}\t{1}\n", x1, x2);
}
}
}
Результат виконання програми:
0
0
0.138189502386377 -0.138189502386376
Висновок:
На цій лабораторній роботі я склав програму мовою С# і ознайомився з методами Ньютона для розв’язування систем нелінійних рівнянь
25.12.2011 16:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора