Квєтний Р.Н. Методи комп’Ютерних обчислень
Подождите немного. Документ загружается.
Нелінійні задачі
31
Глава 3. Нелінійні задачі
В цьому розділі розглянуті методи розв’язання нелінійних рівнянь та
систем рівнянь. До них зводиться багато практичних задач, наприклад,
розрахунки нелінійних електричних кіл та систем керування, розв’язання
нелінійних диференціальних рівнянь, аналіз стійкості систем шляхом
оцінки їх власних значень та ін.
Якщо для найпростіших видів алгебраїчних рівнянь (не вище
третього ступеня) існують точні аналітичні формули, то для
трансцендентних рівнянь і будь-яких систем рівнянь таких методів взагалі
не існує і слід користуватися тільки наближеними ітераційними методами
та алгоритмами, найбільш поширені з яких розглянуто нижче.
3.1. Розв’язання нелінійних рівнянь
Рівняння, в які входять тільки степені аргументу з відповідними
коефіцієнтами, називаються алгебраїчними.
Нелінійні рівняння, що містять тригонометричні або інші спеціальні
функції, називаються трансцендентними.
Загальний вигляд алгебраїчного рівняння:
0...)(
01
1
1
=++++=
−
−
axaxaxaxf
n
n
n
n
. (3.1)
Можна виділити деякі важливі властивості алгебраїчних рівнянь, що
спрощують визначення коренів. Тут і далі ми називаємо деякі властивості
теоремами, як це прийнято в математиці, але наводимо їх без доведень,
щоб не ускладнювати сприйняття матеріалу. За власним бажанням можна
довести ці теореми в якості додаткових самостійних завдань.
1. ОСНОВНА ТЕОРЕМА АЛГЕБРИ. Алгебраїчне рівняння порядку
n має n коренів, які можуть бути як дійсними, так і комплексними.
Кожен корінь рахується відповідну кількість разів, що дорівнює його
кратності. Кратність кореня
0
x рівняється
k
, якщо
0)(...)()(
0
)1(
0
''
0
'
====
−
xfxfxf
k
.
2. Якщо всі коефіцієнти
i
a рівняння (3.1) дійсні, то всі комплексні
корені утворюють комплексно-спряжені пари.
3.ТЕОРЕМА ДЕКАРТА. Число позитивних дійсних коренів
дорівнює або менше за число змін знаків в послідовності коефіцієнтів (те
Роман Квєтний Методи комп’ютерних обчислень
32
ж твердження справедливе відносно числа від’ємних дійсних коренів при
заміні в (3.1)
x
на -
x
).
4. ТЕОРЕМА ЛАГРАНЖА. Верхня межа позитивних дійсних
коренів визначається як
,a,
a
B
R
k
01
0
0
>+=
де
k
– номер першого від’ємного коефіцієнта;
B
– найбільша абсолютна
величина від’ємного коефіцієнта.
5. ТЕОРЕМА ГЮА. Якщо рівняння (3.1) має дійсні корені і дійсні
коефіцієнти, то
.aaa
kkk 11
2
+−
>
Нагадаємо, що прямі аналітичні методи існують лише для
алгебраїчних рівнянь не вище третього порядку, а для трансцендентних
рівнянь прямих методів взагалі не існує. При визначенні дійсних коренів
чисельними методами треба враховувати дві теореми. Перша дозволяє
відокремити корені, тобто встановити якомога тісніші інтервали
[]
β
λ, , в
яких знаходиться один і тільки один корінь рівняння, а друга – оцінити
ступінь наближення.
ТЕОРЕМА 1. Якщо безперервна функція )(
x
f
приймає значення
різних знаків на кінцях відрізка
[
]
β
λ
, , тобто 0)()(
<
β
λ
f
f
, то в середини
цього відрізка міститься щонайменше один корінь рівняння 0)( =
x
f
, тобто
знайдеться хоча б одне число
)
,
(
β
λ
∈
ξ
таке, що 0
=
ξ
)
(
f
.
ТЕОРЕМА 2. Нехай
ξ – точний, а
x
– наближений корені рівняння
0)( =
x
f
, які знаходяться на одному й тому ж відрізку
[]
βα, , причому
β≤≤α≥ xmxf ,)(
'
.
Тоді
m
)x(f
x ≤ξ−
.
Існує ряд методів наближеного розв’язання нелінійних рівнянь,
доцільність застосування кожного із яких визначається видом рівняння,
його порядком, потрібною точністю і т.д.
Слід також пам’ятати, що при визначенні великої кількості коренів
знижувати степінь початкового нелінійного рівняння шляхом ділення на
)(
i
xx − (де х
i
– корінь, що знайдено) треба дуже обережно, що пов’язано з
накопиченням похибки розповсюдження, яка буде міститися в
коефіцієнтах нового рівняння.
Нелінійні задачі
33
3.1.1. Метод половинного ділення
В цьому методі спочатку обчислюється значення функції в точках,
що розташовані через рівні інтервали на осі
x
. Коли )(
n
xf і )(
1+n
xf
мають протилежні знаки, знаходять
2
1 nn
cp
xx
x
+
=
+
, )(
cp
xf . Якщо знак
)(
cp
xf збігається зі знаком )(
n
xf , то надалі замість
n
x використовується
cp
x . Якщо ж )(
cp
xf має знак, протилежний знакові )(
n
xf , тобто збігається
зі знаком )(
1+n
xf , то на
cp
x замінюється
1+n
x . Відзначимо, що і в цьому, і в
наступних методах за умову припинення ітераційного процесу доцільно
брати умову
ε≤
−
+ nn
xx
1
, де
ε
– задана похибка знаходження кореня.
Графічне зображення методу подане на рисунку 3.1, а структура
алгоритму на рисунку 3.2.
Похибка розв’язку
∆ через n ітерацій знаходиться в межах
.xx
n
01
2
1
−≤∆
Метод має малу швидкість збіжності, оскільки інтервал, де
знаходиться корінь, з кожним кроком зменшується не більше ніж в два
рази.
4
x
y
x
0
1
x
3
x
5
x
2
x
Рис. 3.1. Метод половинного ділення
Роман Квєтний Методи комп’ютерних обчислень
34
3.1.2. Метод хибного положення (хорд)
Визначаються значення функції в точках, що розташовані на осі
через рівні інтервали. Це робиться поки кінці інтервалів
n,n
xx
1−
не будуть
мати різні знаки. Пряма, що проведена через ці дві точки, перетинає вісь у
точці
.
)()(
)(
1
1
1
−
−
+
−
−
−=
nn
nn
nnn
xfxf
xx
xfxx
Рис. 3.2. Алгоритм методу половинного ділення
НІ
НІ
ТАК
()
()
cpn
cpn
xfxf
xx
=
=
ТАК
ПОЧАТОК
КІНЕЦЬ
Обчислення функції до зміни знаку при
переході від
()
n
xf
до
()
1+n
xf
Обчислення
cp
x
та
(
)
cp
xf
(
)
(
)
0>
ncp
xfxf
ε
≤
−
+ nn
xx
1
()
()
cpn
cpn
xfxf
xx
=
=
+
+
1
1
Після цього визначають )(
1+n
xf і порівнюють його з
)(
n
xf
. Надалі
користуються
1+n
x
замість того значення, з яким воно збіглося за знаком.
Якщо
ε
≤−
+ nn
xx
1
, то вся процедура повторюється спочатку (рисунок 3.3).
Алгоритм методу хорд подібний до попереднього за винятком
процедури оцінки
.x
n 1+
Нелінійні задачі
35
Треба також враховувати, що в алгоритмі обчислень за цим методом
контроль похибки ведеться за тим кінцем інтервалу, що рухається. В
випадку, що показаний на рисунку 3.3. аналізуються послідовні
наближення: на першому кроці
ε
≤
−
21
xx , на другому –
ε
≤−
31
xx , на
третьому –
ε≤−
43
xx і т. д.
Похибка розв’язку оцінюється за формулою:
,xx
M
mM
nn
−
−
≤∆
+1
1
11
де
11
m,M – відповідно, найбільше та найменше значення модуля першої
похідної на відрізку.
y
x
0
1
x
3
x
2
x
4
x
Рис. 3.3. Метод хо
р
д
3.1.3. Метод Ньютона (дотичних)
В методі Ньютона здійснюється екстраполяція за допомогою
дотичної до кривої в даній точці (рисунок 3.4)
(
)
()
.
1
n
n
nn
xf
xf
xx
′
−=
+
В основі цього методу лежить розкладання функції в ряд Тейлора
(
)
(
)
(
)
(
)
...,
''
2
'
2
+++=+
n
h
nnn
xfxhfxfhxf
Роман Квєтний Методи комп’ютерних обчислень
36
Члени, що містять
h у другому і більших степенях, відкидаються і в
результаті отримується наведена вище наближена формула для оцінки
1+n
x .
Швидкість збіжності цього алгоритму значною мірою залежить від
вірного вибору початкової точки. Коли в процесі обчислень кут нахилу
дотичної
()
xf
′
перетворюється на нуль, застосування цього методу
ускладнюється. Можна також показати, що у випадку дуже великих
значень
()
xf
′′
(опуклість функції) чи кратних коренів метод Ньютона стає
неефективним.
Початкове наближення слід вибирати з умови
(
)()
(
)
(
)
.xfxfxf 0
00
2
0
>
′′
>
′
Похибка методу оцінюється як:
()
,
2
2
1
1
2
nn
xx
m
M
−≤∆
+
де
2
M – найбільше за модулем значення другої похідної на інтервалі
[]
1+nn
x,x .
3
x
y
x
0
1
x
2
x
Рис. 3.4. Метод Ньютона
3.1.4. Метод січних
Однією з головних проблем при застосуванні методу Ньютона є
необхідність аналітичного опису похідної. Якщо це складно чи неможливо,
то можна застосувати її наближену оцінку (рисунок 3.5.) Тоді замість
методу дотичних застосовується метод січних, за яким
Нелінійні задачі
37
(
)
()
,
xF
xf
xx
n
n
nn
′
−=
+1
де
()
n
xF
′
– наближена оцінка похідної, що розглядається як січна, а не як
дотична, і може бути оцінена за формулою
()
(
)
(
)
1
1
−
−
−
−
=
′
nn
nn
n
xx
xfxf
xF
чи
()
(
)
(
)
,
h
xfhxf
xF
nn
n
−
+
=
′
де
h – деякий невеликий крок.
Алгоритм цього методу подібний методу Ньютона, але з іншою
ітераційною формулою.
n
x
1+n
x
y
x
0
1−n
x
Рис. 3.5. Метод січних
3.1.5. Метод простої ітерації
Для застосування цього методу рівняння
(
)
xf = 0 перетворюється до
вигляду
(
)
xgx
=
.
Відповідна ітераційна формула має вигляд
(
)
nn
xgx
=
+1
.
Обчислення закінчується, коли
Роман Квєтний Методи комп’ютерних обчислень
38
.xx
nn
ε
≤
−
+1
Для забезпечення збіжності повинна виконуватися умова про те, що
максимальне за модулем значення q першої похідної функції
()
xg на
відрізку
[]
10
x,x повинно бути менше одиниці
.q 1
<
Тоді процес буде збіжний незалежно від вибору початкової точки в
інтервалі
[]
.x,xx
10
∈
Похибка методу на n – ій ітерації
01
1
xx
q
q
n
−
−
≤∆ .
3.1.6. Визначення комплексних коренів
Для визначення комплексних коренів можна застосовувати ті ж самі
методи, що й для дійсних коренів, але при цьому оперують вже
арифметикою комплексних чисел (контроль збіжності та похибки ведеться
за модулем комплексного числа), що не завжди зручно для користувача.
Існує низка спеціальних методів, що дозволяють оцінювати
комплексні корені, проводячи обчислення з дійсними числами. Більшість з
цих методів базується на перетворенні початкового алгебраїчного рівняння
(3.1) до добутку квадратичних співмножників типу
qpxx ++
2
,
де
q,
p
– коефіцієнти.
Проміжною формою для здійснення такого перетворення є рівняння
у вигляді
(
)
(
)
0
0123
3
1
22
=++++++⋅++
−
−
−
bxbbxb...xbxqpxx
n
n
n
, (3.2)
де
01
bxb + – лінійний залишковий член, який прагнуть звести до нуля, і
щоб початкове рівняння (3.1) ділилося на квадратичний співмножник
qpxx ++
2
без залишку.
Для того, щоб знайти коефіцієнти
2321
bb...,bb
,,n,n −−
при припущенні
,bb 0
01
== розглянемо систему рівнянь, що виходять з еквівалентності
рівнянь (3.1) та (3.2):
Нелінійні задачі
39
.qba
,qbpba
,qppbab
,qbpbab
,qbpbab
,qpbab
,pab
jnjnjnjn
nnn
nn
20
321
4322
5433
21
122
11
0
0
−=
−−=
−−=
−−=
−−=
−−=
−
=
−+−+−−
−−−
−−
M
(3.3)
Вона може бути розв’язана методом прогонки (2.11) чи ітераційним
методом Ліна, алгоритм якого представлений на рисунку 3.6.
3.2. Розв’язання систем нелінійних рівнянь
В загальному випадку система з n нелінійних рівнянь з n невідомими
подається у вигляді:
(
)
()
()
.x,...,x,xf
,x,...,x,xf
,x,...,x,xf
nn
n
n
0
0
0
21
212
211
=
=
=
M
(3.4)
Оскільки нелінійні функції, що входять до системи, неможливо
описати якоюсь визначеною загальною формою, то не може бути
запропоновано будь-якого аналітичного прямого методу для розв’язання
такої системи. З наближених ітераційних методів найбільш простим є
метод простої ітерації, що базується на приведенні системи (3.4) до
системи нелінійних рівнянь у вигляді:
(
)
()
()
.x,...,x,xgx
..............................
,x,...,x,xgx
,x...,xxgx
nnn
n
n,,
21
2122
2111
=
=
=
.
В матричному вигляді
(
)
XGX
=
,
Роман Квєтний Методи комп’ютерних обчислень
40
НІ
ПОЧАТОК
Вибір початкових значень
p
та
q
Обчислення
2321
bbbb
,,...,n,n −−
з системи
(3.3) без двох останніх рівнянь
Обчислення нових значень
*
p
та
*
q
з двох останніх
р
івнянь системи (3.3) при вже
обчислених
32
b,b
ТАК
КІНЕЦЬ
ε
ε
≤−
≤−
*
*
,
qq
pp
*
*
qq
pp
=
=
Рис. 3.6. Алгоритм методу Ліна
де
()
(
)
()
()
.
x,...,x,xg
.......................
,x,...,x,xg
,x,...,x,xg
xG
nn
n
n
=
21
212
211
Далі може бути застосований алгоритм, аналогічний методу Гаусса-
Зейделя для систем лінійних рівнянь. В його основі ітераційні рівняння, що
пов’язують
()
1+m та m ітерації