Решение уравнений в виде процедуры-подпрограммы

• Анализ предметной области (теория). Постановка задачи
• Метод простых итераций
• Метод Ньютона (метод касательных)
• Метод хорд
• Спецификация
• Метод решения
• Организация данных
• Описание процедур и функций
• Общий алгоритм
• Графический способ нахождения интервала изоляции корня
• Контрольный пример
• Текст программы
• Список используемой литературы

Анализ предметной области (теория). Постановка задачи

Дано нелинейное уравнение 1 — 5X + X³ на заданном отрезке [0,1] c заданной точностью =0.0001, нужно реализовать его решение в виде процедуры-подпрограммы следующими методами:

1. методом хорд;

2. методом касательных (Ньютона);

3. методом простой итерации;

4. методом половинного деления.

Заданное уравнение: 1 — 5X + X³ можно решить двумя методами решения уравнения:

1. Графический метод отделения корней уравнения;

2. Основные методы уточнения корней уравнения.

Основные методы уточнения корней уравнения

Метод половинного деления.

Дано нелинейное уравнение: f (x) = 0

Найти корень уравнения, принадлежащий интервалу [a, b], с заданной точностью .

Для уточнения корня методом половинного деления необходимо выполнить следующие операции:

1. Делим интервал пополам:

— координаты середины отрезка

2. В качестве нового интервала изоляции принимаем ту половину интервала, на концах которого функция имеет разные знаки (рис.1) .

Рис. 1. Графический метод отделения корней уравнения методом половинного деления

Для этого:

a) Вычисляем значение функции f (x) в точках a и t.

b) Проверяем: если f (a) f (t) < 0, то корень находится в левой половине интервала [a, b] (рис. 1. а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t.

c) Если f (a) f (t) < 0 не выполняется, то корень находится в правой половине интервала [a, b] (рис. 1. б). Тогда отбрасываем левую половину и делаем переприсвоение a=t. В обоих случаях мы получим новый интервал [a, b] в 2 раза меньший предыдущего.

3. Процесс, начиная с пункта 1, циклически повторяем до тех пор, пока длина интервала [a, b] не станет равной либо меньшей заданной точности, т. е.

Рис. 2. Схема алгоритма уточнения корней по методу половинного деления

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

В ряде случаев весьма удобным приемом уточнения корня уравнения является метод последовательных приближений (метод итераций).

Пусть с точностью необходимо найти корень уравнения f (x) =0, принадлежащий интервалу изоляции [a, b]. Функция f (x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение f (x) =0 должно быть приведено к виду

X= ц (x)

В качестве начального приближения 0 выбираем любую точку интервала [a, b].

Далее итерационный процесс поиска корня строится по схеме:

x₁= ц (x₀)

x₂= ц (x₁)

x_n= ц (x_n-1)

В результате итерационный процесс поиска реализуется рекуррентной формулой (4.3). Процесс поиска прекращается, как только выполняется условие

или число итераций превысит заданное число N.

Для того, чтобы последовательность х₁, х₂,…, х_n приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости:

Рис. 3. Геометрический смысл метода

Переходим к построению схемы алгоритма (рис.4). Вычисление функции оформим в виде подпрограммы.

Рис. 4. Схема алгоритма уточнения корня методом итераций

Метод Ньютона (метод касательных)

Рассмотренные ранее методы решения нелинейных уравнений являются методами прямого поиска. В них для нахождения корня используется нахождение значения функции в различных точках интервала [a, b].

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

Дано нелинейное уравнение: f (x) =0

Найти корень на интервале [a, b] с точностью .

Метод Ньютона основан на замене исходной функции f (x), на каждом шаге поиска касательной, проведенной к этой функции. Пересечение касательной с осью Х дает приближение корня (Рис.5) .

Выберем начальную точку x₀=b (конец интервала изоляции). Находим значение функции в этой точке и проводим к ней касательную, пересечение которой с осью Х дает нам первое приближение корня x₁.

Рис. 5. Графический способ отделения корней методом касательных

x₁ = x₀ — h_0,где,

Поэтому

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой

Процесс поиска продолжаем до тех пор, пока не выполнится условие:

Упростим условие (4.7), исходя из (4.6). Получим:

Метод обеспечивает быструю сходимость, если выполняется условие:

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

Рис. 6. Схема алгоритма уточнения корня методом Ньютона

Метод хорд

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

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т. е. z=a, тогда начальная точка х₀=b (рис.7а) ;

б) при фиксированном правом конце хорд, т. е. z=b, тогда начальная точка х₀=a (рис.7б) ;

