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) е изпълнено, тогава избираме (2.6) като приблизително решение на система (1.1) и завършваме изчисленията. Ако условието (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) задаваме
,a .

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. Числени методи за решаване на системи от линейни алгебрични уравнения (СЛАУ).

Обективен. Запознаване с някои приближени методи за решаване на СЛАУ и тяхната числена реализация на компютър.

Предварителни бележки.Всички методи за решаване на SLAE обикновено се разделят на две големи групи. Първата група включва методи, които обикновено се наричат ​​точни. Тези методи позволяват на всяка система да намира точните стойности на неизвестните след краен брой аритметични операции, всяка от които се изпълнява точно.

Втората група включва всички методи, които не са точни. Те се наричат ​​итеративни, или числени, или приблизителни. Точното решение, когато се използват такива методи, се получава в резултат на безкраен процес на приближения. Привлекателна характеристика на такива методи е тяхната самокорекция и лекота на внедряване на компютър.

Нека разгледаме някои приблизителни методи за решаване на SLAE и да конструираме алгоритми за тяхната числена реализация. Ще получим приблизително решение на SLAE с точност до , където е някакво много малко положително число.

1. Итерационен метод.

Нека SLAE е даден във формата

(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. Метод на простата итерация.

Нека системата от линейни алгебрични уравнения (SLAE) е дадена във формата

(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. Стационарен метод на Seidel.

Методът на Seidel за решаване на SLAE се различава от итерационния метод по това, че след като сме намерили някакво приближение за -тия компонент, ние незабавно го използваме, за да намерим следното
,
, …, ти компонент. Този подход дава възможност да се осигури по-висока скорост на сходимост на метода на Seidel в сравнение с итерационния метод.

Нека SLAE е даден във формата

(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. Нестационарен метод на Зайдел.

Този метод за решаване на SLAE (3.1) осигурява още по-висока степен на сходимост на метода на Seidel.

Нека компонентите на -тото приближение и -тото приближение са намерени по някакъв начин за системата (3.1).

Изчислете корекционния вектор

Нека изчислим стойностите

, (4.2)

Подредете количествата
, в низходящ ред.

В същия ред пренаписваме уравненията в системата (3.1) и неизвестните в тази система., : Линееналгебраи нелинейни ... Управлениезалаборатория върши работаНа ... методическиинструкции запрактиченвърши работаНа застуденти ...

Учебна литература (природонаучни и технически) 2000-2011 opd цикъл - 10 години sd цикъл - 5 години

Литература

... Естественонаукаобщо 1. Астрономия [Текст]: наръчник за ... Численметоди: Линееналгебраи нелинейни ... Управлениезалаборатория върши работаНа ... методическиинструкции запрактиченвърши работаНадисциплина "Икономика на транспорта" застуденти ...

- естествени науки (1)

Урок

... управлениезастудентии учители, предназначени заизползвайте не само в изследването методиработа... поколение практиченумения, използващи реални данни. методиченпрепоръки Накредит работаНададено...

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

Документ

... застудентиестествено- ... върши работаНадисциплина "Генетика и селекция", посветена на актуални въпроситова наука. Систематизирана независима работастудентиНатеоретични и практичен ... линеен, нелинейни, динамичен. всичко методи ...

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

Списък на учебниците

Определител на Еремин линеени нелинейниалгебра : линеени нелинейнипрограмиране: ново метод/ Еремин, Михаил... Застудентии преподаватели по геоложки специалности на университети. kx-1 1794549 99. D3 P 693 ПрактиченуправлениеНа ...

Методът на Нютон (известен също като метод на допирателната) е итеративен числен метод за намиране на корен (нула) дадена функция. Методът е предложен за първи път от английския физик, математик и астроном Исак Нютон (1643-1727), под чието име той печели славата си.

Методът е описан от Исак Нютон в ръкописа De analysi per aequationes numero terminorum infinitas (лат. .Относноанализ чрез уравнения на безкрайни серии), адресиран през 1669 г. до Бароу и в De metodis fluxionum et serierum infinitarum (лат. Метод на флуксии и безкрайни серии) или Geometria analytica ( лат.Аналитиченгеометрия) в колекциите на Нютон, който е написан през 1671 г. Въпреки това, описанието на метода се различава значително от настоящото му представяне: Нютон прилага своя метод изключително към полиноми. Той изчислява не последователни приближения x n , а поредица от полиноми и в резултат получава приблизително решение x.

Методът е публикуван за първи път в Алгебра от Джон Уолис през 1685 г., по чиято молба е описан накратко от самия Нютон. През 1690 г. Джоузеф Рафсън публикува опростено описание в Analysis aequationum universalis (лат. Общ анализуравнения).Рафсън разглежда метода на Нютон като чисто алгебричен и ограничава приложението му до полиноми, но той описва метода, базиран на последователни приближения на x n вместо по-трудната за разбиране последователност от полиноми, използвани от Нютон.

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

В съответствие с този метод проблемът за намиране на корена на функция се свежда до проблема за намиране на пресечната точка с абсцисната ос на допирателната, начертана върху графиката на функцията.

Фиг. 1 . Графика на промяна на функцията

Допирателната, начертана във всяка точка на графиката на функцията, се определя от производната на дадената функция в разглежданата точка, която от своя страна се определя от тангенса на ъгъла α (). Точката на пресичане на допирателната с абсцисната ос се определя въз основа на следната връзка в правоъгълен триъгълник: тангенс на ъгълв правоъгълен триъгълник се определя от отношението на срещуположния катет към съседния катет на триъгълника. Така на всяка стъпка се изгражда допирателна към графиката на функцията в точката на следващото приближение . Пресечна точка на допирателната с оставол ще бъде следващата точка на подход. В съответствие с разглеждания метод, изчисляването на приблизителната стойност на корена нааз-итерациите се правят по формулата:

Наклонът на правата линия се регулира с всяка стъпка по най-добрия начин, но трябва да обърнете внимание на факта, че алгоритъмът не взема предвид кривината на графиката и следователно в процеса на изчисление остава неизвестно в каква посока може да се отклони графиката.

Условието за приключване на итеративния процес е изпълнението на следното условие:

където ˗ допустима грешка при определяне на корена.

Методът има квадратична сходимост. Квадратната скорост на конвергенция означава, че броят на правилните цифри в приближението се удвоява с всяка итерация.

Математическа обосновка

Нека е дадена реална функция, която е определена и непрекъсната върху разглеждания участък. Необходимо е да се намери истинският корен на разглежданата функция.

Извеждането на уравнението се основава на метода прости итерации, според което уравнението води до еквивалентно уравнение за всяка функция . Нека въведем концепцията за картографиране на свиване, която се дефинира от отношението .

За най-добра сходимост на метода в точката на следващото приближение трябва да е изпълнено условието. Това изискване означава, че коренът на функцията трябва да съответства на екстремума на функцията.

Производна на картографиране на свиванесе определя в следната форма:

Нека изразим променлива от този изразпри спазване на предварително приетото твърдение, че за е необходимо да се осигури условието. В резултат на това получаваме израз за определяне на променливата:

Като се има предвид това, приемането на функцията на свиване е както следва:

По този начин алгоритъмът за намиране на числено решение на уравнението се свежда до итеративна изчислителна процедура:

Алгоритъм за намиране на корена на нелинейно уравнение по метода

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 . Двуетапният метод на Нютон

Методът на секанса е двуетапен метод, т.е. ново приближениеопределени от две предишни итерациии . Методът изисква две начални приближенияи . Скоростта на сходимост на метода ще бъде линейна.

• обратно
• Напред

За да добавите коментар към статията, моля, регистрирайте се на сайта.

Решаване на нелинейни уравнения по метода на Нютон

Има няколко модификации на метода за решаване на проблеми с електроенергията. Те позволяват да се увеличи скоростта на конвергенция на итеративния процес и да се намали времето за изчисление.

Основен достойнствометод - има бърза конвергенция.

Идеята на методасе състои в последователна замяна при всяка итерация на изчислението на оригиналната нелинейна система от уравнения с някаква спомагателна линейна система от уравнения, чието решение позволява да се получи следващото приближение на неизвестните, по-близо до желаното решение ( линеаризация).

Разгледайте нелинейно уравнение в общ вид:

Желаното решение на уравнението е точката, в която кривата пресича оста x.

Задаваме първоначалното приближение на неизвестното x(0). Определете стойността на функцията в тази точка w(x(0))и начертайте допирателна към кривата в точка B. Точката на пресичане на тази допирателна с оста x определя следващото приближение на неизвестното x (1)и т.н.

Нека разширим уравнение (1) в редица на Тейлър в близост до точката x(0). Помислете за условията на разширение, съдържащи само 1-вата производна:

(2)

x - x (0) = Δx- корекция на неизвестното. Ако го дефинираме, тогава можем да определим следващото приближение.

От (2) определяме корекцията (3)

Тогава следващото приближение: (5)

По същия начин получаваме да се-ти приближения:

то рекурентна формула на метода на Нютонза решаване на нелинейни уравнения. Позволява да се определят последователни приближения на неизвестни.

Формула (6) може да се получи и по друг начин от фигурата:

Итеративният процес се сближава, ако намалява и се приближава 0 . Резултатът се постига, ако.

Коментар на геометричната интерпретация

Итеративната стъпка на метода се свежда до замяна на кривата с права линия, която се описва от лявата страна на уравнение (2). Тя е допирателна към кривата в точката . Този процес се нарича линеаризация. Пресечна точка на допирателната към кривата с оста хдава друго приближение на неизвестното. Следователно този метод се нарича метод на допирателната.

Пример:

Пример:

За да се определят по този метод всички корени на нелинейно уравнение, е необходимо да се определи по какъвто и да е начин приблизителенместоположението на тези корени и задайте началните приближения в близост до тях.

Лесен начин за определяне на площта на корена е табулиране.

Итеративен процес на Нютон не се сближава, ако първоначалните приближения са избрани така, че:

Процесът или не се сближава, или се сближава много зле.

Метод на Нютон-Рафсън за SNAU решение

Рафсън показа, че итеративният метод на Нютон е предложен за решаване единнелинейни уравнения, може да се използва за решаване системинелинейни уравнения.

В същото време, за да се решат системи от нелинейни уравнения, вместо едно неизвестно, е необходимо да се разгледа наборът (вектор) неизвестен:

вместо един остатък от уравнението, ние считаме остатъчен векторсистемни уравнения:

Една производна в (6) се заменя матрица от производни. Операцията деление в (6) се заменя с умножение по обратенматрица от производни. В този случай методът на Нютон-Рафсън се различава от метода на Нютон чрез прехода от едномерен проблем към многоизмерен.

Помислете за система от реални нелинейни алгебрични уравнения:

(7)

Може да се запише в матрична форма:

където х= x 2 - вектор - колона от неизвестни;

w 1 (x 1, x 2, ... x n)

У = w 2 (x 1, x 2, ... x n) е векторна функция.

w n (x 1, x 2, ... x n)

Позволявам са първоначалните приближения на неизвестните. Нека разширим всяко уравнение на система (7) в серия на Тейлър в близост до точката X (0), тоест извършваме приблизителна замяна на оригиналните нелинейни уравнения с линейни, в които се запазва само 1-вата производна (линеаризация). В резултат на това системата от уравнения (7) приема формата:

(9)

В резултат на това получихме система от линейни уравнения(линеаризирана система), в която корекциите са неизвестни. Коефициентите за неизвестни в тази система са първите производни на уравненията wjна оригиналната нелинейна система във всички неизвестни Xi.. Те образуват матрица от коефициенти - Якобиева матрица:

=

Всеки ред на матрицата се състои от първите производни на следващото уравнение на нелинейната система във всички неизвестни.

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

(10)

Тук е векторът на остатъците от уравненията на първоначалната система. Неговите елементи се получават чрез заместване на неизвестни в уравненията на нелинейна система от последователни приближения;

- матрица на Якоби. Неговите елементи са първите частни производни на всички уравнения на изходната система във всички неизвестни;

- корекционен векторкъм желаните неизвестни. При всяка итерация може да се запише:

Система (10), като се вземе предвид приетата нотация, може да бъде записана:

(12)

Тази система линеенотносно измененията ΔX (k).

Система (13) е линеаризирана система от уравнения, която замества оригиналния SNAU на всяка стъпка от итеративния процес.

Система (13) се решава по всяко познат начин, като резултат намираме корекционния вектор . Тогава от (11) можем да намерим последователни приближениянеизвестен:

Че. всеки итеративна стъпкаПроцесът се състои в решаване на линейната система (13) и определяне на следващото приближение от (14).

От (11) и (12) може да се получи общата сума повтаряща се формула(в матрична форма), съответстващ на метода на Нютон-Рафсън:

(15)

Той има структура, съответстваща на формула (6).

Формула (15) се използва при практически изчисления Рядко, тъй като тук е необходимо да се обърне якобиевата матрица (с висока размерност) при всяка итерация на изчисленията. При реални изчисления корекциите се определят чрез решаване на линейната система (13).

Контрол на завършванетона итеративния процес, изпълняваме върху вектора на остатъците:

Това условие трябва да бъде изпълнено за остатъците всичкосистемни уравнения.

Алгоритъм за решаване на SNAU по метода на Нютон-Рафсън

1. Задаване на вектора на началните приближения на неизвестните.

Задайте точност на изчислението є , други параметри за изчисление

2. Определяне на остатъците на нелинейни уравнения в точката на апроксимация;

2.3. Определяне на елементите на матрицата на Якоби в точката на следващото приближение на неизвестните;

2.4. Решението на линеаризираната система (13) по произволен известен метод. Определяне на корекции към неизвестни.

2.5. Дефиниране на следващото приближение на неизвестните в съответствие с (14).

2.6. Контрол на завършването на итеративния процес в съответствие с (16). Ако условието не е изпълнено, върнете се към стъпка 2.

Пример:

Решете SLAE по метода на Нютон-Рафсън:

(разтвор X 1 \u003d X 2 \u003d 2)

Записваме уравненията под формата на остатъци:

Определяме елементите на матрицата на Якоби:

Матрица на Якоби:

Ние прилагаме алгоритъма на метода на Нютон-Рафсън:

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 (k+1) - Ө i (k), ΔU i \u003d U i (k + 1) - U i (k) .

За да определим елементите на матрицата на Якоби, използваме аналитична диференциация, т.е. диференцираме всяко уравнение на системата (20) по отношение на търсените стойности – ъгли и модули на напрежение. За да се формира матрицата на Якоби, трябва да се получат аналитични изрази за производните на следното видове:

1) Производна на остатъчното уравнение на активната мощност на тития възел по отношение на ъгъла на напрежението на същия възел: ;

2) Производната на остатъчното уравнение на активната мощност на тития възел по отношение на ъгъла на напрежението на съседния j-ти възел: ;

3) Производна на несъответствието на активната мощност на тития възел по модул на напрежението на същия възел: ;

