Тема-01-02



Тема 1.2. Методы решения нелинейных уравнений

Перейти к Теме 1.1 Теме 1.3 Огл.

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

1.2.2 Отделение корней

1.2.2.1 Графическое отделение корней

1.2.2.2 Аналитическое отделение корней

1.2.3 Уточнение корней

1.2.3.1 Метод половинного деления

1.2.3.2 Метод итерации

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

1.2.3.4 Метод хорд

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

1.2.4. Тестовые задания по теме «Методы решения нелинейных уравнений»

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

Одной из важнейших и наиболее распространенных задач математического анализа является задача определения корней уравнения с одним неизвестным, которое в общем виде можно представить как f(x) = 0. В зависимости от вида функции f(x)различают алгебраические и трансцендентные уравнения. Алгебраическими уравненияминазываются уравнения, в которых значение функции f(x) представляет собой полином n-й степени:

f(x) = Р(х) = anxn + a2x2 + …+ a1x + a0 = 0.(1.2.1-1)

Всякое неалгебраическое уравнение называется трансцендентным уравнением. Функция f(x)в таких уравнениях представляет собой хотя бы одну из следующих функций: показательную, логарифмическую, тригонометрическую или обратную тригонометрическую.

Решением уравнения f(x)=0называется совокупность корней, то есть такие значения независимой переменной , при которых уравнение обращается в тождество . Однако, точные значения корней могут быть найдены аналитически только для некоторых типов уравнений. В частности, формулы, выражающие решение алгебраического уравнения, могут быть получены лишь для уравнений не выше четвертой степени. Еще меньше возможностей при получении точного решения трансцендентных уравнений. Следует отметить, что задача нахождения точных значений корней не всегда корректна. Так, если коэффициенты уравнения являются приближенными числами, точность вычисленных значений корней заведомо не может превышать точности исходных данных. Эти обстоятельства заставляют рассматривать возможность отыскания корней уравнения с ограниченной точностью (приближенных корней).

Задача нахождения корня уравнения с заданной точностью (>0)считается решенной, если вычислено приближенное значение , которое отличается от точного значения корня не более чем на значение

(1.2.1-2)

Процесс нахождения приближенного корня уравнения состоит из двух этапов:

отделение корней (локализация корней);

итерационное уточнение корней.

На этапе отделения корней решается задача отыскания возможно более узких отрезков , в которых содержится один и только один корень уравнения.

Этап уточнения корня имеет своей целью вычисление приближенного значения корня с заданной точностью. При этом применяются итерационные методы вычисления последовательных приближений к корню: x0, x1, …, xn, …,в которых каждое последующее приближение xn+1вычисляется на основании предыдущего xn. Каждый шаг называется итерацией. Если последовательность x0, x1, …, xn, …при n имеет предел, равный значению корня , то говорят, что итерационный процесс сходится.

Существуют различные способы отделения и уточнения корней, которые мы рассмотрим ниже.

1.2.2. Отделение корней

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

1.2.2.1. Графическое отделение корней

Графическое отделение корней основано на графическом способе решения уравнений – отыскании точек, в которых функция f(x)пересекает ось 0Х.

Пример 1.2.2-1. Отделить корни уравнения ln (x-1)2 – 0.5 = 0.

На рис. 1.2.2-1 изображен график функции y = ln (x-1)2 – 0.5, из которого следует, что уравнение имеет два действительных корня [-1;0] и [2;3].

Рис.1.2.2-1

В некоторых случаях удобно вначале преобразовать функцию f(x) к виду f(x)=g1(x) — g2(x), из которого, при условии f(x)=0, следует, что g1(x)=g2(x). При построении графиков y1=g1(x)и y2=g2(x)находят отрезки, содержащие точки пересечения этих графиков.

Пример 1.2.2-2.Отделить корни уравнения сos(x) – x + 1 = 0.

Приведем исходное уравнение к виду сos(x)= x – 1. Построив графики функций y1 = сos(x) иy2 = х – 1(рис. 1.2.2), выделим отрезок, содержащий корень [1;2].

Рис. 1.2.2-2

1.2.2.2. Аналитическое отделение корней

Аналитическое отделение корней основано на следующей теореме.

Если функцияf(x) непрерывна и монотонна на отрезке[;]и принимает на концах отрезка значения разных знаков, то на отрезке [;] содержится один корень уравнения f(x)=0.

Действительно, если условия теоремы выполнены, как это имеет место на отрезке [a;b] (рис. 1.2.2-3), то есть f(a)∙f(b)<0 и f'(x)>0 для x [a;b], то график функции пересекает ось только один раз и, следовательно, на отрезке [a;b] имеется один корень уравнения f(x) =0.

Аналогично можно доказать единственность корня на отрезке [c;d],на[d;e]и т.д

Рис. 1.2.2-3

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

установить область определения функции;

