Метод хорд

Идея метода состоит в замене функции f (x) внутри отрезка [ a, b ]линейной функцией (см. рис.7). Точка пересечения x ₁ графика линейной функции и оси абсцисс принимается за значение одной из границ нового отрезка локализации корня, который выбирается так, чтобы выполнялось одно из условий

f (a)· f (x ₁) < 0 или f (x ₁)· f (b) < 0.

Далее процесс повторяется и находится следующее приближение корня x ₂ – точка пересечения графика линейной функции нового отрезка с осью абсцисс.

Для расчёта на каждом шаге абсциссы точки пересечения графика линейной функции и оси 0 x используются выражения вида

или .

Процесс поиска корня продолжается до тех пор, пока не будет выполнено одно из условий окончания вычислений

или ,

где δ _абс и δ _отн – задаваемые абсолютная и относительная разницы между соседними значениями приближения корня, соответственно. Абсолютная погрешность найденного значения корня может быть оценена с помощью неравенства

,

где

, .

При решении практических задач, учитывая предположение о монотонности функции f (x) и её первой производной на отрезке [ a, b ] локализации корня, вместо приведённых формул для M и m используют их приближённые аналоги

, .

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

Пример решения на ПЭВМ в среде Matlab

Пусть надо отыскать все корни уравнения

x ³ – 10 x ² + 25 x – 12 = 0

на отрезке [0,10] с абсолютной погрешностью не хуже 0.001.

Сначала построим график заданной функции на указанном отрезке. Эта операция необходима для локализации корней. Для этого сначала создаётся и сохраняется f.m с формулой для вычисления левой части уравнения:

function y=f(x)

y=x.^3 - 10*x.^2 + 25*x - 12

Затем в окне Command Window задаются команды для построения графика функции. При этом указываются границы изменения аргумента и шаг его изменения, организуется обращение к встроенной функции plot с указанием массивов значений абсцисс и ординат, по которым строится график, а также применяется опция grid для вывода сетки (это можно сделать и интерактивно непосредственно в графическом окне):

x=0:0.01:10

plot(x,f(x)), grid

Получающийся результат работы такой программы показан рис.8. Количество корней в данном случае три, их начальные приближения можно принять в виде 1, 4 и 7.

Для уточнения этих начальных приближений корней и получения

Рис.8.

их значений с заданной погршностью в том же окне Command Window следует последовательно обратиться к функции fzero, встроенной в среду MATLAB, указывая имя функции, где вычисляется левая часть решаемого уравнения, начальные приближения всех трех корней и требуемую погрешность:

fzero(@f,1,0.001)

fzero(@f,4,0.001)

fzero(@f,7,0.001)

Результат вычислений получается в системной переменной ans (см. рис.9). Для увеличения количества выводимых знаков после запятой (по умолчанию выводится 4 знака) можно перед командами вызова функций ввести инструкцию format long.

Встроенная функция fzero обращается к m-файлу, где задана пользователем функция, и использует предложенный Т.Деккером алгоритм, основанный на комбинации методов бисекции, метода секущих и обратной квадратичной интерполяции.

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

Рис.9.

ближения к корню x_{k –2}, x_{k –1} и x_k. По ним строится единственная квадратичная парабола

,

проходящая через точки

.

С помощью уравнения этой параболы находится текущее приближение корня x_{k +1}, как абсцисса точки пересечения параболы c осью 0 x.

Функция fzero определяет точку, где функция меняет знак. Точки, где функция касается оси 0 x, не считаются достоверными корнями. В случае функций без достоверных нулей, эта функция работает до тех пор, пока в качестве значения аргумента уравнения не встретятся бесконечность, неопределённость или комплексное значение. Вместо начального приближения при обращении к функции fzero можно через запятую указать границы интервала локализации искомого корня: fzero(@f,6,7,0.001).

Эта же задача может быть решена методом половинного деления. Программа, реализующая его алгоритм для уточнения первого корня, отрезок локализации которого принят от 0 до 1, может иметь следующий вид:

a=0; левая граница отрезка локализации корня

b=1; правая граница отрезка локализации корня

