Этот метод применяется при решении уравнений вида , если корень уравнения отделён, т.е. и выполняются условия:

1) (функция принимает значения разных знаков на концах отрезка );

2) производная сохраняет знак на отрезке (функция либо возрастает, либо убывает на отрезке ).

Первое приближение корня находится по формуле: .

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

Тогда второе приближение вычисляется по формуле:

, если или , если .

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

Геометрическая интерпретация нахождение решения методом хорд:

При решении уравнения методом хорд поводится прямая соединяющая концы отрезка . Из двух точек А и В выбирается х0. Находится точка пересечения хорды с осью OX. Определяется значение функции в точке пересечения и из найденной точки проводится новая хорда. Этот процесс повторяется до получения необходимой точности.

Формула для n-го приближения имеет вид(х0=а, xn-1=b,xn=x):

В методе хорд условием окончания итераций является:

Условие близости двух последовательных приближений: ;

Условие малости невязки (величина F(xn) есть невязка, полученная на n-й итерации, а -число, с заданной точностью которого необходимо найти решение).

Описание алгоритма метода хорд
Шаг 1. Ввод a,b,ε.
Шаг 2. X:=a-f(a)×(b-a)/(f(b)-f(a)).
Шаг 3. Если dF2(b)×F(b)<0, то a:=x;
Если dF2(a)×F(a)<0, то b:=x;
Шаг 4. Пересчитать X по формуле шага 2.
Шаг 5. Выполнять шаг 3, пока abs(b-a)<=eps.
Шаг 4.Вывод результата – x.
Опишем назначение переменных и функций, используемых в процедуре Hord
dF2 – значение второй производной в точке Х
F – значение функции в точке Х
Х0 – начальное значение Х
А – левая граница
В – правая граница
Е – точность вычислений
Fa – значение функции в точке А
Fb - значение функции в точке В
Представим в виде структурной схемы.

Блок схема алгоритма метода хорд:

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

x i =φ(x i -1) , i=1,2,… где i − номер итерации.- последовательное вычисление значений x i по формуле называется итерационным процессом метода простых итераций, а сама формула - формулой итерационного процесса метода.

Алгоритм решения нелинейного уравнения методом
простых итераций:

Если , то итерационный процесс сходящийся .

Условие сходимости

Точное решение x * получить невозможно, так как требуется бесконечный итерационный процесс.

Можно получить приближенное решение, прервав итерационный x i =φ(x i -1) при достижении условия

где ε - заданная точность; i - номер последней итерации.

В большинстве случаев условие завершения итерационного процесса обеспечивает близость значения x i к точному решению:

Геометрическая иллюстрация метода простых итераций:

1) Итерационный процесс для случая 0< <1 xÎ..

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

1 Геометрическое описание метода секущих
2 Алгебраическое описание метода секущих
3 Метод хорд с итерационной формулой
4 Пример использования метода секущих
5 Сходимость метода секущих
6 Критерий и скорость сходимости метода хорд
7 Историческая справка
8 Пример кода
9 Модификации
10 См. также
11 Литература
12 Примечания
13 Ссылки

Геометрическое описание метода секущих

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

Алгебраическое описание метода секущих

Пусть - абсциссы концов хорды, - уравнение секущей, содержащей хорду. Найдем коэффициенты и из системы уравнений:

Вычтем из первого уравнения второе:

Затем найдем коэффициенты и:

Уравнение принимает вид:

Таким образом, теперь можем найти первое приближение к корню, полученное методом секущих:

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

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

Метод хорд с итерационной формулой

Первые три итерации метода хорд. Синим нарисована функция f(x), красными проводятся хорды.

Иногда методом секущих называют метод с итерационной формулой

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

Пример использования метода секущих

Решим уравнение методом секущих. Зададимся точностью ε=0.001 и возьмём в качестве начальных приближений и концы отрезка, на котором отделён корень: и, числовые значения и выбраны произвольно. Вычисления ведутся до тех пор, пока выполняется неравенство.

В нашем примере, в значение подставляется, а в значение подставляется. Значение это будет числовое значение полученное по этой формуле. дальнейшем подставляем в формулу в значение, а в значение.

По этой формуле последовательно получаем (подчёркнуты верные значащие цифры): (картинка из метода хорд, но не секущих, просьба разделить разделы)

Метод секущих. Первый случай; ; ; ; ; ; ; ; ; ;

Проверим, что метод работает и в том случае, если и выбраны по одну и ту же сторону от корня (то есть, если корень не отделён на отрезке между начальными приближениями). Возьмём для того же уравнения и. Тогда: (картинка уже не из метода секущих, а из метода дихотомии)

