Решение уравнений методом Ньютона

Федеральное агентство по образованию Российской Федерации

 

Уфимский государственный  авиационный технический университет

 

Кумертауский филиал

 

 

 

Кафедра ПА

 

 

 

 

 

КУРСОВАЯ РАБОТА 
по программированию и основам алгоритмизации 
на тему:

«Решение уравнений методом Ньютона (метод касательных)»

 

 

 

 

 

Выполнил: ст. гр. АТП-109

Кинзябулатов В.Р.

Проверил: ст. преподаватель 
А. Я. Митрофанов

 

Оценка: _________________

Подпись: _________________

Дата: _________________

 

 

 

 

 

СОДЕРЖАНИЕ

 

 

 

Введение

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

 

 

 

1. Математическое описание задачи
1. Сущность метода Ньютона.

Пусть х* есть корень уравнения f(x) = 0, единственный на отрезке [a, b].

Предположим, что каким-либо способом, например, графически определено начальное приближение x0 к корню. В этой точке вычислим значение функции f(x0) и ее производной f ′(x = x0 ) . Значение этой производной равно tgα) (см. рисунок .1) – тангенсу угла наклона соответствующей касательной к оси абсцисс. Точка x1 пересечения этой касательной с осью абсцисс есть следующее приближение к корню (поэтому метод Ньютона и называют методом касательных). Эта точка x1 принимается за новое начальное приближение и процесс повторяется. Из рисунка видно, что процесс сходится к искомому корню x*. Процесс уточнения корня закончится, когда выполнится условие

xk+1 − xk < ε,

где ε – допустимая погрешность определения корня. Из геометрических соображений можно получить расчетную формулу для метода Ньютона в виде:

    (1)

Рисунок 1. Иллюстрация метода касательных (Ньютона)

Метод Ньютона  обладает высокой скоростью сходимости. Обычно абсолютная погрешность нахождения корня ε = 10−5 … 10−6 достигается за 5 – 6 итераций. Однако существенным недостатком этого метода является необходимость вычисления производной функции на каждом шаге итерационного процесса. Это может явиться серьезным препятствием, когда функция вычисляется по очень сложному или трудоемкому алгоритму. Несколько уменьшив скорость сходимости, можно ограничиться вычислением производной только на первой итерации, а затем вести вычисления по формуле (1), полагая f '(xk ) ≈ f '(x0 ) :

 

 

2. Словесно-формульное описание алгоритма

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

1. Описание алгоритма

Описание входной информации: a - левая граница промежутка, b - правая граница промежутка, e - относительная погрешность. Необходимо также задать функцию и ее производную.

Алгоритм:

1. Вводим a,b (левый и правый края промежутка);
2. Вводим e (относительная погрешность);
3. Присваиваем x:=a;
4. Вычисляем значение t:=f(x)/f'(x);
5. Вычисляем значение x:=x-t;
6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7
7. Выводим на экран сообщение: «Корень уравнения x=», выводим х,
8. Завершаем алгоритм.

2. Выполнение алгоритма

Пример № 1.

Найти корни уравнения  на отрезке (1; 3) с точностью 0,001.

 

1. Вводим a,b (левый и правый края промежутка) a:=1; b:=3;
2. Вводим eps (относительная погрешность) eps:=0,001;
3. Присваиваем x:=a (x:=1);
4. Вычисляем значение t:=f(x)/f'(x)= f(1)/f'(1)=-1,3333;
5. Вычисляем значение x:=x-t=1-(-1,3333)=2,3333;
6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

1,3333<=0.001 – нет – переходим к п.4

7. Вычисляем значение t:=f(x)/f'(x)= f(2,3333)/f'(2,3333)=0,3137;
8. Вычисляем значение x:=x-t=2,3333-0,3137=2,0196;
9. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,3137<=0.001 – нет – переходим к п.4

10. Вычисляем значение t:=f(x)/f'(x)= f(2,0196)/f'(2,0196)=0,0195;
11. Вычисляем значение x:=x-t=2,0196-0,0195=2,0001;
12. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0195<=0.001 – нет – переходим к п.4

13. Вычисляем значение t:=f(x)/f'(x)= f(2,0001)/f'(2,0001)=0,0001;
14. Вычисляем значение x:=x-t=2,0001-0,0001=2,0000;
15. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0001<=0.001 – да – переходим к п.7

16. Выводим на экран сообщение: «Корень уравнения x=», выводим 2,0000.
17. Завершаем алгоритм.

 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

 

1. Вводим a,b (левый и правый края промежутка) a:=-1 b:=1;
2. Вводим eps (относительная погрешность) eps:=0,0001;
3. Присваиваем x:=a (x:=-1);
4. Вычисляем значение t:=f(x)/f'(x)= f(-1)/f'(-1)=-0,4621;
5. Вычисляем значение x:=x-t=-1-(-0,4621)=-0,5379;
6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,4621<=0.0001 – нет – переходим к п.4

7. Вычисляем значение t:=f(x)/f'(x)= f(-0,5379)/f'(-0,5379)=0,0291;
8. Вычисляем значение x:=x-t=-0,5379-0,0291=-0,5670;
9. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0291<=0.001 – нет – переходим к п.4

10. Вычисляем значение t:=f(x)/f'(x)= f(-0.5670)/f'(-0.5670)=0,0000;
11. Вычисляем значение x:=x-t=-0.5670-0,0002=-0.5672;
12. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0000<=0.001 – да– переходим к п.7

