Симплекс-метод

1. Идея симплекс-метода

Рассмотрим универсальный метод решения канонической задачи ЛП.

известный как симплекс-метод.

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

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

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

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

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

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

Общая схема симплекс-метода состоит из следующих основных шагов.

·0 шаг . Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана) .

·1 шаг . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

·2 шаг . Нахождение переменной, вводимой в состав базисных. (Из условия увеличения целевой функции).

·3 шаг . Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).

·4 шаг . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1-4 образуют одну итерацию симплекс-метода.

Из этой схемы следует, что, во-первых, для начала работы симплекс-метода надо иметь какую-то угловую точку - начальный базисный план, а во-вторых, надо уметь исследовать текущую угловую точку на оптимальность, не вычисляя всех смежных вершин. Эти проблемы легко решаются, если каноническая задача ЛП имеет некий специальный вид.

Определение . Будем говорить, что каноническая задача ЛП имеет «предпочтительный вид», если

1.правые части уравнений, .

Матрица условий содержит единичную подматрицу размера

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

Пример.

Матрица условий и вектор правых частей ограничений имеют вид

Сразу очевидна одна базисная матрица: с единичными векторами

Следовательно, - базисные переменные, а x2, x4 - небазисные. Полагая в системе уравнений x2=x4 =0, немедленно находим x1 =10, x3 =20, x5 =8. Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей bi.

В дальнейшем, базисные переменные будем объединять в вектор x Б.

Таким образом, в канонической задаче предпочтительного вида в качестве начальной базисной матрицы берется единичная подматрица AБ =E, а соответствующие ей базисные переменные равны правым частям ограничений: xБ =b.

. Простейшая реализация симплекс-метода

Простейшая реализация симплекс-метода («простой С-метод») применяется к канонической задаче ЛП, имеющей «предпочтительный вид». Не умаляя общности, будем считать, что единичная подматрица содержится в первых m столбцах. Тогда каноническая задача запишется следующим образом

f(x) = c1x1 + c2x2 +… + cmxm + cm+1xm+1 +… + cnxn ??max(3.1)x1 + a1m+1 xm+1 + … + a1n xn = b1(3.2)x2 + a2m+1 xm+1 + … + a2n xn = b2………………………………………………………….xm + amm+1 xm+1 + … + amn xn = bmxj³ 0, j=1,2,…, n.(3.3)

Матрица условий

содержит единичную подматрицу размера m x m в первых m столбцах, следовательно AБ ={A1, A2,…, Am}=E.

Основные шаги симплекс-метода (теория)

Поскольку единичная базисная матрица находится в первых m столбцах матрицы условий, то первые m координат начального базисного плана являются базисными, а последние n - m координат являются небазисными, то есть равны нулю:

o = (x1, x2,…, xm, 0,…, 0).

Подставляя координаты точки xo в ограничения (3.2) и учитывая, чтоm+1 =… = xn = 0, получаем: x1 = b1, x2 = b2,…, xm = bm, то есть xoБ = b.

Значит начальный базисный план имеет вид:

xo = (b1,…, bm, 0,…, 0),

где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных.

1 шаг.

Из системы ограничений (3.2) выразим базисные переменные через небазисные:

x1= b1 - a1m+1xm+1 - … - a1nxn, x2 = b2 - a2m+1xm+1 - … - a2nxn, ………………………………………… xm = bm - amm+1xm+1 - … - amnxn,(3.4)

Подставим эти выражения в целевую функцию (3.1).

f (x) = c1 (b1 - a1m+1xm+1 - … - a1nxn) + c2 (b2 - a2m+1xm+1 - … - a2nxn) +

………………………………………………..

Cm (bm - amm+1xm+1 - … - amnxn) + cm+1xm+1 +… + cnxn.

Сгруппируем слагаемые при одинаковых небазисных переменных:

f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …-

- (c1 a1n + c2 a2n + … + cm amn - cn). xn.(3.5)

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

c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1 = < cБ, Am+1 > - cm+1 = Dm+1,

…………………………………………………………………………………………………………………………1 a1n + c2 a2n + … + cm amn - cn = < cБ, An > - cn = Dn,