4) Производна на несъответствието на активната мощност на тития възел по модул на напрежението на съседния възел: ;

По същия начин са дефинирани още четири вида производни - производни на уравненията за остатъчна реактивна мощност на тития възел във всички неизвестни:

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

Като се вземат предвид тези производни, матрицата на Якоби може да бъде записана в общата форма:

(23)

Да дефинираме аналитични изразиза производни, диференциращи уравненията на системата (20) по отношение на неизвестни величини. Те изглеждат така:

(24)

Якобиева матрицав общ случай- квадратна матрица, симетрична, размерност, нейните елементи са частни производни на остатъците от уравненията (мощен дисбаланс) във всички неизвестни.

Ако възлите не са свързани помежду си, тогава съответните производни в матрицата на Якоби, разположени извън диагонала, ще бъдат равни на нула (подобно на матрицата на проводимостта) - тъй като. в съответните формули (24) взаимната проводимост yijе фактор и. yij =0.

Всеки ред от матрицата е производната на следващото уравнение на системата (20).

Наличието в схемата на симулираната мрежа на специални възли (референтни и балансиращи възли, FM възли) влияе структурасистеми от уравнения в стационарно състояние и върху структурата на якобиевата матрица:

1. За възли с фиксиране на модуланапрежения (FM), в които дадени и неизвестни са и , от матрицата на Якоби изключенилиния от производни (тъй като 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)са непрекъснати и с постоянен знак за хн .

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

