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

Цей метод має набагато швидшу збіжність, ніж метод простої ітерації. В основі методу Ньютона системи рівнянь (1.1) лежить використання розкладання функцій

, де
(2.1)

в ряд Тейлора, причому члени, що містять другі і більше високі порядкипохідних, що відкидаються. Такий підхід дозволяє вирішення однієї нелінійної системи (1.1) замінити рішенням низки лінійних систем.

Отже, систему (1.1) вирішуватимемо методом Ньютона. В області D виберемо будь-яку точку
і назвемо її нульовим наближенням до точного рішення вихідної системи. Тепер функції (2.1) розкладемо в ряд Тейлора на околиці точки . Будемо мати

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

Усі приватні похідні (2.3) повинні бути обчислені в точці .

(2.3) є система лінійних алгебраїчних рівняньщодо невідомих Цю систему можна вирішити методом Крамера, якщо її основний визначник буде відмінний від нуля та знайти величини

Тепер можна уточнити нульове наближення, побудувавши перше наближення з координатами

тобто.
. (2.6)

З'ясуємо, чи наближення (2.6) отримано з достатнім ступенем точності. Для цього перевіримо умову

,
(2.7)

де наперед задане мале позитивне число (точність, з якою має бути вирішена система (1.1)). Якщо умова (2.7) буде виконано, то за наближене рішення системи (1.1) виберемо (2.6) та закінчимо обчислення. Якщо ж умова (2.7) не виконуватиметься, то виконаємо таку дію. У системі (2.3) замість
візьмемо уточнені значення

, (2.8)

тобто. виконаємо такі дії

. (2.9)

Після цього система (2.3) буде системою лінійних рівнянь алгебри щодо величин Визначивши ці величини, наступне друге наближення
до розв'язання системи (1.1) знайдемо за формулами

Тепер перевіримо умову (2.7)

Якщо ця умова виконується, то закінчуємо обчислення, взявши за наближене рішення системи (1.1) друге наближення
. Якщо ж ця умова не виконується, то продовжуємо будувати наступне наближення, прийнявши (2.3)
Будувати наближення потрібно доти, доки умова не буде виконана.

Робочі формули методу Ньютона на вирішення системи (1.1) можна записати як.

Обчислити послідовність

Тут
є рішенням системи

Сформулюємо алгоритм обчислень за формулами (2.11)-(2.13).

1. Виберемо нульове наближення, що належить області D.

2. У системі лінійних рівнянь алгебри (2.13) покладемо
,а.

3. Розв'яжемо систему (2.13) і знайдемо величини
.

4. У формулах (2.12) покладемо
і обчислимо компоненти наступного наближення.

5. Перевіримо умову (2.7) на : (Див. алгоритм обчислення максимуму кількох величин.)

6. Якщо ця умова виконується, то закінчуємо обчислення, вибравши наближене рішення системи (1.1) наближення . Якщо це умова не виконується, то перейдемо до п.7.

7. Покладемо
для всіх .

8. Виконаємо п.3, поклавши
.

Геометрично цей алгоритм можна записати як.

Алгоритм. Обчислення максимуму кількох величин.

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

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

, (2.14)

тут
. Виберемо нульове наближення
, Що належить області D. Побудуємо систему лінійних рівнянь алгебри (2.3). Вона матиме вигляд

(2.15)

Позначимо

Вирішимо систему (2.15) щодо невідомих
наприклад методом Крамера. Формули Крамера запишемо у вигляді

(2.17)

де основний визначник системи (2.15)

(2.18)

а допоміжні визначники системи (2.15) мають вигляд

.

Знайдені значення підставимо (2.16) і знайдемо компоненти першого наближення
до вирішення системи (2.15).

Перевіримо умову

, (2.19)

якщо це умова виконується, то закінчуємо обчислення, прийнявши за наближене рішення системи (2.15) перше наближення, тобто.
. Якщо умова (2.19) не виконується, то покладемо
,
і побудуємо нову систему лінійних рівнянь алгебри (2.15). Вирішивши її, знайдемо друге наближення
. Перевіримо його на . Якщо ця умова виконуватиметься, то за наближене рішення системи (2.15) виберемо
. Якщо умова не виконуватиметься, покладемо
,
та побудуємо наступну систему (2.15) для знаходження
і т.д.

Завдання

У всіх завданнях потрібно:

Скласти програму чисельної реалізаціїметоду, згідно з запропонованим алгоритмом.

Отримати результати обчислень.

Перевірити отримані результати.

Задано систему двох нелінійних рівнянь.

1.
2.

3.
4.

5.
6.

7.
8.

9.
10.

11.
12.

13.
14.

15.
.

Глава 3. Чисельні методи розв'язання систем лінійних рівнянь алгебри (СЛАУ).

Мета роботи. Знайомство з деякими наближеними методами рішення СЛАУ та їх чисельною реалізацією на ПК.

Попередні зауваження.Усі методи рішення СЛАУ зазвичай поділяють на великі групи. До першої групи належать методи, які називають точними. Ці методи дозволяють будь-яких систем знайти точні значення невідомих після кінцевого числа арифметичних операцій, кожна з яких виконується точно.

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

Розглянемо деякі наближені методи рішення СЛАУ та побудуємо алгоритми їх чисельної реалізації. Наближене рішення СЛАУ будемо отримувати з точністю до , де дуже маленьке позитивне число.

1. Метод ітерації.

Нехай СЛАУ задана у вигляді

(1.1)

Цю систему можна записати у матричному вигляді

, (1.2)

де
- матриця коефіцієнтів при невідомих у системі (1.1),
- стовпець вільних членів,
- стовпець невідомих системи (1.1).

. (1.3)

Розв'яжемо систему (1.1) методом ітерації. Для цього виконаємо такі дії.

По перше. Виберемо нульове наближення

(1.4)

до точного рішення (1.3) системи (1.1). Компонентами нульового наближення можуть бути будь-які числа. Але зручніше компоненти нульового наближення взяти чи нулі
, чи вільні члени системи (1.1)

По-друге. Компоненти нульового наближення підставимо в праву частинусистеми (1.1) та обчислимо

(1.5)

Величини, що стоять зліва (1.5) є компонентами першого наближення
Дії, у яких вийшло перше наближення, називаються ітерацією.

По-третє. Перевіримо нульове та перше наближення на

(1.6)

Якщо умови (1.6) виконуються, то за наближене рішення системи (1.1) виберемо, або , або однаково, т.к. вони відрізняються один від одного не більше ніж на і закінчимо обчислення. Якщо хоча б одну з умов (1.6) не буде виконано, то перейдемо до наступної дії.

По-четверте. Виконаємо таку ітерацію, тобто. у праву частину системи (1.1) підставимо компоненти першого наближення та обчислимо компоненти другого наближення
, де

У п'ятих. Перевіримо
і , тобто. перевіримо умову (1.6) цих наближень. Якщо умови (1.6) будуть виконані, то за наближене рішення системи (1.1) виберемо, або , або однаково, т.к. вони відрізняються один від одного не більше ніж на . В іншому випадку будуватимемо наступну ітерацію, підставивши компоненти другого наближення в праву частину системи (1.1).

Ітерації потрібно будувати доти, доки два сусідні наближення
і відрізнятимуться один від одного не більше, ніж на .

Робочу формулу методу ітерації рішення системи (1.1) можна записати як

Алгоритм чисельної реалізації формули (1.7) може бути таким.

Достатні умови збіжності методу ітерації для системи (1.1) мають вигляд

1.
, .

2.
,
.

3.

2. Метод простої ітерації.

Нехай система лінійних рівнянь алгебри (СЛАУ) задана у вигляді

(2.1)

Щоб систему (2.1) вирішити методом простої ітерації, спочатку треба привести до виду

(2.2)

У системі (2.2) -ое рівняння є -ое рівняння системи (2.1), дозволене щодо -ой невідомої (
).

Метод розв'язання системи (2.1), що полягає у зведенні її до системи (2.2) з наступним рішенням системи (2.2) методом ітерації, називається методом простої ітерації для системи (2.1).

Таким чином, робочі формули методу простої ітерації рішення системи (2.1) матимуть вигляд

(2.3)

Формули (2.3) можна записати у вигляді

Алгоритм чисельної реалізації методу простої ітерації для системи (2.1) за формулами (2.4) може бути таким.

Цей алгоритм можна записати геометрично.

Достатні умови збіжності методу простої ітерації для системи (2.1) мають вигляд

1.
, .

2.
,
.

3.

3. Стаціонарний метод Зейделя.

Метод Зейделя рішення СЛАУ відрізняється від методу ітерації тим, що знайшовши якесь наближення для тієї компоненти, ми відразу ж використовуємо його для відшукання наступних
,
, …, -ий компонент. Такий підхід дозволяє забезпечити вищу швидкість збіжності методу Зейделя проти методом ітерації.

Нехай СЛАУ задана у вигляді

(3.1)

Нехай
- нульове наближення до точного рішення
Системи (3.1). І нехай знайдено -е наближення
. Визначимо компоненти
-ого наближення за формулами

(3.2)

Формули (3.2) можна записати у компактному вигляді

,
,
(3.3)

Алгоритм чисельної реалізації методу Зейделя рішення системи (3.1) за формулами (3.3) може бути таким.

1. Виберемо, наприклад,
,

2. Покладемо.

3. Для всіх обчислимо.

4. Для всіх перевіримо умови
.

5. Якщо всі умови п.4 будуть виконані, то за наближене рішення системи (3.1) виберемо або , або і закінчимо обчислення. Якщо хоча б одна умова у п.4 не буде виконана, перейдемо до п.6.

6. Покладемо та перейдемо до п.3.

Цей алгоритм можна записати геометрично.

Достатня умова збіжності методу Зейделя для системи (3.1) має вигляд
, .

4. Нестаціонарний метод Зейделя.

Цей метод рішення СЛАУ (3.1) забезпечує ще більшу швидкість збіжності методу Зейделя.

Нехай якимось чином для системи (3.1) знайдені компоненти -ого наближення і наближення.

Обчислимо вектор поправки

Підрахуємо величини

, (4.2)

Розташуємо величини
, у порядку їх спадання.

У такому порядку перепишемо рівняння в системі (3.1) і невідомі в цій системі. Лінійнаалгебраі нелінійні ... Керівництводлялабораторних робітпо ... методичнівказівки дляпрактичнихробітпо длястудентів ...

Навчальна література (природничі науки та технічні) 2000-2011 цикл опд – 10 років цикл сд – 5 років

Література

... Природнінаукив цілому 1. Астрономія [Текст]: посібник для ... Чисельніметоди: Лінійнаалгебраі нелінійні ... Керівництводлялабораторних робітпо ... методичнівказівки дляпрактичнихробітподисципліни "Економіка транспорту" длястудентів ...

- природничі науки (1)

Навчальний посібник

... керівництводлястудентівта викладачів, призначене длявикористання не лише при вивченні методівроботи... вироблення практичнихнавичок із використанням реальних даних. Методичнірекомендації повиконання залікової роботиподаному...

- природничі науки - фізико-математичні науки - хімічні науки - науки про землю (геодезичні геофізичні геологічні та географічні науки)

Документ

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

- природничі науки - фізико-математичні науки - хімічні науки - науки про землю (геодезичні геофізичні геологічні та географічні науки) (7)

Список підручників

Визначник Єрьоміна в лінійноїі нелінійноюалгебри : лінійнеі нелінійнепрограмування: новий метод/ Єрьомін, Михайло... Длястудентівта викладачів геологічних спеціальностей вузів. кх-1 1794549 99. Д3 П 693 Практичнекерівництвопо ...

Метод Ньютона (також відомий як метод дотичних) – це ітераційний чисельний метод знаходження кореня (нуля) заданої функції. Метод був вперше запропонований англійським фізиком, математиком та астрономом Ісааком Ньютоном (1643-1727), під ім'ям якого і знайшов свою популярність.

Метод був описаний Ісааком Ньютоном у рукописі De analysi per aequationes numero terminorum infinitas (лат .Про баналізі рівняннями нескінченних рядів), адресованої в 1669 Барроу, і в роботі De metodis fluxionum et serierum infinitarum (лат.Метод флюксій і нескінченні ряди) або Geometria analytica ( лат.аналітичнагеометрія) у зборах праць Ньютона, яка була написана у 1671 році. Проте опис методу суттєво відрізнявся від його нинішнього викладу: Ньютон застосовував свій метод виключно поліномам. Він обчислював не послідовні наближення xn, а послідовність поліномів і в результаті отримував наближене рішення x.

Вперше метод був опублікований в трактаті Алгебра Джона Валліса в 1685, на прохання якого він був коротко описаний самим Ньютоном. У 1690 році Джозеф Рафсон опублікував спрощений опис у роботі Analysis aequationum universalis (лат. Загальний аналізрівнянь).Рафсон розглядав метод Ньютона як суто алгебраїчний і обмежив його застосування поліномами, проте при цьому він описав метод на основі послідовних наближень x n замість більш тяжкої для розуміння послідовності поліномів, використаної Ньютоном.

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

Відповідно до даного методу завдання пошуку кореня функції зводиться до задачі пошуку точки перетину з віссю абсцис дотичної, побудованої до графіка функції .

Рис.1 . Графік зміни функції

Проведена в будь-якій точці дотична лінія до графіка функції визначається похідною цієї функції в точці, що розглядається, яка в свою чергу визначається тангенсом кута α (). Точка перетину дотичної з віссю абсцис визначається виходячи з наступного співвідношення прямокутному трикутнику: тангенс кута.у прямокутному трикутнику визначається ставленням протилежного катета до прилеглого катета трикутника. Таким чином, на кожному кроці будується дотична до графіка функції у точці чергового наближення . Крапка перетину дотичної з віссю Ox буде наступною точкою наближення. Відповідно до розглянутого методу розрахунок наближеного значення кореня наi-ітерації проводиться за формулою:

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

Умовою закінчення ітераційного процесу є виконання наступної умови:

де ˗ допустима похибка визначення кореня.

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

Математичне обґрунтування

Нехай дана речова функція, яка визначена і безперервна на ділянці, що розглядається. Необхідно знайти речовий корінь розглянутої функції.

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

Для найкращої збіжності методу у точці чергового наближення має виконуватися умова. Ця вимога означає, що корінь функції повинен відповідати екстремуму функції .

Похідна стискаючого відображеннявизначається у такому вигляді:

Виразимо з цього вираз зміннуза умови прийнятого раніше твердження про те, що за умови необхідно забезпечити умову . В результаті отримаємо вираз для визначення змінної:

З урахуванням цього стискаюча функція прийому наступний вид:

Таким чином алгоритм знаходження чисельного рішення рівняння зводиться до ітераційної процедури обчислення:

Алгоритм знаходження кореня нелінійного рівняння методом

1. Задати початкову точку наближеного значення кореня функції, і навіть похибка розрахунку (мале позитивне число ) і початковий крок ітерації ().

2. Виконати розрахунок наближеного значення кореня функції відповідно до формули:

3. Перевіряємо наближене значення кореня щодо заданої точності, у разі:

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

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

Приклад розв'язування рівнянь

за методомНьютона для рівняння з однією змінною

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

Варіант розв'язання нелінійного рівняння у програмному комплексіMathCADпредставлений малюнку 3.

Результати розрахунків, саме динаміка зміни наближеного значення кореня, і навіть похибки розрахунку кроку ітерації представлені у графічній формі (див. рис.2).

Рис.2. Результати розрахунку за методом Ньютона для рівняння з однією змінною

Для забезпечення заданої точності при пошуку наближеного значення кореня рівняння в діапазоні необхідно виконати 4 ітерації. на останньому кроціітерації наближене значення кореня нелінійного рівняння визначатиметься значенням: .

Рис.3 . Лістинг програми вMathCad

Модифікації методу Ньютона для рівняння з однією змінною

Існує кілька модифікацій методу Ньютона, спрямованих спрощення обчислювального процесу.

Спрощений метод Ньютона

Відповідно до методу Ньютона потрібно обчислювати похідну функції f(x) на кожному кроці ітерації, що веде до збільшення обчислювальних витрат. Для зменшення витрат, пов'язаних з обчисленням похідної на кожному кроці розрахунку, можна провести заміну похідної f'(x n ) у точці x n у формулі на похідну f'(x 0) у точці x 0 . Відповідно до даного методу розрахунку наближене значення кореня визначається за такою формулою:Модифікований метод Ньютона

Різнисний метод Ньютона

У результаті наближене значення кореня функції f(x) визначатиметься виразом різницевого методу Ньютона:

Двох кроковий метод Ньютона

Відповідно до методу Ньютона потрібно обчислювати похідну функції f(x) кожному кроці ітерації, що завжди зручно, котрий іноді практично неможливо. Даний спосіб дозволяє похідну функції замінити різницевим ставленням (наближеним значенням):

В результаті наближене значення кореня функції f(x) визначатиметься таким виразом:

де

Рис.5 . Двох кроковий метод Ньютона

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

• назад
• Вперед

Для того, щоб додати коментар до статті, будь ласка, зареєструйтесь на сайті.

Розв'язання нелінійних рівнянь методом Ньютона

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

Основне гідністьметоду – він має швидку збіжність.

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

Розглянемо нелінійне рівняння у загальному вигляді:

Шукане рішення рівняння - точка, в якій крива перетинає вісь абсцис.

Задаємо початкове наближення невідомої х (0). Визначаємо значення функції у цій точці w(х (0))і проводимо дотичну до кривої в точці В. Точка перетину цієї дотичної з віссю абсцис визначає наступне наближення невідомої х (1)і т.д.

Розкладемо рівняння (1) у ряд Тейлора на околицях точки х (0). Розглянемо члени розкладання, що містять тільки 1 похідну:

(2)

х - х (0) = Δх- Поправка до невідомої. Якщо визначимо її, то зможемо визначити наступне наближення.

З (2) визначаємо поправку (3)

Тоді наступне наближення: (5)

Аналогічно отримуємо до-е наближення:

Це рекурентна формула методу Ньютонадля вирішення нелінійних рівнянь. Вона дає змогу визначати чергові наближення невідомих.

Формулу (6) можна отримати іншим способом з малюнка:

Ітераційний процес сходиться, якщо зменшується та наближається до 0 . Результат досягнуто, якщо .

Коментар до геометричної інтерпретації

Ітераційний крок методу зводиться до заміни кривої на пряму, яка описується лівою частиною рівняння (2). Вона є дотичною до кривої в точці. Цей процес називається лінеаризацією. Точка перетину дотичної до кривої з віссю хдає чергове наближення невідомої. Тому цей метод називається методом дотичних.

Приклад:

Приклад:

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

Простий спосіб визначення області розташування коренів - табуляція.

Ітераційний процес Ньютона не сходиться, якщо початкові наближення обрані так, що:

Процес або не сходиться чи сходиться дуже погано.

Метод Ньютона-Рафсона для вирішення СНАУ

Рафсон показав, що ітераційний метод Ньютона, запропонований на вирішення одногонелінійного рівняння, можна використовувати для вирішення системнелінійних рівнянь.

При цьому, для вирішення систем нелінійних рівнянь потрібно замість однієї невідомої розглядати сукупність (вектор) невідомих:

замість однієї нев'язки рівняння, розглядаємо вектор нев'язокрівнянь системи:

Одна похідна (6) заміщається матрицею похідних. Операція поділу (6) заміщається множенням на зворотнуматрицю похідних. У цьому випадку метод Ньютона-Рафсона відрізняється від методу Ньютона переходом від одновимірної задачі до багатовимірної.

Розглянемо систему дійсних нелінійних алгебраїчних рівнянь:

(7)

У матричному вигляді її можна записати:

де Х= х 2 – вектор – стовпець невідомих;

w 1 (х 1, х 2, … х n)

W = w 2 (х 1, х 2, ... х n) - Вектор-функція.

w n (х 1, х 2, … х n)

Нехай - Початкові наближення невідомих. Розкладемо кожне рівняння системи (7) у ряд Тейлора в околиці точки Х (0)тобто виконаємо наближену заміну вихідних нелінійних рівнянь лінійними, в яких зберігається тільки 1-а похідна (лінеаризація). У результаті система рівнянь (7) набуває вигляду:

(9)

В результаті отримали систему лінійних рівнянь(лінеаризована система), у якій невідомими є поправки. Коефіцієнти при невідомих у цій системі - перші похідні від рівнянь w jвихідної нелінійної системи за всіма невідомими Х i.. Вони утворюють матрицю коефіцієнтів - матрицю Якобі:

=

Кожен рядок матриці складається з перших похідних від чергового рівняння нелінійної системи по всіх невідомих.

Запишемо лінеаризовану систему (9) у матричній формі:

(10)

Тут - вектор нев'язок рівнянь вихідної системи. Його елементи отримуємо при підстановці в рівняння нелінійної системи чергових наближень невідомих;

- матриця Якобі. Її елементами є перші приватні виробничі від усіх рівнянь вихідної системи по всіх невідомих;

- вектор поправокдо невідомих. На кожній ітерації він може бути записаний:

Систему (10) з урахуванням прийнятих позначень можна записати:

(12)

Ця система лінійнащодо поправок ΔХ (к).

Система (13) – лінеаризована система рівнянь, якою замінюється вихідна СНАУ на кожному кроці ітераційного процесу.

Система (13) вирішується будь-яким відомим способомв результаті знаходимо вектор поправок. Потім з (11) можемо знайти чергові наближенняневідомих:

Т.о. кожен крок ітераційногопроцесу полягає у вирішенні лінійної системи (13) і визначенні чергового наближення з (14).

З (11) та (12) можна отримати загальну рекурентну формулу(у матричному вигляді), що відповідає методу Ньютона-Рафсона:

(15)

Вона має структуру, що відповідає формулі (6).

Формула (15) у практичних розрахунках використовується рідкотому що тут потрібно звертати матрицю Якобі (великої розмірності) на кожній ітерації розрахунків. У реальних розрахунках поправки визначаються результаті рішення лінійної системи (13).

Контроль завершенняітераційного процесу виконуємо по вектору нев'язок:

Ця умова повинна виконуватися для нев'язок всіхрівнянь системи.

Алгоритм рішення СНАУ методом Ньютона-Рафсона

1. Завдання вектора початкових наближень невідомих.

Завдання точності розрахунку є , інших параметрів розрахунку

2. Визначення нев'язок нелінійних рівнянь у точці наближення;

2.3. Визначення елементів матриці Якобі в точці чергового наближення невідомих;

2.4. Рішення лінеаризованої системи (13) будь-яким відомим методом. Визначення поправок до невідомих.

2.5. Визначення чергового наближення невідомих відповідно до (14).

2.6. Контролює завершення ітераційного процесу відповідно до (16). Якщо умова не виконується, повернення до пункту 2.

Прикладник:

Вирішити СЛАУ методом Ньютона-Рафсона:

(Рішення Х 1 = Х 2 = 2)

Запишемо рівняння у вигляді нев'язок:

Визначаємо елементи матриці Якобі:

Матриця Якобі:

Реалізуємо алгоритм методу Ньютона-Рафсона:

1) Перша ітерація:

Початкові наближення

Нев'язки

Матриця Якобі:

Лінеаризована система рівнянь:

1-е наближення невідомих:

2) Друга ітерація

3) Третя ітерація:

… ……… …… …… …… ……..

Рішення систем рівнянь режиму, що встановився, методом Ньютона-Рафсона

Нелінійне рівняння встановленого режиму у формі балансу потужності для -го вузла має вигляд:

(17)

Це рівняння з комплексними невідомими та коефіцієнтами. Для того, щоб такі рівняння виду (17) можна було вирішуватиметодом Ньюто-на-Рафсона, їх перетворять: поділяють дійсні та уявні частини. Внаслідок цього кожне комплексне рівняннявиду (17) розпадається на два дійсні рівняння, які відповідають балансу активної та реактивної потужності у вузлі:

Тут-задані потужності у вузлі;

Невідомі складові напруги у вузлах. Їх потрібно

визначити у результаті розрахунку.

У правій частині рівнянь (18) - розрахункова сумарна потужність перетоків у гілках, відповідних до -му вузлу.

Запишемо ці рівняння (18) у вигляді нев'язок:

Нев'язки рівнянь (19) відповідає розрахунковому небалансуактивної та реактивної потужності в-му вузлі.

Нев'язки описують режим вузла і і є нелінійними функціями від невідомих напруг у вузлах. Потрібно, щоб -> 0.

Розв'язуватимемо методом Ньютона-Рафсона систему 2nрівнянь виду (19), тобто на вирішення завдання розрахунку встановленого режиму електричної мережі методом Ньютона - Рафсона потрібно:

1) сформувати систему 2nрівнянь виду (19) для всіх вузлів електричної мережі, крім балансуючих;

2) організувати ітераційний процес методу Ньютона-Рафсона

для розв'язання цієї системи рівнянь. В результаті рішення

отримуємо шукані складові напруги у вузлах .

Запишемо цю систему рівнянь у загальному вигляді:

(20)

Отримали систему 2 нелінійних рівнянь нев'язокз 2 невідомими, якими. Невідомими в ній є складові напруги - модулі та кути.

Для вирішення системи (20) методом Ньютона-Рафсона потрібно скласти допоміжнулінеаризовану систему рівнянь виду (13), вирішуючи яку на кожній ітерації, визначаємо поправки до невідомих:

(21)

З урахуванням прийнятих позначень система (21) може бути записана:

(22)

де -матриця Якобі, її елементами є приватні похідні від рівнянь системи (20) по всіх невідомих - складових напружень

Вектор нев'язок рівнянь системи (20). Їх значення отримуємо при підстановці рівняння чергових наближень невідомих;

Вектор поправок до невідомих:

; ΔӨ i = Ψ i (к+1) - Ө i (к), ΔU i = U i (к+1) - U i (к) .

Для визначення елементів матриці Якобі застосовуємо аналітичне диференціювання, тобто. диференціюємо кожне рівняння системи (20) за шуканими величинами – кутами та модулями напруг. Щоб сформувати матрицю Якобі, потрібно отримати аналітичні вирази для наступних похідних. видів:

1) Похідна від рівняння нев'язки активної потужності го вузла по куту напруги цього ж вузла: ;

2) Похідна від рівняння нев'язки активної потужності го вузла по куту суміжної напруги j-го вузла: ;

3) Похідна від нев'язки активної потужності го вузла по модулю напруги цього ж вузла: ;

4) Похідна від нев'язки активної потужності го вузла по модулю напруги суміжного вузла: ;

Аналогічно визначаються ще чотири види похідних - похідні від рівнянь нев'язки реактивної потужності го вузла по всіх невідомих:

5) ; 6) ; 7) ; 8) .

З урахуванням цих похідних матрицю Якобі можна записати у загальному вигляді:

(23)

Визначимо аналітичні виразидля похідних, диференціюючи рівняння системи (20) за невідомими величинами. Вони мають вигляд:

(24)

Матриця Якобів загальному випадку- Квадратна матриця, симетрична, розмірністю, її елементами є приватні похідні від нев'язок рівнянь (небалансу потужностей) по всіх невідомих.

Якщо вузли не пов'язані між собою, то відповідні вироблені в матриці матриці Якобі, розташовані поза діагоналі, дорівнюватимуть нулю (аналогічно матриці провідностей) - т.к. у відповідних форму-лах (24) взаємна провідність y ijє співмножником і. y ij =0.

Кожен рядок матриці – похідні від чергового рівняння системи (20).

Наявність у схемі моделюваної мережі спеціальних вузлів (опорні і балансуючі вузли, вузли ФМ) позначається на структурісистеми рівнянь встановленого режиму і на структурі матриці Якобі:

1. Для вузлів з фіксацією модулянапруги (ФМ), в яких задані і невідомими є і , з матриці Якобі виключаєтьсярядок похідних (т.к. Q iне задана, те й рівняння балансу реактивної потужності (18), (19) скласти не можна) і стовпець похідних (т.к. модуль напруги U iвідомий і він виключається зі складу невідомих).

2. Для вузлів опорних та балансуючих – відповідні рядки та стовпці матриці виключаються;

3. Якщо вузли не пов'язані безпосередньо - відповідні вироблені в матриці дорівнюють нулю.

Матрицю Якобі можна розбити на чотири блоку:

1) - похідні від рівнянь небалансу активноюпотужності (20) кутахнапруги;

2) - похідні від рівнянь небалансу активноюпотужності по модулямнапруги;

3) - похідні від рівнянь небалансу реактивноюпотужності (20) кутахнапруги;

4) - похідні від рівнянь небалансу реактивноюпотужності по модулямнапруги.

Це матриці-клітини приватних похідних небалансів активної та реактивної потужностей за невідомими кутами та модулями напруг. Загалом, це квадратні матриці розмірністю n×n.

З огляду на це, матриця Якобі може бути представлена ​​у вигляді блоковоїмат-риці:

Де субвектор невідомих величин.

З урахуванням цього, Тоді лінеаризовану систему рівнянь (22) можна записати у вигляді:

. (25)

Вирішуючи цю лінійну системурівнянь (будь-яким відомим методом) на

до кожної ітерації методу, знаходимо поправки до невідомих, а потім і

чергові наближенняневідомих:

(26)

Чергове наближення невідомих можна також отримати з використанням. ітераційної формулиметоду Ньютона-Рафсона, аналогічною (15):

- · (27)

Тут потрібно звернення матриці Якобі кожної ітерації – громіздка обчислювальна операція.

Алгоритм розв'язання систем рівнянь встановленого режиму методом Ньютона - Рафсона

1. Завдання початкових значень невідомих напруг. Як початкових наближень приймаємо: , тобто. номінальна напруга вузлів;

2. Завдання умов розрахунку: точність ε , гранична кількістьітерацій, що прискорюють коефіцієнти та ін.

3. Визначення нев'язок рівнянь відповідно до рівнянь (20) при чергових наближеннях невідомих;

4. Визначення елементів матриці Якобі відповідно до (24) при чергових наближеннях невідомих;

5. Рішення лінеаризованої системи рівнянь (25) та визначення поправок до невідомих;

6. Визначення чергових наближень невідомих відповідно до (26);

7. Перевірка завершення ітераційного процесу:

Значення нев'язок рівнянь для всіх вузлів повинні бути менше заданої точності.

Якщо умова не виконується, то повернення до пункту 3 і повторення розрахунку при нових наближеннях невідомих.

Існує ряд модифікацій методу Ньютона-РафсонаВ тому числі:

1. Модифікований метод Ньютона-Рафсона.

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

2. Розділений метод Ньютона-Рафсона.

Похідні види дуже малі і їх значеннями можна набрати. В результаті, в матриці Якобі залишаються два блоки - 1-й і 4-й, і система (25), що складається з рівнянь, розпадаєтьсяна дві незалежні системи розмірністю . Кожна з цих систем вирішується окремо від іншої. Це призводить до скорочення обсягу обчислень та необхідної пам'яті ЕОМ.

Метод Ньютона (метод дотичних)

Нехай корінь рівняння f(x)=0 відокремлений на відрізку , причому перша та друга похідні f'(x) і f""(x)безперервні та знакопостійні при хÎ.

Нехай на деякому етапі уточнення кореня отримано (вибрано) чергове наближення до кореня х n . Тоді припустимо, що наступне наближення отримане за допомогою поправки h n , призводить до точного значеннякореня

x = х n + h n. (1.2.3-6)

Вважаючи h nмалою величиною, представимо f(х n + h n) у вигляді ряду Тейлора, обмежуючись лінійними доданками

f(хn+hn)» f(хn) + hnf'(хn). (1.2.3-7)

Враховуючи, що f(x) = f(xn + hn) = 0, отримаємо f(xn) + hnf '(xn) »0.

Звідси h n» - f(х n)/f'(х n). Підставимо значення h nв (1.2.3-6) і замість точного значення кореня xотримаємо чергове наближення

Формула (1.2.3-8) дозволяє отримати послідовність наближень x,тобто

Геометрична інтерпретація методу Ньютонаполягає в наступному
(Рис.1.2.3-6). Приймемо за початкове наближення x 0 правий кінець відрізка b і у відповідній точці 0 на графіку функції y = f(x) побудуємо дотичну. Точка перетину дотичної з віссю абсцис приймається за нове точніше наближення х 1 . Багаторазове повторення цієї процедури дозволяє отримати послідовність наближень х 0 х 1 х 2 , . . ., яка прагне точного значення кореня x.