где сБ = (с1,…, сm) - вектор, составленный из коэффициентов целевой функции при базисных переменных, Am+1,…, An - столбцы матрицы условий А при небазисных переменных xm+1,…, xn.

Выражения

D j = < сБ, Aj > - cj, j = m+1,…, n,(3.6)

называются симплексными разностями или симплексными оценками базисного плана.

С учетом (3.6), формулу (3.5) для целевой функции можно переписать в виде

Эта формула позволяет получить признак оптимальности базисного плана. Если все симплексные оценки с небазисными номерами D j ³ 0, то текущий базисный план - оптимален.

Действительно, если хотя бы одна оценка, например, ?k строго отрицательна, то придавая соответствующей небазисной переменной xk положительное значение, а остальные небазисные переменные плана x полагая равными нулю, получим

f (x) = f (xo) - Dk xk = f (xo) + | D k | xk > f (xo),(3.7)

то есть в этом случае план xo может быть улучшен.

Легко проверить, что симплексные оценки, соответствующие единичным базисным столбцам всегда равны 0.

2 шаг . Нахождение переменной вводимой в состав базисных переменных.

Как следует из формулы (3.7), целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) небазисную переменную xj, которой соответствует отрицательная оценка?j < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную хк с наибольшей по модулю отрицательной оценкой, то есть такую, для которой

где D j = < CБ, Aj > - cj, j = m+1,…, n (номера небазисных переменных).

Таким образом мы получим новый план

x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).

Но х1 - небазисный план, так как число положительных координат равно m+1, число нулевых координат равно n - m -1.

Чтобы получить новую угловую точку, занулим одну из базисных переменных, то есть выведем одну переменную из состава базисных.

3 шаг.

Подставим координаты точки х1 в условия (3.4) и учтем, что переменные xj должны быть неотрицательны

x1 = b1 - a1kxk³ 0 x2 = b2 - a2kxk³ 0 …………………………. xm = bm - amkxk³ 0(3.8)

Из формулы (3.7) видно, что чем больше величина хк > 0, тем больше возрастает целевая функция. Постараемся найти максимальное значение хк, не нарушая ограничений задачи и выполняя условия неотрицательности (3.8).

Неравенства (3.8) можно переписать в виде

A1kxk£ b1 a2kxk£ b2 ……………… amkxk £ bm(3.9)

При решении системы неравенств (3.9) возможны два случая:) среди коэффициентов при хк нет положительных: aik£ 0, i=1,2,…, m. Так как bi> 0, то неравенства (3.9) выполняются при любом сколь угодно большом значении хк. Это говорит о том, что целевая функция не ограничена на множестве планов (max f(x) ® ¥) и следовательно, решения задачи ЛП не существует.) среди коэффициентов при хк есть положительные aik > 0. Решая систему неравенств (3.9) получим:

хк £ bi /aik, для всех i, для которых aik > 0.(3.10)

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

хк = min {bi /aik} по всем i: aik > 0.

Пусть минимум достигается при i = r, то есть хк ? br /ark. Это означает, что базисная переменная хr в условиях (3.8) обращается в нуль.

хr = br - ark xk = br - ark (br /ark) = 0, 1 ??r ??m.

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

4 шаг.

Новый базисный план будет иметь вид

1 = (x1, x2,…, 0,…, xm, 0,…, хk,0,…, 0),

где на месте хr стоит ноль, а хк > 0.тому базисному плану соответствует новая базисная матрица:

Для нахождения координат новой угловой точки х1 каноническая задача ЛП приводится к новому предпочтительному виду, то есть к такой форме, чтобы матрица стала единичной (= E). Для этого столбец Аk нужно преобразовать к единичному представлению,

R-я строка,

в котором коэффициент = 1, а все остальные элементы =0, i ??r. Этого можно добиться с помощью элементарных операций над уравнениями системы. Решение заканчивается тогда, когда для некоторой точки все оценки Dj ³ 0.

3. Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере из главы 2.

Рассмотрим каноническую задачу ЛП

f(x) = x1+ 2x2 +0 x3 + 0 x4 max(3.11)-x1+ 2x2+ x3 = 4,(3.12)3 x1 +2x2 + x4 = 12,(3.13)xj ? 0, j = 1,2,3,4.(3.14)

Матрица условий A = (A1, A2, A3, A4), где

Целевой вектор c =(c1, c2, c3, c4)=(1, 2, 0, 0); вектор правых частей b=(b1, b2) = (4, 12).

0 шаг. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A3, A4 образуют единичную подматрицу. Значит начальная базисная матрица = (A3, A4); x3 и x4 - базисные переменные, x1 и x2 - небазисные переменные, cБ = (c3, c4) = (0, 0).

Начальный базисный план имеет вид

x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.

1 шаг. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (3.6)

D1 = < cБ, A1 > - c1 = 0 ·(-1) + 0 ·3 - 1 = -1.

D2 = < cБ, A2 > - c2 = 0 ·2 + 0 · 2 - 2 = -2.

Так как оценки отрицательны, то план xo - не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

2 шаг . Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x1 или x2, поскольку обе оценки Dj < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.

3 шаг. Определение переменной выводимой из базиса.

После ввода в базис переменной x2 новый план будет иметь вид1 = (0, x2, x3, x4).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x3 или x4.

Подставим координаты плана x1 = (0, x2, x3, x4) в ограничения задачи. Получим

Выразим отсюда базисные переменные x3 и x4 через переменную x2, вводимую в базис.

x3 = 4 - 2x2,(3.15)x4 = 12 - 2x2.(3.16)

Так переменные x3 и x4 должны быть неотрицательны, получим систему неравенств

4 - 2x2 ³ 0,(3.17)12 - 2x2 ³ 0.(3.18)

Чем больше значение x2, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (3.17), (3.18).

Перепишем неравенства в виде

x2£ 4,

x2£12,

откуда максимальное значение x2 = min {4/2, 12/2} = 2. Подставляя это значение в выражения (3.15), (3.16) для x3 и x4, получаем x3 = 0. Следовательно x3 выводится из базиса.

4 шаг. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x1 = (0, x2, 0, x4).

Базис этой точки состоит из столбцов A2 и A4, так что = (A2, A4). Заметим, что этот базис не является единичным, так как вектор A2 = (2, 2), и следовательно задача (3.11) - (3.14) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (3.12), (3.13) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x2, x4, то есть чтобы переменная x2 входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

x1+ 2x2+ x3 = 4, (p1)

x1 +2x2 + x4 = 12. (p2)

Поделим первое уравнение на коэффициент при x2. Получим новое уравнение = p1 / 2, эквивалентное исходному

1/2 x1+ x2+ 1/2 x3 = 2. ()

Используем это уравнение, которое назовем разрешающим, для исключения переменной x2 из второго уравнения. Для этого надо уравнение умножить на 2 и вычесть из p2. Получим уравнение = p2 - 2 = p2 - p1.

x1 - x3 + x4 = 8. ()

В итоге получили новое «предпочтительное» представление исходной задачи (3.11) - (3.14) относительно новых базисных переменных x2, x4:

f(x) = x1+ 2x2 + 0 x3 + 0 x4® max

1/2 x1+ x2+ 1/2 x3 = 2. ()

x1 - x3 + x4 = 8. ()

xj ³ 0, j = 1,2,3,4.

Подставляя сюда представление нового базисного плана x1 = (0, x2,0, x4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x1 = (0,2,0,8); f(x1)=4.

На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.

Мы не будем проводить вторую итерацию по схеме первой, поскольку все вычисления симплекс-метода удобнее проводить в табличном виде.

симплекс переменная канонический программирование

Литература

1. Эконометрика: Учебник / Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 344 с.: ил.

Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - М.: Финансы и статистика, 2002. - 192 с.: ил.

Кремер Н.Ш., Путко Б.А. Эконометрика: Учебник для вузов. - М.: ЮНИТИ-ДАНА, 2002. - 311 с.

Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: учебник. - М.: Дело, 2001. - 400 с.

Катышев П.К., Магнус Я.Р., Пересецкий А.А. Сборник задач к начальному курсу эконометрики. - 3-е изд., испр. - М.: Дело, 2003. - 208 с.

Доугерти К. Введение в эконометрику. - М.: Финансы и статистика, 1999.

Джонстон Дж. Эконометрические методы. - М.: Статистика, 1980.

Кейн Э. Экономическая статистика и эконометрия. Введение в количественный экономический анализ. Вып. 1. - М.: Статистика, 1977.

Ланге О. Введение в эконометрику / Пер. с польск. - М.: Прогресс, 1964.

Лизер С. Эконометрические методы и задачи. - М.: Статистика, 1971.

Маленво Э. Статистические методы эконометрии. - М.: Статистика, 1976.

Тинтнер Г. Введение в эконометрию. - М.: Финансы и статистика, 1965.

Айвазян С.А., Мхитарян В.С. Прикладная статистика и основы эконометрики: учебник для вузов. - М.: ЮНИТИ, 1998.

Вентцель Е.С. Теория вероятностей: Учебник для вузов. - 6-е изд. - М.: Высш. шк., 1999.

Назначение сервиса . Сервис предназначен для нахождения корней уравнений f(x) в онлайн режиме методом хорд.

Инструкция . Введите выражение F(x) , нажмите Далее. Полученное решение сохраняется в файле Word . Также создается шаблон решения в Excel . Ниже представлена видеоинструкция.

F(x) =

Искать в интервале от до
Точность ξ =
Количество интервалов разбиения , n =
Метод решения нелинейных уравнений Метод дихотомии Метод Ньютона (метод касательных) Модифицированный метод Ньютона Метод хорд Комбинированный метод Метод золотого сечения Метод итераций Метод секущих

Правила ввода функции

Примеры
≡ x^2/(x+2)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)

Рассмотрим более быстрый способ нахождения корня на интервале , в предположении, что f(a)f(b)<0.
f’’(x)>0 f’’(x)<0
f(b)f’’(b)>0 f(a)f’’(a)>0


Рис.1а Рис. 1б

Рассмотрим рис.1а. Проведем через точки А и В хорду. Уравнение хорды
.
В точке x=x 1 , y=0, в результате получим первое приближение корня
. (3.8)
Проверяем условия
(а) f(x 1)f(b)<0,
(б) f(x 1)f(a)<0.
Если выполняется условие (а), то в формуле (3.8) точку a заменяем на x 1 , получим

.

Продолжая этот процесс, получим для n-го приближения
. (3.9)
Здесь подвижен конец a, то есть f(x i)f(b)<0. Аналогичная ситуация на рис 2а.
Рассмотрим случай, когда неподвижен конец a .
f’’(x)<0 f’’(x)>0
f(b)f’’(b)<0 f(a)f’’(a)<0


Рис.2а Рис.2б

На рис 1б,2б выполняется f(x i)f(a)<0. Записав уравнение хорды, мы на первом шаге итерационного процесса получим x 1 (см. (3.8)). Здесь выполняется f(x 1)f(a)<0. Затем вводим b 1 =x 1 (в формуле (3.8) точку b заменяем на x 1), получим
.

Продолжая процесс, придем к формуле
. (3.10)
Останов процесса

|x n – x n-1 |<ε; ξ≈x n

Рис. 3
На рис.3 f’’(x) меняет знак, поэтому подвижными будут оба конца.
Прежде чем перейти к вопросу о сходимости итерационного процесса метода хорд введем понятие выпуклой функции.

Определение. Непрерывная на функция называется выпуклой (вогнутой), если для любых двух точек x 1 ,x 2 , удовлетворяющих a≤x 1 f(αx 1 + (1-α)x 2) ≤ αf(x 1) + (1-α)f(x 2) - выпуклая.
f(αx 1 + (1-α)x 2) ≥ αf(x 1) + (1-α)f(x 2) - вогнутая
Для выпуклой функции f’’(x)≥0.
Для вогнутой функции f’’(x)≤0

Теорема 3. Если функция f(x) выпукла (вогнута) на отрезке , то на любом отрезке график функции f(x) лежит не выше (не ниже) хорды, проходящей через точки графика с абсциссами x 1 и x 2 .

