Метод Ньютона для розв’язування систем нелінійних рівнянь icon

Метод Ньютона для розв’язування систем нелінійних рівнянь



НазваниеМетод Ньютона для розв’язування систем нелінійних рівнянь
Дата конвертации22.09.2012
Размер61.06 Kb.
ТипДокументы

Метод Ньютона для розв’язування систем нелінійних рівнянь


Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді


(1)


тобто як п функцій fi від п невідомих хі, причому функції fi не обов'язково лінійно залежать від змінних хі.

Позначимо вектор змінних через X = (x1, x2, …, xn),а вектор функцій через F = (f1, f2,…, fп). Тоді систему (1) можна записати у формі


F(X) = 0. (2)


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


1.Стандартний метод Ньютона


Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем ( найчастіше прямими методами).

Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор X* = (х1*, х2*,..., хп*) і розкладемо кожну функцію в ряд Тейлора в околі розв'язку



де Rіп - члени другого і вищих порядків.

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

(3)


або в іншому вигляді


(4)


де


– матриця Якобі (якобіан) системи (1)


Враховуючи, що ^ X* є розв'язком системи, згідно з (2) можемо записати:


F(X*) = 0.


Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:

(5)


Розв'язком системи (5) є нове значення вектора ^ X, яке не точно дорівнює значенню вектора X* (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати


(6)


Звідси


(7)


де [J(XK)]–1 - обернена матриця Якобі; К = 0, 1, 2, ... .

У достатньо широкому околі розв'язку X* ітераційний процес (7) збігається, якщо det J(Хк) ≠ 0.

Ітераційний процес закінчується при виконанні умови


(8)


де Σ - задана гранична похибка уточнень коренів системи (1).

Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків.


Крок 1. Вибір вектора початкових уточнень


Х(0)-(х1(0), х2(0), ..., хп(0)).


Крок 2. Обчислення елементів матриці Якобі.

Крок 3. Обчислення елементів оберненої матриці Якобі.

Крок 4. Перемноження значень функції (див. формулу (7))





Крок 5. Одержаний на кроці 4 вектор віднімається від вектора ХК, у результаті чого одержується покращений вектор розв'язку ХК+1.

Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор ХК+1 і проводиться наступна ітерація, починаючи з кроку 2.


При використанні стандартного методу Ньютона слід мати на увазі наступне.

1. Стандартний метод Ньютона надзвичайно ефективний.

2. Збіжність на початку ітераційного процесу, як правило, лінійна.

3. Починаючи з деякого кроку ( уточнити його попередньо неможливо), збіжність різко прискорюється і стає квадратичною.

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


Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора F(XK) , матриці Якобі J(XK), оберненої матриці Якобі [J(XK)]–1. Тому на практиці досить часто з метою зменшення витрат машинного часу використовують стандартний метод Ньютона без обертання матриці Якобі.

Позначаючи


(9)

перепишемо (6) у вигляді


(10)


Таким чином, задача зводиться до пошуку вектора поправок (приростів) ΔХК із системи лінійних алгебраїчних рівнянь (10), у якій матрицею коефіцієнтів при невідомих ΔхіK є матриця Якобі J(XK), а вектором-стовпцем вільних членів служить вектор значень функції – F(XK). Розв'язуючи цю систему одним із відомих методів ( як правило, це представники групи прямих методів – метод Гауса з вибором головних елементів, метод LU – факторизації та ін.) , знаходимо ΔХК. Значення ХK+1 визначаємо із виразу


(11)


Приклад. Уточнити корені системи нелінійних рівнянь





стандартним методом Ньютона без обертання якобіана при початкових наближеннях коренів x10 = 3,4; x20 = 2,2.

Знайдемо вирази для функцій





за якими будуть визначатись елементи матриці Якові:





Обчислимо значення функцій та елементів матриці Якобі в точці Х0 = (х10, х20):





Розв'яжемо згідно з (10) систему лінійних рівнянь відносно приростів





Уточнені значення коренів визначаються за формулою (11):





Наступна ітерація проводиться таким чином:

знаходяться значення функцій та елементів матриці Якобі в точці Х1 = (х11, х21) і розв'язується відповідна система лінійних рівнянь:








Звідси





Отже,





2. Метод Ньютона з якобіаном із кінцевих різниць


У цьому методі замість похідних, що входять до складу якобіана, використовуються їхні наближені значення в точці ХК





де h - фіксоване достатньо мале число, наприклад ,1*10-9.


3. Модифікований метод Ньютона


При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан J(XK) , хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення J(X*), де X* –розв'язок. У модифікованому або спрощеному методі Ньютона якобіан J(XK) заміняють правильно підібраною матрицею А. Звичайно, найкращим, але практично недосяжним варіантом була б заміна А = J(X*), де X* - розв'язок.

Але на практиці користуються компромісним рішенням:

– вибирають за А якобіан з початковій точці J(X0), a ітерації проводять за наступною формулою





– зберігають А протягом певного числа ітерацій;

– на певній r-й ітерації змінюють А, прирівнюючи її якобіану J(Xr) і з новим значенням знову виконують певне число ітерацій і т.д.

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




Похожие:

Метод Ньютона для розв’язування систем нелінійних рівнянь iconСтандартний метод Ньютона з обертанням матриці Якобі для розв’язування системи нелінійних рівнянь

Метод Ньютона для розв’язування систем нелінійних рівнянь iconРеферат з математики
Одним з найпоширеніших методів розв'язування систем лінійних рівнянь є метод послідовного виключення невідомих, або метод Гаус­са....
Метод Ньютона для розв’язування систем нелінійних рівнянь iconРеферат з дисципліни Алгоритми мови та програмування Розв’язання систем лінійних рівнянь методом Гауса
...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconОднокрокові методи призначені для розв’язування диференціальних рівнянь першого порядку виду
...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconОднокрокові методи призначені для розв’язування диференціальних рівнянь першого порядку виду
...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconТема : Поглибити знання студентів про методи розв’язування систем лінійних рівнянь та дати практику розв’язання систем лінійних алгебраїчних рівнянь методом Крамера
Тема: Поглибити знання студентів про методи розв’язування систем лінійних рівнянь та дати практику розв’язання систем лінійних алгебраїчних...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconТема : Поглибити знання студентів про методи розв’язування систем лінійних рівнянь та дати практику розв’язання систем лінійних алгебраїчних рівнянь методом Крамера
Тема: Поглибити знання студентів про методи розв’язування систем лінійних рівнянь та дати практику розв’язання систем лінійних алгебраїчних...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconРозв’язування нелінійних рівнянь
Нехай І відомо, що рівняння (1) має єдиний корінь. Покладемо a0=a, b0=b, x0=(a0+b0) Якщо, то. Якщо, то покладемо
Метод Ньютона для розв’язування систем нелінійних рівнянь iconРозв’язування звичайних диференціальних рівнянь
ДР), що містить лише одну незалежну змінну І похідні за нею, називають звичайними (ДР). Це, наприклад, рівняння (1). Др, що містить...
Метод Ньютона для розв’язування систем нелінійних рівнянь iconНаближені методи розв’язування рівнянь та систем рівнянь Розглянемо рівняння з одним невідомим
Розглянемо рівняння з одним невідомим f(X) = Точних методів відшукання всіх коренів такого рівняння немає
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы