Метод простой итерации. Пусть [a, b]- отрезок, содержащий корень уравнения f(x)=0 (1)

Пусть [a, b]- отрезок, содержащий корень уравнения f(x)=0 (1). Заменим уравнение (1) равносильным ему уравнением: x=φ (x) (2) на [a, b].

Построим итерационную последовательность {x_n} с помощью формулы x_n+1=φ (x_n), n=0, 1, 2, … x₀- грубое приближение к корню x_c, x_{0 .} Последовательность x₀, x₁, …, x_n, … может сходиться, так и расходиться. Если последовательность сходиться, а функция φ (x) непрерывна, то предел последовательности {x_n} является корнем уравнения (1).

Теорема 4. Пусть

1. φ (x) определена и дифференцируема на [a, b];

2. φ (x)Î [a, b];

3. что

Тогда

1. x_n+1=φ (x_n), n=0, 1, 2, , где x_c- корень уравнения (2), и причем единственный.

2. ;

3. .

Доказательство. Построим интеграционную последовательность {x_n} с любым начальным значением x₀є [a, b]. В силу условия (2) теоремы все члены последовательности находятся в отрезке [a, b].

Рассмотрим два последовательных приближения x_n=φ (x_n-1) и x_n+1= φ (x_n). По теореме Лагранжа о конечных приращениях

x_n+1-x_n=φ (x_n)-φ (x_n-1)=φ ^’(c) (x_n- x_n-1), c є[x_n-1; x_n]

Перейдя к модулям и принимая во внимание условие (3) теоремы, получим: | x_n+1-x_n|= | φ ^’(c)| | x_n- x_n-1|≤ q| x_n- x_n-1|, т.е. | x_n+1-x_n|≤ q| x_n- x_n-1|. При n=1, 2, … будем иметь: | x₂-x₁|≤ q| x₁- x₀|, | x₃-x₂|≤ q | x₂- x₁|≤ q²| x₁- x₀|, … | x_n+1-x_n|≤ qⁿ | x₁- x₀|.

Рассмотрим ряд: x₀+(x₁-x₀)+(x₂-x₁)+…+(x_n-x_n-1)+… (*).

Сразу заметим, что S_n+1=x_n. Члены ряда (*), начиная со второго, не превосходят по модулю соответствующих членов ряда:

|x₁-x₀|+q|x₁-x₀|+q²|x₁-x₀|+…+qⁿ|x₁-x₀|+… (**)

Но ряд (**) сходится как геометрическая прогрессия со знаменателем q< 1, следовательно, ряд (*) абсолютно сходится по теореме сравнения. Поэтому,

Покажем, что x_c- корень уравнения x=φ (x). Имеем: x_n+1=φ (x_n), n=0, 1, 2,.. Т.к. φ - дифференцируема, то она непрерывна на[a, b], следовательно, можно перейти к пределу: x_c=φ (x_c0), т.е. x_c- корень уравнения (2). Допустим, что и

|x_c- |=| |

Получим противоречие, следовательно,

Оценим погрешность: |x_n-x_c|=|φ (x_n-1)-φ (x_c)|≤ q| x_n-1- x_c|≤ qⁿ|x₀-x_c|≤ qⁿ|b-a|

|x_n-1-x_c|=|(x_n-1-x_n)+(x_n-x_c)|≤ | x_n-1-x_n|+ |x_n-x_c|≤ | x_n-1-x_n|+q| x_n-1-x_c|

| x_n-1-x_c|≤ . С другой стороны: |x_n-x_c|≤ q|x_n-1-x_c| |x_n-1-x_c|≥

≤ |x_n-1-x_c|≤ , |x_n-x_c|≤

Практически уравнение f(x)=0 может быть приведено к виду x=φ (x) многими способами, однако это следует сделать так, чтобы для функции φ (x) выполнялись условия (1)- (3) теоремы.

На практике часто условие (2) не проверяют, а используют следующую теорему:

Теорема 5. Пусть:

1. [a, b] содержит единственный корень уравнения (2);

2. φ (x) дифференцируема на [a, b];

3. , такое, что |φ ^’(x)|≤ q.

Тогда итерационная последовательность x_n+1=φ (x_n), n=0, 1, 2, … сходится к корню x_c хотя бы для одного из натуральных приближений x₀=a или х₀=b и справедливы оценки погрешности предыдущей теоремы.

Для того, чтобы выполнялось условие (3), в некоторых случаях помимо обычных преобразованиях (f(x)=0 x=x+f(x)) полезно иметь в виду следующие специальные приемы:

1 Уравнение f(x)=0 преобразуем к виду: х=x-mf(x), г де m=const, m≠ 0. В этом случае φ (x)=x-mf(x) и φ ^’(x)=1-mf^’(x). Для того чтобы |φ ^’(x)|=|1-mf^’(x)|≤ q< 1, достаточно подобрать m так (если, конечно, это возможно), чтобы для всех x из отрезка [a, b] значением выражения mf^’(x) была положительная правильная дробь.

2 Пусть уравнение f(x)=0 записано в виде x=φ (x). Однако при исследовании функции φ (x) на [a, b], оказалось, что x [a, b] |φ ^’(x)|> 1. Тогда вместо функции y= φ (x) рассмотрим функцию x=g(у), обратную для φ (x). Будем теперь решать уравнение y=g(у) (или, в старых обозначениях, x=g(x)). По свойству производных обратных функций теперь на [a, b] будет иметь место: |g^’(x)|= . Так что для уравнения x=g(x), равносильного искомому условие (3) теоремы оказалось выполненным.