x \u003d x n + h n. (1.2.3-6)

Броене h nмалка стойност, представяме f(x n + h n) като серия на Тейлър, ограничавайки се до линейни членове

f(x n + h n) "f(x n) + h n f'(x n). (1.2.3-7)

Като се има предвид, че f(x) = f(х n + h n) = 0, получаваме f(х n) + h n f ’(х n) » 0.

Оттук h n "- f (x n) / f' (x n). Заместете стойността h nв (1.2.3-6) и вместо точната стойност на корена хполучаваме друго приближение

Формула (1.2.3-8) ви позволява да получите последователност от приближения x 1, x 2, x 3 ..., която при определени условия се сближава до точната стойност на корена х,това е

Геометрична интерпретация на метода на Нютоне както следва
(Фиг.1.2.3-6). Вземаме десния край на сегмента b като първоначално приближение x 0 и в съответната точка B 0 на графиката на функцията y \u003d f (x) изграждаме допирателна. Точката на пресичане на допирателната с оста x се приема като ново, по-точно приближение x 1 . Повтарянето на тази процедура много пъти ви позволява да получите поредица от приближения x 0, x 1, x 2 , . . ., което клони към точната стойност на корена х.

Изчислителната формула на метода на Нютон (1.2.3-8) може да се получи от геометрична конструкция. И така, в правоъгълен триъгълник x 0 B 0 x 1 катет
x 0 x 1 = x 0 V 0 / tga. Като се има предвид, че точка B 0 е на графиката на функцията f(x),и хипотенузата се образува от допирателна към графиката f (x) в точка B 0, получаваме

