Метод хорд описание. Численные методы решения нелинейных уравнений

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

Метод простых итераций для уравнения 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).

Пусть на отрезке функция непрерывна, принимает на концах отрезка значение разных знаков, а производная 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.

Заключение

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

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

Проведя исследования по теме курсовой работы "Численные методы. Решение нелинейных уравнений", я добилась поставленных во введении целей. Были подробно рассмотрены методы уточнения корней. К каждому определению и теореме были приведены несколько примеров. Все теоремы доказаны.

Использование различных источников дало возможность полностью раскрыть тему.

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 Метод наискорейшего спуска Методы...

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

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

Рассмотрим более быстрый способ нахождения корня на интервале , в предположении, что 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) заменяется хордой и абсцисса точки пересечения хорды с осью 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.