Рис. 7. (а, б) Графический способ отделения корней методом хорд

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а)

для случая б)

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

Метод обеспечивает быструю сходимость, если f (z) f" (z) > 0, т. е. хорды фиксируются в том конце интервала [a, b], где знаки функции f (z) и ее кривизны f" (z) совпадают.

Рис. 8. Схема алгоритма уточнения корня методом хорд

Спецификация

Входные данные:

· E (точность, с которой должен быть вычислен результат)

· a (левая граница промежутка)

· b (правая граница промежутка)

Выходные данные:

· Меню с предлагаемыми методами решения уравнения.

Программа должна:

· Запросить входные данные

· Вывести меню с предлагаемыми методами решения.

· Вывести численное значение результата и количество итераций.

Метод решения

Задачу о нелинейном уравнении можно разбить на три блока:

блок ввода

блок выбора метода решения

блок вывода результата

И реализовать его решение следующими методами:

1. методом двойного деления;

2. методом хорд;

3. методом касательных (Ньютона);

4. методом простой итерации.

уравнение алгоритм программа корень

Организация данных

A, — Левая граница отрезка

B, — Правая граница отрезка

EPS, — Точность нахождения корня =10 ^{- N}

X: real; - Для записи конечного результата вычисления

k: byte; - Число итераций

с: real-Середина отрезка

x0: real-Задаваемый корень

Описание процедур и функций

function f (X: real): real; - функция вычисления уравнения 1 — 5X + X³

на заданном отрезке [0,1].

function df (X: real): real; - функция вычисления производной.

function fi (x: real): real; - функция вычисления уравнения вида х= (х). (1).

function d2f (x: real): real; - функция вычисления двойной производной.

procedure del₂ (a, b, eps: real; var x: real; var k: integer); - процедура вычисления корня и количества итераций нелинейного уравнения 1 — 5X + X³ на заданном отрезке [0,1] методом двойного деления.

procedure simp_iter (a, b, eps: real; var x: real; var k: integer); - процедура вычисления корня и количества итераций нелинейного уравнения 1 — 5X + X³ на заданном отрезке [0,1] методом простых итераций.

procedure kasat (x0,eps: real; var x: real; var k: integer); - процедура вычисления корня и количества итераций нелинейного уравнения 1 — 5X + X³ на заданном отрезке [0,1] методом касательных.

procedure xord (a, b, eps: real; var x: real; var k: integer); - процедура вычисления корня и количества итераций нелинейного уравнения 1 — 5X + X³ на заданном отрезке [0,1] методом хорд.

Общий алгоритм

Рис. 9. Блок-схема работы программы.

Графический способ нахождения интервала изоляции корня

Уравнение 1 — 5X + X³ на заданном отрезке [0,1] представим в виде уравнения X³ = 5X-1 и уравнения Y = 5X-1

Точка пересечения и есть решение уравнения 1 — 5X + X3 на заданном отрезке [0,1]

Контрольный пример

Рисунок 1

Рисунок 2

Рисунок 3

Рисунок 4

Рисунок 5

Рисунок 6

Программа выводит меню. Пользователь должен выбрать 1 пункт меню, чтобы ввести точность (Рис.1), после того как пользователь вводит точность (Рис.2) и после нажатия клавиши Enter, программа выводит меню заново. Теперь пользователь может выбрать в меню любой из методов (Рис. 3, Рис. 4, Рис. 5,Рис.6, Рис.7):

Методом двойного деления;

