Конспект лекций междисциплинарного курса МДК.01.04 Математические методы разработки алгоритмов профессионального модуля ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем (стр. 5 )

На практике часто в качестве берут функцию , где с – некоторая постоянная. Постоянную c выбирают таким образом, чтобы для всех x∈[a, b]. При таком выборе функции метод простой итерации называют методом релаксации.

Получим условия выбора с для метода релаксации:

Таким образом, если f/(x) < 0, то 2/f/(x) < c < 0. Если же f/(x) > 0, то 2/f/(x) > c > 0.

Видно, что знак у с совпадает со знаком f/(x). Часто с берут в виде:

.

Пример 2.5.1. Найти  второй корень уравнения x3 – 6x2 + 3x + 11 = 0, который лежит на интервале [1, 3] с точностью .

Решение.

Сначала найдем функцию . В нашем случае f(x) = x3 – 6x2 + 3x + 11.

Для нахождения c необходимо найти максимальное и минимальное значения f/(x) на отрезке [1, 3]. Для этого необходимо найти значения f/(x) на концах интервала и в точках, где f//(x) = 0, т. е. в точках экстремума, если такие точки для рассматриваемого интервала существуют. Затем выбрать среди этих значений f/(x) максимальное и минимальное значения:

f/(1) = 3x2 – 12x + 3 = -6,

f/(3) = -6,

f//(x) = 6x – 12 = 0 при x = 2, ,  f/(2) = -8.

Следовательно,

Таким образом,

.

Вычисления оформим в виде таблицы:

k	x	|xk+1-xk|	|f(xk)|
0	2	-	1
1	2.142857	0.142857	0.282799
2	2.102457	0.0404	0.07896
3	2.113737	0.01128	0.022164
4	2.110571	0.003166	0.006213
5	2.111459	0.000888	0.001742
6	2.11121	0.000249	0.000489

Здесь

x0 = (1+3)/2 = 2,

 

и т. д.

Условием окончания итерационного процесса является условие:

|xk+1 – xk| < е или  |f(xk)| < е.

2.5. Метод Ньютона (метод касательных)

Напомним, что мы решаем уравнение f(x) = 0.

Метод определяется формулой

Геометрическая интерпретация метода такова (рис. 2.3): участок кривой  y = f(x) при , если , или , если , заменяется отрезком касательной, проведённой из точки xk. Уравнение касательной имеет вид:

.

Найдем точку пересечения (которую обозначим как xk+1) касательной с осью  y = 0:

.

Откуда

.

Рис. 2.3. Геометрическая интерпретация метода Ньютона

Можно показать, что |xk+1– x*|  < q ⋅ |xk – x*|2, т. е. метод сходится со вторым порядком (квадратичная сходимость).

Метод Ньютона можно трактовать как метод простой итерации при .

Замечание. Если известен интервал изоляции корня уравнения, в котором f//(x) не меняет знак, то в качестве начального приближения берут тот конец интервала изоляции, для которого знаки f(x) и f//(x) совпадают.

Пример 2.4.1. Найти методом Ньютона третий корень уравнения  x3 – 6x2 + 3x + 11 = 0, который лежит на интервале [4, 5] с точностью .

Решение. Сначала убедимся, что f//(x) не меняет знака на заданном отрезке:

f//(x) = 6x – 12;

f//(x) > 0 при x > 2, т. е. f//(x) > 0 на интервале [4,5]. 

Так как  f(5) = 1 > 0, то x0 = 5.

Вычисления оформим в виде таблицы: 

k	xk	|xk+1-xk|	f(xk)	f/(xk)
0	5	-	1	18
1	4.944444	0.055556	0.027606	17.00926
2	4.942821	0.001623	2.33E-05	16.98059
3	4.94282	1.37E-06	1.66E-11	16.98057

Здесь

f(xk) = xk3 – 6xk2 + 3xk + 11,

f/(xk) = 3xk – 12xk + 3,

.

В качестве корня можно взять значение: x = 4.943. Видно, что процесс сходится уже на второй итерации.

Для сравнения найдем первый корень нашего уравнения x3 – 6x2 + 3x + 11 = 0 на отрезке [-2,-1] методом Ньютона.

Решение. Так как f//(x) = 6x – 12, то f//(x) < 0 на интервале [-2,-1], а так как  f(-2) = -27 > 0, то x0 = -2.

Вычисления оформим в виде таблицы:

k	xk	|xk+1-xk|	f(xk)	f/(xk)
0	-2	-27	39
1	-1.30769	0.692308	-5.41966	23.82249
2	-1.08019	0.227502	-0.50182	19.46272
3	-1.05441	0.025783	-0.00613	18.9882
4	-1.05408	0.000323	-9.5E-07	18.98229
5	-1.05408	5.02E-08	-2.3E-14	18.98229

Напомним, что методом дихотомии мы достигли заданной точности 0.001 на 10-ой итерации.

Вычислим второй корень нашего уравнения на отрезке [1,3]. Заметим, что  f//(x) = 6x – 12 меняет знак на отрезке при х=2. Уменьшим интервал изоляции так, чтобы f//(x) не меняла знака. Рассмотрим интервал [2.1; 3]:

f//(2.1) = 6⋅2.1 – 12 = 0.6 > 0 

f(2.1) = 0.101 > 0.

Следовательно, x0 = 2.1

Вычисления оформим в виде таблицы:

k	xk	|xk+1-xk|	f(xk)	f/(xk)
0	2.1	0.101	-8.97
1	2.11126	0.01126	3.95E-05	-8.96286
2	2.111264	4.4E-06	6.47E-12	-8.96286
3	2.111264	7.22E-13	0	-8.96286

Если сравнивать с методом простой итерации, то значение этого корня мы получили за две итерации вместо шести.

Эти примеры показывают, что метод Ньютона является более быстросходящимся. Но для его использования необходимо брать начальное приближение достаточно близкое к корню.

Упрощенный метод Ньютона. Эта модификация метода Ньютона используется, если производная f /(x) представляет собой сложную функцию, и для ее вычисления на каждой итерации используется много времени. Зададим  x0 – начальное приближение и вычислим производную z = f /(x0). На следующих итерациях используется вычисленное значение производной:

.

Это упрощение несколько замедляет процесс сходимости к решению, однако сокращает время каждого итерационного цикла.

3. Приближение функций

Если задана функция y(x), то это означает, что любому допустимому значению х сопоставлено значение у. Но нередко оказывается, что нахождение этого значения очень трудоёмко. Например, у(х) может быть определено как решение сложной задачи, в которой х играет роль параметра или у(х) измеряется в дорогостоящем эксперименте. При этом можно вычислить небольшую таблицу значений функции, но прямое нахождение функции при большом числе значений аргумента будет практически невозможно. Функция у(х) может участвовать в каких-либо физико-технических или чисто математических расчётах, где её приходится многократно вычислять. В этом случае выгодно заменить функцию у(х) приближённой формулой, то есть подобрать некоторую функцию φ(х), которая близка в некотором смысле к у(х) и просто вычисляется. Затем при всех значениях аргумента полагают у(х)≈φ(х).