69312

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

Лекция

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

Методи розв’язування систем нелінійних рівнянь Нехай маємо деяку систему нелінійних рівнянь 6.54 де Для розв’язку нелінійної системи 6. Якщо при k→∞ xik→αi i = 12n то кажуть що метод сходиться до деякого розв’язку.

Украинкский

2014-10-03

146 KB

14 чел.

Лекціія 14.

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

Нехай маємо деяку систему нелінійних рівнянь

 (6.53)

де fi, i = 1,2,…,n - функції дійсних змінних x1,x2,…,xn.

Для зручності викладу запишемо систему (6.1) у виді операторного рівняння

(6.54)

де


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

За аналогією з (6.5) для методу простої ітерації можна записати:

 (6.55)

чи

i = 1,..,n.

Метод полягає в тому, що за початковим значенням знаходиться наступне наближення за формулами:

, i = 1,2,…,n...

У загальному виді, якщо знайдене k-е наближення x1(k), x2(k),…,xn(k), то k + 1 наближення знаходиться за формулами

, i = 1,2,…,n...

Якщо при k→∞, xi(k)→αi, i = 1,2,…,n, то кажуть, що метод сходиться до деякого розв’язку. Для того, щоб отримати розв’язок з потрібною точністю ε, процес продовжують доти, доки два послідовних наближення будуть відрізнятися не більш, ніж на задану величину ε.

Збіжність ітерацій забезпечується, якщо виконується умова, аналогічна (6.7)

, (6.56)

де J(x) = Ψ’ - матриця Якобі, чи матриця частинних похідних системи функцій φ1,φ2,…φn по змінних x1,x2,…xn, тобто

Швидкість збіжності простих ітерацій як і раніше лінійна:

Одним із серйозних недоліків методу простої ітерації є складність вибору функцій φi, i = 1,2,…,n, які б задовольняли достатній умові збіжності (6.56).

Тому в більшості випадків для розв’язку системи нелінійних рівнянь використовується узагальнений метод Ньютона, для якого за аналогією з (6.13) записується базова матрично-векторна процедура:

 k = 0,1,2,…... (6.57)

де використовується інша матриця Якобі, обумовлена системою (6.53):

 (6.58)

Щоб уникнути процедури обернення матриці Якобі, матричне рівняння (6.56) переписується у виді системи лінійних рівнянь

 (6.59)

де

 і  (6.60)

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

Вважаючи, що матриця A(x(k)) є невиродженою, розвязують ітераційно систему лінійних рівнянь (6.59), починаючи з заданого початкового наближення x(0) = (x1(0),x2,(0),…,xn(0))t, і знаходять вектори x(k), k = 0,1,2,… Для того, щоб отримати розв’язок з потрібною точністю, процес продовжують доти, доки два послідовних наближення будуть відрізнятися один від одного не більш, ніж на задану похибку.

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

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

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

де ej - координатний вектор:hj = xj(k + 1) - xj(k)

Застосування різницевої апроксимації сповільнює процес розв’язку, тому що збіжність процедури від квадратичної зміщується до нелінійної з p =  = 1,618, як у метода хорд. При такій апроксимації первісна еквівалентна система лінійних рівнянь (6.53) перетвориться в систему рівнянь, що залежить від h:

 (6.61)

Якщо ввести hj = f(x(k)), то можна за аналогією з (6.38) отримати узагальнений метод Стефенсона.

При дуже великих розмірностях розв'язуваних систем нелінійних рівнянь можна також застосовувати нелінійний ітераційний метод Зейделя (глава 3), при якому кожне рівняння вихідної системи (6.47) зважується незалежно відносно тільки однієї змінної

 (6.62)

Приклад 6.12.

Розв’язати методом Ньютона наступну систему рівнянь:

при початкових умовах x0 = 1,5, y0 = 3,5

Спочатку обчислимо матрицю Якобі для заданих початкових умов:

Потім оцінюємо значення нев'язок

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

звідки

Продовжуючи виконувати аналогічним чином ітерації, переконаємося, що x2, y3.

Приклад 6.13.

Знайти, використовуючи пакет Mathematica, розв’язки системи нелінійних рівнянь методом Ньютона:

Визначимо Якобіан вихідної матриці

Ja[x_, y_] = Jac[{f1[x,y], f2[x,y]}, {x,y}]
{{-y+Sec[x-y]
2, -x-Sec[x-y]2}, (1.x, 4y}}
Det[Ja[1, 0.5]]]

3.89534

Якобіан не дорівнює нулю, визначимо вектор - функцію. Спочатку знайдемо матрицю, обернену до матриці Якобі, і визначимо її у вихідній точці.

Jin = Inverse[Ja[1, 0.5]]]

Визначимо вектор функції F() і Ψ()

F[X_List]: = [f1[x,y], f2[x,y]}/.(x- > X[[1]], y- > X[[2]]};
Z
[X]: = [X[[1]], X[[2]]}-Jin.F[x]

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

NestList[x, {1., 0.5}, 6]

Розв’яжемо розглянутий приклада стандартним оператором Mathematica

FindRoot[{f1[x,y] =  = 0, {f2[x,y] =  = 0, {x, 1.}, {y, 0.5}]

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

Висновки:

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

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

3. Поступове зрушення в область розв’язку забезпечує метод Давиденка (чи метод продовження розв’язку по параметру), за рахунок багаторазового розв’язку задачі, що модифікується під час розв’язку.

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

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

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

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

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

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

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

Вправи:

1.  Використовуючи метод Ньютона, знайти значення .

2.  Деякі комп'ютери не мають спеціального пристрою для поділу чисел. Щоб обчислити 1/y, y > 0 формується наближення зворотного числа, яке потім використовують як нульову ітерацію. Нехай f(x) = (1/x) - y. Показати, що формула методу Ньютона має вид
xk + 1 = xk(2 - yxk)

3 Користаючись цією формулою, обчислити 1/y для y = 1,2,…,10, поклавши x(0) = 0,01.

4 Використовуючи ту ж функцію f(x), повторити обчислення методом дихотомії. Вибрати початковий інтервал [0.001; 2].

5.  Розв’язати нелінійне рівняння (x + 1)ex - 1 - 1 = 0, використовуючи метод Ньютона
(Відповідь.
 x*0,6)

6.  Розв’язати нелінійне рівняння ex - x2 - 2x - 2 = 0, використовуючи метод Ньютона при початковому значенні x(0) = 2,0.
(Відповідь. x*2,7)

7. Розв’язати нелінійне рівняння 1 - x - e - 2x = 0, використовуючи метод Ньютона. Довести, що рівняння має два дійсних корені.
(Відповідь.
x10,x20,8 )

6. Розв’язати нелінійне рівняння e - 2x - 1 + x = 0 методом дихотомії. Знайти інтервал ізоляції кореня.
(Відповідь. 0.775 <
x < 0.8.)

7. Знайти 10 найменших позитивних значень x, для яких пряма y = x перетинає графік y = tg x. Розв’язок цієї задачі використовується при визначенні максимального навантаження, що може нести стержень без зміни форми. (Каханер-Демидович )

8. Знайти дійсні корені рівняння x4 - 3x2 + 75x - 10000 = 0 (Каханер-Демидович)

9. Застосувати метод Ньютона до рівняння f(x) = (x - 1)2, що має нуль кратності 2.

10. Рівняння Кеплера для обчислення орбіти має вигляд M = E - esinE Символи M, E і e позначають середню аномалію, ексцентричну аномалію та ексцентриситет орбіти. Знайти E, якщо M = 24,85109 і e = 0,1.

11. Розв’язати наступну систему рівнянь
припускаючи, що
x1 ≥ 0, x2π/2, x3 > 0
(Відповідь:
x1 = 35,55, x2 = 44,91, x30,65)

12. Знайти розв’язки наступних систем рівнянь

PAGE  140


 

А также другие работы, которые могут Вас заинтересовать

73550. Сущность информационного рынка как социально-экономического явления 106 KB
  Сущность и определение понятия информационный рынок. Сущность и определение понятия информационный рынок Одним из основных понятий современной рыночной экономики является понятие информационный рынок. Прежде чем перейти непосредственно к понятию информационный рынок необходимо обратиться к содержанию понятия рынок: Существует множество определений...
73551. Методи розрахунку лінійних електричних кіл (ЛЕК) постійного струму при наявності двох і більше джерел живлення 468 KB
  Метод вузлових і контурних рівнянь полягає в складанні на основі законів Кірхгофа системи вузлових і контурних рівнянь, що містять невідомі величини струмів, які протікають у вітках кола, та розв’язання цієї системи рівнянь шляхом підстановок або за допомогою матриць та формул Крамера.
73552. УКРАїНСЬКА ІСТОРІОГРАФіЯ ЗА КНЯЖОЇ ДОБИ (ХІ- ХШ ст.) 61 KB
  Ми не будемо тут більш детально на цьому зупинятися і з’ясовувати, чи була Київська Русь українською державою, чи це було “Русское государство”, чи це була “колиска”, з якої виросли три східнослов’янські народи – російський, український і білоруський. З цього приводу існує маса літератури
73553. Історичні знання в Україні в литовсько-польську добу 85 KB
  Методологічною основою продовжує залишатися провіденціалізм, хоча окремі оповідання носять характер прагматичного оповідання. Прагматизм - це напрям в історії, який обмежується викладом подій в їх зовнішніх звязках і послідовності, не викриваючи обєктивних законів історичного розвитку.
73554. Символічний метод розрахунку лінійних електричних кіл (ЛЕК) однофазного синусоїдного змінного струму 856.5 KB
  Розрахункові дії з комплексними параметрами ЛЕК однофазного СЗС. Закони Ома і Кірхгофа в комплексній формі. Символічний метод розрахунку однофазних кіл СЗС з одним джерелом ЕРС.
73555. Українська історіографія в епоху Гетьманщини 177 KB
  Події від середини ХVІІ і до кінця ХVІІІ ст. – це період Національної революції, Гетьманщини і ліквідації автономного ладу України в складі Російської імперії. Національна революція, що почалася 1848 року, привела до утворення Української гетьманської держави. На червень 1652 року Україна фактично виборола незалежність
73556. Введение в высокотемпературную теплотехнологию и энергетику теплотехнологии 32.17 MB
  Возобновляемые источники энергии – энергия солнца ветра тепла земли естественного движения водных потоков а также энергия существующих в природе градиентов температур. Возобновляемые ТЭР основаны на использовании возобновляемых источников энергии: солнечного излучения энергии морей рек и океанов внутреннего тепла Земли воды и воздуха энергии естественного движения водных потоков и существующих...
73557. Методи розрахунку однофазних лінійних електричних кіл синусоїдного змінного струму при наявності двох і більше джерел живлення 668.5 KB
  Застосування символічного методу при розрахунку Іф кіл СЗС при наявності двох і більше джерел живлення. Методи вузлових і контурних рівнянь та контурних струмів. Методи вузлових потенціалів (двох вузлів) та суперпозиції. Метод еквівалентного генератора.
73558. Українська історіографія на початку національного відродження (кінець XVIII — перша половина XIX ст.) 97 KB
  Україна переживала з кінця XVIII століття складний етап своєї історії. Після поділу Польщі українські землі опинилися у складі двох імперій: Російської (80% території) і Австрійської. Суспільне життя краю характеризувалося кризою кріпосницького ладу, розгортанням російського визвольногопольського національно-визвольного та процесом українського національного відродження.