(1.2.3-9)

(1.2.3-10)

Тази формула съвпада с (1.2.3-8) за n-то приближение.

От Фиг.1.2.3-6 се вижда, че изборът на точка a като първоначално приближение може да доведе до факта, че следващото приближение x 1 ще бъде извън сегмента, на който е отделен коренът х. В този случай конвергенцията на процеса не е гарантирана. В общия случай изборът на първоначалното приближение се извършва в съответствие с следващото правило: за първоначално приближение трябва да се вземе такава точка x 0 n, в която f (x 0) × f '' (x 0)> 0, т.е. знаците на функцията и втората й производна съвпадат.

Условията за сходимост на метода на Нютон са формулирани в следната теорема.

Ако коренът на уравнението е отделен на отсечката, и f'(x 0) и f''(x) са различни от нула и запазват знаците си при xo, тогава ако изберем такава точка като първоначално приближениех 0 О , Какво f(x 0).f¢¢(x 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 при xО [-0,9; 2].

Второто производно f "(x) \u003d 1 / (x + 2) 2\u003e 0 за всяко x.

По този начин условията за конвергенция са изпълнени. Тъй като f "" (x)> 0 в целия диапазон от допустими стойности, тогава за прецизиране на корена за първоначалното приближение х 1изберете x 0 \u003d -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). Въз основа на x 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 е абсцисата на пресечната точка на хордата с оста 0x. Нека съставим уравнението на права отсечка:

