1 в чем заключается метод хорд. Численные методы решения нелинейных уравнений
Численные методы 1
Решение нелинейных уравнений 1
Постановка задачи 1
Локализация корней 2
Уточнение корней 4
Методы уточнения корней 4
Метод половинного деления 4
Метод хорд 5
Метод Ньютона (метод касательных) 6
Численное интегрирование 7
Постановка задачи 7
Метод прямоугольников 8
Метод трапеций 9
Метод парабол (формула Симпсона) 10
Численные методы
На практике в большинстве случаев найти точное решение возникшей математической задачи не удается. Это происходит потому, что искомое решение обычно не выражается в элементарных или других известных функциях. Поэтому большое значение приобрели численные методы.
Под численными методами подразумеваются методы решения задач, сводящиеся к арифметическим и некоторым логическим действиям над числами. В зависимости от сложности задачи, заданной точности, применяемого метода может потребоваться огромное количество действий, и здесь без быстродействующего компьютера не обойтись.
Решение, полученное численным методом, обычно является приближенным, т. е. содержит некоторую погрешность. Источниками погрешности приближенного решения задачи являются:
погрешность метода решения;
погрешности округлений в действиях над числами.
Погрешность метода вызвана тем, что численным методом обычно решается другая, более простая задача, аппроксимирующая (приближающая) исходную задачу. В ряде случаев численный метод представляет собойбесконечный процесс , которыйв пределе приводит к искомому решению. Процесс, прерванный на некотором шаге, дает приближенное решение.
Погрешность округления зависит от количества арифметических действий, выполняемых в процессе решения задачи. Для решения одной и той же задачи могут применяться различные численные методы. Чувствительность к погрешностям округления существенно зависит от выбранного метода.
Решение нелинейных уравнений Постановка задачи
Решение нелинейных уравнений с одним неизвестным является одной из важных математических задач, возникающих в различных разделах физики, химии, биологии и других областях науки и техники.
В общем случае нелинейное уравнение с одним неизвестным можно записать:
f (x ) = 0 ,
где f (x ) – некоторая непрерывная функция аргументаx .
Всякое число x 0 , при которомf (x 0 ) ≡ 0, называется корнем уравненияf (x ) = 0.
Методы решения нелинейных уравнений делятся на прямые (аналитические, точные) иитерационные . Прямые методы позволяют записать решение в виде некоторого соотношения (формулы). При этом значения корней могут быть вычислены по этой формуле за конечное число арифметических операций. Подобные методы развиты для решения тригонометрических, логарифмических, показательных, а также простейших алгебраических уравнений.
Однако подавляющее большинство нелинейных уравнений, встречающихся на практике, не удается решить прямыми методами. Даже для алгебраического уравнения выше четвертой степени не удается получить аналитического решения в виде формулы с конечным числом арифметических действий. Во всех таких случаях приходится обращаться к численным методам, позволяющим получить приближенные значения корней с любой заданной точностью.
При численном подходе задача о решении нелинейных уравнений разбивается на два этапа: локализация (отделение) корней, т.е. нахождение таких отрезков на осиx , в пределах которых содержится один единственный корень, иуточнение корней , т.е. вычисление приближенных значений корней с заданной точностью.
Локализация корней
Для отделения корней уравнения f (x ) = 0 необходимо иметь критерий, позволяющий убедится, что, во-первых, на рассматриваемом отрезке [a ,b ] имеется корень, а, во-вторых, что этот корень единственный на указанном отрезке.
Если функция f (x ) непрерывна на отрезке [a ,b ], а на концах отрезка её значения имеют разные знаки, т. е.
f (a ) f (b ) < 0 ,
то на этом отрезке расположен, по крайней мере, один корень.
Рис 1. Отделение корней. Функция f (x ) не монотонна на отрезке [a ,b ].
Это условие, как видно из рисунка (1), не обеспечивает единственности корня. Достаточным дополнительным условием, обеспечивающем единственность корня на отрезке [a ,b ] является требование монотонности функции на этом отрезке. В качестве признака монотонности функции можно воспользоваться условием постоянства знака первой производнойf ′(x ) .
Таким образом, если на отрезке [ a ,b ] функция непрерывна и монотонна, а ее значения на концах отрезка имеют разные знаки, то на рассматриваемом отрезке существует один и только один корень.
Воспользовавшись этим критерием, можно отделить корни аналитическим способом, находя интервалы монотонности функции.
Отделение корней можно выполнить графически , если удается построить график функцииy =f (x ) . Например, график функции на рисунке (1) показывает, что эта функция на интервале может быть разбита на три интервала монотонности и на этом интервале у нее существуют три корня.
Отделение корней можно также выполнить табличным способом. Допустим, что все интересующие нас корни уравнения (2.1) находятся на отрезке [A, B ]. Выбор этого отрезка (интервала поиска корней) может быть сделан, например, на основе анализа конкретной физической или иной задачи.
Рис. 2. Табличный способ локализации корней.
Будем вычислять значения f (x ) , начиная с точкиx =A , двигаясь вправо с некоторым шагомh (рис. 2). Как только обнаруживается пара соседних значенийf (x ) , имеющих разные знаки, так соответствующие значения аргументаx можно считать границами отрезка, содержащего корень.
Надежность табличного способа отделения корней уравнений зависит как от характера функции f (x ) , так и от выбранной величины шагаh . Действительно, если при достаточно малом значенииh (h <<|B −A |) на границах текущего отрезка [x, x +h ] функцияf (x ) принимает значения одного знака, то естественно ожидать, что уравнениеf (x ) = 0 корней на этом отрезке не имеет. Однако, это не всегда так: при несоблюдении условия монотонности функцииf (x ) на отрезке [x, x +h ] могут оказаться корни уравнения (рис. 3а).
Рис 3а Рис 3б
Также несколько корней на отрезке [x, x +h ] могут оказаться и при выполнении условияf (x ) f (x + h ) < 0 (рис. 3б). Предвидя подобные ситуации, следует выбирать достаточно малые значенияh .
Отделяя таким образом корни, мы, по сути, получаем их приближенные значения с точностью до выбранного шага. Так, например, если в качестве приближенного значения корня взять середину отрезка локализации, то абсолютная погрешность этого значения не будет превосходить половины шага поиска (h /2). Уменьшая шаг в окрестности каждого корня, можно, в принципе, повысить точность отделения корней до любого наперед заданного значения. Однако такой способ требует большого объема вычислений. Поэтому при проведении численных экспериментов с варьированием параметров задачи, когда приходится многократно осуществлять поиск корней, подобный метод не годится для уточнения корней и используется только для отделения (локализации) корней, т.е. определения начальных приближений к ним. Уточнение корней проводится с помощью других, более экономичных методов.
Пусть на отрезке функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f "(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).
Рис. 1.
Алгоритм приближенного вычисления корня методом хорд.
Исходные данные: f (x) - функция; е - требуемая точность; x 0 - начальное приближение.
Результат: xпр - приближенный корень уравнения f (x) = 0.
Метод решения:
Рис. 2. f "(x) f ""(x)>0 .
Рассмотрим случай, когда f "(x) и f ""(x) имеют одинаковые знаки (рис. 2).
График функции проходит через точки A 0 (a,f(a)) и B 0 (b,f(b)) . Искомый корень уравнения (точка x* ) нам неизвестен, вместо него возьмет точку х 1 пересечения хорды А 0 В 0 с осью абсцисс. Это и будет приближенное значение корня.
В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2) : .
Тогда уравнение хорды А 0 В 0 запишется в виде: .
Найдем значение х = х 1 , для которого у = 0 : . Теперь корень находится на отрезке . Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A 1 (x 1 ,f(x 1 )) и B 0 (b,f(b)) , и найдем х 2 - точку пересечения хорды А 1 В 0 с осью Ох : x 2 =x 1 .
Продолжая этот процесс, находим
x 3 =x 2 .
Получаем рекуррентную формулу вычисления приближений к корню
x n+1 =x n .
В этом случае конец b отрезка остается неподвижным, а конец a перемещается.
Таким образом, получаем расчетные формулы метода хорд:
x n+1 =x n ; x 0 =a . (4)
Вычисления очередных приближений к точному корню уравнения продолжается до тех пор, пока не достигнем заданной точности, т.е. должно выполняться условие: |x n+1 -x n |< , где - заданная точность.
Теперь рассмотрим случай, когда первая и вторая производные имеют разные знаки, т.е. f "(x) f ""(x)<0 . (рис. 3).
Рис. 3. Геометрическая интерпретация метода хорд для случая f "(x) f ""(x)<0 .
Соединим точки A 0 (a,f(a)) и B 0 (b,f(b)) хордой А 0 В 0 . Точку пересечения хорды с осью Ох будем считать первым приближение корня. В этом случае неподвижным концом отрезка будет являться конец а .
Уравнение хорды А 0 В 0 :. Отсюда найдем x 1 , полагая y = 0 : x 1 =b . Теперь корень уравнения x . Применяя метод хорд к этому отрезку, получим x 2 =x 1 . Продолжая и т.д., получим x n+1 =x n .
Расчетные формулы метода:
x n+1 =x n , x 0 =0 . (5)
Условие окончания вычислений: |x n+1 -x n |< . Тогда хпр = xn+1 с точностью Итак, если f "(x) f ""(x)>0 приближенное значение корня находят по формуле (4), если f "(x) f ""(x)<0 , то по формуле (5).
Практический выбор той или иной формулы осуществляется, пользуясь следующим правилом: неподвижным концом отрезка является тот, для которого знак функции совпадает со знаком второй производной.
Пример. Проиллюстрировать действие этого правила на уравнении
(x-1)ln(x)-1=0 , если отрезок изоляции корня .
Решение. Здесь f(x)=(x-1)ln(x)-1 .
f "(x)=ln(x)+;
f ""(x)= .
Вторая производная в этом примере положительна на отрезке изоляции корня : f ""(x)>0 , f(3) >0, т.е. f(b) f""(x)>0 . Таким образом, при решении данного уравнения методом хорд для уточнения корня выбираем формулы (4).
var e,c,a,b,y,ya,yb,yn,x,x1,x2,xn,f1,f2:real;
begin e:=0.0001;
writeln("vvedi nachalo otrezka");
writeln("vvedi konec otrezka");
y:=((x-1)*ln(x))-1;
y:=((x-1)*ln(x))-1;
yb:=y; c:=(a+b)/2; x:=c;
y:=((x-1)*ln(x))-1;
f1:=ln(x) + (x-1)/x ;
f2:= 1/x + 1/(x*x);
if (ya*yb < 0) and (f1*f2 > 0)
then begin x1:=a; while abs(x2 - x) > e do
x2:=x1 - (yn*(b-x1))/(yb - yn);
writeln("koren uravneniya xn = ", x2)
end elsebegin x1:=b;
while abs(x2 - x) > e do
begin x:=x1; y:=((x-1)*ln(x))-1; yn:=y;
x2:=x1 - (yn*(x1- a))/(yn - ya);
writeln("koren uravneniya xn = ", x2);
Метод простых итераций
Рассмотрим уравнение f(x)=0 (1) с отделенным корнем X . Для решения уравнения (1) методом простой итерации приведем его к равносильному виду: x=ц(x). (2)
Это всегда можно сделать, причем многими способами. Например:
x=g(x) · f(x) + x ? ц(x) , где g(x ) - произвольная непрерывная функция, не имеющая корней на отрезке .
Пусть x (0) - полученное каким-либо способом приближение к корню x (в простейшем случае x (0) =(a+b)/2). Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:
x (k+1) =ц(x (k) ), k=0, 1, 2, ... (3)
начиная с приближения x (0) .
УТВЕРЖДЕНИЕ: 1 Если последовательность {x (k) } метода простой итерации сходится и функция ц непрерывна, то предел последовательности является корнем уравнения x=ц(x)
ДОКАЗАТЕЛЬСТВО: Пусть. (4)
Перейдем к пределу в равенстве x (k+1) =ц(x (k) ) Получим с одной стороны по (4), что а с другой стороны в силу непрерывности функции ц и (4) .
В результате получаем x * =ц(x * ). Следовательно, x * - корень уравнения (2), т.е. X=x * .
Чтобы пользоваться этим утверждением нужна сходимость последовательности {x (k) }. Достаточное условие сходимости дает:
ТЕОРЕМА 1: (о сходимости) Пусть уравнение x=ц(x) имеет единственный корень на отрезке и выполнены условия:
- 1) ц(x) C 1 ;
- 2) ц(x) " x ;
- 3) существует константа q > 0: | ц "(x) | ? q . Tогда итерационная последовательность {x (k) }, заданная формулой x (k+1) = ц(x (k) ), k=0, 1, ... сходится при любом начальном приближении x (0) .
ДОКАЗАТЕЛЬСТВО: Рассмотрим два соседних члена последовательности {x (k) }: x (k) = ц(x (k-1) ) и x (k+1) = ц(x (k) ) Tак как по условию 2) x (k) и x (k+1) лежат внутри отрезка , то используя теорему Лагранжа о средних значениях получаем:
x (k+1) - x (k) = ц(x (k) ) - ц(x (k-1) ) = ц "(c k )(x (k) - x (k-1) ), где c k (x (k-1) , x (k) ).
Отсюда получаем:
| x (k+1) - x (k) | = | ц "(c k ) | · | x (k) - x (k-1) | ? q | x (k) - x (k-1) | ?
? q (q | x (k-1) - x (k-2) |) = q 2 | x (k-1) - x (k-2) | ? ... ? q k | x (1) - x (0) |. (5)
Рассмотрим ряд
S ? = x (0) + (x (1) - x (0) ) + ... + (x (k+1) - x (k) ) + ... . (6)
Если мы докажем, что этот ряд сходится, то значит сходится и последовательность его частичных сумм
S k = x (0) + (x (1) - x (0) ) + ... + (x (k) - x (k-1) ).
Но нетрудно вычислить, что
S k = x (k)) . (7)
Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x (k) }.
Для доказательства сходимости pяда (6) сравним его почленно (без первого слагаемого x (0) ) с рядом
q 0 | x (1) - x (0) | + q 1 |x (1) - x (0) | + ... + |x (1) - x (0) | + ..., (8)
который сходится как бесконечно убывающая геометрическая прогрессия (так как по условию q < 1 ). В силу неравенства (5) абсолютные величины ряда (6) не превосходят соответствующих членов сходящегося ряда (8) (то есть ряд (8) мажорирует ряд (6). Следовательно ряд (6) также сходится. Tем самым сходится последовательность {x (0) }.
Получим формулу, дающую способ оценки погрешности |X - x (k+1) |
метода простой итерации.
X - x (k+1) = X - S k+1 = S ? - S k+1 = (x (k+2) - (k+1) ) + (x (k+3) - x (k+2) ) + ... .
Следовательно
|X - x (k+1) | ? |x (k+2) - (k+1) | + |x (k+3) - x (k+2) | + ... ? q k+1 |x (1) - x (0) | + q k+2 |x (1) - x (0) | + ... = q k+1 |x (1) - x (0) | / (1-q).
В результате получаем формулу
|X - x (k+1) | ? q k+1 |x (1) - x (0) | / (1-q). (9)
Взяв за x (0) значение x (k) , за x (1) - значение x (k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство q k+1 ? q выводим:
|X - x (k+1) | ? q k+1 |x (k+1) - x (k) | / (1-q) ? q|x (k+1) - x (k) | / (1-q).
Итак, окончательно получаем:
|X - x (k+1) | ? q|x (k+1) - x (k) | / (1-q). (10)
Используем эту формулу для вывода критерия окончания итерационной последовательности. Пусть уравнение x=ц(x) решается методом простой итерации, причем ответ должен быть найден с точностью е, то есть
|X - x (k+1) | ? е.
С учетом (10) получаем, что точность е будет достигнута, если выполнено неравенство
|x (k+1) -x (k) | ? (1-q)/q. (11)
Таким образом, для нахождения корней уравнения x=ц(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа е(1-q)/q.
ЗАМЕЧАНИЕ 1: В качестве константы q обычно берут оценку сверху для величины
Геометрическая интерпретация
Рассмотрим график функции. Это означает, что решение уравнения и - это точка пересечения с прямой:
Рисунок 1.
И следующая итерация - это координата x пересечения горизонтальной прямой точки с прямой.
Рисунок 2.
Из рисунка наглядно видно требование сходимости. Чем ближе производная к 0, тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если, то каждое следующее приближение строится с другой стороны от корня:
Рисунок 3.
Заключение
Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов - сред и языков программирования.
Итогом работы можно считать созданную функциональную модель нахождения корней уравнения методами простой итерации, Ньютона, хорд и половинного деления. Данная модель применима к детерминированным задачам, т.е. погрешностью экспериментального вычисления которых можно пренебречь. Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.
Проведя исследования по теме курсовой работы "Численные методы. Решение нелинейных уравнений", я добилась поставленных во введении целей. Были подробно рассмотрены методы уточнения корней. К каждому определению и теореме были приведены несколько примеров. Все теоремы доказаны.
Использование различных источников дало возможность полностью раскрыть тему.
Назначение сервиса . Сервис предназначен для нахождения корней уравнений f(x) в онлайн режиме методом хорд.Инструкция . Введите выражение F(x) , нажмите Далее. Полученное решение сохраняется в файле Word . Также создается шаблон решения в Excel . Ниже представлена видеоинструкция.
Правила ввода функции
Примеры≡ 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)≥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
. (3.11)
Имеем
(3.12)
(то есть значение функции y(x) в точке x n на хорде совпадает с f(ξ)).
Так как , то из (3.12) следует
или
. (3.13)
Для рис. 1а , следовательно
или
значит что и т.д. (см. (3.11)).
Для рис 2а . Следовательно, из (3.12) получим
значит
так как ч.т.д.
Аналогичное доказательство для рис.1б и рис.2б. Таким образом, мы доказали, что последовательность чисел является сходящейся.
a≤x 0
Сходимость метода хорд линейная с коэффициентом .
, (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.