69312

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

Лекция

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

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

Украинкский

2014-10-03

146 KB

17 чел.

Лекціія 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


 

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

85408. Оценка конкурентоспособности фирмы и определение путей ее повышения 1.21 MB
  Объектом исследования выступало ООО «Стеклодом», занимающееся производством и установкой светопрозрачных конструкций (оконные и балконные дверные блоки). Предмет исследования – конкурентоспособность организации.
85409. PR-СОПРОВОЖДЕНИЕ ДЕЯТЕЛЬНОСТИ ФЕДЕРАЛЬНОГО КАЗНАЧЕЙСТВА 1.98 MB
  Цель исследования – исследовать основные направления информационной политики органов государственной власти, в частности исполнительной власти, и провести анализ функционирования коммуникационной модели взаимодействия Федерального казначейства с общественностью.
85410. Пути повышения эффективности маркетинговой деятельности ООО «Принт – Экспресс» с применением Интернет 756.5 KB
  Целью работы являлась дать заключение о целесообразности применения российскими предприятиями возможностей глобальной сети Интернет в маркетинговой деятельности и повышении эффективности маркетинговой деятельности при внедрении в нее интернет-технологий.
85411. Розробка комплексного закладу ресторанного господарства у складі ресторану української кухні на 100 місць та шинку на 20 місць по вул. Хотинській у м.Чернівці 906.5 KB
  Предмет досліджень - комплексний заклад ресторанного господарства у складі ресторану української кухні на 100 місць та шинку на 20 місць, наукове обґрунтування і розробка технологій десертів і з додаванням функціональної добавки, а саме яблучного кріопорошку.
85412. Разработка мероприятия по повышению эффективности управления мотивацией персонала ресторана «Охотников» 698 KB
  Мотивация сотрудников занимает одно из центральных мест в управлении персоналом, поскольку она выступает непосредственной причиной их поведения. Ориентация работников на достижение целей организации по существу является главной задачей руководства персоналом.
85413. Оценка эффективности производственно-хозяйственной деятельности предприятия ТОО «Промстройиндустрия» 2.18 MB
  Изучение деятельности дает вероятность выработать необходимую тактику и стратегию развития предприятия, на основе которых формируется производственная программа, выявляются резервы повышения эффективности производства. Повысить экономическую эффективность значит: добиться большего результата с наименьшими затратами ресурсов.
85414. Учет и аудит аутсорсинговой деятельности на примере ООО Каппа-Консалтинг 8.39 MB
  Глобализация мировой экономики и вступление РФ в международный рынок капитала создание рыночной системы учета и отчетности и переход на международные стандарты финансовой бухгалтерской отчетности МСФО потребовали создания новых элементов рыночной экономики фирм по оказанию бухгалтерских услуг аутсорсеров.
85416. Правовое положение государственных унитарных предприятий как субъектов гражданского оборота 165.3 KB
  Государственные унитарные предприятия являются одними из таких субъектов которые имеют насыщенные исторические и правовые корни. Сейчас являясь самостоятельным участником гражданского оборота государственные унитарные предприятия фигурируют едва ли не во всех отраслях экономики.