Графический способ решения нелинейных уравнений

Графический метод решения задач нелинейного программирования

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.
Построить семейство линий уровня целевой функции f(х₁, х₂) = C при различных значениях числового параметра С.
При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.
Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.
Найти координаты точки оптимума и определить в ней значение ЦФ.

Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.

Пример . В задаче выпуклого программирования требуется:

найти решение графическим методом;
написать функцию Лагранжа и найти ее седловую точку, используя решение, полученное графически.

F(X) = x₁ 2 +(x₂-2) 2
2x₁+x₂ ≥ 7
x₁+2x₂ ≥ 5

Решение. 1) Строим два ограничения, тем самым определяя ОДР. Можно использовать этот калькулятор. Также удобно строить ограничения через этот сервис.

Затем строим функцию цели. В данном случае это окружность.

Поскольку задача минимума, то ищем первое касание линии уровня области ОДР. В данном случае это точка пересечения с прямой 2x₁+x₂-7=0.
Найдем точку пересечения. Для этого построим уравнение касательной, проходящей через центр окружности O(0;2) и перпендикулярно прямой 2x₁+x₂-7=0 (можно использовать этот калькулятор). Получаем: 2x₂-x₁-4=0. Решая систему уравнений:
2x₁+x₂-7=0
2x₂-x₁-4=0,
получаем: x₁=2, x₂=3.

2) Найдем экстремум функции F(X) = x₁ 2 +(x₂-2) 2 , используя калькулятор Функция Лагранжа :
L( X , λ )=F( X )+∑(λ_i·φ_i)
где F( X ) — целевая функция вектора X; φ_i(X) — ограничения в неявном виде (i=1..n)
В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция: F(X) = x₁ 2 +(x₂-2) 2
Перепишем ограничение задачи в неявном виде:
φ₁(X) = 7 — (2*x₁+x₂) = 0 (X₁)
φ₂(X) = 5 — (x₁+2*x₂) = 0 (X₂)
Составим вспомогательную функцию Лагранжа: L(X, λ) = x₁ 2 +(x₂-2) 2 — λ₁*(7 — (2*x₁+x₂)) — λ₂*(5 — (x₁+2*x₂))
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х_i и неопределенным множителям λ.
Составим систему:
∂L/∂x₁ = 2*λ₁+λ₂+2*x₁ = 0
∂L/∂x₂ = λ₁+2*λ₂+2*x₂-4 = 0
∂L/∂λ₁ = 2*x₁+x₂-7 = 0
∂L/∂λ₂ = x₁+2*x₂-5 = 0
Решив данную систему, получаем:
а) для случая X₁: x₁ = λ₁/2 + λ₂ + 2; x₂ = 7 — 2x₁
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2; x₁ = 2; x₂ = 3.
Поскольку λ₂ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(2;3)=5

б) для случая X₂: x₂ = λ₁/2 + λ₂ + 2; x₁ = 5 — 2x₂
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2/5; x₁ = 11/5; x₂ = 3/5.
Поскольку λ₁ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(11/5;3/5)=6.8

Минимальное значение составит Z_min(2;3)=5.

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

Уравнения, в которых содержатся неизвестные функции, произведенные в степень больше единицы, называются нелинейными.
Например, y=ax+b – линейное уравнение, х^3 – 0,2x^2 + 0,5x + 1,5 = 0 – нелинейное (в общем виде записывается как F(x)=0).

Системой нелинейных уравнений считается одновременное решение нескольких нелинейных уравнений с одной или несколькими переменными.

Существует множество методов решения нелинейных уравнений и систем нелинейных уравнений, которые принято относить в 3 группы: численные, графические и аналитические. Аналитические методы позволяют определить точные значения решения уравнений. Графические методы наименее точны, но позволяют в сложных уравнениях определить наиболее приближенные значения, с которых в дальнейшем можно начинать находить более точные решения уравнений. Численное решение нелинейных уравнений предполагает прохождения двух этапов: отделение корня и его уточнение до определенно заданной точности.
Отделение корней осуществляется различными способами: графически, при помощи различных специализированных компьютерных программ и др.

Рассмотрим несколько методов уточнения корней с определенно заданной точностью.

Методы численного решения нелинейных уравнений

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

Суть метода половинного деления заключается в делении интервала [a,b] пополам (с=(a+b)/2) и отбрасывании той части интервала, в которой отсутствует корень, т.е. условие F(a)xF(b)

Рис.1. Использование метода половинного деления при решении нелинейных уравнений.

Рассмотрим пример. Необходимо решить уравнение х^3 – 0,2x^2 + 0,5x + 1,5 = 0 с точностью до e 0, то начала отрезка a переносится в x (a=x), иначе, конец отрезка b переносится в точку x (b=x). Полученный отрезок делим опять пополам и т.д. Весь произведенный расчет отражен ниже в таблице.