Метод секущих. Второй случай; ; ; ; ; ; ; ;

Мы получили то же значение корня за то же число итераций.

Сходимость метода секущих

Итерации метода секущих сходятся к корню, если начальные величины and достаточно близки к корню. Метод секущих является быстрым. Порядок сходимости α, равен золотому сечению

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

Этот результат справедлив, если дважды дифференцируема и корень не является кратным - .

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

Критерий и скорость сходимости метода хорд

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

Историческая справка

Первым, кто смог найти приближённые решения кубических уравнений, был Диофант, тем самым заложив основу метода хорд. Сохранившиеся работы Диофанта сообщают об этом. Однако первым, кто понял его методы, был Ферма в XVII веке, а первым, кто дал объяснение методу хорд, был Ньютон (1670-е гг.).

Пример кода

Пример функции вычисления корня методом хорд на отрезке на Си/Си++.

Double f(double x) { return sqrt(fabs(cos(x))) - x; // Заменить функцией, корни которой мы ищем } // a, b - пределы хорды, epsilon - необходимая погрешность double findRoot(double a, double b, double epsilon) { while(fabs(b - a) > epsilon) { a = b - (b - a) * f(b)/(f(b) - f(a)); b = a - (a - b) * f(a)/(f(a) - f(b)); } // a - i-1, b - i-тый члены return b; }

Модификации

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

См. также

Метод Ньютона (метод касательных)
Метод простой итерации
Обратная параболическая интерполяция

Литература

Демидович Б.П. и Марон И.А. Основы вычислительной математики. - Наука, 1970. - С. 664.
Бахвалов, Жидков, Кобельков. Численные методы. - Наука. - ISBN 5-94774-060-5.

Примечания

Алгебра
Математика и её история. Джон Стиллвелл

Ссылки

Решение уравнений методом хорд онлайн
«Методы решения алгебраических уравнений» на сайте www.petrsu.ru
«Методы дихотомии» на сайте www.epikoiros.narod.ru
Ю. Губарь, Курс «Введение в математическое моделирование» Лекция 4: Численные методы решения нелинейных уравнений // Интуит.ру, 15.03.2007

метод хорд, метод хорд gif, метод хорд онлайн, метод хорд пример

Метод хорд Информацию О

В методе секущих, иначе называемом МЕТОДЕ ХОРД, приближенное значение производной в формуле (3.7) определяется по двум последовательным приближениям
и
по соотношению

(3.9)

что приводит к замене касательной в точке
секущей, проведенной через две точки кривойy = f (x ) (рис.9) или, что то же самое, - к аппроксимации функции f (x ) на этом интервале линейной функцией.

Условия сходимости метода секущих аналогичны условиям сходимости метода Ньютона. Порядок сходимости метода секущих определяется соотношениями

где
.

Рисунок 9 – Геометрическая интерпретация метода секущих

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

3.1.5. Метод парабол

Рассмотренный метод секущих можно интерпретировать как метод, в котором на каждой итерации исходная функция аппроксимируется линейной функцией (секущей), построенной по двум точкам, принадлежащим f (x ) . Развивая далее идеи аппроксимации, можно для построения итерационных формул использовать информацию о функции в нескольких точках, предшествующих точке
В методе парабол по трем последовательным приближениямстроится многочлен второй степени (парабола), приближающий исходную функцию. Иначе этот метод называют МЕТОДОМ МЮЛЛЕРА или методом КВАДРАТИЧНОЙ ИНТЕРПОЛЯЦИИ. За новое приближение берется обычно ближайший к
корень соответствующего квадратного уравнения. Геометрическая интерпретация метода парабол дана на рис.10.

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

где p = 1,839.

Рисунок 10 – Геометрическая интерпретация метода парабол

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

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

Лекция № 8

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

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

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

Систему нелинейных уравнений запишем в векторной форме

f (x ) = 0 (3.10)

где
- вектор-столбец неизвестных,- вектор-столбец функций. В методе простой итерации система (3.10) приводится к эквивалентной системе вида
гдеили

(3.11)

Полагая известным начальное приближение для корня построим итерационный процессили

(3.12)

Рассмотрим поведение вектора погрешности

полагая, что погрешность – величина малая. Для компонент вектора x можем записать

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

,
(3.13)

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

Если обозначить матрицу производных системы функций
для
(МАТРИЦУ ЯКОБИ) ЧЕРЕЗ

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

(3.14)

Достаточное условие сходимости итерационного процесса (3.12) формулируется следующим образом: если какая-либо норма матрицы
согласованная с рассматриваемой нормой вектораx , меньше единицы, то метод итераций сходится, Условие сходимости
есть обобщение на случай нелинейной системы условия (3.5) для одного уравнения.

Метод итераций Зейделя

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

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

Метод Ньютона

Основная идея метода Ньютона – решение системы нелинейных уравнений f (x ) = 0 - сводится к решению последовательности линейных задач, дающих в пределе решение исходной задачи. Линейная задача получается путем выделения из нелинейных уравнений главной линейной части.

Рассмотрим погрешность вычисления корня на k -й итерации
гдеПолагая, что функциинепрерывны и дифференцируемы в окрестности корня и

) – малые величины, разложимв ряд Тейлора, сохранив лишь линейную часть разложения. Получим систему уравнений