Нека поставим y=0 и намерим стойността x=x 1 (друго приближение):

Повтаряме процеса на изчисление, за да получим следващото приближение на корена - x 2 :

В нашия случай (фиг.1.2.11) и формулата за изчисление на метода на акордите ще изглежда така

Тази формула е валидна, когато точка b се приема като фиксирана точка, а точка a действа като първоначално приближение.

Да разгледаме друг случай (фиг. 1.2.3-9), когато .

Уравнението на права линия за този случай има формата

Следващото приближение x 1 при y = 0

Тогава рекурсивната формула за метода на акордите за този случай има формата

Трябва да се отбележи, че за фиксирана точка в метода на хордите изберете края на сегмента, за който е изпълнено условието f (x)∙f¢¢ (x)>0.

Така, ако точката a се приеме за фиксирана точка , тогава x 0 = b действа като първоначално приближение и обратно.

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

Оценката на грешката на метода на акордите се определя от израза

(1.2.3-15)

Крайно условие на итерационния процес по метода на акордите

(1.2.3-16)

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

Пример 1.2.3-4. Посочете корена на уравнението e x - 3x = 0, отделен на отсечка с точност до 10 -4 .

Нека проверим условието за конвергенция:

Следователно a=0 трябва да бъде избрано като фиксирана точка и x 0 \u003d 1 трябва да се приеме като първоначално приближение, тъй като f (0) \u003d 1> 0 и f (0) * f "(0)> 0 .

