Решение нелинейных уравнений
xn и возвратиться к началу шага 2. 2 Шаг 3. При выполнении условия останова работа алгоритма прекращается с x* xn 1 ; иначе переходим к шагу 1 с n n 1 . Метод Ньютона правильно определяет направление убывания функции, но продвижение в этом направлении корректируется с помощью деления xn ) f ( xn ) в отрезка пополам, если не выполняется условие релаксации f (
шаге 2 (рисунок 10). Рисунок 10. Один шаг гибридного метода Ньютона–половинного деления На рисунке 11 приведена блок-схема рассмотренного гибридного алгоритма. 12 Рисунок 11. Блок-схема гибридного метода Ньютона–половинного деления Метод простой итерации5 Пусть дано уравнение f ( x) 0 и отрезок a; b , функция f(x) удовлетворяет условиям: 1) f(x) – дифференцируема на a; b ; 2) f (a ) f (b) 0 , т. е. f(x) имеет разные знаки на концах отрезка; 3) f ( x ) 0 на a; b . Заменим f ( x) 0 равносильным ему уравнением x (x ) . Выбирая произвольное значение x0 a; b, вычислим x1 ( x0 ) , x2 ( x1 ) , x3 ( x2 ) , … и т. д. xn 1 ( xn ) , n 0, 1, Слово «простой» означает, что для вычисления следующего приближения необходимо знать только одно предыдущее приближение. 5 13 Геометрически процесс итерации – нахождение абсциссы точки пересечения кривой y (x) и прямой y x (рисунок 12). На рисунке 13 приведен пример циклического итерационного процесса. Рисунок 12. Графическая иллюстрация метода простой итерации: а – односторонний сходящийся процесс; б – односторонний расходящийся процесс; в – двухсторонний сходящийся процесс; г – двухсторонний расходящийся процесс Процесс сходится к корню, если выполнены следующие условия теоремы о сходимости (достаточное условие сходимости). Теорема 4. Пусть функция (x ) определена и дифференцируема на a; b , причем все ее значения ( x) a; b. Тогда, если существует правильная дробь q, такая что ( x) q 1 при x a; b , 14 то процесс итерации сходится независимо от начального приближения x0 a; b и предельное значение x * lim xn является единственным корнем уравнения x (x ) на a; b . n Рисунок 13. Графическая иллюстрация метода простой итерации: циклический итерационный процесс а – цикл периода 2; б – цикл периода 4 На рисунке 14 представлена блок-схема решения нелинейного уравнения методом простой итерации [3]. Здесь c – начальное приближение; предполагается, что итерационный процесс сходится или, если в этом нет уверенности, необходимо ограничить число итераций, введя для них счетчик. Рисунок 14. Блок-схема метода простой итерации Рассмотрим один из способов равносильного приведения f ( x) 0 к виду x (x ) . Построим функцию ( x) f ( x) x , 1 0 , если f ( x ) 0 ; r 15 1 0 , если f ( x ) 0 , r r max f (a ) , f (b) . Тогда процесс итерации xn 1 ( xn ) , n 0, 1, сходится к корню x * при любом x0 a; b. Скорость сходимости оценивается как6 m n x * xn q , 1 q m x0 ( x0 ) q r 1 или q max ( x ) , x a; b. Примером условия окончания может быть xn xn 1 или 1 q xn xn 1 , q где – требуемая точность. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Вержбицкий, В. М. Основы численных методов: Учебник для вузов / В. М. Вержбицкий. – М.: Высш. шк., 2002. – 840 с. 2. Мудров А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. – Томск: МП «Раско», 1991. – 272 с. 3. Турчак Л. И. Основы численных методов: Учеб. пособие. – М.: Наука. Гл. ред. физ.-мат. лит., 1987. – 320 с. 4. Волков Е. А. Численные методы: Учеб. пособие для вузов. – М.: Наука., 1987. – 248 с. 5. Калиткин Н. Н. Численные методы. – М.: Наука, 1978. – 512 с. 6. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислительные методы высшей математики. Т. 1. – Мн., «Вышэйш. школа», 1972. – 584 с. 7. Самарский А. А. Введение в численные методы. – М.: Наука. – 1997. – 286 с. 8. Бедарев И. А. Методы вычислений: учеб. пособие / И. А. Бедарев, Ю. В. Кратова, Н. Н. Федорова; Новосиб. гос. архитектур.-строит. ун-т (Сибстрин). – 2-е изд., перераб. и доп. – Новосибирск : НГАСУ (Сибстрин), 2009. – 116 с. 6 Метод простой итерации сходится со скоростью геометрической прогрессии. 16
Численные методы решения нелинейных уравнений
где f(x) — заданная алгебраическая или трансцендентная функция.
Решить уравнение — значит найти все его корни, то есть те значения x , которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня xПP , которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε , то есть
Величину ε также называют допустимой ошибкой , которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:
- Отделение корней, то есть нахождение интервалов из области определения функции f(x) , в каждом из которых содержится только один корень уравнения f(x)=0 .
- Уточнение корней до заданной точности.
Отделение корней
Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x) . Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.
Для примера рассмотрим задачу решения уравнения
где угол x задан в градусах. Указанное уравнение можно переписать в виде
Для графического отсечения корней достаточно построить график функции
Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8) .
Аналитическое отделение корней
Аналитическое отделение корней основано на следующих теоремах.
Теорема 1 . Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е.
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2 . Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0 .
Уточнение корней
Для уточнения корней может использоваться один из следующих методов:
Метод последовательных приближений (метод итераций)
Метод итерации — численный метод решения математических задач, используемый для приближённого решения алгебраических уравнений и систем. Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить решение с заданной точностью в виде предела последовательности итераций. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения решения.
Функциональное уравнение может быть записано в виде
Функцию f(x) называют сжимающим отображением .
Последовательность чисел x0, x1 ,…, xn называется итерационной , если для любого номера n>0 элемент xn выражается через элемент xn-1 по рекуррентной формуле
а в качестве x0 взято любое число из области задания функции f(x) .
Реализация на C++ для рассмотренного выше примера
Уравнение может быть записано в форме
Результат выполнения
Метод Ньютона (метод касательных)
Если известно начальное приближение x0 корня уравнения f(x)=0, то последовательные приближения находят по формуле
Графическая интерпретация метода касательных имеет вид
Реализация на C++
Для заданного уравнения
производная будет иметь вид
Результат выполнения
Метод секущих (метод хорд)
Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие
то последующие приближения находят по формуле
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(x) = 0 производят по формулам:
Геометрическая интерпретация метода хорд:
Реализация на C++
В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается искомый корень.
Результат выполнения
Метод половинного деления (метод дихотомии)
Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие
то последующие приближения находятся по формуле
и вычисляется f(xi) . Если f(xi)=0 , то корень найден. В противном случае из отрезков выбирается тот, на концах которого f(x) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.
Геометрическая интерпретация метода дихотомии
Реализация на C++
Результат выполнения
Для численного поиска решения также можно использовать генетические алгоритмы.
Решение нелинейных уравнений
При решении нелинейных уравнений невозможно выразить переменную. В этих случаях целесообразно применить ряд численных методов нахождения корней уравнения. Ниже рассмотрены некоторые из них.
Любое уравнение можно представить в виде f (x) = 0 , перенеся всё в одну сторону, тогда поиск корней уравнения сводится к поиску точек пересечения функции f (x) с осью абсцисс. Для более удобной реализации методов в языке Паскаль целесообразно сразу описать функцию f (x) как подпрограмму:
function F(x:real):real;
begin
F:= . ;
end;
Существует ряд методов численного решения нелинейных уравнений, целесообразность применения каждого из которых определяется видом уравнения, его порядком, требуемой точностью и т. д. Эти методы подробно рассмотрены в [1,2,5].
Метод отделения корней
Итак, дано уравнение ƒ(x) = 0, где ƒ(x) – непрерывная функция. Поиск корней уравнения сводится к поиску точек пересечения функции ƒ(x ) с осью абсцисс. Все рассматриваемые ниже методы подразумевают, что уже найден отрезок [a,b], в котором существует один корень уравнения. В зависимости от вида функции таких отрезков может быть несколько, а для периодических функций – бесконечное множество. Метод отделения корней осуществляет поиск таких отрезков.
Наиболее наглядным является графический способ отделения корней. Для реализации этого метода необходимо построить график функции. Это будет легко сделать, если составить программу, которая будет выдавать таблицу значений функции при меняющемся с некоторым шагом h аргументе x (см. рис. 1).
Если есть такая таблица значений функции, то график функции можно и не строить. Достаточно найти две строчки, где значение функции меняет знак на противоположный. Такой способ называется табличным методом отделения корней (см. пример).
Рис. 1. Графическая интерпретация метода отделения корней
Пример. 4.1. Реализация табличного метода отделения корней.
Здесь x пробегает значения от xn до xk с шагом h и при этом на экран выводятся значения x и f(x). Отрезок [xn, xk] и шаг h нужно подбирать для каждой функции, исходя из её характера. Шаг должен быть меньше, чем расстояние между корнями уравнения, чтобы исключить попадание в шаг двух корней.
program tablica;
var xn,xk,x,h:real;
function F(x:real):real;
begin F:=sqrt(x)+2*sqr(x)+3*x; end;
begin
write(‘Введите начало интервала > ’); readln(xn);
write(‘Введите конец интервала > ’); readln(xk);
write(‘Введите шаг > ’); readln ( h );
x:=xn;
while x<xk do
begin
writeln(‘x=’,x,‘ f(x)=’,f(x));
x:=x+h;
end;
end.
Процесс выбора отрезка [a,b], содержащего корень, можно автоматизировать. Для этого нужно, начиная с какого-то начального значения, смещать отрезок длиной h в цикле и каждый раз анализировать значения функции на концах этого отрезка. Корень присутствует, если эти значения разного знака. Можно использовать сложное условие
(f(a)>0 AND f(b)<0) OR (f(a)<0 AND f(b)>0),
а можно просто найти произведение и проверить его знак. Корень присутствует, если f(a)*f(b)<0 . После этого можно уточнять значение корня, а можно перейти к поиску следующего отрезка, задав начало поиска от конца найденного.
Пример. 4.2. Поиск ближайшего отрезка, содержащего корень.
program poisk;
var a,b,h:real;
function F(x:real):real;
begin F:=sqrt(x)+2*sqr(x)+3*x; end;
begin
write(‘Введите начало поиска > ’); readln(b);
write(‘Введите шаг > ’); readln ( h );
repeat
a:=b;
b:=a+h;
until f(a)*f(b)<0;
writeln(‘a=’,a,‘ b=’,b);
end.
Метод половинного деления
Пусть дано уравнение ƒ(x) = 0, где ƒ ( x ) – непрерывная функция, корень Р отделен на отрезке [a,b], т. е. ƒ(a) × ƒ(b) > 0, причем | b – a | < E. Требуется найти значение корня Р с точностью до Е (см. рис. 2).
Если корень Р не отделен на заданном отрезке, т. е. ƒ (a) и ƒ (b) одного знака и, следовательно, ƒ (a) × ƒ b) > 0, то вычисляются значения функции в точках, расположенных через равные интервалы на оси Х. Когда ƒ (an) и ƒ (bn) имеют противоположные знаки, то значения a = an и b=bn принимаются в качестве начальных и находят середину отрезка [a,b], т. е. с=(a+b)/2. Тогда отрезок [a,b] точкой с разделится на два равных отрезка [a,c] и [c,b], длина которых равна (b–a)/2. Из двух этих образовавшихся отрезков выбирается тот, на концах которого функция ƒ (x) принимает значения противоположных знаков; обозначим его [a1,b1]. Затем отрезок [a1,b1] делим пополам и проводим те же действия. Получим отрезок [a2,b2], длина которого равна (b–a)/2 2 . Процесс деления отрезка пополам производится до тех пор, когда на каком-то k-м этапе будет получен отрезок [ak,bk], такой, что
bk – ak = (b – a)/2 k ≤ E и ak ≤ P ≤ bk ,
где число k указывает на количество проведенных делений. Числа ak и bk – корни уравнения ƒ (x) = 0 с точностью до E. За приближенное значение корня следует взять Р=(ak+bk)/2, причем погрешность не превысит (b–a)/2 k+ 1 .
Рис. 2. Графическая интерпретация метода половинного деления
Отметим, что в качестве условия прекращения счета более целесообразно пользоваться условием E ≤ I bk – ak I .
Блок-схема алгоритма представлена на рис. 3.
Рассмотренный метод имеет относительно малую скорость сходимости, но отличается от других методов простотой реализации алгоритма, не требующего вычисления производных заданной функции.
На блок-схеме видно два цикла. Первый реализует поиск отрезка [a,b] длиной h, на котором есть корень уравнения. Второй цикл уменьшает этот отрезок методом половинного деления до тех пор, пока его длина не станет меньше заданной погрешности е. Удобнее всего для организации циклов применить оператор repeat … until. Внутри второго цикла размещён условный оператор, который проверяет, с какой стороны нужно уменьшить отрезок [a,b].
Рис. 3. Блок-схема алгоритма метода половинного деления
Метод касательных
Расчетная формула метода касательных (или метод Ньютона-Рафсона) получается из разложения функции ƒ(x) = 0 в ряд Тейлора в окрестности точки xn. При ограничении разложения двумя членами ряда получим
Здесь O (от английского order) означает порядок остаточного члена в разложении, который в дальнейшем считается малым.
Обычно окончательная формула записывается в виде
Таким образом, зная какое-либо предыдущее приближение xn, где n – номер приближения или итерации (n ≥ 0), можно определить последующее приближенное значение корня xn+1. Если заданное (xn) и расчетное (xn+1) значения совпадают с точностью ε, т. е.
то значение xn+1 считается приближенным значением корня уравнения ƒ (x) = 0.
Кроме предыдущего условия окончания счета, можно использовать условие малости функций ƒ (x) около корня, т. е. | ƒ (xn)| ≤ εf или | ƒ (xn+1) | ≤ εf , где εf – заданная погрешность.
Рассмотрим геометрическое толкование метода касательных (см. рис. 4), где значение корня Р определяется следующим образом.
Рис. 4. Графическая интерпретация метода касательных
Исходя из некоторого начального приближения xn, находим соответствующее ему значение ƒ (xn) (точка А), проводим касательную к кривой ƒ (x) через точку А и ищем точку пересечения этой касательной с осью Х. Эта точка будет значением xn+1, т. к. требовалось провести через точку с координатами xn, ¦(xn) прямую с угловым коэффициентом ƒ ‘(xn) и затем найти её пересечение с осью Х.
Величина отрезка (xn – xn+1) больше заданной погрешности e, поэтому поиск значения корня продолжается аналогично. Принимая последнее найденное значение xn+1 за исходное, определяем следующее значение xn+2 по той же формуле
далее опять проверяется условие
Повторение поиска следующей точки продолжается до тех пор, пока не выполнится условие окончания поиска приближенного значения корня.
Для составления программ можно руководствоваться блок-схемой, представленной на рис. 5.
Рис. 4.5. Блок-схема алгоритма метода касательных
Наличие в блок-схеме вывода f(x1) означает дополнительную проверку правильности определения корня, т. к. в этом случае значение функции должно быть близко к нулю.
Замечание. При реализации этого метода целесообразно функцию ¦(x) и её производную ¦ ‘ (x) описать как подпрограммы:
function F(x:real):real;
begin F:= . ; end;
function F1(x:real):real;
begin F1:= . ; end;
При этом функция должна быть предварительно продифференцирована вручную.
Основной цикл удобнее всего организовать при помощи оператора repeat … until.
Метод касательных обладает относительно большой скоростью сходимости при выполнении следующих условий:
- Начальное приближение x0 выбрано достаточно близко к корню уравнения ƒ (x) = 0.
- Вторая производная ƒ «(x) не принимает больших значений.
- Первая производная ƒ ‘ (x) не слишком близка к нулю.
Важно помнить, что успешность поиска корня напрямую зависит от того, насколько близко к корню выбрано начальное приближение. Поэтому иногда целесообразно вначале провести поиск отрезка, содержащего корень, методом отделения корней, как это было сделано перед реализацией метода половинного деления. Подбирая необходимый шаг, можно легко найти такой отрезок. Тогда в качестве первого приближения можно взять любой из его концов или середину этого отрезка.
Модифицированный метод Ньютона
Модифицированный метод Ньютона лишь немного отличается от метода касательных и обладает меньшей скоростью сходимости. Здесь значение производной вычисляется всего один раз в точке первого приближения и больше не изменяется. Следовательно, её вычисление будет стоять до оператора цикла. Общая формула вычисления последующего приближения будет выглядеть так:
Решение нелинейных уравнений
Уравнения, в которых содержатся неизвестные функции, произведенные в степень больше единицы, называются нелинейными.
Например, 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.
, где 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