определить критические точки функции, решив уравнение f(x)=0;

составить таблицу знаков функции f(x) в критических точках и на границах области определения;

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

Пример 1.2.2-3.Отделить корни уравнения xln(x+2) = 0.

Область допустимых значений функции f(x) = x — ln(x+2) лежит в интервале (-2; ∞), найденных из условия x+2>0. Приравняв производную f(x)=1-1/(x+2)к нулю, найдем критическую точкухk= -1. Этиданные сведены в табл.1.2.2-1 и табл. 1.2.2-2 знаков функции f(x).

Таблица1.2.2-1 Таблица 1.2.2-.2

x

x2

-1

x→∞

x

-1.9

-1.1

-0.9

2.0

Sign(f(x))

+

+

Sign(f(x))

+

+

Уравнение x — ln(x+2) = 0 имеет два корня (-2;-1] и [-1; ∞) . Проверка знака функции внутри каждого из полученных полуинтервалов (табл.1.2.2) позволяет отделить корни уравнения на достаточно узких отрезках [-1.9;-1.1] и [-0.9;2.0].

1.2.3. Уточнение корней

Задача уточнения корня уравнения с точностью , отделенного на отрезке [a;b], состоит в нахождении такого приближенного значения корня , для которого справедливо неравенство.Если уравнение имеет не один, а несколько корней, то этап уточнения проводится для каждого отделенного корня.

1.2.3.1. Метод половинного деления

Пусть корень уравнения f(x)=0отделен на отрезке [a;b], то есть на этом отрезке имеется единственный корень, а функция на данном отрезке непрерывна.

Метод половинного деления позволяет получить последовательность вложенных друг в друга отрезков [a1;b1], [a2;b2], …,[ai;bi],…, [an;bn], таких что f(ai).f(bi) 0, где i=1,2,…,n, а длина каждого последующего отрезка вдвое меньше длины предыдущего:

Рис.1.2.3-1

Последовательное сужение отрезка вокруг неизвестного значения корня обеспечивает выполнение на некотором шаге n неравенства bn — an. Поскольку при этом для любого х[an;bn] будет выполняться неравенство — х, то с точностью любое

может быть принято за приближенное значение корня, например его середину отрезка

В методе половинного деления от итерации к итерации происходит последовательное уменьшение длины первоначального отрезка [a0;b0]в два раза (рис. 1.2.3-1). Поэтому на n-м шаге справедлива следующая оценка погрешности результата:

(1.2.3-1)

где — точное значение корня, хn [an;bn] – приближенное значение корня на n-м шаге.

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

(1.2.3-2)

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

Рис. 1.2.3-2. Схема алгоритма метода половинного деления

Схема алгоритма метода половинного деления приведена на рис. 1.2.3-2. В приведенном алгоритме предполагается, что левая часть уравнения f(x)оформляется в виде программного модуля.

Пример 1.2.3-1.Уточнить корень уравнения x3+x-1=0 с точностью =0.1, который локализован на отрезке [0;1].

Результаты удобно представить с помощью таблицы1.2.3-3.

Таблица 1.2.3-3

k

a

b

f(a)

f(b)

(a+b)/2

f((a+b)/2)

a k

b k

1

0

1

-1

1

0.5

-0.375

0.5

1

2

0.5

1

-0.375

1

0.75

0.172

0.5

0.75

3

0.5

0.75

-0.375

0.172

0.625

-0.131

0.625

0.75

4

0.625

0.75

-0.131

0.172

0.688

0.0136

0.625

0.688

Послечетвертой итерации длина отрезка |b4-a4|=|0.688-0.625|=0.063 стала меньше величины , следовательно, за приближенное значение корня можно принять значение середины данного отрезка: x = (a4+b4)/2 = 0.656.

Значение функции f(x) в точке x=0.656 равно f(0.656)= -0.062.

1.2.3.2. Метод итерации

Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x=(x). Если корень уравнения отделен на отрезке [a;b], то исходя из начального приближения x0[a;b], можно получить последовательность приближений к корню

x1 = (x0), x2 = (x1), …,,(1.2.3-3)

где функция (x) называется итерирующей функцией.

Условие сходимости метода простой итерации определяется следующей теоремой.