Доказательство:

Рассмотрим выпуклую функцию. Уравнение хорды: проходящей через x 1 и x 2 имеет вид:
.
Рассмотрим точку c= αx 1 + (1-α)x 2 , где aÎ

С другой стороны, по определению выпуклой функции имеем f(αx 1 + (1-α)x 2) ≤ αf 1 + (1-α)f 2 ; поэтому f(c) ≤ g(c) ч.т.д.

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

Теорема 4. Пусть задана непрерывная: дважды дифференцируемая функция f(x) на и пусть f(a)f(b)<0, а f’(x) и f’’(x) сохраняют свои знаки на (см. рис 1а,1б и рис 2а,2б). Тогда итерационный процесс метода хорд сходится к корню ξ с любой наперед заданной точностью ε.
Доказательство: Рассмотрим для примера случай f(a)f’’(a)<0 (см рис 1а и 2а). Из формулы (9) следует, что x n > x n -1 так как (b-x n -1)>0, а f n -1 /(f b -f n -1)<0. Это справедливо для любого n, то есть получаем возрастающую последовательность чисел
a≤x 0 Докажем теперь, что все приближения x n < ξ, где ξ - корень. Пусть x n -1 < ξ. Покажем, что x n тоже меньше ξ. Введем
. (3.11)
Имеем
(3.12)
(то есть значение функции y(x) в точке x n на хорде совпадает с f(ξ)).
Так как , то из (3.12) следует
или
. (3.13)
Для рис. 1а , следовательно
или
значит что и т.д. (см. (3.11)).
Для рис 2а . Следовательно, из (3.12) получим
значит
так как ч.т.д.
Аналогичное доказательство для рис.1б и рис.2б. Таким образом, мы доказали, что последовательность чисел является сходящейся.
a≤x 0 a≤ ξЭто значит, что для любого ε можно указать такое n, что будет выполняться |x n - ξ |<ε. Теорема доказана.
Сходимость метода хорд линейная с коэффициентом .
, (3.14)
где m 1 =min|f’(x)|, M 1 =max|f’(x)|.
Это вытекает из следующих формул. Рассмотрим случай неподвижного конца b и f(b)>0.
Имеем из (3.9) . Отсюда
. Учитывая, что , мы можем записать или
.
Заменяя в знаменателе правой части (ξ-x n -1) на (b-x n -1) и учитывая, что (ξ-x n -1)< (b-x n -1), получим , что и требовалось доказать (см. неравенство (3.14)).
Доказательство сходимости для случая рис.3 (f’’(x) меняет знак; в общем случае как f’, так и f’’ могут менять знаки) более сложное и здесь не приводится.

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

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

Метод простых итераций для уравнения f (x ) = 0 заключается в следующем:

1) Исходное уравнение преобразуют к виду, удобному для итераций:

x = φ (х ). (2.2)

2) Выбирают начальное приближение х 0 и вычисляют последующие приближения по итерационной формуле
x k = φ (х k -1), k =1,2, ... (2.3)

Если существует предел итерационной последовательности, он является корнем уравнения f (x ) = 0, т. е. f (ξ ) =0.

y = φ (х )

a x 0 x 1 x 2 ξ b

Рис. 2. Сходящийся процесс итераций

На рис. 2 показан процесс получения очередного приближения по методу итераций. Последовательность приближений сходится к корню ξ .

Теоретические основы для применения метода итера­ций дает следующая теорема.

Теорема 2.3 . Пусть выполняются условия:

1) корень уравнения х = φ(х) принадлежит отрезку [а , b ];

2) все значения функции φ (х ) принадлежат отрезку [а , b ],т. е. а ≤ φ (х )≤ b ;

3) существует такое положительное число q < 1, что производная φ "(x ) во всех точках отрезка [а , b ] удовлет­воряет неравенству |φ "(x ) | ≤ q .

1) итерационная последовательность х п = φ (х п- 1)(п = 1, 2, 3, ...) сходится при любом x 0 Î [а , b ];

2) предел итерационной последовательности является корнем уравнения

х = φ (x ), т. е. если x k = ξ, то ξ= φ (ξ);

