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

Пусть требуется решить уравнение, представленное в виде

x = g (x), (5)

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

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

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

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

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

… … …

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

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

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

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

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

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

 

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

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

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

 

Теорема.

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

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

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

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

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

, (8)

где

Укажем теперь один из способов преобразования уравнения

f(x) = 0 (9)

к виду x = g(x), допускающему применение метода итераций, сходящихся к решению уравнения (9).

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

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

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

на [ a,b ]. Пусть , ;

положим

,

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

. (10)

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

0 < m f ^' (x) M,

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

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

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

Замечание 3. При нахождении корня уравнения (1) с заданной точностью или при оценке погрешности k-го приближения можно, не вычисляя точного значения числа

q = max | g ^' (x) |,ограничиться следующей практической рекомендацией:

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

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

Блок – схема алгоритма, реализующего итерационный метод, приведена на рис. 3.2.

 

 

>

<

<

b = x1

d = b - a

a = x1

0

x1 = (a + b ) / 2

 

 

 

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

 

Лабораторная работа 4

Решение нелинейных уравнений

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

 

Задание на работу:

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

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

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

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

Отчет по лабораторной работе должен содержать:

- название работы

- цель работы

- тексты программ

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

- выводы

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

Для разработки программ на 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 -го приближения?

Раздел 4

Интерполирование функций

Краткое введение. Постановка задачи интерполирования.

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

. (1)

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

(2)

 

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

 

В общем случае, задача имеет бесчисленное множество решений.

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

Будем искать полином степени не выше n и удовлетворяющий условию (2).

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

Если - имеет место задача интерполирования (интерполирование “в узком смысле”).

При решается задача экстраполирования.