Пусть кореньх* уравнения x=(x)отделен на отрезке [a;b]и построена последовательность приближений по правилу xn=(xn-1). Тогда, если все члены последовательности xn=(xn-1) [a;b]и существует такоеq (0, что для всех х [a; b]выполняется |’(x)| = q<1, то эта последовательность является сходящейся и пределом последовательности является значение корня x*, т.е. процесс итерации сходится к корню уравнения независимо от начального приближения.

Таким образом, если выполняется условие сходимости метода итераций, то последовательность x0, x1, x2, …, xn,…,полученная с помощью формулы xn+1 = (xn), сходится к точному значению корня:

если

Условие (x)[a;b] при x[a;b] означает, что все приближения x1, x2, …, xn,…,полученные по итерационной формуле, должны принадлежать отрезку [a;b], на котором отделен корень.

Для оценки погрешности метода итерации справедливо условие

(1.2.3-4)

За число q можно принимать наибольшее значение |'(x)|, а процесс итераций следует продолжать до тех пор, пока не выполнится неравенство

(1.2.3-5)

На практике часто используется упрощенная формула оценки погрешности. Например, если 0

|xn1 — xn|.

Использование итерационной формулы xn+1=(xn) позволяет получить значение корня уравнения f(x)=0 с любой степенью точности.

Геометрическая иллюстрация метода итераций. Построим на плоскости X0Y графики функций y=x и y=(x). Корень уравнения х=(x) является абсциссой точки пересечения графиков функции y = (x) и прямой y=x. Возьмем некоторое начальное приближение x0 [a;b]. На кривойy = (x) ему соответствует точка А0 = (x0). Чтобы найти очередное приближение, проведем через точку А0прямую горизонтальную линию до пересечения с прямой y = x (точкаВ1) и опустим перпендикуляр до пересечения с кривой (точкаА1), то естьх1=(x0). Продолжив построение аналогичным образом, имеем ломаную линию А0, В1, А1, В2, А2…, для которой общие абсциссы точек представляют собой последовательное приближение х1, х2, …, хn («лестницу») к корню х*. Из рис. 1.2.3-3а видно, что процесс сходится к корню уравнения.

Рассмотрим теперь другой вид кривой y = (x) (рис. 1.2.6b). В данном случае ломаная линия А0, В1, А1, В2, А2…имеет вид “спирали”. Однако, и в этом случае наблюдается сходимость.

a) b)

Рис. 1.2.3-3

Нетрудно видеть, что в первом случае для производной выполняется условие 0<’(x)< 1,а во втором случае производная ’(x)<0и’(x)>-1. Таким образом, очевидно, что если |’(x)|<1, то процесс итераций сходится к корню.

Теперь рассмотрим случаи, когда |’(x)|>1. На рис. 1.2.3-4а показан случай, когда ’(x)>1, а на рис. 1.2.3-4b – когда ’(x) < -1.В обоих случаях процесс итерации расходится, то есть, полученное на очередной итерации значение х все дальше удаляется от истинного значения корня.

b)

Рис. 1.2.3-4

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

Пусть функция (x) дифференцируема и монотонна в окрестностях корня и существует числоk |‘(x)|, где k 1 (т.е. процесс расходится). Заменим уравнение х=(x) эквивалентным ему уравнением х=(х),где (х) = 1/(x)(перейдем к обратной функции). Тогда

а значит q=1/k<1 и процесс будет сходиться.

Представим функцию (x) как (x) = х — f(x), где — коэффициент,не равный

нулю. Для тогочтобы процесс сходился, необходимо, чтобы 0<|(x)|=|1 - f(x)|<1. Возьмем = 2/(m1+M1), где m1иM1– минимальное и максимальное значенияf’(x) (m1=min|f’(x)|, M1=max|f’(x)|)для х[a;b],т.е.0 m1 f(x) M11.Тогда

и процесс будет сходящимся, рекуррентная формула имеет вид

Если f(x) < 0, то в рекуррентной формуле f(x) следует умножить на -1.

Параметр λ может быть также определен по правилу:

Если , то , а если , то , где .

Схема алгоритма метода итерации приведена на рис. 1.2.3-5.

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

Рис. 1.2.3-5. Схема алгоритма метода итерации

Пример 1.2.3-2.Уточнить корень уравнения 5x – 8∙ln(x) – 8 =0 с точностью 0.1, который локализован на отрезке [3;4].

Приведем уравнение к виду, удобному для итераций:

Следовательно, за приближенное значение корня уравнения принимаем значение x3=3.6892, обеспечивающее требуемую точность вычислений. В этой точке f(x3)=0.0027.

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

Пусть корень уравнения f(x)=0 отделен на отрезке [a;b], причем первая и вторая производные f’(x) и f(x) непрерывны и знакопостоянны при х [a;b].

Пусть на некотором шаге уточнения корня получено (выбрано) очередное приближение к корню хn. Тогда предположим, что следующее приближение, полученное с помощью поправки hn, приводит к точному значению корня

= хn + hn. (1.2.3-6)

Считаяhn малой величиной, представим f(хn+ hn) в виде ряда Тейлора, ограничиваясь линейными слагаемыми

f(хn + hn) f(хn) + hnf’(хn). (1.2.3-7)

Учитывая, что f() = f(хn + hn) = 0, получим f(хn) + hnf ’(хn) 0.

Отсюда hn — f(хn)/ f’(хn). Подставим значение hn в (1.2.3-6) и вместо точного значения корня получим очередное приближение



Страницы: 1 | 2 | Весь текст




map