Численные методы метод хорд. Численные методы
Рассматриваемый
метод так же, как и метод половинного
деления, предназначен для уточнения
корня на интервале
принимает значения разных знаков.
Очередное приближение в отличие от
метода половинного деления берем не в
середине отрезка, а в точке
,
где пересекает ось абсцисс прямая линия
(хорда), проведенная через точкиА
иВ
(рис. 2.6).
Запишем уравнение прямой, проходящей через точки А иВ :
.
Для
точки пересечения прямой с осью абсцисс
(
)
получим уравнение
. (2.13)
В
качестве нового интервала для продолжения
итерационного процесса выбираем тот
из двух
и
,
на концах которого функция
принимает значения разных знаков. Для
рассматриваемого случая (рис. 2.6) выбираем
отрезок
,
так как
.
Следующая итерация состоит в определении
нового приближения
как точки пересечения хорды
с осью абсцисс и т.д.
Заканчиваем процесс уточнения корня, когда расстояние между очередными приближениями станет меньше заданной точности, т.е.
(2.14)
или при выполнении условия (2.12).
ØЗамечание. Метод
половинного деления и метод хорд очень
похожи, в частности, процедурой проверки
знаков функции на концах отрезка. При
этом второй их них в ряде случаев дает
более быструю сходимость итерационного
процесса. Однако в некоторых случаях
метод хорд может сходится существенно
медленнее метода половинного деления.
Такая ситуация показана на рис. 2.7. Оба
рассмотренных метода не требуют знания
дополнительной информации о функции
.
Например, не требуется, чтобы функция
была дифференцируема. Даже для разрывных
функций рассмотренные методы обладают
гарантированной сходимостью. Более
сложные методы уточнения корня используют
дополнительную информацию о функции
,
прежде всего свойство дифференцируемости.
Как результат они обычно обладают более
быстрой сходимостью, но в то же время,
применимы для более узкого класса
функций, и их сходимость не всегда
гарантирована. Примером такого метода
служит метод Ньютона.<
Метод Ньютона (метод касательных)
Пусть
нам известно начальное приближение к
корню
(вопрос выбора начального приближение
будет подробно рассмотрен ниже). Проведем
в этой точке касательную к кривой
(рис. 2.8). Эта касательная пересечет ось
абсцисс в точке
,
которую будем рассматривать в качестве
следующего приближения. Значение
легко найти из рисунка:
,
выражая отсюда , получим
.
Аналогично могут быть найдены и следующие приближения. Формула для k +1-го приближения имеет вид
,
(2.15)
Из
формулы (2.15) вытекает условие применимости
метода: функция
должна быть дифференцируемой и
в окрестности корня не должна менять
знак.
Для окончания итерационного процесса могут быть использованы условия (2.12) или (2.14).
ØЗамечание 1. В
методе Ньютона, в отличие от предыдущих
методов, не обязательно задавать отрезок
,
содержащий корень уравнения, а достаточно
найти некоторое начальное приближение
корня
.<
ØЗамечание 2.
Формула метода Ньютона может быть
получена и из других соображений.
Зададимся некоторым начальным приближением
корня
.
Заменим функциюf
(x
)
в окрестности точки
отрезком ряда Тейлора:
и
вместо нелинейного уравнения
решим линеаризованное уравнение
рассматривая его решение как следующее (первое) приближение к искомому значению корня. Решение этого уравнение очевидно:
Повторяя это процесс приходим к формуле Ньютона (2.15).<
Сходимость
метода Ньютона
. Выясним основные
условия сходимости последовательности
значений
,
вычисляемых по формуле (2.15), к корню
уравнения (2.1). Предполагая, что
дважды непрерывно дифференцируема,
разложим
в ряд Тейлора в окрестностиk
-го
приближения
Разделив
последнее соотношение на
и перенеся часть слагаемых из левой
части в правую, получим:
.
Учитывая,
что выражение в квадратных скобках
согласно (2.15) равно
,
переписываем это соотношение в виде
.
. (2.16)
Из (2.16) следует оценка
, (2.17)
где
,
.
Очевидно, что ошибка убывает, если
. (2.18)
Полученное условие означает, что сходимость зависит от выбора начального приближения.
Оценка (2.17) характеризует скорость убывания погрешности для метода Ньютона: на каждом шаге погрешность пропорциональна квадрату погрешности на предыдущем шаге. Следовательно, метод Ньютона обладает квадратичной сходимостью.
Выбор начального приближения в методе Ньютона. Как следует из условия (2.18) сходимость итерационной последовательности, получаемой в методе Ньютона, зависит от выбора начального приближения . Это можно заметить и из геометрической интерпретации метода. Так, если в качестве начального приближения взять точку (рис. 2.9), то на сходимость итерационного процесса рассчитывать не приходится.
Если же в качестве начального приближения выбрать точку , то получим сходящуюся последовательность.
В
общем случае, если задан отрезок
,
содержащий корень, и известно, что
функция
монотонна на этом отрезке, то в качестве
начального приближения
можно выбрать ту границу отрезка
,
где совпадают знаки функции
и второй производной
.
Такой выбор начального приближения
гарантирует сходимость метода Ньютона
при условии монотонности функции на
отрезке локализации корня.
Пусть на отрезке функция непрерывна, принимает на концах отрезка значение разных знаков, а производная 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) заменяется хордой и абсцисса точки пересечения хорды с осью Ox является приближенным значением корня.
Рисунок 2 – Геометрическая интерпретация метода Ньютона.
Пусть для определенности f" (х)> 0, f"" (x) >0, f (а) <0, f (b)> 0 (рис. 3, а). Возьмем за начальное приближение искомого корня х* значения х 0 =а. Через точки а 0 и В проведем хорду и за первое приближение корня х* возьмем абсциссу x 1 точки пересечения хорды с осью ОХ. Теперь приближенное значение х 1 корня можно уточнить если применить метод хорд на отрезке [х 1 ; b ]. Абсцисса х 2 точки пересечения хордыА 1 В будет другим приближением корня. Продолжая данный процесс далее, получим последовательность х 0 , х 1 , х 2 ,..., х k , ... приближенных значений корня х* данного уравнения.
Таким образом метод хорд можно записать так:
, k=0, 1.2, …, (8)
В общем случае неподвижным будет тот конец отрезка изолированного корня, в которой знак функции f(х) совпадает со знаком второй производной, а за начальное приближение x 0 можно взять точку отрезка [а; b ], в которой f(x 0)×f"’(x 0) < 0.
К примеру, когда f (a) >0, f (b) <0, f"(х)< 0, f"(х)< 0 (рис. .3, б) конец b отрезка [а; b ] является неподвижным.
В случае если f (а)>0, f (b)< 0, f" (х)< 0, f"(x) >0 (рис.3, в), или f (а) <0, f (b) >0, f’ (х) >0, f"’ (x) <0 (рис. 3, г), точка а является неподвижным концом отрезка [а; b ].
Достаточные условия сходимости метода хорд дает такая теорема.
Рисунок 3. – Геометрическая интерпретация метода хорд
Теорема. Пусть на отрезке [а; b ] функция f (х) непрерывна вместе со своими производными второго порядка включительно, причем f(a)×f(b)<0, а производные f" (x) и f" (х) сохраняют свои знаки на [а; b ], тогда существует такая окружность корня х* уравнения f (x) =0, что для любого начального приближения х 0 этой окружности последовательность {х k }, вычисленная по формуле (8), сходится к корню х*.
Метод хорд. - понятие и виды. Классификация и особенности категории "Метод хорд." 2017, 2018.
Пусть 1) функция y=F(x) определена и непрерывна на отрезке . 2) F(a)F(b)<0 Требуется найти корень на отрезке с точностью &... .
При дифференцировании этим методом отмечают ряд точек на вычерченной кривой графика функции, которые соединяют хордами, т.е. заменяют заданную кривую ломаной линией (Рис.2). Принимают следующее допущение: угол наклона касательных в точках, расположенных посередине... .
В некоторых случаях несколько большей скоростью сходимости обладает метод хорд, у которого на втором этапе при выборе очередного приближения внутри отрезка, содержащего корень, учитывается величина невязки на концах отрезка: точка выбирается ближе к тому концу, где... .
Идея метода проиллюстрирована рисунком. Задается интервал , на котором f(x0)f(x1) &... .
В данном методе в качестве приближения выбирается не середина отрезка, а точка пересечения хорды с осью абсцисс. Уравнение хорды АВ, соединяющей концы отрезка: (1) Точка пересечения с осью абсцисс имеет координаты, подставим в (1) и найдем (2). Сравниваем знаки и... .
Если и - приближенные значения корня по недостатку и избытку. 1. Если на, то, при этом. 2. Если на, то, при этом. Пример. Отделить корни аналитически и уточнить их комбинированным методом хорд и касательных с точностью до 0,001. , следовательно, для вычислений...
Численные методы 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 ) = 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).