Метод простих iтерацiй

Метод простих iтерацiй заснований на представленні рівняння f(x)=0 в вигляді х=F(x)i багаторазовому використанні iтерацiйної формули Х(n+1)=F(x(n)) до тих пiр, доки виконується умова |x _n+1 – x _n| E, де Е - задана похибка обчислення кореня x. Iтерацiйний процес збiгається (тобто x(n) прямує до розв'язку при n ® ), якщо виконується умова½F´(x)½<1приa<x<b.

Для розв’язування рівняння F(x) = x – SIN(x) - 0.25 = 0програма має вигляд

PROGRAM ITERACIA;

LABEL 1,2;

Uses CRT;

Var X, E:real;

{Ф У Н К Ц I Я}

Function F(X:real):real;

Begin

F:=SIN(X)+0.25;

End;

BEGIN

ClrScr;

WriteLn(Розв'язок рівнняня методом простих ітерацій ');

Writeln;

2:; Write('Введiть Х-початкове ');

Readln(x);

Writeln(Задайте похибку E ');

Readln(E);

F(X);

IF ABS(F-X)<E THEN GOTO 1;

X:=F; GOTO 2;

1:; Writeln('Корінь= ',X'); GOTO 2;

END.

Для розв'язання в ітераційних методах важливим є вибір початкового значення x₀ та виконання умов збіжності ітераційної процедури до точного розв’язку x^k. Iтераційний процес буде збіжним в методі простих ітерацій, якщо| , що графічно можна проілюструвати графіками:

Рис.2.1.а Рис 2.1.б

В першому випадку 0 < y'(x) < 1, тобто тангенс кута нахилу дотичної до осі x менший 45⁰ і такий процес наближення до розв’язку називається одностороннім (Рис.2.1.а). В другому випадку - 1 < y'(x) < 0і процес є двостороннім (Рис.2.1.б).

Якщо ж y´(x) > 1, то процес розходиться при будь-яких початкових x₀ (Рис.2.2.а,2.2.б).

Рис.2.2.а Рис2.2.б

Для двостороннього процесу при y'(x) < -1 процес також розходиться (Рис.2.3).

з

Рис.2.3.

Якщо досліджуване рівняння f(x)=0не містить змінної x в чистому вигляді, наприклад, f(x)=cos(x), то для використання методу простих ітерацій необхідно рівняння переписати в вигляді F(x) = k f(x)+ x = x, деk введемо так, щоб виконувалась умова | f´(x)| < 1. При цьому F´(x) = |kf´(x) + 1| < 1, і, значить,k підбирається таким чином, щоб .

Установимо критерій збіжності математично. Нехай x_k=x^*+e_k; x_k+1=x^*+e_k+1 де x^*- корінь, e-відхилення.

Поблизу кореня функцію можливо представити двома членами ряду Тейлора. Тоді формула x_k+1=F(x_k) запишеться у вигляді x^*+e_k+1 F(x^*)+e_kF´(x^*). Так як x^*=F(x^*), то e_k+1=e_kF´(x^*). Для збіжності необхідно , або F´(x^*)<1.

Якщо k виберемо так, щоб –1<F´(x)<0, то збіжність двостороння і критерій виходу з ітераційної процедури .