Ітераційний метод Ньютона для СНАР

Нехай, керуючись підходами, викладеними в розділі 2, знайдено p -е наближення

одного з ізольованих коренів  векторного рівняння (4.2). Тоді точний корінь можна подати у вигляді

,                       (4.3)

де  - похибка кореня.

Підставимо (4.3) у (4.2):

.                  (4.4)

Нехай  – неперервна диференційована функція в деякій опуклій області, що містить  і , розкладемо ліву частину (4.4) в ряд за степеням малого вектора , обмежившись лінійними членами:

(4.5)

З (4.5) випливає, що під  треба розуміти матрицю Якобі системи функцій f₁, f₂,…,f_n   щодо x₁,x₂,…,x_n

Система (4.5) являє собою систему лінійних рівнянь відносно похибок   (i=1,2,…,n) з матрицею W(x), тому формула (4.5) набере вигляду

_.

Допускаючи, що W(x)– невироджена, знаходимо

,

значить,

.            (4.6)

Отримали інтерполяційну формулу Ньютона для СНАР. Очевидно, формула (4.6) дозволить побудувати збіжну до кореня ітераційну послідовність за умови, що відображення  буде стискаючим. Для цього треба правильно обрати нульове наближення .

Теорема 3. Маємо нелінійну систему рівнянь з дійсними коефіцієнтами (4.2), де вектор-функція визначена і неперервна разом зі своїми частковими похідними 1-го і 2-го порядків в області w. Вважатимемо, що  є точка, яка лежить у w разом зі своїм замкненим -околом. Причому виконані умови:

1) Матриця Якобі при =  має обернену Г₀, де ||Г₀||<=A₀, (в змісті m-норми)

2) ||Г₀f(x⁰)||<=B₀<=H/2

3) <=C при i,j=1,2,…,n

4) постійні A₀, B₀ і C задовольняють нерівність m ₀ =2n₀B₀C<=1

Тоді процес Ньютона (4.6) при початковому наближенні  збігається і граничний вектор

є розв ’ я зком системи таким, що ||x*-x⁰||<=2B₀<=H.

Модифікований метод Ньютона

При побудові процесу Ньютона (4.6) істотною незручністю є необхідність для кожного кроку заново обчислювати обернену матрицю Якобі. Якщо ця матриця неперервна в околі шуканого розв’язку x⁰, досить близького до x^*, то приблизно можна покласти

і ми приходимо до модифікованого методу Ньютона

.

Метод градієнтного спуску

Припустимо, що в системі нелінійних алгебраїчних рівнянь (4.2) функції f_i дійсні і неперервно диференційовані в їхній загальній області визначення. Розглянемо функцію

 .    (4.7)

Очевидно, що кожен розв’язок системи (4.2) перетворює в нуль функцію U(x); і навпаки, числа x₁,x₂,...,x_n, для яких функція U(x) дорівнює нулю, є коренем системи (4.2).

Припустимо, що система має лише ізольований розв’язок, що являє собою точку строгого мінімуму функції U(x) у n -вимірному просторі ={x₁,x₂,..., x_n }.

Нехай  - корінь системи (4.2) і - його нульове наближення. Через точку   проведемо поверхню рівня функції U(). Якщо точка   досить близька до кореня , то при наших припущеннях поверхня рівня U()=U( ) буде схожа на еліпсоїд.

З точки   рухаємося по нормалі до поверхні U()=U( ) доти, поки ця нормаль не доторкнеться в деякій точці  іншої поверхні рівня U()= U( ).

Потім, відправляючись від точки , знову рухаємося по нормалі до поверхні рівня U()= U( ) доти, поки ця нормаль не доторкнеться в деякій точці  нової поверхні рівня U()= U( ), і т.д.

Оскільки U( )>U( )>U( )>..., то, рухаючись таким чином, ми швидко наближаємося до точки з найменшим значенням U ("дно ями"), що відповідає кореневі системи (4.2). Позначимо через

градієнт функції U(). Визначимо описаний алгоритм пошуку точок-наближень за формулою

 .          (4.8)

Залишається визначити множники l _p. Для цього розглянемо скалярну функцію .

Функція F (l) дає зміну рівня функції U уздовж відповідної нормалі до поверхні рівня в точці . Множник l = l _p потрібно вибрати таким, щоб F (l) мала мінімум. Керуючись необхідною умовою екстремуму функції, одержуємо рівняння

. (4.9)

Найменший додатний корінь цього рівняння і дасть нам значення l _p.  Будемо вважати, що l - мала величина, квадратом і вищими ступенями якої можна зневажити. Маємо . Розкладаючи функції f_i за степенями l з точністю до лінійних членів, одержимо

,

де . Звідси

Отже, ,

де - матриця Якобі. Далі маємо

.

Звідси ,