(3.15)

линейную относительно компонент вектора погрешностей. Если использовать эту систему для отыскания компонент вектора погрешностей, то в силу приближенности системы (3.15) – оставлена лишь линейная часть – найденное значение вектора погрешности будет лишь приближенным, Тогда при подстановке полученного решения в соотношение
будет иметь вместо приближенное уточненное значение корня, которое обозначим через
Используя запись системы (3.15) в виде

где - матрица производных системы функций(матрица Якоби), можем записать итерационный процесс для нахождения вектораx :

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

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

На каждой итерации метода Ньютона требуется вычислять матрицу производных
и решать систему линейных уравнений (3.15). Можно попытаться уменьшить объем вычислений за счет отказа от вычисления матрицы
на каждой итерации и использования на всех итерациях постоянного значения
вычисленного по начальному приближению. Напомним, что при этом может быть дополнительно существенно уменьшен объем вычислений, если для решения последовательности линейных систем использовать алгоритм, позволяющий выполнить преобразование матрицы
к верхней треугольной только один раз. Следует иметь в виду, однако, что, во-первых, указанная модификация метода Ньютона гарантирует лишь линейную сходимость итераций (против квадратичной в окрестности корня в методе Ньютона) и, во-вторых, константа в линейной зависимости погрешности при неудачном выборе начального приближения может оказаться весьма большой и сходимость будет медленней. Таким образом, увеличивается число итераций, необходимое для достижения заданной точности, и уменьшение общего объема вычислений не гарантировано.

Ускорение сходимости по Эйткену

Предположим, что отношение есть величина постоянная и неизменная в процессе итераций. Тогда

Из этого соотношения следует, что

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

Лекция № 9

4. МЕТОДЫ ПРИБЛИЖЕНИЯ И АППРОКСИМАЦИИ ФУНКЦИЙ

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

При нахождении нулей функции f , для которой вычисление f"(x) затруднено, часто лучшим выбором, чем метод Ньютона, является метод секущих. В этом алгоритме начинают с двумя исходными числами x 1 и х 2 . На каждом шаге x k+1 получают из x k и x k-1 как единственный нуль линейной функции, принимающей значения f(x k) в x k и f(x k-1) в x k-1 . Эта линейная функция представляет секущую к кривой у = f(х), проходящую через ее точки с абсциссами x k и x k-1 - отсюда название метод секущих.

Пусть -- абсциссы концов хорды, -- уравнение секущей, содержащей хорду. Найдем коэффициенты и из системы уравнений:

Вычтем из первого уравнения второе:

Затем найдем коэффициенты и:

Уравнение принимает вид:

Таким образом, теперь можем найти первое приближение к корню, полученное методом секущих:

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

Пример решения задачи методом секущих

В Delphi напишем программу для расчета корней уравнений методом секущих:

procedure TForm1.Button1Click(Sender: TObject);

var ck1, x0, x1, x2, eps:real;

x1:=StrToFloat(Form1.Edit1.Text);

x2:=StrToFloat(Form1.Edit2.Text);

eps:=StrToFloat(Form1.Edite.Text);

{уточнения корня по итерационной форме}

x2:=x1-(x0-x1)*f(x1)/(f(x0)-f(x1));

until abs(x2-x1)

{Заключительные вычисления}

ck2:= (ck1-c01)/2+c02;

ck3:= (-ck1+c01)/2+c03 ;

ck4:=(-2*ck1+2*c01)/2+c04;

{Вывод результатов в поле Memo}

Form1.Memo2.clear ;

Form1.Memo2.Lines.Add ("Метод деления пополам");

Form1.Memo2.Lines.Add

("ck1 =" + FloatToStr(ck1));

Form1.Memo2.Lines.Add

("ck2 =" + FloatToStr(ck2));

Form1.Memo2.Lines.Add

("ck3 =" + FloatToStr(ck3));

Form1.Memo2.Lines.Add

("ck4 =" + FloatToStr(ck4));

