ЛР_ОТП_M03434
.pdf41
ЛАБОРАТОРНА РОБОТА № 5
РІШЕННЯ НЕЛІНІЙНИХ РІВНЯНЬ МЕТОДАМИ НЬЮТОНА ТА ПРОСТИХ ИТЕРАЦІЙ
5.1Мета роботи.
Вивчення чисельних методів рішення нелінійних рівнянь та придбання практичних навиків роботи в системі MatLab.
5.2Завдання до лабораторної роботи
Для виконання лабораторної роботи необхідно.
1.Вивчити алгоритми ітераційних методів(Ньютона та Про-
стих ітерацій).
2.Скласти програми-функції для знаходження коренів будьякого нелінійного рівняння методами Ньютона та Простих ітерацій з заданою точністю.
3.Виконати в MatLab індивідуальні завдання наведені в роз-
ділі 5.4.
4.Зберегти результати роботи (програми, протоколи обчислень, графіки) в відповідних файлах.
5.Скласти звіт.
5.3Основні теоретичні відомості
Метод Ньютона (метод дотичних). Розрахункова формула ме-
тоду Ньютона має :
x(n+1) = x(n) − f (x(n) ) f ' (x(n) ) .
Геометрично метод Ньютона означає, що наступне наближення
до кореня x(n+1) є точка пересічення з віссю ОХ дотичної, що проведена до графіка функції y=f(x) в точці (x(n) , f (x(n) )).
PDF created with pdfFactory Pro trial version www.pdffactory.com
42
Рисунок 5.1 – Метод Ньютона
Ефективність методу залежить від початкового наближення x0. Наприклад, воно може збігатися з одним із кінців інтервалу ізоляції кореня [a, b], для якого виконується умова f (x) * f ′′(x) > 0 . На прак-
тиці ж вибір значення x0 набагато складніший. Умови збіжності методу Ньютона, можна визначити у такий спосіб:
-функція f(x) має бути принаймі двічі диференційована на інтервалі [a, b];
-перша похідна функції не повинна перетворюватися на нуль f ′(x) ¹ 0 ;
-виконується умова f (x) * f ′′(x) < f ′(x)2 на інтервалі [a, b].
Таким чином, збіжність обчислень методу гарантується лише для монотонних і обмежених за крутістю функцій.
Критерій закінчення ітераційного процесу. При заданій точності ε >0 обчислення слід вести до тих пір, поки не виявиться виконаним
неравенство x(n) − x(n−1) < ε або |f(x (n))|<ε.
Програма, що реалізовує метод Ньютона, наведена в лістингу
5.1.
Лістинг 5.1. Файл newton.m. function [x,k]=newton(fname,fname1,x0,eps)
%корінь методом Ньютона,
%повертає корінь і кількість ітерацій.
%fname - ім'я функції, fname1 – похідна,
%х0 – початкове наближення до кореня,
PDF created with pdfFactory Pro trial version www.pdffactory.com
43
% eps – точність. k=0;
f=feval(fname,x0); f1= feval(fname1,x0); x1=x0-f/f1;
while abs(x0-x1)>eps & k < 100 x0=x1; f=feval(fname,x0);
f1= feval(fname1,x0); x1=x0-f/f1;
k=k+1;
end;
x=x1;
Приклад 5.1. Вирішити рівняння f(x)=0, де
f (x) = 3x4 + 4x3 − 12x2 − 5
методами Ньютона и розподілу навпіл. Порівняти методи за швидкістю збіжності і обчислень.
1.Створимо функцію f(x), ім'я функції var1 function y=var1(x) y=3*x.^4+4*x.^3-12*x.^2-5;
2.Її похідна
function y=var11(x) y=12*x^3+12*x^2-24*x;
3.Программа-сценарій (файл test.m)для порівняння швидкості збіжності методів Ньютона і розподілу навпіл:
x1=zeros(1,6); k1=zeros(1,6); x2=zeros(1,6); k2=zeros(1,6); eps=[0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001];
for i=1:6 [x1(i),k1(i)]=bisec(@var1,-3,-2,eps(i));
[x2(i),k2(i)]=newton(@var1,@var11,-2.5,eps(i)); end;
disp x1,x2 plot(log(1./eps),k1,'k-.',log(1./eps),k2,'k:') grid on
PDF created with pdfFactory Pro trial version www.pdffactory.com
44
Результат роботи скрипта test.m наведений на малюнку 5.2. По осі 0Х відкладені натуральні логарифми від зворотної величини точності (із зростанням точності зростає і аргумент по осі 0Х). По осі 0Y
– число ітерацій, необхідне для обчислення кореня із заданою точністю.
Видно, що із зростанням точності метод Ньютона вимагає значно менше ітерацій, правда, на кожній ітерації значення функції і значення похідної, тоді як в методі розподілу навпіл на кожній ітерації обчислюється лише одне значення функції.
Як вказано вище, метод Ньютона володіє локальною збіжністю, тобто областю його збіжності є мала околиця кореня. Невдалий вибір може дати ітераційну послідовність, що розходиться.
Рисунок 5.2 – Залежність кількості ітерацій від точності для методів розподілу навпіл (верхня лінія) і методу Ньютона (нижня лінія)
Приклад 5.2. Чутливість методу Ньютона до вибору початкового наближення.
1. Лістинг функції – файл f24.m function y=f24(x) y=(x-1.3)./((x-1.3).^2+1);
PDF created with pdfFactory Pro trial version www.pdffactory.com
45
2.Лістинг похідної функції – файл f241.m function y=f241(x) y=(1-(x-1.3).^2)./((x-1.3).^2+1).^2;
3.Лістинг скрипта – файл test1.m
%Програма тестування методу Ньютона на чутливість
%до вибору початкового наближення
[root1, iter1] = newton('f24','f241', 1.87,1e-8); % Перевіримо корені
y=f24(root1)
[root2, iter2] = newton('f24','f241', 1.88,1e-8); y1=f24(root2)
% Порівняємо кількість ітерацій iter1
iter2
4.Протокол запуску програми і результати її работи:
>>test1
y = 0
y1 =4.1016e-030 iter1 = 7
iter2 = 100
Бачимо, що число ітерацій в першому випадку набагато менше, ніж в другому.
Метод простої ітерації (метод послідовних повторень)
Для |
методу простої ітерації потрібно початкове рівняння |
f (x) = 0 |
перетворити до виду, зручному для ітерацій x = ϕ(x) . Це |
перетворення можна виконати різними способами. Функція ϕ(x) називається ітераційною функцією. Розрахункова формула методу простої ітерації має x(n+1) = ϕ(x(n) ) .
Теорема про збіжність методу простої ітерації.
Хай рівняння x = ϕ(x) має єдиний корінь на відрізку [a, b] і виконані умови:
1.φ(x) визначена і диференційована на [a, b];
2.Існує таке дійсне q, що ϕ ' (x) ≤ q <1 для всіх x€[a, b].
PDF created with pdfFactory Pro trial version www.pdffactory.com
46
Тоді ітераційна послідовність x(n+1) = ϕ(x(n) ) (n = 1, 2, ) сходиться
при будь-якому початковому наближенні x0 € [a, b].
Критерій закінчення ітераційного процесу. При заданій точності ε >0 обчислення слід вести до тих пір, поки не виявиться виконаною
нерівність x(n) − x(n−1) < ε , (n = 1, 2, ).
Приклад 5.3. Знайти методом простих ітерацій розв’язок рів-
няння
x4 - 11x3 + x2 +x +0.1 = 0
а також точність досягнуту за 10 ітерацій.
1.Лістинг програми-функції, що обчислює точність досягнуту за к ітерацій при розв’язуванні рівнянь методом простих ітерацій:
Function [x,eps]=Iter(fi,fi1,x0,k)
%fi – ім'я функції;
%fi1 – похідна функції;
%x0 – початкове наближення;
%k – кількість ітерацій;
%x – корінь;
%eps – точність.
2.Задамо початкову функцію f(x)= x4 - 11x3 + x2 +x +0.1, функцію φ(x)= -x4 + 11x3 - x2 -0.1 и її першу похідну використовуючи ко-
манду inline:
>>f=inline(‘x.^4-11*x.^3+x.^2+x+0.1’); >>fi=inline(‘-x.^4+11*x.^3-x.^2-0.1’); >>fi1=inline(‘-4*x.^3+33*x.^2-2*x’);
3.Для коренів нелінійного рівняння використовуємо графічний метод:
>>x1= -1; >>x2=1; >>dx=10^-3; >>x=x1:dx:x2;
>>plot(x,f(x)); grid on
4.Виберемо інтервал локалізації – [-1,1] і за 10 ітерацій:
>>[x,eps]=Iter(‘fi’,’fi1’,-1,10)
x=0.3942 eps=10^-5
PDF created with pdfFactory Pro trial version www.pdffactory.com
47
Індивідуальні завдання до лабораторної роботи
Для заданого нелінійного рівняння (варіанти індивідуальних завдань наведені в другій колонці Додатка А, стор.64):
1.Виконати відокремлення коренів нелінійного рівняння та провести уточнення цих коренів з заданою точністю методами:
а) Ньютона; б) простої ітерації.
2.Порівняти обчислень при розрахунку указаними методами із різними значеннями точності.
3.Разом з "ручним" рішенням представте рішення, що отримуються стандартними засобами MatLab.
5.5Завдання на самостійну роботу
Завдання для підготовки до модульного контролю і самоперевірки приведені в Додатку Б (стор. 65).
5.6Контрольні питання
1.Запишіть розрахункову формулу методу Ньютона і дайте геометричну інтерпретацію методу.
2.Опишіть алгоритм методу простої ітерації і дайте геометричну інтерпретацію методу.
3.Вкажіть достоїнства і недоліки методу простої ітерації в порівнянні з методом Ньютона.
4.Умова збіжності методу Ньютона.
5.Умова збіжності методу простої ітерації.
PDF created with pdfFactory Pro trial version www.pdffactory.com
48
ЛАБОРАТОРНАЯ РАБОТА №6
ТЕМА: РІШЕННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАІЧНИХ РІВНЯНЬ
6.1Мета роботи.
Вивчення чисельних методів рішення систем лінійних алгебраічних рівнянь(СЛАР) та придбання практичних навиків використання системи MatLab.
6.2Завдання до лабораторної роботи
1.Вивчити можливості MatLab по використанню прямих методів рішення СЛАУ.
2.Вивчити алгоритми ітераційних методів - ітерації Якобі та Зейде-
ля.
3.Скласти відповідні програми-функції методів Якобі та Зейделя.
4.Виконати в MatLab індивідуальні завдання наведені в розділі 6.4.
5.Скласти звіт.
6.3Основні теоретичні відомості
Розглянемо систему, що складається з m лінійних алгебраїчних рівнянь алгебри з n невідомими:
ì |
a x + a x |
2 |
+ ×××a |
|
x |
n |
= b , |
|
|||||||||
ï |
|
11 1 |
|
12 |
|
|
1n |
|
|
|
1 |
|
|||||
ï a21 x1 + a22 x2 + ×××a2n xn = b2 , |
(6.1) |
||||||||||||||||
í |
|
|
|
|
|
|
××× |
|
|
|
|
|
|
|
|
|
|
ï |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ïa |
x + a |
m2 |
x |
2 |
+ ×××a |
mn |
x |
n |
= b |
m |
, |
||||||
î |
|
m1 1 |
|
|
|
|
|
|
|
|
|
||||||
яка може бути записана в матричній формі |
|
|
|
|
|
|
|||||||||||
|
|
|
|
A × x = b , |
|
|
|
|
|
|
|
|
(6.2) |
||||
де A – прямокутна матриця розмірності m × n : |
|
|
|
||||||||||||||
|
|
æ a |
|
|
a |
××× |
|
|
|
a |
ö |
|
|
||||
|
|
ç |
11 |
|
|
12 |
|
|
|
|
|
|
1n |
÷ |
|
|
|
|
|
ç a21 |
|
a22 |
××× |
|
|
|
a2n |
÷ |
, |
|
|||||
|
|
A = ç |
××× |
|
|
|
|
|
|
|
|
|
|
÷ |
|
||
|
|
ç |
|
|
|
|
|
|
|
|
|
|
÷ |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
ç |
|
|
am2 |
××× |
|
|
|
|
|
÷ |
|
|
|||
|
|
èam1 |
|
|
|
amn ø |
|
|
PDF created with pdfFactory Pro trial version www.pdffactory.com
49 |
|
|
|
x – вектор n-ого порядку: |
|
|
|
æ x |
ö |
|
|
ç |
1 |
÷ |
|
ç x |
÷ |
|
|
x = ç |
××× |
÷ |
, |
ç |
÷ |
|
|
|
|
||
ç |
|
÷ |
|
è xn |
ø |
|
|
b – вектор порядку m: |
|
|
|
æ b |
ö |
|
|
ç |
1 |
÷ |
|
çb |
÷ |
|
|
b = ç |
××× |
÷. |
|
ç |
÷ |
|
|
|
|
||
çb |
÷ |
|
|
è |
n |
ø |
|
æ b |
ö |
|
|
ç |
1 |
÷ |
|
çb |
÷ |
|
|
b = ç |
××× |
÷. |
|
ç |
÷ |
|
|
|
|
||
çb |
÷ |
|
|
è |
n |
ø |
|
Розв’язком системи називається така впорядкована сукупність чисел x: x1 = c1 , x2 = c2 , ... , xn = cn , що обертає всі рівняння систе-
ми (6.1) у тождества.
Припустимо, що матриця системи A задана і є неособливою, тобто визначник системи D ≠ 0. Відомо, що в цьому випадку вирішення системи існує, єдино і стійко за вхідними даними. На практиці, особливо при обчисленнях на комп'ютерах, коли відбувається округлення або відкидання молодших розрядів чисел, далеко не завжди удається отримати точну рівність визначника нулю. При D ≈ 0 розв’язок системи чутливий до зміни коефіцієнтів системи. Таким чином малі похибки обчислень або даних можуть привести до похибок в рішенні Такі системи рівнянь називаються погано обумовленими.
Методи розв’язання СЛАР діляться на дві групи:
-прямі методи;
-ітераційні методи.
PDF created with pdfFactory Pro trial version www.pdffactory.com
50
Прямі методи і їх реалізація в пакеті MatLab
В прямих (або точних) методах кількість арифметичних дій, потрібних для отримання розв’язку x системи (6.1) є скінченним числом.
Істотним недоліком прямих методів є накопичення похибок в процесі, оскільки обчислення на будь-якому етапі використовують результати попередніх операцій. Це особливо небезпечно для великих систем, коли різко зростає загальне число операцій, а також для погано обумовлених систем, чутливим до похибок.
Метод Гаусса
Розглянемо метод Гаусса розв’язання системи рівнянь. Прямий хід складається з m-1 кроків виключення.
1 Крок. Виключимо |
невідоме |
x1 |
рівнянь з номерами |
|||
j = 2,3,..m. Припустимо, що |
a11 ¹ 0 . Називатимемо його провідним |
|||||
елементом 1-го кроку. |
|
a j1 |
|
|
|
|
μ j1 |
= |
|
|
|||
a11 , j |
= 2,3,Km звані множниками 1- |
|||||
Знайдемо величини |
|
го кроку. Віднімемо послідовно з другого, третього, ...m-го рівнянь
системи перше рівняння, помножене відповідно на μ21, μ31,...,μm1. В результаті 1-го кроку отримаємо еквівалентну систему рівнянь:
Аналогічно проводяться слідуючи кроки. Після (m-1)-го кроку виключення отримаємо систему рівнянь
PDF created with pdfFactory Pro trial version www.pdffactory.com