Итерационный метод решения нелинейных уравнений

Пусть требуется решить уравнение

x = g (x),(3.3)

где правая часть уравнения – непрерывная на отрезке функция g (x).

Суть метода итераций (метода последовательных приближений)состоит в следующем.

Начиная с произвольной точки x⁰,принадлежащей отрезку [a,b], последовательно получаем:

x ⁽¹⁾ = g (x ⁽⁰⁾)( первое приближение );

x ⁽²⁾ = g (x ⁽¹⁾)( второе приближение );

… … …

x ^{(k + 1)} = g (x ^(k))( k + 1-е приближение ).

Последовательность

x ⁽⁰⁾, x ⁽¹⁾, … , x ^(k), …

называется последовательностью итераций для уравнения (3.1) с начальной точкой x ⁽⁰⁾.

Если все точки (3.2) принадлежат отрезку [a,b] и существует предел

, то , перейдя к пределу в равенстве

x ^{( k + 1)} = g ( x ^{(k )}) (k = 0,1,2,...) , (3.4)

получим , то есть .

Следовательно, если существует предел последовательности итераций (3.3) , то он является корнем уравнения (3.1). Достаточные условия сходимости последовательности итераций содержатся в следующей теореме.

Теорема:

Пусть функция g(x) имеет на отрезке [a, b]непрерывную производную и выполнены два условия:

1) при x [a , b] ;

2) значения функции y = g(x)принадлежат отрезку [a,b]для любого x [a,b].

Тогда при любом выборе начального приближения x⁽⁰⁾ [a,b]процесс итераций сходится к единственному корню уравнения (3.1) на отрезке [a,b].

Оценка погрешности k -го приближения x ^(k) к корню вычисляется по формуле:

,

где

Укажем теперь один из способов преобразования уравнения f(x)=0 к виду x=g(x), допускающему применение метода итераций, сходящихся к решению уравнения (3.4).

Для любого числа уравнение (3.5) равносильно уравнению (3.3), где

g (x)= x + f( x ). (3.5)

Предположим , что производная f ^' (x) > 0и непрерывна на [ a, b] .

Пусть , ;

положим

,

и рассмотрим функцию

. (3.6)

Для функции, определенной формулой (3.6), выполняются достаточные условия сходимости метода итераций решения уравнения (3.5). В частности, первое условие теоремы следует из неравенств:

0 < m f ^' (x) M ;

0 g ^' (x) = 1 - (1/M) f ^' (x) 1 - m/M = g < 1 .

Замечание 1.Если окажется, что производная f ^'(x)отрицательна на отрезке [ a , b], то уравнение (3.1) можно заменить на равносильное уравнение -f(x) = 0и использовать указанное преобразование.

Замечание 2. Если вычисление точного числа затруднительно, то можно заменить его произвольным числом М₁> M. Однако при большем М₁ , число q = 1 - m / М₁ ближе к единице и процесс итераций сходится медленнее.

Замечание 3. При нахождении корня уравнения (3.1) с заданной точностью или при оценке погрешности k-го приближения можно, не вычисляя точного значения числа q = max | g ^' (x) |, ограничиться следующей практической рекомендацией:

при 0 < q (1/2) при (1/2) < q < 1.

Блок-схема алгоритма, реализующего итерационный метод

Рис 3.3

Блок-схема алгоритма, реализующего метод половинного деления приве-дена на рис. 3.3.

Лабораторная работа 4. Решение не линейных уравнений

Работа выполняется с использованием палитры программирования системы автоматизации математических вычислений Mathcad.

Задания:

1. Разработать программы нахождения корней нелинейного уравнения методом половинного деления и методом итераций.

2. Найти корень заданной функции с требуемой точностью (eps=0,000 1).

3. Сравнить количество итераций, требуемых для нахождения решения с заданной точностью тех и других методов.

4. Задать линейную функцию, имеющую корень на том же интервале [a,b], и решить данное линейное уравнение. Сравнить число итераций в одном и другом методе. Объяснить полученные результаты.

Варианты задании.

1) x ⁴ - 3x -20 = 0 ( x > 0 ); 2) x ³ - 2x - 5 = 0 ( x > 0 );

3) x ³ + 3x + 5 = 0; 4) x ⁴ + 5x -7 = 0 ( x > 0 );

5) x ³ - 12x - 5 = 0 ( x > 0 ); 6) x ³ - 2x ² - 4x + 5 = 0 ( x < 0 );

7) x + e ^x = 0; 8) x ⁵ - x - 2 = 0;

9) x ³ - 10x + 5 = 0 ( x < 0 ); 10) 2 - lnx - x = 0;

11) x ³ + 2x - 7 = 0; 12) x ³ + x ² - 11 = 0 ( x > 0 );

13) x ⁴ -2x - 4 = 0 ( x > 0 ); 14) 2e ^x + x - 1 = 0;

15) x ⁴ - 2x - 4 = 0 ( x < 0 ); 16) 2x ³ + x ² - 4 = 0 ( x > 0 );

17) e ^x - x - 2 = 0; 18) (1/2) e ^x - x - 1 = 0 ( x > 0 );

19) x ² - cos x = 0 ( x > 0 ); 20) x ² + lnx = 0;

Требования к оформлению отчета:

1) название и цель работы;

2) тексты программ;

3) результаты, полученные в процессе выполнения работы;

4) выводы.

Вспомогательные материалы

Для разработки программ на Mathcadе можно использовать приемы, описанные в лабораторных работах 1 и 2.

Существует бесчисленное множество линейных функций, имеющих корень на интервале [a,b]. Поясним это на примере.

Пусть a=2,b=7. Пусть корень уравнения равен 5. Тогда функция

F(x) = k1+k2*x, имеющая корень, равный пяти, может иметь следующий вид:

F(x)=10–2*x(один из коэффициентов задается произвольно, другой находится из уравнения F(x) = 0).

Контрольные вопросы:

1. Зачем нужна процедура отделения корней уравнения?

2. Что называется корнем уравнения?

3. Какова точность метода половинного деления?

4. Каким образом исходное уравнение преобразуется к виду, удобному для итераций?

5. Чему равна оценка погрешности k -го приближения?

ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ

Постановка задачи интерполирования. На отрезке заданы n+1 точки , которые называются узлами интерполяции, и значение некоторой функции в этих точках

. (4.1)

Требуется построить интерполирующую функцию F(x), принадлежащую известному классу и принимающую в узлах интерполяции те же значения, что и :

(4.2)

Рис. 4.1. Интерполирование функции y = f(x)