3) справедливо неравенство, характеризующее ско­рость сходимости итерационной последовательности

| ξ-x k | ≤ (b-a )×q k . (2.4)

Очевидно что, эта теорема ставит, довольно, жесткие условия, которые необходимо проверить перед примене­нием метода итераций. Если производная функции φ (x ) по модулю больше единицы, то процесс итераций расхо­дится (рис. 3).

y = φ (x ) y = x

Рис. 3. Расходящийся процесс итераций

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

|x k - x k - 1 | ≤ ε . (2.5)

Метод хорд заключается в замене кривой у = f (x ) отрезком прямой, проходящей через точки (а , f (a )) и (b , f (b )) рис. 4). Абсцисса точки пересечения прямой с осью ОХ принимается за очередное приближение.

Чтобы получить расчетную формулу метода хорд, за­пишем уравнение прямой, проходящей через точки (a , f (a )) и (b , f (b )) и, приравнивая у к нулю, найдем х :

Þ

Алгоритм метода хорд :

1) пусть k = 0;

2) вычислим следующий номер итерации: k = k + 1.

Найдем очередное k -e приближение по формуле:

x k = a - f (a )(b - a )/(f (b ) - f (a )).

Вычислим f (x k );

3) если f (x k )= 0 (корень найден), то переходим к п. 5.

Если f (x k ) ×f (b )>0, то b = x k , иначе a = x k ;

4) если |x k – x k -1 | > ε , то переходим к п. 2;

5) выводим значение корня x k ;

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

Рис. 4. Метод хорд

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

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

Первый способ выражает геометрический смысл метода Ньютона и состоит в том, что вместо точки пересечения графика функции у = f (x )с осью Оx ищем точку пересечения с осью Оx касательной, проведенной к графику функции в точке (x n , f (x n )),как показано на рис. 5. уравнение касательной имеет вид у - f (x n )= f " (x n )(x - x n ).

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

В точке пересечения касательной с осью Оx переменная у = 0. Приравнивая у к нулю, выразим х и получим формулу метода касательных :

(2.6)

Второй способ: разложим функцию f (x )в ряд Тейлора в окрестности точки х = х n :

Ограничимся линейными слагаемыми относительно (х - х п ),приравняем к нулю f (x ) и, выразив из получен­ного уравнения неизвестное х ,обозначив его через х n +1 получим формулу (2.6).

Приведем достаточные условия сходимости метода Ньютона.

Теорема 2.4 . Пусть на отрезке [а , b ]выполняются ус­ловия:

1) функция f (x )и ее производные f " (х )и f "" (x )непре­рывны;

2) производные f " (x)и f ""(x )отличны от нуля и сохра­няют определенные постоянные знаки;

3) f (a )× f (b ) < 0 (функция f (x )меняет знак на отрезке).
Тогда существует отрезок [α , β ], содержащий искомый корень уравнения f (x ) = 0, на котором итерационная пос­ледовательность (2.6) сходится. Если в качестве нулевого приближения х 0 выбрать ту граничную точку [α , β ], в ко­торой знак функции совпадает со знаком второй произ­водной,

т.е. f (x 0)× f" (x 0)>0, то итерационная последо­вательность сходится монотонно

Замечание . Отметим, что метод хорд как раз идет с противо­положной стороны, и оба этих метода могут друг друга допол­нять. Возможен и комбинированный метод хорд-касательных.

5. Метод секущих

Метод секущих может быть получен из метода Ньютона при замене производной приближенным выражени­ем – разностной формулой:

, ,

. (2.7)

В формуле (2.7) используются два предыдущих при­ближения х п и x n - 1 .Поэтому при заданном начальном приближении х 0 необходимо вычислить следующее приближение x 1 , например, методом Ньютона с приближенной заменой производной по формуле

,

Алгоритм метода секущих :

1) заданы начальное значение х 0 и погрешность ε . Вычислим

;

2) для п = 1, 2, ... пока выполняется условие |x n – x n -1 | > ε , вычисляем х п+ 1 по формуле (2.7).

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