Метод секущих (метод хорд)

В этом и следующем разделе рассмотрим модификации метода Ньютона.

Как видно из формулы (2.13), метод Ньютона требует для своей реализации вычисления производной, что ограничивает его применение. Метод секущих лишен этого недостатка. Если производную заменить ее приближением:

f "(x n ) ,

то вместо формулы (2.13) получим

x n +1 = x n -. . (2.20)

Это означает, что касательные заменены секущими. Метод секущих является двухшаговым методом, для вычисления приближения x n +1 необходимо вычислить два предыдущих приближения x n и x n - 1 , и, в частности, на первой итерации надо знать два начальных значения x 0 и x 1 .

Формула (2.20) является расчетной формулой метода секущих . На рис. 2.9 приведена геометрическая иллюстрация метода секущих.

Очередное приближение x n +1 получается как точка пересечения с осью OX секущей, соединяющей точки графика функции f (x ) с координатами (x n -1 , f (x n - 1)) и (x n , f (x n)).

Сходимость метода . Сходимость метода секущих устанавливает следующая теорема.

Теорема 2.4 Пусть x * - простой корень уравнения f (x ) = 0, и в некоторой окрестности этого корня функция f дважды непрерывно дифференцируема, причем f" (x ) 0. Тогда найдется такая малая -окрестность корня x * , что при произвольном выборе начальных приближений x 0 и x 1 из этой окрестности итерационная последовательность, определенная по формуле (2.20) сходится и справедлива оценка:

|x n + 1 - x * | C |x n - x * | p , n 0, p = 1.618. (2.21)

Сравнение оценок (2.15) и (2.21) показывает, что p < 2, и метод секущих сходится медленнее, чем метод Ньютона. Но в методе Ньютона на каждой итерации надо вычислять и функцию, и производную, а в методе секущих - только функцию. Поэтому при одинаковом объеме вычислений в методе секущих можно сделать примерно вдвое больше итераций и получить более высокую точность.

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

Критерий окончания. Критерий окончания итераций метода секущих такой же, как и для метода Ньютона. При заданной точности >

|x n - x n - 1 | < . (2.22)

Пример 2.4.

Применим метод секущих для вычисления положительного корня уравнения 4(1 - x 2) - e x = 0 с точностью = 10 -3 .

Корень этого уравнения находится на отрезке , так как f (0) = 3 > 0, а f (1) = -e < 0. Подсчитаем вторую производную функции: f "(x ) = -8 - e x . Условие f (x )f " (x ) 0 выполняется для точки b = 1. В качестве начального приближения возьмем x 0 = b = 1. В качестве второго начального значения возьмем x 1 = 0.5. Проведем вычисления по расчетной формуле (2.20). Результаты приведены в табл. 2.4.

Таблица 2.4

	x n

Метод ложного положения

Рассмотрим еще одну модификацию метода Ньютона.

Пусть известно, что простой корень x * уравнения f (x ) = 0 находится на отрезке [a, b ] и на одном из концов отрезка выполняется условие f (x )f" (x ) 0. Возьмем эту точку в качестве начального приближения. Пусть для определенности это будет b . Положим x 0 = a. Будем проводить из точки B = (b, f (b )) прямые через расположенные на графике функции точки B n с координатами (x n , f (x n ), n = 0, 1, … . Абсцисса точки пересечения такой прямой с осью OX есть очередное приближение x n+ 1 .

Геометрическая иллюстрация метода приведена на рис. 2.10.

Прямые на этом рисунке заменяют касательные в методе Ньютона (рис. 2.8). Эта замена основана на приближенном равенстве

f "(x n ) . (2.23)

Заменим в расчетной формуле Ньютона (2.13) производную f "(x n ) правой частью приближенного равенства (2.23). В результате получим расчетную формулу метода ложного положения :

x n +1 = x n -.. (2.24)

Метод ложного положения обладает только линейной сходимостью. Сходимость тем выше, чем меньше отрезок [a, b ].

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

|x n - x n - 1 | < . (2.25)

Пример 2.5.

Применим метод ложного положения для вычисления корня уравнения x 3 + 2x - 11 = 0 с точностью = 10 -3 .

Корень этого уравнения находится на отрезке , так как f (1) = -8 < 0, а f (2) = 1 > 0. Для ускорения сходимости возьмем более узкий отрезок , поскольку f (1.9) < 0, а f (2) > 0. Вторая производная функции f (x ) = x 3 + 2x - 11 равна 6x. Условие f (x )f" (x ) 0 выполняется для точки b = 2. В качестве начального приближения возьмем x 0 = a = 1.9. По формуле (2.24) имеем