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


 

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

33780. Понятие права собственности. Общая собственность 16.89 KB
  права собственности носят абсолютный характер. Иначе говоря в таких ситуациях два или более лица сообща становятся субъектами права собственности на одно и то же имущество вещь. Следовательно отношения общей собственности характеризуются множественностью субъектов права собственности на конкретный объект.
33781. Виды сделок 23.45 KB
  Таким образом сделку характеризуют следующие признаки: является юридическим актом сделка всегда волевой акт то есть действия людей это правомерное действие сделка специально направлена на возникновение прекращение или изменение гражданских правоотношений сделка порождает гражданские правоотношения только для её участников но иногда сделки в пользу третьего лица Виды сделок В научной литературе различают следующие основания классификации и соответствующие виды сделок: В зависимости от числа сторон: односторонние и многосторонние...
33782. Исковая давность 15.93 KB
  Виды сроков давности Вообще различают только два вида для сроков: общий 3 года например для исков по ничтожным сделкам специальные ранее назывались сокращенные сроки но чтобы не вводить в заблуждение нужно отметить некоторые специальные сроки длятся более 3 лет устанавливаются для особых случаев например 1 год для оспаривания недействительности оспоримых сделок Сроки по исковой давности не распространяется на: требования о защите личных неимущественных прав и других нематериальных благ кроме случаев предусмотренных законом;...
33783. Состав наследственного имущества 15.34 KB
  Из этого следует что самовольно возведенный дом или гараж объектом права собственности не является и в состав наследственного имущества включен быть не может. К числу переходящих по наследству объектов неимущественного характера относятся некоторые права в сфере интеллектуальной собственности.1112 ГК РФ в состав наследственного имущества не входят: права и обязанности неразрывно связанные с личностью наследодателя а именно: его право на алименты право на возмещение вреда причиненного его жизни или здоровью; права и обязанности...
33784. Представительство и доверенность 26.63 KB
  Основания возникновения и виды представительства Основания возникновения представительства: волеизъявление представляемого оно может быть отражено либо в доверенности либо в договоре; юридические факты указанные в законе например родители являются законными представителями своих детей без специальных полномочий в силу п. Представительство основанное на доверенности так как доверенность является односторонней сделкой совершаемой представляемым по его усмотрению. Представитель по доверенности как правило не обладает правом...
33785. Понятие семейного права. Источники семейного права 22.17 KB
  Источники семейного права. Семейное право это отрасль права которая регулирует семейные отношения возникающие из факта брака и принадлежности к семье. Сюда входят: заключение и прекращение брака; права и обязанности супругов; права и обязанности родителей и детей; алиментные обязательства членов семьи; применение российского семейного законодательства к семейным отношениям с участием иностранных граждан и лиц без гражданства; формы воспитания детей оставшихся без попечения родителей; признание брака фиктивным; лишение родительских прав и...
33786. Порядок и условия заключения и прекращения брака. Личные права и обязанностей супругов 22.6 KB
  Порядок заключения брака 1. Заключение брака производится в личном присутствии лиц вступающих в брак по истечении месяца со дня подачи ими заявления в органы записи актов гражданского состояния. При наличии уважительных причин орган записи актов гражданского состояния по месту государственной регистрации заключения брака может разрешить заключение брака до истечения месяца а также может увеличить этот срок но не более чем на месяц.
33787. Личные и имущественные права и обязанности родителей и детей 20.34 KB
  Права и обязанности родителей и детей можно аналогично правам и обязанностям супругов разделить на две группы: личные и имущественные а в составе последних их подразделяют на: а права и обязанности по поводу имущества и б алиментные права и обязанности. Права родителей по отношению к ребенку которым считается лицо не достигшее 18 лет обладают рядом особенностей: они имеют срочный характер существуют только в отношении несовершеннолетних детей. Кроме того права родителей прекращаются при вступлении несовершеннолетних детей в брак и в...
33788. Лишение родительских прав и восстановление в родительских правах 16.9 KB
  Родители один из родителей могут быть лишены родительских прав если они: уклоняются от выполнения обязанностей родителей в том числе при злостном уклонении от уплаты алиментов; отказываются без уважительных причин взять своего ребенка из родильного дома отделения либо из иного лечебного учреждения воспитательного учреждения учреждения социальной защиты населения или из других аналогичных учреждений; злоупотребляют своими родительскими правами; жестоко обращаются с детьми в том числе осуществляют физическое или психическое насилие над...