Розрахункова формула методу Ньютона (1.2.3-8) можна отримати з геометричного побудови. Так у прямокутному трикутнику х 0 В 0 х 1 катет
х 0 х 1 = х 0 0 /tga. Враховуючи, що точка 0 знаходиться на графіку функції f(x),а гіпотенуза утворена дотичною до графіка f(x) у точці В 0 отримаємо

(1.2.3-9)

(1.2.3-10)

Ця формула збігається з (1.2.3-8) для n-го наближення.

З рис.1.2.3-6 видно, що вибір як початкового наближення точки а може призвести до того, що наступне наближення х 1 виявиться поза відрізком , на якому відокремлений корінь x. І тут збіжність процесу не гарантована. У загальному випадку вибір початкового наближення здійснюється відповідно до наступним правилом: за початкове наближення слід прийняти таку точку х 0 Î, у якій f(х 0)×f''(х 0)>0, тобто знаки функції та її другий похідний збігаються.

Умови збіжності методу Ньютона сформульовані у наступній теоремі.

Якщо корінь рівняння відокремлений на відрізку, причому f'(х 0)і f''(х) відмінні від нуля і зберігають свої знаки прихÎ, то, якщо вибрати як початкове наближення таку точкух 0 Î , що f(х 0).f¢¢(х 0)>0 , то корінь рівняння f(x)=0 може бути обчислений з будь-яким ступенем точності.

Оцінка похибки методу Ньютона визначається так:

(1.2.3-11)

де - найменше значення при

Найбільше значення при

Процес обчислень припиняється, якщо ,

де - задана точність.

Крім того, умовою досягнення заданої точності при уточненні кореня методом Ньютона можуть бути такі вирази:

Схема алгоритму методу Ньютона наведено на рис. 1.2.3-7.

Ліва частина вихідного рівняння f(x) та її похідна f'(x) в алгоритмі оформлені у вигляді окремих програмних модулів.

Рис. 1.2.3-7. Схема алгоритму методу Ньютона

Приклад 1.2.3-3.Уточнити методом Ньютона корені рівняння x-ln(x+2) = 0за умови, що коріння цього рівняння відокремлено на відрізках x 1 Î[-1.9;-1.1] та x 2 Î [-0.9;2 ].

Перша похідна f'(x) = 1 – 1/(x+2) зберігає свій знак кожному з відрізків:

f’(x)<0 при хÎ [-1.9; -1.1],

f’(x)>0 при хÎ [-0.9; 2].

Друга похідна f"(x) = 1/(x+2) 2 > 0 за будь-яких х.

Отже, умови збіжності виконуються. Оскільки f""(x)>0на всій області допустимих значень, то для уточнення кореня за початкове наближення x 1виберемо х 0 =-1,9 (оскільки f(-1,9)×f”(-1.9)>0). Отримаємо послідовність наближень:

Продовжуючи обчислення, отримаємо наступну послідовність перших чотирьох наближень: -1.9; -1.8552, -1.8421; -1.8414 . Значення функції f(x) у точці x=-1.8414 дорівнює f(-1.8414)=-0.00003 .

Для уточнення кореня x 2 Î[-0.9;2] виберемо як початкове наближення 0 =2 (f(2)×f”(2)>0). З х 0 = 2, отримаємо послідовність наближень: 2.0;1.1817; 1.1462; 1.1461. Значення функції f(x) у точці x=1.1461 дорівнює f(1.1461)=-0.00006.

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

Метод хорд

Геометрична інтерпретація методу хордполягає в наступному
(Рис.1.2.3-8).

Проведемо відрізок прямої через точки A та B. Чергове наближення x 1 є абсцисою точки перетину хорди з віссю 0х. Побудуємо рівняння відрізка прямої:

Покладемо y=0і знайдемо значення х=х 1 (чергове наближення):

Повторимо процес обчислень для отримання чергового наближення до кореня - х 2 :

У разі (рис.1.2.11) і розрахункова формула методу хорд матиме вигляд

Ця формула справедлива, коли за нерухому точку приймається точка b, а як початкове наближення виступає точка a.

Розглянемо інший випадок (рис. 1.2.3-9), коли .

Рівняння прямої для цього випадку має вигляд

Чергове наближення х 1 за y = 0

Тоді рекурентна формула методу хорд для цього випадку має вигляд

Слід зазначити, що за нерухому точку методу хорд вибирають той кінець відрізка , для якого виконується умова f (x)∙f¢¢ (x)>0.

Таким чином, якщо за нерухому точку прийняли точку а , то як початкове наближення виступає х 0 = b, і навпаки.

Достатні умови, які забезпечують обчислення кореня рівняння f(x)=0 за формулою хорд, будуть тими самими, що й методу дотичних (метод Ньютона), тільки замість початкового наближення вибирається нерухома точка. Метод хорд є модифікацією методу Ньютона. Різниця полягає в тому, що як чергове наближення в методі Ньютона виступає точка перетину дотичної з віссю 0Х, а в методі хорд - точка перетину хорди з віссю 0Х - наближення сходяться до кореня з різних сторін.

Оцінка похибки методу хорд визначається виразом

(1.2.3-15)

Умова закінчення процесу ітерацій за методом хорд

(1.2.3-16)

Якщо M 1<2m 1 , то для оценки погрешности метода может быть использована формула | x n -x n -1 |£e.

Приклад 1.2.3-4. Уточнити корінь рівняння e x - 3x = 0, відокремлений на відрізку з точністю 10 -4.

Перевіримо умову збіжності:

Отже, за нерухому точку слід вибрати а=0, а як початкове наближення прийняти х 0 =1, оскільки f(0)=1>0 і f(0)*f"(0)>0.