Проблемът за намиране на решения на система от n нелинейни алгебрични или трансцендентни уравнения с n неизвестни от вида

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

широко разглеждани в изчислителната практика. Подобни системи от уравнения могат да възникнат например при числено моделиране на нелинейни физически системи на етапа на търсене на техните стационарни състояния. В редица случаи системи от вида (6.1) се получават косвено, в процеса на решаване на друга изчислителна задача. Например, когато се опитвате да минимизирате функция от няколко променливи, можете да потърсите тези точки в многомерно пространство, където градиентът на функцията е нула. В този случай трябва да се реши системата от уравнения (6.1) с левите части, проекциите на градиента върху координатните оси.

Във векторната нотация системата (6.1) може да бъде записана в по-компактна форма

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

Намирането на решения на система от нелинейни уравнения е много по-трудна задача от решаването на едно нелинейно уравнение. Въпреки това редица итеративни методи за решаване на нелинейни уравнения могат също да бъдат разширени до системи от нелинейни уравнения.

Метод на проста итерация

Методът на простата итерация за системи от нелинейни уравнения е по същество обобщение на едноименния метод за едно уравнение. Основава се на факта, че системата от уравнения (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) \u003d g 1 (x 1 (k), x 2 (k), ..., x n (k)), x 2 (k + 1) \u003d 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 ), тогава конвергенцията

методът не е гарантиран. Ясно е, че проблемът с избора на първоначалното приближение, който не е прост дори за едно уравнение, става много труден за нелинейни системи.

Решете системата от нелинейни уравнения:

	(х...		) =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	х 1+		+ ∂ F 1		xn,
	∂x			∂x
F2 (x1 ... xn ) ≈ F2 (a1 ... an ) +	∂F2	х 1+			∂F2	xn,
	∂x				∂x
...................................
F n(x 1 ... x n) ≈ F n(a 1 ... a n) +	∂Fn	х 1+			∂Fn	xn .
	∂x				∂x

Замествайки в системата (4.1), получаваме следната система от линейни алгебрични уравнения по отношение на нарастванията:

∂ F 1			∂ F 1			+ ∂ F 1			= -F,
∂x			∂x			∂x
∂F2			∂F2				∂F2		= -F,
∂x			∂x				∂x
..............................
∂Fn			∂Fn				∂Fn		= -F.
∂x			∂x				∂x
Стойности F 1 ...				производни				изчислено при

x 2 \u003d a 2, ... x n \u003d a n.

Детерминантата на системата (4.3) е Якобиан:

∂ F 1		∂ F 1
∂x		∂x
∂F2		∂F2
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.