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

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

 

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

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

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

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

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

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

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

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

1.2.3.4. Метод хорд

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

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

 

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

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

f(x) = Р(х) = a_n xⁿ + a₂ x² + …+ a₁ x + a₀ = 0. ( 1.2.1-1)

 

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

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

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

(1.2.1-2)

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

 

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

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

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

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

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

 

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

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

 

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

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

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

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

Метод половинного деления позволяет получить последовательность вложенных друг в друга отрезков [a_1; b₁], [a₂; b₂], …, [a_i; b_i], …, [a_n; b_n], таких что f(a_i).f(b_i) < 0, где i=1, 2, …, n, а длина каждого последующего отрезка вдвое меньше длины предыдущего:

Рис.1.2.3-1

 

Последовательное сужение отрезка вокруг неизвестного значения корня обеспечивает выполнение на некотором шаге n неравенства |b_n - a_n| < e. Поскольку при этом для любого хÎ [a_n; b_n] будет выполняться неравенство | - х| < , то с точностью любое

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

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

 

( 1.2.3-1 )

 

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

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

 

(1.2.3-2)

 

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

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

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

 

Пример 1.2.3-1. Уточнить корень уравнения x³+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.5	-0.375	0.5
	0.5		-0.375		0.75	0.172	0.5	0.75
	0.5	0.75	-0.375	0.172	0.625	-0.131	0.625	0.75
	0.625	0.75	-0.131	0.172	0.688	0.0136	0.625	0.688

 

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

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

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

 

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

 

x₁ = j(x₀), x₂ = j(x₁), …, , ( 1.2.3-3 )

 

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

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

 

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

Таким образом, если выполняется условие сходимости метода итераций, то последовательность x₀, x₁, x₂, …, x_n, …, полученная с помощью формулы x_n+1 = j(x_n ), сходится к точному значению корня :

 

если

 

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

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

 

(1.2.3-4)

 

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

 

(1.2.3-5)

 

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

 

|x_n-1 - x_n| £ .

 

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

 

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

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

a) b)

Рис. 1.2.3-3

 

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

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

a) b)

Рис. 1.2.3-4

 

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

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

 

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

 

2. Представим функцию j(x) как j(x) = х - lf(x), где l - коэффициент, не равный

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

 

 

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

 

Если 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].

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

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

Метод хорд

 

Геометрическая интерпретация метода хорд состоит в следующем
(рис.1.2.3-8).

Рис.1.2.3-8

 

Проведем отрезок прямой через точки A и B. Очередное приближение x₁ является абсциссой точки пересечения хорды с осью 0х. Построим уравнение отрезка прямой:

 

 

Положим y = 0 и найдем значение х = х₁ (очередное приближение):

 

 

Повторим процесс вычислений для получения очередного приближения к корню - х₂:

 

 

В нашем случае (рис.1.2.11) и расчетная формула метода хорд будет иметь вид

(1.2.3-13)

 

Эта формула справедлива, когда за неподвижную точку принимается точка b, а в качестве начального приближения выступает точка a.

Рассмотрим другой случай (рис. 1.2.3-9), когда .

 

Рис.1.2.3-9

 

Уравнение прямой для этого случая имеет вид

 

 

Очередное приближение х₁ при y = 0

 

 

Тогда рекуррентная формула метода хорд для этого случая имеет вид

 

(1.2.3-14)

 

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

Таким образом, если за неподвижную точку приняли точку а, то в качестве начального приближения выступает х₀ = b, и наоборот.

Достаточные условия, которые обеспечивают вычисление корня уравнения f(x)=0 по формуле хорд, будут теми же, что и для метода касательных (метод Ньютона), только вместо начального приближения выбирается неподвижная точка. Метод хорд является модификацией метода Ньютона. Разница состоит в том, что в качестве очередного приближения в методе Ньютона выступает точка пересечения касательной с осью 0Х, а в методе хорд – точка пересечения хорды с осью 0Х – приближения сходятся к корню с разных сторон.

Оценка погрешности метода хорд определяется выражением

 

(1.2.3-15)

Условие окончания процесса итераций по методу хорд

 

(1.2.3-16)

 

В случае, если M₁< 2m₁, то для оценки погрешности метода может быть использована формула | x_n - x_n-1| £ e.

 

Пример 1.2.3-4. Уточнить корень уравнения e^x – 3x = 0, отделенный на отрезке [0; 1] с точностью 10^-4.

Проверим условие сходимости:

 

 

Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х₀=1, поскольку f(0)=1> 0 и f(0)*f" (0)> 0.

Результаты расчета, полученные с использованием формулы
1.2.3-14, представлены в таблице 1.2.3-4.

 

Таблица 1.2.3-4

i	x	f(x)
	0.7812	-0.1569
	0.6733	-0.0591
	0.6356	-0.0182
…	………..	………..
	0.6191	-4.147∙ 10-5

 

Требуемая точность достигается на 8-й итерации. Следовательно, за приближенное значение корня можно принять х = 0.6191.

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

Выбор неподвижной точки, определяющей вид расчетной формулы, производится путем сравнения одного из концов отрезка [a; b] с начальным приближением (x₀=a). В качестве неподвижного конца отрезка (точка с) выбирается тот, который не совпадает с начальным приближением.

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

 

Нелинейное уравнение – это

1) алгебраическое или трансцендентное уравнение

2) алгебраическое уравнение

3) тригонометрическое уравнение

4) трансцендентное уравнение

 

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

 

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

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

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

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

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

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

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

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

1.2.3.4. Метод хорд

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

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

 

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

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

f(x) = Р(х) = a_n xⁿ + a₂ x² + …+ a₁ x + a₀ = 0. ( 1.2.1-1)

 

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

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

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

(1.2.1-2)

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

 

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

123Следующая ⇒

Поделиться:

Популярное:

1. III. Интегральная математическая модель расчета газообмена в здании, при пожаре
2. IV. Математическая двухзонная модель пожара в здании
3. LANGUAGE IN USE - Повторение грамматики: система времен английских глаголов в активном залоге
4. Linux - это операционная система, в основе которой лежит лежит ядро, разработанное Линусом Торвальдсом (Linus Torvalds).
5. SWIFT как система передачи данных.
6. VI. Приемно-комплексная система
7. Автоматическая система сепарирования Алькап. Назначение, принцип действия.
8. Авторская технология преподавания математики «Учителя года-98» В.Л. Ильина
9. Адресно-аналоговая система пожарной сигнализации
10. АНАЛИЗ ОДНОМЕРНЫХ ПОТОКОВ ПРИ НЕЛИНЕЙНЫХ
11. Англо-американская правовая система
12. Англо-саксонская правовая система. Особенности американского права.