Завдання про знаходження рішень системи з n нелінійних алгебраїчних або трансцендентних рівнянь з невідомими виду

	f 1(x 1, x 2, … x n ) = 0,
	f 2(x 1, x 2, … x n ) = 0,
	……………………
	f n (x 1, x 2, ... x n) = 0,

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

У векторних позначеннях систему (6.1) можна записати у більш компактній формі

вектор стовпець функцій, символом () T позначена операція транспо-

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

Метод простої ітерації

p align="justify"> Метод простої ітерації для систем нелінійних рівнянь по суті є узагальненням однойменного методу для одного рівняння. Він заснований на тому, що система рівнянь (6.1) наводиться до вигляду

x 1 = g 1 (x 1, x 2, …, x n), x 2 = g 2 (x 1, x 2, …, x n),

……………………

x n = g n (x 1, x 2, …, x n),

та ітерації проводяться за формулами

x 1 (k + 1) = g 1 (x 1 (k), x 2 (k), …, x n (k)), x 2 (k + 1) = g 2 (x 1 (k), x 2 (k), …, x n (k)),

……………………………

x n (k + 1) = g n (x 1 (k), x 2 (k), …, x n (k)).

Тут верхній індекс свідчить про номер наближення. Ітераційний процес (6.3) починається з деякого початкового наближення

(x 1 (0 ) ,x 2 (0 ) ,… ,x n (0 ) ) і продовжуються до тих пір, поки модулі прирощень

всіх аргументів після однієї k-ітерації не стануть меншими за задану величинуε :x i (k + 1 ) − x i (k )< ε дляi = 1,2,… ,n .

Хоча метод простої ітерації прямо веде до рішення і легко програмується, він має дві істотні недоліки. Один із них – повільна збіжність. Інший полягає в тому, що якщо початкове наближення вибрано далеко від істинного рішення (X 1, X 2, ..., X n), то збіжність

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

Розв'язати систему нелінійних рівнянь:

	(x ...		) =0
F n (x 1 ...		x n) = 0.

Немає прямих методів вирішення нелінійних систем загального вигляду. Лише окремих випадках систему (4.1) можна вирішити безпосередньо. Наприклад, для двох рівнянь іноді вдається висловити одне невідоме через інше і таким чином звести завдання до вирішення одного нелінійного рівняння щодо одного невідомого.

Для вирішення систем нелінійних рівнянь зазвичай застосовуються ітераційні методи.

Метод Ньютона

У разі одного рівняння F(x) = 0 алгоритм методу Ньютона був легко отриманий шляхом запису рівнянь, що стосується кривої y = F(x). В основі методу Ньютона для систем рівнянь лежить використання розкладання функцій F 1 (x 1 ... x n ) в ряд Тейлора, причому члени,

щі другі (і вищих порядків) похідні, відкидаються. Нехай наближені значення невідомих системи (4.1) рівні зі-

відповідально a 1 ,a 2 ,....,a n . Завдання полягає у знаходженні прирощень (по-

правок) до цих значень	x 1 ,x 2 ,...,	x n , завдяки яким рішення сис-
теми запишеться у вигляді:
x 1= a 1+ x 1,	x 2= a 2+	x 2, ...., x n = a n + x n.

Проведемо розкладання лівих частин рівнянь (4.1) з урахуванням розкладання до ряду Тейлора, обмежуючись лише лінійними членами віднос-

тельно прирощень:
F1 (x1 ... xn) ≈ F1 (a1 ... an) +	∂ F 1	x 1+		+ ∂ F 1		x n,
	∂x			∂x
F2 (x1 ... xn) ≈ F2 (a1 ... an) +	∂ F 2	x 1+			∂ F 2	x n,
	∂x				∂x
...................................
F n(x 1 ... x n) ≈ F n(a 1 ... a n) +	∂ F n	x 1+			∂ F n	xn.
	∂x				∂x

Підставляючи в систему (4.1), отримаємо наступну систему лінійних рівнянь алгебри щодо прирощень:

∂ F 1			∂ F 1			+ ∂ F 1			= −F ,
∂x			∂x			∂x
∂ F 2			∂ F 2				∂ F 2		= −F ,
∂x			∂x				∂x
..............................
∂ F n			∂ F n				∂ F n		= −F.
∂x			∂x				∂x
Значення F 1 ...				похідні				обчислюються при

x 2 = a 2 … x n = a n .

Визначником системи (4.3) є якобіан:

∂ F 1		∂ F 1
∂x		∂x
∂ F 2		∂ F 2
J = ∂ x		∂ x.

… … … …

∂ F n… … ∂ F n∂ x 1 ∂ x n

x 1 = a 1,

Для існування єдиного рішення системи якобіан може бути відмінний від нуля кожної ітерації.

Таким чином, ітераційний процес розв'язання системи рівнянь методом Ньютона полягає у визначенні прирощень x 1, x 2, ..., x n до значень невідомих на кожній ітерації шляхом розв'язання системи лінійних рівнянь алгебри (4.3). Рахунок припиняється, якщо всі збільшення стають малими за абсолютною величиною: maxx i< ε . В ме-

Тоді Ньютона також важливий зручний вибір початкового наближення для забезпечення оптимальної збіжності. Збіжність погіршується із збільшенням числа рівнянь системи.

Як приклад розглянемо використання методу Ньютона на вирішення системи двох рівнянь:

∂ ∂ F 1. x

Величини, що стоять у правій частині, обчислюються при x = a, y = b.

Якщо виконуються умови		y − b		< εи		x − a			при заданому M , то
виводяться значення x і y ,	в іншому випадку								відбувається висновок
x, y, M.