Методом простых итераций;

Методом касательных;

Методом хорд.

В ходе работы программы получены следующие результаты:

Вывод: Наиболее быстрыми и эффективными методами решения нелинейного уравнения 1 — 5X + X³ на заданном отрезке [0,1] c заданной точностью, являются: метод простых итераций и метод касательных.

Текст программы

program Projectmy;

{$APPTYPE CONSOLE}

uses

SysUtils;

var

x, a, b, eps: real;

n, i: integer;

function f (x: real): real;

begin

f: =1−5*x+x*x*x; end;

function fi (x: real): real;

begin

fi: = (x*x*x+1) /5;

end;

function df (x: real): real;

begin

df: =3*x*x-5;

end;

function d2f (x: real): real;

begin

d2f: =6*x*x;

end;

Procedure del₂ (a, b, eps: real; var x: real; var k: integer);

var

c, ya, yc: real;

begin

k: =0;

ya: =f (a);

while b-a>eps do

begin

k: =k+1;

c: =0.5* (a+b);

yc: =f (c);

if ya*yc>0 then

begin

a: =c;

ya: =yc;

end

else b: =c;

end;

x: =0.5* (a+b);

end;

Procedure simp_iter (x0,eps: real; var x: real; var k: integer);

begin

k: =0;

x: =fi (x0);

while abs (x-x0) >=eps do

begin

k: =k+1;

x0: =x;

x: =fi (x0);

end;

end;

Procedure kasat (x0,eps: real; var x: real; var k: integer);

begin

k: =0;

x: =x0-f (x0) /df (x0);

while abs (x-x0) >=eps do

begin

k: =k+1;

x0: =x;

x: =x0-f (x0) /df (x0);

end;

end;

Procedure xord (a, b, eps: real; var x: real; var k: integer);

var

xk, fx, fk, h: real;

begin

k: =0;

if f (a) *d2f (a) >0

then begin xk: =a; x: =b end

else begin xk: =b; x: =a end;

fk: =f (xk);

repeat

k: =k+1;

fx: =f (x);

h: =fx* (x-xk) / (fx-fk);

x: =x-h;

until abs (h)

end;

procedure menu (var i: integer);

begin

writeln ('1 — Vvedite eps');

writeln ('2 — Metod polovinogo deleniay');

writeln ('3 — Metod iter');

writeln ('4 — Metod kasatelnix');

writeln ('5 — Metod xord');

writeln ('6 — exit');

repeat

writeln (' ENTER: ');

readln (i);

until (i>0) and (i<7);

end;

begin

a: =0;

b: =1;

while true do

begin

menu (i);

case i of

1: begin

writeln ('vvedute eps');

readln (eps);

end;

2: begin

del₂ (a, b, eps, x, n);

writeln ('x0=', x: 10: 8,' f (x0) =', f (x): 10: 8,' n=', n); end;

3: begin

simp_iter (a, eps, x, n);

writeln ('x0=', x: 10: 8,' f (x0) =', f (x): 10: 8,' n=', n);

end;

4: begin

kasat (a, eps, x, n);

writeln ('x0=', x: 10: 8,' f (x0) =', f (x): 10: 8,' n=', n);

end;

5: begin

xord (a, b, eps, x, n);

writeln ('x0=', x: 10: 8,' f (x0) =', f (x): 10: 8,' n=', n);

end;

6: begin

exit;

end;

end;

end;

readln;

readln;

end.

Список используемой литературы

1. Методические указания по подготовке отчета по учебной практике.

2. Трауб Дж. Итерационные методы решения уравнений. — М.: Мир, 1985.258 с.

3. Фаронов В. В. Программирование на персональных ЭВМ в среде Турбо-Паскаль. М.: Изд-во МГТУ, 1990. — 446 с.

4.А. М. Епанешников, В. А. Епанешников. Программирование в среде Turbo Pascal 7.0. Издательство. Диалог-МИФИ, 2004.368 с.

5. http://bestpupils.com/index. php? option=com_wrapper&view=

wrapper&Itemid=111