x=(a+b)/2 середина отрезка

while (x-a)>0.001 0.001 – погрешность поиска корня

if f(x)*f(a)<=0

b =x;

else

a =x;

end

x=(a+b)/2 деление отрезка пополам

end

Результат работы этой программы имеет вид:

x =

0.5000

x =

0.7500

x =

0.6250

x =

0.6875

x =

0.6563

x =

0.6406

..........

..........

x =

0.6270

x =

0.6279

Последовательная замена в программе значений для a и b на 2.5 и 3.5 и на 6 и 7 позволяет уточнить второй и третий корни рассматриваемого уравнения:

x =

2.9990

и

x =

6.3721

Если задаться целью решить рассматриваемое уравнение методом Ньютона–Рафсона, то последовательность действий будет иметь следующий вид. Имея в ранее созданном файле f.m описание левой части уравнения , следует сформировать файл f1.m с описанием её первой производной :

function y=f1(x)

y=3*x.^2 - 20*x + 25;

После этого программа, реализующая уточнение приближённого значения корня, равного 1, методом Ньютона–Рафсона, может быть представлена в виде

x=1; начальное приближение корня

while (abs(f(x)/f1(x))>0.001) 0.001 – погрешность поиска корня

x=x-f(x)/f1(x);

end

x1=x вывод результата в командное окно

Эту программу надо сохранить в файле с именем, например, root.m, и затем запустить его на выполнение. Результат его работы показан ниже:

x1 =

0.6277

Замена в файле root.m начального значение корня последовательно на 4 и 7 при запуске его на выполнение позволяет получить следующие сообщения:

x1 =

3.0000

и

x1 =

6.3723

Эти значения корней с точностью до 10^–3 совпадают со значениями, которые были получены при применении метода половинного деления и встроенной функции fzero.

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

a=0;b=1; границы отрезка локализации

x=a; x1=b;

while (abs(x1-x)>0.001) начало итераций, 0.001 – погрешность поиска корня

k=(f(b)-f(a))/(b-a);

x1=x;

x=(k*a-f(a))/k; вычисление нового приближения корня

if ((f(x)*f(a))>0) выбор границ нового отрезока локализации корня

a=x;

else

b=x;

end

end

x1=x вывод результата в командное окно

Запуск этой программы на выполнение для первоначальных отрезков локализации [0, 1], [2.5, 3.5] и [6, 7] трёх корней исходного уравнения позволяет получить следующие их значения

x1 =

0.6280

x1 =

3.0000

x1 =

6.3722

Для решения этого же уравнения методом простых итераций сначала надо привести исходное уравнений

x ³ – 10 x ² + 25 x – 12 = 0

к виду x = φ (x) так, чтобы функция φ на отрезках [ a, β ] локализации каждого корня подчинялась бы условию сходимости метода

.

Для отрезка [0, 1] исходное уравнение можно преобразовать следующим образом:

.

В этом случае производная правой части будет

.

На отрезке [0, 1] она по модулю всегда меньше 1. Поэтому в качестве начального приближения корня можно взять любое число с этого отрезка, например х = 1.

Для других отрезков локализации корней исходное уравнение можно преобразовать к виду

.

В этом случае параметр релаксации l подбирается из условия сходимости метода

или .

Для отрезка [2.5, 3.5] это условие даёт следующий диапазон параметра релаксации: 0<l<0.24, а для отрезка [6, 7]: –0.063<l<0. В связи с этим можно принять l = 0.2 и l = –0.05 соответственно.

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

x=1;

while abs((12-x^3+10*x^2)/25-x)>0.001

x=(12-x^3+10*x^2)/25;

end

x= x

x=3.5

while abs(0.2*(x^3-10*x^2+25*x-12))>0.001

x=x+0.2*(x^3-10*x^2+25*x-12);

end

x= x

x=7

while abs(0.05*(x^3-10*x^2+25*x-12))>0.001

x=x-0.05*(x^3-10*x^2+25*x-12);

end

x= x

Результатом выполнения этой программы будут следующие значения корней:

x =

0.6289

x =

2.9994

и

x =

6.3715

Дата добавления: 2015-07-08