Метод деления отpезка пополам

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

На тему: НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ. МЕТОДЫРЕШЕНИЯ СИСТЕМЫНЕЛИНЕЙНЫХ УРАВНЕНИЙ

Москва, 2008 год

НАХОЖДЕНИЕ КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ

Постановка задачи

Пусть задана функция , непрерывная вместе со своими несколькими производными. Требуется найти все или некоторые вещественные корни уравнения

. (1)

Данная задача распадается на несколько подзадач. Во-первых, необходимо определить количество корней, исследовать их характер и расположение. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью e. Первая и вторая задачи решаются, как правило, аналитическими или графическими методами. В случае, когда ищутся только вещественные корни уравнения (1), полезно составить таблицу значений функции . Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один.

Найденные приближенные значения корней можно уточнить с помощью различных итерационных методов. Рассмотрим три метода: 1) метод дихотомиии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона.

Методы решения задачи

Метод деления отpезка пополам

Наиболее простым методом, позволяющим найти корень нелинейного уравнения (1), является метод половинного деления.

Пусть на отрезке [a, b] задана непрерывная функция Если значения функции на концах отрезка имеют разные знаки, т.е. то это означает, что внутри данного отрезка находится нечетное число корней. Пусть для определенности корень один. Суть метода состоит в сокращении на каждой итерации вдвое длины отрезка. Находим середину отрезка [a,b] (см. рис. 1) Вычисляем значение функции и выбираем тот отрезок, на котором функция меняет свой знак. Новый отрезок вновь делим пополам. И этот процесс продолжаем до тех пор, пока длина отрезка не сравняется с наперед заданной погрешностью вычисления корня e. Построение нескольких последовательных приближений по формуле (3) приведено на рисунке 1.

Итак, алгоритм метода дихотомии:

1. Задать отрезок [a,b] и погрешность e.

2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться.

Рис.1. Метод деления отрезка пополам для решения уравнения вида f(х)=0.

3. В противном случае вычислить c=(a+b)/2

4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c.

5. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3.

Так как за N шагов длина отрезка [a, b] сокращается в 2^N раз, то заданная погрешность отыскания корня e будет достигнута за итераций.

Как видно, скорость сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Если отрезок [a, b] содержит больше одного корня (но нечетное число), то всегда будет найден какой-нибудь один.

Замечание. Для определения интервала, в котором лежит корень, необходим дополнительный анализ функции , основанный либо на аналитических оценках, либо на использование графического способа решения. Можно также организовать перебор значений функции в различных точках, пока не встретится условие знакопеременности функции

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

При использовании этого метода исходное нелинейное уравнение (1) необходимо переписать в виде

(2)

Обозначим корень этого уравнения C_*. Пусть известно начальное приближение корня . Подставляя это значение в правую часть уравнения (2), получаем новое приближение

и т.д. Для (n+1)- шага получим следующее приближение

(3)

Таким образом, по формуле (3) получаем последовательность С₀, С₁,…,С_n₊₁, которая стремиться к корню С_* при n®¥. Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т. е. выполняется условие

(4)

Исследуем условие и скорость сходимости числовой последовательности {C _n} при n®¥. Напомним определение скорости сходимости. Последовательность {C_n}, сходящаяся к пределу С_*, имеет скорость сходимости порядка a, если при n®¥ выполняется условие

(5)

Допустим, что имеет непрерывную производную, тогда погрешность на (n+1)-м итерационном шаге e_n₊₁=C_n₊₁-C_*=g(C_n)-g(C_*) можно представить в виде ряда

e_n+1» C_n+1– C_* = g¢(C_*) (C_n-C_*) +¼@ g¢(C_*) e_n+¼

Таким образом, получаем, что при выполнении условия

çg¢(C_*) ç< 1 (6)

последовательность (3) будет сходиться к корню с линейной скоростью a=1. Условие (6) является условием сходимости метода простой итерации. Очевидно, что успех метода зависит от того, насколько удачно выбрана функция .

Например, для извлечения квадратного корня, т. е. решения уравнения вида x =a², можно положить

x=g₁(x)=a/x (7а)

или

x=g₂(x)=(x+a/x)/2. (7б)

Нетрудно показать, что

½g₁^'(C)½=1,

½g₂^'(C)½<1.

Таким образом, первый процесс (7а) вообще не сходится, а второй (7б) сходится при любом начальном приближении С₀ >0.

Рис. 2. Графическая интерпретация метода простых итераций для решения уравнения вида x=g(х).

Построение нескольких последовательных приближений по формуле (3)

С₀, С₁, …, С_n = C_*

приведено на рисунке 2.

Метод Ньютона

В литературе этот метод часто называют методом касательных, а также методом линеаризации. Выбираем начальное приближение С₀. Допустим, что отклонение С₀ от истинного значения корня С_* мало, тогда, разлагая f(C_*) в ряд Тейлора в точке С₀, получим

f(C_*) = f(C₀) + f ¢(C₀) (C_*-C₀) +¼ (8)

Если f ¢(C₀) ¹ 0, то в (8) можно ограничится линейными по DC =C-C₀ членами. Учитывая, что f(C_*)=0, из (9) можно найти следующее приближение для корня

C₁ = C₀– f (C₀) / f¢(C₀)

или для (n+1)-го приближения

C_n+1= C _n – f (C _n) / f ¢(C _n) (9)

Для окончания итерационного процесса можно использовать одно из двух условий

çC_n₊₁– C_n ç< e

или

çf(C_n₊₁) ç< e.

Исследование сходимости метода Ньютона проводится аналогично предыдущему случаю. Самостоятельно получить, что при выполнении условия

½f ^''(C)/2f'(C)½<1.

метод Ньютона имеет квадратичную скорость сходимости ().

Рис. 3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0.

Построение нескольких последовательных приближений по формуле (9)

С₀, С₁, …, С_n = C_*

приведено на рисунке 3.

Задание

1. Для заданной функции f(x)

· определите число вещественных корней уравнения f(x)=0, место их расположения и приближенные значения (постройте график или распечатайте таблицу значений).

· Вычислите один из найденных корней (любой) с точностью e=0,5*10^-3.

Для вычислений используйте метод деления отрезка пополам (определите число итераций), а затем этот же корень найдите с помощью метода Ньютона (также определив число итерационных шагов).

Сравните полученные результаты.

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

1. x³–3x² +6x – 5 = 0 2. x ³+sin x –12x-1=0

3. x³ –3x²–14x – 8 = 0 4. 3x + cos x + 1 =0

5. x²+4sin x –1 = 0 6. 4x –ln x = 5

7. x⁶–3x² +x – 1 = 0 8. x³ – 0.1x² +0.3x –0.6 = 0

9. 10. (x -1)³ + 0.5e^x = 0