де W`(x) - транспонована матриця Якобі. Тому остаточно , а . Отримали розрахункову формулу методу градієнтного спуску з визначенням кроку.

Сучасна комп’ютерна техніка дозволяє суттєво спростити цей метод розв’язання нелінійних систем. Множник l _p у формулі (4.8) обирають як достатньо малий постійний крок у напрямку антиградієнта. Наприклад, l _p =0.00001.

Приклад. Розв’язати систему нелінійних рівнянь з точністю e=0,0001

Скористаємося методом градієнтного спуску. Для цього побудуємо функцію , де , а .

Кожен розв’язок системи - це нуль функції  і навпаки. Виберемо початкове наближення . Позначимо  Пошук розв’язку проводимо за формулою

.

Множник l(p) визначається так: , де:

.

Тоді процес здійснюється за формулою

;

W – матрица Якобі: .

Пошук наближень до розв’язку припиняється за умови .

Реалізація алгоритму на псевдокоді:

VectorF(F,x):

//розраховуємо коефіцієнти вектора F при x

end

VectorW(W,x):

//розраховуємо коефіціенти матриці W при x

end

//W – матриця Якобі

//F – матриця системи

//Z – результат множення

multWF(W,F,Z): // множення W на F

15 for i:=1 to W.lengthI do

16 for j:=1 to W.lengthJ do

17 Z[i]+=W[i,j]*F[j]

18 done

19 done

End

//A – вихідна матриця

//X – транспонована матриця

Transpon(A,X):

1 for i:=1 to A.lengthI do

2 for j:=1 to A.lengthJ do

3 if i=j then

4 X[i,j]:=A[i,j]

5 else

6 X[i,j]:=A[j,i]

7 fi

8 done

9 done

End

Scalar(A,B): //скалярний добуток векторів a та b

1 s:=0

2 for i:=1 to A.length do

3 s+=A[i]*B[i]

4 done

5 return s

end

// розв’язання нелінійної системи методом градієнтного спуску

Solve_NonLinear_System(F,W,X):

1 n:=A.lengthI

2 for i:=1 to n do

3 X[i]:=-1;

Done

5 k:=0

Repeat

7 k++

8 for i:=1 to n do

9 XK[i]:=X[i]

Done

11 Vectorf(F,xk)

12 MatrixW(W,xk)

13 MultWF(wt,f,u)

14 MultWF(w,u,z)

15 mu:=(scalar(f,z))/(scalar(z,z))

16 maxr:=0

17 for i:=1 to n do

18 X[i]:=XK[i]-mu*U[i]

19 if abs(X[i]-XK[i])>maxr then

20 maxr:=abs(X[i]-XK[i])

Fi

22 until maxr<eps

Done

end.

Відповідь: X=0.50, Y=1.00, Z=1.00.

 

Метод релаксацій

 

Перепишемо систему (4.1) у вигляді

= + ,

де - деяка константа, і побудуємо ітераційний процес за схемою

^(k+1) = ^(k) + .

Параметр  повинен бути таким, щоб в околі pозв’язку виконувалася достатня умова збіжності

|| Е + W || < 1,

де E - одинична матриця, а W – матриця Якобі. На практиці виконання цієї умови досить складно перевірити, тому значення параметра  вибирають пробним шляхом, перевіряючи виконання необхідної умови збіжності після здійснення кожної ітерації

|| ^(k)- ^(k-1)||<|| ^(k-1)- ^(k-2)||.

Якщо виявиться, що на якій-небудь ітерації ця умова не виконується, то необхідно змінити значення параметра .

Приклад. Знайти з точністю всі корені системи нелінійних рівнянь

використовуючи метод Ньютона для системи нелінійних рівнянь. Знайти корінь за допомогою убудованого блоку розв’язку рівнянь Given Find пакета MATHCAD. Рівняння системи:

.

Локалізація кореня

Перше рівняння, визначене відносно x2: . Друге рівняння, визначене відносно x2: .

Маємо .

Перший корінь

Початкове наближення: .

Точність для блоку Given Find: TOL:= .

Розв’язання системи f(x1,x2)=0 за допомогою убудованого блоку MATHCAD:

Given

  0

0

Find(

Отриманий наближений розв’язок .

Питання і завдання до розділу 4

 

1 Постановка задачі розв’язання системи нелінійних рівнянь. Основні етапи розв’язування задачі.

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

3 Метод Ньютона: опис методу, теорема про збіжність, критерій закінчення.

4 Недоліки методу Ньютона. Модифікації методу Ньютона.

5 Застосування методів розв’язання систем нелінійних рівнянь для задачі мінімізації функцій.

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

a)    , ;

b)  , .

7 Чи можна стверджувати, що система має, й до того ж єдиний, розв’язок?

8 Для системи рівнянь виписати розрахункові формули методу релаксацій:

9 Розв’язати методом простої ітерації такі системи:

a)  , ;

b)     , .

10 Для функції  знайти точки мінімуму, звівши задачу до розв’язання системи рівнянь.

Розділ 5

Апроксимація функцій

Апроксимація (від лат. approximo - наближаюся) - заміна одних математичних об'єктів іншими, якомось чином близькими до вихідних. Апроксимація дозволяє досліджувати числові характеристики і якісні властивості об'єкта, зводячи задачу до вивчення більш простих або більш зручних об'єктів (наприклад таких, характеристики яких легко обчислюються або властивості яких уже відомі). У теорії чисел вивчаються діофантові наближення, зокрема наближення ірраціональних чисел раціональними. У геометрії і топології розглядаються апроксимації кривих, поверхонь, просторів і відображень. Деякі розділи математики цілком присвячені апроксимації, наприклад наближення функцій.