Рис.2. Таблица результатов вычислений

В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946

При использовании метода хорд, задается отрезок [a,b], в котором есть только один корень с установленной точностью e. Через точки в отрезке a и b, которые имеют координаты (x(F(a);y(F(b)), проводится линия (хорда). Далее определяются точки пересечения этой линии с осью абсцисс (точка z).
Если F(a)xF(z)

Рис.3. Использование метода хорд при решении нелинейных уравнений.

Рассмотрим пример. Необходимо решить уравнение х^3 – 0,2x^2 + 0,5x + 1,5 = 0 с точностью до e 0;

Определим вторую производную F’’(x) = 6x-0,4.

F’’(-1)=-6,4 0 соблюдается, поэтому для определения корня уравнения воспользуемся формулой:

, где x0=b, F(a)=F(-1)=-0,2

Весь произведенный расчет отражен ниже в таблице.

Рис.4. Таблица результатов вычислений

В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946

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

Данный метод основывается на построении касательных к графику, которые проводятся на одном из концов интервала [a,b]. В точке пересечения с осью X (z1) строится новая касательная. Данная процедура продолжается до тех пор, пока полученное значение не будет сравним с нужным параметром точности e (F(zi)

Рис.5. Использование метода касательных (Ньютона) при решении нелинейных уравнений.

Рассмотрим пример. Необходимо решить уравнение х^3 – 0,2x^2 + 0,5x + 1,5 = 0 с точностью до e 0 выполняется, поэтому расчеты производим по формуле:

Весь произведенный расчет отражен ниже в таблице.

Рис.6. Таблица результатов вычислений

В результате вычислений получаем значение с учетом требуемой точности, равной x=-0,946

Если материал был полезен, вы можете отправить донат или поделиться данным материалом в социальных сетях:

Графический способ решения нелинейных уравнений

1. Приближенное решение нелинейных уравнений

Пусть дано уравнение с одним неизвестным

, (1.1)

где f ( x ) — заданная алгебраическая или трансцендентная функция.

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

Решить уравнение — значит найти все его корни, то есть те значения х , которые обращают уравнение в тождество, или доказать, что корней нет.

В общем случае не существует формул, по которым определяются точные значения корней уравнения (1.1). Для отыскания корней используют приближенные методы, при этом корни находятся с некоторой заданной точностью ε . Это означает, что если x — точное значение корня уравнения, а x ’ — его приближенное значение с точностью ε , то | x — x ’ | ≤ ε . Если корень найден с точностью ε , то принято писать x = x ± ε .

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

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

1. Отделение корней, то есть нахождение интервалов из области определения функции f ( x ), в каждом из которых содержится только один корень уравнения (1).

2. Уточнение корней до заданной точности.

Отделение корней можно проводить графически и аналитически.

Для того , чтобы графически отделить корни уравнения (1.1), строят график функции y = f ( x ). Абсциссы точек его пересечения с осью Ox есть действительные корни уравнения (рис. 1). Практически бывает удобнее заменить уравнение (1.1) равносильным ему уравнением

, (1.2)

где Φ( x ) и Ψ( x ) — более простые функции, чем f ( x ). Абсциссы точек пересечения графиков функций y = Φ( x ) и y = Ψ( x ) дают корни уравнения (1.2), а значит и исходного уравнения (1.1) (рис.2).

Аналитическое отделение корней основано на следующей теореме: если непрерывная на отрезке [ a , b ] функция y = f ( x ) принимает на концах отрезка значения разных знаков, т.е. f ( a )· f ( b ) f ( x ) = 0; если при этом производная f ’ ( x ) сохраняет знак внутри отрезка [ a , b ], то корень является единственным.

Уточнение корней заключается в сужении интервала изоляции корня и выполняется одним из специальных методов. Рассмотрим самый простой из них — метод половинного деления.

Пусть корень отделён и принадлежит отрезку [ a , b ]. Находим середину отрезка [ a , b ] по формуле

Если f ( c ) = 0, то с — искомый корень. Если f ( c ) ≠ 0, то в качестве нового отрезка изоляции корня [ a ₁ , b ₁ ] выбираем ту половину [ a , c ] или [ c , b ], на концах которой f ( x ) принимает значения разных знаков. Другими словами, если f ( a ) ∙ f ( c ) a , c ], если f ( a ) ∙ f ( c ) — отрезку [ c , b ]. Полученный отрезок снова делим пополам, находим c₁ ,

вычисляем f ( c ₁ ), выбираем отрезок [ a ₂ , b ₂ ] и т.д. Длина каждого нового отрезка вдвое меньше длины предыдущего, то есть за n шагов отрезок сократится в 2 n раз. Как только будет выполнено условие