13. Выводим на экран сообщение: «Корень уравнения x=», выводим -0,5672.
14. Завершаем алгоритм.

 

 

 

3. Выводы по результатам выполнения алгоритма

 

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

 

 

 

3. Блок-схема алгоритма

Запись алгоритмов в виде блок-схем является наиболее наглядным видом  записи. В то же время этот способ является и наиболее громоздким.

1. Блок-схема алгоритма

 

 

 

 

 

 

 

 

 

 

2. Выполнение алгоритма, записанного в виде блок-схемы

 

Пример  № 1. Найти корни уравнения на отрезке (1; 3) с точностью 0,001.

 

Шаг	Блок	Действие	Переход   (связь)	Переменные
1.	1	начало	2
2.	2	Ввод а=1, b=3, eps=0.001	3	а=1 b=3 eps=0.001
3.	3	x:=a	4	x=1
4.	4	t:=f(x)/f'(x) x:=x-t	5	t=-1,3333 x=2,3333
5	5	Проверка условия | t | <=eps	Нет Переход к блоку 4
6	4	t:=f(x)/f'(x) x:=x-t	5	t=0,0195 x=2,0001
7	5	Проверка условия | t | <=eps	Нет Переход к блоку 4
8	4	t:=f(x)/f'(x) x:=x-t	5	t=0,0001 x=2,0000
9	5	Проверка условия | t | <=eps	Да Переход к блоку 6
10	6	Вывод x	7	x=2.0000
11	7	Конец

 

 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

Шаг	Блок	Действие	Переход   (связь)	Переменные
1.	1	начало	2
2.	2	Ввод а=-1, b=1, eps=0.0001	3	а=-1 b=1 eps=0.0001
3.	3	x:=a	4	x=-1
4.	4	t:=f(x)/f'(x) x:=x-t	5	t=-0,4621 x=-0,5379
5	5	Проверка условия | t | <=eps	Нет Переход к блоку 4
6	4	t:=f(x)/f'(x) x:=x-t	5	t=0,0291 x=-0,5670
7	5	Проверка условия | t | <=eps	Нет Переход к блоку 4
8	4	t:=f(x)/f'(x) x:=x-t	5	t=0,0000 x=-0.5672
9	5	Проверка условия | t | <=eps	Да Переход к блоку 6
10	6	Вывод x	7	x=-0.5672
11	7	Конец

 

 

 

 

4. Описание алгоритма на алгоритмическом языке

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

1. Описание алгоритма

Алгоритм Newton;

 

Переменные a,b,eps,t,x,f,f1;

 

НАЧАЛО

 

ПишиСтр (a,b,eps);

 

x:=a;

Повторяй 

t:=f(x)/f1(x);

x:=x-t;

до тех  пор пока не выполнится условие| t | <=eps

ПишиСтр (x);

КОНЕЦ

 

 

 

2. Выполнение алгоритма, записанного на алгоритмическом языке

Пример  № 1. Найти корни уравнения на отрезке (1; 3) с точностью 0,001.

 

№ п/п	Команды	Переменные	На экране
1.	ПишиСтр (a,b,eps)	а=1 b=3 eps=0.001
2.	x:=a	x:=1
3.	t:=f(x)/f'(x) x:=x-t	t=-1,3333 x=2,3333
4	Проверка условия | t | <=eps - нет
5	t:=f(x)/f'(x) x:=x-t	t=0,0195 x=2,0001
6	Проверка условия | t | <=eps - нет
7	t:=f(x)/f'(x) x:=x-t	t=0,0001 x=2,0000
8	Проверка условия | t | <=eps – да
9	ПишиСтр (x)	x=2,0000	2,0000

 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

№ п/п	Команды	Переменные	На экране
1.	ПишиСтр (a,b,eps)	а=-1 b=1 eps=0.0001
2.	x:=a	x:=-1
3.	t:=f(x)/f'(x) x:=x-t	t=-0,4621 x=-0,5379
4	Проверка условия | t | <=eps - нет
5	t:=f(x)/f'(x) x:=x-t	t=0,0291 x=-0,5670
6	Проверка условия | t | <=eps - нет
7	t:=f(x)/f'(x) x:=x-t	t=0,0000 x=-0.5672
8	Проверка условия | t | <=eps – да
9	ПишиСтр (x)	x=-0.5672	-0.5672

 

3. Выводы по результатам выполнения алгоритма

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

 

5. Реализация алгоритма на языке Pascal
1. Краткое описание языка программирования

Язык программирования Pascal был разработан в 1968-1971 гг. Никлаусом  Виртом в Цюрихском Институте информатики (Швейцария), и назван в честь Блеза Паскаля – выдающегося математика, философа и физика 17-го века. Первоначальная цель разработки языка диктовалась необходимостью создания инструмента "для обучения программированию как систематической дисциплине". Однако очень скоро обнаружилась чрезвычайная эффективность языка Pascal в самых разнообразных приложениях, от решения небольших задач численного характера до разработки сложных программных систем - компиляторов, баз данных, операционных систем и т.п. К настоящему времени Pascal принадлежит к группе наиболее распространенных и популярных в мире языков программирования:

• существуют многочисленные реализации языка практически для всех машинных архитектур;
• разработаны десятки диалектов и проблемно-ориентированных расширений языка Pascal;
• обучение программированию и научно-технические публикации в значительной степени базируются на этом языке.