В отличие от метода половинного деления, метод хорд предлагает, что деление рассматриваемого интервала будет выполняться не в его середине, а в точке пересечения хорды с осью абсцисс (ось - Х). Следует отметить, что под хордой понимается отрезок, который проведен через точки рассматриваемой функции по концам рассматриваемого интервала. Рассматриваемый метод обеспечивает более быстрое нахождение корня, чем метод половинного деления, при условии задания одинакового рассматриваемого интервала.

Геометрически метод хорд эквивалентен замене кривой хордой, проходящей через точки и (см. рис.1.).

Рис.1. Построение отрезка (хорды) к функции .

Уравнение прямой (хорды), которая проходит через точки А и В имеет следующий вид:

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

Для точки пресечения прямой с осью абсцисс записанное выше уравнение перепишется в следующем виде:

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

или .

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

Рис.2. Пояснение к определению погрешности расчета.

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

Алгоритм нахождения корня нелинейного уравнения по методу хорд

1. Найти начальный интервал неопределенности одним из методов отделения корней. З адать погрешность расчета (малое положительное число ) и начальный шаг итерации () .

2. Найти точку пересечения хорды с осью абсцисс:

3. Необходимо найти значение функции в точках , и . Далее необходимо проверить два условия:

Если выполняется условие , то искомый корень находится внутри левого отрезка положить, ;

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

В результате находится новый интервал неопределенности, на котором находится искомых корень уравнения:

4. Проверяем приближенное значение корня уравнения на предмет заданной точности, в случае:

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

Если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.

Пример решения уравнений методом хорд

В качестве примера, рассмотрим решение нелинейного уравнения методом хорд. Корень необходимо найти в рассматриваемом диапазоне с точностью .

Вариант решения нелинейного уравнения в программном комплексе MathCAD .

Результаты расчетов, а именно динамика изменения приближенного значения корня, а также погрешности расчета от шага итерации представлены в графической форме (см. рис.1).

Рис.1. Результаты расчета по методу хорд

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

Примечание:

Модификацией данного метода является метод ложного положения (False Position Method ), который отличается от метода секущих только тем, что всякий раз берутся не последние 2 точки, а те точки, которые находятся вокруг корня.

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

Случай №1:

Из первого условия получается, что неподвижной стороной отрезка является – сторона a .

Случай №2:

3. Метод хорд

Пусть дано уравнение f(x) = 0, где f(x) - непрерывная функция, имеющая в интервале (a, b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке .

Идея метода хорд состоит в том, что на достаточно малом промежутке дугу кривой y = f(x) можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай (рис. 1), когда первая и вторая производные имеют одинаковые знаки, т.е. f "(x)f ²(x) > 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

Приближение корня x = x1, для которого y = 0, определяется как

.

Аналогично для хорды, проходящей через точки A1 и B, вычисляется следующее приближение корня

.

В общем случае формула метода хорд имеет вид:

. (2)

Если первая и вторая производные имеют разные знаки, т.е.

f "(x)f "(x) < 0,

то все приближения к корню x* выполняются со стороны правой границы отрезка , как это показано на рис. 2, и вычисляются по формуле:

. (3)

Выбор формулы в каждом конкретном случае зависит от вида функции f(x) и осуществляется по правилу: неподвижной является граница отрезка изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (2) используется в том случае, когда f(b)f "(b) > 0. Если справедливо неравенство f(a)f "(a) > 0, то целесообразно применять формулу (3).

Рис. 1 Рис. 2

Рис. 3 Рис. 4

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

.

Тогда условие завершения вычислений записывается в виде:

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

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

Пусть уравнение (1) имеет корень на отрезке , причем f "(x) и f "(x) непрерывны и сохраняют постоянные знаки на всем интервале .

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной. Для этого выбирается некоторое начальное приближение корня x0 на интервале и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) до пересечения с осью абсцисс (рис. 3). Уравнение касательной в точке C0 имеет вид

Затем проводится касательная через новую точку C1(x1, f(x1)) и определяется точка x2 ее пересечения с осью 0x и т.д. В общем случае формула метода касательных имеет вид:

В результате вычислений получается последовательность приближенных значений x1, x2, ..., xi, ..., каждый последующий член которой ближе к корню x*, чем предыдущий. Итерационный процесс обычно прекращается при выполнении условия (4).

Начальное приближение x0 должно удовлетворять условию:

f(x0) f ¢¢(x0) > 0. (6)

В противном случае сходимость метода Ньютона не гарантируется, так как касательная будет пересекать ось абсцисс в точке, не принадлежащей отрезку . На практике в качестве начального приближения корня x0, обычно выбирается одна из границ интервала , т.е. x0 = a или x0 = b, для которой знак функции совпадает со знаком второй производной.

Метод Ньютона обеспечивает высокую скорость сходимости при решении уравнений, для которых значение модуля производной ½f ¢(x)½вблизи корня достаточно велико, т.е. график функции y = f(x) в окрестности корня имеет большую крутизну. Если кривая y = f(x) в интервале почти горизонтальна, то применять метод касательных не рекомендуется.

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

, (7)

т.е. значение производной достаточно вычислить только один раз в начальной точке. Геометрически это означает, что касательные в точках Ci(xi, f(xi)), где i = 1, 2, ..., заменяется прямыми, параллельными касательной, проведенной к кривой y = f(x) в начальной точке C0(x0, f(x0)), как это показано на рис. 4.

В заключение необходимо отметить, что все изложенное справедливо в том случае, когда начальное приближение x0 выбрано достаточно близким к истинному корню x* уравнения. Однако это не всегда просто осуществимо. Поэтому метод Ньютона часто используется на завершающей стадии решения уравнений после работы какого-либо надежно сходящегося алгоритма, например, метода половинного деления.

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

Чтобы применить этот метод для решения уравнения (1) необходимо преобразовать его к виду . Далее выбирается начальное приближение и вычисляется x1, затем x2 и т.д.:

x1 = j(x0); x2 = j(x1); …; xk = j(xk-1); ...

нелинейный алгебраический уравнение корень

Полученная последовательность сходится к корню при выполнении следующих условий:

1) функция j(x) дифференцируема на интервале .

2) во всех точках этого интервала j¢(x) удовлетворяет неравенству:

0 £ q £ 1. (8)

При таких условиях скорость сходимости является линейной, а итерации следует выполнять до тех пор, пока не станет справедливым условие:

.

Критерий вида

может использоваться только при 0 £ q £ ½. Иначе итерации заканчиваются преждевременно, не обеспечивая заданную точность. Если вычисление q затруднительно, то можно использовать критерий окончания вида

; .

Возможны различные способы преобразования уравнения (1) к виду . Следует выбирать такой, который удовлетворяет условию (8), что порождает сходящийся итерационный процесс, как, например, это показано на рис. 5, 6. В противном случае, в частности, при ½j¢(x)½>1, итерационный процесс расходится и не позволяет получить решение (рис. 7).

Рис. 5

Рис. 6

Рис. 7

Заключение

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

Список использованных источников

1. Алексеев В. Е., Ваулин А.С., Петрова Г. Б. - Вычислительная техника и программирование. Практикум по программированию:Практ.пособие/ -М.: Высш. шк. , 1991. - 400 с.

2. Абрамов С.А., Зима Е.В. - Начала программирования на языке Паскаль. - М.: Наука, 1987. -112 с.

3. Вычислительная техника и программирование: Учеб. для техн. вузов/ А.В. Петров, В.Е. Алексеев, А.С. Ваулин и др. - М.: Высш. шк., 1990 - 479 с.

4. Гусев В.А., Мордкович А.Г. - Математика: Справ. материалы: Кн. для учащихся. - 2-е изд. - М.: Просвещение, 1990. - 416 с.

Точке приближенного решения, т. е. Последовательные приближения (4) строятся по формулам: , (9) где – начальное приближение к точному решению. 4.5 Метод Зейделя на основе линеаризованного уравнения Итерационная формула для построения приближенного решения нелинейного уравнения (2) на основе линеаризованного уравнения (7) имеет вид: 4.6 Метод наискорейшего спуска Методы...

Предыдущая статья: Чему равна скорость света Следующая статья: Гармонические колебания Физика формула частоты колебаний